A set covering approach with column generation for parsimony haplotyping

We introduce an exact algorithm, based on Integer Linear Programming, for the parsimony haplotyping problem (PHP). The PHP is derived from a molecular biology procedure aimed at the determination of an optimal set of {\em haplotypes} that explain a given set of {\em genotypes}. Our approach is based on a Set Covering formulation of the problem, solved by branch and bound with both column- and row- generation. Existing ILP methods for the PHP suffer from the large size of the solution space, when the genotypes are long and with many {\em heterozygous} sites. Our approach, on the other hand, is based on an effective implicit representation of the solution space, and allows the solution of both real-life and simulated instances which are very hard to solve for other ILPs.