 |
HAL-LIRMM - Open Archive |  |
Journal articles
Exact approaches for scaffolding
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.
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01219627
Contributor : Annie Chateau Connect in order to contact the contributor
Submitted on : Thursday, October 22, 2015 - 10:15:44 PM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM
Contributor : Annie Chateau Connect in order to contact the contributor
Submitted on : Thursday, October 22, 2015 - 10:15:44 PM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM