臺灣博碩士論文加值系統

真核細胞(Eukaryotic cells)中的主要亞細胞(subcellular)部分有細胞核(Nucleus)、細胞質(Cytoplasm)與粒線體(Mitochondrion)。在分子細胞生物領域，確認蛋白質序列在亞細胞的位置(location)是主要目標之一﹔因為蛋白質序列在亞細胞的位置與其在細胞內所扮演的角色相關，其所得到的知識應用到新的蛋白質序列有助於迅速基礎研究與藥物研發。細胞核是重要的亞細胞之一，是一個相當複雜的胞器負責包裹細胞各種生命過程與其相關的調控因素。所以，預測蛋白質序列在亞細胞與亞細胞核中的位置是相當重要的問題。
從蛋白質序列來進行計算預測是可經濟地確認其未知的功能。正確的預測方法不僅強調有效能特徵與高效能的分類器，可以擷取高效能特徵子集更是重要。本論文針對預測蛋白質序列在亞細胞與亞細胞核中的位置的問題，提出兩個演算法GOmining與ESVM來擷取相當高效能特徵子集。此兩種演算法是結合基因演算法(genetic algorithm)與支援向量機(support vector machine)分類器，可以擷取相當高效能特徵子集。
本論文運用GOmining與ESVM演算法分別提出兩個預測系統ProLo-GO與ProLoc來擷取高效能基因註解特徵(Gene Ontology Terms)與物化特性(physicochemical properties)。蛋白質序列資料集SNL6與SNL9 (可分為6與9亞細胞核類別) 是用來驗證ProLoc預測系統。ProLoc針對此兩個蛋白質序列資料集，依序擷取數量33與28個物化特徵子集﹔其預測準確度高達56.4%與72.8%。
至於ProLoc-GO預測系統，針對於SCL12與SCL16(可分為12與16亞細胞類別)蛋白質序列資料集，其使用GOmining演算法可依序擷取到數量44與60個相當高效能基因註解特徵子集，並且獲得90.3%與 84.9%預測準確度。這些擷取到的高效能基因註解特徵子集包含一些基本重要的基因註解特徵(這些基因註解特徵與亞細胞是相關連的)。
既然基因註解特徵與GOmining演算法是有效能，一個有效增進預測準確度的預測蛋白質序列在亞細胞核中的位置的系統NuProLoc便產生。此預測系統使用GOmining演算法來擷取相當高效能基因註解特徵。對於SNL6與SNL9蛋白質序列資料集，NuProLoc獲得75.6%與82.4%預測準確度，大大提升ProLoc的效能。
隨著基因地圖註解特徵數量與群組快速的增加，使得以基因地圖註解特徵為基礎的方法，和以物化特性為基礎的方法，更有效預測蛋白質序列在亞細胞與亞細胞核中的位置。因此GOmining與ESVM演算法是兩個有效擷取特徵子集的工具，可以推廣至其他蛋白質序列的預測問題。

Eukaryotic cells consist of some major parts, the nucleus, cytoplasm, Mitochondrion, Extracellular, and Chloroplast. One of the fundamental goals in molecular cell biology and proteomics is to identify their subcellular locations or environments because the function of a protein and its role in a cell are closely correlated with which compartment or organelle it resides in. The knowledge thus obtained can help us timely utilize these newly found protein sequences for both basic research and drug discovery. Among the subcellualr compartments, the nucleus is a highly complex organelle that forms a package for cells and their corresponding regulatory factors. Therefore, preicition of subcellualr and subnuclear localization are critical problems in biological field.
Computational prediction methods from primary protein sequences are fairly economic in terms of identifying many proteins with unknown functions. Accurate prediction methods not only rely on informative features and classifier design but also emphasize in feature section. This dissertation proposes two novel genetic algorithm based algorithms, GOmining and ESVM, for subcellualr and subnucelar localization prediction. The two algorithms combined with support vector machine (SVM) can determine the best number m of n features and identify a small number m out of the n features and determine simultaneously.
This dissertation using the GOmining and ESVM proposes two prediciotn systems, ProLoc-GO and ProLoc, by mining informative Gene Ontology (GO) terms and physicochemical composition (PCC) for protein subcellular and subnuclear localization, respectively. To evaluate ProLoc, this study uses two datasets SNL6 and SNL9, which have 504 proteins localized in six subnuclear compartments and 367 proteins localized in nine subnuclear compartments. The ProLoc utilizing the selected mPCC=33 and 28 PCC features has accuracies of 56.37% for SNL6 and 72.82% for SNL9, respectively.
As for the ProLoc-GO system, it utilizes GOmining to identify a small number m out of the n GO terms as input features to SVM, where m << n. The m informative GO terms contain the essential GO terms annotating subcellular compartments such as GO:0005634 (Nucleus), GO:0005737 (Cytoplasm) and GO:0005856 (Cytoskeleton). Two existing data sets SCL12 (human protein with 12 locations) and SCL16 (Eukaryotic proteins with 16 locations) with <25% sequence identity are used to evaluate ProLoc-GO which has been implemented by using a single SVM classifier with the m=44 and m=60 informative GO terms, respectively. ProLoc-GO using input sequences yields test accuracies of 88.1% and 83.3% for SCL12 and SCL16, respectively.
Since GOmining incoperated with GO is effieient, an improved prediction system NuProLoc by using GOmining is proposed for subnucelar localization prediction. The NuProLoc yields accuracies 75.6% and 82.4% for SNL6 and SNL9, respectively, which significiently better than 56.37% and 72.82% for ProLoc.
The growth of Gene Ontology and physicochemical properties in size and popularity has increased the effectiveness of GO-based and PCC-based features. GOmining and ESVM can serve as tools for selecting informative GO terms and PCC features in solving sequence-based prediction problems.

