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

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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/877104
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact