蛋白質為生命構成的主要物質，也是生命活動的主要承擔者，研究蛋白質分子的三維結構和功能對於我們對疾病的瞭解或是生物製藥的過程有很大的幫助。而目前解析出蛋白質三維結構的方法，除了利用資訊科學的統計學習理論去預測其結構，科學家們在實際上大部分是由X光線繞射(X-ray diffraction)或是核磁共振(NMR)所實驗定義出來的。其中核磁共振這個方法,可能會耗上數個禮拜到數個月，才能夠解出一個蛋白質的三維結構，不僅耗時且花費成本，而且不一定能解析出蛋白質結構。但如果是此蛋白質的溶液可以析出結晶，科學家們可以使用X光繞射的方法對此結晶進行分析，便只需要幾個小時便可以解出此蛋白質的三維結構。但是有很多的蛋白質並沒有辦法產生結晶，所以在蛋白質結構定義的過程中對於蛋白質結晶與否的預測是一個重要的問題。
  我們希望經由蛋白質的一級結構，也就是胺基酸(Amino Acid)序列的資料，使用支援向量機(Support Vector Machine, SVM) ，利用空間轉換的觀念，使用一個平面去將可以結晶和不能結晶的兩個蛋白質類別做切割，達到分類的效果。而去預測此蛋白質是否可以結晶,可以結晶的話，便不需要大費周章的去用NMR來解出蛋白質的結構，更快的取得蛋白質三維結構資訊。
  在最後我們希望找出更多蛋白質本身影響結晶的特性，無論化學或是物理性質，經由胺基酸序列所能提供給我們的資訊來編碼，進一步的提升預測蛋白質結晶的準確率。接著我們希望經過特徵選取(Feature Selection)的方式，根據特徵選取後預測的準確率，挑出其中真正大部分影響結晶的特徵值，藉由這些特徵值，來幫助做蛋白質結晶時的外在條件篩選。最後我們使用支援向量機做出來的5-Fold成果為79.5%，對於可以產生結晶的蛋白質族群預測率為80.8%，而對於無法結晶的蛋白質族群預測率為78.3%。這個實驗的最終目的，就是希望找出影響蛋白質非結晶的要素，更進一步的想辦法去改善這些造成蛋白質無法結晶的因素，幫助科學家們可以將這個蛋白質析出結晶，以更快速的利用X光繞射的方法取得蛋白質結構的資訊。

In structural genomics, proteins are essential materials that define life. A protein’s function is strongly related to it’s structure. The ultimate goal of structural research is to determine the three-dimensional structure of a protein. However, structure determination is often a time-consuming and expensive process. Also the process of experimental determination of protein structure has a high ratio of failures at different stages.
  There are two prevalent methods for protein structure determination - the magnetic resonance (NMR) spectroscopy and X-ray crystallography. The NMR protein structure determination requires weeks of data acquisition, expensive stable isotope labeling, and extensive manual analysis of data. On the other hand, X-ray crystallography is by far the most successful approach to structure determination. But X-ray crystallography has an importance condition. That is the protein target must be crystallized first. Then the resulting crystal must diffract to sufficient resolution. Therefore, prediction of protein crystallization is an essential problem for structural research. 
  Protein Data Bank (PDB) provides us detailed protein sequence information. We use information from a protein’s primary structure, i.e. the amino acid sequence, as the input to the support vector machine to predict the protein’s crystallizability. Several protein features that correlate with protein crystallization are identified first. The support vector machine then generates a hyperplane in the feature space to predict the protein sequence’s crystallizability. We also investigated two feature selection methods - the wrapper method and the filter method. The purpose is to remove irrelevant and redundant features, and thus reduce dimensionality of the input data. A feature subset can be resulted to make the support vector machine result in higher prediction accuracy. The feature selection approach can also help us recognize which protein features are more important for protein crystallization. This can help the chemist to understand the key factors of protein crystallization. An overall prediction accuracy of 79% was achieved on a screened PDB data set with 5-fold cross-validation. The true-positive rate (crystallization) is 80.8% and the true-negative (non-crystllizable) rate is 78.4%.

