臺灣博碩士論文加值系統

近幾年中，由於在生物資訊領域的研究與發展與日俱增，以至於藉由大量運算來求得更好的效能的需求亦不斷地持續成長，基因序列比對就是一個明顯的例子。基於叢集技術可以減少執行時間和增進基因序列比對的效率，所以此類的需求通常使用平行計算的技術來解決。例如，mpiBLAST 就是一個結合NCBI BLAST軟體和平行計算訊息交換介面標準所實作出來的平行版BLAST軟體。然而，大部分的實驗室都沒有足夠的能力來建造一個具有強大計算能力的叢集環境，因此他們往往都是用數十台甚至是上百台個人電腦來建構出一個看似計算能力不錯的叢集環境。而且叢集環境通常受限於本地端環境，所以此一限制將嚴重阻礙計算能力的擴充性，不過這些缺點和限制可以由格網架構的概念來解決。
在格網環境中，散佈各地之虛擬組織的資源可以透過格網的概念來調派和集中，因此可以滿足各種在生物資訊應用方面的計算需求。在這篇論文中，我們將開發一個名為G-BLAST的生物格網架構。目前，G-BLAST是針對在格網環境上執行序列比對的工作而設計，而其最終則是透過一台伺服器來連接應用在各叢集節點上的mpiBLAST來完成序列比對的工作。此外，G-BLAST 還具有選擇最適合的工作節點、根據不同節點的效能來動態切割基因資料庫以及根據以往所執行的歷史紀錄來動態調整每個所屬於G-BLAST底下之工作節點的效能值等能力。為了加強G-BLAST的使用性，我們開發一個格網服務的入口和一個網格服務的圖型使用者介面應用軟體；使用者可以透過此介面來遞交工作、觀察工作的狀態以及接收比對結果，而系統管理者則可以透過此介面來管理他們自己的工作節點和觀察工作節點的使用況。此外，我們的介面和G-BLAST是透過WSRF的標準來溝通。

The research and development of bioinformatics (e.g., genomic sequence alignment) has been growing with each passing day in the past few years so that continue demands on large computing powers are required to support better performance. This trend requires usually solved by parallel computing techniques, because Cluster technology can reduce the execution time and increase genomic sequence alignment efficiency. For example, mpiBLAST is a parallel version of NCBI BLAST that combines the NCBI BLAST with Message Passing Interface standards. However, most laboratories can not build up powerful computing environments. They usually connect dozens or even hundreds of personal computers to build weak computing environments. Besides, Cluster usually is limited by a local computing environment that hinders the computing extendibility significantly. The concepts of the Grid framework are designated to overcome the aforementioned problems. Grid environments coordinate the resources of distributed virtual organizations and satisfy various computational demands for bioinformatics applications. In this thesis, we have deployed a BioGrid framework named G-BLAST. Currently, G-BLAST is designed for genomic sequence alignment by using the Grid environment and accessible mpiBLAST application, which is designed for Cluster environment, from a server node. G-BLAST is endowed with selection the most adaptive work nodes, dynamic fragmenting genomic database, and self-adjust performance data abilities. To enhance the capability and usability of G-BLAST, we also deployed a Grid Service Portal and a Grid Service GUI desk application for general users to submit jobs and for host administrators to maintain their own work nodes.

摘要 i
Abstract ii
Acknowledgements iii
Contents iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 The Goal and Contributions 3
1.3 Thesis and Organization 4
Chapter 2 Background Review 5
2.1 Grid Computing 5
2.2 Grid Middleware 6
2.3 WSRF 7
2.4 Cluster Computing 8
2.5 mpiBLAST 9
Chapter 3 Design and Implementation of G-BLAST 13
3.1 User Portal 15
3.2 Schedule System 16
3.3 Information System 19
3.4 Job Dispatch System 21
3.5 Segmentation Database System 23
3.6 Job Monitor System 27
3.7 Combination Results System 27
3.8 mpiBLAST Cluster System 27
3.8.1 mpiBLAST Server 28
3.8.2 mpiBLAST Client 28
Chapter 4 Experimental Environments 29
4.1 mpiBLAST on PC Cluster Environment 29
4.2 G-BLAST on Grid Environment 31
Chapter 5 Experimental Results 33
5.1 mpiBLAST on PC Cluster Environment (Query: nt.5706771) 33
5.2 G-BLAST on Grid Environment (Query: nt.5706771) 36
5.3 mpiBLAST on PC Cluster Environment (Query: nt.ests) 37
5.4 G-BLAST on Grid Environment (Query: nt.ests) 39
5.5 Learning Curve 41
5.6 Discussions 44
Chapter 6 Conclusions and Future Work 46
Bibliography 47

