{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,9]],"date-time":"2026-08-09T19:45:28Z","timestamp":1786304728050,"version":"3.56.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T00:00:00Z","timestamp":1675728000000},"content-version":"vor","delay-in-days":6,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovacion","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,2,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Pairwise sequence alignment remains a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies demand faster and scalable algorithms that can cope with the ever-increasing sequence lengths. Classical pairwise alignment algorithms based on dynamic programming are strongly limited by quadratic requirements in time and memory. The recently proposed wavefront alignment algorithm (WFA) introduced an efficient algorithm to perform exact gap-affine alignment in O(ns) time, where s is the optimal score and n is the sequence length. Notwithstanding these bounds, WFA\u2019s O(s2) memory requirements become computationally impractical for genome-scale alignments, leading to a need for further improvement.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>In this article, we present the bidirectional WFA algorithm, the first gap-affine algorithm capable of computing optimal alignments in O(s) memory while retaining WFA\u2019s time complexity of O(ns). As a result, this work improves the lowest known memory bound O(n) to compute gap-affine alignments. In practice, our implementation never requires more than a few hundred MBs aligning noisy Oxford Nanopore Technologies reads up to 1 Mbp long while maintaining competitive execution times.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>All code is publicly available at https:\/\/github.com\/smarco\/BiWFA-paper.<\/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\/btad074","type":"journal-article","created":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T13:57:00Z","timestamp":1675778220000},"source":"Crossref","is-referenced-by-count":64,"title":["Optimal gap-affine alignment in\n                    <i>O<\/i>\n                    (\n                    <i>s<\/i>\n                    ) space"],"prefix":"10.1093","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7951-3914","authenticated-orcid":false,"given":"Santiago","family":"Marco-Sola","sequence":"first","affiliation":[{"name":"Computer Sciences Department, 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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8345-8356","authenticated-orcid":false,"given":"Jordan M","family":"Eizenga","sequence":"additional","affiliation":[{"name":"Genomics Institute, University of California Santa Cruz , Santa Cruz, CA 95064, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9744-131X","authenticated-orcid":false,"given":"Andrea","family":"Guarracino","sequence":"additional","affiliation":[{"name":"Genomics Research Centre, Human Technopole , Milan 20157, Italy"},{"name":"Department of Genetics, Genomics and Informatics, University of Tennessee Health Science Center , Memphis, TN 38163, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8863-3539","authenticated-orcid":false,"given":"Benedict","family":"Paten","sequence":"additional","affiliation":[{"name":"Genomics Institute, University of California Santa Cruz , Santa Cruz, CA 95064, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3821-631X","authenticated-orcid":false,"given":"Erik","family":"Garrison","sequence":"additional","affiliation":[{"name":"Department of Genetics, Genomics and Informatics, University of Tennessee Health Science Center , Memphis, TN 38163, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9848-8758","authenticated-orcid":false,"given":"Miquel","family":"Moreto","sequence":"additional","affiliation":[{"name":"Computer Sciences Department, 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"}]}],"member":"286","published-online":{"date-parts":[[2023,2,7]]},"reference":[{"key":"2023060913400780000_btad074-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol"},{"key":"2023060913400780000_btad074-B2","doi-asserted-by":"crossref","first-page":"1869","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":"2023060913400780000_btad074-B3","doi-asserted-by":"crossref","first-page":"1","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 Bioinf"},{"key":"2023060913400780000_btad074-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","author":"Daily","year":"2015","journal-title":"J. Parallel Distributed Comput"},{"key":"2023060913400780000_btad074-B5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023060913400780000_btad074-B6","author":"Eizenga","year":"2022"},{"key":"2023060913400780000_btad074-B7","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":"2023060913400780000_btad074-B8","author":"Garrison","year":"2012"},{"key":"2023060913400780000_btad074-B9","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. Mol. Biol"},{"key":"2023060913400780000_btad074-B10","volume-title":"An Introduction to Bioinformatics Algorithms","author":"Jones","year":"2004"},{"key":"2023060913400780000_btad074-B11","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1101\/gr.113985.110","article-title":"Adaptive seeds tame genomic sequence comparison","volume":"21","author":"Kie\u0142basa","year":"2011","journal-title":"Genome Res"},{"key":"2023060913400780000_btad074-B12","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1101\/gr.215087.116","article-title":"CANU: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation","volume":"27","author":"Koren","year":"2017","journal-title":"Genome Res"},{"key":"2023060913400780000_btad074-B13","author":"Li","year":"2013"},{"key":"2023060913400780000_btad074-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":"2023060913400780000_btad074-B15","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":"2023060913400780000_btad074-B16","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":"2023060913400780000_btad074-B17","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1093\/bioinformatics\/btaa777","article-title":"Fast gap-affine pairwise alignment using the wavefront algorithm","volume":"37","author":"Marco-Sola","year":"2021","journal-title":"Bioinformatics"},{"key":"2023060913400780000_btad074-B18","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1101\/gr.107524.110","article-title":"The genome analysis toolkit: a mapreduce framework for analyzing next-generation DNA sequencing data","volume":"20","author":"McKenna","year":"2010","journal-title":"Genome Res"},{"key":"2023060913400780000_btad074-B19","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1146\/annurev-genom-120120-081921","article-title":"The need for a human pangenome reference sequence","volume":"22","author":"Miga","year":"2021","journal-title":"Annu. Rev. Genomics Hum. Genet"},{"key":"2023060913400780000_btad074-B20","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01840446","article-title":"An O(ND) difference algorithm and its variations","volume":"1","author":"Myers","year":"1986","journal-title":"Algorithmica"},{"key":"2023060913400780000_btad074-B21","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1093\/bioinformatics\/4.1.11","article-title":"Optimal alignments in linear space","volume":"4","author":"Myers","year":"1988","journal-title":"Bioinformatics"},{"key":"2023060913400780000_btad074-B22","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":"2023060913400780000_btad074-B23","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":"2023060913400780000_btad074-B24","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/s12864-016-3404-9","article-title":"Chimpipe: accurate detection of fusion genes and transcription-induced chimeras from RNA-seq data","volume":"18","author":"Rodr\u00edguez-Mart\u00edn","year":"2017","journal-title":"BMC Genomics"},{"key":"2023060913400780000_btad074-B25","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":"2023060913400780000_btad074-B26","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":"2023060913400780000_btad074-B27","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1016\/0196-8858(81)90046-4","article-title":"Comparison of biosequences","volume":"2","author":"Smith","year":"1981","journal-title":"Adv. Appl. Math"},{"key":"2023060913400780000_btad074-B28","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":"2023060913400780000_btad074-B29","author":"Suzuki","year":"2017"},{"key":"2023060913400780000_btad074-B30","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":"2023060913400780000_btad074-B31","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":"2023060913400780000_btad074-B32","first-page":"1","article-title":"A review of parallel implementations for the Smith\u2013Waterman algorithm","author":"Xia","year":"2021","journal-title":"Interdisciplinary Sciences: Computational Life Sciences"},{"key":"2023060913400780000_btad074-B33","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1089\/10665270050081478","article-title":"A greedy algorithm for aligning DNA sequences","volume":"7","author":"Zhang","year":"2000","journal-title":"J. Comput. Biol"},{"key":"2023060913400780000_btad074-B34","doi-asserted-by":"crossref","first-page":"e82138","DOI":"10.1371\/journal.pone.0082138","article-title":"SSW library: an SIMD Smith\u2013Waterman 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":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad074\/49117986\/btad074.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/2\/btad074\/50530586\/btad074.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/2\/btad074\/50530586\/btad074.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T10:41:22Z","timestamp":1686307282000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad074\/7030690"}},"subtitle":[],"editor":[{"given":"Pier Luigi","family":"Martelli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2023,2,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2,3]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad074","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2022.04.14.488380","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,2,1]]},"published":{"date-parts":[[2023,2,1]]},"article-number":"btad074"}}