Source-linked AI summary
Scaling metagenome sequence assembly with probabilistic de Bruijn graphs
Jason Pell, Arend Hintze, Rosangela Canino-Koning, Adina Howe, James M. Tiedje, C. Titus Brown
TL;DR
Complex metagenomes can exceed available memory during de novo assembly. This paper uses Bloom-filter probabilistic de Bruijn graphs to partition assembly graphs, reducing peak assembly memory by nearly 40-fold for a soil metagenome.
Problem
Complex metagenomes can require terabytes of memory for de novo assembly, exceeding the capacity of available computers.
Method
The paper stores k-mers in Bloom filters to represent and traverse de Bruijn graphs probabilistically, then partitions the graphs before assembly.
Results
Nearly 40-fold lower peak memory was achieved for assembly of a real soil metagenome, with identical assembly results.
Takeaways & Limitations
Probabilistic graph storage provides a memory-efficient approach for scaling metagenome assembly and analyzing large assembly graphs.
Takeaways & Limitations
False-positive connectivity can distort graph structure if the false-positive rate becomes too high, so effective partitioning requires staying below a percolation threshold.
Abstract
from arXiv · showhide
Deep sequencing has enabled the investigation of a wide range of environmental microbial ecosystems, but the high memory requirements for {\em de novo} assembly of short-read shotgun sequencing data from these complex populations are an increasingly large practical barrier. Here we introduce a memory-efficient graph representation with which we can analyze the k-mer connectivity of metagenomic samples. The graph representation is based on a probabilistic data structure, a Bloom filter, that allows us to efficiently store assembly graphs in as little as 4 bits per k-mer, albeit inexactly. We show that this data structure accurately represents DNA assembly graphs in low memory. We apply this data structure to the problem of partitioning assembly graphs into components as a prelude to assembly, and show that this reduces the overall memory requirements for {\em de novo} assembly of metagenomes. On one soil metagenome assembly, this approach achieves a nearly 40-fold decrease in the maximum memory requirements for assembly. This probabilistic graph representation is a significant theoretical advance in storing assembly graphs and also yields immediate leverage on metagenomic assembly.
Introduction
The introduction frames metagenome assembly as a memory-scaling problem and presents probabilistic de Bruijn graphs based on Bloom filters as a memory-efficient solution. Read partitioning using this representation reduces soil metagenome assembly memory nearly 40-fold.
- Motivation: Deep sequencing of complex microbial ecosystems can produce shotgun datasets that exceed available computer memory, limiting current assembly methods.These ecosystems may contain millions of microbial species and remain poorly understood because many microbes cannot be cultured or studied individually.
- Memory bottleneck: De Bruijn graph memory scales with unique k-mers, so soil metagenomes may require terabytes of memory despite human genomes assembling in less than 512GB.The graph stores k-mers rather than reads, but soil samples can contain millions or more species and substantial abundance variation.
- Probabilistic representation: The work introduces a Bloom-filter representation for storing de Bruijn graphs in fixed memory, permitting false positives but not false negatives.Bloom filters store sparse sets without collision detection, and the paper applies them to assembly graphs.
- Read partitioning: Read partitioning separates the probabilistic de Bruijn graph into disconnected components so subsets of reads can be assembled separately.This exploits the biological feature that many metagenomic microbes should not assemble together.
- Result: Nearly 40-fold decrease in memory required for soil metagenome assembly is achieved by applying the probabilistic graph representation to partitioning.The result demonstrates immediate leverage of the representation for scaling metagenome assembly.
Results
Bloom-filter graphs preserved large-scale DNA de Bruijn graph structure below an approximately 18% false-positive threshold, while sequencing errors contributed more complexity than reasonable graph approximation. The approach reduced graph-storage and metagenome-assembly memory substantially without changing the resulting assembly.
- Graph fidelity: 15% false positives did not systematically connect distant k-mers, whereas rates above 20% produced spurious real-k-mer connections that lowered component diameter.The larger-scale graph structure remained retained through p = 0.183.
- Graph fidelity: 18.3% ± 0.1% was the estimated site percolation threshold for DNA de Bruijn graphs with k between 5 and 12.The threshold appeared independent of k within the tested range.
- Graph fidelity: Below 18% false positives, large-scale graph connectivity was unlikely to change.Component-size analysis suggested global connectivity was retained up to the percolation threshold.
- Graph fidelity: Sequencing errors outweighed errors from inexact graph representation at a reasonable false-positive rate.In an exact Illumina representation, only 9.9% of graph k-mers truly existed in the reference genome.
- Metagenome assembly: 30-fold lower maximum memory usage was achieved by partitioning the dataset before ABySS assembly, while all assemblies remained identical with 1,444 contigs totaling 1.07 megabases.The unpartitioned dataset required 33GB, whereas partitioning required under 1GB.
Discussion
Probabilistic de Bruijn graphs provide tunable, fixed-memory storage that can preserve large-scale graph structure while substantially reducing metagenome assembly memory through partitioning. Their utility depends on controlling false positives below the connectivity threshold, after which partitions can be assembled flexibly and efficiently.
- Graph representation: 1% false positive rates still provide efficient graph representations, improving theoretical and actual memory usage over Velvet and ABySS.The false positives are fewer than erroneous k-mers generated by sequencing errors and have less effect on branching structure.
- False-positive effects: 18.3% marks the reported boundary below which long false paths are not spontaneously created and large-scale graph properties do not change.Above this rate, the global graph structure slowly degrades.
- Partitioning: 20-40x decrease in memory produced identical partitioning results for the MSB2 soil metagenome.The E. coli analysis also achieved a 30-fold decrease in memory usage over the exact representation at a false positive rate of 1%.
- Partitioning: 345,000 reads was the size of the largest MSB2 partition, keeping downstream assembly memory requirements small despite higher partitioning memory at a false positive rate of 15%.The higher partitioning memory resulted from larger components created by local false positives.
- Downstream assembly: Partitioned components can be assembled with parameters matched to each partition’s coverage and heterogeneity, enabling rapid exploration of multiple assembly settings.Data partitioned at a low k0 can be exactly assembled with any k ≥ k0 because shorter overlaps include all longer overlaps.
- Graph representation: 4 bits per k-mer is achievable because Bloom-filter storage supports a wide range of tunable false positive rates without changing the graph’s global structure.Higher false positive rates trade memory savings for more elaborate local structure and longer traversal time.
Assembler software.
The study used ABySS and Velvet for assembly, while implementing its probabilistic graph representation and partitioning algorithm in the open-source khmer package.
- Assembler software: Assemblies used ABySS v1.3.1 with 31-mers and Velvet v1.1.07, but Velvet was excluded from partitioning analysis because stochastic error correction makes results depend on read order.ABySS was run with 8 processes; Velvet was run with velveth and velvetg.
- Assembler software: The graph representation and partitioning algorithm were implemented in khmer, written in C++ and Python 2.6 and released under the BSD open source license.The package and figure-generation scripts are available in the khmer repository; graph visualizations used Graphviz.
Average Component Size
Average component size rises sharply as the false positive rate approaches the percolation threshold. In randomly generated circular chromosomes, graph diameter remains constant through an 18.3% false positive rate.
- Average component size sharply increases as the false positive rate approaches the percolation threshold.
- Length of Longest Shortest Path: 18.3% is the highest stated false positive rate through which circular-chromosome diameter remains constant.The comparison uses randomly generated 58bp circular chromosomes represented as cycles of 50 8-mers, considering only real k-mers as endpoints.
- Bloom filters become more efficient than lossless data structures at higher k values because inserted k-mers are sparser than all possible k-mers.
- Percolation-threshold estimates were evaluated across k values from 5 to 12, with lower k showing greater finite-size sampling errors.The analysis defines p as the fraction of nodes present and θ as the fraction of nodes in the largest component.