Fast exact gap-affine partial order alignment with POASTA

Journal article (2025)

Authors

L.R. van Dijk Broad Institute of MIT and Harvard, Pattern Recognition and Bioinformatics - EEMCS
Abigail L. Manson McGuire Broad Institute of MIT and Harvard
Ashlee M. Earl Broad Institute of MIT and Harvard
Kiran Garimella Broad Institute of MIT and Harvard
T.E.P.M.F. Abeel Broad Institute of MIT and Harvard, Pattern Recognition and Bioinformatics - EEMCS
Research Group
Pattern Recognition and Bioinformatics (EEMCS) (TU Delft)
More Info
expand_more

Published Date

2025

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Intelligent Systems

Research Group

Pattern Recognition and Bioinformatics

Abstract

Motivation
Partial order alignment is a widely used method for computing multiple sequence alignments, with applications in genome assembly and pangenomics, among many others. Current algorithms to compute the optimal, gap-affine partial order alignment do not scale well to larger graphs and sequences. While heuristic approaches exist, they do not guarantee optimal alignment and sacrifice alignment accuracy.

Results
We present POASTA, a new optimal algorithm for partial order alignment that exploits long stretches of matching sequence between the graph and a query. We benchmarked POASTA against the state-of-the-art on several diverse bacterial gene datasets and demonstrated an average speed-up of 4.1x and up to 9.8x, using less memory. POASTA’s memory scaling characteristics enabled the construction of much larger POA graphs than previously possible, as demonstrated by megabase-length alignments of 342 Mycobacterium tuberculosis sequences.