LGH: A Fast and Accurate Algorithm for Single Individual Haplotyping Based on a Two-Locus Linkage Graph

Area of Science:

• Genetics and Genomics
• Bioinformatics
• Computational Biology

Background:

• Phased haplotype information is essential for understanding genetic variations between individuals.
• The single individual haplotyping (SIH) problem involves reconstructing haplotypes from DNA fragments using computational algorithms.

Purpose of the Study:

• To develop a fast and accurate heuristic algorithm for solving the single individual haplotyping problem.
• To improve the reconstruction of haplotype pairs from sequenced DNA fragments.

Main Methods:

• Encoding aligned DNA fragments into a two-locus linkage graph.
• Applying a heuristic algorithm based on vertex labeling to find minimum weight edge labelings.
• Utilizing an adapted breadth-first search for error-tolerant component detection and iterative graph condensation.

Main Results:

• The developed heuristic algorithm successfully reconstructs haplotype pairs.
• The algorithm demonstrates higher accuracy and speed compared to five existing SIH algorithms in experiments.
• Sequencing errors are corrected, and edge weights are adjusted during the process.

Conclusions:

• The proposed vertex labeling approach provides an effective solution for the single individual haplotyping problem.
• This algorithm offers a significant advancement in computational methods for genetic analysis and haplotype reconstruction.