臺灣博碩士論文加值系統

　　為了因應爆炸性高維度成長的生物資訊量，進行生物資訊研究時的生物資料庫以及分析工具就顯得至關重要，而序列比對 (Sequence alignment)則是生物資訊中相當重要的一個研究領域。為了改善舊有的演算法缺點，美國National Center for Biotechnology Information (NCBI)提供了一個名為BLAST的處理工具，用來因應處理DNA或蛋白質序列比對的快速尋找機制。近年來，憑藉著GPU CUDA平行處理的技術日新月異增進，有學者提出以GPU平行化的方式來改善BLAST的效能，其演算法被命名為CUDA-BLASTP，主要是採用Deterministic Finite-state Automaton (DFA)的方式來存放資料改善BLAST的Seed Generation階段的比對過程。因此，本篇論文是將CUDA-BLASTP進行整體4個階段的分析後，得出於階段1 Seed Generation執行查表比對時佔整體執行時間的絕大部分，為此我們提出新的索引表資料結構取代舊有的DFA，來提升CUDA-BLASTP的效能。於測試階段，我們特別使用了長度小於1,024的Query與CUDA-BLASTP演算法做比較，並且針對長度小於128的Query與陳昭佑等人的方法進行測試。經過實驗證明，在進行BLAST序列比對時 ，若不考慮記憶體大小且Query長度小於1,024時，可以採用我們所設計之索引表。

　　In order to respond to the explosive high-dimensional growth of biological information , the biological database and analytical tools for Bioinformatics research are crucial, and sequence alignment is a very important research field in Bioinformatics. In order to improve the shortcomings of the old algorithm, the National Center for Biotechnology Information (NCBI) provides a processing tool, called BLAST, to respond to the rapid search mechanism for DNA or protein sequence alignment. In recent years, with the rapid advancement of GPU CUDA parallel processing, some scholars have proposed to improve the performance of BLAST by GPU. The algorithm is named CUDA-BLASTP, mainly using Deterministic Finite-state Automaton (DFA). The way to store data improves the alignment process of BLAST's Seed Generation stage. Therefore, this paper analyzes four stages of CUDA-BLASTP, and the stage 1 occupied most of the overall execution time when the stage 1 performs table lookup comparison. For the reason, we propose a new Query index table data structure. The data structure replaces the old mathod of DFA to improve the performance of CUDA-BLASTP. In the final test stage, we specifically used Query with a length less than 1,024 to compare with the CUDA-BLASTP algorithm, and tested the Query with a length less than 128, compared with Chen Zhaoyou et al. Experiments have shown that when performing BLAST sequence alignment, if we do not consider the memory size and the Query length is less than 1,024, everyone can use the index table we designed.

目錄
中文摘要 I
英文摘要 II
致謝 III
目錄 IV
圖目錄 V
表目錄 VII

第一章　緒論 1

第二章　相關資訊 4
2.1　統一計算架構(CUDA) 4
2.2　圖形處理單元(GPU) 7
2.3　序列比對問題 10
2.4　BLAST演算法 11
2.5　GPU-BLAST演算法 18
2.6　CUDA-BLASTP演算法 21
2.7　在 GPU 中使用 CUDA 去改善 CUDA-BLASTP 24

第三章　研究方法 27
3.1　CUDA-BLASTP分析 27
3.2　提出改善方法 28

第四章　實驗數據 36
4.1　與CUDA-BLAST演算法進行測試 36
4.1.1　門檻值為13之測試 36
4.1.2　門檻值為12之測試 39
4.2　與文獻[17]之方法進行測試 42

第五章　結論 46

參考文獻 47

