Inference of haplotypes from samples of diploid populations: complexity and algorithms

Area of Science:

• Genomics
• Computational Biology
• Bioinformatics

Background:

• Large-scale human population screening for DNA polymorphisms, particularly single nucleotide polymorphisms (SNPs), is the next frontier in genomics.
• Current methods collect genotype (blended) SNP data, but inferring haplotype (partitioned) data from diploid individuals is difficult.
• Existing nondeterministic inference algorithms (Clark, 1990; Clark et al., 1998) face limitations.

Purpose of the Study:

• To investigate the efficiency and determinism of SNP haplotype inference.
• To determine if an optimized, deterministic variant of existing inference methods can be developed.
• To address the computational complexity of inferring haplotype data from genotype data.

Main Methods:

• Analysis of a nondeterministic inference algorithm for SNP data.
• Mathematical proof demonstrating the NP-hard and Max-SNP complete nature of the problem.
• Development and implementation of an approach combining an exponential-time operation with integer linear programming.

Main Results:

• The SNP haplotype inference problem is proven to be NP-hard and Max-SNP complete.
• The reduction creates problem instances that align with restrictions observed in real-world data.
• Despite the inherent complexity, the developed linear programming approach demonstrates efficiency and accuracy on simulated data.

Conclusions:

• Accurate haplotype inference from genotype data remains computationally challenging.
• The proposed linear programming method offers a practical and effective solution for inferring haplotypes.
• This work advances computational approaches for large-scale human genomics studies.