Phylogeny- and parsimony-based haplotype inference with constraints

Michael Elberfeld*, Till Tantau

*Corresponding author for this work


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. An extension of this approach tries to incorporate prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. The objective is to increase the accuracy of haplotyping methods, but it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand 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
JournalInformation and Computation
Pages (from-to)33-47
Number of pages15
Publication statusPublished - 01.04.2012


Dive into the research topics of 'Phylogeny- and parsimony-based haplotype inference with constraints'. Together they form a unique fingerprint.

Cite this