Title |
Exact approaches for scaffolding
|
---|---|
Published in |
BMC Bioinformatics, October 2015
|
DOI | 10.1186/1471-2105-16-s14-s2 |
Pubmed ID | |
Authors |
Mathias Weller, Annie Chateau, Rodolphe Giroudeau |
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. |
X Demographics
Geographical breakdown
Country | Count | As % |
---|---|---|
United States | 2 | 67% |
Unknown | 1 | 33% |
Demographic breakdown
Type | Count | As % |
---|---|---|
Members of the public | 2 | 67% |
Scientists | 1 | 33% |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
Sweden | 1 | 6% |
France | 1 | 6% |
Unknown | 14 | 88% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Researcher | 7 | 44% |
Student > Ph. D. Student | 3 | 19% |
Professor | 1 | 6% |
Student > Bachelor | 1 | 6% |
Student > Postgraduate | 1 | 6% |
Other | 0 | 0% |
Unknown | 3 | 19% |
Readers by discipline | Count | As % |
---|---|---|
Computer Science | 6 | 38% |
Agricultural and Biological Sciences | 6 | 38% |
Unknown | 4 | 25% |