International Journal of Engineering and Manufacturing (IJEM)
IJEM Vol. 1, No. 4, 29 Aug. 2011
Cover page and Table of Contents: PDF (size: 146KB)
Parallelization of Needleman-Wunsch Algorithm Based on Software Pipelining
Full Text (PDF, 146KB), PP.59-64
Views: 0 Downloads: 0
Author(s)
Hanwen Hu
1
Zhenzhou Ji
1
Index Terms
Bioinformatics, sequence alignment, Needleman-Wunsch, software pipelining, OpenMP
Abstract
Sequence alignment is one of the most important algorithms that analyzing massive biological information. In modern bioinformatics, it plays an important role in field of serching for similar sequences, predicting sequence information of unkown sequence, looking for specific position of sequence, predicting protein structure and so on. Needleman-Wunsch algorithm is the earliest global alignment algorithm, it gets widely application with its accuracy, however, it has a high time complexity and its speed is slower. This paper adopts software pipelining technique to optimize Needleman-Wunsch algorithm with parallelization, and OpenMP which is the industrialized standard of shared memory programming is used to parallelize it. The performance of Needlelman-Wunsch algorithm can get a great improvement with the optimization.
Cite This Paper
Hanwen Hu,Zhenzhou Ji,"Parallelization of Needleman-Wunsch Algorithm Based on Software Pipelining", IJEM, vol.1, no.4, pp.59-64, 2011. DOI: 10.5815/ijem.2011.04.09
Reference
[1]Zhongneng Xu, Bioinformatics, Tsinghua University Press, Sep 2008, pp. 134-164, (in Chinese).
[2]David W Mount, Bioinformatics:sequence and genome analysis, USA: Cold Spring Harbor Laboratory Press, 2002.
[3]T K Attwood, D J Parry—Smith, Introdution to Bioinformatics, Prentice Hall, 1st ed., Mar 1999.
[4]S Needleman, C Wunsch, “Ageneral method applicable to the search for similarities in theamino acid sequences oftwo Proteins, ”Journal of Molecular Biology, l 970, 48, pp.443-453.
[5]T Smith, M Waterman, “Identification of common molecular sequence,” Journal of Molecular Biology, 1981, 147, pp.195-197.
[6]Maoyi Li, “Bioinformatics problem of sequence alignment,” pp.8-25, unpublished, (in Chinese).
[7]Fuxiang Zhang, Jinling Zhou, “The Parallelization Research and the application of the Sequence Compares to Algorithm,” vol.8. No.4. Journal of Weifang University, Jul 2008, (in Chinese).
[8]Min Lin, “Sequence alignment algorithm of protein,” No.2. Journal of Fujian Computer, 2010, (in Chinese).
[9]Vicki H. Allan, Reese B. Jones, Randall M. Lee, Stephen J. Allan, “Software Pipelining,” vol.27. No.4. Journal of ACM Computing Surveys, Sep 1995, pp.367-432.