Space-Efficient Hash Table Enables Long Genomic K-Mer Counting in Memory

Computer scientists have introduced a space-efficient hash table designed to count large genomic sequence markers directly in computer memory without exhausting physical random-access memory. Developed by Diego Díaz-Domínguez, Miika Leinonen, and Leena Salmela, the framework, named Kaarme, addresses a critical memory bottleneck that emerges when analyzing modern long and highly accurate sequencing reads. By storing only the terminal nucleotide of overlapping sequence fragments alongside internal pointers to previously encountered fragments, the system avoids recording complete nucleotide sequences across every table entry, substantially reducing the physical RAM footprint required for large sequence dictionaries.

Strings of fixed length k, known throughout computational genomics as k-mers, form the algorithmic foundation for diverse analytical tasks, including sequence error correction, genome assembly, genetic variant calling, metagenomic classification, and repeat analysis. In typical workflows, the initial computational step consists of k-mer counting, which calculates the exact frequency of every k-length substring occurring across a collection of sequencing reads. While earlier sequencing technologies produced short reads that relied on k-mer lengths under one hundred base pairs, modern sequencing platforms like Pacific Biosciences HiFi sequencing generate long reads with very low error rates. Leveraging these longer read lengths requires assembling genomes with k-mers extending up to several thousand base pairs to reduce branching in assembly graphs.

Conventional k-mer counting software often relies on hash tables optimized primarily for small sequence lengths. In standard systems, a DNA k-mer can be encoded using two bits per symbol, enabling entire sequences to fit into single machine words when k does not exceed thirty-two base pairs. However, when k becomes substantial, explicit key storage requires O(N k / w) machine words, where N represents the number of distinct k-mers and w is the machine word size. For large k values across extensive read sets, this explicit representation rapidly exhausts system memory. Existing genome assemblers have historically addressed this limitation by avoiding comprehensive k-mer dictionaries altogether, relying on sparse graphs, minimizer winnowing, or intermediate disk storage.

The Kaarme architecture circumvents this memory scaling bottleneck by exploiting the biological reality that consecutive k-mers extracted from sequencing reads overlap across k minus one nucleotide positions. In Kaarme, each occupied bucket in the hash table records a relative representation comprising the frequency of the sequence, a pointer to another hash table bucket that encodes the preceding k minus one prefix symbols, and the single rightmost nucleotide symbol of the sequence. For initial sequence fragments that lack an existing predecessor bucket during the linear scan of a read, the algorithm temporarily stores complete sequences within a secondary dynamic buffer. As soon as a valid reference bucket appears later during processing, the entry is transitioned into relative form and the buffer space is flagged for reuse.

The research team extended this framework to accommodate canonical k-mers, which are defined as the lexicographically or hash-determined smaller representation between a sequence and its reverse complement. Collapsing reverse-complement pairs into single canonical entries halves the required hash table capacity in practice, though it removes the strict left-to-right spelling invariant because consecutive read sequences do not necessarily share the same canonical orientation. To resolve this, the canonical hash table entry incorporates six specific fields: frequency, reference bucket pointer, terminal symbol, initial symbol, and two orientation bits that define the relative text overlap. Reconstructing sequences from this canonical structure involves an inward reconstruction algorithm that slides an analytical window back and forth across reference chains until all nucleotide positions are recovered.

The theoretical bounds of the Kaarme framework demonstrate that non-canonical dictionary construction operates in O(N + u k / w) words of space, where u denotes the total number of reads in the sequencing dataset. The secondary buffer requires at most u k-mers to store initial prefixes, bounding buffer consumption to O(u k / w) words. While theoretical worst-case decoding time for canonical k-mers exhibits an exponential upper bound of O(sigma to the power of k) over a DNA alphabet of size sigma, the authors proved that reference chains remain strictly acyclic. In practice, the cancellation of visited trie paths keeps operational retrieval times close to linear, preventing the theoretical worst-case delays from materializing in realistic genomic datasets.

To evaluate performance, the authors implemented Kaarme in C++ using lock-free atomic compare-and-swap instructions and a two-stage Bloom filter mechanism that filters out k-mers occurring only once. They benchmarked Kaarme against an in-house baseline tool named Plain, which stores explicit canonical sequences using two bits per symbol, as well as established external tools including Jellyfish, CHTKC, DSK, and Gerbil. The experimental evaluations utilized three PacBio HiFi sequencing datasets: an Escherichia coli read set at 100x coverage, the same E. coli set at 280x coverage, and a downsampled Drosophila melanogaster read set at 20x coverage. Testing spanned k values of 51, 101, 151, 201, 251, and 301 on a standard computer equipped with sixteen gigabytes of RAM and an eight-thread processor.

Empirical results confirmed that canonical Kaarme dramatically reduced memory consumption compared to explicit hash storage. On the 100x coverage E. coli dataset at k equal to 51, Kaarme required 362 megabytes of RAM compared to 529 megabytes for Plain, representing approximately thirty percent memory savings. On the D. melanogaster dataset at k equal to 51, Kaarme reduced memory usage by approximately forty percent, and successfully completed counting up to k equal to 301, whereas Plain exhausted available RAM once k reached 151. Across all datasets, Kaarme maintained a constant memory footprint per distinct k-mer in the hash table, while Plain exhibited linear memory growth as k increased. Across peak memory measurements, the secondary dynamic buffer accounted for an average of less than eleven percent of Kaarme’s total space usage.

When compared to specialized k-mer counters, Kaarme demonstrated substantial memory savings in scenarios where competitor tools operated purely in RAM without relying on external disk space. The software used up to five times less space than standard explicit hash tables while running less than 1.5 times slower. External disk-assisted tools such as CHTKC and DSK maintained their operations within the 15-gigabyte memory limit by heavily utilizing disk storage for excess k-mers, whereas Kaarme operated as a dedicated in-memory structure. Kaarme proved slower overall than disk-partitioned competitors, with runtimes dominated by the counting phase as sequence lengths increased, but maintained the smallest memory footprint among in-memory counters across high values of k.

The authors noted specific constraints regarding how Kaarme could integrate into broader bioinformatics pipelines. While incorporating Kaarme into existing tools like DSK or CHTKC could theoretically reduce their internal hash table overhead, aggressive read partitioning might fragment input sequences and sever overlap continuity, which would expand the secondary dynamic buffer. Nevertheless, by demonstrating that overlapping sequence pointers can replace explicit string keys with minimal runtime penalties, the Kaarme framework establishes a practical, memory-frugal foundation for scalable long-read genomic analysis.

Beyond constructing the compact in-memory index, the framework provides an extraction routine called DumpDict to output sequence keys and their frequencies into uncompressed text for all k-mers exceeding an occurrence threshold tau. In the non-canonical dictionary, extraction initializes a k-symbol buffer from right to left using the terminal characters stored along reference chains. Although reconstructing the initial k-mer in an unbroken chain requires traversing k successive buckets, every subsequent sequence along that chain is resolved by shifting the buffer and reading a single newly visited bucket. To maximize retrieval efficiency, the algorithm scans the hash table once to flag all referenced buckets, subsequently launching extraction exclusively from unreferenced buckets to ensure maximum chain lengths. In canonical dictionaries, DumpDict executes the canspell routine to reconstruct the leading sequence of a chain, after which each succeeding canonical k-mer requires inspecting only one additional bucket.

The researchers also established an algorithmic enhancement to accelerate dictionary construction beyond the baseline expected runtime of O(nk). During table probing, exhaustive string comparison is only required when an occupied bucket represents a de Bruijn graph node reached via an alternative incoming edge. To prevent redundant multi-symbol decodings during collisions, the authors introduced an auxiliary hash table alongside a displacement field that records the probing step distance d within each entry. This auxiliary table stores up to three alternative incoming bucket references for each distinct sequence. Incorporating these pointers expands overall memory requirements to O(|E|+u*k/w) computer words, where |E| denotes total de Bruijn graph edges, while reducing expected construction time to O(n+(|E|-|V|)k+q), where |V| represents graph vertices and q accounts for expected hash collision comparisons.

Detailed runtime profiling demonstrated that Kaarme dedicates most of its operational time to frequency counting, with smaller shares allocated to Bloom filtering and dictionary dumping. On the 100x coverage E. coli dataset at k equal to 51, Kaarme achieved a total runtime of 151 seconds compared to 122 seconds for Plain. Peak memory overhead was mitigated by deleting the initial Bloom filter before initiating frequency counting, effectively cutting filter memory consumption in half. Decompression benchmarks on the E. coli read set verified that practical pointer traversals remain close to linear, preventing the theoretical worst-case exponential delays from materializing in practice. The software title itself highlights this navigational architecture: käärme is the Finnish word for snake, reflecting how reference pointer chains weave continuously through the compact hash table entries.

Subject of Research: Space-efficient k-mer counting hash tables for long-read genomic analysis

Article Title: Space-efficient computation of k-mer dictionaries for large values of k

Article References: Díaz-Domínguez, D., Leinonen, M., & Salmela, L. (2024). Space-efficient computation of k-mer dictionaries for large values of k. Algorithms for Molecular Biology, 19(1), Article 14. https://doi.org/10.1186/s13015-024-00259-1

Image Credits: AI Generated

DOI: 10.1186/s13015-024-00259-1

Keywords: k-mer counting, hash table, Kaarme, computational biology, genomics, bioinformatics, de Bruijn graph, HiFi sequencing, Bloom filter, canonical k-mers, memory efficiency, open addressing, string algorithms, rolling hash, genomic dictionaries, sequence analysis