目錄
第一章 緒論	1
1.1研究背景	1
1.2研究動機	2
1.3 論文組織架構	3
第二章 文獻分析	5
2.1 基因結構體學	5
2.1.1 找出蛋白質結構的方法	7
2.2 蛋白質結晶的原理	10
2.3 支持向量機	12
2.3.1 核心函數(Kernel)	17
2.4 蛋白質結晶預測的方法	18
第三章 預測蛋白質結晶的方法	24
3.1 資料的前處理	24
3.1.1 蛋白質長度以及同源的篩選	26
3.2 影響蛋白質結晶的因素	28
3.3 不平衡資料集的解決方法	32
3.3.1 重新取樣	33
3.3.2 Synthetic Minority Over-sampling Technique (SMOTE)	36
3.3.3 One-Class Support Vector Machine (OCSVM)	40
3.3.4 調整權重(Weighting)	43
3.4 特徵選取(Feature Selection)	45
3.4.1 過濾方法(Filter Method)	46
3.4.2 包裝方法(Wrapper Method)	48
第四章 系統架構與實驗結果	52
4.1 系統架構	52
4.2 蛋白質序列編碼	54
4.3 實驗結果與討論	61
第五章 結論與未來展望	69
參考文獻	71
附錄 英文論文	76
 
圖目錄
圖2.1 轉錄與轉譯的過程 	7
圖2.2 X-Ray解析蛋白質結構流程圖 	8
圖2.3 X-Ray入射波示意圖	 8
圖2.4 原子核自轉受到磁場影響後的改變 	9
圖2.5 原子核能階示意圖 	10
圖2.6 依能階高低轉換出來的波峰圖 	10
圖2.7 蛋白質溶液過飽和析出結晶	 12
圖2.8 三個資料點可線性分割的情況	 14
圖2.9 四個資料點無法線性分割的情況 	14
圖2.10 區分超平面 	17
圖2.11 資料點經過核心函數在空間中的轉換 	18
圖2.12 XtalPred的蛋白質預測網頁工具  	23
圖3.1 蛋白質序列同源的情況	 28
圖3.2 資料點在特徵空間上的位置 	36
圖3.3 ROC曲面圖 	38
圖3.4 在特徵空間上製作人工樣本	 39
圖3.5 階層式的支持向量機	41
圖3.6 One-Class SVM所訓練出的模組	 42
圖3.7 經權重調整後的超平面區間改變 	44
圖3.8 資料點在不同特徵空間的分佈 	47
圖3.9 資料點在特徵空間中的亂度分佈情況 	48
圖3.10 包裝演算法的流程 	49
圖3.11 最佳向前搜尋演算法的示意圖 	51
圖4.1 支援向量機訓練預測流程圖 	53
圖4.2 PDB蛋白質不規則序列資訊 	57
圖4.3 編碼前的檔案格式 	60
圖4.4 編碼後的檔案格式 	60
圖4.5 TargetDB檔案格式 	66

 
表目錄
表2.1 CRYSTALP的胺基酸對特徵  	21
表3.1 蛋白質突變應用在蛋白質結晶上的例子  	30
表3.2 蛋白質序列的截斷與刪除應用在蛋白質結晶上的例子 	31
表3.3 蛋白質融合應用在蛋白質結晶上的例子 	 32
表4.1 不同的親水性定義 	56
表4.2 胺基酸的解離常數 	59
表4.3 權重調整前後的結果 	62
表4.4 單一特徵預測準確率 	63
表4.5 加上特徵值pI前後的準確率 	64
表4.6 與SECRET和CRYSTALP方法比較結果 	65
表4.7 TargetDB測試資料集結果 	68

