On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2018

On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs

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.
Fichier principal
Vignette du fichier
recomb-cg_2018_on_the_hardness_of_approximating_linearization_of_scaffolds_sharing_repeated_contigs.pdf (542.91 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01900395 , version 1 (22-10-2018)
lirmm-01900395 , version 2 (29-03-2019)

Identifiers

Cite

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, Magog-Orford, QC, Canada. pp.91-107, ⟨10.1007/978-3-030-00834-5_5⟩. ⟨lirmm-01900395v2⟩
214 View
234 Download

Altmetric

Share

More