Exact approaches for scaffolding

Mathias Weller 1, 2 Annie Château 3, 1 Rodolphe Giroudeau 4
3 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01219627
Contributeur : Annie Chateau <>
Soumis le : jeudi 22 octobre 2015 - 22:15:44
Dernière modification le : mercredi 10 octobre 2018 - 14:28:13

Lien texte intégral

Identifiants

Collections

Citation

Mathias Weller, Annie Château, Rodolphe Giroudeau. Exact approaches for scaffolding. BMC Bioinformatics, BioMed Central, 2015, pp.S2. 〈http://www.biomedcentral.com/1471-2105/16/S14/S2〉. 〈10.1186/1471-2105-16-S14-S2〉. 〈lirmm-01219627〉

Partager

Métriques

Consultations de la notice

220