On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs

Tom Davot 1 Annie Château 2 Rodolphe Giroudeau 1 Mathias Weller 3
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Communication dans un congrès
RECOMB-CG: Comparative Genomics, Oct 2018, Sherbrooke, Canada. 16th RECOMB Satellite Conference on Comparative Genomics, 2018, 〈https://recombcg2018.usherbrooke.ca〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01900395
Contributeur : Tom Davot <>
Soumis le : lundi 22 octobre 2018 - 09:29:58
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-01900395, version 1

Collections

Citation

Tom Davot, Annie Château, Rodolphe Giroudeau, Mathias Weller. On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs. RECOMB-CG: Comparative Genomics, Oct 2018, Sherbrooke, Canada. 16th RECOMB Satellite Conference on Comparative Genomics, 2018, 〈https://recombcg2018.usherbrooke.ca〉. 〈lirmm-01900395〉

Partager

Métriques

Consultations de la notice

33

Téléchargements de fichiers

16