This posts discusses some variants of minimizers, inspired by the previous post on bidirectional anchors.

The final goal is to introduce variations of minimizers and evaluate their density. It will turn out that ‘reduced minimizers’ have density very close to some lower bound.

Minimizer schemes take an \(\ell = k+w-1\) mer, and select a substring of length \(k\) in a deterministic way, in such a way that consecutive $ℓ$-mers are likely to share their chosen $k$-mer.

Minimizers can be used for various purposes, such as:

- Compressing sequences, such as in minimizer-space De Bruijn graphs (Ekim, Berger, and Chikhi 2021).
*Locality preserving hashing*of kmers (Pibiri 2022; Pibiri, Shibuya, and Limasset 2023).- Here a large \(k \geq \log_\sigma N\) is used so that minimizers are unique keys.
- The objective is to have as few minimizers as possible in any sequence, to reduce the number of cache-misses due to non-locality.

- Similarity estimation (Li 2016).
- Here the goal is to cluster similar reads. Ideally reads with a few small mutations have the same minimizer.

Locality preserving hashing and similarity estimation both cluster kmers on similarity, but there are some differences:

- In LPH, we want
*consecutive*kmers to share a minimizer. I.e. we want to partition the De Bruijn graph into long paths. - In similarity estimation, we want
*similar*kmers to share a minimizer, where*similar*explicitly includes small mutations. I.e. we want to partition the De Bruijn graph into ‘blobs’ covering many variants.

A critical property is the *density*: the proportion of positions that is chosen
as the start of a minimizer. Fewer chosen positions means better compression and better
locality of hashing.

I will first discuss some types of minimizers and introduce some new variants, and then experimentally evaluate their density on random strings.

## Background

Related but out of scope topics are:

- universal minimizers: not really a local sampling scheme;
- spaced minimizers/syncmers/strobemers: used for similarity search methods, but not used for locality sensitive hashing.

### Minimizers

**Minimizers:** Minimizers were introduced independently
by Roberts et al. (2004) and Schleimer, Wilkerson, and Aiken (2003): Given a
$(k+w-1)$-mer, consider the \(w\) contained $k$-mers. The (rightmost) $k$-mer with minimal
hash (for some given hash function \(h\)) is the minimizer.

An example:

```
l=11, k=5, w=l-k+1=7
lmer:
***********
candidate minimizer kmers:
*****
|*****
||*****
|||*****
||||*****
|||||*****
||||||*****
|||||||
8136192 // hashes in [0,9]
| // rightmost minimal hash
***** // minimizer
```

**Density:** By definition, minimizers sample at least one in every \(w\) positions, so
trivially have a *density* of at least \(1/w\).

Schleimer, Wilkerson, and Aiken (2003) prove that on random strings, any minimizer scheme has a density at least \[\frac{1.5+\frac{1}{2w}}{w+1}\geq \frac{1.5}{w+1}.\]

- Marçais, DeBlasio, and Kingsford (2018) contradict that theorem by
constructing a universal minimizer with lower density, and remark that the
previous result only applies to ‘randomized local schemes’.
- Note: I am quite unsure what is the current status of this \(1.5/(w+1)\) lower bound.

- Instead they prove that density is at least \[\frac{1.5 + \frac{1}{2w} + \max(0, \lfloor \frac{k-w}{w}\rfloor)}{w+k}.\]

- Marçais, DeBlasio, and Kingsford (2018) contradict that theorem by
constructing a universal minimizer with lower density, and remark that the
previous result only applies to ‘randomized local schemes’.
Random minimizers have a density of \(2/(w+1) + o(1/w)\) when \(k > (3+\epsilon) \log_\sigma (w+1)\) (Zheng, Kingsford, and Marçais 2020b; Marçais et al. 2017).

This is only \(33\%\) above the lower bound!

**Is \((3+\epsilon)\) tight?**

#### Robust minimizers

To reduce the density, Schleimer, Wilkerson, and Aiken (2003) suggest the following: when the minimizer of the preceding k-mer is still a minimizer, reuse it, even when it is not rightmost.

Continuing the example:

```
l=11, k=5, w=7
************ // n=12 text
***** ***** // first & last minimizer
81361921 // n-k+1 hashes of 5-mers
-1--1-- // minimal hashes in first lmer
***** // minimizer is rightmost
1--1--1 // minimal hashes in second lmer
***** // reuse minimizer, instead of starting at rightmost 1.
```

When the same kmer occurs twice in an $ℓ$-mer, only one of them will be selected in a way dependent on the context. For most applications, this non-determinism is not a problem.

Still there is a drawback: When two distinct kmers have the same hash, only one of them is selected. Although unlikely, this is not good for downstream applications. To prevent this, minimizers \(x\) could be ordered by \((h(x), x)\) instead of just \(h(x)\).

#### PASHA

PASHA (Ekim, Berger, and Orenstein 2020) is another minimizer selection algorithm based on a universal hitting set. It works as follows:

