Block Aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices
Bioinformatics · 2023
DOI: 10.1093/bioinformatics/btad487 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, 2023. Verfasst von Daniel Liu und 1 weiteren Autor:innen. Beteiligte Einrichtung: University of California Los Angeles, Los Angeles, CA, United States. Hauptthemen laut MEDLINE: Algorithms, Proteins. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Emergent Ventures.
Abstract (Originalsprache)
Motivation Efficiently aligning sequences is a fundamental problem in bioinformatics. Many recent algorithms for computing alignments through Smith–Waterman–Gotoh dynamic programming (DP) exploit Single Instruction Multiple Data (SIMD) operations on modern CPUs for speed. However, these advances have largely ignored difficulties associated with efficiently handling complex scoring matrices or large gaps (insertions or deletions). Results We propose a new SIMD-accelerated algorithm called Block Aligner for aligning nucleotide and protein sequences against other sequences or position-specific scoring matrices. We introduce a new paradigm that uses blocks in the DP matrix that greedily shift, grow, and shrink. This approach allows regions of the DP matrix to be adaptively computed. Our algorithm reaches over 5–10 times faster than some previous methods while incurring an error rate of less than 3% on protein and long read datasets, despite large gaps and low sequence identities. Availability and implementation Our algorithm is implemented for global, local, and X-drop alignments. It is available as a Rust library (with C bindings) at https://github.com/Daniel-Liu-c0deb0t/block-aligner.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Substanzen
Autor:innen und Institutionen
- University of California Los Angeles, Los Angeles, CA, United States.
- School of Biological Sciences, Artificial Intelligence Institute, Institute of Molecular Biology and Genetics, Seoul National University, Seoul, South Korea.
ORCID-Profile: Daniel Liu, Martin Steinegger
Förderung
- Emergent Ventures
Zitieren
APA
Liu, D., & Steinegger, M. (2023). Block Aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices. Bioinformatics. https://doi.org/10.1093/bioinformatics/btad487
Vancouver
Liu D, Steinegger M. Block Aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices. Bioinformatics. 2023. doi:10.1093/bioinformatics/btad487
BibTeX
@article{Liu2023,
author = {Liu, Daniel and Steinegger, Martin},
title = {Block Aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices},
journal = {Bioinformatics},
year = {2023},
doi = {10.1093/bioinformatics/btad487}
}
EUVIMED