Efficient and tight upper bounds for haplotype inference by pure parsimony using delayed haplotype selection
See where this sits in the topic map →Summary AI-generated
- TL;DR
- Haplotype inference from genotype data is a key step toward better understanding the role of genetic variations in inherited diseases.
- Problem
- The Haplotype Inference by Pure Parsimony (HIPP) problem aims to minimize the number of haplotypes required to explain a set of genotypes, which is NP-hard and often solved using constraint satisfaction techniques where the upper bound on the number of required haplotypes is a critical issue.
- Method
- We combine the basic idea of Clark’s method with a more sophisticated approach for selecting explaining haplotypes, explicitly introducing a bias toward parsimonious explanations.
- Results
- Experiments on a large set of real and artificially generated examples show that the new method is much more effective than Clark’s method at finding parsimonious solutions while retaining its simplicity and speed.
- Contributions
- A new algorithm that can either approximate the HIPP problem or compute an upper bound on the size of the pure parsimony solution to efficiently encode the problem as a constraint satisfaction problem.
- Limitations
- Not specified in the abstract.
- Takeaways
- The proposed method improves upon Clark's method by effectively generating parsimonious solutions while preserving speed and simplicity.
- Applications
- The algorithm can be used to obtain an approximate solution to the HIPP problem or to find an upper bound on the size of the pure parsimony solution, which helps encode the problem as a constraint satisfaction problem.
- Topics
- Not specified in the abstract.
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
Abstract. Haplotype inference from genotype data is a key step towards a better understanding of the role played by genetic variations on inherited diseases. One of the most promising approaches uses the pure parsimony criterion. This approach is called Haplotype Inference by Pure Parsimony (HIPP) and is NP-hard as it aims at minimising the number of haplotypes required to explain a given set of genotypes. The HIPP problem is often solved using constraint satisfaction techniques, for which the upper bound on the number of required haplotypes is a key issue. Another very well-known approach is Clark’s method, which resolves genotypes by greedily selecting an explaining pair of haplotypes. In this work, we combine the basic idea of Clark’s method with a more sophisticated method for the selection of explaining haplotypes, in order to explicitly introduce a bias towards parsimonious explanations. This new algorithm can be used either to obtain an approximated solution to the HIPP problem or to obtain an upper bound on the size of the pure parsimony solution. This upper bound can then used to efficiently encode the problem as a constraint satisfaction problem. The experimental evaluation, conducted using a large set of real and artificially generated examples, shows that the new method is much more effective than Clark’s method at obtaining parsimonious solutions, while keeping the advantages of simplicity and speed of Clark’s method. 1