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
cocoa_2018_new_results_about__the_linearization_of_scaffolds_sharing_repetead_contigs.pdf (472.82 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

Cite

Dorine Tabary, Tom Davot, Mathias Weller, Annie Chateau, Rodolphe Giroudeau. New Results About the Linearization of Scaffolds Sharing Repeated Contigs. COCOA 2018 - 12th International Conference on Combinatorial Optimization and Applications, Sep 2018, Atlanta, GA, United States. pp.94-107, ⟨10.1007/978-3-030-04651-4_7⟩. ⟨lirmm-01900389v2⟩
492 View
323 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More