誌謝 i
中文摘要 ii
Abstract iv
List of Figures ix
List of Tables xi
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Problem Description 2
1.3 Dissertation Organization 6
Chapter 2 Related Works 7
2.1 Existing Works 7
2.2 K-peptide Composition 9
2.3 Conventional Classifiers 9
2.3.1 Fuzzy k-nearest Neighbors 9
2.3.2 Support Vector Machine 10
2.4 Performance Evaluation 10
Chapter 3 Data Sets 12
3.1 Compartments 12
3.2 Subcellular Compartments 13
3.3 Subnuclear Compartments 15
Chapter 4 Pre-anayisis of Data Sets 17
4.1 GO Annotations with BLAST 17
4.2 Essential GO Terms 19
4.3 Physicochemical Composition Features 21
Chapter 5 Subcellular Localization Prediciton 23
5.1 Proposed GOmining Algorithm 23
5.2 ProLoc-GO Prediction System 26
5.3 SVM-RBS 27
5.4 Results and Discussion 27
5.4.1 Selected Informative GO Terms 27
5.4.2 Evaluation of Feature Selection 30
5.4.3 Performance Comparison 31
5.4.4 Performance of Using Known Accession Numbers 34
5.4.5 Analysis of Informative GO Terms 35
5.4.6 Discussion 40
Chapter 6 PCC Features for Subnuclear Localization Prediction 41
6.1 SVM-based Prediction System ProLoc 41
6.2 Evolutionary Support Vector Machine (ESVM) 41
6.3 Results and Discussion 44
6.3.1 Automatic Feature Selection 44
6.3.2 Factor Analysis of Selected Features 47
6.3.3 Performance Comparison of ProLoc 51
6.3.4 Discussion 53
Chapter 7 GO Terms for Subnucelar Localization Prediction 54
Chapter 7 GO Terms for Subnucelar Localization Prediction 55
7.1 Proposed NuProLoc System 55
7.2 Current Results 56
7.2.1 Selecting Informative GO Terms 56
7.2.2 Evaluation of Feature Selection 59
7.2.3 Performance Comparison 60
7.2.4 Analysis of Informative GO Terms 62
Chapter 8 Conclusions 65
8.1 Summary 65
8.2 Future Work 66
References 68
Appendix A 75
C. V. 75

[1] M. Bhasin, A. Garg, and G. P. S. Raghava, "PSLpred: prediction of subcellular
localization of bacterial proteins," Bioinformatics, vol. 21, 2005, pp. 2522-2524.
[2] M. Bhasin and G. P. S. Raghava, "ESLpred: SVM-based method for subcellular
localization of eukaryotic proteins using dipeptide composition and PSI-BLAST,"
Nucleic Acids Research, vol. 32, 2004, pp. W414-419.
[3] Y. D. Cai, X. J. Liu, X. B. Xu, and K. C. Chou, "Support vector machines for
prediction of protein subcellular location by incorporating quasi-sequence-order
effect," Journal of Cellular Biochemistry, vol. 84, 2002, pp. 343-348.
[4] J. L. Gardy, M. R. Laird, F. Chen, S. Rey, C. J. Walsh, M. Ester, and F. S. L.
Brinkman, "PSORTb v.2.0: Expanded prediction of bacterial protein subcellular
localization and insights gained from comparative proteome analysis,"
Bioinformatics, vol. 21, 2005, pp. 617-623.
[5] A. Garg, M. Bhasin, and G. P. S. Raghava, "Support Vector Machine-based Method
for Subcellular Localization of Human Proteins Using Amino Acid Compositions,
Their Order, and Similarity Search," Journal of Biological Chemistry, vol. 280, 2005,
pp. 14427-14432.
[6] S. Hua and Z. Sun, "Support vector machine approach for protein subcellular
localization prediction.," Bioinformatics, vol. 17, 2001, pp. 721-728.
[7] S. Y. Ho, C. H. Hsieh, H. M. Chen, and H. L. Huang, "Interpretable gene expression
classifier with an accurate and compact fuzzy rule base for microarray data
analysis," BioSystems vol. 85, 2006, pp. 165-176.
[8] D. Sarda, G. Chua, K.-B. Li, and A. Krishnan, "pSLIP: SVM based protein
subcellular localization prediction using multiple physicochemical properties," BMC
Bioinformatics, vol. 6, 2005, pp. 152-163.
Using Gene Ontology Annotation and Physicochemical Properties for Prediction of Protein Subcellular and
Subnuclear Localization
FCU e-Thesys( 2007/200869 )
[9] W. L. Huang, H. M. Chen, S. F. Hwang, and S. Y. Ho, "Accurate prediction of
enzyme subfamily class using an adaptive fuzzy k-nearest neighbor method,"
BioSystems, , vol. 90, 2007, pp. 405-418.
[10] Z. H. Sun, G. Bebis, and R. Miller, "Object detection using feature subset selection,"
Pattern Recognition, vol. 37, 2004, pp. 2165-2176.
[11] M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein, H. Butler, J. M. Cherry, A. P.
Davis, K. Dolinski, S. S. Dwight, J. T. Eppig, M. A. Harris, D. P. Hill, L.
Issel-Tarver, A. Kasarskis, S. Lewis, J. C. Matese, J. E. Richardson, M. Ringwald, G.
M. Rubin, and G. Sherlock, "Gene ontology: tool for the unification of biology. The
Gene Ontology Consortium," Nat Genet., 2000, pp. 25-29.
[12] K. C. Chou and H. B. Shen, "Hum-PLoc: A novel ensemble classifier for predicting
human protein subcellular localization," Biochemical and Biophysical Research
Communications, vol. 347, 2006, pp. 150-157.
[13] K. C. Chou and H. B. Shen, "Predicting Eukaryotic Protein Subcellular Location by
Fusing Optimized Evidence-Theoretic K-Nearest Neighbor Classifiers," J. Proteome
Res., vol. 5, 2006, pp. 1888 - 1897.
[14] K. C. Chou and H. B. Shen, "Euk-mPLoc: A Fusion Classifier for Large-Scale
Eukaryotic Protein Subcellular Location Prediction by Incorporating Multiple Sites,"
J. Proteome Res., 2007.
[15] Z. Lei and Y. Dai, "Assessing protein similarity with Gene Ontology and its use in
subnuclear localization prediction," BMC Bioinformatics, 2006, pp. 491-590.
[16] W. L. Huang, C. W. Tung, H. L. Huang, S. F. Hwang, and S. Y. Ho, "ProLoc:
Prediction of protein subnuclear localization using SVM with automatic selection
from physicochemical composition features.," BioSystems, vol. 90, 2007, pp.
573-581.
[17] L. Nanni and A. Lumini, "An ensemble of K-local hyperplanes for predicting
Using Gene Ontology Annotation and Physicochemical Properties for Prediction of Protein Subcellular and
Subnuclear Localization
FCU e-Thesys( 2007/200870 )
protein-protein interactions," Bioinformatics, vol. 22, 2006, pp. 1207-1210.
[18] S. Kawashima and M. Kanehisa, "AAindex: Amino Acid index database," Nucleic
Acids Research, vol. 28, 2000, pp. 374-374.
[19] G. E. S. Heidi, K. M. Gail, N. Kathryn, V. F. Lisa, F. Rachel, D. Graham, F. C. Javier,
and A. B. Wendy, "Large-scale identification of mammalian proteins localized to
nuclear sub-compartments," Human Molecular Genetics, vol. 10, 2001, pp.
1995-2011.
[20] D. L. Spector, "Nuclear domains," Journal of Cell Science, vol. 114, 2001, pp.
2891-2893.
[21] W. L. Huang, C. W. Tung, S. W. Ho, S. F. Hwang, and S. Y. Ho, "ProLoc-GO:
Utilizing informative Gene Ontology terms for sequence-based prediction of protein
subcellular localization," Accepted by BMC Bioinformatics., 2008.
[22] K. C. Chou and H. B. Shen, "Predicting protein subnuclear location with optimized
evidence-theoretic K-nearest classifier and pseudo amino acid composition,"
Biochemical and Biophysical Research Communications, vol. 337, 2005, pp.
752-756.
[23] O. Emanuelsson, H. Nielsen, S. Brunak, and G. von Heijne, "Predicting Subcellular
Localization of Proteins Based on their N-terminal Amino Acid Sequence," J. Mol.
Biol. , vol. 300, 2000, pp. 1005-1016.
[24] K. Nakai and P. Horton, "PSORT: a program for detecting sorting signals in proteins
and predicting their subcellular localization," Trends in Biochemical Sciences, vol.
24, 1999, pp. 34-35.
[25] J. Cedano, P. Aloy, J. A. P’erez-Pons, and E. Querol, "Relation between amino acid
composition and cellular location of proteins," J. Mol. Biol. , vol. 266, 1997, pp.
594-600.
[26] H. Nakashima and K. Nishikawa, "Discrimination of intracellular and extracellular
Using Gene Ontology Annotation and Physicochemical Properties for Prediction of Protein Subcellular and
Subnuclear Localization
FCU e-Thesys( 2007/200871 )
proteins using amino acid composition and residue-pair frequencies," J. Mol. Biol. ,
vol. 238, 1994, pp. 54-61.
[27] K. J. Park and M. Kanehisa, "Prediction of protein subcellular locations by support
vector machines using compositions of amino acid and amino acid pairs,"
Bioinformatics, vol. 19, 2003, pp. 1656-1663.
[28] Z. Lei and Y. Dai, "An SVM-based system for predicting protein subnuclear
localizations," BMC Bioinformatics, vol. 6, 2005, pp. 291-298.
[29] A. Garg, M. Bhasin, and G. P. Raghava, "Support vector machine-based method for
subcellular localization of human proteins using amino acid compositions, their
order, and similarity search," J. Biol. Chem., vol. 280, 2005, pp. 14427-14432.
[30] Y. Huang and Y. Li, "Prediction of protein subcellular locations using fuzzy k-NN
method," Bioinformatics, vol. 20, 2004, pp. 21-28.
[31] C. S. Yu, C. J. Lin, and J. K. Hwang, "Predicting subcellular localization of proteins
for Gram-negative bacteria by support vector machines based on n-peptide
compositions," Protein Science, vol. 13, 2004, pp. 1402-1406.
[32] W. L. Huang, C. W. Tung, S. W. Ho, S. F. Hwang, and S. Y. Ho, "ProLoc-GO:
Utilizing informative Gene Ontology terms for sequence-based prediction of protein
subcellular localization," Submitted to BMC Bioinformatics., 2007.
[33] A. Lewin and I. Grieve, "Grouping Gene Ontology terms to improve the assessment
of gene set enrichment in microarray data," BMC Bioinformatics, vol. 7, 2006, pp.
426.
[34] S. Carroll and V. Pavlovic, "Protein classification using probabilistic chain graphs
and the Gene Ontology structure," Bioinformatics, vol. 22, 2006, pp. 1871-1878.
[35] K. Wolstencroft, P. Lord, L. Tabernero, A. Brass, and R. Stevens, "Protein
classification using ontology classification," Bioinformatics, vol. 22, 2006, pp.
e530-538.
Using Gene Ontology Annotation and Physicochemical Properties for Prediction of Protein Subcellular and
Subnuclear Localization
FCU e-Thesys( 2007/200872 )
[36] Z. Qian, Y. D. Cai, and Y. Li, "A novel computational method to predict transcription
factor DNA binding preference," Biochemical and Biophysical Research
Communications, vol. 348, 2006, pp. 1034-1037.
[37] M. Popescu, J. M. Keller, and J. A. Mitchell, "Fuzzy Measures on the Gene
Ontology for Gene Product Similarity," IEEE/ACM Trans. Comput. Biol.
Bioinformatics, vol. 3, 2006.
[38] J. M. Keller, M. R. Gray, and J. A. Givens, "A fuzzy k-nearest neighbours
algorithm," IEEE Trans. Syst. Man Cybern., vol. 15, 1985, pp. 580-585.
[39] K. C. Chou, "Using amphiphilic pseudo amino acid composition to predict enzyme
subfamily classes," Bioinformatics, vol. 21, 2005, pp. 10-19.
[40] C. C. Chang and C. J. Lin, "LIBSVM : a library for support vector machines,
Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm," 2001.
[41] T. Joachims, Learning to Classify Text Using Support Vector Machines: Methods,
Theory, and Algorithms, Kluwer Academic Publishers, 2002.
[42] R. Apweiler, A. Bairoch, C. H. Wu, W. C. Barker, B. Boeckmann, S. Ferro, E.
Gasteiger, H. Huang, R. Lopez, M. Magrane, M. J. Martin, D. A. Natale, C.
O''Donovan, N. Redaschi, and L. S. Yeh, "UniProt: the Universal Protein
knowledgebase," Nucleic Acids Res. , vol. 32, 2004, pp. D115-D119.
[43] G. L. Wang and R. L. Dunbrack Jr., "PISCES: a protein sequence culling server,"
Bioinformatics, vol. 19, 2003, pp. 1589-1591.
[44] G. Dellaire, R. Farrall, and W. A. Bickmore, "The Nuclear Protein Database (NPD):
sub-nuclear localisation and functional annotation of the nuclear proteome," Nucleic
Acids Research, vol. 31, 2003, pp. 328-330.
[45] V. Brendel, "PROSET--a fast procedure to create non-redundant sets of protein
sequences," Mathematical and Computer Modelling, vol. 16, 1992, pp. 37-43.
[46] E. Camon, M. Magrane, D. Barrell, V. Lee, E. Dimmer, J. Maslen, D. Binns, N.
Using Gene Ontology Annotation and Physicochemical Properties for Prediction of Protein Subcellular and
Subnuclear Localization
FCU e-Thesys( 2007/200873 )
Harte, R. Lopez, and R. Apweiler, "The Gene Ontology Annotation (GOA) Database:
sharing knowledge in Uniprot with Gene Ontology," Nucleic Acids Res., vol. 32,
2004, pp. D262-266.
[47] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, "Basic local

