TY  - JOUR
A1  - Cracco, Andrea
A1  - Tomescu, Alexandru I.
T1  - Extremely fast construction and querying of compacted and colored de Bruijn graphs with GGCAT
Y1  - 2023/07/01 
JF  - Genome Research 
JO  - Genome Research 
SP  - 1198 
EP  - 1207 
DO  - 10.1101/gr.277615.122 
VL  - 33 
IS  - 7 
UR  - http://genome.cshlp.org/content/33/7/1198.abstract 
N2  - Compacted de Bruijn graphs are one of the most fundamental data structures in computational genomics. Colored compacted de Bruijn graphs are a variant built on a collection of sequences and associate to each k-mer the sequences in which it appears. We present GGCAT, a tool for constructing both types of graphs, based on a new approach merging the k-mer counting step with the unitig construction step, as well as on numerous practical optimizations. For compacted de Bruijn graph construction, GGCAT achieves speed-ups of 3× to 21× compared with the state-of-the-art tool Cuttlefish 2. When constructing the colored variant, GGCAT achieves speed-ups of 5× to 39× compared with the state-of-the-art tool BiFrost. Additionally, GGCAT is up to 480× faster than BiFrost for batch sequence queries on colored graphs. 
ER  -