Parsimony haplotyping in polynomial time
Tim Oosterwijk
Parsimony haplotyping is the problem of finding a set of haplotypes of minimum
cardinality that explains a given set of genotypes. This problem is NP-complete
in the general case, but restricted cases of the problem have been found to be
solvable in polynomial time. In particular the (k,l)-bounded problem has been
studied, where k and l are the maximal number of heterozygote sites occurring
per genotype and per site. Only the (*,2)-bounded problem is still open, where
* denotes no restriction.
It has been proven that (*,2)-bounded instances have compatibility graphs that
can be constructed from cliques and cycles by pasting along a 2-clique. In this
presentation we give a constructive proof of the fact that (*,2)-bounded
instances are solvable in polynomial time if the compatibility graph consists
of a bounded number of cliques and cycles of bounded length.