Haplotyping with missing data via perfect path phylogenies

Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau*

*Corresponding author for this work
9 Citations (Scopus)


Computational methods for inferring haplotype information from genotype data are used in studying the association between genomic variation and medical condition. Recently, Gusfield proposed a haplotype inference method that is based on perfect phylogeny principles. A fundamental problem arises when one tries to apply this approach in the presence of missing genotype data, which is common in practice. We show that the resulting theoretical problem is NP-hard even in very restricted cases. To cope with missing data, we introduce a variant of haplotyping via perfect phylogeny in which a path phylogeny is sought. Searching for perfect path phylogenies is strongly motivated by the characteristics of human genotype data: 70% of real instances that admit a perfect phylogeny also admit a perfect path phylogeny. Our main result is a fixed-parameter algorithm for haplotyping with missing data via perfect path phylogenies. We also present a simple linear-time algorithm for the problem on complete data.

Original languageEnglish
JournalDiscrete Applied Mathematics
Issue number6-7
Pages (from-to)788-805
Number of pages18
Publication statusPublished - 01.04.2007


Dive into the research topics of 'Haplotyping with missing data via perfect path phylogenies'. Together they form a unique fingerprint.

Cite this