Source-linked AI summary
Using cascading Bloom filters to improve the memory usage for de Brujin graphs
Kamil Salikhov, Gustavo Sacomoto, Gregory Kucherov
TL;DR
Large NGS datasets make compact de Bruijn graph representations important. The paper recursively applies Bloom filters to represent false positives in the exact method of. It reports substantially lower memory use and faster queries than.
Problem
Large NGS datasets make compact de Bruijn graph representation important, and several approaches have been proposed.
Source: §1 · pp. 1–2Method
Results
30% to 40% less memory and 20% to 30% faster query times are reported compared with.
Source: §1 · p. 2, §5 · p. 10Takeaways & Limitations
The experiments support a practical exact de Bruijn graph representation that uses less memory and improves query time over.
Source: §1 · p. 2, §5 · p. 10The method could not be experimentally compared with.
Source: §5 · p. 11
Abstract
from arXiv · showhide
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. In this work, we show how to reduce the memory required by the algorithm of [3] that represents de Brujin graphs using Bloom filters. Our method requires 30% to 40% less memory with respect to the method of [3], with insignificant impact to construction time. At the same time, our experiments showed a better query time compared to [3]. This is, to our knowledge, the best practical representation for de Bruijn graphs.
1 Introduction
Huge NGS datasets make compact de Bruijn graph representations important. This section situates the work among prior approaches and introduces a recursive Bloom-filter improvement to, reporting lower memory use and faster queries.
1 Introduction
- NGS reads can number in the hundreds of millions and total tens or hundreds of Gb, motivating compact graph representations.De Bruijn graphs underpin many tools for NGS data, especially genome assembly.Source: §1 · p. 1
- Prior compact representations include succinct structures, sparse storage, and probabilistic graphs; Chikhi and Rizk made the probabilistic scheme exact.For multiple reads, has size 4m + O(M log m) bits, whose practical second-term constant is unclear.Source: §1 · p. 2
- 30% to 40% less memory and 20% to 30% faster query times than are reported for the cascading Bloom-filter method.The experiments also confirm theoretical predictions for structure size.Source: §1 · p. 2
- The method improves by recursively applying Bloom filters to false positives and storing successive false-positive sets.The paper reports 30% to 40% less memory than, with memory growing little as k grows.Source: §1 · p. 2
2 Cascading Bloom filter
The section extends the exact representation in by recursively encoding successive false-positive sets with Bloom filters. Membership is recovered from the first filter that rejects a queried k-mer, with a finite implementation storing the final set explicitly.
2 Cascading Bloom filter
- The first filter stores T0, while T1 records potential neighboring k-mers falsely accepted by that filter.The method relies on queries being restricted to graph nodes and their potential neighbors.Source: §2 · p. 3
- The construction recursively represents each false-positive set with a new Bloom filter and tracks the next set of mistakes.B_i stores T_i−1; T_i contains elements accepted by B_i that do not belong to T_i−1 but do belong to T_i−2.Source: §2 · p. 3
- Membership in T0 is determined by the parity of the first rejected filter: odd means present, while even means absent.If B1 rejects K, the index is defined as zero.Source: §2 · p. 3
- The correctness argument uses the Bloom-filter property that a rejection proves non-membership in the represented set, alongside the graph-query restriction in.The induction places K in the relevant alternating sets until the first filter rejects it.Source: §2 · p. 3
- A finite implementation stores B1 through Bt and explicitly represents Tt; if all filters accept K, membership is checked against Tt.This truncates the otherwise infinite sequence of filters.Source: §2 · pp. 3–4
3 Memory and time usage
The section estimates memory use for cascading Bloom filters, then considers finite cascades and per-filter sizing. It reports that small cascades retain near-optimal, nearly k-independent space, while varying filter sizes yields further savings.
3 Memory and time usage
- With infinitely many filters, the estimated minimum is 8.45 bits per k-mer at r = 5.464.The estimate refines the critical false-positive count from eight potential extensions to six for almost all nodes.Source: §3 · p. 4
- For t = 4, estimated space per k-mer is close to the infinite-filter optimum and remains almost constant across k.Table 1 compares the t = 4 estimate with the method of [3] (t = 1).Source: §3 · p. 5, Table 1 · p. 5
- Doubling k increases memory by 1.44 bits in, versus 0.11 to 0.22 bits with this method.Source: §3 · p. 5
- With small t, preprocessing grows insignificantly versus, and querying can be faster when savings from checking the smaller Tt outweigh querying multiple filters.The authors state that experiments confirm this query-time trade-off.Source: §3 · pp. 5–6
3.1 Using different values of r for different filters
- For finite cascades with different ri, the space estimate combines a truncated bitmap sum with explicit storage for Tt, so the optimal filter ratios must be adjusted.The stated Tt storage estimate depends on whether t is even or odd.Source: §3 · p. 4, §3.1 · p. 6
- The minimum value of the expression becomes 7.913; separately, in the truncated case, using different ri values gives a small 2% to 4% improvement over a unique r.Source: §3.1 · p. 6
4 Experimental results
Across E. coli and human-read tests, 4 Bloom reduced structure size and improved traversal time over 1 Bloom, while construction time increased on the human dataset.
4.1 Implementation and experimental setup
- The tests compared 1, 2, and 4 Bloom versions using Minia, with construction and membership-query changes evaluated against.For the varying-k tests, the authors used 10M 100bp E. coli reads and extracted k-mers occurring at least twice.Source: §4.1 · pp. 6–7, §4.2 · p. 7
4.2 E.coli dataset, varying k
- 32% to 39% less structure size with 4 Bloom and 18% to 30% faster traversal than were observed across the tested k values.The 4-Bloom structure ranged from 8.60 to 8.89 bits per stored k-mer, an increase of only 3%; construction was 5% to 22% faster in these tests.Source: §4.2 · pp. 7–8, Figure 1 · p. 9
4.3 E. coli dataset, varying coverage
- With increasing E. coli coverage, memory per k-mer stayed almost constant and 4 Bloom used 33% less memory than 1 Bloom.Distinct k-mers rose by around 10% per additional 5M reads, which the authors attribute to sequencing errors not removed by cutoff d = 3.Source: §4.3 · p. 8, Figure 2 · p. 10
4.4 Human dataset
- On the human dataset, 4 Bloom reduced structure size by 34% and traversal time by 26%, but construction time rose by 10% (4 Bloom) and 7% (2 Bloom) versus 1 Bloom.Disk writing and reading dominated construction time, and the 2- and 4-Bloom versions made more disk accesses.Source: §4.4 · pp. 8, 10
5 Discussion and Conclusions
Cascading Bloom filters use 30%–40% less memory than the single-filter method, with query time also lower and construction time ranging from 10% slower to 22% faster. The authors could not experimentally compare their method with and identify a possible Bloom-filter replacement as future work.
5 Discussion and Conclusions
- 30%–40% less memory and 20%–30% lower query time than the single-filter method, with construction time ranging from 10% slower to 22% faster.The structure uses 8.5–9 bits per stored k-mer, compared with 13–15 bits for.Source: §5 · p. 10
- No experimental comparison with was possible because its implementation was unavailable; its space bound depends heavily on read count, unlike the new structure’s near-invariance to coverage.The coverage observation is reported in Section 4.3.Source: §5 · pp. 10–11
- Work suggests a possible reduction to about 5 bits per k-mer, but replacing Bloom filters may significantly increase construction and query time, an issue requiring further study.Source: §5 · p. 11