Protein Classification Based On Graph Kernels

Protein sciences are important parts of the biological sciences, and protein classification is a hot research field of protein sciences. The extensive research of pattern recognition and machine learning is promoting the development of protein classification rapidly. In the field of pattern recognition, most of the patterns are non-linear. Protein classification is a complex and non-linear classification problem, so we need to seek an efficient way to classify the non-linear patterns urgently. The proposal of kernel methods solves the non-linear problems of non-linear models. Therefore, kernel methods are attracting more and more interests of scholars and researchers.Many objects in the real world are structured and one of most efficient representation for modeling the structured objects are graphs. We get graph kernels when we combine kernel methods with graphs. Based on the widely applicable of graphs, graph kernel has been applied to many areas and achieved wide attention. Ease of representation and computation is an important criterion for judging the graph kernels. Several different graph kernels have been defined in machine learning which can be categorized into three classes: graph kernels based on walks and paths, graph kernels based on limited-size subgraphs, and graph kernels based on subtree patterns. With the proposal of Weisfeiler-Lehman graph matching algorithm, experiments show that when we combine WL method with graph kernels and apply the new graph kernels to the support vector machine(SVM) to classify the proteins, we will gain better recognition rate. Also, our new method is applicable to most of graphs.The main work and contributions of the paper focus on the following:(1) In-depth understanding of the basic principles of classifier. The paper analyzed the nature of kernel functions, the identification method of them and the construction method of complex kernels. We introduced Support Vector Machine(SVM) and the concept of graph kernels. The paper also elaborated several existing graph kernels.(2) The paper made a brief introduction to the WL graph matching method and combined it with the graph kernels. We could achieve better results when using WL graph kernels to measure the degree of similarity between two graphs, because WL graph kernels could fully tap the topology and vertexes information of graphs. Protein functions are closely related to its spatial structure, we could simulate protein molecules using graphs. In the experimental section, we represent the protein molecules according to their primary structures and tertiary structures, then we perform WL graph kernel on them. We achieve higher accuracy than other kernels while the time complexity is little difference.