Sassy 1 & 2: Fuzzy searching DNA using SIMD

Approximate String Matching Link to heading

  • Not semi-global alignment
  • Not \(O(nm/w)\)!
  • Lots and LOTS of old literature!

Intricacies of ASM Link to heading

  • What is a match?
    • end pos? (start, end)? full path?

  • Which matches to report? Link to heading

  • Forward \(\neq\) reverse-complement
  • Traceback is a mess!

Overhang Link to heading

  • figure

Myers’ Bitpacking Link to heading

  • Horizontal vs vertical tiling

SIMD: Chunking the text Link to heading

  • figure

Sassy 1 results Link to heading

  • 1 or 2 plots

Applications Link to heading

  • Application: grep-like CLI
  • Application: Crispr off-target searching

Sassy 2: batching \(\gg\) chunking Link to heading

  • text chunking requires gathering the text and transposing it into SIMD-lanes
  • batching is simpler when many short patterns
  • v2 fig

Sassy 2 results Link to heading

  • v2 results
  • barbell results