Theseus: fast and optimal affine-gap sequence-to-graph alignment
Bioinformatics · 2026
DOI: 10.1093/bioinformatics/btag561 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, 2026. Verfasst von Albert Jiménez-Blanco und 4 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, Universitat Politècnica de Catalunya, Barcelona, 08034, Spain. Hauptthemen laut MEDLINE: Algorithms, Sequence Alignment, Software, Computational Biology. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 45 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Spanish Ministerio de Ciencia, Innovación y Universidades y de la Agencia.
Abstract (Originalsprache)
Motivation Sequence-to-graph alignment is a central problem in bioinformatics, with applications in multiple sequence alignment (MSA) and pangenome analysis, among others. However, current algorithms for optimal affine-gap alignment impose high memory and computational requirements, limiting their scalability to aligning long sequences to complex graphs. Practical solutions partially address this problem using heuristic strategies that ultimately trade off optimality for speed. Results This work presents Theseus, a novel, fast, and optimal affine-gap sequence-to-graph alignment algorithm. Theseus leverages similarities between genomic sequences to accelerate the alignment computation and reduces the overall memory requirements without compromising optimality. To that end, Theseus processes only a subset of the dynamic programming cells, using a sparse-data strategy that enables efficient sequence-to-graph alignment. Moreover, our algorithm supports optimal affine-gap alignment on arbitrary directed graphs, including those with cycles. We evaluate Theseus on two key problems: MSA and pangenome read mapping. For MSA, we compare it against SPOA, abPOA, and POASTA. Theseus is 1.6× to 17.6× faster than POASTA, and 7.3× faster, on average, than SPOA, both optimal aligners. Compared with abPOA, Theseus ensures optimality and scales to the largest problems. For pangenome read mapping, we benchmark Theseus against the alignment stage of the mapping tool vg map, along with the alignment kernels of SPOA, abPOA, and POASTA. Theseus outperforms the other methods, showing a 1.9× to 16.9× speedup on short reads. Moreover, Theseus is 1.5× to 36.3× faster than vg when aligning against synthetic cyclic graphs. Availability and implementation Theseus code and documentation are publicly available at https://github.com/albertjimenezbl/theseus-lib.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Department of Computer Science, Universitat Politècnica de Catalunya, Barcelona, 08034, Spain.
- Computer Sciences Department, Barcelona Supercomputing Center, Barcelona, 08034, Spain.
- Department of Computer Science and Systems Engineering, University of Zaragoza, Zaragoza, 50018, Spain.
- Department of Computer Architecture and Operative Systems, Universitat Autònoma de Barcelona, Barcelona, 08193, Spain.
- Department of Computer Architecture, Universitat Politècnica de Catalunya, Barcelona, 08034, Spain.
ORCID-Profile: Albert Jiménez-Blanco, Lorién López-Villellas, Juan Carlos Moure, Miquel Moreto, Santiago Marco-Sola
Förderung
- Spanish Ministerio de Ciencia, Innovación y Universidades y de la Agencia
Zitieren
APA
Jiménez-Blanco, A., López-Villellas, L., Moure, J. C., Moreto, M., & Marco-Sola, S. (2026). Theseus: fast and optimal affine-gap sequence-to-graph alignment. Bioinformatics. https://doi.org/10.1093/bioinformatics/btag561
Vancouver
Jiménez-Blanco A, López-Villellas L, Moure JC, Moreto M, Marco-Sola S. Theseus: fast and optimal affine-gap sequence-to-graph alignment. Bioinformatics. 2026. doi:10.1093/bioinformatics/btag561
BibTeX
@article{JimnezBlanco2026,
author = {Jiménez-Blanco, Albert and López-Villellas, Lorién and Moure, Juan Carlos and Moreto, Miquel and Marco-Sola, Santiago},
title = {Theseus: fast and optimal affine-gap sequence-to-graph alignment},
journal = {Bioinformatics},
year = {2026},
doi = {10.1093/bioinformatics/btag561}
}
EUVIMED