Parallelization of Needleman-Wunsch Algorithm Based on Software Pipelining
Автор: Hanwen Hu ,Zhenzhou Ji
Журнал: International Journal of Engineering and Manufacturing(IJEM) @ijem
Статья в выпуске: 4 vol.1, 2011 года.
Бесплатный доступ
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.
Bioinformatics, sequence alignment, Needleman-Wunsch, software pipelining, OpenMP
Короткий адрес: https://sciup.org/15014148
IDR: 15014148
Список литературы Parallelization of Needleman-Wunsch Algorithm Based on Software Pipelining
- Zhongneng Xu, Bioinformatics, Tsinghua University Press, Sep 2008, pp. 134-164, (in Chinese).
- David W Mount, Bioinformatics:sequence and genome analysis, USA: Cold Spring Harbor Laboratory Press, 2002.
- T K Attwood, D J Parry—Smith, Introdution to Bioinformatics, Prentice Hall, 1st ed., Mar 1999.
- 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.
- T Smith, M Waterman, “Identification of common molecular sequence,” Journal of Molecular Biology, 1981, 147, pp.195-197.
- Maoyi Li, “Bioinformatics problem of sequence alignment,” pp.8-25, unpublished, (in Chinese).
- 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).
- Min Lin, “Sequence alignment algorithm of protein,” No.2. Journal of Fujian Computer, 2010, (in Chinese).
- 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.
