Post

Sassy is out now! Ever need to search for approximate matches of short DNA strings? Sassy is the tool to use! Available now wherever you get your code With @rickbitloo.bsky.social curiouscoding.nl/papers/sassy... github.com/ragnarGrootK...

First off, the problem definition :) Sassy solves approximate string matching (ASM): finding all occurrences of a pattern in a text, with up to k errors. As you would expect from me, Sassy uses unit-cost edit distance.

The one long-lasting takeaway from this work: Searching a pattern P in text T and searching rev(P) in rev(T) give different results! Saying 'we find all matches' is kinda undefined, unless you specifically list all *intervals* of the text that align with cost <= k. But nobody does that.

Anyway, research on ASM is super old, with so many papers on it between 1980 and 2000. But then Myers'99 ruined the fun by introducing his O(ceil[k/w]*n) bitpacking algorithm (m=|P|, n=|T|), that computes 64 states in a column at once. Edlib also implements pretty much exactly this figure.

Speaking of Edlib: like many other modern tools, it solves 'semi-global alignment', which finds a (set of) alignments of the pattern to a substring of the text *of optimal cost*. Note that this can be much less than the set of matches of cost ≤k.

Algorithmically, the first main feature of Sassy is to tile the bitvectors horizontally, in the text direction. This way, we don't waste as much compute when only the top rows of the matrix are needed. In particular, usually the top 2*k rows are sufficient to get DP entries >k: O(k*ceil[n/w]).

On top of that, we use SIMD to process 4 chunks of each (long) input text in parallel, similar to simd-minimizers. Final complexity on random text: O(k*ceil[n/W]).

Then, there is one more small contribution: we extend 'overlap' alignments to have an 'overhang' cost. This way, we can allow patterns matching only a prefix or suffix of the text, and control the penalty for characters extending beyond the text. By default, a cost of 0.5 works well.

All this results in over 10x speedup compared to Edlib when searching text without matches, especially when k is small. We see a similar speedup compared to parasail.

Sassy is available as: - rust library: cargo add sassy - CLI tool: cargo install sassy - python library: pip install sassy-rs - c bindings: see the repo crates.io/crates/sassy

In all cases, the API is simple and similar: create a `Searcher` object with the alphabet and settings of your choice (ASCII/DNA/IUPAC), and then call `search(pattern, text, k)` on it.

Just one major drawback at this point: we didn't make an arm/neon port yet, and so we depend on avx2 and bmi2 instructions. Feel free to help out with this ;)