蒋强荣 邱广

摘 要： 由于蛋白质的多样性及其结构的复杂性，采用传统按照属性简单线性组合的函数方法难以实现正确分类。图核方法则为此提供了一个解决方案，通过图核方式将蛋白质具有的结构信息提取出来，将两图的相似性比较转化为两图各顶点之间匹配度的比较。提出混合矩阵的点边相似核，将图的邻接矩阵看作各顶点样本向量，通过寻找两图最相似的顶点对进行核值计算。此外，还提出将图核与神经网络相结合，利用神经网络良好的分类性能提高分类准确率。实验结果表明，采用该方法比原有方法的分类准确率提高了15%～30%。

关键词：神经网络;图核;蛋白质分类

DOI：10. 11907/rjdk. 181754

中图分类号：TP301文献标识码：A文章编号：1672-7800（2019）002-0020-04

Abstract： Due to the protein diversity and its structure complexity， the traditional linear combination according to the properties of the simple function is difficult to the correct classification. The kernel method provides a solution to extract the structural information of the protein and better use its structural information. By transforming the similarity comparison of two graphs into two graph matching degree between each vertex. The mixed matrix of similar kernel point edge is proposed. The graphsadjacency matrix are taken as the samples of each vertex vector and thekernel value is obtained by looking for the most similar vertex of the two graphs. In addition， it is proposed to combine the graph kernel with neural network to improve the classification accuracy by using the good classification performance of neural network. The experimental results show that the method is 15% to 30% higher than the original method.

Key Words： neural network; graph kernel; protein classification

引言

蛋白质分类是生物信息学中的关键问题之一，许多无监督方法被应用于蛋白质分类问题中，其中的代表性方法包括自然矢量方法[1]、蛋白质地图[2]、K-string字典[3]、Yau-Hausdorff 距离[4]等。随着机器学习的快速发展，将机器学习方法应用于蛋白質分类也取得了很大进展。Khan等[5]采用蚁群优化方法，结合关联规则挖掘与监督分类机制对蛋白质进行分类;Lacey等[6]将隐马尔可夫模型与随机决策树应用于蛋白质分类;Islam等[7]将自然语言处理的N-Gram模型应用于蛋白质分类等。考虑到蛋白质的三维结构包含大量信息，Jiang等[8]提出将图核应用于蛋白质的图结构信息提取，并结合SVM进行分类;对于蛋白质各种特征信息的融合问题，Singh等[9]采用混合特征选择技术对蛋白质进行分类。以上机器学习方法在蛋白质分类方面取得了一定效果，本文通过对蛋白质三维结构的分析，利用图核提取其结构特征并进行分类。

采用图核方式对蛋白质进行分类的研究目前已有了很大进展，图核的基本思想是通过提取图结构的子部分，比较子部分的结构相似性以衡量两图相似性，将其之间的相似度作为图核的核值。目前已有通过提取图的通路、子树与最短路径等子部分，比较这些子部分的相似性以确定图核。通过不同子部分的比较可得到不同图核，分别为随机通路核、子树核及最短路径核等[10-12]。其共同目标是通过将图分割成各个子结构，由顶点标签与边的权重确定核值，而提取子结构会丢失原有全局结构信息，从而导致相似度计算的准确率降低。在Shervashidze等[13]的研究中，提出的WL核通过迭代方式，对两图及其衍生图计算相似度，可一定程度上改善上述问题。WL核是基于Weisfeiler-Lehman（WL）图匹配方法结合图核思想得到的[15]，WL核的主要优点是能够通过迭代，使两图相似的子部分越来越相似，不相似部分随着迭代深入，区别越来越大，在计算结果上体现为相似部分的值越来越大，不相似部分的值越来越小，从而使WL核在图结构分类上得到较好效果。但WL核每次迭代都保留原始图结构，只修改顶点标签信息，对边的权值却未能进行很好地处理。在图结构中，图的邻接矩阵包含了图的所有邻接关系，将图的顶点信息添加到邻接矩阵中，邻接矩阵则拥有图结构的全部信息。基于此，本文提出混合矩阵的点边相似核，可以尽量将特征损失降到最低。

神经网络主要由神经元组成，所组成的网络结构具有较强的非线性映射能力，信息常处于神经元权重范围内，以此增强网络的鲁棒性。反向传输算法是训练神经网络的常用算法，即借助权重的有序调节实现神经网络的有序性及稳定性，其中权重分布又可通过误差函数数值加以改变，以此完成适当的输出任务。此外，隐含层、输入层与输出层是神经网络基本层，这三层代表了正向传播方向，神经元之间可互相影响，一旦出现输出结果不符合预期的情况，此时应适当调整信号传播程序。在此期间，不断缩小误差函数值，以确保信息提取工作顺利进行[16，20]。本文将图核与神经网络相结合，利用神经网络良好的分类性能，以及图核对蛋白质丰富图结构的特征提取，提高蛋白质分类准确率。

