2026-08-27T21:20:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27526 2026-08-27T06:04:07Z ddc:004 open_access

The Anti-Lexicographic SUS-Anchor: An Empirically Optimal Selection Scheme Groot Koerkamp, Ragnar Minimizers Sampling scheme Sketching Maximal suffix Smallest unique substring - Motivation. Selection schemes provide a way to select a subset of positions in a text in such a way that no two consecutive selected positions are more than w apart. These selected positions can be used as "anchor" points for text indices such that every sufficiently long pattern corresponds to at least one anchor [Ayad et al., 2025]. Closely related are sampling schemes, that sample a k-mer from each window of w consecutive k-mers in a text, and the more restricted minimizer schemes, that achieve this by taking the smallest k-mer according to some order. In recent years, there has been a renewed interest in the search for low density schemes that select/sample only a small fraction of positions/k-mers. The mod-minimizer [Groot Koerkamp and Pibiri, 2024] provides a near-optimal density of 1/w as k / w → ∞, while schemes such as the greedy minimizer work well for explicit small parameters roughly in the regime k ≤ 2w, for k and w up to 15 or so. When k < log_σ w is small, minimizer schemes cannot do well [Marçais et al., 2018]. As a first step towards low density sampling schemes in this regime, we fix k = 1 and search for a near-optimal selection scheme to improve the existing bidirectional string anchors (bd-anchors) [Loukides et al., 2023; Ayad et al., 2025]. - Methods. Inspired by bd-anchors, we introduce the smallest unique substring or SUS-anchor: given a window, this considers all suffixes that do not occur as a substring elsewhere in the window. It then samples the start position of the smallest suffix according to the new anti-lexicographic order that minimizes the first character and maximizes the remaining characters. We give a linear-time and O(w) space streaming algorithm to compute all SUS-anchors of a string. - Results. For alphabet size σ = 4 and k = 1, the parameter-free anti-lexicographic SUS-anchor empirically has density < 1% away from the density lower bound and is at least 4× closer to the lower bound than all other tested schemes. For alphabet size σ = 2, the density is at most 10% above the lower bound, which still improves 2× to 3× the overhead of the random minimizer and is consistently better than the greedy minimizer. Likewise, the anti-lexicographic minimizer performs better than all other schemes apart from the greedy minimizer. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ragnar Groot Koerkamp 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.22 urn:nbn:de:0030-drops-275261 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.22 eng https://creativecommons.org/licenses/by/4.0/legalcode