Linearizing Genomes: Exact Methods and Local Search - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2020

Linearizing Genomes: Exact Methods and Local Search


In this article, we address the problem of genome linearization from the perspective of Polynomial Local Search, a complexity class related to finding local optima. We prove that the linearization problem, with a neighborhood structure, the neighbor slide, is PLS-complete. On the positive side, we develop two exacts methods, one using tree decompositions with an efficient dynamic programming, the other one using an integer linear program. Finally, we compare them on real instances.
Fichier principal
Vignette du fichier
main.pdf (519.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-02332049 , version 1 (24-10-2019)
lirmm-02332049 , version 2 (29-01-2020)



Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. Linearizing Genomes: Exact Methods and Local Search. SOFSEM, Jan 2020, Limassol, Cyprus. pp.505-518, ⟨10.1007/978-3-030-38919-2_41⟩. ⟨lirmm-02332049v1⟩
160 View
194 Download



Gmail Facebook X LinkedIn More