Singletrack: an algorithm for improving memory consumption and performance of gap-affine sequence alignment
Authors:
Open Access
- 13 April 2026
- journal article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 42 (5)
Abstract
Motivation: 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. Results: 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× and 4× and WFA usage by 3× and 5× for gap-affine and dual gap-affine alignments, respectively. Moreover, replacing KSW2’s memory-reduction technique with Singletrack accelerates its SK implementation by up to 1.4× at the cost of doubling memory consumption, while Singletrack increases the performance of the WFA implementation in WFA2-lib by 1.2–2.1×. 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× higher performance. Availability and implementation: The Singletrack implementations presented in this work are available on Zenodo (DOI: 10.5281/zenodo.18770585) and GitHub (https://github.com/LorienLV/singletrack).Keywords
All Related Versions
Funding Information
- Spanish Ministry of Science, Innovation and Universities (MICIU/AEI/10.13039/501100011033)
- Spanish Ministry of Science, Innovation and Universities (PID2020-113614RB-C21)
- Spanish Ministry of Science, Innovation and Universities (PID2022-136454NB C22)
- Spanish Ministry of Science, Innovation and Universities (PID2023-146193OB-I00)
- Spanish Ministry of Science, Innovation and Universities (PID2023-146511NB-I00)
- Spanish Ministry of Science, Innovation and Universities (CNS2025-166442)
- Generalitat de Catalunya GenCat-DIUiE (2021-SGR-00763)
- Generalitat de Catalunya GenCat-DIUiE (2021-SGR-00574)
- Gobierno de Aragón (E45_20R T58_23R)
- Arm-BSC Center of Excellence
- Lenovo-BSC Contract-Framework Contract
- Ministry for Digital Transformation and the Civil Service
- European Commission
- State Secretariat for Telecommunications and Digital Infrastructures
- European Union - Next Generation EU (TSI-069100-2023-0015)
- European Union’s Horizon Europe
- STRATUM (101137416)
- Barcelona Zettascale Laboratory
- Ministry for Digital Transformation and of Public Services
- European Union—NextGenerationEU
This publication has 28 references indexed in Scilit:
- From molecules to genomic variations: Accelerating genome analysis via intelligent algorithms and architecturesComputational and Structural Biotechnology Journal, 2022
- The Human Pangenome Project: a global resource to map genomic diversityNature, 2022
- Current challenges and solutions of de novo assemblyQuantitative Biology, 2019
- Nanopore sequencing and assembly of a human genome with ultra-long readsNature Biotechnology, 2018
- From next-generation resequencing reads to a high-quality variant data setHeredity, 2016
- Coming of age: ten years of next-generation sequencing technologiesNature Reviews Genetics, 2016
- Optimal sequence alignment allowing for long gapsBulletin of Mathematical Biology, 1990
- Algorithms for approximate string matchingInformation and Control, 1985
- An improved algorithm for matching biological sequencesJournal of Molecular Biology, 1982
- Comparative biosequence metricsJournal of Molecular Evolution, 1981