This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Lancia, G. Articles by Serafini, P. Search for Related Content

A Set-Covering Approach with Column Generation for Parsimony Haplotyping

Dipartimento di Matematica e Informatica, University of Udine, 33100 Udine, Italy
Dipartimento di Matematica e Informatica, University of Udine, 33100 Udine, Italy
lancia{at}dimi.uniud.it
serafini{at}dimi.uniud.it

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.

Key words: integer programming; computational biology; haplotyping; branch and price; branch and cut; set covering
History: received November 2007; accepted April 2008.