SneakySnake: a fast and accurate universal genome pre-alignment filter for CPUs, GPUs and FPGAs
SneakySnake: a fast and accurate universal genome pre-alignment filter for CPUs, GPUs and FPGAs
复制标题
DOI：
10.1093/bioinformatics/btaa1015
复制
发表时间：
2020-12-01
期刊：
影响因子：
5.8
通讯作者：
Mutlu, Onur
中科院分区：
文献类型：
--
作者：
Alser, Mohammed;Shahroodi, Taha;Mutlu, Onur
动机：我们介绍了SneakySnake，一个高度并行和高度准确的预对齐过滤器，显着降低了计算成本高的序列比对的需要。SneakySnake的核心思想是将VLSI芯片布局中的近似串匹配（ASM）问题归结为单网络布线（SNR）问题。在信噪比问题中，我们感兴趣的是在一个特殊的网格布局，包含障碍物，找到连接两个终端的最佳路径，以最少的布线成本。SneakySnake算法快速解决SNR问题，并使用找到的最佳路径来决定是否需要执行序列比对。将ASM问题简化为SNR也使得SneakySnake能够高效地在CPU、GPU和FPGA上实现。结果：与最先进的预对准滤波器Shouji、GateKeeper和SHD相比，SneakySnake显著提高了预对准滤波的精度，最高可达四个数量级。对于短序列，SneakySnake加速Edlib（Myers位向量算法的最先进实现）和Parasail（最先进的序列比对仪，具有可配置的评分功能），最高可达37.7 x和43.9 x（平均>12倍），分别与其CPU实现，并分别高达413倍和689倍（平均>400倍），与FPGA和GPU加速。对于长序列，SneakySnake的CPU实现将Parasail和KSW 2（minimap2的序列对齐器）分别加速高达979 x（平均276.9 x）和91.7 x（平均31.7 x）。由于SneakySnake不会取代序列比对，用户仍然可以获得他们选择的比对器的所有功能（例如可配置的评分函数），而不像现有的加速努力牺牲了一些比对器功能。
Motivation: We introduce SneakySnake, a highly parallel and highly accurate pre-alignment filter that remarkably reduces the need for computationally costly sequence alignment. 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 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 or not performing sequence alignment is necessary. Reducing the ASM problem into SNR also makes SneakySnake efficient to implement on 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. For short sequences, SneakySnake accelerates Edlib (state-of-the-art implementation of Myers's bit-vector algorithm) and Parasail (stateof-the-art sequence aligner with a configurable scoring function), by up to 37.7 x and 43.9 x (>12 x on average), respectively, with its CPU implementation, and by up to 413 x and 689 x (>400 x on average), respectively, with FPGA and GPU acceleration. For long sequences, the CPU implementation of SneakySnake accelerates Parasail and KSW2 (sequence aligner of minimap2) by up to 979 x (276.9 x on average) and 91.7 x (31.7 x on average), respectively. As SneakySnake does not replace sequence alignment, users can still obtain all capabilities (e.g. configurable scoring functions) of the aligner of their choice, unlike existing acceleration efforts that sacrifice some aligner capabilities.