On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : lirmm-01900395 , version 1

Citer

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⟩
184 Consultations
220 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More