Computational complexity of perfect-phylogeny-related haplotyping problems

Michael Elberfeld, Till Tantau


Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. This problem, which has strong practical applications, can be approached using both statistical as well as combinatorial methods. While the most direct combinatorial approach, maximum parsimony, leads to NP-complete problems, the perfect phylogeny model proposed by Gusfield yields a problem, called pph, that can be solved in polynomial (even linear) time. Even this may not be fast enough when the whole genome is studied, leading to the question of whether parallel algorithms can be used to solve the pph problem. In the present paper we answer this question affirmatively, but we also give lower complexity bounds on its complexity. In detail, we show that the problem lies in Mod2L, a subclass of the circuit complexity class NC2, and is hard for logarithmic space and thus presumably not in NC1. We also investigate variants of the pph problem that have been studied in the literature, like the perfect path phylogeny haplotyping problem and the combined problem where a perfect phylogeny of maximal parsimony is sought, and show that some of these variants are TC0-complete or lie in AC0.

Original languageEnglish
Title of host publicationMFCS 2008: Mathematical Foundations of Computer Science 2008
Number of pages12
Volume5162 LNCS
PublisherSpringer Verlag
Publication date27.10.2008
ISBN (Print)978-3-540-85237-7
ISBN (Electronic)978-3-540-85238-4
Publication statusPublished - 27.10.2008
Event33rd International Symposium on Mathematical Foundations of Computer Science - Torun, Poland
Duration: 25.08.200829.08.2008
Conference number: 73962


Dive into the research topics of 'Computational complexity of perfect-phylogeny-related haplotyping problems'. Together they form a unique fingerprint.

Cite this