Haplotype-aware long-read error correction

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Long-read sequencing technologies generate crucial data for genome assembly.
• Accurate error correction of these reads is vital, especially for organisms with ploidy greater than one.
• Existing haplotype-aware correction methods often rely on heuristics or deep learning, lacking a rigorous foundation.

Purpose of the Study:

• To develop a mathematically grounded framework for haplotype-aware long read error correction in de novo genome assembly.
• To address the challenge of preserving haplotype-specific variations during read correction without a reference genome.

Main Methods:

• Formulated the problem within the minimum error correction framework, extending from reference-based haplotype phasing.
• Proved the NP-hard nature of the de novo error correction problem.
• Developed practical heuristics to enable scaling of the exact algorithm for large datasets.

Main Results:

• The proposed method achieves accuracy comparable to current state-of-the-art techniques.
• Demonstrated effectiveness on PacBio HiFi sequencing data from human and plant genomes.
• The implementation is publicly available for use.

Conclusions:

• The developed rigorous formulation and heuristic approach provide an effective solution for haplotype-aware long read error correction.
• This work advances de novo genome assembly by accurately preserving haplotype variations in complex genomes.