Linearizing Genomes: Exact Methods and Local Search

Tom Davot 1, 2 Annie Chateau 2 Rodolphe Giroudeau 1 Mathias Weller 3
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02332049
Contributor : Tom Davot <>
Submitted on : Thursday, October 24, 2019 - 3:56:40 PM
Last modification on : Wednesday, November 13, 2019 - 10:21:07 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-02332049, version 1

Citation

Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. Linearizing Genomes: Exact Methods and Local Search. SOFSEM, Jan 2020, Limassol, Cyprus. ⟨lirmm-02332049⟩

Share

Metrics

Record views

15

Files downloads

11