Computing the minimum recombinant haplotype configuration from incomplete genotype data on a pedigree by integer...

Area of Science:

• Genetics
• Bioinformatics
• Computational Biology

Background:

• Haplotype reconstruction is crucial for genetic mapping and association studies.
• The minimum-recombinant haplotype configuration (MRHC) problem is computationally challenging (NP-hard), especially with missing data.

Purpose of the Study:

• To develop an effective integer linear programming (ILP) formulation for the MRHC problem with missing alleles.
• To present a branch-and-bound strategy for efficient haplotype reconstruction.
• To incorporate marker interval distance into haplotyping algorithms.

Main Methods:

• Integer linear programming (ILP) formulation for MRHC.
• Branch-and-bound strategy with partial order relationships and variable ordering.
• Lower and upper bounds for pruning the search tree.
• Maximum likelihood approach for selecting the best haplotype configuration.
• Integration of marker interval distance into a rule-based algorithm.

Main Results:

• The ILP algorithm reconstructs haplotypes from simulated data (50 loci, 29 individuals) in seconds.
• Accuracy exceeds 99.8% for complete data and 98.3% for 20% missing data.
• The algorithm is significantly faster than SimWalk2 and provides comparable or better haplotype quality.
• Successful application to a real genome-scale SNP dataset with missing alleles.

Conclusions:

• The developed ILP approach provides an effective and efficient solution for haplotype reconstruction with missing data.
• The method demonstrates high accuracy and speed, outperforming existing statistical approaches.
• This work advances the construction of haplotype maps and genetic analyses by enabling robust haplotyping even with incomplete genetic information.