Efficient inference of haplotypes from genotypes on a pedigree

Area of Science:

• Computational Biology
• Genetics
• Bioinformatics

Background:

• Haplotype reconstruction is crucial for understanding genetic inheritance patterns.
• Existing methods face challenges with large pedigrees and numerous markers.
• The computational complexity of finding minimum-recombinant haplotype configurations was previously unknown.

Purpose of the Study:

• To establish the computational complexity of the minimum-recombinant haplotype configuration (MRHC) problem.
• To develop efficient algorithms for haplotype reconstruction in large pedigrees.
• To provide a practical tool for large-scale haplotype inference.

Main Methods:

• Proved the NP-hardness of the MRHC problem.
• Developed an iterative block-extension algorithm for efficient haplotype reconstruction.
• Created a polynomial-time exact algorithm for zero-recombinant scenarios using linear algebra over Z2.

Main Results:

• The MRHC problem is NP-hard, indicating inherent computational difficulty.
• The block-extension algorithm (PedPhase) demonstrates high efficiency and accuracy on simulated and real data.
• The zero-recombinant algorithm precisely identifies all feasible haplotype configurations.

Conclusions:

• Haplotype reconstruction is computationally challenging but solvable with efficient algorithms.
• PedPhase is a valuable tool for large-scale haplotype inference, particularly for datasets with low recombination rates.
• The study provides both theoretical complexity insights and practical algorithmic solutions for haplotype reconstruction.