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.

### A set covering approach with column generation for parsimony haplotyping

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
File in questo prodotto:
File
cover.pdf

non disponibili

Tipologia: Abstract
Licenza: Non pubblico
Dimensione 256.67 kB
Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/877104