A Set-Covering Approach with Column Generation for Parsimony Haplotyping
Giuseppe Lancia, Paolo Serafini
INFORMS Journal on Computing · 2009 · Volume 21 · Issue 1
Abstract
We introduce an exact algorithm, based on integer linear programming (ILP), for the parsimony haplotyping problem (PHP). The PHP uses molecular data and is aimed at the determination of a smallest set of haplotypes that explain a given set of 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 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 data and simulated instances, which are very hard to solve for other ILPs.
Keywords
integer programming, computational biology, haplotyping, branch and price, branch and cut, set covering
Enable JavaScript for citation tools and additional paper interactions.