On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
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
main.pdf (556.35 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

  • HAL Id : lirmm-01900395 , version 1

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, Sherbrooke, Canada. ⟨lirmm-01900395v1⟩
178 View
213 Download

Share

Gmail Facebook X LinkedIn More