Parallel Implementation of Smith-Waterman Algorithm using MPI, OpenMP and Hybrid Model
Zeiad El-Saghir1, Hamdy Kelash2, Sayed Elnazly3, Hossam Faheem4
1Dr. Zeiad El-Saghir, Department of Computer Science and Information, Majmaah College of Science of University, Zolfi Saudi Arabia. Eng.
2Sayed Elnazly, Department of Computer Science and Engineering, Menoufia Electronic Engineering University, Egypt.
3Assistant Prof. Hamdy Kelash, Department of Computer Science and Engineering, Menoufia Electronic Engineering University, Egypt.
4Prof. Hossam Faheem, Department of Computer Systems, Ain Shams Computers and Information University, Egypt.
Manuscript received on 10 December 2014 | Revised Manuscript received on 20 December 2014 | Manuscript Published on 30 December 2014 | PP: 1-5 | Volume-4 Issue-7, December 2014 | Retrieval Number: G1873124714/14©BEIESP
Open Access | Editorial and Publishing Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Pairwise sequence alignment is often used to reveal similarities between sequences, locate patterns of conservation, study gene regulation, and infer evolutionary relationships [1]. Although the Smith–Waterman is the only algorithm guaranteed to find the optimal local alignment, it is also the slowest one as it costs O(mn) for computation & space. Also the volume of biological data is doubling about every six months so the total cost is O(kmn) where k is the size of the database [2, 3]. By using parallel hardware and software architecture accurate results can be achieved in reasonable time. In this paper we show a comparative study for parallelizing smith-waterman algorithm using different parallel models, pure MPI, pure OpenMP and hybrid MPI/OpenMP model. Based on the results it will be proved that hybrid programming which employ the coarse grain and fine grain parallelization, is more efficient compared with pure MPI and pure OpenMP.
Keywords: Smith-Waterman Algorithm; MPI, Openmp, Hybrid MPI Openmp, Bio-Informatics, Parallel Programming.
Scope of the Article: Web Algorithms