Post

It's a good day when the first item in your feed is your own work :) @rickbitloo.bsky.social was annoyed that scanning reads for all 96 rapid kit barcodes is bottleneck in Barbell, so he made Sassy2: 13x (150bp) to 4.6x (8kbp) faster than v1 by batch-searching patterns, and >100Gbp/s on 16 threads!

bioRxiv Bioinfo@biorxiv-bioinfo.bsky.social

Sassy2: Batch Searching of Short DNA Patterns https://www.biorxiv.org/content/10.64898/2026.03.10.710811v1

13/3/26, 12:18 am11 reposts24 likes

Ragnar {Groot Koerkamp}

@curiouscoding.nl

13 Mar

Oh, the missing gh link: github.com/ragnarGrootK...

github.comGitHub - RagnarGrootKoerkamp/sassy: Fast approximate string searchingFast approximate string searching. Contribute to RagnarGrootKoerkamp/sassy development by creating an account on GitHub.

Ragnar {Groot Koerkamp}

@curiouscoding.nl

13 Mar

That's on top of ~10x speedup over Edlib that we got in v1, (which also has a slightly updated preprint)! Specifically, v1 splits the text into 4 chunks and uses SIMD in the text direction, but this is inefficient when the text is only ~W=256 long, which v2 fixes. www.biorxiv.org/content/10.1...

Ragnar {Groot Koerkamp}

@curiouscoding.nl

13 Mar

Just for reference, the tiling strategy in v1: the text is split into 4 chunks that are processed in parallel with 1 chunk per 64 bit SIMD lane. Each lane represents 64 adjacent *columns* of the DP matrix.

Ragnar {Groot Koerkamp}

@curiouscoding.nl

13 Mar

In v2, we filp the SIMD tiling and bitpacking direction: Each lane represents a separate *pattern*, and the bits are adjacent *rows* of the matrix. Basically the original 'pack multiple patterns in a word' of Hyyrö 2005, but on an AVX-512 SIMD level. So now we can search 16 32bp patterns at once!

Ragnar {Groot Koerkamp}

@curiouscoding.nl

13 Mar

Another cool trick, also by Hyyrö: if k=3 edits are allowed, then most of the time, this cost is exceeded after aligning around 6-10 characters. Thus, we first only find cost <=k candidate matches of the 16bp suffix of each pattern, so that we can double the SIMD parallellism to 32 x 16bp.