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

Linearizing Genomes: Exact Methods and Local Search

Abstract

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 (537.12 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. Linearizing Genomes: Exact Methods and Local Search. SOFSEM 2020 - 46th International Conference on Current Trends in Theory and Practice of Informatics, Jan 2020, Limassol, Cyprus. pp.505-518, ⟨10.1007/978-3-030-38919-2_41⟩. ⟨lirmm-02332049v2⟩
179 View
219 Download

Altmetric

Share

More