Minimizer selection

Definition

The minimizer of a k-mer is the canonical form of the m-mer that is smallest according to a chosen ordering among the k-m+1 overlapping m-mers contained in the k-mer, with m<k (Roberts et al. 2004). Canonical form is the same operation defined for a full kmer (see DNA encoding), applied here to an m-mer s instead: s^c = \min_{\mathrm{lex}}\left(s,\operatorname{RC}(s)\right).

In OBIkmer, canonical m-mers are ordered according to a deterministic hash function H applied to their canonical form:

s_1^c <_h s_2^c \quad\Longleftrightarrow\quad H(s_1^c) < H(s_2^c).

Thus, for a k-mer K, let

M(K)=(s_1,\ldots,s_{k-m+1})

be its sequence of overlapping m-mers. The minimizer is

\operatorname{minimizer}(K) = s_j^c, \qquad j=\underset{i}{\operatorname{argmin}}\;H(s_i^c).

In other words, the hash function defines the ordering of canonical m-mers, while the minimizer itself is the canonical form of the m-mer selected by that ordering.

Applying the minimizer to consecutive k-mers partitions a sequence into super-kmers (see Super-kmers).

Hash-based minimizer ordering

obikmer selects minimizers by hash order rather than plain lexicographic order. Ordering m-mers lexicographically on their 2-bit encoding systematically favors AT-rich m-mers (an all-A m-mer always encodes to 0), which causes low-complexity regions to dominate as minimizers and produces unbalanced partitions (Golan & Shur 2025; Kille et al. 2023; Pan & Reinert 2024; Zheng et al. 2020; 2021).

Instead, a well-distributed hash function H is applied to the canonical (lexicographically minimal) form of each m-mer, and the m-mer with the smallest H value wins. Because H is a bijective mixing function with good avalanche properties (Steele et al. 2014), its output behaves approximately as a composition-independent pseudorandom ordering of distinct m-mers. Under the usual random-hash assumption, each distinct m-mer in a window has approximately the same probability of being the minimum, independently of nucleotide composition.

The canonical form used as input to H is still the lexicographic minimum of forward/reverse-complement — hashing is applied on top of it, not used to redefine it. Defining canonicity by hash value instead would bias the distribution of hash values themselves toward small values (the minimum of two independent hashes is not uniformly distributed), reintroducing a bias one layer down.

Hash function

The hash function (H) applies Stafford's 64-bit mixing function, variant 13 (Stafford 2011), to the m-mer encoding XORed with a seed \sigma:

H(x):
    x ← x  ⊕  σ
    x ← x  ⊕  (x >> 30)
    x ← x  ×  0xbf58476d1ce4e5b9
    x ← x  ⊕  (x >> 27)
    x ← x  ×  0x94d049bb133111eb
    return x ⊕ (x >> 31)

The hash uses a fixed non-zero seed

\sigma=\texttt{0x9e3779b97f4a7c15}.

The choice of \sigma is not arbitrary. Low-complexity m-mers (homopolymers and short tandem repeats) are disproportionately abundant in real genomes. If one of them happened to be the global argmin of H, it could therefore occur as the minimizer in far more windows than expected from the composition-uniform behavior described above. This is not a bias of the mixing function itself, but a consequence of the repeated occurrence of the same input in real sequence data.

In particular, with \sigma=0, the all-A m-mer is encoded as 0, and

\operatorname{Mix13}(0)=0,

This makes it the global argmin of the hash function. The non-zero seed eliminates the particular pathological correspondence between the all-A m-mer and the zero output of the mixer.

Exhaustive enumeration of all 4^m m-mers confirms that, with \sigma=\texttt{0x9e3779b97f4a7c15}, the global argmin is neither a homopolymer nor a periodic repeat for any tested (m):

`m`	argmin (canonical)	decoded sequence	minimal period
3	16	`CAA`	3
5	78	`ACATG`	5
7	5512	`CCCGAGA`	7
9	108760	`CGGGATCGA`	9
11	179014	`AAGGTGTCACG`	11
13	33759044	`GAAATACTTCACA`	13
15	29869313	`AACTACTTACCAAAC`	15

When the minimal period of the sequence is m, as observed in the table above, the sequence is primitive: it cannot be represented as repetitions of a shorter sequence.

See Partitioning and indexing architecture for how this hash routes a super-kmer to a partition.

Bibliography

Golan, S. & Shur, A.M. (2025). Expected density of random minimizers. In: Lecture Notes in Computer Science, Lecture Notes in Computer Science. Springer Nature Switzerland, Cham, pp. 347–360.

Kille, B., Garrison, E., Treangen, T.J. & Phillippy, A.M. (2023). Minmers are a generalization of minimizers that enable unbiased local Jaccard estimation. Bioinformatics (Oxford, England), 39.

Pan, C. & Reinert, K. (2024). A simple refined DNA minimizer operator enables 2-fold faster computation. Bioinformatics (Oxford, England), 40.

Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M. & Yorke, J.A. (2004). Reducing storage requirements for biological sequence comparison. Bioinformatics (Oxford, England), 20, 3363–3369.

Stafford, D. (2011). Better Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer. Available at: https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html. Last accessed 12 September 2026.

Steele, G.L., Jr, Lea, D. & Flood, C.H. (2014). Fast splittable pseudorandom number generators. In: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications. ACM, New York, NY, USA.

Zheng, H., Kingsford, C. & Marçais, G. (2020). Improved design and analysis of practical minimizers. Bioinformatics (Oxford, England), 36, i119–i127.

Zheng, H., Kingsford, C. & Marçais, G. (2021). Sequence-specific minimizers via polar sets. Bioinformatics (Oxford, England), 37, i187–i195.

Minimizer selection

Definition

Hash-based minimizer ordering

Hash function

Bibliography

Wiki sidebar

Theory

Kmer indexing

Phylogeny

Kmer-based

SNP-based

Usage

Formats