| Haplotype inference by Pure Parsimony: a survey. | |
| | |
MedLine Citation:
|
PMID: 20726791 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
Ana Graça; Inês Lynce; João Marques-Silva; Arlindo L Oliveira |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't; Review |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: 17 ISSN: 1557-8666 ISO Abbreviation: J. Comput. Biol. Publication Date: 2010 Aug |
Date Detail:
|
Created Date: 2010-08-23 Completed Date: 2010-12-07 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 969-92 Citation Subset: IM |
Affiliation:
|
Instituto Superior Técnico (IST), Technical University of Lisbon, INESC-ID Lisboa, Lisbon, Portugal. assg@sat.inesc-id.pt |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms Animals Genotype Haplotypes* Humans Models, Genetic* |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Introducing knowledge into differential expression analysis.
Next Document: Conformational optimization with natural degrees of freedom: a novel stochastic chain closure algori...