Source-linked AI summary
Succinct Data Structures for Assembling Large Genomes
Thomas C Conway, Andrew J Bromage
TL;DR
Genome assembly requires processing large collections of short reads, but de Bruijn graph assemblers face severe memory constraints. The paper uses entropy-compressed and succinct data structures to represent these graphs near theoretical space limits. The representation uses about 5.2 bytes per edge and enables larger genomes to fit in memory than the compared velvet runs.
Problem
De novo assembly is limited by computational hardness and the high practical memory requirements of de Bruijn graph assemblers.
Method
The paper represents read-supported de Bruijn assembly graphs with entropy-compressed and succinct data structures, including sparse and near-optimal bitmap representations.
Results
5.2 bytes per edge were required by the representation, while its compactness allowed the thalassiosira genome to fit in memory with 302 MB for the graph.
Takeaways & Limitations
The representation was effective across genomes from bacterial to mammalian scale and supports further work toward a practical assembler.
Takeaways & Limitations
The paper does not address sequencing-error detection or correction and does not resolve the identification of true paths among combinatorially many Eulerian paths.
Abstract
from arXiv · showhide
Motivation: Second generation sequencing technology makes it feasible for many researches to obtain enough sequence reads to attempt the de novo assembly of higher eukaryotes (including mammals). De novo assembly not only provides a tool for understanding wide scale biological variation, but within human bio-medicine, it offers a direct way of observing both large scale structural variation and fine scale sequence variation. Unfortunately, improvements in the computational feasibility for de novo assembly have not matched the improvements in the gathering of sequence data. This is for two reasons: the inherent computational complexity of the problem, and the in-practice memory requirements of tools. Results: In this paper we use entropy compressed or succinct data structures to create a practical representation of the de Bruijn assembly graph, which requires at least a factor of 10 less storage than the kinds of structures used by deployed methods. In particular we show that when stored succinctly, the de Bruijn assembly graph for homo sapiens requires only 23 gigabytes of storage. Moreover, because our representation is entropy compressed, in the presence of sequencing errors it has better scaling behaviour asymptotically than conventional approaches.
1 INTRODUCTION
De novo genome assembly faces computational and memory barriers, especially for de Bruijn graph methods handling many short reads. The paper motivates compact graph representations that preserve efficient access while reducing storage demands.
- 1 INTRODUCTION: De Bruijn graph assembly has pressing memory demands, motivating extremely compact representations with efficient access operations.The proposed entropy-compressed or succinct structures approach theoretical space bounds while supporting constant- or logarithmic-time queries.
- 1.1 de Bruijn Graphs & Assembly: De Bruijn graphs represent k-mers as nodes and connect overlapping k-mers whose shared substrings have length k −1.Genome assembly uses a read-supported subset of this graph, with edge counts recording observed ρ-mers.
- 1.1 de Bruijn Graphs & Assembly: Each node has at most four successor and four predecessor nodes because the DNA alphabet contains four symbols.Successors extend the node’s final k bases by each possible DNA symbol.
- 1.1 de Bruijn Graphs & Assembly: Assembly paths must account for reverse-complement reads, and the graph’s Eulerian structure links assembled sequences to Eulerian tours.Reads are processed in both directions, with reverse-complement nodes commonly merged and edges made bidirected.
- 1.1.2 From de Bruijn Assembly Graphs To Genomes: At 40× coverage, sequencing errors are expected to produce about 14 million spurious edges, outnumbering true edges by 14-fold.True-edge counts remain stable as coverage increases, while unique error-derived edges grow linearly.
- 1.1.2 From de Bruijn Assembly Graphs To Genomes: Existing assemblers reduce memory through reverse-complement merging and unbranched-path merging, but these techniques are characterized as ad hoc.The discussion therefore motivates avoiding pointer-heavy graph representations through more principled compact structures.
2 APPROACH
The approach represents the de Bruijn assembly graph near its information-theoretic minimum by encoding its edges succinctly and inferring nodes from them. Bitmap queries and rank/select operations support efficient graph traversal and edge-count access.
- The approach reframes pointer storage as an information-representation problem, asking which graph information is necessary rather than storing every explicit node connection.
- The representation targets the information-theoretic lower bound for the edge subset while retaining efficient random access.The edge set's self-information determines the minimum number of bits needed to encode the graph.
- For k = 25, the human genome yields 4,796,397,453 distinct de Bruijn assembly-graph edges, including reverse complements.
- The graph is encoded as a sparse bitmap over all possible edges, with set bits identifying assembly-graph edges and nodes inferred from those edges.For a node n, probing the four candidate successor-edge positions determines its successor set.
- Rank and select operations map bitmap positions to edge ranks, enabling efficient traversal of successor edges.These operations are inverses and allow successor-edge ranks to be computed from the bitmap.
3 METHODS
The methods exploit the graph's extreme sparsity with succinct bitmap structures and construct the representation through external sorting and merging of ρ-mers. Edge counts are also compressed while preserving random access.
- The human-genome bitmap is extremely sparse: only 4.7 × 10^9 of 4.5 × 10^15 bits are set, a fraction of 10^-8.An uncompressed bitmap would require 512TB for the typical ρ = 26 case, motivating sparse encoding.
- Succinct representations store bitmaps close to their theoretical minimum while supporting rank and select efficiently.The framework distinguishes dense and sparse bitmaps and uses Elias–Fano coding for sparse representations.
- The darray, sarray, and rrrarray structures provide alternatives optimized for dense, sparse, or broadly varying bitmap densities.
- The graph is constructed by extracting ρ-mers, sorting them into disk runs, binary-merging the runs, and counting duplicates into edge-count pairs.The merging phase uses log N passes over pairs of sorted runs.
- Edge counts are compressed by separating each count into least-significant, middle, and most-significant bit fields with succinct bitmaps for sparse components.The least significant 8 bits are stored in a dense byte vector, while bitmap annotations identify entries requiring additional fields.
4 RESULTS
The succinct representation builds assembly graphs compactly across reference genomes, with graph size varying less than construction time. It uses less storage than pointer-based approaches while retaining practical graph traversal.
- The tested genomes were evaluated by distinct edge count, assembly-graph size including edge counts, and graph-construction time.
- 325 MB of peak memory assembled Mycobacterium leprae with Velvet, while the succinct graph and edge counts required 32 MB.Velvet failed on the next-smallest tested genome after exhausting main memory.
- 302 MB stored the Thalassiosira graph, plus about 4 MB for traversal structures, allowing the genome to fit easily in memory.The depth-first traversal visited approximately every node once and took 202 seconds on a graph with 60,312,974 edges.
5 DISCUSSION
The representation is succinct and practical, but completing a de novo assembler requires additional error handling, path disambiguation, and implementation improvements.
- Succinct representations use within a small constant factor of minimum possible space, distinguishing this approach from alternative memory-reduction methods.The paper also considers cuckoo-hashing-based representations as a competing approach.
- The current representation does not address sequencing-error detection or correction and requires reads and paired reads to disambiguate Eulerian paths.Reads support initial path disambiguation, while paired-end or mate-pair reads support scaffolding.
- The graph representation relies on de Bruijn graph relationships and cannot be treated as an arbitrary graph by duplicating or arbitrarily merging graph parts.Edges may be added or removed, but arbitrary graph transformations are outside the representation's stated assumptions.
- 5.1 A Succinct Representation of Sequence Reads: Sequence reads can be compactly represented by storing initial k-mers, read lengths, and edge choices relative to paths in the de Bruijn graph.Sorted reads support indexing by initial k-mer; sparse bitmaps encode read starts and two-bit edge ranks encode path choices.
- 5.1 A Succinct Representation of Sequence Reads: Reads not represented as graph paths can be encoded against a nearest path using divergence positions and the corresponding read bases.Finding the nearest path is an optimization problem for which the paper suggests simple heuristics may suffice.
- 5.1 A Succinct Representation of Sequence Reads: The scheme could encode explicit gaps in technologies such as strobe reads by adding an auxiliary bitmap, identified as future research.This extension is presented as a possible generalization rather than a completed component.
6 CONCLUSION
The paper presents a memory-efficient, near-minimal-bit representation of de Bruijn assembly graphs and demonstrates it across bacterial and mammalian genomes.
- Succinct data structures represent de Bruijn assembly graphs close to the minimum number of bits while remaining memory-efficient.The authors state that the representation was demonstrated on genomes ranging from bacterial to mammalian scale, including human.
Funding:
The work acknowledges funding from Australian government and research programs through NICTA.
- NICTA was funded by the Australian Government's communications department, the Australian Research Council, and ICT Centre of Excellence programs.