GGCAT

GGCAT constructs and queries compacted and colored de Bruijn graphs for efficient representation and analysis of genomic sequences.

Key Features:

• Compacted de Bruijn graphs: Constructs compacted de Bruijn graphs that collapse repetitive regions into unitigs to reduce graph complexity while preserving sequence connectivity.
• Colored compacted de Bruijn graphs: Associates k-mers with sample-specific colors to enable multi-sample analyses such as haplotype phasing and comparative metagenomics.
• Integrated k-mer counting and unitig construction: Integrates the k-mer counting step directly with unitig construction to streamline graph building and improve throughput.
• Practical optimizations: Implements performance-focused optimizations that reduce computation time and memory footprint compared to alternative approaches.
• Performance benchmarks: Reports speed-ups of 3×–21× versus Cuttlefish 2 for compacted graph construction, 5×–39× versus BiFrost for colored compacted graph construction, and up to 480× faster batch sequence queries on colored graphs versus BiFrost.

Scientific Applications:

• Genome assembly: Enables assembly workflows by providing compact graph representations of sequencing reads.
• Variant calling and detection: Supports variant discovery by representing sequence variation within the graph structure.
• Haplotype phasing: Uses colored graphs to trace k-mer presence across samples for phasing analyses.
• Metagenomic studies: Facilitates analysis of mixed-species samples through colored graph comparisons and unitig representation.
• Comparative genomics and population structure: Supports multi-sample comparisons to explore genetic diversity and population-level variation.

Methodology:

Constructs compacted and colored de Bruijn graphs and integrates k-mer counting directly with unitig construction; supports querying of colored graphs for batch sequence searches.