[1] J.M. Chandonia and S.E. Brenner, “The impact of structural genomics: Expectations and Outcomes,” Science, 311: 347-351, 2006.
[2] W.L. Bragg, “The structure of some crystals as indicated by their diffraction of X-rays,” Proceedings of the Royal Society (London), A89:248–277, 1914.
[3] J.M. Tyszka, S.E. Fraser and R.E. Jacobs,“Magnetic resonance microscopy: recent advances and  applications,”Current Opinion in Biotechnology, 16(1): 93-99, 2006.
[4] A. McPherson, “Introduction to protein crystallization,” Methods, 34:254–265, 2004.
[5] E. Alpaydın, Introduction to Machine Learning (Adaptive Computation and Machine Learning), MIT Press, 2004.
[6] V. Vapnik, The Nature of Statistical Learning Theory, Springer Verlag , 1999.
[7] Vapnik and Chervonekis, “Structural risk minimization, SRM,” http://www.svms.org/srm/, 1974.
[8] I.V. Tetko, D.J. Livingstone and A.I. Luik, “Neural network studies. 1. Comparison of Overfitting and Overtraining, ” J. Chem. Inf. Comput. Sci., 35:826-833, 1995. 
[9] C. Cortes and V. Vapnik, “Support-Vector Networks, ” Machine Learning, 20, 1995. http://www.springerlink.com/content/k238jx04hm87j80g/
[10]P. Smialowski, T. Schmidt, J. Cox, A. Kirschner, and D. Frishman1, “Will My Protein Crystallize? A Sequence-Based Predictor,” PROTEINS: Structure, Function, and Bioinformatics, 62:343–355, 2006.
[11]K. Chen, L. Kurgan and M. Rahbari, “Prediction of protein crystallization using collocation of amino acid pairs,” Biochemical and biophysical research communications, 355:764-769, 2007.
[12]I.M. Overton and G.J. Barton, “A normalised scale for structural genomics target ranking: The OB-Score,” FEBS Letters, 580:4005–4009, 2006.
[13]L. Slabinski1, L. Jaroszewski, L. Rychlewski, I.A. Wilson, S.A. Lesley and A. Godzik, “XtalPred: a web server for prediction of protein crystallizability,” Bioinformatics Applications Note, 23:3403–3405, 2007.
[14]W. Li and A. Godzik, “Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences.” Bioinformatics, 22:1658-9, 2006.
[15]G.E. Dale, C. Oefner and A. D'Arcy, “The protein as a variable in protein crystallization,” Journal of Structural Biology, 142:88–97, 2003.
[16]Guoxun He, Hui Han and Wenyuan Wang, “An over-sampling expert system for learning from imbalanced data sets,” Neural Networks and Brain, 1:537- 541, 2005.
[17]N.V. Chawla, K.W. Bowyer, L.O. Hall and W.P. Kegelmeyer, “SMOTE: synthetic minority over-sampling technique,” Journal of Artificial Intelligence Research, 16:321–357, 2002.
[18] L.M. Manevitz and M. Yousef “One-Class SVMs for document classification,” Journal of Machine Learning Research, 2:139-154, 2001.
[19]Xue-wen Chen, Byron Gerlach and David Casasent, “Pruning support vectors for imbalanced data classification,” Proceedings of International Joint Conference on Neural Networks, Montreal, Canada, 2005.
[20] M. Dash, K. Choi and P. Scheuermann & Huan Liu,“Feature selection for clustering—A filter solution” Data Mining, 2002. ICDM 2002. Proceedings. 2002 IEEE International Conference, 115-122, 2002.
[21]R. Kohav and G.H.John, “Wrappers for feature subset selection” Artificial Intelligence, 97:273-324, 1997.
[22] Engelman D.M., Steitz T.A. and Goldman A., “Identifying nonpolar transbilayer helices in amino acid sequences of membrane proteins, ”Annu Rev Biophys Biophys Chem, 15:321–353,1986.
[23] Kyte J. and Doolittle R.F., “A simple method for displaying the hydropathic character of a protein,” J Mol Biol, 157:105–132, 1982.
[24] Rose G.D., Geselowitz A.R., Lesser G.J., Lee R.H. and Zehfus M.H., “Hydrophobicity of amino acid residues in globular proteins, ”Science, 229:834–838, 1985.
[25] Gilis D., Massar S., Cerf N.J. and Rooman M., “Optimality of the genetic code with respect to protein stability and amino-acid frequencies,” Genome Biol, 2:RESEARCH0049, 2001.
[26] Katherine A., Kantardjieff and Bernhard Rupp, “Protein isoelectric point as a predictor for increased crystallization screening efficiency,” Bioinformatics Applications Note, 20:2162–2168, 2004.