×

Extended islands of tractability for parsimony haplotyping. (English) Zbl 1286.92036

Amir, Amihood (ed.) et al., Combinatorial pattern matching. 21st annual symposium, CPM 2010, New York, NY, USA, June 21–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13508-8/pbk). Lecture Notes in Computer Science 6129, 214-226 (2010).
Summary: Parsimony haplotyping is the problem of finding a smallest size set of haplotypes that can explain a given set of genotypes. The problem is NP-hard, and many heuristic and approximation algorithms as well as polynomial-time solvable special cases have been discovered. We propose improved fixed-parameter tractability results with respect to the parameter “size of the target haplotype set” \(k\) by presenting an \(O ^{*}(k ^{4k })\)-time algorithm. This also applies to the practically important constrained case, where we can only use haplotypes from a given set. Furthermore, we show that the problem becomes polynomial-time solvable if the given set of genotypes is complete, i.e., contains all possible genotypes that can be explained by the set of haplotypes.
For the entire collection see [Zbl 1192.68005].

MSC:

92D10 Genetics and epigenetics
68Q25 Analysis of algorithms and problem complexity
92-08 Computational methods for problems pertaining to biology
PDFBibTeX XMLCite
Full Text: DOI