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

Kamil Salikhov, Gustavo Sacomoto, Gregory Kucherov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

31 Citations (Scopus)

Abstract

De Brujin graphs are widely used in bioinformatics for processing next-generation sequencing (NGS) data. Due to the 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. In this work, we show how to reduce the memory required by the algorithm of Chikhi and Rizk (WABI, 2012) that represents de Brujin graphs using Bloom filters. Our method requires 30% to 40% less memory with respect to their method, with insignificant impact to construction time. At the same time, our experiments showed a better query time compared to their method. This is, to our knowledge, the best practical representation for de Bruijn graphs.

Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings
Pages364-376
Number of pages13
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event13th Workshop on Algorithms in Bioinformatics, WABI 2013 - Sophia Antipolis, France
Duration: 2 Sep 20134 Sep 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8126 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Workshop on Algorithms in Bioinformatics, WABI 2013
Country/TerritoryFrance
CitySophia Antipolis
Period2/09/134/09/13

Fingerprint

Dive into the research topics of 'Using cascading bloom filters to improve the memory usage for de Brujin graphs'. Together they form a unique fingerprint.

Cite this