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 · 2025
Read Fast and exact gap-affine partial order alignment with POASTA by Lucas R van Dijk, Abigail L Manson, Ashlee M Earl, Kiran V Garimella, Thomas Abeel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/pmc-11755094.txt.
Description
Van Dijk, Manson, Earl, Garimella, and Abeel speed up a classic method for aligning DNA sequences to a graph of known variants. Partial order alignment underpins genome assembly and pangenome work, but exact methods crawl on large graphs. Their 2024 tool, POASTA, guarantees the best alignment under a scoring scheme that charges gaps by length, while rivals cut corners.
The trick is exploiting long exact matches between the graph and the query sequence. On bacterial gene datasets, the tool ran about four times faster than the best rival on average, sometimes near ten times, with less memory. Its lean memory allowed alignments across 342 tuberculosis genomes spanning millions of letters. The code is public on GitHub.
Catalog record
| CREATOR | Lucas R van Dijk, Abigail L Manson, Ashlee M Earl, Kiran V Garimella, Thomas Abeel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |