Fast and exact gap-affine partial order alignment with POASTA
Preprint
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. Availability and implementation: POASTA is available on Github at https://github.com/broadinstitute/poasta .Keywords
All Related Versions
- Published version: Bioinformatics, 41 (1).
This publication has 28 references indexed in Scilit:
- Pangenome graph construction from genome alignments with Minigraph-CactusNature Biotechnology, 2023
- On the Complexity of Sequence-to-Graph AlignmentJournal of Computational Biology, 2020
- Identification and Characterization of Genetic Determinants of Isoniazid and Rifampicin Resistance in Mycobacterium tuberculosis in Southern IndiaScientific Reports, 2019
- Multi-platform discovery of haplotype-resolved structural variation in human genomesNature Communications, 2019
- A complete bacterial genome assembled de novo using only nanopore sequencing dataNature Methods, 2015
- Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing dataNature Methods, 2013
- Multiple sequence alignment using partial order graphsBioinformatics, 2002
- Biological Sequence Analysis1998
- On the Complexity of Multiple Sequence AlignmentJournal of Computational Biology, 1994
- Finding approximate patterns in stringsJournal of Algorithms, 1985