EUVIMEDEUVIMED entdecken
Crossref

A scalable parallel algorithm for global sequence alignment with customizable scoring scheme

Muhammad Umair Sadiq, Muhammad Murtaza Yousaf

Concurrency and Computation: Practice and Experience · 15.11.2023 · 35 (25)

DOI: 10.1002/cpe.7888 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Concurrency and Computation: Practice and Experience, online erschienen am 07.08.2023. Verfasst von Muhammad Umair Sadiq und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 67 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Sequence alignment is a critical computational problem in various domains, including genomics, proteomics, and natural language processing. The Needleman‐Wunsch (NW) algorithm is a classical dynamic programming approach for finding the optimal global alignment between two sequences. However, its quadratic time and space complexity make it impractical for aligning large‐scale sequences, which are increasingly common in modern applications. In this article, we propose a parallel variation of the NW algorithm that enables scalable global sequence alignment with customizable scoring schemes. Our approach re‐formulates the dependencies in the NW algorithm to enable parallel execution, thereby leveraging the computational power of modern parallel architectures, such as graphics processing unit (GPU). Furthermore, our algorithm supports arbitrary linear scoring schemes, which allows us to use domain‐specific knowledge to improve alignment accuracy. We establish the correctness of our algorithm and evaluate its performance using real DNA and user trajectory sequences on GPUs. Our parallel algorithm has shown impressive results in our experiments, with a peak performance of 27.99 GCUPS (giga cell updates per second) and a maximum speedup of 48.18 times compared to the traditional sequential implementation. Additionally, our algorithm demonstrates remarkable scalability, enabling the alignment of sequences of any length while ensuring balanced work distribution and optimal utilization of resources. Our primary objective is to harness the computational capabilities of a single GPU and fully utilize the processing power of multi‐core CPUs.

Zitieren

APA

Sadiq, M. U., & Yousaf, M. M. (2023). A scalable parallel algorithm for global sequence alignment with customizable scoring scheme. Concurrency and Computation: Practice and Experience, 35(25). https://doi.org/10.1002/cpe.7888

Vancouver

Sadiq MU, Yousaf MM. A scalable parallel algorithm for global sequence alignment with customizable scoring scheme. Concurrency and Computation: Practice and Experience. 2023;35(25). doi:10.1002/cpe.7888

BibTeX
@article{Sadiq2023,
  author = {Sadiq, Muhammad Umair and Yousaf, Muhammad Murtaza},
  title = {A scalable parallel algorithm for global sequence alignment with customizable scoring scheme},
  journal = {Concurrency and Computation: Practice and Experience},
  year = {2023},
  volume = {35},
  number = {25},
  doi = {10.1002/cpe.7888}
}
Kostenlos starten →