In silico read normalization using set multi-cover optimization.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• De Bruijn graphs are essential for sequencing data assembly.
• High-throughput sequencing generates large datasets, posing computational challenges for assembly.
• Existing read normalization methods may discard critical k-mers, impacting graph connectivity and assembly accuracy.

Purpose of the Study:

• To develop a read normalization algorithm that preserves all k-mers and their relative abundances.
• To address the computational challenges of assembling high-coverage sequencing data.
• To improve genome assembly quality and enable the discovery of novel transcripts.

Main Methods:

• Normalization is framed as a set multi-cover problem.
• A heuristic algorithm, Optimized Read Normalization Algorithm (ORNA), is proposed.
• ORNA identifies the minimum set of reads to retain all k-mers and their abundances.

Main Results:

• ORNA preserves all k-mers and graph connections from the original dataset.
• Tested on RNA-seq data, ORNA outperforms existing normalization algorithms.
• Normalizing error-corrected data yields more accurate assemblies.
• ORNA enables the prediction of novel transcripts by combining datasets.
• The algorithm offers significant dataset reduction (1-30%) with minimal quality loss.

Conclusions:

• ORNA is an effective and general-purpose normalization tool for sequencing data.
• The algorithm enhances genome assembly accuracy and facilitates novel transcript discovery.
• ORNA provides a computationally efficient solution for handling large sequencing datasets.