Sunday, November 22, 2026
Science
No Result
View All Result
  • Login
  • HOME
  • SCIENCE NEWS
  • CONTACT US
  • HOME
  • SCIENCE NEWS
  • CONTACT US
No Result
View All Result
Scienmag
No Result
View All Result
Home Science News Biotechnology

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

November 14, 2026
in Biology, Biotechnology
Juliet Wilcox
By Juliet Wilcox Scienmag Editorial Profile - Human Genetics
Reading Time: 6 mins read
0
Space-Efficient Hash Table Enables Long Genomic K-Mer Counting in Memory

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

65
SHARES
587
VIEWS
Share on FacebookShare on Twitter
ADVERTISEMENT

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

Cite Scienmag News

Juliet Wilcox. (November 14, 2026). Space-Efficient Hash Table Enables Long Genomic K-Mer Counting in Memory. Scienmag. https://scienmag.com/space-efficient-hash-table-enables-long-genomic-k-mer-counting-in-memory/

Juliet Wilcox. "Space-Efficient Hash Table Enables Long Genomic K-Mer Counting in Memory." Scienmag, 14 November 2026, https://scienmag.com/space-efficient-hash-table-enables-long-genomic-k-mer-counting-in-memory/. Accessed 22 November 2026.

Juliet Wilcox. "Space-Efficient Hash Table Enables Long Genomic K-Mer Counting in Memory." Scienmag. November 14, 2026. https://scienmag.com/space-efficient-hash-table-enables-long-genomic-k-mer-counting-in-memory/

Tags: bioinformaticsBloom filtercanonical k-merscomputational biologyde Bruijn graphgenomic dictionariesgenomicshash tableHiFi sequencingk-mer countingKaarmememory efficiencyopen addressingrolling hashsequence analysisstring algorithms
Share26Tweet16
Previous Post

Lipid Gene Lpl Shows Anti-Inflammatory Potential in Kidney Disease

Next Post

Serum Deprivation Clarifies RhoA and ROCK1 Modulation in Triple-Negative Breast Cancer Cells

Related Posts

Engineered Vaccine Platforms Transform Disease Prevention and Targeted Immunotherapy Across Clinical Applications
Biology

Engineered Vaccine Platforms Transform Disease Prevention and Targeted Immunotherapy Across Clinical Applications

November 22, 2026
Single-Cell Sequencing Uncovers RNA Methylation Pathway Driving Kidney Cancer Metastasis
Biology

Single-Cell Sequencing Uncovers RNA Methylation Pathway Driving Kidney Cancer Metastasis

November 22, 2026
Lung Growth Factors Fail to Protect Stem Cells from Hyperoxia
Biology

Lung Growth Factors Fail to Protect Stem Cells from Hyperoxia

November 21, 2026
Bat Fly Found on Silver-Tipped Bat in Central Amazon
Biology

Bat Fly Found on Silver-Tipped Bat in Central Amazon

November 21, 2026
Prairie Voles Reveal Lateral Habenula Activation During Social Fear Transmission
Biology

Prairie Voles Reveal Lateral Habenula Activation During Social Fear Transmission

November 21, 2026
Exercise Modalities Show Differing Dose Associations With Endothelial Function in Adult Trials
Biology

Exercise Modalities Show Differing Dose Associations With Endothelial Function in Adult Trials

November 21, 2026
Next Post
Serum Deprivation Clarifies RhoA and ROCK1 Modulation in Triple-Negative Breast Cancer Cells

Serum Deprivation Clarifies RhoA and ROCK1 Modulation in Triple-Negative Breast Cancer Cells

  • Mothers who receive childcare support from maternal grandparents show more optimized

    Mothers who receive childcare support from maternal grandparents show more parental warmth, finds NTU Singapore study

    27656 shares
    Share 11059 Tweet 6912
  • University of Seville Breaks 120-Year-Old Mystery, Revises a Key Einstein Concept

    1061 shares
    Share 424 Tweet 265
  • Bee body mass, pathogens and local climate influence heat tolerance

    682 shares
    Share 273 Tweet 171
  • Researchers record first-ever images and data of a shark experiencing a boat strike

    546 shares
    Share 218 Tweet 137
  • Groundbreaking Clinical Trial Reveals Lubiprostone Enhances Kidney Function

    531 shares
    Share 212 Tweet 133
Science

Embark on a thrilling journey of discovery with Scienmag.com—your ultimate source for cutting-edge breakthroughs. Immerse yourself in a world where curiosity knows no limits and tomorrow’s possibilities become today’s reality!

RECENT NEWS

  • Illness Perceptions Drive Student Self-Medication in Semi-Rural Nigerian University Study
  • Younger Pet Dogs Prefer Yellow Bowls Over Blue and Grey Options
  • Organ Donor Study Links Fatal Asthma to Widespread Mucosal Immune Dysregulation
  • Case Study Examines How Anthropocene Education Disrupts Conventional University Learning

Categories

  • Agriculture
  • Anthropology
  • Archaeology
  • Athmospheric
  • Biology
  • Biotechnology
  • Blog
  • Bussines
  • Cancer
  • Chemistry
  • Climate
  • Earth Science
  • Editorial Policy
  • Marine
  • Mathematics
  • Medicine
  • Pediatry
  • Policy
  • Psychology & Psychiatry
  • Science Education
  • Science News
  • Social Science
  • Space
  • Technology and Engineering

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 5,151 other subscribers

© 2026 Scienmag - Science Magazine

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
No Result
View All Result
  • HOME
  • SCIENCE NEWS
  • CONTACT US

© 2026 Scienmag - Science Magazine

Discover more from Science

Subscribe now to keep reading and get access to the full archive.

Continue reading