- Start with a complete De Bruijn graph of order \(k\), i.e., containing all \(4^k\) kmers.
- Remove from this a minimal set of $k$-mers \(U_1\) that make the graph acyclic.
- Then remove additional $k$-mers to remove all paths of length \(\geq \ell\).
- This is done using the DOCKS heuristic (Orenstein et al. 2017), which greedily removes the vertex containing the most (length \(\ell\)) paths.

PASHAs main contribution is a considerable speedup over DOCKS. It still remains slow and has to process the full \(4^k\) graph, limiting it to \(k\leq 16\), but has the lower density.

#### Miniception

Miniception (Zheng, Kingsford, and Marçais 2020b) is a specific minimizer selection algorithm. It works using an additional parameter \(k_0\) around \(3\cdot \log_\sigma(k)\). It additionally requires \(k_0 \geq k-w\), although I do not think this is explicitly mentioned in the paper.

For a window \(T\) of length \(\ell = k+w-1\) characters, Miniception selects a minimizer as follows:

Set \(w_0 = k-k_0\) and find all \((k_0, w_0)\) minimizers under some hash \(h_0\).

Out of the \(w\) $k$-mers in \(T\), keep only those:

- whose prefix $k_0$-mer is a \((k_0, w_0)\) minimizer of \(T\), or
- whose suffix $k_0$-mer is a \((k_0, w_0)\) minimizer of \(T\).

This is equivalent to saying that the minimal $k_0$-mer in the $k$-mer is its prefix or suffix.

From the filtered $k$-mers, select the one with minimal hash \(h\).

In the limit, it achieves density down to \(1.67/w\) for \(w\sim k\).

Sadly the preprint (Zheng, Kingsford, and Marçais 2020a) has a typo in Figure 6, making the results hard to interpret.

### Bd-anchors

**Bidirectional anchors** (bd-anchors) are a variant on minimizers that take the minimal
lexicographic *rotation* instead of the minimal k-mer substring (Loukides, Pissis, and Sweering 2023; Ayad, Loukides, and Pissis 2023).
I wrote above them before in this post.

**Reduced bd-anchors** restrict this rotation to not start in the last
\(r=4\log_\sigma(\ell)\) positions.

**Density:** Reduced bd-anchors have a density of \(2/(\ell+1-r)\) for large
alphabet, and somewhat larger for small \(\sigma\).

Bd-anchors have a slightly different purpose than minimizers, in that they are keyed by their position in the text, rather than by the corresponding string itself. Thus, a suffix array is built on suffixes and reverse-prefixes starting/ending there.

For random strings, reduced bd-anchors are a dense subset of the \(k=r+1\) minimizers.

Given the bd-anchors, two suffix arrays are built. One of suffixes starting at anchors, and one on reverse prefixes ending at anchors.

**Note:** bd-anchors are not a so-called *forward* scheme. That is, it is possible
for the window to shift right, but the selected position to jump backwards.
Example here.

**Optimization:**
When querying an $ℓ$-mer, in practice only the longer of the
prefix and suffix is actually looked up in the corresponding suffix array. Thus,
we don’t need to two suffix arrays over *all* bd-anchors:

- The forward SA over suffixes only needs to contains bd-anchors occurring in the left half of some $ℓ$-mer.
- The reverse SA over suffixes only needs to contains bd-anchors occurring in the right half of some $ℓ$-mer.

This makes things slightly sparser.

## New ideas

### Biminimizers

Here is an idea I had and that was also tried by Giulio for SSHash (Pibiri 2022). Surely there is some literature on this but I’m at a loss to find it. Please let me know.

In short: use robust minimizers, but always use at least two candidate positions.
For this, we can use two hash functions and take the minimizer for \(h_1\) and
\(h_2\). Or we can consider the *bottom two* minimizers with lowest score for \(h\).
(The latter performs slightly better in evals so is what I’ll go with.)

This also generalizes to *t-minimizers*, where we robustly choose the rightmost
of \(t\) candidates generated either by \(t\) hash functions or the bottom-\(t\) of a
single hash function.

A new example:

```
8336192 // hashes
| | // bottom two minimal hashes
***** // biminimizer
```

Like robust minimizers, this has one big drawback: **Minimizers are not
deterministic.** Downstream applications will likely have to make two queries to
locate the minimizer. But this may be worth the tradeoff compared to the space savings.

### Reduced minimizers

*(Naming suggestions welcome.)*

Bidirectional anchors have a benefit over minimizers since they always use \(r=O(\log_\sigma (\ell))\) instead of possibly much larger \(k\). This means their average density \(2/(\ell+1-r)\) can be lower than \(2/(w+1) = 2/(\ell-k+2)\). Similarly, Miniception uses a separate \(k_0\) of order \(3 \log_\sigma(k)\) to achieve

Why do we use large \(k\), when small \(k=\Omega(\log \ell)\) is sufficient and preferable for lower density? The reason is that for locality preserving hashing we would like (nearly) unique keys of length \(\log_\sigma(N)\).

It seems that two conceptually distinct parameters are merged:

