{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T01:55:02Z","timestamp":1780624502671,"version":"3.54.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T00:00:00Z","timestamp":1599782400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Pairwise alignment of sequences is a fundamental method in modern molecular biology, implemented within multiple bioinformatics tools and libraries. Current advances in sequencing technologies press for the development of faster pairwise alignment algorithms that can scale with increasing read lengths and production yields.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this article, we present the wavefront alignment algorithm (WFA), an exact gap-affine algorithm that takes advantage of homologous regions between the sequences to accelerate the alignment process. As opposed to traditional dynamic programming algorithms that run in quadratic time, the WFA runs in time O(ns), proportional to the read length n and the alignment score s, using O(s2) memory. Furthermore, our algorithm exhibits simple data dependencies that can be easily vectorized, even by the automatic features of modern compilers, for different architectures, without the need to adapt the code. We evaluate the performance of our algorithm, together with other state-of-the-art implementations. As a result, we demonstrate that the WFA runs 20\u2013300\u00d7 faster than other methods aligning short Illumina-like sequences, and 10\u2013100\u00d7 faster using long noisy reads like those produced by Oxford Nanopore Technologies.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The WFA algorithm is implemented within the wavefront-aligner library, and it is publicly available at https:\/\/github.com\/smarco\/WFA.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa777","type":"journal-article","created":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T19:46:28Z","timestamp":1598989588000},"page":"456-463","source":"Crossref","is-referenced-by-count":159,"title":["Fast gap-affine pairwise alignment using the wavefront algorithm"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7951-3914","authenticated-orcid":false,"given":"Santiago","family":"Marco-Sola","sequence":"first","affiliation":[{"name":"Department of Computer Sciences, Barcelona Supercomputing Center , Barcelona 08034, Spain"},{"name":"Departament d\u2019Arquitectura de Computadors i Sistemes Operatius, Universitat Aut\u00f2noma de Barcelona , Barcelona 08193, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan Carlos","family":"Moure","sequence":"additional","affiliation":[{"name":"Departament d\u2019Arquitectura de Computadors i Sistemes Operatius, Universitat Aut\u00f2noma de Barcelona , Barcelona 08193, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miquel","family":"Moreto","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, Barcelona Supercomputing Center , Barcelona 08034, Spain"},{"name":"Departament d\u2019Arquitectura de Computadors, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antonio","family":"Espinosa","sequence":"additional","affiliation":[{"name":"Departament d\u2019Arquitectura de Computadors i Sistemes Operatius, Universitat Aut\u00f2noma de Barcelona , Barcelona 08193, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,9,11]]},"reference":[{"key":"2023051706071574900_btaa777-B1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-019-09637-5","article-title":"Sequencing of human genomes with nanopore technology","volume":"10","author":"Bowden","year":"2019","journal-title":"Nat. Commun"},{"key":"2023051706071574900_btaa777-B2","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/2597652.2597677","author":"Chac\u00f3n","year":"2014"},{"key":"2023051706071574900_btaa777-B3","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":"2023051706071574900_btaa777-B4","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.jpdc.2014.08.009","article-title":"A work stealing based approach for enabling scalable optimal sequence homology detection","volume":"79-80","author":"Daily","year":"2015","journal-title":"J. Parallel Distrib. Comput"},{"key":"2023051706071574900_btaa777-B5","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1038\/ng.806","article-title":"A framework for variation discovery and genotyping using next-generation DNA sequencing data","volume":"43","author":"DePristo","year":"2011","journal-title":"Nat. Genet"},{"key":"2023051706071574900_btaa777-B6","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","article-title":"Striped smith\u2013waterman speeds database searches six times over other SIMD implementations","volume":"23","author":"Farrar","year":"2007","journal-title":"Bioinformatics"},{"key":"2023051706071574900_btaa777-B7","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J.\u00a0Mol. Biol"},{"key":"2023051706071574900_btaa777-B8","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF02458577","article-title":"Optimal sequence alignment allowing for long gaps","volume":"52","author":"Gotoh","year":"1990","journal-title":"Bull. Math. Biol"},{"key":"2023051706071574900_btaa777-B9","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/270563.571472","article-title":"Algorithms on stings, trees, and sequences: computer science and computational biology","volume":"28","author":"Gusfield","year":"1997","journal-title":"ACM Sigact News"},{"key":"2023051706071574900_btaa777-B10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/IDT.2008.4802483","author":"Hasan","year":"2008"},{"key":"2023051706071574900_btaa777-B11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","article-title":"Fast parallel and serial approximate string matching","volume":"10","author":"Landau","year":"1989","journal-title":"J. Algorithms"},{"key":"2023051706071574900_btaa777-B12","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"2023051706071574900_btaa777-B13","author":"Li","year":"2013"},{"key":"2023051706071574900_btaa777-B14","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":"2023051706071574900_btaa777-B15","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1186\/1471-2105-8-185","article-title":"160-fold acceleration of the smith-waterman algorithm using a field programmable gate array (FPGA)","volume":"8","author":"Li","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023051706071574900_btaa777-B16","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1186\/1471-2105-14-117","article-title":"Cudasw++ 3.0: accelerating smith-waterman protein database search by coupling CPU and GPU SIMD instructions","volume":"14","author":"Liu","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023051706071574900_btaa777-B17","first-page":"257","author":"Liu","year":"2014"},{"key":"2023051706071574900_btaa777-B18","doi-asserted-by":"crossref","first-page":"3166","DOI":"10.1093\/bioinformatics\/btu507","article-title":"BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm","volume":"30","author":"Loving","year":"2014","journal-title":"Bioinformatics"},{"key":"2023051706071574900_btaa777-B19","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1038\/nmeth.2221","article-title":"The gem mapper: fast, accurate and versatile alignment by filtration","volume":"9","author":"Marco-Sola","year":"2012","journal-title":"Nat. Methods"},{"key":"2023051706071574900_btaa777-B20","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0092-8240(88)80016-8","article-title":"Sequence comparison with concave weighting functions","volume":"50","author":"Miller","year":"1988","journal-title":"Bull. Math. Biol"},{"key":"2023051706071574900_btaa777-B21","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01840446","article-title":"Ano (nd) difference algorithm and its variations","volume":"1","author":"Myers","year":"1986","journal-title":"Algorithmica"},{"key":"2023051706071574900_btaa777-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 (JACM)"},{"key":"2023051706071574900_btaa777-B23","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/978-3-662-44753-6_5","volume-title":"International Workshop on Algorithms in Bioinformatics","author":"Myers","year":"2014"},{"key":"2023051706071574900_btaa777-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":"2023051706071574900_btaa777-B25","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-coffee: a novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol"},{"key":"2023051706071574900_btaa777-B26","doi-asserted-by":"crossref","first-page":"3437","DOI":"10.1093\/bioinformatics\/bty380","article-title":"Generic accelerated sequence alignment in SeqAn using vectorization and multi-threading","volume":"34","author":"Rahn","year":"2018","journal-title":"Bioinformatics"},{"key":"2023051706071574900_btaa777-B27","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1093\/bioinformatics\/16.8.699","article-title":"Six-fold speed-up of Smith\u2013Waterman sequence database searches using parallel processing on common microprocessors","volume":"16","author":"Rognes","year":"2000","journal-title":"Bioinformatics"},{"key":"2023051706071574900_btaa777-B28","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1101\/gr.089532.108","article-title":"ABySS: a parallel assembler for short read sequence data","volume":"19","author":"Simpson","year":"2009","journal-title":"Genome Res"},{"key":"2023051706071574900_btaa777-B29","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":"2023051706071574900_btaa777-B30","first-page":"130633","author":"Suzuki","year":"2017"},{"key":"2023051706071574900_btaa777-B31","doi-asserted-by":"crossref","first-page":"45","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":"2023051706071574900_btaa777-B32","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1186\/1756-0500-1-107","article-title":"SWPS3 \u2013 fast multi-threaded vectorized Smith-Waterman for IBM cell\/BE and \u00d786\/SSE2","volume":"1","author":"Szalkowski","year":"2008","journal-title":"BMC Res. Notes"},{"key":"2023051706071574900_btaa777-B33","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","article-title":"Algorithms for approximate string matching","volume":"64","author":"Ukkonen","year":"1985","journal-title":"Inf. Control"},{"key":"2023051706071574900_btaa777-B34","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1093\/bioinformatics\/13.2.145","article-title":"Using video-oriented instructions to speed up sequence comparison","volume":"13","author":"Wozniak","year":"1997","journal-title":"Bioinformatics"},{"key":"2023051706071574900_btaa777-B35","doi-asserted-by":"crossref","first-page":"e82138","DOI":"10.1371\/journal.pone.0082138","article-title":"SSW library: an SIMD Smith-Waterman C\/C++ library for use in genomic applications","volume":"8","author":"Zhao","year":"2013","journal-title":"PLoS One"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa777\/33736224\/btaa777.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/4\/456\/50359789\/btaa777.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/4\/456\/50359789\/btaa777.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T06:14:32Z","timestamp":1684304072000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/4\/456\/5904262"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2020,9,11]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa777","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,2,15]]},"published":{"date-parts":[[2020,9,11]]}}}