New Polynomial-Time Algorithm around the Scaffolding Problem

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
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We describe in this paper an approximation algorithm for the scaffolding problem, which is part of genome inference in bioinformatics. The aim of the problem is to find a maximum weighted collection of disjoint alternating cycles and paths covering a particular graph called scaffold graph. The problem is known to be NP-complete, and we describe further result concerning a special class of graphs aiming to be close to real instances. The described algorithm is the first polynomial-time approximation algorithm designed for this problem on non-complete graphs.
Document type :
Conference papers
Complete list of metadatas
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02047701
Contributor : Tom Davot <>
Submitted on : Monday, February 25, 2019 - 10:52:33 AM
Last modification on : Thursday, July 11, 2019 - 3:01:19 PM
Long-term archiving on : Sunday, May 26, 2019 - 1:16:19 PM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

LIRMM | MAB | MAORE | ALGCO | MIPS | UNIV-MONTPELLIER

Citation

Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. New Polynomial-Time Algorithm around the Scaffolding Problem. AlCoB: Algorithms for Computational Biology, May 2019, Berkeley, United States. pp.25-38, ⟨10.1007/978-3-030-18174-1_2⟩. ⟨lirmm-02047701⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

83

Files downloads

39

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD