EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Block Aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices

Daniel Liu iD, Martin Steinegger iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsProteinsPosition-Specific Scoring MatricesSequence AlignmentSequence AnalysisSoftware

Substanzen

Proteins

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