{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T04:12:13Z","timestamp":1779336733333,"version":"3.51.4"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T00:00:00Z","timestamp":1776211200000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Spanish Ministry of Science, Innovation and Universities","award":["MICIU\/AEI\/10.13039\/501100011033"],"award-info":[{"award-number":["MICIU\/AEI\/10.13039\/501100011033"]}]},{"name":"Spanish Ministry of Science, Innovation and Universities","award":["PID2020-113614RB-C21"],"award-info":[{"award-number":["PID2020-113614RB-C21"]}]},{"name":"Spanish Ministry of Science, Innovation and Universities","award":["PID2022-136454NB C22"],"award-info":[{"award-number":["PID2022-136454NB C22"]}]},{"name":"Spanish Ministry of Science, Innovation and Universities","award":["PID2023-146193OB-I00"],"award-info":[{"award-number":["PID2023-146193OB-I00"]}]},{"name":"Spanish Ministry of Science, Innovation and Universities","award":["PID2023-146511NB-I00"],"award-info":[{"award-number":["PID2023-146511NB-I00"]}]},{"name":"Spanish Ministry of Science, Innovation and Universities","award":["CNS2025-166442"],"award-info":[{"award-number":["CNS2025-166442"]}]},{"name":"Generalitat de Catalunya GenCat-DIUiE","award":["2021-SGR-00763"],"award-info":[{"award-number":["2021-SGR-00763"]}]},{"name":"Generalitat de Catalunya GenCat-DIUiE","award":["2021-SGR-00574"],"award-info":[{"award-number":["2021-SGR-00574"]}]},{"DOI":"10.13039\/501100010067","name":"Gobierno de Arag\u00f3n","doi-asserted-by":"publisher","award":["E45_20R T58_23R"],"award-info":[{"award-number":["E45_20R T58_23R"]}],"id":[{"id":"10.13039\/501100010067","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Arm-BSC Center of Excellence"},{"name":"Lenovo-BSC Contract-Framework Contract"},{"name":"Ministry for Digital Transformation and the Civil Service"},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"name":"State Secretariat for Telecommunications and Digital Infrastructures"},{"name":"European Union - Next Generation EU","award":["TSI-069100-2023-0015"],"award-info":[{"award-number":["TSI-069100-2023-0015"]}]},{"name":"European Union\u2019s Horizon Europe"},{"name":"STRATUM","award":["101137416"],"award-info":[{"award-number":["101137416"]}]},{"name":"Barcelona Zettascale Laboratory"},{"name":"Ministry for Digital Transformation and of Public Services"},{"name":"European Union\u2014NextGenerationEU"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,5,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Advances in DNA sequencing have outpaced advances in computation, making sequence alignment a major bottleneck in genome data analyses. Classical dynamic programming (DP) algorithms are particularly memory-intensive, especially when computing gap-affine and dual gap-affine alignments. Existing strategies to reduce memory consumption often sacrifice speed or alignment accuracy.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We present Singletrack, an efficient algorithm for backtrace gap-affine and dual gap-affine alignments that requires storing a single DP matrix while preserving optimal alignment results. Compared to classical DP algorithms, Singletrack removes the need to store additional matrices (i.e. 2 for gap-affine and 4 for dual gap-affine), significantly reducing memory consumption and, in turn, reducing pressure on the memory hierarchy and improving overall performance. Most importantly, Singletrack is a general backtrace method compatible with state-of-the-art DP-based algorithms and heuristics, such as the Suzuki-Kasahara (SK) and the Wavefront Alignment (WFA) algorithms. We demonstrate that Singletrack reduces memory consumption for both SK and WFA algorithms, lowering SK usage by 2\u00d7 and 4\u00d7 and WFA usage by 3\u00d7 and 5\u00d7 for gap-affine and dual gap-affine alignments, respectively. Moreover, replacing KSW2\u2019s memory-reduction technique with Singletrack accelerates its SK implementation by up to 1.4\u00d7 at the cost of doubling memory consumption, while Singletrack increases the performance of the WFA implementation in WFA2-lib by 1.2\u20132.1\u00d7. Compared to the efficient linear-memory BiWFA algorithm, the Singletrack-accelerated version of WFA trades a practical increase in memory usage for up to 5.2\u00d7 higher performance.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>The Singletrack implementations presented in this work are available on Zenodo (DOI: 10.5281\/zenodo.18770585) and GitHub (https:\/\/github.com\/LorienLV\/singletrack).<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btag183","type":"journal-article","created":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T11:46:56Z","timestamp":1775821616000},"source":"Crossref","is-referenced-by-count":0,"title":["Singletrack: an algorithm for improving memory consumption and performance of gap-affine sequence alignment"],"prefix":"10.1093","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1891-4359","authenticated-orcid":false,"given":"Lori\u00e9n","family":"L\u00f3pez-Villellas","sequence":"first","affiliation":[{"name":"Departamento de Inform\u00e1tica e Ingenier\u00eda de Sistemas\/Arag\u00f3n Institute for Engineering Research (I3A), Universidad de Zaragoza , Zaragoza, 50018,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8950-2776","authenticated-orcid":false,"given":"Cristian","family":"I\u00f1iguez","sequence":"additional","affiliation":[{"name":"Barcelona Supercomputing Center , Barcelona, 08034,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3958-9664","authenticated-orcid":false,"given":"Albert","family":"Jim\u00e9nez-Blanco","sequence":"additional","affiliation":[{"name":"Barcelona Supercomputing Center , Barcelona, 08034,","place":["Spain"]},{"name":"Department of Computer Science, Universitat Polit\u00e8cnica de Catalunya , Barcelona, 08034,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4871-3192","authenticated-orcid":false,"given":"Quim","family":"Aguado-Puig","sequence":"additional","affiliation":[{"name":"Departament d\u2019Arquitectura de Computadors i Sistemes Operatius, Universitat Aut\u00f2noma de Barcelona , Barcelona, 08193,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9848-8758","authenticated-orcid":false,"given":"Miquel","family":"Moret\u00f3","sequence":"additional","affiliation":[{"name":"Barcelona Supercomputing Center , Barcelona, 08034,","place":["Spain"]},{"name":"Department of Computer Science, Universitat Polit\u00e8cnica de Catalunya , Barcelona, 08034,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4164-5078","authenticated-orcid":false,"given":"Jes\u00fas","family":"Alastruey-Bened\u00e9","sequence":"additional","affiliation":[{"name":"Departamento de Inform\u00e1tica e Ingenier\u00eda de Sistemas\/Arag\u00f3n Institute for Engineering Research (I3A), Universidad de Zaragoza , Zaragoza, 50018,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5916-7898","authenticated-orcid":false,"given":"Pablo","family":"Ib\u00e1\u00f1ez","sequence":"additional","affiliation":[{"name":"Departamento de Inform\u00e1tica e Ingenier\u00eda de Sistemas\/Arag\u00f3n Institute for Engineering Research (I3A), Universidad de Zaragoza , Zaragoza, 50018,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7951-3914","authenticated-orcid":false,"given":"Santiago","family":"Marco-Sola","sequence":"additional","affiliation":[{"name":"Barcelona Supercomputing Center , Barcelona, 08034,","place":["Spain"]},{"name":"Department of Computer Science, Universitat Polit\u00e8cnica de Catalunya , Barcelona, 08034,","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2026,4,13]]},"reference":[{"key":"2026052023582176600_btag183-B1","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":"2026052023582176600_btag183-B2","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1186\/s13059-021-02443-7","article-title":"Technology dictates algorithms: recent developments in read alignment","volume":"22","author":"Alser","year":"2021","journal-title":"Genome Biol"},{"key":"2026052023582176600_btag183-B3","doi-asserted-by":"crossref","first-page":"4579","DOI":"10.1016\/j.csbj.2022.08.019","article-title":"From molecules to genomic variations: accelerating genome analysis via intelligent algorithms and architectures","volume":"20","author":"Alser","year":"2022","journal-title":"Comput Struct Biotechnol J"},{"key":"2026052023582176600_btag183-B4","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped blast and psi-blast: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res"},{"key":"2026052023582176600_btag183-B5","first-page":"1209","article-title":"On economical construction of the transitive closure of a directed graph","volume":"194","author":"Arlazarov","year":"1970","journal-title":"In Dokl Akad Nauk SSSR"},{"key":"2026052023582176600_btag183-B6","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":"2026052023582176600_btag183-B7","doi-asserted-by":"crossref","first-page":"2008","DOI":"10.1038\/s41592-024-02430-3","article-title":"Building pangenome graphs","volume":"21","author":"Garrison","year":"2024","journal-title":"Nat Methods"},{"key":"2026052023582176600_btag183-B8","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1038\/nrg.2016.49","article-title":"Coming of age: ten years of next-generation sequencing technologies","volume":"17","author":"Goodwin","year":"2016","journal-title":"Nat Rev Genet"},{"key":"2026052023582176600_btag183-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":"2026052023582176600_btag183-B10","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":"2026052023582176600_btag183-B11","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","article-title":"A linear space algorithm for computing maximal common subsequences","volume":"18","author":"Hirschberg","year":"1975","journal-title":"Commun ACM"},{"key":"2026052023582176600_btag183-B12","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1038\/nbt.4060","article-title":"Nanopore sequencing and assembly of a human genome with ultra-long reads","volume":"36","author":"Jain","year":"2018","journal-title":"Nat Biotechnol"},{"key":"2026052023582176600_btag183-B13","doi-asserted-by":"crossref","DOI":"10.64898\/2026.02.12.705572","article-title":"Theseus: fast and optimal affine-gap sequence-to-graph alignment","author":"Jim\u00e9nez-Blanco","year":"2026"},{"key":"2026052023582176600_btag183-B14","author":"Li","year":"2013"},{"key":"2026052023582176600_btag183-B15","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","article-title":"Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2026052023582176600_btag183-B16","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":"2026052023582176600_btag183-B17","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/s40484-019-0166-9","article-title":"Current challenges and solutions of de novo assembly","volume":"7","author":"Liao","year":"2019","journal-title":"Quant Biol"},{"key":"2026052023582176600_btag183-B18","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":"2026052023582176600_btag183-B19","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":"2026052023582176600_btag183-B20","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":"2026052023582176600_btag183-B21","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":"2026052023582176600_btag183-B23","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1038\/hdy.2016.102","article-title":"From next-generation resequencing reads to a high-quality variant data set","volume":"118","author":"Pfeifer","year":"2017","journal-title":"Heredity (Edinb)"},{"key":"2026052023582176600_btag183-B22","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":"2026052023582176600_btag183-B24","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1089\/cmb.2012.0022","article-title":"Mapping reads on a genomic sequence: an algorithmic overview and a practical comparative analysis","volume":"19","author":"Schbath","year":"2012","journal-title":"J Comput Biol"},{"key":"2026052023582176600_btag183-B25","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/BF01733210","article-title":"Comparative biosequence metrics","volume":"18","author":"Smith","year":"1981","journal-title":"J Mol Evol"},{"key":"2026052023582176600_btag183-B26","doi-asserted-by":"crossref","DOI":"10.1073\/pnas.2113075119","article-title":"Anchorwave: sensitive alignment of genomes with high sequence diversity, extensive structural polymorphism, and whole-genome duplication","volume":"119","author":"Song","year":"2022","journal-title":"Proc Natl Acad Sci USA"},{"key":"2026052023582176600_btag183-B27","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":"2026052023582176600_btag183-B28","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":"Inform Control"},{"key":"2026052023582176600_btag183-B29","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1038\/s41586-022-04601-8","article-title":"The human pangenome project: a global resource to map genomic diversity","volume":"604","author":"Wang","year":"2022","journal-title":"Nature"},{"key":"2026052023582176600_btag183-B30","doi-asserted-by":"crossref","first-page":"bbaf061","DOI":"10.1093\/bib\/bbaf061","article-title":"Foralign: accelerating gap-affine dna pairwise sequence alignment using for-blocks based on four russians approach with linear space complexity","volume":"26","author":"Wei","year":"2024","journal-title":"Brief Bioinform"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btag183\/68080126\/btag183.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/42\/5\/btag183\/68080126\/btag183.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/42\/5\/btag183\/68080126\/btag183.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T03:59:15Z","timestamp":1779335955000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btag183\/8653977"}},"subtitle":[],"editor":[{"given":"Jianlin","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2026,4,13]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,5,3]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btag183","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,5]]},"published":{"date-parts":[[2026,4,13]]},"article-number":"btag183"}}