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.
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 : Friday, April 5, 2019 - 1:11:48 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-02047701, version 1

Collections

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. ⟨lirmm-02047701⟩

Share

Metrics

Record views

72

Files downloads

30