Sassy2: Batch Searching of Short DNA Patterns

Sassy2 is een in Rust geïmplementeerd hulpmiddel dat door het efficiënt verdelen van meerdere korte DNA-patronen over SIMD-kanalen en het toepassen van een suffix-filter, de batch-zoeksnelheid voor ongeveer stringmatching aanzienlijk verbetert ten opzichte van eerdere methoden.

De kern

🧬 Sassy2: De Super-Snelheidsscout voor DNA

Stel je voor dat je een enorme bibliotheek hebt (het menselijk DNA), vol met miljarden letters (A, C, G, T). Je hebt een lijst met korte zoekwoorden (zoals barcodes, primers of CRISPR-gidsen) en je wilt weten waar deze woorden in de bibliotheek staan, zelfs als er een paar letters verkeerd zijn gespeld (door foutjes in de sequencing).

Dit is wat bioinformatici doen, maar het is vaak traag en lastig. Sassy2 is de nieuwe, razendsnelle tool die dit probleem oplost.

1. Het Probleem: De "Zoektocht in de Sneeuwstorm"

Vroeger waren zoektools als Sassy1 of Edlib als een enkele detective die door de bibliotheek loopt.

• Als je één zoekwoord had, ging het snel.
• Maar als je 100 zoekwoorden had, moest de detective 100 keer door de hele bibliotheek lopen.
• Als de zoekwoorden heel kort waren (zoals een kort woord van 20 letters), was het zoeken zelfs nog lastiger. De detective moest elke keer stoppen om te checken of het woord echt klopte, wat veel tijd kostte.

2. De Oplossing: Sassy2 (De "Super-Team" aan Detectives)

Sassy2 gebruikt een slimme truc die SIMD (Single Instruction, Multiple Data) heet. In plaats van één detective, stuur je een heel team detectives tegelijkertijd de bibliotheek in.

• De Analogie van de Lanes (Spoorbanen):
  Stel je een superhighway voor met 32 of 64 rijbanen naast elkaar.
  • Sassy1 deelde de tekst (de bibliotheek) in stukken en stuurde elke detective een ander stukje tekst. Dit werkte goed voor lange teksten, maar bij korte teksten stonden veel rijbanen leeg (verspilde kracht).
  • Sassy2 doet het anders: het deelt de zoekwoorden uit. Elke rijbaan krijgt een ander zoekwoord, maar ze scannen allemaal dezelfde tekst tegelijk. Zo wordt de hele snelweg volgepropt met werk.

3. De Slimme Truc: De "Korte Check" (Suffix Filter)

Hier wordt het echt slim. Soms hoef je niet het hele zoekwoord te checken om te weten dat het niet klopt.

• Voorbeeld: Als je zoekt naar het woord "SCHAAP" en je ziet in de tekst "SCHA...Z", dan weet je al bij de eerste paar letters dat het geen schaap is. Je hoeft niet tot het einde te lezen.

Sassy2 gebruikt dit idee:

1. Fase 1 (De Snelle Scan): Het team kijkt eerst alleen naar het eindje van de zoekwoorden (bijvoorbeeld de laatste 16 letters). Dit is heel snel en ze kunnen hierdoor nog meer zoekwoorden tegelijk verwerken.
2. Fase 2 (De Diepteprik): Alleen als dat eindje misschien wel klopt, gaan ze het hele woord controleren.
   • Vergelijking: Het is alsof je op een feestje op zoek bent naar vrienden. Je kijkt eerst alleen naar hun schoenen (de korte check). Als je iemand met rode schoenen ziet, loop je pas naar hen toe om te kijken of het echt je vriend is. Als ze blauwe schoenen hebben, loop je gewoon voorbij. Dit bespaart enorm veel tijd!

4. Wat is het Resultaat? (De Snelheid)

De resultaten zijn indrukwekkend. Sassy2 is niet alleen sneller, maar ook veel efficiënter:

