Practical dynamic de Bruijn graphs

Kuhnle, Alan; Crawford, Victoria; Boucher, Christina; Chikhi, Rayan; Gagie, Travis

Document type :

Article dans une revue scientifique: Article original

DOI :

10.1093/bioinformatics/bty500

Title :

Practical dynamic de Bruijn graphs

Author(s) :

Kuhnle, Alan [Auteur]
Department of Computer and Information Science and Engineering [Gainesville] [UF|CISE]
Crawford, Victoria [Auteur]
Department of Computer and Information Science and Engineering [Gainesville] [UF|CISE]
Boucher, Christina [Auteur]
Department of Computer and Information Science and Engineering [Gainesville] [UF|CISE]
Chikhi, Rayan [Auteur]

Bioinformatics and Sequence Analysis [BONSAI]
Gagie, Travis [Auteur]
Centre for Biotechnology and Bioengineering [Santiago] [CeBiB]

Journal title :

Bioinformatics

Publisher :

Oxford University Press (OUP)

Publication date :

2018-06-22

ISSN :

1367-4803

HAL domain(s) :

Informatique [cs]/Bio-informatique [q-bio.QM]

English abstract : [en]

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, ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://hal.archives-ouvertes.fr/hal-01935559/document
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-01935559/document
Open access
Access the document

https://academic.oup.com/bioinformatics/article-pdf/34/24/4189/27088776/bty500.pdf
Open access
Access the document

https://academic.oup.com/bioinformatics/article-pdf/34/24/4189/27088776/bty500.pdf
Open access
Access the document

https://academic.oup.com/bioinformatics/article-pdf/34/24/4189/27088776/bty500.pdf
Open access
Access the document

https://academic.oup.com/bioinformatics/article-pdf/34/24/4189/27088776/bty500.pdf
Open access
Access the document

https://academic.oup.com/bioinformatics/article-pdf/34/24/4189/27088776/bty500.pdf
Open access
Access the document

https://academic.oup.com/bioinformatics/article-pdf/34/24/4189/27088776/bty500.pdf
Open access
Access the document

document
Open access
Access the document

main.pdf
Open access
Access the document

bty500.pdf
Open access
Access the document

document
Open access
Access the document

main.pdf
Open access
Access the document

Practical dynamic de Bruijn graphs BibTeX CSV Excel RIS

Files

Practical dynamic de Bruijn graphs

BibTeX

CSV

Excel

RIS