BMC Bioinformatics | |
Exact approaches for scaffolding | |
Research | |
Rodolphe Giroudeau1  Mathias Weller2  Annie Chateau2  | |
[1] Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier - UMR 5506 CNRS, 161 rue Ada, 34090, Montpellier, France;Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier - UMR 5506 CNRS, 161 rue Ada, 34090, Montpellier, France;Institut de Biologie Computationnelle, Lirmm Bât 5 - 860 rue de St Priest, 34090, Montpellier, France; | |
关键词: scaffolding; exact methods; dynamic programming; treewidth; preprocessing; fixed-parameter tractable; | |
DOI : 10.1186/1471-2105-16-S14-S2 | |
来源: Springer | |
【 摘 要 】
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.
【 授权许可】
CC BY
© Weller et al.; 2015
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202311107584063ZK.pdf | 1685KB | download |
【 参考文献 】
- [1]
- [2]
- [3]
- [4]
- [5]
- [6]
- [7]
- [8]
- [9]
- [10]
- [11]
- [12]
- [13]
- [14]
- [15]
- [16]
- [17]
- [18]
- [19]
- [20]
- [21]
- [22]
- [23]
- [24]
- [25]
- [26]
- [27]
- [28]
- [29]
- [30]
- [31]
- [32]
- [33]
- [34]
- [35]
- [36]
- [37]
- [38]
- [39]
- [40]