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 @Roberts2004-rz.

For an m-mer s, its canonical form is defined as

s^c = \min_{\mathrm{lex}}\left(s,\operatorname{RC}(s)\right),

where \operatorname{RC}(s) denotes the reverse complement of s.

The ordering used to select the minimizer is independent of this canonicalization. In OBIkmer, canonical m-mers are ordered according to a deterministic hash function h:

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 set 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.

The minimizer partitions a sequence into super-kmers: maximal runs of overlapping kmers that share the same minimizer (see Kmers and 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 bijection with good avalanche properties, every distinct m-mer in a window has an equal chance of holding the minimum hash value, independent of its 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

s is a fixed non-zero seed:

s = \lfloor 2^{64}/\varphi \rfloor = \texttt{0x9e3779b97f4a7c15}

The hash function is a 64-bit mixing function (splitmix64-style finalizer) applied to the m-mer XORed with s:

H(x) = \text{mix64}(x \oplus s)

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

The choice of s is not arbitrary. Low-complexity m-mers (homopolymers, short tandem repeats) are disproportionately abundant in real genomes; if one of them happened to be the perpetual argmin of H — as the all-A m-mer is when s = 0, since \text{mix64}(0) = 0 is a fixed point — it would win far more windows than the composition-uniform behavior established above predicts, not because H favors it, but because that pathological input keeps recurring in real sequence data. Exhaustive checks confirm that, with this seed, the argmin is never a homopolymer or any periodic repeat, for every 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

If the minimum period length is found to be m as observed in the above table, then the sequence is aperiodic, as no shorter period can be identified.

Partition routing

A super-kmer's partition is the low p bits of its minimizer's hash:

\text{partition} = H(\text{minimizer}) \bmod 2^p

See Partitioning and indexing architecture for more details.

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.

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

Partition routing

Bibliography

Wiki sidebar

Theory

Kmer indexing

Phylogeny

Kmer-based

SNP-based

Usage

Formats