On the Linearization of Scaffolds Sharing Repeated Contigs

Mathias Weller 1, 2 Annie Chateau 1, 2 Rodolphe Giroudeau 3
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions (“contigs”) are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomial-time and $NP$ -hard special cases like planarity or bounded degree.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01672893
Contributor : Rodolphe Giroudeau <>
Submitted on : Wednesday, December 27, 2017 - 4:06:17 PM
Last modification on : Wednesday, July 10, 2019 - 11:05:46 AM

Identifiers

Collections

Citation

Mathias Weller, Annie Chateau, Rodolphe Giroudeau. On the Linearization of Scaffolds Sharing Repeated Contigs. COCOA: Conference on Combinatorial Optimization and Applications, Dec 2017, Shanghai, China. pp.509-517, ⟨10.1007/978-3-319-71147-8_38⟩. ⟨lirmm-01672893⟩

Share

Metrics

Record views

200