蔣強榮 邱廣

摘 要： 由于蛋白質(zhì)的多樣性及其結(jié)構(gòu)的復雜性，采用傳統(tǒng)按照屬性簡單線性組合的函數(shù)方法難以實現(xiàn)正確分類。圖核方法則為此提供了一個解決方案，通過圖核方式將蛋白質(zhì)具有的結(jié)構(gòu)信息提取出來，將兩圖的相似性比較轉(zhuǎn)化為兩圖各頂點之間匹配度的比較。提出混合矩陣的點邊相似核，將圖的鄰接矩陣看作各頂點樣本向量，通過尋找兩圖最相似的頂點對進行核值計算。此外，還提出將圖核與神經(jīng)網(wǎng)絡相結(jié)合，利用神經(jīng)網(wǎng)絡良好的分類性能提高分類準確率。實驗結(jié)果表明，采用該方法比原有方法的分類準確率提高了15%～30%。

關(guān)鍵詞：神經(jīng)網(wǎng)絡;圖核;蛋白質(zhì)分類

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

引言

蛋白質(zhì)分類是生物信息學中的關(guān)鍵問題之一，許多無監(jiān)督方法被應用于蛋白質(zhì)分類問題中，其中的代表性方法包括自然矢量方法[1]、蛋白質(zhì)地圖[2]、K-string字典[3]、Yau-Hausdorff 距離[4]等。隨著機器學習的快速發(fā)展，將機器學習方法應用于蛋白質(zhì)分類也取得了很大進展。Khan等[5]采用蟻群優(yōu)化方法，結(jié)合關(guān)聯(lián)規(guī)則挖掘與監(jiān)督分類機制對蛋白質(zhì)進行分類;Lacey等[6]將隱馬爾可夫模型與隨機決策樹應用于蛋白質(zhì)分類;Islam等[7]將自然語言處理的N-Gram模型應用于蛋白質(zhì)分類等?？紤]到蛋白質(zhì)的三維結(jié)構(gòu)包含大量信息，Jiang等[8]提出將圖核應用于蛋白質(zhì)的圖結(jié)構(gòu)信息提取，并結(jié)合SVM進行分類;對于蛋白質(zhì)各種特征信息的融合問題，Singh等[9]采用混合特征選擇技術(shù)對蛋白質(zhì)進行分類。以上機器學習方法在蛋白質(zhì)分類方面取得了一定效果，本文通過對蛋白質(zhì)三維結(jié)構(gòu)的分析，利用圖核提取其結(jié)構(gòu)特征并進行分類。

采用圖核方式對蛋白質(zhì)進行分類的研究目前已有了很大進展，圖核的基本思想是通過提取圖結(jié)構(gòu)的子部分，比較子部分的結(jié)構(gòu)相似性以衡量兩圖相似性，將其之間的相似度作為圖核的核值。目前已有通過提取圖的通路、子樹與最短路徑等子部分，比較這些子部分的相似性以確定圖核。通過不同子部分的比較可得到不同圖核，分別為隨機通路核、子樹核及最短路徑核等[10-12]。其共同目標是通過將圖分割成各個子結(jié)構(gòu)，由頂點標簽與邊的權(quán)重確定核值，而提取子結(jié)構(gòu)會丟失原有全局結(jié)構(gòu)信息，從而導致相似度計算的準確率降低。在Shervashidze等[13]的研究中，提出的WL核通過迭代方式，對兩圖及其衍生圖計算相似度，可一定程度上改善上述問題。WL核是基于Weisfeiler-Lehman（WL）圖匹配方法結(jié)合圖核思想得到的[15]，WL核的主要優(yōu)點是能夠通過迭代，使兩圖相似的子部分越來越相似，不相似部分隨著迭代深入，區(qū)別越來越大，在計算結(jié)果上體現(xiàn)為相似部分的值越來越大，不相似部分的值越來越小，從而使WL核在圖結(jié)構(gòu)分類上得到較好效果。但WL核每次迭代都保留原始圖結(jié)構(gòu)，只修改頂點標簽信息，對邊的權(quán)值卻未能進行很好地處理。在圖結(jié)構(gòu)中，圖的鄰接矩陣包含了圖的所有鄰接關(guān)系，將圖的頂點信息添加到鄰接矩陣中，鄰接矩陣則擁有圖結(jié)構(gòu)的全部信息?；诖耍疚奶岢龌旌暇仃嚨狞c邊相似核，可以盡量將特征損失降到最低。

