圖核結合神經網絡的蛋白質分類方法

蔣強榮 邱廣

摘 要： 由于蛋白質的多樣性及其結構的復雜性，采用傳統按照屬性簡單線性組合的函數方法難以實現正確分類。圖核方法則為此提供了一個解決方案，通過圖核方式將蛋白質具有的結構信息提取出來，將兩圖的相似性比較轉化為兩圖各頂點之間匹配度的比較。提出混合矩陣的點邊相似核，將圖的鄰接矩陣看作各頂點樣本向量，通過尋找兩圖最相似的頂點對進行核值計算。此外，還提出將圖核與神經網絡相結合，利用神經網絡良好的分類性能提高分類準確率。實驗結果表明，采用該方法比原有方法的分類準確率提高了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.