Projects per year
Abstract
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 NPcomplete 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 Mod_{2}L, a subclass of the circuit complexity class NC^{2}, and is hard for logarithmic space and thus presumably not in NC^{1}. 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 TC^{0}complete or lie in AC^{0}.
Original language  English 

Title of host publication  MFCS 2008: Mathematical Foundations of Computer Science 2008 
Number of pages  12 
Volume  5162 LNCS 
Publisher  Springer Verlag 
Publication date  27.10.2008 
Pages  299310 
ISBN (Print)  9783540852377 
ISBN (Electronic)  9783540852384 
DOIs  
Publication status  Published  27.10.2008 
Event  33rd International Symposium on Mathematical Foundations of Computer Science  Torun, Poland Duration: 25.08.2008 → 29.08.2008 Conference number: 73962 
Fingerprint
Dive into the research topics of 'Computational complexity of perfectphylogenyrelated haplotyping problems'. Together they form a unique fingerprint.Projects
 1 Finished

Complexity of haplotyping problems
Tantau, T., Schnoor, I., Elberfeld, M., Kuczewski, J. & Pohlmann, J.
01.01.05 → 31.12.10
Project: DFG Projects › DFG Individual Projects