Exact approaches for scaffolding - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles BMC Bioinformatics Year : 2015

Exact approaches for scaffolding


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.
Fichier principal
Vignette du fichier
1471-2105-16-S14-S2.pdf (1.65 Mo) Télécharger le fichier

Dates and versions

lirmm-01219627 , version 1 (22-10-2015)



Mathias Weller, Annie Chateau, Rodolphe Giroudeau. Exact approaches for scaffolding. BMC Bioinformatics, 2015, 16 (Suppl 14), pp.S2. ⟨10.1186/1471-2105-16-S14-S2⟩. ⟨lirmm-01219627⟩
215 View
53 Download



Gmail Mastodon Facebook X LinkedIn More