{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:31Z","timestamp":1772138071351,"version":"3.50.1"},"reference-count":51,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:00:00Z","timestamp":1741824000000},"content-version":"vor","delay-in-days":12,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","award":["MCIN\/AEI\/10.13039\/501100011033"],"award-info":[{"award-number":["MCIN\/AEI\/10.13039\/501100011033"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","award":["PID2019-107255GB-C21"],"award-info":[{"award-number":["PID2019-107255GB-C21"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","award":["PID2020-113614RB-C21"],"award-info":[{"award-number":["PID2020-113614RB-C21"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","award":["TED2021-132634A-I00"],"award-info":[{"award-number":["TED2021-132634A-I00"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Pairwise sequence alignment is a core component of multiple sequencing-data analysis tools. Recent advancements in sequencing technologies have enabled the generation of longer sequences at a much lower price. Thus, long-read sequencing technologies have become increasingly popular in sequencing-based studies. However, classical sequence analysis algorithms face significant scalability challenges when aligning long sequences. As a result, several heuristic methods have been developed to improve performance at the expense of accuracy, as they often fail to produce the optimal alignment.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>This paper introduces QuickEd, a sequence alignment algorithm based on a bound-and-align strategy. First, QuickEd effectively bounds the maximum alignment-score using efficient heuristic strategies. Then, QuickEd utilizes this bound to reduce the computations required to produce the optimal alignment. Compared to O(n2) complexity of traditional dynamic programming algorithms, QuickEd\u2019s bound-and-align strategy achieves O(ns^) complexity, where n is the sequence length and s^ is an estimated upper bound of the alignment-score between the sequences. As a result, QuickEd is consistently faster than other state-of-the-art implementations, such as Edlib and BiWFA, achieving performance speedups of 4.2\u22125.9\u00d7 and 3.8\u22124.4\u00d7, respectively, aligning long and noisy datasets. In addition, QuickEd maintains a stable memory footprint below 35 MB while aligning sequences up to 1 Mbp.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>QuickEd code and documentation are publicly available at https:\/\/github.com\/maxdoblas\/QuickEd.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf112","type":"journal-article","created":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T16:19:00Z","timestamp":1741623540000},"source":"Crossref","is-referenced-by-count":3,"title":["QuickEd: high-performance exact sequence alignment based on bound-and-align"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8909-3033","authenticated-orcid":false,"given":"Max","family":"Doblas","sequence":"first","affiliation":[{"name":"Computer Sciences Department, Barcelona Supercomputing Center , Barcelona 08034,","place":["Spain"]},{"name":"Department of Computer Architecture, Universitat Polit\u00e8cnica de Catalunya Barcelona 08034,","place":["Spain"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5166-3806","authenticated-orcid":false,"given":"Oscar","family":"Lostes-Cazorla","sequence":"additional","affiliation":[{"name":"Computer Sciences Department, Barcelona Supercomputing Center , Barcelona 08034,","place":["Spain"]},{"name":"Department of Electronic Engineering, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4871-3192","authenticated-orcid":false,"given":"Quim","family":"Aguado-Puig","sequence":"additional","affiliation":[{"name":"Computer Sciences Department, Barcelona Supercomputing Center , Barcelona 08034,","place":["Spain"]},{"name":"Department of Electronic Engineering, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]},{"name":"Department of Computer Architecture and Operative Systems, Universitat Aut\u00f2noma de Barcelona , Barcelona 08193,","place":["Spain"]}]},{"given":"Cristian","family":"I\u00f1iguez","sequence":"additional","affiliation":[{"name":"Computer Sciences Department, Barcelona Supercomputing Center , Barcelona 08034,","place":["Spain"]}]},{"given":"Miquel","family":"Moreto","sequence":"additional","affiliation":[{"name":"Computer Sciences Department, Barcelona Supercomputing Center , Barcelona 08034,","place":["Spain"]},{"name":"Department of Computer Architecture, Universitat Polit\u00e8cnica de Catalunya Barcelona 08034,","place":["Spain"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7951-3914","authenticated-orcid":false,"given":"Santiago","family":"Marco-Sola","sequence":"additional","affiliation":[{"name":"Computer Sciences Department, Barcelona Supercomputing Center , Barcelona 08034,","place":["Spain"]},{"name":"Department of Computer Science, Universitat Polit\u00e8cnica de Catalunya , Barcelona 08034,","place":["Spain"]}]}],"member":"286","published-online":{"date-parts":[[2025,3,13]]},"reference":[{"key":"2025032802555228000_btaf112-B1","doi-asserted-by":"crossref","first-page":"btad701","DOI":"10.1093\/bioinformatics\/btad701","article-title":"WFA-GPU: gap-affine pairwise read-alignment using GPUS","volume":"39","author":"Aguado-Puig","year":"2023","journal-title":"Bioinformatics"},{"key":"2025032802555228000_btaf112-B2","doi-asserted-by":"crossref","first-page":"63782","DOI":"10.1109\/ACCESS.2022.3182714","article-title":"Accelerating edit-distance sequence alignment on gpu using the wavefront algorithm","volume":"10","author":"Aguado-Puig","year":"2022","journal-title":"IEEE Access"},{"key":"2025032802555228000_btaf112-B3","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1186\/s12859-019-3086-9","article-title":"Gasal2: a GPU accelerated sequence alignment library for high-throughput NGS data","volume":"20","author":"Ahmed","year":"2019","journal-title":"BMC Bioinformatics"},{"key":"2025032802555228000_btaf112-B4","doi-asserted-by":"crossref","first-page":"btae631","DOI":"10.1093\/bioinformatics\/btae631","article-title":"Bimsa: accelerating long sequence alignment using processing-in-memory","volume":"40","author":"Alonso-Mar\u00edn","year":"2024","journal-title":"Bioinformatics"},{"key":"2025032802555228000_btaf112-B5","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":"2025032802555228000_btaf112-B6","doi-asserted-by":"crossref","first-page":"5282","DOI":"10.1093\/bioinformatics\/btaa1015","article-title":"Sneakysnake: a fast and accurate universal genome pre-alignment filter for CPUS, GPUS and FPGAS","volume":"36","author":"Alser","year":"2021","journal-title":"Bioinformatics"},{"key":"2025032802555228000_btaf112-B7","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","article-title":"A new approach to text searching","volume":"35","author":"Baeza-Yates","year":"1992","journal-title":"Commun ACM"},{"key":"2025032802555228000_btaf112-B8","first-page":"951","author":"Cali","year":"2020"},{"key":"2025032802555228000_btaf112-B9","doi-asserted-by":"crossref","first-page":"22079","DOI":"10.1109\/ACCESS.2022.3153032","article-title":"FPGA acceleration of pre-alignment filters for short read mapping with HLS","volume":"10","author":"Castells-Rufas","year":"2022","journal-title":"IEEE Access"},{"key":"2025032802555228000_btaf112-B10","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":"2025032802555228000_btaf112-B11","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":"2025032802555228000_btaf112-B12","first-page":"1466","author":"Doblas","year":"2023"},{"key":"2025032802555228000_btaf112-B13","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/1471-2105-9-11","article-title":"SEQAN an efficient, generic C++ library for sequence analysis","volume":"9","author":"D\u00f6ring","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2025032802555228000_btaf112-B14","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":"2025032802555228000_btaf112-B15","doi-asserted-by":"crossref","first-page":"1159","DOI":"10.1038\/nmeth.2256","article-title":"Gem: crystal-clear DNA alignment","volume":"9","author":"Faust","year":"2012","journal-title":"Nat Methods"},{"key":"2025032802555228000_btaf112-B16","author":"Groot Koerkamp","year":"2024"},{"key":"2025032802555228000_btaf112-B17","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/btae032","article-title":"Exact global alignment using a with chaining seed heuristic and match pruning","volume":"40","author":"Groot Koerkamp","year":"2024","journal-title":"Bioinformatics"},{"key":"2025032802555228000_btaf112-B18","first-page":"263","article-title":"Minimum detour methods for string or sequence comparison","volume":"61","author":"Hadlock","year":"1988","journal-title":"Congressus Numerantium"},{"key":"2025032802555228000_btaf112-B19","first-page":"392","author":"Haghi","year":"2023"},{"key":"2025032802555228000_btaf112-B20","first-page":"151","author":"Haghi","year":"2021"},{"key":"2025032802555228000_btaf112-B21","doi-asserted-by":"crossref","first-page":"giz125","DOI":"10.1093\/gigascience\/giz125","article-title":"Chromosome-scale assembly comparison of the Korean reference genome KOREF from Promethion and Pacbio with HI-C mapping information","volume":"8","author":"Kim","year":"2019","journal-title":"Gigascience"},{"key":"2025032802555228000_btaf112-B22","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":"2025032802555228000_btaf112-B23","author":"Li","year":"2013"},{"key":"2025032802555228000_btaf112-B24","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":"2025032802555228000_btaf112-B25","doi-asserted-by":"crossref","first-page":"btad151","DOI":"10.1093\/bioinformatics\/btad151","article-title":"Scrooge: a fast and memory-frugal genomic sequence aligner for CPUS, GPUS, and ASICS","volume":"39","author":"Lindegger","year":"2023","journal-title":"Bioinformatics"},{"key":"2025032802555228000_btaf112-B26","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1186\/s12864-024-10440-w","article-title":"Sequencing accuracy and systematic errors of nanopore direct RNA sequencing","volume":"25","author":"Liu-Wei","year":"2024","journal-title":"BMC Genomics"},{"key":"2025032802555228000_btaf112-B27","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/j.future.2024.03.050","article-title":"Genarchbench: a genomics benchmark suite for ARM HPC processors","volume":"157","author":"L\u00f3pez-Villellas","year":"2024","journal-title":"Fut Generat Comput Syst"},{"key":"2025032802555228000_btaf112-B28","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":"2025032802555228000_btaf112-B29","doi-asserted-by":"crossref","first-page":"btad074","DOI":"10.1093\/bioinformatics\/btad074","article-title":"Optimal gap-affine alignment in O (S) space","volume":"39","author":"Marco-Sola","year":"2023","journal-title":"Bioinformatics"},{"key":"2025032802555228000_btaf112-B30","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":"2025032802555228000_btaf112-B31","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/0471250953.bi1113s50","article-title":"Efficient alignment of illumina-like high-throughput sequencing reads with the genomic multi-tool (gem) mapper","volume":"50","author":"Marco-Sola","year":"2015","journal-title":"Curr Protoc Bioinf"},{"key":"2025032802555228000_btaf112-B32","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":"2025032802555228000_btaf112-B33","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":"2025032802555228000_btaf112-B34","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":"2025032802555228000_btaf112-B35","first-page":"52","author":"Myers","year":"2014"},{"key":"2025032802555228000_btaf112-B36","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"},{"key":"2025032802555228000_btaf112-B37","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":"2025032802555228000_btaf112-B38","doi-asserted-by":"crossref","first-page":"2534","DOI":"10.1093\/bioinformatics\/btq485","article-title":"Gassst: global alignment short sequence search tool","volume":"26","author":"Rizk","year":"2010","journal-title":"Bioinformatics"},{"key":"2025032802555228000_btaf112-B39","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":"2025032802555228000_btaf112-B40","author":"Schmidt","year":"2023"},{"key":"2025032802555228000_btaf112-B41","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":"2025032802555228000_btaf112-B42","first-page":"254","author":"Soria-Pardos","year":"2022"},{"key":"2025032802555228000_btaf112-B43","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":"2025032802555228000_btaf112-B44","author":"Suzuki","year":"2017"},{"key":"2025032802555228000_btaf112-B45","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":"2025032802555228000_btaf112-B46","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1145\/3296957.3173193","article-title":"Darwin: a genomics co-processor provides up to 15,000 x acceleration on long read assembly","volume":"53","author":"Turakhia","year":"2018","journal-title":"SIGPLAN Not"},{"key":"2025032802555228000_btaf112-B47","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":"2025032802555228000_btaf112-B48","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","article-title":"Finding approximate patterns in strings","volume":"6","author":"Ukkonen","year":"1985","journal-title":"J Algorithms"},{"key":"2025032802555228000_btaf112-B49","doi-asserted-by":"crossref","first-page":"1348","DOI":"10.1038\/s41587-021-01108-x","article-title":"Nanopore sequencing technology, bioinformatics and applications","volume":"39","author":"Wang","year":"2021","journal-title":"Nat Biotechnol"},{"key":"2025032802555228000_btaf112-B50","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"},{"key":"2025032802555228000_btaf112-B51","doi-asserted-by":"crossref","first-page":"2306","DOI":"10.1093\/bioinformatics\/bty930","article-title":"BGSA: a bit-parallel global sequence alignment toolkit for multi-core and many-core architectures","volume":"35","author":"Zhang","year":"2019","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaf112\/62402837\/btaf112.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/3\/btaf112\/62402837\/btaf112.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/3\/btaf112\/62402837\/btaf112.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T16:55:08Z","timestamp":1743353708000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btaf112\/8075120"}},"subtitle":[],"editor":[{"given":"Can","family":"Alkan","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3,4]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf112","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2024.09.13.612714","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,3]]},"published":{"date-parts":[[2025,3]]},"article-number":"btaf112"}}