Fast and exact gap-affine partial order alignment with POASTA
Bioinformatics · 26.12.2024 · 41 (1)
DOI: 10.1093/bioinformatics/btae757 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, online erschienen am 03.01.2025. Verfasst von Lucas R van Dijk und 4 weiteren Autor:innen. Beteiligte Einrichtung: Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard, Cambridge, MA 02142, United States. Hauptthemen laut MEDLINE: Algorithms, Sequence Alignment, Software, Sequence Analysis, DNA. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 37 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NIAID NIH HHS.
Abstract (Originalsprache)
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.1× and up to 9.8×, 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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard, Cambridge, MA 02142, United States.
- Delft Bioinformatics Lab, TU Delft, 2628 XE Delft, The Netherlands.
- Data Sciences Platform, Broad Institute of MIT and Harvard, Cambridge, MA 02142, United States.
ORCID-Profile: Lucas R van Dijk, Abigail L Manson, Ashlee M Earl, Kiran V Garimella, Thomas Abeel
Förderung
- NIAID NIH HHS
Zitieren
APA
van Dijk, L. R., Manson, A. L., Earl, A. M., Garimella, K. V., & Abeel, T. (2024). Fast and exact gap-affine partial order alignment with POASTA. Bioinformatics, 41(1). https://doi.org/10.1093/bioinformatics/btae757
Vancouver
van Dijk LR, Manson AL, Earl AM, Garimella KV, Abeel T. Fast and exact gap-affine partial order alignment with POASTA. Bioinformatics. 2024;41(1). doi:10.1093/bioinformatics/btae757
BibTeX
@article{vanDijk2024,
author = {van Dijk, Lucas R and Manson, Abigail L and Earl, Ashlee M and Garimella, Kiran V and Abeel, Thomas},
title = {Fast and exact gap-affine partial order alignment with POASTA},
journal = {Bioinformatics},
year = {2024},
volume = {41},
number = {1},
doi = {10.1093/bioinformatics/btae757}
}
EUVIMED