GGCAT: an optimized tool for fast compacted and colored de Bruijn graph construction

De Bruijn graphs are a widely used data structure in bioinformatics, often serving as the basis for more complex analyses. In this thesis, we present a tool called GGCAT and its updated version GGCAT 2 to compute compacted and optionally colored de Bruijn graphs for DNA datasets. GGCAT outperforms other state-of-the-art tools available for this task in time, memory, and temporary disk space usage on many different kinds of data, from pangenomes to sequencing reads. This is due to a set of optimized algorithms designed to reduce both runtime and memory usage. GGCAT 2 is a major overhaul of the first version, with improvements in all performance metrics, and in particular a large reduction in the required temporary disk space through a novel compaction technique. It supports multiple representations of de Bruijn graphs, from classical maximal unitigs to the more compact simplitigs and minimum-size eulertigs, all with custom algorithms able to handle extremely large datasets. The tool is open source and available on GitHub.