A polynomial case of the parsimony haplotyping problem

The parsimony haplotyping problem was shown to be NP-hard when each genotype had k⩽3 ambiguous positions, while the case for k⩽2 was open. In this paper, we show that the case for k⩽2 is polynomial, and we give approximation and FPT algorithms for the general case of k⩾0 ambiguous positions.