Efficient haplotype inference from pedigrees with missing data using linear systems with disjoint-set data structures

Area of Science:

• Computational Biology
• Genetics
• Bioinformatics

Background:

• Haplotype inference from pedigree data is crucial for genetic studies.
• The zero recombination assumption is valid for tightly linked markers like single nucleotide polymorphisms (SNPs).
• Existing methods may lack efficiency for complex pedigrees or large datasets.

Purpose of the Study:

• To develop a mathematically rigorous and efficient algorithm for haplotype inference under the zero recombination model.
• To improve upon existing algorithms in terms of speed and accuracy.
• To handle complex pedigree structures, including loops and missing data.

Main Methods:

• Formulating genotype constraints as a linear system of inheritance variables.
• Utilizing disjoint-set data structures for efficient constraint detection and consistency checking.
• Extending the algorithm to accommodate looped pedigrees and missing genotypic data.

Main Results:

• Achieved nearly linear time complexity O(mn x alpha(n)) for tree pedigrees without missing data.
• Demonstrated correct identification of all 0-recombinant solutions with high efficiency.
• Showcased 10 to 10(5)-fold improvements compared to other popular algorithms.

Conclusions:

• The developed algorithm provides a significant advancement in haplotype inference efficiency and accuracy.
• The mathematical formulation and use of disjoint-set structures are key to the algorithm's performance.
• The C++ implementation, to be part of the PedPhase package, is robust for various pedigree types and data completeness.