Fast and exact gap-affine partial order alignment with POASTA

Lucas R. van Dijk; Abigail L. Manson; Ashlee M. Earl; Kiran V. Garimella; Thomas Abeel

doi:10.1093/bioinformatics/btae757

Fast and exact gap-affine partial order alignment with POASTA

Lucas R. van Dijk^*, Abigail L. Manson , Ashlee M. Earl, Kiran V. Garimella, Thomas Abeel

^*Corresponding author for this work

Pattern Recognition and Bioinformatics

Research output: Contribution to journal › Article › Scientific › peer-review

50 Downloads (Pure)

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.

Original language	English
Number of pages	9
Journal	Bioinformatics
Volume	41
Issue number	1
DOIs	https://doi.org/10.1093/bioinformatics/btae757
Publication status	Published - 2025

Keywords

multiple sequence alignment
partial order alignment
pangenome graphs

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1093/bioinformatics/btae757

btae757Final published version, 3.5 MBLicence: CC BY

Cite this

@article{437e59edf29d42a49abf395234b42070,

title = "Fast and exact gap-affine partial order alignment with POASTA",

abstract = "MotivationPartial 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.ResultsWe 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{\textquoteright}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.",

keywords = "multiple sequence alignment, partial order alignment, pangenome graphs",

author = "{van Dijk}, {Lucas R.} and Manson, {Abigail L.} and Earl, {Ashlee M.} and Garimella, {Kiran V.} and Thomas Abeel",

year = "2025",

doi = "10.1093/bioinformatics/btae757",

language = "English",

volume = "41",

journal = "Bioinformatics",

issn = "1367-4803",

publisher = "Oxford University Press",

number = "1",

}

TY - JOUR

T1 - Fast and exact gap-affine partial order alignment with POASTA

AU - van Dijk, Lucas R.

AU - Manson , Abigail L.

AU - Earl, Ashlee M.

AU - Garimella, Kiran V.

AU - Abeel, Thomas

PY - 2025

Y1 - 2025

N2 - MotivationPartial 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.ResultsWe 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.

AB - MotivationPartial 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.ResultsWe 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.

KW - multiple sequence alignment

KW - partial order alignment

KW - pangenome graphs

UR - http://www.scopus.com/inward/record.url?scp=85216428458&partnerID=8YFLogxK

U2 - 10.1093/bioinformatics/btae757

DO - 10.1093/bioinformatics/btae757

M3 - Article

SN - 1367-4803

VL - 41

JO - Bioinformatics

JF - Bioinformatics

IS - 1

ER -

Fast and exact gap-affine partial order alignment with POASTA

Abstract

Keywords

UN SDGs

Access to Document

Other files and links

Fingerprint

Characterizing bacterial genetic diversity: In species' pangenomes and microbial communities

Cite this