Singletrack

This repository contains different implementations of Singletrack, a general technique to reduce memory consumption and improve the performance of gap-affine and dual gap-affine sequence alignment algorithms. This technique was presented on DOI: 10.1101/2025.10.31.68562

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.
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 2x and 4x and WFA usage by 3x and 5x 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.4x at the cost of doubling memory consumption, while Singletrack increases the performance of the WFA implementation in WFA2-lib by 1.2–2.1x. 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.2x higher performance.

BibTex citation

@article{LpezVillellas2025,
    title = {Singletrack: An Algorithm for Improving Memory Consumption and Performance of Gap-Affine Sequence Alignment},
    url = {http://dx.doi.org/10.1101/2025.10.31.685625},
    DOI = {10.1101/2025.10.31.685625},
    publisher = {openRxiv},
    author = {López-Villellas,  Lorién and Iñiguez,  Cristian and Jiménez-Blanco,  Albert and Aguado-Puig,  Quim and Moretó,  Miquel and Alastruey-Benedé,  Jesús and Ibáñez,  Pablo and Marco-Sola,  Santiago},
    year = {2025},
    month = nov 
}