In-silico read normalization using Set Multi-Cover optimization

De Bruijn graph is a common assembly data structure. But, with the advances in deep sequencing technologies, assembling high coverage datasets has become a computational challenge. Read normalization, a lossy read filtering approach, is widely applied to reduce resource requirements. Current normalization algorithms, though efficient, provide no guarantee to preserve important k-mers having low abundance. Here normalization is phrased as a Set Multi Cover problem on n reads and a heuristic algorithm is proposed, named ORNA. ORNA normalizes to the minimum number of reads required to retain all k-mers and its relative abundance information. Hence, no connection information from the original graph is lost. ORNA was compared against two other normalization algorithms and was found to be performing better in many cases. Though this work is based on RNA-seq data, ORNA can also be applied for other non-uniform datasets