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 analysis but suffer from high memory demands.
• Efficiently indexing large collections of reference sequences is a significant challenge in bioinformatics.

Purpose of the Study:

• To introduce novel, lossless compressed data structures for c-dBGs.
• To address the memory usage challenge in large-scale sequence indexing.

Main Methods:

• Leveraging the repetitiveness of color sets in large genome collections.
• Factorizing color sets into repeating patterns and representing them efficiently.
• Developing algorithms for lossless compression of c-dBGs.

Main Results:

• Achieved substantial improvements in space efficiency compared to previous solutions, sometimes by an order of magnitude.
• The compressed indexes only moderately impact query efficiency.
• Experimental validation across diverse datasets and query workloads.

Conclusions:

• The proposed compressed data structures offer a significant advancement in memory reduction for c-dBG indexing.
• These methods enable more scalable and efficient analysis of large genomic datasets.
• The C++17 implementation is publicly available for use.