SneakySnake

SneakySnake converts approximate string matching (ASM) problems into single net routing (SNR) instances to pre-filter candidate genomic read–reference pairs and reduce the number of full sequence alignments, thereby accelerating sequence alignment on CPUs, GPUs, and FPGAs.

Key Features:

• Highly Parallel and Accurate Filtering: Implements a highly parallel pre-alignment filter that reduces the number of full sequence alignments while preserving alignment accuracy.
• Algorithmic Innovation: Transforms ASM into the single net routing (SNR) problem from VLSI layout and identifies optimal paths on a grid with obstacles to decide whether full alignment is required.
• Cross-Architecture Efficiency: Supports implementations on CPUs, GPUs, and FPGAs to leverage diverse hardware parallelism.
• Superior Performance: Outperforms pre-alignment filters Shouji, GateKeeper, and SHD by up to four orders of magnitude in accuracy, and accelerates Edlib and Parasail on short reads by 37.7×–689× and Parasail and KSW2 (used in minimap2) on long reads by up to 979× and 91.7×, respectively.
• Compatibility with Existing Aligners: Maintains full aligner functionality, preserving configurable scoring functions and other aligner features.

Scientific Applications:

• Short-read alignment (Illumina): Pre-filters candidate pairs for short-read aligners processing Illumina data to reduce computational cost for Edlib and Parasail.
• Long-read alignment (ONT, PacBio): Pre-filters candidate pairs for long-read workflows with ONT and PacBio reads to reduce computational cost for Parasail and KSW2/minimap2.
• Large-scale genomic studies: Decreases the number of expensive full alignments required, reducing compute load in large-scale genomic analyses.

Methodology:

Converts approximate string matching into the single net routing (SNR) problem and solves SNR by finding optimal paths on a grid with obstacles to determine whether full sequence alignment is necessary.