[1]A Sturn, B Mlecnik, R Pieler, J Rainer, T Truskaller, Z. Trajanoski, “Client-Server Environment for High-Performance Gene Expression Data Analysis,” Bioinformatics, 2003, 19(6):772-773.
[2]K. Fumikazu, Y. Tomoyuki, F. Akinobu, D. Xavier, S. Kenji, and K. Akihiko, “OBIGrid: A New Computing Platform for Bioinformatics,” Genome Informatics, 13:484-485, 2002.
[3]S. Gernot, R. Dietmar, and T. Zlatko, “ClusterControl: A Web Interface for Distributing and Monitoring Bioinformatics Applications on a Linux Cluster,” Bioinformatics, 20(5):805-807, 2004.
[4]R. Buyya, “High Performance cluster Computing: System and Architectures,” Vol. 1, Prentice Hall PTR, NJ, 1999.
[5]R. Prodan and T. Fahringer, “ZENTURIO: An Experiment Management System for cluster and Grid Computing,” Proceedings of IEEE International Conference on cluster Computing (CLUSTER’02), pp. 9-18, Chicago, Illinois, USA, 2002.
[6]F. Achard, G. Vaysseis, and E. Barillot, “XML, bioinformatics and data integration,” Bioinformatics, vol. 17 no.2 2001 Pages 115-125.
[7]G. Kandaswamy, L. Fang, Y. Huang, S. Shirasuna, S. Marru, and D. Gannon, “Building web service for scientific grid applications,” International Business Machines Corporation, 2006, VOL. 50
[8]J. Andrade, L. Berglund, M. Uhlen, and J. Odebrg, “The use of the Grid technology to solve computationally and data intensive bioinformatics tasks,” Workshop on state-of-the-art in scientific and parallel computing, 2006
[9]A. Krishnan, “GridBLAST: a Globus-based high-throughput implementation of BLAST in a Grid computing framework,” Concurrency and Computation: Practice and Experience, 2005, 17(13), pp. 1607-1623
[10]C. Oehmen and J. Nieplochs, “ScalaBLAST: A Scalable Implementation of BLAST for High-Performance Data-Intensive Bioinformatics Analysis,” IEEE Transactions on Parallel and Distributed Systems, 2006, vol. 17, no. 8, pp. 740-749.
[11]Y. Sun, S. Zhao, H. Yu, G. Gao, and J. Luo, “ABCGrid: Application for Bioinformatics Computing Grid,” Bioinformatics, 2007, 23(5): 1175 – 1177
[12]J. Wang, and Q. Mu, “Soap-HT-BLAST: high throughput BLAST based on Web services,” Bioinformatics, 2003, 19(14): 1863-1864.
[13]NCBI BLAST, http://130.14.29.110/BLAST/.
[14]mpiBLAST, http://mpiblast.lanl.gov/.
[15]MPI, http://www.lam-mpi.org/.
[16]I. Foster, “The Grid: A New Infrastructure for 21st Century Science,” Physics Today, 55(2):42-47, 2002.
[17]I. Foster and C. Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure (Elsevier Series in Grid Computing), Morgan Kaufmann, 2nd edition, 2003.
[18]GT4, http://www.globus.org/
[19]C. T. Yang, Y. L. Kuo, K. C. Li, and J. L. Gaudiot, “On Design of Cluster and Grid Computing Environments for Bioinformatics Applications,” Distributed Computing - IWDC 2004: 6th International Workshop, Lecture Notes in Computer Science, Springer-Verlag, Arunabha Sen, Nabanita Das, Sajal K. Das, et al. (Eds.), Kolkata, India, vol. 3326, pp. 82-87, Dec. 27-30, 2004.
[20]R. Nobrega, J. Barbosa, and P. Monteiro, “BioGrid Application Toolkit: a Grid-based Problem Solving Environment Tool for Biomedical Data Analysis,” VECPAR, 2006
[21]P. Bala, J. Pytlinski, M. Nazaruk, V. Alessandrini, D. Girou, D. Erwin, D. Mallmann, J. MacLaren, J. Brooke, and J. Myklebust, “BioGRID - An European Grid for Molecular Biology,” Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, 2002, pp. 412.
[22]C.T. Yang, Y.L. Kuo, and C.L. Lai, “Designing Computing Platform for BioGrid,” International Journal of Computer Applications in Technology, 2005, vol. 22, no. 1, pp. 3-13.
[23]WSRF, http://www.globus.org/wsrf/.
[24]I. Foster and C. Kesselman, “Globus: A metacomputing infrastructure toolkit,” The International Journal of Supercomputer Applications and High Performance Computing, 11(2):115–128, summer 1997.
[25]N. Karonis, B. Toonen, and I. Foster, “MPICH-G2: A Grid-Enabled Implementation of the Message Passing Interface,” Journal of Parallel and Distributed Computing (JPDC), Vol. 63, No. 5, pp. 551-563, May 2003.
[26]C. T. Yang, Y. L. Kuo and C. L. Lai, “Design and Implementation of a Computational Grid for Bioinformatics,” Proceedings of the 2004 IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE 04), pp. 448-451, Grand Hotel, Taipei, Taiwan, March 28-31, 2004.
[27]NCBI, http://www.ncbi.nlm.nih.gov/.
[28]http://www.oasis-open.org/
[29]http://www.epm.ornl.gov/pvm