SneakySnake: A Fast and Accurate Universal Genome Pre-Alignment Filter for CPUs, GPUs, and FPGAs
📜 Abstract
Motivation: We introduce SneakySnake, a highly parallel and highly accurate pre-alignment filter that remarkably reduces the need for the computationally costly sequence alignment step. The key idea of SneakySnake is to reduce the approximate string matching (ASM) problem to the single net routing (SNR) problem in VLSI chip layout. In the SNR problem, we are interested in only finding the optimal path that connects two terminals with the least routing cost on a special grid layout that contains obstacles. The SneakySnake algorithm quickly solves the SNR problem and uses the found optimal path to decide whether performing sequence alignment is necessary. Reducing the ASM problem into SNR also makes SneakySnake efficient to implement for all modern high-performance computing architectures (CPUs, GPUs, and FPGAs). Results: SneakySnake significantly improves the accuracy of pre-alignment filtering by up to four orders of magnitude compared to the state-of-the-art pre-alignment filters, Shouji, GateKeeper, and SHD. SneakySnake accelerates Edlib (state-of-the-art implementation of Myers’s bit-vector algorithm) and Parasail (sequence aligner with configurable scoring function), by up to 37.6× and 43.9× (>12× on average), respectively, without requiring hardware acceleration, and by up to 413× and 689× (>400× on average), respectively, using hardware acceleration. SneakySnake also accelerates the sequence alignment of minimap2, a state-of-the-art read mapper, by 2.51× to 6.83× without requiring hardware acceleration. As SneakySnake does not replace sequence alignment, users can still configure the aligner of their choice for different scoring functions, surpassing most existing efforts that aim to accelerate sequence alignment. Availability: https://github.com/CMU-SAFARI/SneakySnake
✨ Summary
Summary
The paper introduces SneakySnake, a lossless pre-alignment filter that transforms approximate string matching into a single-net-routing problem. Its design supports CPU, GPU, and FPGA implementations and is intended to eliminate dissimilar sequence pairs before invoking computationally expensive alignment algorithms. The paper reports substantial reductions in false accepts and large end-to-end speedups when combined with Edlib, Parasail, and minimap2. (arxiv.org)
Influence
The work was subsequently published as a Bioinformatics journal article and released with an open-source implementation. The accompanying software has been extended to support multithreading and both short- and long-read pre-alignment filtering, indicating practical continuation of the original implementation. (pubmed.ncbi.nlm.nih.gov)
Later research has used SneakySnake as a comparative baseline or positioned it within the broader hardware-accelerated genome-analysis literature. A survey of genome-analysis architectures identifies it as a pre-alignment filter spanning CPUs, GPUs, and FPGAs, while the later FilterFuse work reports comparative end-to-end results against SneakySnake for long-read pre-alignment filtering. These references indicate that SneakySnake became a recognized baseline for evaluating subsequent genomic filtering architectures, although the available evidence does not establish broad industrial deployment. (pmc.ncbi.nlm.nih.gov)