title: Tractable Cases of (*,2)-Bounded Parsimony Haplotyping.
abstract: Parsimony haplotyping is the problem of finding a set of haplotypes of minimum cardinality that explains a given set of genotypes, where a genotype is explained by two haplotypes if it can be obtained as a combination of the two. This problem is NP-complete in the general case, but polynomially solvable for (k, l)-bounded instances for certain k and l. Here, k denotes the maximum number of ambiguous sites in any genotype, and l is the maximum number of genotypes that are ambiguous at the same site. Only the complexity of the (*, 2)-bounded problem is still unknown, where * denotes no restriction. It has been proved that (*, 2)-bounded instances have compatibility graphs that can be constructed from cliques and circuits by pasting along an edge. In this paper, we give a constructive proof of the fact that (*, 2)-bounded instances are polynomially solvable if the compatibility graph is constructed by pasting cliques, trees and circuits along a bounded number of edges. We obtain this proof by solving a slightly generalized problem on circuits, trees and cliques respectively, and arguing that all possible combinations of optimal solutions for these graphs that are pasted along a bounded number of edges can be enumerated efficiently.
authors.forename: Judith
authors.initials: J
authors.lastname: Keijsper
authors.forename: Tim
authors.initials: T
authors.lastname: Oosterwijk
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D055808:Drug Discovery / Q000379:methods*; D020022:Genetic Predisposition to Disease; D006239:Haplotypes / Q000235:genetics*; D006801:Humans; D008957:Models, Genetic