神經(jīng)網(wǎng)絡主要由神經(jīng)元組成，所組成的網(wǎng)絡結(jié)構(gòu)具有較強的非線性映射能力，信息常處于神經(jīng)元權(quán)重范圍內(nèi)，以此增強網(wǎng)絡的魯棒性。反向傳輸算法是訓練神經(jīng)網(wǎng)絡的常用算法，即借助權(quán)重的有序調(diào)節(jié)實現(xiàn)神經(jīng)網(wǎng)絡的有序性及穩(wěn)定性，其中權(quán)重分布又可通過誤差函數(shù)數(shù)值加以改變，以此完成適當?shù)妮敵鋈蝿?。此外，隱含層、輸入層與輸出層是神經(jīng)網(wǎng)絡基本層，這三層代表了正向傳播方向，神經(jīng)元之間可互相影響，一旦出現(xiàn)輸出結(jié)果不符合預期的情況，此時應適當調(diào)整信號傳播程序。在此期間，不斷縮小誤差函數(shù)值，以確保信息提取工作順利進行[16，20]。本文將圖核與神經(jīng)網(wǎng)絡相結(jié)合，利用神經(jīng)網(wǎng)絡良好的分類性能，以及圖核對蛋白質(zhì)豐富圖結(jié)構(gòu)的特征提取，提高蛋白質(zhì)分類準確率。

利用圖核方式提取蛋白質(zhì)結(jié)構(gòu)信息，首先需要將蛋白質(zhì)三維結(jié)構(gòu)轉(zhuǎn)換成圖結(jié)構(gòu)模型。圖 1展示了PDB編號為1a6x的大腸埃希氏菌APO-BCCP87蛋白質(zhì)轉(zhuǎn)換成圖結(jié)構(gòu)模型的過程。左圖是蛋白質(zhì)三維空間結(jié)構(gòu)，右圖是Borgwardt等[14]將其轉(zhuǎn)換成的圖結(jié)構(gòu)模型，圖的節(jié)點代表二級結(jié)構(gòu)類型，虛線（不存在于最后的圖結(jié)構(gòu)中）表示氨基酸鏈接順序，實線（存在于最后的圖結(jié)構(gòu)中）表示連接相鄰的氨基酸鏈。相鄰的定義是氨基酸鏈間的距離小于某個閾值（單位為埃）。

1 混合矩陣點邊相似核

圖核的任務是比較兩圖相似性，并用一個給定的值表示。由于圖的鄰接矩陣包含圖各頂點的鄰接關(guān)系，以及邊的權(quán)值信息，通過將各頂點的權(quán)值信息添加到鄰接矩陣的主對角線上，則新的鄰接矩陣包含圖結(jié)構(gòu)全部信息。

將圖定義為四元組G（V，E，I，R），其中V是頂點集合，E為邊的集合，I表示邊的權(quán)值集合，R表示頂點的權(quán)值集合。圖的賦權(quán)鄰接矩陣定義為：

其中[vi]、[vj]是圖中兩個頂點，[I（vi，vj）]表示連接頂點[vi]和[vj]之間邊的權(quán)值。

圖的頂點權(quán)值對角矩陣定義為：

其中[R（vi）]表示頂點[vi]的權(quán)值，則混合矩陣定義為：[H=P+D]，即混合矩陣融合了圖的頂點與邊的權(quán)值信息。假設圖[G1]、[G2]添加了頂點與邊權(quán)值信息的混合矩陣為[A]、[B]，則混合矩陣的點邊相似核算法如下：

1.1 樣本降維

將混合矩陣[A]、[B]的每一行看作一個頂點的樣本，則[A]、[B]分別為圖[G1]、[G2]各頂點樣本向量構(gòu)成的矩陣，為了減少樣本特征損失，利用[PCA][17-18]降維的方式將[A]、[B]中各頂點樣本向量歸一化到[k]維。PCA通過線性變換將原始數(shù)據(jù)變換為一組各維度線性無關(guān)的表示，可用于提取數(shù)據(jù)主要特征分量，常用于高維數(shù)據(jù)的降維。

設有m條n維數(shù)據(jù)，降維步驟具體如下：

（1）將原始數(shù)據(jù)按列組成n行m列矩陣X。？

（2）將X的每一行（代表一個屬性字段）進行零均值化，即減去這一行的均值。？

（3）求出協(xié)方差矩陣。

（4）求出協(xié)方差矩陣的特征值及對應特征向量。？

（5）將特征向量按對應特征值大小從上到下按行排列成矩陣，取前k行組成矩陣P。？

（6）Y=PX即為降維到k維后的數(shù)據(jù)，即：

其中，[m]、[n]分別為混合矩陣[A]、[B]的維數(shù)，[XAn×k]、[XBm×k]分別為圖[G1]、[G2]的頂點樣本降維到[k]維的各樣本向量，[ PAn×k]、[PBm×k]分別由兩圖各頂點樣本向量協(xié)方差矩陣的前[k]個特征向量構(gòu)成。

1.2 相似度矩陣

對于歸一化之后的頂點樣本向量[XAn×k]、[XBm×k]， 兩圖的相似性比較可轉(zhuǎn)化為頂點樣本之間的相似性度量，則由兩圖各頂點之間相似度構(gòu)成的相似矩陣為：

兩頂點向量的相似度由歐式距離給出，即：

1.3 點邊相似核

