Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn Graphs

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Colored de Bruijn graphs (c-dBGs) are crucial for sequence indexing in computational biology.
• Large memory footprints of c-dBGs hinder scalability for extensive genomic datasets.
• Efficiently mapping k-mers to their color sets is essential for applications like read mapping and abundance estimation.

Purpose of the Study:

• To introduce novel lossless compressed data structures for c-dBGs.
• To address the significant memory challenges associated with large-scale sequence indexing.
• To improve the space-effectiveness of indexing k-mer color sets.

Main Methods:

• Leveraging the inherent repetitiveness of color sets in large, related genome collections.
• Factorizing color sets into repeating patterns across the entire dataset.
• Representing these patterns once to avoid redundant storage of atomic lists of integers.

Main Results:

• Achieved substantial improvements in space efficiency compared to previous solutions, with some indexes being an order of magnitude smaller.
• Demonstrated significant reductions in memory usage for c-dBG representations.
• Maintained only moderate impacts on query efficiency despite dramatic space savings.

Conclusions:

• The developed compressed data structures offer a highly space-effective solution for indexing colored de Bruijn graphs.
• These methods significantly reduce memory requirements for large-scale genomic data analysis.
• The approach balances substantial space reduction with acceptable query performance.