臺灣博碩士論文加值系統

隨著蛋白質資料的快速增加，有效的分析蛋白質之間的關係成為了一個重要的標的，而蛋白質結構比對則是分析蛋白質的關係之中重要的方法之一。藉由有效的計算兩個蛋白質結構的相似度，可以得知這兩個蛋白質在演化上的關係如何，以藉此推斷兩個蛋白質功能上的相似性。而蛋白質結構比對最重要的因素是快速與準確，因此本研究使用了幾何雜湊這個演算法來比對蛋白質結構。幾何雜湊演算法本來是用在電腦視覺領域，用來比對兩個空間中的結構，是目前最主要的結構比對的演算法。而本論文改良了幾何雜湊演算法，提升了它的準確率，並對不同的蛋白質結構比對，設計了幾個不同的幾何雜湊比對法。最後提出了一個蛋白質位元向量的概念，藉由本研究所提出的蛋白質位元向量，可以快速的推算出兩個蛋白質結構的相似度，來判斷有無進行更精確的比對的需求。在實驗部分，本論文使用了數個蛋白質資料庫(Protein Data Bank)中的資訊來進行比對，而所得到的實驗結果都不錯。藉由本研究所提出的蛋白質結構比對工具，可以有效的讓生化學家在蛋白質分析上有遠大的助力。

With the fast increasing of proteins’ data, effectively analyzing the relation between proteins has become an important issue. One important approach to analyze the relation between proteins is protein structure comparison(PSC). By calculating the similarity between two protein’s structures, we can get the relationship between two structures in evolution. According to these information, we can inference these proteins may possess some similar function.
The most important issue of protein structure comparison is fast and preciseness. Therefore, the geometric hashing algorithm was proposed to align two protein structures. Geometric hashing is a technique based on computer vision, used to compare two structures. We improve the geometric hash algorithm, especially increasing the accuracy. We also proposed several variant geometric hashing algorithms for protein structure comparison of different purpose. Finally, we propose bit-vector-based similarity estimation for fast PSC.
In our experiments, we use compare several proteins from PDB(Protein Data Bank), and get some good results. The proposed algorithms are well coded and provided on the web. Molecular biologist can leverage our research results by using the provided tool.

目錄 1
圖表目錄 3
表目錄 4
Chapter 1 導論 5
Chapter 2 相關研究 7
2.1. 蛋白質結構相關研究 7
2.1.1. 定義 7
2.1.2. 蛋白質結構的相關研究 8
2.1.3. 蛋白質結構的相關技巧 9
2.1.4. Root Mean Square Deviation (RMSD) 10
2.2. 幾何雜湊的相關研究 11
2.2.1. 幾何雜湊(Geometric Hashing)的基本原理與相關文獻 11
2.2.2. 幾何雜湊的應用：分子生化資訊 18
2.2.3. 幾何雜湊的變形 18
Chapter 3 問題定義 20
3.1. 定義 20
3.2. 快速的三維結構比對技術 20
3.3. 數學定義 21
3.3.1. 雜湊函式定義 21
3.3.2. 點與點之間視為相對的方式 22
3.3.3. 再雜湊(Rehashing) 23
Chapter 4 幾何雜湊方法的定義與變化 25
4.1. 雜湊表定義 25
4.1.1. 以距離為雜湊函式 25
4.1.2. 以直角座標為雜湊函式 26
4.1.3. 以極座標為雜湊函式 28
4.1.4. 以極座標為雜湊函式-變形 30
4.2. 整體演算法流程 33
Chapter 5 實驗與討論 35
5.1. 跟原本的幾何雜湊比較的結果 35
5.2. 各種的蛋白質結構比對上的應用 37
5.2.1. 應用一：對固定大小的小型蛋白質結構所進行之比對 37
5.2.2. 應用二：在大型蛋白質結構中進行小片段比對 44
5.2.3. 利用蛋白質的位元向量來判斷彼此的相似度 48
5.3. 雜湊函式比較 51
5.3.1. 參數設定 51
5.3.2. 實驗結果 51
5.4. 雜湊的限制 55
Chapter 6 應用 56
6.1. 應用的核心 56
6.2. API的發表 56
Chapter 7 結論與未來方向 57
7.1. 總結貢獻 57
7.2. 未來方向 57
相關文獻 59

1.Branden, C. and J. Tooze, Introduction to protein structure. Garland Publishing, New York, London., 1999.
2.Berman, H.M., et al., The Protein Data Bank. Acta Crystallogr D Biol Crystallogr, 2002. 58(Pt 6 No 1): p. 899-907.
3.Can, T. and Y.F. Wang, CTSS: A Robust and Efficient Method for Protein Structure Alignment Based on Local Geometrical and Biological Features. Proc IEEE Comput Soc Bioinform Conf, 2003. 2: p. 169-79.
4.Remington, S.J. and B.W. Matthews, A systematic approach to the comparison of protein structures. J Mol Biol, 1980. 140(1): p. 77-99.
5.Alexandrov, N.N., K. Takahashi, and N. Go, Common spatial arrangements of backbone fragments in homologous and non-homologous proteins. J Mol Biol, 1992. 225(1): p. 5-9.
6.Alexandrov, N.N. and D. Fischer, Analysis of topological and nontopological structural similarities in the PDB: new examples with old structures. Proteins, 1996. 25(3): p. 354-65.
7.Shih, E.S. and M.J. Hwang, Protein structure comparison by probability-based matching of secondary structure elements. Bioinformatics, 2003. 19(6): p. 735-41.
8.Mizuguchi, K. and N. Go, Comparison of spatial arrangements of secondary structural elements in proteins. Protein Eng, 1995. 8(4): p. 353-62.
9.Wang, J.-N., A Study for Protein Structural Comparison Algorithms- A New Approach for Rough structural Comparison. 2005.
10.Bachar, O., et al., A computer vision based technique for 3-D sequence-independent structural comparison of proteins. Protein Eng, 1993. 6(3): p. 279-88.
11.Pennec, X. and N. Ayache, A geometric algorithm to find small but highly similar 3D substructures in proteins. Bioinformatics, 1998. 14(6): p. 516-22.
12.Dror, O., et al., Multiple structural alignment by secondary structures: algorithm and applications. Protein Sci, 2003. 12(11): p. 2492-507.
13.Rigoutsas., I. and R. Hummel., Implementation of geometric hashing on the connection machine. Workshop on Directions in Automated Cad-based Vision., 1991.
14.Rigoutsos., I. and R. Hummel. Robust similarity invariant matching in the presence of noise. in Proceedings of the 8th Israeli Conference on Artificial Intelligence and Computer Vision. 1991.
15.George Bebis, M. Georgiopoulost., and N.d.V. Lobo. Learning Geometric Hashing Functions for Model-Based Object Recognition. in Computer Vision, 1995. Proceedings., Fifth International Conference on. 1995.
16.林育星, 利用蛋白質序列與與結構關係預測酵素種類. 2006.
17.Jonassen, I., et al., Structure motif discovery and mining the PDB. Bioinformatics, 2002. 18(2): p. 362-7.
18.Bairoch, A., The ENZYME data bank in 1999. Nucleic Acids Res, 1999. 27(1): p. 310-1.
19.許智鈞, Identification and Application of Functional Protein substructure base on Local Structure Comparison. 2006.