利用图核方式提取蛋白质结构信息，首先需要将蛋白质三维结构转换成图结构模型。图 1展示了PDB编号为1a6x的大肠埃希氏菌APO-BCCP87蛋白质转换成图结构模型的过程。左图是蛋白质三维空间结构，右图是Borgwardt等[14]将其转换成的图结构模型，图的节点代表二级结构类型，虚线（不存在于最后的图结构中）表示氨基酸链接顺序，实线（存在于最后的图结构中）表示连接相邻的氨基酸链。相邻的定义是氨基酸链间的距离小于某个阈值（单位为埃）。

1 混合矩阵点边相似核

图核的任务是比较两图相似性，并用一个给定的值表示。由于图的邻接矩阵包含图各顶点的邻接关系，以及边的权值信息，通过将各顶点的权值信息添加到邻接矩阵的主对角线上，则新的邻接矩阵包含图结构全部信息。

将图定义为四元组G（V，E，I，R），其中V是顶点集合，E为边的集合，I表示边的权值集合，R表示顶点的权值集合。图的赋权邻接矩阵定义为：

其中[vi]、[vj]是图中两个顶点，[I（vi，vj）]表示连接顶点[vi]和[vj]之间边的权值。

图的顶点权值对角矩阵定义为：

其中[R（vi）]表示顶点[vi]的权值，则混合矩阵定义为：[H=P+D]，即混合矩阵融合了图的顶点与边的权值信息。假设图[G1]、[G2]添加了顶点与边权值信息的混合矩阵为[A]、[B]，则混合矩阵的点边相似核算法如下：

1.1 样本降维

将混合矩阵[A]、[B]的每一行看作一个顶点的样本，则[A]、[B]分别为图[G1]、[G2]各顶点样本向量构成的矩阵，为了减少样本特征损失，利用[PCA][17-18]降维的方式将[A]、[B]中各顶点样本向量归一化到[k]维。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示，可用于提取数据主要特征分量，常用于高维数据的降维。

设有m条n维数据，降维步骤具体如下：

（1）将原始数据按列组成n行m列矩阵X。？

（2）将X的每一行（代表一个属性字段）进行零均值化，即减去这一行的均值。？

（3）求出协方差矩阵。

（4）求出协方差矩阵的特征值及对应特征向量。？

（5）将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵P。？

（6）Y=PX即为降维到k维后的数据，即：

其中，[m]、[n]分别为混合矩阵[A]、[B]的维数，[XAn×k]、[XBm×k]分别为图[G1]、[G2]的顶点样本降维到[k]维的各样本向量，[ PAn×k]、[PBm×k]分别由两图各顶点样本向量协方差矩阵的前[k]个特征向量构成。

1.2 相似度矩阵

对于归一化之后的顶点样本向量[XAn×k]、[XBm×k]， 两图的相似性比较可转化为顶点样本之间的相似性度量，则由两图各顶点之间相似度构成的相似矩阵为：

两顶点向量的相似度由欧式距离给出，即：

1.3 点边相似核

点边相似核的核值是通过寻找两图中最相似的顶点对，即在相似矩阵中寻找不在同一行也不在同一列，且使其和最大的各个相似值，它们的和即为核值，而寻找方式可转化为二分图的最大匹配问题。假设[VA]、[VB]分别表示图[G1]、[G2]各顶点的集合，[SABn×m（i，j）]表示[VAi]與[VBj]相连接的边的权值，则构成的赋权完全二分图如图2所示。

通过匈牙利算法得到最大匹配图[M（i），i=1，2，？，][min （m，n）]，[W[M（i）]]表示[M（i）]匹配中各边的权值之和，则点边相似核为：

1.4 算法时间复杂度

样本归一化的时间复杂度为[PCA]算法时间复杂度[O（n3）]，构造相似度矩阵的时间复杂度为[O（n2）]，点边相似核的时间复杂度为匈牙利算法与求最大匹配权值之和的时间复杂度，即为[O（n4）]，所以点边相似核的时间复杂度为[O（n4）]。

2 图核与神经网络结合

核矩阵是由各样本之间的相似度构成的，其每一行为一个样本与其它各样本之间的相似度，而分类问题是通过比较两样本特征向量之间的相似度进行的。因此，以所有样本为参考值，一个样本与所有样本之间的相似度可作为该样本特征向量，即为具有图结构特征信息的样本提供提取特征的方式，并可结合神经网络进行分类，利用神经网络的良好性能提高分类准确率，如图3所示。

3 实验结果与分析

数据库是由PDB提供的公开数据集，图结构数据包含D&D、ENZYMES、NCI1、NCI2和MUTAG数据库。ENZYMES 是一个具有三层结构的蛋白质数据集，其包含从酶蛋白质数据库中获取的600个蛋白质酶，在该情况下的主要任务是给每个蛋白质正确添加一个6层结构的类。D&D是一个包含1178个蛋白质结构的数据集，每个蛋白质可看作一个图，图中节点表示氨基酸，两个节点之间的边小于6埃则可用一条边连接。各数据库基本信息如表1所示。

实验将图核与神经网络相结合，利用神经网络对蛋白质进行分类。神经网络的输入为通过图核提取的特征向量，输出为各类别标签，输入层的节点个数为特征向量维数，输出层的节点个数为样本类别数。网络结构包含两层隐藏层，节点个数都为256，优化器选择自适应梯度下降方式。为了保证实验结果的可靠性，实验采取10-折交叉验证方式进行，表2中的结果为10-折交叉实验的平均值。

