New Polynomial-Time Algorithm around the Scaffolding Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

New Polynomial-Time Algorithm around the Scaffolding Problem


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.
Fichier principal
Vignette du fichier
main.pdf (512.52 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-02047701 , version 1 (25-02-2019)



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



Gmail Mastodon Facebook X LinkedIn More