The Anti-Lexicographic SUS-anchor

Minimizer schemes Link to heading

Input: a window \(W\in \Sigma^{w+k-1}\)

Minimizer scheme: Sample the \(k\)-mer with the one with smallest hash: \[f(W) = \mathrm{argmin}_{0\leq i\lt w\ \ } h(W_{i\dots i+k}).\]

Sampling scheme: Arbitrary function \(f: \Sigma^{w+k-1}\to \{0, \dots, w-1\}.\)

Density: The expected fraction of sampled \(k\)-mers in a random string:

• E​A​DCAE.....

• .​A​DCAEB....

• ..DC​A​EBE...

• ...C​A​EBEC..

• ....​A​EBECD.

• .....E​B​ECDC

• E​A​DC​A​E​B​ECDC

Density bounds Kille et al. 2024 Link to heading

Conjecture: Optimal schemes exist for \(k\equiv 1\pmod w\)?

• \(k\to\infty\): yes, mod-mini Groot Koerkamp and Pibiri 2024
• \(\sigma\to\infty\): yes, mod-mini
• \(w=2\): yes, w.i.p. by Bryce
• \(k=1\): almost, today

Results Link to heading

Today: near-optimal selection schemes Link to heading

Selection scheme

• \(k=1\), i.e., sample a position: \(f: \Sigma^w\to \{0, 1, \dots, w-1\}\).

Bidirectional anchors Loukides, Pissis, and Sweering 2023

• Sample the start position of the lexicographically smallest rotation of \(W\).

• E​A​DCAE.....

• .​A​DCAEB....

• ..DC​A​EBE...

• ...C​A​EBEC..

• ....​A​EBECD.

• .....E​B​ECDC

• E​A​DC​A​E​B​ECDC

• Can be used to build an index on selected prefixes & suffixes. Loukides, Pissis, and Sweering 2023

Drawbacks of bd-anchors Link to heading

• Rotations wrap around:
  • ​FB​A​DC..
  • ​.BADC​A​.
  • ​..​A​DCAE

• Small strings cluster:
  • A​AABCD....
  • .​A​ABCDE.
  • ..​A​BCDEF

SUS-anchors Link to heading

• Sample the smallest unique substring
• CABBAB.
  • C A B B A B CA AB BB BA AB CAB ABB BBA BAB CABB ABBA BBAB CABBA ABBAB CABBAB
  • C A B B A B CA AB BB BA AB CAB ABB BBA BAB CABB ABBA BBAB CABBA ABBAB CABBAB
  • C A B B A B CA AB BB BA AB CAB ABB BBA BAB CABB ABBA BBAB CABBA ABBAB CABBAB

• C​ABB​AB.

• Equivalent: consider the smallest unique suffix

• SUS-anchors are forward…
  • ​FB​A​DC..
  • ​.B​AD​CA.
  • ​..​AD​CAE

• but small strings still cluster:
  • AAA​BCD..
  • .​AA​BCDE.
  • ..​A​BCDEF

• Goal: Avoid overlapping SUS-anchors

The anti-lexicographic SUS-anchor Link to heading

• Anti-lexicographic order:

  • compare the first character normally, and the remaining characters in reverse.
  • The smallest string is AZZZZ....
  • Like 10-minimizers/DNA-spacers (Shur, Tziony, and Orenstein 2026)

• Anti-lexicographic SUS-anchor: anti-lex smallest unique substring.

• Small strings do not overlap anymore:
  • AA​AB​CD..
  • .A​AB​CDE.
  • ..​AB​CDEF

• Some intuition
  • SUS-anchors are optimal when sampled substrings never overlap
  • Bad case:
  • ​10001000​100.
  • .000​1000​1001

Density results Link to heading

Results on real data Link to heading

Conclusion Link to heading

Anti-lex SUS-anchors…

• are parameter-free,
• have near-optimal density,
• and can be streamed in linear time.

References Link to heading

References Link to heading