表2结果显示，用图核方式提取图结构的特征信息并通过神经网络进行分类是可行的。由于ENMEZY数据库包含数据集较少，神经网络训练不充分，导致准确率偏低。已有的一般图核结合神经网络对图结构样本进行分类的方法与采用SVM结合核矩阵方式分类结果相差不大，而本文提出的基于混合矩阵点边相似核对图结构样本进行分类的方法，分类准确率有了极大提升，效果明显优于其它方法。可以看出，图核与神经网络的结合对于具有图结构特征的样本分类具有非常好的效果。

4 結语

图核是机器学习研究中用于处理结构化数据的重要方法，对于具有图结构的样本数据，如何比较其相似性成为图核的基本任务。综合目前已有的图核方法，本文提出能够尽可能减少特征损失的混合矩阵的点边相似核，以提高图结构相似性比较的准确性，同时与具有良好分类效果的神经网络相结合，有效提高了图结构样本的分类准确率。该方法还可扩展应用于任何具有丰富图结构信息的样本数据。

参考文献：

[1] ZHAO X， WAN X， HE R L， et al. A new method for studying the evolutionary origin of the SAR11 clade marine bacteria[J]. Molecular Phylogenetics & Evolution， 2016， 98：271-279.

[2] YU C， CHENG S Y， HE R L， et al. Protein map： an alignment-free sequence comparison method based on various properties of amino acids[J]. Gene， 2011， 486（1-2）：110.

[3] YU C， HE R L， YAU S S. Protein sequence comparison based on K-string dictionary[J]. Gene， 2013， 529（2）：250.

[4] TIAN K， YANG X， KONG Q， et al. Two dimensional yau-hausdorff distance with applications on comparison of DNA and protein sequences.[J]. Plos One， 2015， 10（9）：e0136577.

[5] KHAN M A， SHAHZAD W， BAIG A R. Protein classification via an ant-inspired association rules-based classifier[J]. International Journal of Bio-Inspired Computation， 2016， 8（1）：51.

[6] LACEY A， DENG J， XIE X. Protein classification using hidden Markov models and randomised decision trees[C]. International Conference on Biomedical Engineering and Informatics. IEEE，2015：659-664.

[7] ISLAM S A， KEARNEY C M， CHOUDHURY A， et al. Protein classification using modified N-gram and skip-gram models： extended abstract[C].The ACM International Conference. ACM， 2017：586-586.

[8] JIANG Q， XIONG Z， ZHAI C. Graph kernels and applications in protein classification[J]. Telkomnika Indonesian Journal of Electrical Engineering， 2016， 12（10）：214.

[9] SINGH U， TRIPATHI S. Protein classification using hybrid feature selection technique[M]. Jaipur：Springer， 2016.

[10] BAI L， ROSSI L， CUI L， et al. A nested alignment graph kernel through the dynamic time warping framework[C]. International Workshop on Graph-Based Representations in Pattern Recognition， 2017：59-69.

[11] TAKERKART S， BERTON G， MALFAIT N， et al. Learning from diffusion-weighted magnetic resonance images using graph kernels[C].International Workshop on Graph-Based Representations in Pattern Recognition， 2017：39-48.

[12] GISCARD P L， WILSON R C. The all-paths and cycles graph kernel[J]. IEEE Transactions on Neural Networks and Learning Systems，2017（8）：1-8.

[13] SHERVASHIDZE N， SCHWEITZER P， LEEUWEN E J V， et al. Weisfeiler-Lehman graph kernels[J]. Journal of Machine Learning Research， 2011， 12（3）：2539-2561.

[14] BORGWARDT K M， ONG C S， SCH？NAUER S， et al. Protein function prediction via graph kernels[J]. Bioinformatics， 2005， 21： i47-i56.

[15] WEISFEILER B， LEHMAN A A. A reduction of a graph to a canonical form and an algebra arising during this reduction[J]. Nauchno-Technicheskaya Informatsia， 1968， 2（9）： 12-16.

[16] RALAIVOLA L， SWAMIDASS S J， SAIGO H， et al. Graph kernels for chemical informatics[J]. Neural Networks the Official Journal of the International Neural Network Society， 2005， 18（8）：1093.

[17] MIKA S， SMOLA A， SCHOLZ M. Kernel PCA and de-noising in feature spaces[C]. Conference on Advances in Neural Information Processing Systems II， 1999：536-542.

[18] DU J， WANG L， JIE B， et al. Network-based classification of ADHD patients using discriminative subnetwork selection and graph kernel PCA[J]. Computerized Medical Imaging & Graphics the Official Journal of the Computerized Medical Imaging Society， 2016， 52：82-88.

[19] WANG L， SAHBI H. Directed acyclic graph kernels for action recognition[C]. IEEE International Conference on Computer Vision. IEEE， 2013：3168-3175.

[20] HANSEN L K， SALAMON P. Neural network ensembles[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 12（10）：993-1001.