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...

Giulio Ermanno Pibiri

@jermp.bsky.social

20 July 2025

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 :)

Ragnar {Groot Koerkamp}

@curiouscoding.nl

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...

projects.lsv.ens-paris-saclay.frprojects.lsv.ens-paris-saclay.fr

20/7/25, 1:35 pm0 reposts1 like

Ragnar {Groot Koerkamp}

@curiouscoding.nl

20 July 2025

Didn't look much into implementations yet. FFT is unlikely to be competitive, but O(n*sqrt(m)) is probably not better than O(n*k) either (just the top O(k) rows). There are a few recent papers using SIMD, but for now my feeling is that the bitpacking for edit distance is very competitive.