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.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
EditorsAmihood Amir, Laxmi Parida
Number of pages13
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Publication date06.2010
ISBN (Print)978-3-642-13508-8
ISBN (Electronic)978-3-642-13509-5
Publication statusPublished - 06.2010
Event21st Annual Symposium, CPM 2010 - New York, United States
Duration: 21.06.201023.06.2010


Dive into the research topics of 'Phylogeny- and Parsimony-Based Haplotype Inference with Constraints'. Together they form a unique fingerprint.

Cite this