Skip to Main content Skip to Navigation
Conference papers

On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs

Tom Davot 1 Annie Chateau 2 Rodolphe Giroudeau 1 Mathias Weller 3
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 metadata

Cited literature [23 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01900395
Contributor : Tom Davot <>
Submitted on : Monday, October 22, 2018 - 9:29:58 AM
Last modification on : Tuesday, June 8, 2021 - 11:04:02 AM
Long-term archiving on: : Wednesday, January 23, 2019 - 1:10:16 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01900395, version 1

Citation

Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs. RECOMB-CG: Comparative Genomics, Oct 2018, Sherbrooke, Canada. ⟨lirmm-01900395v1⟩

Share

Metrics

Record views

75

Files downloads

29