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.
Type de document :
Communication dans un congrès
COCOA: Conference on Combinatorial Optimization and Applications, Dec 2018, Atlanta, United States. 12th Annual International Conference on Combinatorial Optimization and Applications, 2018, 〈http://spacl.kennesaw.edu/cocoa2018/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01900389
Contributeur : Tom Davot <>
Soumis le : lundi 22 octobre 2018 - 09:20:56
Dernière modification le : mercredi 24 octobre 2018 - 01:19:33

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01900389, version 1

Collections

Citation

Dorine Tabary, Tom Davot, Mathias Weller, Annie Château, Rodolphe Giroudeau. New results about the linearization of scaffolds sharing repeated contigs. COCOA: Conference on Combinatorial Optimization and Applications, Dec 2018, Atlanta, United States. 12th Annual International Conference on Combinatorial Optimization and Applications, 2018, 〈http://spacl.kennesaw.edu/cocoa2018/〉. 〈lirmm-01900389〉

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

28