We describe an integer programming (IP) model that can be applied to the solution of all genome-rearrangement problems in the literature. No direct IP model for such problems had ever been proposed prior to this work. Our model employs an exponential number of variables, but it can be solved by column generation techniques. I.e., we start with a small number of variables and we show how the correct missing variables can be added to the model in polynomial time.

A unified integer programming model for genome rearrangement problems

LANCIA, Giuseppe;RINALDI, Franca;SERAFINI, Paolo
2015-01-01

Abstract

We describe an integer programming (IP) model that can be applied to the solution of all genome-rearrangement problems in the literature. No direct IP model for such problems had ever been proposed prior to this work. Our model employs an exponential number of variables, but it can be solved by column generation techniques. I.e., we start with a small number of variables and we show how the correct missing variables can be added to the model in polynomial time.
2015
9783319164823
9783319164823
File in questo prodotto:
File Dimensione Formato  
granada_lnbi.pdf

non disponibili

Descrizione: versione post print
Tipologia: Documento in Post-print
Licenza: Non pubblico
Dimensione 247.73 kB
Formato Adobe PDF
247.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
doc00566020210331114136.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 5.45 MB
Formato Adobe PDF
5.45 MB 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: https://hdl.handle.net/11390/1073498
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact