New Results About the Linearization of Scaffolds Sharing Repeated Contigs

Dorine Tabary 1 Tom Davot 1 Mathias Weller 2, 3 Annie Chateau 4 Rodolphe Giroudeau 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Solutions to genome scaffolding problems can be represented as paths and cycles in a "solution graph". However, when working with repetitions, such solution graphs may contain branchings and, thus, they may not be uniquely convertible into sequences. Having introduced various ways of extracting the unique parts of such solutions, we extend previously known NP-hardness results to the case that the solution graph is planar, bipartite, and subcubic, and show that there is no PTAS in this case.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01900389
Contributor : Tom Davot <>
Submitted on : Friday, March 29, 2019 - 4:35:42 PM
Last modification on : Friday, July 12, 2019 - 1:28:42 AM
Long-term archiving on : Sunday, June 30, 2019 - 3:47:27 PM

File

cocoa_2018_new_results_about__...
Files produced by the author(s)

Identifiers

Citation

Dorine Tabary, Tom Davot, Mathias Weller, Annie Chateau, Rodolphe Giroudeau. New Results About the Linearization of Scaffolds Sharing Repeated Contigs. COCOA: Conference on Combinatorial Optimization and Applications, Sep 2018, Atlanta, GA, United States. pp.94-107, ⟨10.1007/978-3-030-04651-4_7⟩. ⟨lirmm-01900389v2⟩

Share

Metrics

Record views

85

Files downloads

97