EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Theseus: fast and optimal affine-gap sequence-to-graph alignment

Albert Jiménez-Blanco iD, Lorién López-Villellas iD, Juan Carlos Moure iD, Miquel Moreto iD, Santiago Marco-Sola iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsSequence AlignmentSoftwareComputational BiologyGenomics

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}
}
Kostenlos starten →