EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

BSAlign: A Library for Nucleotide Sequence Alignment

Haojing Shao iD, Jue Ruan iD

Genomics, Proteomics & Bioinformatics · 2024

DOI: 10.1093/gpbjnl/qzae025 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Genomics, Proteomics & Bioinformatics, 2024. Verfasst von Haojing Shao und 1 weiteren Autor:innen. Beteiligte Einrichtung: Shenzhen Branch, Guangdong Laboratory of Lingnan Modern Agriculture, Genome Analysis Laboratory of the Ministry of Agriculture and Rural Affairs, Agr…. Hauptthemen laut MEDLINE: Sequence Alignment, Algorithms, Software. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Increasing the accuracy of the nucleotide sequence alignment is an essential issue in genomics research. Although classic dynamic programming (DP) algorithms (e.g., Smith–Waterman and Needleman–Wunsch) guarantee to produce the optimal result, their time complexity hinders the application of large-scale sequence alignment. Many optimization efforts that aim to accelerate the alignment process generally come from three perspectives: redesigning data structures [e.g., diagonal or striped Single Instruction Multiple Data (SIMD) implementations], increasing the number of parallelisms in SIMD operations (e.g., difference recurrence relation), or reducing search space (e.g., banded DP). However, no methods combine all these three aspects to build an ultra-fast algorithm. In this study, we developed a Banded Striped Aligner (BSAlign) library that delivers accurate alignment results at an ultra-fast speed by knitting a series of novel methods together to take advantage of all of the aforementioned three perspectives with highlights such as active F-loop in striped vectorization and striped move in banded DP. We applied our new acceleration design on both regular and edit distance pairwise alignment. BSAlign achieved 2-fold speed-up than other SIMD-based implementations for regular pairwise alignment, and 1.5-fold to 4-fold speed-up in edit distance-based implementations for long reads. BSAlign is implemented in C programing language and is available at https://github.com/ruanjue/bsalign.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

Sequence AlignmentAlgorithmsSoftwareSequence Analysis, DNAGene LibraryComputational BiologyBase Sequence

Stichwörter der Autor:innen

Banded dynamic programmingEdit distanceF evaluationPairwise alignmentStriped vectorization

Autor:innen und Institutionen

  • Shenzhen Branch, Guangdong Laboratory of Lingnan Modern Agriculture, Genome Analysis Laboratory of the Ministry of Agriculture and Rural Affairs, Agricultural Genomics Institute at Shenzhen, Chinese Academy of Agricultu…

ORCID-Profile: Haojing Shao, Jue Ruan

Zitieren

APA

Shao, H., & Ruan, J. (2024). BSAlign: A Library for Nucleotide Sequence Alignment. Genomics, Proteomics & Bioinformatics. https://doi.org/10.1093/gpbjnl/qzae025

Vancouver

Shao H, Ruan J. BSAlign: A Library for Nucleotide Sequence Alignment. Genomics, Proteomics & Bioinformatics. 2024. doi:10.1093/gpbjnl/qzae025

BibTeX
@article{Shao2024,
  author = {Shao, Haojing and Ruan, Jue},
  title = {BSAlign: A Library for Nucleotide Sequence Alignment},
  journal = {Genomics, Proteomics & Bioinformatics},
  year = {2024},
  doi = {10.1093/gpbjnl/qzae025}
}
Kostenlos starten →