alignment search tool.," J. Mol. Biol. , vol. 215, 1990, pp. 403-410.
[48] S. F. Altschul, T. L. Madden, A. A. Schaffer, J. Zhang, Z. Zhang, W. Miller, and D. J.
Lipman, "Gapped BLAST and PSIBLAST:a new generation of protein database
search programs.," Nucleic Acids Res., vol. 25, 1997, pp. 3389-3402.
[49] S. Y. Ho, J. H. Chen, and M. H. Huang, "Inheritable genetic algorithm for
biobjective 0/1 combinatorial optimization problems and its applications," Systems,
Man and Cybernetics, Part B, IEEE Transactions on, vol. 34, 2004, pp. 609-620.
[50] S. Y. Ho, L. S. Shu, and J. H. Chen, "Intelligent evolutionary algorithms for large
parameter optimization problems," Evolutionary Computation, IEEE Transactions
on, vol. 8, 2004, pp. 522-541.
[51] M. Stone, "Cross-validatory choice and assessment of statistical predictions,"
Journal of the Royal Statistical Society, vol. 36, 1974, pp. 111-147.
[52] T. Li, C. Zhang, and M. Ogihara, "A comparative study of feature selection and
multiclass classification methods for tissue classification based on gene expression,"
Bioinformatics, vol. 20, 2004, pp. 2429-2437.
[53] C. W. Tung and S. Y. Ho, "POPI: Predicting immunogenicity of MHC class I
binding peptides by mining informative physicochemical properties. ,"
Bioinformatics, vol. 23, 2007, pp. 942-949.
[54] G. Yi, S.-H. Sze, and M. R. Thon, "Identifying clusters of functionally related genes
in genomes," Bioinformatics,, 2007, pp. doi: 10.1093/bioinformatics/btl673.
[55] Z. Lu and L. Hunter, "GO Molecular Function Terms Are Predictive of Subcellular
Localization.," Pacific Symposium on Biocomputing, 2005, pp. 151-161.
Using Gene Ontology Annotation and Physicochemical Properties for Prediction of Protein Subcellular and
Subnuclear Localization
FCU e-Thesys( 2007/200874 )
[56] "GOA. [ftp://ftp.ebi.ac.uk/pub/databases/GO/goa/UNIPROT/]."
[57] Y. Yuan and M. J. Shaw, "Induction of fuzzy decision trees," Fuzzy Sets and Systems,
vol. 69, 1995, pp. 125-139.