An Efficient Hybrid MPI-OpenMP Based Parallel Approach for Longest Common Subsequence

Yadav A. Khan A. Ahmed M.
2023 Institution of Engineering and Technology

IET Conference Proceedings
2023 #2023 Issue 4 35 - 40 pp.

In the area of bio-informatics and pattern recognition, sequence alignment and pattern matching are important operations, respectively. Finding the Longest Common Subsequence(LCS) plays an essential role in sequential alignment and pattern matching operations. The longest common subsequence problem is generally solved using the dynamic programming paradigm. It takes a considerable amount of time to solve the LCS problem for the large inputs, especially when executed sequentially. Now every computer system is equipped with multicore architectures, and this system supports parallelization. In recent years, several methods have been proposed to solve LCS, which exploits parallelism for faster execution. In this paper, we explore a hybrid parallel approach to solve the LCS problem efficiently and faster. The proposed method uses two levels of parallelism: Message Passing Interface(MPI) and OpenMP-API. The experiment results show that the proposed method outperformed the sequential method and the OpenMP-based diagonal parallelization method.

Dynamic Programming , Longest Common Subsequence(LCS) , Message Passing Interface , OpenMP , Parallel algorithms

Text of the article Перейти на текст статьи

Dept. of Computer Science and Engineering, Malaviya National Institute of Technology, Jaipur, India
Karaganda Medical University, Kazakhstan

Dept. of Computer Science and Engineering
Karaganda Medical University

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026