A Column Generation Approach for Pure Parsimony Haplotyping

We present two integer programming models for the Haplotype Inference by Pure Parsimony problem. The first model uses variables to decide the haplotype coordinates and the two haplotypes that explain each genotype, and contains quadratic constraints. By decomposition, we obtain a second linear model where all the possible haplotypes and genotype subsets are enumerated and each variable decides if a haplotype explains a genotype subset. Preliminary tests show that the linear relaxation, solved by column generation, is tight and often provides the optimal integer solution for small instances.