Copyright Alan Kuhnle, Victoria Crawford
Compact data structures for the representation of de Bruijn graphs are important for genome sequence assembly. A fully dynamic data structure supporting efficient and exact membership queries for de Bruijn graphs was recently proposed in [1]. This software is an implementation of the data structure in [1] with dynamic edges (and not dynamic nodes).
[1]: Belazzougui, D., Gagie, T., Maekinen, V., and Previtali, M. (2016). Fully Dynamic de Bruijn Graphs. In String Processing and Information Retrieval, pages 145–152.
This implementation depends on the Boost C++ library: http://www.boost.org/doc/libs/1_59_0/more/getting_started/unix-variants.html
Installing Boost on a Debian-based system should require only the following command:
sudo apt-get install libboost-all-dev
We use the BBhash implementation of a minimal perfect hash function, which is included in our source code. The implementation is available here: https://github.com/rizkg/BBHash/
The dynamic De Bruijn graph is implemented in the class FDBG in cpp-src/FDBG.cpp.
We provide a program cpp-src/BuildDataStructure.cpp that takes in a fasta file and a k-mer length. A Makefile to compile this file is provided in cpp-src, which may need to be edited to include the Boost location on your system.
In the cpp-src directory, a file yeast.fasta is present. This is the reference genome for yeast strain S288C in fasta format; it can be used to test our data structure with the BuildDataStructure.cpp example program.
- Install the Boost dependency (see dependencies above).
- Go to ./cpp-src
- Compile using the included Makefile, editing it if necessary.
make - After compilation, the executable bds should have been produced. This program requires two arguments.
The first argument is any fasta file, for example the included yeast.fasta file. The second argument
is the desired value of k for de Bruijn graph, must be between 1 and 31.
Example:
./bds yeast.fasta 20
During execution, bds will print detailed logs to the screen. These logs indicate when each step of the construction of the data structure begins. In order, these steps are the following
- Parses fasta file
- Writes binary files for the k-mers found so that on future runs, these files are loaded instead
- Begins construction of De Bruijn graph
- Construction of Karp-Rabin hash function
- Injectivity test
- Construction of minimal perfect hash function
- Computation of r inverse modulo P
- Construction of IN, OUT matrices
- Forest construction
- Once construction is complete, the data structure is saved in binary format to a file.
- Tree height tests are conducted on the forest
- Edges are dynamically removed from the data structure, and then added back in; the forest is updated after each change.
The prime required to build the hash function must be at least n^2, where n is the number of nodes in the graph. In our implementation, the prime is stored in 64 bits. This means that n <= 3037000499 in order for the hash function to be constructed. To allow for greater values of n, BBHash would need to be modified. See the paper for more details.