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. METHODS: We introduce Sassy, a library and tool for ASM of short patterns in long texts. Sassy splits the text into 4 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. RESULTS: Sassy is 4× to 15× faster than Edlib for patterns ≤1000bp, 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 minutes. Sassy also scales well to larger k, unlike CHOPOFF whose index took over 10 hours to build for k=5. AVAILABILITY: Sassy is available as library and binary at https://github.com/RagnarGrootKoerkamp/sassy, and archived at swh : 1: dir: e884758dce5777a441bc2799dc8824e563c5f97b.
Beeloo et al. (Fri,) studied this question.