A fast and accurate algorithm for single individual haplotyping

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Human genome sequencing typically provides genotype data, mixing paternal and maternal haplotypes.
• Phased haplotype information is crucial for understanding genetic variations and enhancing genome-wide association studies.
• Single Individual Haplotyping algorithms reconstruct haplotypes from DNA fragments, a practical approach with advancing sequencing technology.

Purpose of the Study:

• To develop a novel optimization model for single individual haplotyping.
• To generalize existing haplotyping models like Minimum Error Correction (MEC) and Maximum Fragments Cut (MFC).
• To create an efficient algorithm for solving the proposed haplotyping model.

Main Methods:

• Proposed the Balanced Optimal Partition (BOP) model, combining "errors corrected" and "fragments cut" measures.
• Developed a heuristic dynamic programming algorithm named H-BOP to solve the BOP model.
• Implemented a strategy to limit intermediate solutions to a small integer k for efficiency.

Main Results:

• The BOP model generalizes MEC and MFC, allowing flexibility through parameter tuning.
• The H-BOP algorithm demonstrated superior speed and accuracy compared to the state-of-the-art ReFHap algorithm in simulations and real data.
• H-BOP exhibits linear time complexity concerning input size, ensuring scalability for large datasets.

Conclusions:

• H-BOP provides an efficient and accurate solution for single individual haplotyping.
• The algorithm scales well, making it suitable for large-scale genomic data analysis.
• The H-BOP code is publicly available upon request.