[1] Arthur Lesk, Introduction to Bioinformatics, 4th Edition, Oxford University Press, 2014
[2] CHANG, Dar-Jen; KIMMER, Christopher; OUYANG, Ming. Accelerating the Nussinov RNA folding algorithm with CUDA/GPU. In: The 10th IEEE International Symposium on Signal Processing and Information Technology. IEEE, 2010. p. 120-125.
[3] SMITH, Temple F., et al. Identification of common molecular subsequences. Journal of molecular biology, 1981, 147.1: 195-197.
[4] GOTOH, Osamu. An improved algorithm for matching biological sequences. Journal of molecular biology, 1982, 162.3: 705-708.
[5] ALTSCHUL, Stephen F., et al. Basic local alignment search tool. Journal of molecular biology, 1990, 215.3: 403-410.
[6] ALTSCHUL, Stephen F., et al. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic acids research, 1997, 25.17: 3389-3402.
[7] VOUZIS, Panagiotis D.; SAHINIDIS, Nikolaos V. GPU-BLAST: using graphics processors to accelerate protein sequence alignment. Bioinformatics, 2010, 27.2: 182-188.
[8] LIU, Weiguo; SCHMIDT, Bertil; MULLER-WITTIG, Wolfgang. CUDA-BLASTP: accelerating BLASTP on CUDA-enabled graphics hardware. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011, 8.6: 1678-1684.
[9] ZHANG, Jing; WANG, Hao; FENG, Wu-chun. cublastp: Fine-grained parallelization of protein sequence search on cpu+ gpu. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 2017, 14.4: 830-843.
[10] YE, Weicai, et al. H-BLAST: a fast protein sequence alignment toolkit on heterogeneous computers with GPUs. Bioinformatics, 2017, 33.8: 1130-1138.
[11] NVIDIA GPU (2012). WHAT IS GPU ACCELERATED COMPUTING? Available :
http://www.nvidia.com/object/what-is-gpu-computing.html (July 12, 2019)
[12] NVIDIA (2009). NVIDIA Cuda2.0 Program-ming Guide. Available :
http://developer.download.nvidia.com/compute/cuda/2_0/docs/NVIDIA_CUDA_Programming_Guide_2.0.pdf (July 12, 2019)
[13] NVIDIA (2012). NVIDIA Developer. Available : https://deve-oper.nvidia.com/ (July 12, 2019)
[14] HALFHILL, Tom R. Parallel Processing with CUDA, Nvidia's High-Performance Computing Platform uses Massive Multithreading. MICRO-PROCESSOR REPORT, 2008, 28.
[15] NVIDIA CUDA (2012). CUDA Parallel Com-puting Platform. Available :
http://www.nvidia.com/object/cuda_home_new.html (July 12, 2019)
[16] NVIDIA CUDA (2014). CUDA C Programming Guide. Available :
http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html (July 12, 2019)
[17] 陳昭佑、魏凱城、伍朝欽。 在 GPU 中使用 CUDA 去改善 CUDA-BLASTP。 Conference on Network and Information Security(CNIS)，2018。
[18] DE VERDIERE, Guillaume Colin. Introduction to GPGPU, a hardware and software background. Comptes Rendus Mécanique, 2011, 339.2-3: 78-89.
[19] 朱洵 (2015)。使用GPGPU 改善禁忌搜尋法解決工作排程問題之研究。彰化師範大學資工系研究所碩士論文，未出版，彰化市師大路二號。
[20] 程式前沿(Januar y 19, 2016 )。 CUDA 程式設計——GPU 架構，由sp，sm，thread，block，grid，warp 說起。 檢自:
https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/569806/ (July 12, 2019 )
[21] HONG, Sungpack, et al. Accelerating CUDA graph algorithms at maximum warp. In:
Acm Sigplan Notices. ACM, 2011. p. 267-276.
[22] Evy A. Salcedo T. (n.d.). Introdução a CUDA. Available :
http://www.pbxbrasil.com/Pesquisa/Ferramentas/cuda/dia02/aulasCuda/arquitetura/arquitetura.html (July 12, 2019)
[23] Heresy (July 09, 2008)。 CUDA 的 Threading：Block 和Grid 的設定與 Warp。檢自:
http://viml.nchc.org.tw/blog/paper_info.php?CLASS_ID=1&SUB_ID=1&PAPER_ID=72 (July 12, 2019 )
[24] GLASCO, David. An Analysis of BLASTP Implementation on NVIDIA GPUs. 2012.
[25] UniProt (July 03, 2019). UniProtKB/Swiss-Prot UniProt release 2019_06. Available :
https://www.uniprot.org/statistics/Swiss-Prot (July 12, 2019)
[26] 劉妍芳、魏凱城、伍朝欽。 BLAST 索引表於GPU 中之設計。 工程應用科技研討會，2019，p. 157-161。
[27] 華人百科(無日期)。 SwissProt。檢自: https://www.itsfun.com.tw/SwissProt/wiki-3449375-9963055 (July 12, 2019)
[28] Xu, D., et al. (n.d.). Genome Composite Distance Phylogeny. Available :
http://digbio.missouri.edu/ComPhy/ (July 12, 2019)