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
LANCIA, Giuseppe;SERAFINI, Paolo
2009-01-01
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.File | Dimensione | Formato | |
---|---|---|---|
cover.pdf
non disponibili
Tipologia:
Abstract
Licenza:
Non pubblico
Dimensione
256.67 kB
Formato
Adobe PDF
|
256.67 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.