Inferring haplotypes from genotypes on a pedigree with mutations, genotyping errors and missing alleles

Area of Science:

• Genetics
• Bioinformatics
• Computational Biology

Background:

• Haplotype inference from pedigree genotypes is crucial but often complicated by genotyping errors and de novo mutations.
• Existing methods frequently overlook the impact of these data imperfections, potentially leading to inaccurate haplotype reconstructions.

Purpose of the Study:

• To develop a robust method for inferring haplotypes from genotype data that explicitly accounts for genotyping errors, de novo mutations, and missing alleles.
• To introduce and solve the Haplotype Configuration with Mutations and Errors (HCME) problem, a combinatorial optimization framework for accurate haplotype inference.

Main Methods:

• Formulated the HCME problem as a combinatorial optimization task, recognizing its NP-hard nature.
• Developed a heuristic algorithm centered around an integer linear program (ILP) utilizing linear equations over Galois field GF(2).
• The algorithm is designed to detect, locate, and correct genotyping errors beyond Mendelian inheritance checks.

Main Results:

• The proposed algorithm achieves highly accurate haplotype inference across various pedigree structures.
• Demonstrated the capability to detect and locate genotyping errors missed by standard Mendelian checks.
• Successfully recovered 65%-94% of genotyping errors, with performance varying based on pedigree topology.

Conclusions:

• The developed heuristic algorithm effectively infers haplotypes from imperfect genotype data, significantly improving accuracy.
• The method provides a powerful tool for error correction in genetic data, enhancing the reliability of downstream analyses.
• This approach offers a significant advancement in handling complex genetic data with errors and mutations in pedigree studies.