Lossless indexing with counting de Bruijn graphs.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Public sequencing data repositories are growing rapidly, necessitating efficient storage and indexing for large-scale analysis.
• Existing annotated de Bruijn graphs excel at indexing k-mer sets but struggle with quantitative attributes like gene expression or genome positions.

Purpose of the Study:

• To propose and evaluate counting de Bruijn graphs, a novel data structure generalizing annotated de Bruijn graphs.
• To enable efficient indexing of quantitative attributes, such as k-mer counts and positional information, within compressed graph representations.

Main Methods:

• Developed the concept of counting de Bruijn graphs, which augment node-label relations with attributes.
• Applied counting de Bruijn graphs to index k-mer abundances from human RNA-seq data.
• Utilized positional annotations within counting de Bruijn graphs to index entire sequencing reads.

Main Results:

• Counting de Bruijn graphs achieved over eightfold smaller representations for k-mer abundances compared to state-of-the-art tools, with faster construction and querying.
• Positional annotations resulted in indexes 27% smaller (human RNA-seq) and 57% smaller (viral PacBio HiFi) than gzip-compressed input.
• A comprehensive index of viral PacBio SMRT reads (875 Gbp) occupied only 178 GB.
• Generated a lossless, queryable index of the RefSeq collection 4.6-fold smaller than MegaBLAST.

Conclusions:

• Counting de Bruijn graphs offer a significant advancement in compressing and indexing sequencing data, particularly for quantitative attributes.
• This approach enhances existing de Bruijn graph methods, broadening their applicability for tasks like k-mer counting, positional indexing, and novel sequence alignment algorithms.