  The de Bruijn graph $G_K$ of a set of strings $S$ is a key data structure in
genome assembly that represents overlaps between all the $K$-length substrings
of $S$. Construction and navigation of the graph is a space and time bottleneck
in practice and the main hurdle for assembling large, eukaryote genomes. This
problem is compounded by the fact that state-of-the-art assemblers do not build
the de Bruijn graph for a single order (value of $K$) but for multiple values
of $K$. More precisely, they build $d$ de Bruijn graphs, each with a specific
order, i.e., $G_{K_1}, G_{K_2}, ..., G_{K_d}$. Although, this paradigm
increases the quality of the assembly produced, it increases the memory by a
factor of $d$ in most cases. In this paper, we show how to augment a succinct
de Bruijn graph representation by Bowe et al. (Proc. WABI, 2012) to support new
operations that let us change order on the fly, effectively representing all de
Bruijn graphs of order up to some maximum $K$ in a single data structure. Our
experiments show our variable-order de Bruijn graph only modestly increases
space usage, construction time, and navigation time compared to a single order
graph.
