Phylogeny- and Parsimony-Based Haplotype Inference with Constraints

Michael Elberfeld, Till Tantau


Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. In their cpm 2009 paper, Fellows et al. studied an extension of this approach that incorporates prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. While this approach may help to increase the accuracy of haplotyping methods, it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the present paper we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption.
TitelCombinatorial Pattern Matching
Redakteure/-innenAmihood Amir, Laxmi Parida
ErscheinungsortBerlin, Heidelberg
Herausgeber (Verlag)Springer Berlin Heidelberg
ISBN (Print)978-3-642-13508-8
ISBN (elektronisch)978-3-642-13509-5
PublikationsstatusVeröffentlicht - 06.2010
Veranstaltung21st Annual Symposium, CPM 2010 - New York, USA / Vereinigte Staaten
Dauer: 21.06.201023.06.2010


Untersuchen Sie die Forschungsthemen von „Phylogeny- and Parsimony-Based Haplotype Inference with Constraints“. Zusammen bilden sie einen einzigartigen Fingerprint.