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.
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
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⟩
