Variable-Order de Bruijn Graphs

The de Bruijn graph GK 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 or update d de Bruijn graphs, each with a specific order, i.e., GK1, GK2,..., GKd. Although, this paradigm increases the quality of the assembly produced, it increases the run time by roughly a factor of d. 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.