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.