New results about the 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

New results about the 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 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.
Fichier principal
Vignette du fichier
main.pdf (487.66 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : lirmm-01900389 , version 1

Cite

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, Dec 2018, Atlanta, United States. ⟨lirmm-01900389v1⟩
484 View
318 Download

Share

Gmail Facebook X LinkedIn More