- The length \(k_0=r+1\) of the minimizer, which we would like to be small.
- The length \(k\) of the key we want to extract, which we would like to be larger.

Inspired by previous methods, here is a new sampling scheme.

First, find a minimizer of length \(k_0=1+3 \log_\sigma w\), say at position \(0\leq i < w = \ell - k_0 + 1\).

Extract a key of length \(k\leq (\ell+k_0)/2\):

- If \(i \leq (w-1)/2\),
*extend right*, i.e. extract \(Q_{i..i+k}\). This is in bounds because: \[i+k \leq (w-1)/2 + (\ell+k_0)/2 = (\ell-k_0)/2 + (\ell +k_0)/2 = \ell.\] - If \(i \geq (w-1)/2\),
*extend left*, i.e. extract \(Q_{i+k_0-k..i+k_0}\). This is in bounds because: \[i+k_0-k \geq (w-1)/2 - (\ell+k_0)/2 = (\ell-k_0)/2 - (\ell +k_0)/2 = 0.\]

TODO: Split into three cases for larger \(k\).

- If \(i \leq (w-1)/2\),

Here is an example for \(\ell \geq 2k-3-1\). Stars indicate the candidate $k_0$-minimizers, and the dashes indicate the extension to a $k$-mer key.

```
l=10, k=7, r=3
lmer:
**********
minimizers (*), and extracted keys (*=)
***----
***----
***----
***----
----***
----***
----***
----***
```

And here is a 3-way split example that additionally includes extension around the middle.

```
l=10, k=8, r=3
lmer:
***********
minimizers (*), and keys (*=)
***=====
***=====
***=====
===***==
===***==
===***==
=====***
=====***
```

It seems that this scheme performs well when \(k\) is around \(\ell/2\), say \(\ell/3 < k < 2\ell/3\).

**TODO:** There are cases where we can be flexible in the exact point where we switch
from extending left to extending right. Should we switch around the middle? Or
better make one of the runs as long as possible?

## Experiments

Here are some quick results.

- Code is at https://github.com/RagnarGrootKoerkamp/minimizers.
- PASHA is excluded – even though it’s very good, it’s too much effort to download $k$mers to quickly benchmark it.

Note:

- bd-anchors depend only on \(\ell = w+k-1\), and hence density decreases in \(k\).
- Biminimizers are best for \(k\leq w\) (but have drawbacks).
- Miniception is always better than vanilla minimizers.
- Reduced minimizers are terrible for \(k\leq w\), but best for \(k>1.25 w\).
- They get very close to \((1.5+2/w)/(w+1)\).
- Why are they bad?
- Can we optimize them more? By using more ideas from miniception?

- Can we optimize miniception by introducing a third layer of minimizers??
- Or what if we sort filtered kmers by their contained k0-mer before comparing their own hash?

- For larger alphabet \(\sigma = 256\) (not shown), results are mostly the same but bd-anchors have slightly lower density.

## Conclusion

For \(k \geq 1.25 w\), reduced minimizers achieve density very close to the lower bound of \((1.5+1/2w)/(w+1)\) that holds for random minimizers.

**TODO**

- Make an explicit experiment for \(k=21\), \(w=10\), \(\ell=31\).
- Compare to PASHA?
- Analyzer robust minimizers formally.
- See if robust minimizers can be improved for small \(k < 1.25w\).
- Implement 3-way split for robust minimizers.
- Plots on distribution of distance between adjacent selected positions.

## References

*Proceedings of the Vldb Endowment*16 (9): 2117–31. https://doi.org/10.14778/3598581.3598586.

*Cell Systems*12 (10): 958–68.e6. https://doi.org/10.1016/j.cels.2021.08.009.

*Research in Computational Molecular Biology*, 37–53. Springer International Publishing. https://doi.org/10.1007/978-3-030-45257-5_3.

*Bioinformatics*32 (14): 2103–10. https://doi.org/10.1093/bioinformatics/btw152.

*Ieee Transactions on Knowledge and Data Engineering*35 (11): 11093–111. https://doi.org/10.1109/tkde.2022.3231780.

*Bioinformatics*34 (13): i13–22. https://doi.org/10.1093/bioinformatics/bty258.

*Bioinformatics*33 (14): i110–17. https://doi.org/10.1093/bioinformatics/btx235.

*Plos Computational Biology*13 (10): e1005777. https://doi.org/10.1371/journal.pcbi.1005777.

*Bioinformatics*38 (Supplement_1): i185–94. https://doi.org/10.1093/bioinformatics/btac245.

*Bioinformatics*39 (Supplement_1): i534–43. https://doi.org/10.1093/bioinformatics/btad219.

*Bioinformatics*20 (18): 3363–69. https://doi.org/10.1093/bioinformatics/bth408.

*Proceedings of the 2003 Acm Sigmod International Conference on Management of Data*. Sigmod/Pods03. ACM. https://doi.org/10.1145/872757.872770.

*Bioinformatics*36 (Supplement_1): i119–27. https://doi.org/10.1093/bioinformatics/btaa472.