{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T23:16:15Z","timestamp":1776122175717,"version":"3.50.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"22-23","license":[{"start":{"date-parts":[[2020,12,1]],"date-time":"2020-12-01T00:00:00Z","timestamp":1606780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Semiconductor Research Corporation grant"},{"name":"EMBO Installation Grant","award":["IG-2521"],"award-info":[{"award-number":["IG-2521"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>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\u2019s bit-vector algorithm) and Parasail (state-of-the-art sequence aligner with a configurable scoring function), by up to 37.7\u00d7 and 43.9\u00d7 (&amp;gt;12\u00d7 on average), respectively, with its CPU implementation, and by up to 413\u00d7 and 689\u00d7 (&amp;gt;400\u00d7 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\u00d7 (276.9\u00d7 on average) and 91.7\u00d7 (31.7\u00d7 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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availabilityand implementation<\/jats:title>\n                  <jats:p>https:\/\/github.com\/CMU-SAFARI\/SneakySnake.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa1015","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T02:43:35Z","timestamp":1606272215000},"page":"5282-5290","source":"Crossref","is-referenced-by-count":36,"title":["SneakySnake: a fast and accurate universal genome pre-alignment filter for CPUs, GPUs and FPGAs"],"prefix":"10.1093","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6117-3701","authenticated-orcid":false,"given":"Mohammed","family":"Alser","sequence":"first","affiliation":[{"name":"Department of Computer Science, ETH Zurich , Zurich 8006, Switzerland"},{"name":"Department of Information Technology and Electrical Engineering, ETH Zurich , Zurich 8006, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taha","family":"Shahroodi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich , Zurich 8006, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"G\u00f3mez-Luna","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich , Zurich 8006, Switzerland"},{"name":"Department of Information Technology and Electrical Engineering, ETH Zurich , Zurich 8006, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Can","family":"Alkan","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Bilkent University , Ankara 06800, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Onur","family":"Mutlu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich , Zurich 8006, Switzerland"},{"name":"Department of Information Technology and Electrical Engineering, ETH Zurich , Zurich 8006, Switzerland"},{"name":"Department of Computer Engineering, Bilkent University , Ankara 06800, Turkey"},{"name":"Department of Electrical and Computer Engineering, Carnegie Mellon University , Pittsburgh, PA 15213, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,12,26]]},"reference":[{"key":"2023062707095695100_btaa1015-B1","doi-asserted-by":"crossref","first-page":"3355","DOI":"10.1093\/bioinformatics\/btx342","article-title":"GateKeeper: a new hardware architecture for accelerating pre-alignment in DNA short read mapping","volume":"33","author":"Alser","year":"2017","journal-title":"Bioinformatics"},{"key":"2023062707095695100_btaa1015-B2","first-page":"33","article-title":"MAGNET: understanding and improving the accuracy of genome pre-alignment filtering","volume":"13","author":"Alser","year":"2017","journal-title":"Trans. Internet Res"},{"key":"2023062707095695100_btaa1015-B3","doi-asserted-by":"crossref","first-page":"4255","DOI":"10.1093\/bioinformatics\/btz234","article-title":"Shouji: a fast and efficient pre-alignment filter for sequence alignment","volume":"35","author":"Alser","year":"2019","journal-title":"Bioinformatics"},{"key":"2023062707095695100_btaa1015-B4","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1109\/MM.2020.3013728","article-title":"Accelerating genome analysis: a primer on an ongoing journey","volume":"40","author":"Alser","year":"2020","journal-title":"IEEE Micro"},{"key":"2023062707095695100_btaa1015-B5","article-title":"Technology dictates algorithms: recent developments in read alignment","author":"Alser","year":"2020","journal-title":"arXiv Preprint arXiv : 2003.00110"},{"key":"2023062707095695100_btaa1015-B6","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1186\/1471-2105-13-238","article-title":"Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory","volume":"13","author":"Chaisson","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023062707095695100_btaa1015-B7","author":"Chakraborty","year":"2018"},{"key":"2023062707095695100_btaa1015-B8","author":"Charikar","year":"2018"},{"key":"2023062707095695100_btaa1015-B9","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1109\/TCBB.2014.2326876","article-title":"Accelerating the next generation long read mapping with the FPGA-based system","volume":"11","author":"Chen","year":"2014","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf"},{"key":"2023062707095695100_btaa1015-B10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1038\/nature15393","article-title":"A global reference for human genetic variation","volume":"526","author":"Consortium","year":"2015","journal-title":"Nature"},{"key":"2023062707095695100_btaa1015-B11","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1186\/s12859-016-0930-z","article-title":"Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments","volume":"17","author":"Daily","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023062707095695100_btaa1015-B12","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1038\/nbt0704-909","article-title":"What is dynamic programming?","volume":"22","author":"Eddy","year":"2004","journal-title":"Nat. Biotechnol"},{"key":"2023062707095695100_btaa1015-B13","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/s12539-017-0225-8","article-title":"FPGASW: accelerating large-scale smith\u2013waterman sequence alignment application with backtracking on FPGA linear systolic array","volume":"10","author":"Fei","year":"2018","journal-title":"Interdiscip. Sci. Comput. Life Sci"},{"key":"2023062707095695100_btaa1015-B14","doi-asserted-by":"crossref","first-page":"3669","DOI":"10.1093\/bioinformatics\/btaa179","article-title":"Apollo: a sequencing-technology-independent, scalable and accurate assembly polishing algorithm","volume":"36","author":"Firtina","year":"2020","journal-title":"Bioinformatics"},{"key":"2023062707095695100_btaa1015-B15","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1147\/JRD.2019.2934048","article-title":"Processing-in-memory: a workload-driven perspective","volume":"63","author":"Ghose","year":"2019","journal-title":"IBM J. Res. Dev"},{"key":"2023062707095695100_btaa1015-B16","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1186\/s12864-018-4460-0","article-title":"GRIM-Filter: fast seed location filtering in DNA read mapping using processing-in-memory technologies","volume":"19","author":"Kim","year":"2018","journal-title":"BMC Genomics"},{"key":"2023062707095695100_btaa1015-B17","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1109\/TCS.1976.1084243","article-title":"Use of Steiner\u2019s problem in suboptimal routing in rectilinear metric","volume":"23","author":"Lee","year":"1976","journal-title":"IEEE Trans. Circuits Syst"},{"key":"2023062707095695100_btaa1015-B18","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Soviet Physics-Doklady"},{"key":"2023062707095695100_btaa1015-B19","doi-asserted-by":"crossref","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","article-title":"Minimap2: pairwise alignment for nucleotide sequences","volume":"34","author":"Li","year":"2018","journal-title":"Bioinformatics"},{"key":"2023062707095695100_btaa1015-B20","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1002\/cpe.3371","article-title":"GSWABE: faster GPU-accelerated sequence alignment with optimal alignment retrieval for short DNA sequences","volume":"27","author":"Liu","year":"2015","journal-title":"Concurr. Comput. Pract. Exp"},{"key":"2023062707095695100_btaa1015-B21","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.micpro.2019.01.009","article-title":"Processing data where it makes sense: enabling in-memory computation","volume":"67","author":"Mutlu","year":"2019","journal-title":"Microproc. Microsyst"},{"key":"2023062707095695100_btaa1015-B22","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1145\/316542.316550","article-title":"A fast bit-vector algorithm for approximate string matching based on dynamic programming","volume":"46","author":"Myers","year":"1999","journal-title":"J. ACM"},{"key":"2023062707095695100_btaa1015-B23","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","article-title":"A guided tour to approximate string matching","volume":"33","author":"Navarro","year":"2001","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"2023062707095695100_btaa1015-B24","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol"},{"key":"2023062707095695100_btaa1015-B25","year":"2019"},{"key":"2023062707095695100_btaa1015-B26","year":"2019"},{"key":"2023062707095695100_btaa1015-B27","doi-asserted-by":"crossref","first-page":"1542","DOI":"10.1093\/bib\/bby017","article-title":"Nanopore sequencing technology and tools for genome assembly: computational analysis of the current state, bottlenecks and future directions","volume":"20","author":"Senol Cali","year":"2019","journal-title":"Brief. Bioinf"},{"key":"2023062707095695100_btaa1015-B28","author":"Senol Cali","year":"2020"},{"key":"2023062707095695100_btaa1015-B0757044","article-title":"Seshadri, V. et al (","year":"2017"},{"key":"2023062707095695100_btaa1015-B30","doi-asserted-by":"crossref","first-page":"1394","DOI":"10.1093\/bioinformatics\/btw753","article-title":"Edlib: a C\/C++ library for fast, exact sequence alignment using edit distance","volume":"33","author":"\u0160o\u0161i\u0107","year":"2017","journal-title":"Bioinformatics"},{"key":"2023062707095695100_btaa1015-B31","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1186\/s12859-018-2014-8","article-title":"Introducing difference recurrence relations for faster semi-global alignment of long sequences","volume":"19","author":"Suzuki","year":"2018","journal-title":"BMC Bioinformatics"},{"key":"2023062707095695100_btaa1015-B32","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/j.compbiolchem.2011.07.006","article-title":"Comparison of linear gap penalties and profile-based variable gap penalties in profile\u2013profile alignments","volume":"35","author":"Wang","year":"2011","journal-title":"Comput. Biol. Chem"},{"key":"2023062707095695100_btaa1015-B33","year":"2013"},{"key":"2023062707095695100_btaa1015-B34","doi-asserted-by":"crossref","first-page":"S13","DOI":"10.1186\/1471-2164-14-S1-S13","article-title":"Accelerating read mapping with FastHASH","volume":"14","author":"Xin","year":"2013","journal-title":"BMC Genomics"},{"key":"2023062707095695100_btaa1015-B35","doi-asserted-by":"crossref","first-page":"1553","DOI":"10.1093\/bioinformatics\/btu856","article-title":"Shifted Hamming distance: a fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping","volume":"31","author":"Xin","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa1015\/35152174\/btaa1015.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/22-23\/5282\/50715957\/btaa1015.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/22-23\/5282\/50715957\/btaa1015.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T07:37:35Z","timestamp":1687851455000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/22-23\/5282\/6033580"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,12,1]]},"references-count":35,"journal-issue":{"issue":"22-23","published-print":{"date-parts":[[2021,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa1015","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,12,1]]},"published":{"date-parts":[[2020,12,1]]}}}