Theseus: Fast and Optimal Affine-Gap Sequence-to-Graph Alignment

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Sequence-to-graph alignment is crucial for multiple sequence alignment (MSA) and pangenome analysis.
• Existing optimal affine-gap alignment algorithms have high memory and computational demands, limiting scalability.
• Heuristic methods offer speed but compromise alignment optimality.

Purpose of the Study:

• Introduce Theseus, a novel algorithm for fast and optimal affine-gap sequence-to-graph alignment.
• Address the limitations of current methods in terms of speed and memory efficiency.
• Enable scalable and accurate alignment for complex genomic graphs.

Main Methods:

• Developed a novel algorithm, Theseus, for optimal affine-gap sequence-to-graph alignment.
• Implemented a sparse-data strategy by processing a subset of dynamic programming cells.
• Leveraged sequence similarities to accelerate computation and reduce memory footprint.
• Supported alignment on arbitrary directed graphs, including those with cycles.

Main Results:

• Theseus demonstrates significant speedups compared to existing optimal aligners like POASTA and SPOA in MSA.
• It achieves comparable or better performance than heuristic methods like abPOA while ensuring optimality.
• In pangenome read mapping, Theseus shows substantial speed improvements over vg map and other alignment kernels.
• Outperforms vg on synthetic cyclic graphs, highlighting its efficiency with complex structures.

Conclusions:

• Theseus provides a fast, optimal, and memory-efficient solution for sequence-to-graph alignment.
• It advances the capabilities for large-scale pangenome analysis and multiple sequence alignment.
• The algorithm offers a scalable approach for aligning sequences to complex genomic graphs.