Coverage-preserving sparsification of overlap graphs for long-read assembly

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Read-overlap graphs are essential for de novo genome assembly.
• String graph models are widely used for graph sparsification to improve assembly contiguity.
• Coverage preservation is critical, especially for complex genomes, to avoid losing haplotype information.

Purpose of the Study:

• To develop a theoretical framework for analyzing coverage-preserving properties of graph models in genome assembly.
• To identify limitations of the standard string graph model regarding coverage preservation.
• To propose practical heuristics for retaining essential contained reads and mitigating coverage gaps.

Main Methods:

• Developed a novel theoretical framework to analyze coverage-preserving properties of graph models.
• Proved de Bruijn and overlap graphs are coverage-preserving.
• Demonstrated the standard string graph model's deficiency and identified contained read removal as a cause of coverage gaps.
• Proposed and validated heuristics for retaining a small fraction of contained reads.

Main Results:

• The standard string graph model is not guaranteed to be coverage-preserving.
• Ignoring contained reads can introduce significant coverage gaps (e.g., 50 gaps on average for HG002 nanopore data).
• Proposed heuristics effectively close most coverage gaps by retaining only 1-2% of contained reads.

Conclusions:

• The standard string graph model requires modifications to ensure coverage preservation.
• The proposed heuristics offer a practical solution to prevent coverage gaps in genome assembly.
• This work enhances the reliability of de novo genome assembly for complex genomic datasets.