Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Practical dynamic de Bruijn graphs

Alan Kuhnle 1 Victoria Crawford 1 Christina Boucher 1 Rayan Chikhi 2 Travis Gagie 3
2 BONSAI - Bioinformatics and Sequence Analysis
CNRS - Centre National de la Recherche Scientifique, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189, Université de Lille, Sciences et Technologies, Inria Lille - Nord Europe
Abstract : As datasets of DNA reads grow rapidly, it becomes more and more important to represent de Bruijn graphs compactly while still supporting fast assembly. Previous implementations have not supported edge deletion, however, which is important for pruning spurious edges from the graph. Belazzougui et al. Belazzougui et al. (2016b) recently proposed a compact and fully dynamic representation, which supports exact membership queries and insertions and deletions of both nodes and edges. In this paper we give a practical implementation of their data structure, supporting exact membership queries and insertions and deletions of edges only, and demonstrate experimentally that its performance is comparable to that of state-of-the-art implementations based on Bloom filters. Our source-code is publicly available at https://github.com/csirac/kbf under an open-source license.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-01935559
Contributeur : Rayan Chikhi Connectez-vous pour contacter le contributeur
Soumis le : mercredi 11 décembre 2019 - 15:02:11
Dernière modification le : mercredi 23 mars 2022 - 15:51:19
Archivage à long terme le : : jeudi 12 mars 2020 - 13:19:04

Fichier

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

Identifiants

Citation

Alan Kuhnle, Victoria Crawford, Christina Boucher, Rayan Chikhi, Travis Gagie. Practical dynamic de Bruijn graphs. Bioinformatics, Oxford University Press (OUP), 2018, ⟨10.1093/bioinformatics/bty500⟩. ⟨hal-01935559⟩

Partager

Métriques

Consultations de la notice

93

Téléchargements de fichiers

38