Space-efficient representation of genomic k-mer count tables

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• k-mer counting is fundamental in bioinformatics, generating large count tables (GBs).
• Existing k-mer count tables lack efficient random-access query capabilities.
• Current methods struggle with the skewed distributions typical of whole-genome k-mer counts.

Purpose of the Study:

• To design an efficient representation for k-mer count tables.
• To enable fast random-access queries on these large datasets.
• To improve space efficiency beyond existing methods.

Main Methods:

• Application of Compressed Static Functions (CSFs).
• Development of Bloom-enhanced CSFs (BCSFs) to handle skewed distributions.
• Integration of BCSFs with minimizer-based bucketing for further compression.
• Extension of representations for approximate k-mer counting.

Main Results:

• BCSFs provide compact representations, overcoming limitations of standard CSFs.
• Combined techniques achieve space proportional to empirical zero-order entropy, even breaking the lower bound for large k.
• Experimental validation on whole genomes and unassembled reads demonstrates significant space savings (up to 50% less than empirical entropy for exact counts).

Conclusions:

• The proposed BCSFs offer a highly efficient method for storing and querying k-mer count data.
• These techniques are crucial for handling the massive datasets generated in modern genomics.
• The approach significantly advances the state-of-the-art in bioinformatics data compression and querying.