Post

Cool stuff boys! It would be interesting to compare against kmer matches under Hamming distance. Since your method is specialized for short patterns, maybe kmer under H. dist could give similar results, but hopefully in an even shorter time :)

We briefly looked into that! Especially it's relevant for CRISPR where the penalty of indels is actually super high. From a theoretical perspectice, FFT gives O(n*lg(m)), and combinatorially it's O(n*sqrt(m)). 1/ projects.lsv.ens-paris-saclay.fr/confsrentree...

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.