Sassy: fuzzy searching DNA sequences using SIMD
Bioinformatics · 03.05.2026 · 42 (5)
DOI: 10.1093/bioinformatics/btag244 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, online erschienen am 24.05.2026. Verfasst von Rick Beeloo und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Theoretical Biology and Bioinformatics, Utrecht University, Utrecht, 3584CH, Netherlands. Hauptthemen laut MEDLINE: Sequence Analysis, DNA, Software, DNA. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 108 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: ZonMw, ETH Research.
Abstract (Originalsprache)
Motivation Approximate string matching (ASM) is the problem of finding all occurrences of a pattern in a text while allowing up to k errors. Many modern methods use seed-chain-extend, which is fast in practice, but does not guarantee finding all matches with ≤k errors. However, applications such as CRISPR off-target detection require exhaustive results. Results We introduce Sassy, a library and tool for ASM of short patterns in long texts. Sassy splits the text into four parts that are searched in parallel, and uses bitvectors in the text direction rather than the pattern direction. This has complexity O(k⌈n/W⌉) when searching a random text of length n, where W=256 is the SIMD width, and provides significant speedups for small k. Separately, we allow matches of the pattern to extend beyond the text for an overhang cost of, e.g. α=0.5 per character, to find matches near contig or read ends. Sassy is 4× to 15× faster than Edlib for patterns ≤1000 bp, and can search text with a throughput near 2 Gbp/s. Likewise, Sassy is over 100× faster than parasail. We apply Sassy to CRISPR off-target detection by searching 61 guide sequences in a human genome. Sassy is 100× faster than SWOffinder and only slightly slower (for k≤3) than CHOPOFF, for which building its index takes 20 min. Sassy also scales well to larger k, unlike CHOPOFF whose index took over 10 h to build for k=5. Availability and implementation Sassy is available as library and binary at https://github.com/RagnarGrootKoerkamp/sassy, and archived at swh:1:dir:e884758dce5777a441bc2799dc8824e563c5f97b.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Substanzen
Autor:innen und Institutionen
- Department of Theoretical Biology and Bioinformatics, Utrecht University, Utrecht, 3584CH, Netherlands.
- Department of Computer Science, ETH Zurich, Zurich, 8092, Switzerland.
- Department of Computer Science, Karlsruhe Institute of Technology, Karlsruhe, 76131, Germany.
ORCID-Profile: Rick Beeloo, Ragnar Groot Koerkamp
Förderung
- ZonMw
- ETH Research
Zitieren
APA
Beeloo, R., & Groot Koerkamp, R. (2026). Sassy: fuzzy searching DNA sequences using SIMD. Bioinformatics, 42(5). https://doi.org/10.1093/bioinformatics/btag244
Vancouver
Beeloo R, Groot Koerkamp R. Sassy: fuzzy searching DNA sequences using SIMD. Bioinformatics. 2026;42(5). doi:10.1093/bioinformatics/btag244
BibTeX
@article{Beeloo2026,
author = {Beeloo, Rick and Groot Koerkamp, Ragnar},
title = {Sassy: fuzzy searching DNA sequences using SIMD},
journal = {Bioinformatics},
year = {2026},
volume = {42},
number = {5},
doi = {10.1093/bioinformatics/btag244}
}
EUVIMED