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

Abstract

Background: 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).

Results: 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.

Conclusions: 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.

Figure 1

A complete example of removing false positives in the probabilistic de Bruijn graph. (a) shows$\hspace{0.17em}\mathcal{S}$, an example de Bruijn graph (the 7 non-dashed nodes), and$\hspace{0.17em}\mathcal{ℬ}$, its probabilistic representation from a Bloom filter (taking the union of all nodes). Dashed rectangular nodes (in red in the electronic version) are immediate neighbors of$\hspace{0.17em}\mathcal{S}$ in$\hspace{0.17em}\mathcal{ℬ}$. These nodes are the critical false positives. Dashed circular nodes (in green) are all the other nodes of$\hspace{0.17em}\mathcal{ℬ}$; (b) shows a sample of the hash values associates to the nodes of$\hspace{0.17em}\mathcal{S}$ (a toy hash function is used); (c) shows the complete Bloom filter associated to$\hspace{0.17em}\mathcal{S}$; incidentally, the nodes of$\hspace{0.17em}\mathcal{ℬ}$ are exactly those to which the Bloom filter answers positively; (d) describes the lower bound for exactly encoding the nodes of$\hspace{0.17em}\mathcal{S}$ (self-information) and the space required to encode our structure (Bloom filter, 10 bits, and 3 critical false positives, 6 bits per 3-mer).

Figure 2

Optimal data structure size for the parameterr, then for the parameterk.(a) Structure size (Bloom filter, critical false positives) in function of the number of bits per k-mer allocated to the Bloom filter (also called ratio r) for k = 27. The trade-off that optimizes the total size is shown in dashed lines. (b) Optimal size of the structure for different values of k.

Figure 3

Data structure sizes for the probabilistic de Bruijn graph. Data structure sizes (Bloom filter, marking structure, and cFP if applicable) for the probabilistic de Bruijn graph with (top right) and without the cFP structure (top left), for an actual dataset (E. coli, k = 23). All plots are in function of the number of bits per k-mer allocated to the Bloom filter. Additionally, the difference is shown (bottom left and bottom right) between a reference assembly made using an exact de Bruijn graph, and an assembly made with each structure.