• Tegenover de oude tools: Sassy2 is tot 450 keer sneller dan de standaard tool (Edlib) en tot 23 keer sneller dan de vorige versie (Sassy1), vooral bij korte teksten.
• In de praktijk:
  • Bij het zoeken naar CRISPR-fouten in het hele menselijk genoom: Het duurt nu slechts 30 milliseconden per zoekopdracht. Vroeger duurde dat meer dan een seconde.
  • Bij het sorteren van DNA-sequenties (barcodes): Het kan meer dan 100 miljard letters per seconde verwerken.

5. Waarom is dit belangrijk?

In de biologie en geneeskunde moeten we vaak zoeken naar zeer korte patronen in enorme hoeveelheden data.

• CRISPR: Om te weten of een gen-therapie per ongeluk een verkeerd stukje DNA snijdt.
• Barcodes: Om te weten welk monster uit een buisje komt als je duizenden monsters tegelijk scant.

Sassy2 maakt deze taken zo snel dat onderzoekers niet meer hoeven te wachten op hun computer, maar direct resultaten kunnen zien. Het is alsof je van een fiets op een raket bent gestapt.

Kort samengevat:
Sassy2 is een slimme, parallelle zoekmachine die korte DNA-woorden razendsnel vindt door eerst alleen naar het eindje te kijken en pas later het hele woord te controleren, terwijl hij honderden zoekopdrachten tegelijk uitvoert.

Technische samenvatting

Probleemstelling

Het zoeken naar korte DNA-patronen (zoals barcodes, primers of CRISPR-spacers, typisch 20–40 bp) binnen sequentiële reads of genoomsequenties is een fundamentele taak in de bio-informatica. Dit valt onder het probleem van meerdere benaderende string-matching (MASM): het vinden van alle voorkomens van meerdere patronen in een tekst met maximaal $k$ fouten (mismatches, inserties of deleties).

Bestaande methoden hebben beperkingen:

• Klassieke benaderingen (gebaseerd op exacte matches) worden inefficiënt voor korte patronen wanneer het aantal toegestane fouten ($k$) toeneemt, wat leidt tot veel valse positieven of gemiste matches.
• Sassy1 (de voorganger) optimaliseerde het zoeken naar één patroon in lange teksten door tekst-chunks over SIMD-lanes te verdelen. Dit werkt echter niet optimaal voor korte teksten of batches van veel korte patronen, omdat de SIMD-registers dan onderbenut blijven of tekst herhaaldelijk gescand moet worden.
• Edlib (een veelgebruikte bibliotheek) mist SIMD-vectorisatie en is aanzienlijk trager, hoewel deze dynamisch de drempel kan verlagen.

Methodologie

Sassy2 introduceert een nieuwe aanpak die speciaal is ontworpen voor het batch-verwerken van meerdere korte, even lange patronen met behulp van SIMD (Single Instruction, Multiple Data) parallelisme.

1. SIMD Pattern Tiling (in plaats van Text Tiling)
In tegenstelling tot Sassy1 (dat tekst verdeelde over lanes), verdeelt Sassy2 de patronen over de SIMD-lanes.

• Een SIMD-register van breedte $W$ wordt opgedeeld in $L$ onafhankelijke lanes van breedte $w$.
• Elke lane houdt een onafhankelijke Myers bit-vector staat bij.
• Hierdoor wordt de tekst slechts één keer gescand, terwijl elk teken gelijktijdig wordt vergeleken met alle $L$ patronen. Dit elimineert de noodzaak om de tekst voor elk patroon opnieuw te coderen en te scannen.

2. Tweestapsbenadering met Suffix-filtering
Om het probleem van het ontbreken van "early rejection" (vroege afwijzing) bij pattern-tiling op te lossen, introduceert Sassy2 een tweestapsproces:

• Fase 1: Suffix-filtering. In plaats van het volledige patroon te vergelijken, wordt eerst alleen het suffix (het einde) van de patronen gecontroleerd.
  • Er wordt gebruikgemaakt van een kleinere woordbreedte $w'$ (bijv. 8, 16 of 32 bits) in plaats van de volledige lane-breedte $w$.
  • Dit verhoogt het aantal beschikbare lanes ($L' = W/w'$), waardoor meer patronen parallel kunnen worden verwerkt.
  • Alleen posities waar het suffix binnen de foutmarge ($k$) past, worden doorgestuurd naar de volgende fase.
• Fase 2: Volledige verificatie. Voor de kandidaat-posities die het filter doorstaan, wordt de volledige Myers DP-matrix berekend over het volledige patroon en de bijbehorende tekstslice.
  • Batch tracing: Als meerdere eindpunten dicht bij elkaar liggen, worden ze gegroepeerd in een continu bereik. Dit maakt het mogelijk om de DP-matrix te "amortiseren" (amortized), waardoor minder kolommen hoeven te worden berekend dan bij het onafhankelijk verwerken van elke match.

3. Implementatie

• Geschreven in Rust.
• Ondersteunt AVX2 (256-bit) en AVX-512 (512-bit) instructiesets.
• Geoptimaliseerd voor patronen met gelijke lengte (momenteel een beperking ten opzichte van Sassy1).

Belangrijkste Bijdragen

1. Multi-pattern SIMD-implementatie: Een praktische implementatie van Myers' bit-parallelisme die meerdere korte patronen parallel verwerkt binnen SIMD-lanes, geoptimaliseerd voor snelle laad- en opslagbewerkingen.
2. Suffix-filter: Een efficiëntere en snellere methode dan de "early-break" check in Sassy1. Door eerst korte suffixen te filteren met meer lanes, wordt de doorvoer aanzienlijk verhoogd, vooral bij typische bio-informatica-toepassingen.
3. Batch-verwerking: De tool is specifiek ontworpen om batches van patronen (bijv. honderden gRNA's of barcodes) in één keer te verwerken, wat de totale doorvoer maximaliseert.

Resultaten

De prestaties zijn getest op synthetische data en real-world genomics-taken, vergeleken met Sassy1 en Edlib.

Synthetische Data:

• Voor korte teksten ($n \le 200$ bp) bereikt Sassy2 een snelheidswinst van 10–50x ten opzichte van Sassy1.
• Voor grote teksten ($n \ge 1$ Mbp) is de winst 2–4x ten opzichte van Sassy1.
• T.o.v. Edlib zijn de snelheidswinsten enorm: tot 467x voor korte teksten en 20–45x voor real-world taken.
• De doorvoer schaalt bijna lineair met het aantal patronen totdat de SIMD-lanes vol zitten.

Real-world Toepassingen (16 threads):

1. CRISPR Off-target Zoeken: Zoeken naar 312 gRNA's in het menselijk genoom (CHM13).
   • Sassy2: 105,9 Gbp/s per gRNA (30 ms per gRNA).
   • Sassy1: 28,6 Gbp/s (3,7x trager).
   • Edlib: 3,0 Gbp/s (35,7x trager).
2. Barcode Demultiplexing (Nanopore): Zoeken naar 96 barcodes in Nanopore reads.
   • Sassy2: 116,8 Gbp/s per barcode (0,27 s totaal).
   • Sassy1: 25,5 Gbp/s (4,6x trager).
   • Edlib: 2,57 Gbp/s (45x trager).

Betekenis en Conclusie

Sassy2 vertegenwoordigt een significante doorbraak in het efficiënt zoeken naar korte DNA-patronen. Door de combinatie van SIMD-geoptimaliseerd pattern-tiling en een suffix-filter, overkomt het de beperkingen van eerdere methoden die inefficiënt waren voor korte teksten of batches patronen.

De tool maakt hoge doorvoer mogelijk (meer dan 100 Gbp/s per patroon) voor kritieke taken zoals CRISPR-design en het verwerken van Nanopore-data. Hoewel de huidige versie beperkt is tot patronen van gelijke lengte, biedt Sassy2 een robuuste, praktische oplossing voor een breed scala aan genomics-zoekopdrachten en demonstreert het hoe oude algoritmen (Myers' bit-vector) effectief kunnen worden gemoderniseerd voor hedendaagse hardware-architecturen.