利用GPGPU 搭配CUDA語言平行化加速生物演算法Smith-Waterman的序列比對

GPGPU with CUDA for Accelerating the Smith-Waterman Sequence Alignment Process

紀佳瑋(Jia-Wei Chi)

指導教授 ： 陳依蓉

國立暨南國際大學/科技學院/資訊工程學系/碩士(2014年)

https://doi.org/10.6837/NCNU.2014.00303

摘要

目前在生物資訊學中時常必須針對兩條序列進行搜尋比對，找出兩條序列相似的片段。隨著科技及資訊的進步，資料庫中累積的序列數量急速的增加，為了滿足及解決大量搜尋的需求，於是有人提出了各式各樣的搜尋比對工具，如Smith-Waterman、BLAST、…等搜尋比對演算法。由於資料庫越來越大，搜尋的時間已經無法在期望的時間內完成，所以往往期望能有一個更好的加速比對技術。然而GPGPU本身擁有的多個計算單元適用於大量的資料運算，且再搭配上CUDA語言即可充分的發揮GPGPU的計算效能。在本篇論文中我們使用了GPGPU來當作平行化計算的設備，並提出了一個平行化的計算方式和優化記憶體的方法，改善Smith-Waterman演算法的搜尋效率，藉此可以減少執行的時間，達到一個較好的效率提升。

關鍵字

生物資訊學 ； 搜尋比對 ； Smith-Waterman ； BLAST ； GPU ； CUDA

並列摘要

In bioinformatics, we often have to search for the similarity of the two sequences to identify similar fragments of two sequences. For more advanced technology &information progress, the number of sequence accumulated in the databases increases rapidly in order to solve a large number of searching. So there are a lot of search algorithms & tools had been suggested, such as Smith-Waterman, BLAST …, etc. Due to the size of database growing, the search time increase and could not completed search job within a requested time. How to find a better algorithm to accelerate the search speed is what we’re looking for. The GPGPU( General Purpose GPU), own a lot of SP(Streaming Processor) , is very suitable for large computing requirements. Under the specific support of particular language CUDA, GUGPU can fully perform well. In this paper we use the GPGPU as the parallel computing platform. We present a parallel method of calculation and also provide the way of optimization of memory to improve the efficiency of Smith-Waterman search algorithm. It makes us reduce the execution time to achieve a better efficiency.

並列關鍵字

Smith-Waterman ； GPU ； CUDA

參考文獻

[1] Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ, Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Res, 1997.

[2] C.W. Yu, K.H. Kwong, K.H. Lee, P.H.W. Leong, A smith-waterman systolic cell, 2005.

[3] Edans Flavius O. Sandes, Alba Cristina M.A. de Melo, CUDAlign: Using GPU to Accelerate theComparison of Megabase Genomic Sequences, in Proc. IEEE Symp.Principles and Practice of Parallel Programming (PPoPP 10), IEEEPress, Jan. 2010.

[4] Graphics Processing Unit(GPUs)：Architecture and Programming. http://cs.nyu.edu/courses/spring12/CSCI-GA.3033-012/.

[5] Gregory M. Striemer, Ali Akoglu, Sequence Alignment with GPU: Performance and Design Challenges, IPDPS IEEE, May 2009, 1-10.