Haplotype inference by Pure Parsimony: a survey

Area of Science:

• Computational Biology
• Genetics
• Bioinformatics

Background:

• Haplotype inference reconstructs genetic haplotypes from population genotypes.
• The Haplotype Inference by Pure Parsimony (HIPP) problem seeks the minimal set of haplotypes explaining observed genotypes.
• HIPP is an NP-hard problem with historical solutions based on integer programming and branch-and-bound.

Purpose of the Study:

• To provide an overview of methods for solving the Haplotype Inference by Pure Parsimony (HIPP) problem.
• To evaluate the efficiency and competitiveness of HIPP solvers.
• To compare HIPP with established statistical methods in haplotype inference.

Main Methods:

• Review of preprocessing, bounding, and heuristic techniques for HIPP.
• Empirical evaluation of exact HIPP solvers on synthetic and real datasets.
• Assessment of bounding techniques for the exact HIPP problem.
• Comparison of HIPP with a reference statistical method.

Main Results:

• Boolean satisfiability, pseudo-Boolean optimization, and answer set programming offer more efficient HIPP solutions.
• HIPP is now a feasible and competitive approach for haplotype inference.
• Bounding techniques significantly impact the performance of exact HIPP solvers.
• Empirical evaluation demonstrates the effectiveness of HIPP on diverse problem instances.

Conclusions:

• Haplotype Inference by Pure Parsimony is a viable and efficient method for reconstructing haplotypes.
• Modern computational approaches have significantly advanced the tractability of HIPP.
• HIPP demonstrates competitive performance against established statistical methods in haplotype inference.