Exact approaches for scaffolding

Mathias Weller 1, 2 Annie Chateau 3, 1 Rodolphe Giroudeau 4
3 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper presents new structural and algorithmic results around the scaffolding problem, which occurs prominently in next generation sequencing. The problem can be formalized as an optimization problem on a special graph, the "scaffold graph". We prove that the problem is polynomial if this graph is a tree by providing a dynamic programming algorithm for this case. This algorithm serves as a basis to deduce an exact algorithm for general graphs using a tree decomposition of the input. We explore other structural parameters, proving a linear-size problem kernel with respect to the size of a feedback-edge set on a restricted version of Scaffolding. Finally, we examine some parameters of scaffold graphs, which are based on real-world genomes, revealing that the feedback edge set is significantly smaller than the input size.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01219627
Contributor : Annie Chateau <>
Submitted on : Thursday, October 22, 2015 - 10:15:44 PM
Last modification on : Friday, March 15, 2019 - 5:02:19 PM

Links full text

Identifiers

Collections

Citation

Mathias Weller, Annie Chateau, Rodolphe Giroudeau. Exact approaches for scaffolding. BMC Bioinformatics, BioMed Central, 2015, pp.S2. ⟨http://www.biomedcentral.com/1471-2105/16/S14/S2⟩. ⟨10.1186/1471-2105-16-S14-S2⟩. ⟨lirmm-01219627⟩

Share

Metrics

Record views

285