Space-efficient and exact de Bruijn graph representation based on a Bloom filter

By Rayan Chikhi, Guillaume Rizk. Algorithms for Molecular Biology, 2012

415 citations recorded by the source corpus.

The de Bruijn graph data structure is widely used in next-generation sequencing (NGS). Many programs, e.g. de novo assemblers, rely on in-memory representation of this graph. However, current techniques for representing the de Bruijn graph of a human genome require a large amount of memory (≥30 GB). We propose a new encoding of the de Bruijn graph, which occupies an order of magnitude less space than current representations. The encoding is based on a Bloom filter, with an additional structure to remove critical false positives. An assembly software implementing this structure, Minia, performed a complete de novo assembly of human genome short reads using 5.7 GB of memory in 23 hours.

Subfields: Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/a1737410449fa937b2f621b3a731b7071d6f7be9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Genotyping-By-Sequencing for Plant Genetic Diversity Analysis: A Lab Guide for SNP Genotyping (2014, methodology): “Minia software [25,26] is used to construct the de novo reference contigs for calling SNPs.”
ABySS 2.0: resource-efficient assembly of large genomes using a Bloom filter (2016, neutral): “…include the following: (1) SGA (Simpson and Durbin 2011), which uses the Burrows-Wheeler transform to compress and index sequencing data; (2) Minia (Chikhi and Rizk 2013), which uses a Bloom filter (Bloom 1970) to represent the de Bruijn graph; (3) BCALM 2 (Chikhi et al. 2016), which employs…”
Variation graph toolkit improves read mapping by representing genetic variation in the reference (2018, neutral): “Overall vg performs at least as well as bwa mem even on reference-derived reads, and substantially better on reads containing non-reference variants.”
Informed and automated k-mer size selection for genome assembly (2013, methodology): “…methods were developed, there have been numerous improvements and the ﬁeld is now rich with tools that provide biologists several options [Ribeiro et al., 2012, Luo et al., 2012, Bankevich et al., 2013, Chikhi and Rizk, 2012, Peng et al., 2012, Simpson and Durbin, 2011, Zerbino and Birney, 2008].”
metaSPAdes: a new versatile metagenomic assembler. (2017, methodology): “Chikhi and Rizk (2013 ) developed Minia assembler that efficiently represents the de Bruijn graphs using the Bloom filter (Chikhi and Rizk 2013; Salikhov et al. 2014).”
MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph (2014, methodology): “To evaluate the performance on large scale metagenomics data, we assembled an Iowa prairie soil metagenomics dataset that comprises 3.3 billion reads totaling 252 billion base-pairs (Howe, et al., 2014) using MEGAHIT and Minia, another memory-efficient as-sembler (Chikhi and Rizk, 2012).”
Critical Assessment of Metagenome Interpretation: the second round of challenges (2021, background): “On strain-madness data, GATB 21,22 ranked best, with HipMer in second place.”