點邊相似核的核值是通過尋找兩圖中最相似的頂點對，即在相似矩陣中尋找不在同一行也不在同一列，且使其和最大的各個相似值，它們的和即為核值，而尋找方式可轉(zhuǎn)化為二分圖的最大匹配問題。假設[VA]、[VB]分別表示圖[G1]、[G2]各頂點的集合，[SABn×m（i，j）]表示[VAi]與[VBj]相連接的邊的權(quán)值，則構(gòu)成的賦權(quán)完全二分圖如圖2所示。

通過匈牙利算法得到最大匹配圖[M（i），i=1，2，？，][min （m，n）]，[W[M（i）]]表示[M（i）]匹配中各邊的權(quán)值之和，則點邊相似核為：

1.4 算法時間復雜度

樣本歸一化的時間復雜度為[PCA]算法時間復雜度[O（n3）]，構(gòu)造相似度矩陣的時間復雜度為[O（n2）]，點邊相似核的時間復雜度為匈牙利算法與求最大匹配權(quán)值之和的時間復雜度，即為[O（n4）]，所以點邊相似核的時間復雜度為[O（n4）]。

2 圖核與神經(jīng)網(wǎng)絡結(jié)合

核矩陣是由各樣本之間的相似度構(gòu)成的，其每一行為一個樣本與其它各樣本之間的相似度，而分類問題是通過比較兩樣本特征向量之間的相似度進行的。因此，以所有樣本為參考值，一個樣本與所有樣本之間的相似度可作為該樣本特征向量，即為具有圖結(jié)構(gòu)特征信息的樣本提供提取特征的方式，并可結(jié)合神經(jīng)網(wǎng)絡進行分類，利用神經(jīng)網(wǎng)絡的良好性能提高分類準確率，如圖3所示。

3 實驗結(jié)果與分析

數(shù)據(jù)庫是由PDB提供的公開數(shù)據(jù)集，圖結(jié)構(gòu)數(shù)據(jù)包含D&D、ENZYMES、NCI1、NCI2和MUTAG數(shù)據(jù)庫。ENZYMES 是一個具有三層結(jié)構(gòu)的蛋白質(zhì)數(shù)據(jù)集，其包含從酶蛋白質(zhì)數(shù)據(jù)庫中獲取的600個蛋白質(zhì)酶，在該情況下的主要任務是給每個蛋白質(zhì)正確添加一個6層結(jié)構(gòu)的類。D&D是一個包含1178個蛋白質(zhì)結(jié)構(gòu)的數(shù)據(jù)集，每個蛋白質(zhì)可看作一個圖，圖中節(jié)點表示氨基酸，兩個節(jié)點之間的邊小于6埃則可用一條邊連接。各數(shù)據(jù)庫基本信息如表1所示。

實驗將圖核與神經(jīng)網(wǎng)絡相結(jié)合，利用神經(jīng)網(wǎng)絡對蛋白質(zhì)進行分類。神經(jīng)網(wǎng)絡的輸入為通過圖核提取的特征向量，輸出為各類別標簽，輸入層的節(jié)點個數(shù)為特征向量維數(shù)，輸出層的節(jié)點個數(shù)為樣本類別數(shù)。網(wǎng)絡結(jié)構(gòu)包含兩層隱藏層，節(jié)點個數(shù)都為256，優(yōu)化器選擇自適應梯度下降方式。為了保證實驗結(jié)果的可靠性，實驗采取10-折交叉驗證方式進行，表2中的結(jié)果為10-折交叉實驗的平均值。

表2結(jié)果顯示，用圖核方式提取圖結(jié)構(gòu)的特征信息并通過神經(jīng)網(wǎng)絡進行分類是可行的。由于ENMEZY數(shù)據(jù)庫包含數(shù)據(jù)集較少，神經(jīng)網(wǎng)絡訓練不充分，導致準確率偏低。已有的一般圖核結(jié)合神經(jīng)網(wǎng)絡對圖結(jié)構(gòu)樣本進行分類的方法與采用SVM結(jié)合核矩陣方式分類結(jié)果相差不大，而本文提出的基于混合矩陣點邊相似核對圖結(jié)構(gòu)樣本進行分類的方法，分類準確率有了極大提升，效果明顯優(yōu)于其它方法?？梢钥闯?，圖核與神經(jīng)網(wǎng)絡的結(jié)合對于具有圖結(jié)構(gòu)特征的樣本分類具有非常好的效果。

4 結(jié)語

圖核是機器學習研究中用于處理結(jié)構(gòu)化數(shù)據(jù)的重要方法，對于具有圖結(jié)構(gòu)的樣本數(shù)據(jù)，如何比較其相似性成為圖核的基本任務。綜合目前已有的圖核方法，本文提出能夠盡可能減少特征損失的混合矩陣的點邊相似核，以提高圖結(jié)構(gòu)相似性比較的準確性，同時與具有良好分類效果的神經(jīng)網(wǎng)絡相結(jié)合，有效提高了圖結(jié)構(gòu)樣本的分類準確率。該方法還可擴展應用于任何具有豐富圖結(jié)構(gòu)信息的樣本數(shù)據(jù)。

參考文獻：

[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.