Abstract
<title>Abstract</title> <p>Succinct de Bruijn graphs (dBGs) store a k-mer graph in four to five bits per edge, enabling metagenome assemblers to run on modern computers. Yet standard traversal methods, such as breadth-first search (BFS) with a 32-bit distance array or depth-first search (DFS) with a node stack, require Θ(N log N) bits, exceeding the graph size. Space-efficient traversal techniques using O(N) bits have been available for a decade, but they have not been implemented or tested on a succinct dBG. We implemented a bitmap-plus-streamed-distance BFS and an ElmasryHagerup-Kammer-style DFS on a succinct de Bruijn graph and evaluated their performance on a graph of 800 million edges. The pure algorithmic reduction, in the auxiliary state and excluding the shared graph, is 11× for BFS and 4.7× for DFS. The overall reduction in memory is bounded by the size of the graph representation, resulting in 2.36× for BFS and 1.64× for DFS on this graph.</p>