Projects per year
Abstract
Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast haplotyping method is based on an evolutionary model in which a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing, which is often the case in laboratory data, the resulting formal problem ipph, which stands for incomplete perfect phylogeny haplotyping, is NPcomplete. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NPcomplete; but here, at least, a fixedparameter algorithm is known. Such drastic and ad hoc simplifications turn out to be unnecessary to make ipph tractable: we present the first theoretical analysis of a parameterized algorithm, which we develop in the course of the paper, that works for arbitrary instances of ipph. This tractability result is optimal insofar as we prove ipph to be NPcomplete whenever any of the parameters we consider is not fixed, but part of the input.
Original language  English 

Journal  Theoretical Computer Science 
Volume  432 
Pages (fromto)  3851 
Number of pages  14 
ISSN  03043975 
DOIs  
Publication status  Published  11.05.2012 
Fingerprint
Dive into the research topics of 'Influence of tree topology restrictions on the complexity of haplotyping with missing data'. 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