EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Exact global alignment using A* with chaining seed heuristic and match pruning

Ragnar Groot Koerkamp iD, Pesho Ivanov iD

Bioinformatics · 2024

DOI: 10.1093/bioinformatics/btae032 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, 2024. Verfasst von Ragnar Groot Koerkamp und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, ETH Zurich, Rämistrasse 101, Zurich 8092, Switzerland. Hauptthemen laut MEDLINE: Software, Heuristics. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: ETH Research.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation Sequence alignment has been at the core of computational biology for half a century. Still, it is an open problem to design a practical algorithm for exact alignment of a pair of related sequences in linear-like time. Results We solve exact global pairwise alignment with respect to edit distance by using the A* shortest path algorithm. In order to efficiently align long sequences with high divergence, we extend the recently proposed seed heuristic with match chaining, gap costs, and inexact matches. We additionally integrate the novel match pruning technique and diagonal transition to improve the A* search. We prove the correctness of our algorithm, implement it in the A*PA aligner, and justify our extensions intuitively and empirically. On random sequences of divergence d=4% and length n, the empirical runtime of A*PA scales near-linearly with length (best fit n1.06, n≤107 bp). A similar scaling remains up to d=12% (best fit n1.24, n≤107 bp). For n=107 bp and d=4%, A*PA reaches >500× speedup compared to the leading exact aligners Edlib and BiWFA. The performance of A*PA is highly influenced by long gaps. On long (n>500kb) ONT reads of a human sample it efficiently aligns sequences with d<10%, leading to 3× median speedup compared to Edlib and BiWFA. When the sequences come from different human samples, A*PA performs 1.7× faster than Edlib and BiWFA. Availability and implementation github.com/RagnarGrootKoerkamp/astar-pairwise-aligner.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

SoftwareHeuristicsHumansSequence Analysis, DNAAlgorithmsSeeds

Autor:innen und Institutionen

  • Department of Computer Science, ETH Zurich, Rämistrasse 101, Zurich 8092, Switzerland.

ORCID-Profile: Ragnar Groot Koerkamp, Pesho Ivanov

Förderung

  • ETH Research

Zitieren

APA

Groot Koerkamp, R., & Ivanov, P. (2024). Exact global alignment using A* with chaining seed heuristic and match pruning. Bioinformatics. https://doi.org/10.1093/bioinformatics/btae032

Vancouver

Groot Koerkamp R, Ivanov P. Exact global alignment using A* with chaining seed heuristic and match pruning. Bioinformatics. 2024. doi:10.1093/bioinformatics/btae032

BibTeX
@article{GrootKoerkamp2024,
  author = {Groot Koerkamp, Ragnar and Ivanov, Pesho},
  title = {Exact global alignment using A* with chaining seed heuristic and match pruning},
  journal = {Bioinformatics},
  year = {2024},
  doi = {10.1093/bioinformatics/btae032}
}
Kostenlos starten →