Researchers have introduced a new sampling algorithm designed to significantly reduce the space required for indexing large biological text collections, such as DNA sequences. The method, named the open-closed mod-minimizer, improves upon existing techniques by selecting a sparser subset of k-mers, which are short substrings of a fixed length k, from a longer string. This reduction in density leads to smaller indexes and faster computational methods, a critical advantage in bioinformatics where data volumes are immense. The work was published in Algorithms for Molecular Biology in March 2025 by Ragnar Groot Koerkamp, Daniel Liu, and Giulio Ermanno Pibiri.
The study addresses a fundamental challenge in sequence comparison and indexing: how to efficiently sample k-mers from a window of w consecutive k-mers. The standard approach, known as the random minimizer, selects the smallest k-mer in the window according to a random order. While simple and versatile, this method has a density of 2/(w+1), meaning it selects a relatively large fraction of k-mers. Lower density is desirable because it results in smaller data structures and faster queries, but the random minimizer is not optimal.
Previous work by Groot Koerkamp and Pibiri introduced the mod-minimizer, which achieves a lower density approaching 1/w when k is large compared to w. However, this method performs poorly when k is small, a regime common in applications like building de Bruijn graphs or sparse data structures for l-mers. In these cases, k is typically fixed at a small value, such as 20, while w increases, making k less than w. The authors sought a method that performs well in this small-k regime and can be extended to large k.
The core innovation is the open-closed minimizer, which extends the miniception method by Zheng et al. The miniception samples the smallest closed syncmer in the window. A closed syncmer is a k-mer whose smallest substring of length s appears at either the beginning or the end. The new method also considers open syncmers, where the smallest substring of length s is in the middle position. The algorithm prefers the smallest open syncmer, then the smallest closed syncmer, and finally the smallest k-mer if neither is present. This preference for open syncmers is based on their distance guarantee, which ensures that consecutive open syncmers are at least a certain number of positions apart, leading to lower density.
To extend this improvement to the large-k regime, the authors generalized the mod-minimizer framework. The original mod-minimizer uses the smallest t-mer as an anchor to determine the position of the sampled k-mer. The extended version allows any sampling scheme to be used as the anchor. By using the open-closed minimizer as the anchor, the authors created the open-closed mod-minimizer. This hybrid approach combines the low density of the open-closed minimizer for small k with the asymptotic optimality of the mod-minimizer for large k, achieving lower density than the standard mod-minimizer for all values of k.
The authors provided a rigorous analysis of the density of the open-closed minimizer. They developed a polynomial-time algorithm to compute the exact density by analyzing the probability distribution of configurations of open and closed syncmers in a context of two consecutive windows. This analysis revealed that the open-closed minimizer significantly improves the density of the miniception, making it comparable to the double decycling method of Pellow et al., which is known for its low density but higher computational complexity. The open-closed minimizer is computationally simpler, operating in amortized O(1) time per k-mer, whereas the double decycling method requires O(k) time.
Experimental results demonstrated the practical benefits of the new algorithm. The authors tested the methods by building SSHash indexes, a type of k-mer dictionary based on minimizers, across several datasets including the human genome, a pangenome of Salmonella Enterica, and the genome of the axolotl. For parameters (w,k) = (11,21), the open-closed minimizer reduced the space usage of SSHash indexes by at least 11% and up to 14.5% compared to the random minimizer. The open-closed mod-minimizer further improved this, reducing space usage by 18% on the whole human genome, from 8.70 bits per k-mer to 7.13 bits per k-mer.
The study also highlighted the limitations of existing methods for large k. The miniception and other syncmer-based methods suffer from a sharp increase in density when k grows, as fewer k-mers qualify as syncmers. The decycling set-based methods also perform poorly for large k because the universal hitting sets become too sparse. The extended mod-minimizer framework overcomes this by using the open-closed minimizer as an anchor, which maintains low density even when k is large. This makes the open-closed mod-minimizer a practical and versatile tool for a wide range of bioinformatics applications.
The authors noted that while the open-closed mod-minimizer achieves lower density than the random mod-minimizer for many practical values of k, a formal analysis of its density is more complex. They lack a closed-form formula for the density of the extended mod-minimizer when using the open-closed minimizer as an anchor, which is a direction for future work. Nevertheless, the empirical results strongly support the effectiveness of the new method. The software implementations in C++ and Rust are publicly available on GitHub, allowing other researchers to test and apply the algorithm.
This work contributes to the ongoing effort to optimize sequence indexing methods, which are foundational to many bioinformatics tools. By providing a method that is both theoretically sound and practically efficient, the authors have offered a valuable resource for the community. The ability to reduce index size by up to 18% without modifying the underlying data structure has immediate implications for large-scale genomic analyses, where memory and storage constraints are significant. The open-closed mod-minimizer represents a step forward in the design of sampling algorithms, balancing computational simplicity with optimal performance across different parameter regimes.
The theoretical framework for these sampling algorithms relies on the concept of density, defined as the expected fraction of selected k-mers in a string. For a string of length n, the density is calculated as the ratio of the number of sampled k-mers to the total number of k-mers, n-k+1. In practice, researchers approximate this value using finite but sufficiently long random strings. The performance of a sampling scheme is often evaluated against a lower bound derived by Kille et al., which is expressed as the maximum of two terms involving the ceiling of (w+k)/w divided by w+k. This lower bound represents the theoretical minimum density achievable by any forward scheme. The open-closed minimizer and its extended variants are designed to approach this bound more closely than previous methods, particularly in the regime where k is small relative to w. The analysis of these schemes involves computing the probability that two consecutive windows sample different k-mers, a metric that directly correlates with the overall density of the index.
A key technical contribution of the study is the development of a polynomial-time algorithm to compute the exact density of the open-closed minimizer. Traditional methods for calculating the density of forward schemes require enumerating all possible substrings in a De Bruijn sequence of order w+k, a process that scales exponentially and becomes computationally infeasible for even moderate values of w and k. The new recursive method avoids this exponential cost by analyzing a context of w+k characters, which contains two consecutive windows. The algorithm tracks the number of open and closed syncmers, as well as the number of “charged” k-mers at the edges of the context. By using dynamic programming, the algorithm can compute the probability distribution of these configurations in O(x^7) time, where x is the number of s-mers in the context. A more efficient implementation that counts open and closed k-mers independently runs in O(x^5). This computational approach allows for precise density calculations without relying on empirical approximations, providing a rigorous foundation for comparing the performance of different sampling schemes.
The experimental evaluation of the proposed methods was conducted using C++ implementations compiled with gcc 11.1.0 on Ubuntu 18.04.6. The authors utilized the 128-bit pseudorandom hash function CityHash to hash k-mers, ensuring that the order of k-mers was effectively random. The experiments focused on measuring the space usage of SSHash indexes, a data structure that relies on minimizers for sparse indexing. The datasets included the human genome (GRCh38), chromosome 13 of the human genome, a pangenome of 100 Salmonella Enterica genomes, and the genome of the axolotl, which is notable for its large size with more than 18 billion distinct k-mers for k=31. The choice of these datasets reflects the diverse range of genomic applications where efficient k-mer sampling is critical. The results showed that the open-closed minimizer consistently reduced the space usage of SSHash indexes compared to the random minimizer, with improvements ranging from 11% to 14.5% depending on the dataset.
The study also examined the behavior of the sampling methods as k increases relative to w. The authors observed that syncmer-based methods, including the miniception and the open-closed minimizer, experience a degradation in performance when k becomes significantly larger than w. This occurs because fewer k-mers qualify as open or closed syncmers as k grows, leading to a higher frequency of windows that fall back to the random minimizer. The decycling set-based methods face a similar issue, as the universal hitting sets they rely on become too sparse to ensure that most windows contain a sampled k-mer. The extended mod-minimizer framework addresses this limitation by using the open-closed minimizer as an anchor, which allows the method to maintain low density even when k is large. This hybrid approach leverages the strengths of both the small-k and large-k regimes, providing a robust solution for a wide range of parameter values. The authors noted that while the open-closed mod-minimizer achieves lower density than the random mod-minimizer for many practical values of k, a formal closed-form formula for its density remains an area for future research.
Subject of Research: Development of the open-closed mod-minimizer algorithm for efficient k-mer sampling in bioinformatics
Article Title: The open-closed mod-minimizer algorithm
Article References: Groot Koerkamp, R., Liu, D., & Pibiri, G. E. (2025). The open-closed mod-minimizer algorithm. Algorithms for Molecular Biology, 20(1), Article 4. https://doi.org/10.1186/s13015-025-00270-0
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00270-0
Keywords: bioinformatics, k-mer sampling, genomic indexing, open-closed mod-minimizer, sequence comparison, data compression, Algorithms for Molecular Biology, minimizer scheme, syncmers, SSHash, open-closed, mod-minimizer
News Source: Juliet Wilcox. (November 13, 2026). New Algorithm Reduces Genomic Index Size by 18 Percent. Scienmag.
