臺灣博碩士論文加值系統

蛋白質的功能與胺基酸鍊的摺疊結構有密切的關係，因此對於蛋白質結構的研究，有助於我們對蛋白質功能的瞭解。而蛋白質結構比對演算法就是其中一種很重要的蛋白質結構研究工具。
本論文提出一種蛋白質局部結構比對的方法，目的是想要找出具有相同生化功能的蛋白質，它們所共有的局部結構片段；之後更進一步利用這些找出來的片段，來做蛋白質功能的預測。整個演算法我們可以分為四大步驟，一、以pair-wise的方式找出蛋白質相似的局部結構片段。二、找出局部結構片段之間的相似性。三、局部結構片段的分群。四、找出代表性的pattern。
在實驗方面，針對已知的蛋白脢，我們將找出來的片段與具有生化功能的基質用jmol3D蛋白質檢視工具顯示出來，可以發現我們所找出來的片段都會在基質的附近，這表示我們所找出來的片段，確實具有某程度的生物意義。另外，將我們的演算法與林育星 95年的「利用蛋白質序列與結構關係預測酵素種類」演算法做比較。我們也確實能補足他的演算法在某些EC number中無法找出pattern的缺陷。

The functions of proteins are mainly affected by their structures. Therefore, the study of protein structures is helpful to realize the protein function. Protein structure comparison algorithm is one of the important tools in protein structure research.
In this thesis, we introduce a protein local structure comparison method. We try to find the common local substructures from proteins which have the same biochemical function. And then we can use those substructures to predict the protein function. In our algorithm has four main steps：1. pair-wise protein local structure comparison to find the common local substructures. 2. calculate the similarity between substructures. 3. cluster substructures by similarity 4. find the representative pattern.
In our experiment, we use the protein 3D viewer Jmol to show the location of patterns which we find and substrate. We can find out that patterns are near the substrates. Therefore, we can announce the patterns have some biochemical meaning. In addition, we compared our algorithm with 「Enzyme class prediction via mining conserved region in sequence and structure」algorithm（Lin ,2006）. We can find patterns from the EC numbers which it can’t find any patterns.

目錄 iv
圖表目錄 vi
表目錄 vii
Chapter 1 緒論 1
1.1. 研究背景 1
1.2. 研究動機與目的 1
1.3. 論文架構 2
Chapter 2 蛋白質結構比對之相關研究 3
2.1. 相關演算法研究 3
2.1.1. 相關名詞定義 3
2.1.2. 相似度定義 5
2.1.3. 動態規劃演算法 (Dynamic programming) 7
2.1.4. 幾何雜湊演算法(Geometric hashing) 8
2.1.5. Enzyme Classification（EC）numbers 10
2.1.6. 修正(Refinement) 10
2.2. 分群演算法 11
2.2.1. K-Means 11
2.2.2. 階層式的分群 11
2.3. 蛋白質結構比對演算法的種類 13
2.4. 以胺基酸序列片段為基礎的蛋白質結構比對演算法 15
2.4.1. ProSup 16
2.4.2. FLASH（Fast alignment for finding structural homology of proteins） 16
2.4.3. 複雜度分析 17
2.5. 以局部結構比對為基礎的蛋白質結構比對演算法 17
2.5.1. 利用蛋白質序列與結構關係預測酵素種類[22] 18
Chapter 3 以局部結構比對為基礎的蛋白質功能性片段的尋找與應用 21
3.1. 問題定義 21
3.2. Flow chart of proposed protein local structure comparison and predict method 22
3.3. 以橢圓模型為基礎的蛋白質結構局部比對（A protein local structure comparison method based on hyper-ellipsoidal clusters） 23
3.3.1. Flow chart of protein local structure comparison 23
3.3.2. 對蛋白質上的二級結構與Coils做分群 24
3.3.3. 篩選座標系 26
3.3.4. 蛋白質結構比對 27
3.4. 求片段之間的相似關係（Find the similarity of all substructures） 29
3.5. 片段分群（Substructure Clustering） 30
3.6. 尋找代表性局部相似結構（fine representative pattern） 30
3.7. 未知蛋白質功能預測（protein function predict） 31
Chapter 4 實驗 32
4.1. 實驗一、利用EC number找pattern 32
4.2. 實驗二、與其它演算法做比較 36
4.2.1. 找不到pattern的EC number 36
4.2.2. 找的到pattern的EC number 37
4.2.3. 討論： 39
4.3. 實驗三、未知蛋白質功能預測 39
Chapter 5 結論與未來展望: 41
5.1. 結果討論 41
5.2. 相關比較 41
5.3. 改進方式 42
5.3.1. 事先做整體序列比對 42
5.3.2. 局部結構片段比對速度提升 43
5.4. 未來展望 43
5.4.1. 建立pattern資料庫 43
5.4.2. 將pattern依EC number的階層做分類 43
5.4.3. 套用binding site資訊 44
參考資料 45

