Variable-Order de Bruijn Graphs
Authors:
- Christina BoucherCBChristina Boucher
- Alex BoweABAlex Bowe
- Travis GagieTravis Gagie
- Simon J. PuglisiSPSimon J. Puglisi
- Kunihiko SadakaneKSKunihiko Sadakane
- 1 April 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10680314,p. 383-392
Abstract
The de Bruijn graph GK of a set of strings Sis 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 genomes. This problem is compounded because 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: they builddde Bruijn graphs, each with a specific order, i.e., GK1, GK2, GKd. Al-though, this paradigm increases the quality of the assembly produce but it greatly increases runtime, because of the need to construct graphs instead of one. 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 Kin 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.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Wavelet trees for allJournal of Discrete Algorithms, 2014
- Manifold de Bruijn Graphs2014
- On the Representation of de Bruijn Graphs2014
- Space-Efficient and Exact de Bruijn Graph Representation Based on a Bloom FilterLecture Notes in Computer Science, 2012
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static ArraysSIAM Journal on Computing, 2011
- Genome 10K: A Proposal to Obtain Whole-Genome Sequence for 10 000 Vertebrate SpeciesJournal of Heredity, 2009
- Sequencing of natural strains of Arabidopsis thaliana with short readsGenome Research, 2008
- ALLPATHS: De novo assembly of whole-genome shotgun microreadsGenome Research, 2008
- Practical Entropy-Compressed Rank/Select Dictionary2007
- A New Algorithm for DNA Sequence AssemblyJournal of Computational Biology, 1995