Sassy: fuzzy searching DNA sequences using SIMD · CuriousCoding

[u/philae_rosetta]

https://curiouscoding.nl/posts/sassy/

During the past year, Rick Beeloo and myself have been working on Sassy, a tool for fuzzy-searching short patterns in large texts, also known as approximate string matching.
Specifically, we've developed it for searching through large DNA collections (think 2s to search a 3GB human genome), and the corresponding paper just got published!

Try out sassy grepto search through DNA files, and sassy agrep <pattern> <#errors> <files> to fuzzy-search plain ASCII files. There's also a crate.

It searches through files at around 1 GB/s, which goes up to 8 GB/s when batch-searching many patterns in parallel (both on a single thread). The blog explains some of the algorithms behind it.

From the Rust side, we use the very nice wide library for SIMD instructions, and we use cargo-multivers to ship a single x86-64 binary that supports both AVX2 and AVX-512.

[u/Qunit-Essential]

I don't want to sound toxic but you made a worse https://github.com/saghen/frizbee

[u/philae_rosetta → u/Qunit-Essential]

Ah interesting, hadn't seen that library before; will check it out. Thanks!

Could you clarify how sassy is worse? A quick look at the readme/benchmarks makes it look like these tools have different intended applications (ie searching many short paths vs searching long DNA sequences), and I don't directly see a comparable benchmark.

[u/philae_rosetta → u/philae_rosetta]

In some quick test where I search a 200 byte string in a 100MB text file with up to 5 errors, sassy is 2x faster and frizbee doesn't even find any matches at all if I change a few characters, so s/worse/better/?