Using cascading Bloom filters to improve the memory usage for de Brujin graphs

Kamil Salikhov 1 Gustavo Sacomoto 2, 3 Gregory Kucherov 4, 5, *
* Corresponding author
2 Baobab
PEGASE - Département PEGASE [LBBE]
3 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
Abstract : Background
De Brujin graphs are widely used in bioinformatics for processing next-generation sequencing data. Due to a very large size of NGS datasets, it is essential to represent de Bruijn graphs compactly, and several approaches to this problem have been proposed recently.
Results
In this work, we show how to reduce the memory required by the data structure of Chikhi and Rizk (WABI'12) that represents de Brujin graphs using Bloom filters. Our method requires 30% to 40% less memory with respect to their method, with insignificant impact on construction time. At the same time, our experiments showed a better query time compared to the method of Chikhi and Rizk.
Conclusion
The proposed data structure constitutes, to our knowledge, currently the most efficient practical representation of de Bruijn graphs.
Document type :
Journal articles
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00971576
Contributor : Ed. Bmc <>
Submitted on : Thursday, April 3, 2014 - 9:27:37 AM
Last modification on : Wednesday, November 20, 2019 - 3:13:46 AM
Long-term archiving on : Thursday, July 3, 2014 - 11:06:09 AM

Files

1748-7188-9-2.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Kamil Salikhov, Gustavo Sacomoto, Gregory Kucherov. Using cascading Bloom filters to improve the memory usage for de Brujin graphs. Algorithms for Molecular Biology, BioMed Central, 2014, 9 (1), pp.2. ⟨10.1186/1748-7188-9-2⟩. ⟨hal-00971576⟩

Share

Metrics

Record views

626

Files downloads

307