kmcEx

kmcEx encodes counted k-mers and their frequencies in a memory-efficient, retrieval-optimized representation to enable large-scale k-mer-based genomic analyses such as error correction, repeat detection, multiple sequence alignment, and genome assembly.

Key Features:

• Memory-efficient encoding: Achieves an average memory-saving ratio of approximately 13.81× compared to raw input data when applied to datasets containing 31-mers.
• Coupled-bit array data structure: Implements a Bloom filter-like structure composed of coupled-bit arrays, with one array representing the k-mer and another encoding frequency information.
• Hashing scheme: Employs seven hash functions to populate the coupled-bit arrays and control collisions.
• Constant-time retrieval: Maintains a controlled retrieval time complexity that remains effectively constant.
• Reduced false-positive rate: Lowers the Bloom filter false-positive rate by approximately two orders of magnitude.
• Experimental validation: Performance and robustness were evaluated on five real datasets.

Scientific Applications:

• Error correction: Provides memory-efficient access to k-mer counts for sequencing error correction workflows.
• Repeat detection: Enables scalable detection of repeats using counted k-mer frequencies.
• Multiple sequence alignment: Supports k-mer-based inputs and frequency queries for alignment preprocessing and heuristics.
• Genome assembly: Supplies compact k-mer and frequency encodings suitable for assembly algorithms that rely on k-mer statistics.

Methodology:

Uses a Bloom filter-like data structure of coupled-bit arrays (one for k-mer representation and one for frequency encoding) with seven hash functions to encode k-mers and frequencies, yielding effectively constant retrieval time and a substantially reduced false-positive rate.