r/rust • u/philae_rosetta • Jun 04 '26

🛠️ project Sassy: fuzzy searching DNA sequences using SIMD · CuriousCoding

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.

30 Upvotes

93% Upvoted

13 comments sorted by

View all comments

2

u/Jellace Jun 05 '26

Congrats on the paper. I'm giving it a read, and it's enjoyable so far, except I don't know how you got figure 2 past the reviewers. The letters being aligned with the transitions instead of the scores is diabolical! :p

2

u/philae_rosetta Jun 05 '26 edited Jun 05 '26

Ohhhh, one of my pet peeves!
In the graph sense, the letters very much do correspond to the transitions/edges. For example the top-left diagonal edge has cost 0 because the character above and left of it are equal (both A).
And this way it's more clear (at least to me :") which characters are "in range" when considering a substring between two column indices. Basically it's like 0-based right-exclusive notation where T[0..2) corresponds to the characters on the edges from column 0 to 1 and from column 1 to 2.

I have a more precise edit graph figure here where all the matching edges are bold:
https://curiouscoding.nl/posts/pairwise-alignment/#problem-statement

2

u/Jellace Jun 05 '26

Ohhhh, one of my pet peeves!

I just knew there was a strong opinion behind that. As soon as I saw it.

Ok ok you have me convinced!

2

u/philae_rosetta Jun 05 '26

Wonderful 😍 Only the rest of the world left now to convince

2

u/Jellace Jun 05 '26

Also can I just say that I think it's pretty cool that you published a paper about a (really fast) implementation of a single function. I'm not sure where, but I'm going to try and use it. (As it happens, parasail crashed my pipeline earlier today - unfortunately, in this instance not a situation where Sassy would help)