CALDERA

CALDERA identifies significant de Bruijn subgraphs to enhance bacterial genome-wide association studies (GWAS) by capturing polymorphic genes as cohesive units from k-mer-derived de Bruijn graphs.

Key Features:

• De Bruijn graph utilization: Constructs de Bruijn graphs (DBGs) from genomic k-mers and identifies closed connected subgraphs that represent polymorphic genes as cohesive units.
• Covariate construction: Builds covariates from closed connected subgraphs to use in association analyses, accommodating genetic diversity without requiring a common reference genome.
• Novel enumeration scheme: Implements an enumeration scheme to test all closed connected subgraphs efficiently by exploiting the concept of testable hypotheses.
• Improved statistical power and interpretability: Uses subgraph-level features to increase detection power and interpretability of associations compared with isolated k-mer approaches.

Scientific Applications:

• Bacterial GWAS: Maps genotype–phenotype associations in bacterial populations using subgraph-derived genetic features.
• Detection of genetic determinants of traits: Identifies genetic determinants of bacterial traits such as drug resistance and hypervirulence.

Methodology:

Construct de Bruijn graphs from genomic k-mers; identify closed connected subgraphs; construct covariates from those subgraphs for association testing; enumerate and test all closed connected subgraphs using a scheme that exploits testable hypotheses, thereby avoiding reliance on a common reference genome.