Haplotype Inference by Pure Parsimony: A Survey
See where this sits in the topic map →Summary AI-generated
- TL;DR
- This survey provides an overview of methods for haplotype inference—the process of recovering underlying haplotypes from a population's genotypes.
- Problem
- Under the assumption of pure parsimony, the haplotype inference problem consists of finding the smallest set of haplotypes that can explain a given group of genotypes, a task known to be NP-hard.
- Method
- The paper covers various exact and heuristic approaches, ranging from early integer linear programming and branch-and-bound techniques to more recent, highly efficient methods based on Boolean satisfiability, pseudo-Boolean optimization, and answer set programming, alongside preprocessing and bounding techniques.
- Results
- The article presents an empirical evaluation of exact HIPP solvers on synthetic and real problem instances, alongside an evaluation of bounding techniques for the exact problem.
- Contributions
- This article provides a comprehensive survey and overview of algorithmic methods for solving the HIPP problem, including preprocessing, bounding techniques, heuristics, and an empirical evaluation.
- Limitations
- Not specified in the abstract.
- Takeaways
- HIPP can now be considered a feasible and competitive approach for haplotype inference, as discussed through comparisons with well-established statistical reference algorithms.
- Applications
- Not specified in the abstract.
- Topics
- Computational Biology; Haplotype Inference; Pure Parsimony; Integer Linear Programming; Boolean Satisfiability
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
Given a set of genotypes from a population, the process of recovering the haplotypes that explain the genotypes is called haplotype inference. The haplotype inference problem under the assumption of pure parsimony consists in finding the smallest number of haplotypes that explain a given set of genotypes. This problem is NP-hard. The original formulations for solving the Haplotype Inference by Pure Parsimony (HIPP) problem were based on integer linear programming and branch-and-bound techniques. More recently, solutions based on Boolean satisfiability, pseudo-Boolean optimization, and answer set programming have been shown to be remarkably more efficient. HIPP can now be regarded as a feasible approach for haplotype inference, which can be competitive with other different approaches. This article provides an overview of the methods for solving the HIPP problem, including preprocessing, bounding techniques, and heuristic approaches. The article also presents an empirical evaluation of exact HIPP solvers on a comprehensive set of synthetic and real problem instances. Moreover, the bounding techniques to the exact problem are evaluated. The final section compares and discusses the HIPP approach with a well-established statistical method that represents the reference algorithm for this problem.