cdbg

cdbg constructs compressed de Bruijn graphs to compactly represent genetic variation across multiple genomes for population genomics.

Key Features:

• Compressed Representation: Uses a compressed de Bruijn graph format to encapsulate population-scale genomic data for space-efficient storage and manipulation.
• Algorithmic Efficiency: Implements algorithms that outperform previous methods such as splitMEM, which were limited to smaller datasets.
• Linear-Time Suffix Tree Algorithm: Incorporates a linear-time suffix tree algorithm using a compressed suffix tree approach.
• Burrows-Wheeler Transform (BWT): Employs the Burrows-Wheeler transform to construct the compressed de Bruijn graph, with running time proportional to [Formula: see text], where σ represents the alphabet size.
• Scalability: Demonstrated on seven human genomes, indicating capability to handle large-scale, complex genomic datasets.

Scientific Applications:

• Population Genomics: Captures variation across multiple individuals to support analyses of genetic diversity and population structure.
• Genome Sequencing Analysis: Provides a space-efficient representation to support analysis of complete genomes and low-cost genome sequencing efforts.

Methodology:

Constructs compressed de Bruijn graphs directly from genomic data without uncompressed intermediate representations using suffix trees, a compressed-suffix-tree linear-time suffix tree algorithm, and the Burrows-Wheeler transform (BWT), with the BWT-based construction running in time proportional to [Formula: see text] where σ denotes the alphabet size.