On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs

Tom Davot 1 Annie Chateau 2 Rodolphe Giroudeau 1 Mathias Weller 3, 4
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 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 graph may contain branchings and they may not be uniquely convertible into sequences. Having introduced, in a previous work, 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 the APX-completeness in this case. We also provide some practical tests.
Document type :
Conference papers
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01900395
Contributor : Tom Davot <>
Submitted on : Friday, March 29, 2019 - 4:38:27 PM
Last modification on : Wednesday, July 10, 2019 - 10:28:01 AM
Long-term archiving on : Sunday, June 30, 2019 - 3:42:36 PM

File

recomb-cg_2018_on_the_hardness...
Files produced by the author(s)

Identifiers

Citation

Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs. RECOMB-CG, Oct 2018, Magog-Orford, QC, Canada. pp.91-107, ⟨10.1007/978-3-030-00834-5_5⟩. ⟨lirmm-01900395v2⟩

Share

Metrics

Record views

85

Files downloads

134