Exact approaches for scaffolding

BMC Bioinformatics

Research

Rodolphe Giroudeau¹  Mathias Weller²  Annie Chateau² 

[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