1.C. Brändén and J. Tooze, Introduction to protein structure. Second edition. 1999: Garland Publishing, New York.
2.Lesk, A.M., Introduction to Protein Architecture. 2001: Oxford University Press,USA.
3.Chen, I., A protein structure comparison method based on hyper-ellipsoidal clusters. 2004.
4.Wang, J.-N., A Study for Protein Structural Comparison Algorithms- A New Approach for Rough structural Comparison. 2005.
5.Berman, H.M., et al., The Protein Data Bank. Nucleic Acids Res, 2000. 28(1): p. 235-42.
6.Ingvar Eidhammer, Inge Jonassen, and W.R. Taylor, Protein Bioinformatics:An Alogorithmic Approach to Sequence and Structure Analysis. 2004.
7.Zuker, M. and R.L. Somorjai, The alignment of protein structures in three dimensions. Bull Math Biol, 1989. 51(1): p. 55-78.
8.Bairoch, A., The ENZYME data bank in 1999. Nucleic Acids Res, 1999. 27(1): p. 310-1.
9.Martin, A.C., PDBSprotEC: a Web-accessible database linking PDB chains to EC numbers via SwissProt. Bioinformatics, 2004. 20(6): p. 986-8.
10.Li, W., L. Jaroszewski, and A. Godzik, Clustering of highly homologous sequences to reduce the size of large protein databases. Bioinformatics, 2001. 17(3): p. 282-3.
11.Gerstein, M. and M. Levitt, Comprehensive assessment of automatic structural alignment against a manual standard, the scop classification of proteins. Protein Sci, 1998. 7(2): p. 445-56.
12.Jewett, A.I., C.C. Huang, and T.E. Ferrin, MINRMS: an efficient algorithm for determining protein structure similarity using root-mean-squared-distance. Bioinformatics, 2003. 19(5): p. 625-34.
13.WR, T., Protein structure comparison using iterated double dynamic programming. Protein Sci, 1999. 8: p. 654-665.
14.Falicov, A. and F.E. Cohen, A surface of minimum area metric for the structural comparison of proteins. J Mol Biol, 1996. 258(5): p. 871-92.
15.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.
16.Grindley HM, et al., Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J Mol Biol, 1993. 229: p. 707–721.
17.Escalier, V., et al., Pairwise and multiple identification of three-dimensional common substructures in proteins. J Comput Biol, 1998. 5(1): p. 41-56.
18.Holm, L. and C. Sander, Protein structure comparison by alignment of distance matrices. J Mol Biol, 1993. 233(1): p. 123-38.
19.Rackovsky, S. and D.A. Goldstein, Protein comparison and classification: a differential geometric approach. Proc Natl Acad Sci U S A, 1988. 85(3): p. 777-81.
20.Zhu, J. and Z. Weng, FAST: a novel protein structure alignment algorithm. Proteins, 2005. 58(3): p. 618-27.
21.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.
22.林育星, 利用蛋白質序列與結構關係預測酵素種類. 2006.
23.Jonassen, I., et al., Structure motif discovery and mining the PDB. Bioinformatics, 2002. 18(2): p. 362-7.
24.R.O. Duda, P.E.H., D.G. Stork, Pattern classification. Second edition. 2001: Wiley-Interscience Publication.