EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fast and exact gap-affine partial order alignment with POASTA

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

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsSequence AlignmentSoftwareSequence Analysis, DNAMycobacterium tuberculosisGenome, Bacterial

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}
}
Kostenlos starten →