New Polynomial-Time Algorithm around the Scaffolding Problem

Tom Davot 1, 2 Annie Chateau 2 Rodolphe Giroudeau 1 Mathias Weller 3, 4
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 CNRS - Centre National de la Recherche Scientifique
4 LIGM - Laboratoire d'Informatique Gaspard-Monge
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

Cited literature [10 references]  Display  Hide  Download
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02047701
Contributor : Tom Davot <>
Submitted on : Monday, February 25, 2019 - 10:52:33 AM
Last modification on : Wednesday, November 13, 2019 - 1:13:41 AM
Long-term archiving on: Sunday, May 26, 2019 - 1:16:19 PM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

LIRMM | CNRS | MAB | MAORE | MIPS | UNIV-MONTPELLIER | ENPC | LIGM | PARISTECH | LIGM_MOA | UPEC-UPEM

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

134

Files downloads

117

Contact

Informations

CCSD