title: 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.
authors.forename: Mathias
authors.initials: M
authors.lastname: Weller
authors.forename: Annie
authors.initials: A
authors.lastname: Chateau
authors.forename: Rodolphe
authors.initials: R
authors.lastname: Giroudeau
mesh_terms: D000465:Algorithms; D000818:Animals; D001419:Bacteria / Q000235:genetics; D020451:Contig Mapping; D016678:Genome; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods*