局部路徑相似度的蛋白質(zhì)鏈接預(yù)測

王金哲， 王遠威， 王紅梅

(長春工業(yè)大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

鏈接預(yù)測旨在通過基于現(xiàn)有的網(wǎng)絡(luò)拓撲信息，預(yù)測網(wǎng)絡(luò)中缺失或者可能存在的交互關(guān)系[1]。鏈接預(yù)測是一種典型的復雜網(wǎng)絡(luò)分析應(yīng)用。在蛋白質(zhì)交互網(wǎng)絡(luò)中，預(yù)測蛋白質(zhì)之間的相互作用對于理解蛋白質(zhì)交互網(wǎng)絡(luò)本身和其拓撲結(jié)構(gòu)均有重要的意義[2]。

近年來，國內(nèi)外學者在蛋白質(zhì)交互網(wǎng)絡(luò)(Protein-Protein Interaction Network, PPI)的鏈接預(yù)測方面做了大量的工作?，F(xiàn)有的鏈接預(yù)測方法通常是利用節(jié)點局部信息進行預(yù)測。作為經(jīng)典的鏈接預(yù)測方法，基于局部信息相似性的方法由于具有準確性高和復雜性低的特性，已應(yīng)用于蛋白質(zhì)交互網(wǎng)絡(luò)中的鏈接預(yù)測。

基于局部信息相似性的方法通常都會基于節(jié)點間相似程度越高，鏈接出現(xiàn)的可能性越高這一假設(shè)來進行鏈接預(yù)測[3]。

經(jīng)典的局部相似性方法有共同鄰居(Common Nneighbors, CN)[4]、Adamic-Adar(AA)[5]、資源分配(Resource Allocation， RA)[6]和偏好連接(Preferential Attachment， PA)[7]等。Saito等[8]提出基于節(jié)點及其鄰居節(jié)點的拓撲關(guān)系來預(yù)測蛋白質(zhì)交互出現(xiàn)的可能性。這些經(jīng)典的鏈接預(yù)測方法大多利用節(jié)點的共同鄰居信息，而沒有考慮到蛋白質(zhì)社區(qū)結(jié)構(gòu)信息對鏈接預(yù)測的貢獻。

蛋白質(zhì)之間的交互通常依賴生物過程的內(nèi)部機制[9]。蛋白質(zhì)社區(qū)通常會共同完成某一種或若干種生物學功能。在預(yù)測PPI網(wǎng)絡(luò)的潛在交互信息時，需要結(jié)合蛋白質(zhì)所在的社區(qū)結(jié)構(gòu)信息來進行蛋白質(zhì)交互預(yù)測。

基于上述理論，近年來有諸多學者提出了基于社區(qū)結(jié)構(gòu)信息的蛋白質(zhì)交互預(yù)測方法。洪海燕等[10]將PPI網(wǎng)絡(luò)看作一個有權(quán)無向圖，提出了一種基于空間關(guān)系映射的蛋白質(zhì)相互作用預(yù)測方法;Sun等[11]基于群落結(jié)構(gòu)和節(jié)點度的關(guān)系，提出了一種局部親和力結(jié)構(gòu)(LAS)的相似度計算方法;基于節(jié)點鏈接與所屬社區(qū)緊密程度有關(guān)這一假設(shè),Li等[12]提出了一種基于社區(qū)關(guān)系強度的鏈接預(yù)測方法。上述方法更注重挖掘網(wǎng)絡(luò)拓撲結(jié)構(gòu)，缺乏對蛋白質(zhì)本身拓撲信息的挖掘。因此，在考慮到基于局部信息相似性的方法和社區(qū)結(jié)構(gòu)的蛋白質(zhì)交互預(yù)測方法存在的不足，文中提出了一種融合社區(qū)結(jié)構(gòu)和節(jié)點度的局部路徑相似度的蛋白質(zhì)鏈接預(yù)測方法(PIPM)，在考慮蛋白質(zhì)交互網(wǎng)絡(luò)社區(qū)信息的同時，結(jié)合蛋白質(zhì)之間的拓撲結(jié)構(gòu)進行鏈接預(yù)測。

1 相關(guān)理論

1.1 社區(qū)發(fā)現(xiàn)

Infomap方法是M Rosvall等[13]提出的，它是思路比較特別且準確率較高的一種方法。該方法從信息論方面出發(fā)，通過雙層編碼方法將社區(qū)發(fā)現(xiàn)與信息編碼結(jié)合到一起。通過量化編碼長度，找到長度最短的社區(qū)劃分，即找到一個好的社區(qū)劃分。Infomap方法的迭代過程如下:

輸入：網(wǎng)絡(luò)G的鏈接集合；

輸出：網(wǎng)絡(luò)G的社區(qū)結(jié)構(gòu)。

1)初始化，將網(wǎng)絡(luò)中每個節(jié)點視為一個社區(qū)；

2)將網(wǎng)絡(luò)中的節(jié)點隨機選取出一個序列，按順序?qū)⒚總€節(jié)點賦給鄰居節(jié)點所在的社區(qū)，取平均比特下降最大時的社區(qū)賦給該節(jié)點，如果沒有下降，則該點的社區(qū)不變；

3)重復2)直到平均每步編碼長度不再變化；

4)得到網(wǎng)絡(luò)G的社區(qū)結(jié)構(gòu)。

1.2 相似度方法

現(xiàn)有的基于相似度的鏈接預(yù)測方法由于計算復雜度低，得到了較廣泛的應(yīng)用。CN、AA、RA、Jaccard、 PA及基于節(jié)點間路徑指數(shù)的Katz和局部路徑指數(shù)(Local Path， LP)是七種經(jīng)典的鏈接預(yù)測方法,見表1。

表1 七種經(jīng)典鏈接預(yù)測方法簡介表

2 融合社區(qū)結(jié)構(gòu)和節(jié)點度的局部路徑相似度的蛋白質(zhì)鏈接預(yù)測方法

社區(qū)結(jié)構(gòu)信息可以為鏈接預(yù)測提供重要信息[17]?？紤]到傳統(tǒng)鏈接預(yù)測方法存在的不足，結(jié)合蛋白質(zhì)交互網(wǎng)絡(luò)的特點及復雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特性，提出一種融合社區(qū)結(jié)構(gòu)和節(jié)點度的局部路徑相似度的蛋白質(zhì)鏈接預(yù)測方法，預(yù)測蛋白質(zhì)與蛋白質(zhì)之間交互作用。主要分為四步：

1) 利用Infomap方法將網(wǎng)絡(luò)中節(jié)點劃分成多個社區(qū);

2) 計算每個社區(qū)的緊密度指標;

3)計算基于節(jié)點度的局部路徑相似度(Localpathsimilaritybasedonnodedegree，DLP);

4)結(jié)合社區(qū)緊密度指標和DLP，共同預(yù)測蛋白質(zhì)交互網(wǎng)絡(luò)中的潛在鏈接。

2.1 基于Infomap的社區(qū)發(fā)現(xiàn)方法

示例網(wǎng)絡(luò)圖如圖1所示。

根據(jù)1.1介紹的Infomap方法，首先將示例網(wǎng)絡(luò)(見圖1(a))進行社區(qū)劃分，社區(qū)發(fā)現(xiàn)的結(jié)果見圖1(b) ，示例網(wǎng)絡(luò)被分成兩個社區(qū)A和B。

2.2 社區(qū)緊密度

在進行計算社區(qū)緊密度之前，首先刪除比例為δ的鏈接作為測試集，在3.4的實驗中，將δ分別取為5%、10%和20%。在本節(jié)刪除10%的示例網(wǎng)絡(luò)已有鏈接作為演示，假如刪除的鏈接為1-5和9-10，得到的測試網(wǎng)絡(luò)如圖2所示。

我們注意到這樣一個事實：位于同一社區(qū)內(nèi)節(jié)點間的關(guān)系通常會更緊密。因此，定義一個社區(qū)緊密度，計算社區(qū)內(nèi)節(jié)點之間的平均最短路徑，用它來衡量社區(qū)的緊密度。圖2刪除測試集的示例中，A社區(qū)的平均最短路徑為1.7，B社區(qū)的平均最短路徑為1.3，可以發(fā)現(xiàn)，B社區(qū)比A社區(qū)內(nèi)節(jié)點聯(lián)系更緊密。也就是說社區(qū)的平均最短路徑越小，社區(qū)內(nèi)節(jié)點之間的鏈接愈緊密，即社區(qū)緊密度與社區(qū)平均最短路徑成反比。

2.3 基于節(jié)點度的局部路徑相似度

蛋白質(zhì)交互網(wǎng)絡(luò)中聯(lián)系比較稀疏，節(jié)點之間具有的共同鄰居也相對較少。為了解決傳統(tǒng)鏈接預(yù)測方法，僅考慮共同鄰居信息的不足，文中方法引入節(jié)點間次級鄰居信息[16]，將節(jié)點間共同鄰居、次級鄰居與節(jié)點自身的度相結(jié)合，共同預(yù)測蛋白質(zhì)網(wǎng)絡(luò)中潛在鏈接的概率。

示例網(wǎng)絡(luò)中A社區(qū)結(jié)構(gòu)如圖3所示。

分析示例網(wǎng)絡(luò)1-3(節(jié)點1與節(jié)點3之間的鏈接)和節(jié)點1-5存在鏈接的概率大小來說明文中方法的有效性。在圖3中，1-3和1-5的共同鄰居都是2個。若僅利用共同鄰居進行鏈接預(yù)測，則1-3和1-5產(chǎn)生鏈接的概率相同，但從示例網(wǎng)絡(luò)中可以明顯看出，1-5鏈接的可能性高于1-3，即僅利用節(jié)點間的共同鄰居估計兩節(jié)點鏈接的概率是不準確的。因此，在共同鄰居的基礎(chǔ)上，挖掘次級鄰居對節(jié)點間鏈接可能性的貢獻。事實上，網(wǎng)絡(luò)中節(jié)點4作為節(jié)點1的次級鄰居對于1-5的鏈接有著積極貢獻。與此同時，假設(shè)節(jié)點間的鏈接概率與目標節(jié)點本身的度呈反比關(guān)系，即目標節(jié)點的度越大，節(jié)點間鏈接的概率越小。

考慮到次級鄰居和目標節(jié)點度對最終鏈接產(chǎn)生的影響，文中定義一個基于節(jié)點度的局部路徑相似度DLP，具體如下

式中：ka----節(jié)點a的度；

kb----節(jié)點b的度；

M----網(wǎng)絡(luò)的鄰接矩陣。

文中方法旨在通過結(jié)合社區(qū)緊密度和基于節(jié)點度的局部路徑相似度兩個主要方面預(yù)測網(wǎng)絡(luò)中節(jié)點間的相似度，具體定義如下

式中：λa----節(jié)點a所在社區(qū)的平均最短路徑;

1/λa----節(jié)點a所在社區(qū)的緊密度定義。

文中方法在圖2的示例網(wǎng)絡(luò)上進行驗證，圖2存在49對沒有鏈接的節(jié)點對，實驗結(jié)果中，相似度最高的五對節(jié)點對見表2。

表2 示例網(wǎng)絡(luò)的預(yù)測結(jié)果Top5

表1中加黑字體標注的是刪除的節(jié)點對，在49對沒有鏈接的節(jié)點對中，刪除的9-10和1-5節(jié)點對的相似度排在前四的位置上，表明了本方法的有效性。

2.4 方法流程

提出一種融合社區(qū)結(jié)構(gòu)和節(jié)點度的局部路徑相似度的蛋白質(zhì)鏈接預(yù)測方法，PIPM方法具體步驟為：

輸入：網(wǎng)絡(luò)G的鏈接集合；

輸出：未鏈接節(jié)點間的相似性分數(shù)。

1)使用社區(qū)發(fā)現(xiàn)方法Infomap，將網(wǎng)絡(luò)劃分成多個社區(qū)；

2)根據(jù)上一步所劃分的社區(qū)結(jié)構(gòu)，計算社區(qū)緊密度；

3)計算基于節(jié)點度的局部路徑相似度DLP；

4)結(jié)合社區(qū)緊密度和DLP計算未連接節(jié)點間的相似度分數(shù)。

3 實驗與分析

3.1 實驗環(huán)境

為說明文中方法的有效性，使用Python實現(xiàn)了PIPM方法以及七種對比方法。使用的電腦配置為：處理器 3.3 GHz Intel Core i7，內(nèi)存16 GB 1 867 MHz DDR3。實驗數(shù)據(jù)集是酵母蛋白質(zhì)交互網(wǎng)絡(luò)(PPI)。實驗次數(shù)為20次。

3.2 數(shù)據(jù)集

實驗使用文獻[18]中的核心數(shù)據(jù)集作為實驗數(shù)據(jù)集，進行蛋白質(zhì)交互網(wǎng)絡(luò)上的鏈接預(yù)測。該數(shù)據(jù)集有1 647個蛋白質(zhì)(節(jié)點)，2 518對相互作用(鏈接)。同時，將網(wǎng)絡(luò)中的鏈接隨機劃分為訓練集和測試集。

3.3 評價指標

為了從整體上衡量文中方法的精確度，使用AUC(Ares Under receiver operating characteristic Curve)評價指標[19]，它是衡量鏈接預(yù)測方法有效性的常用指標，AUC值在0與1之間，越接近1，表示預(yù)測效果越好。實驗中，獨立進行n次比較，每次在測試集中隨機選擇一條邊l1，在實際不存在的邊中隨機選擇一條邊l2，如果其中l(wèi)1的相似度分數(shù)高于l2有n′次，l1的相似度分數(shù)等于l2有n″次，則AUC值可以通過下式計算

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

在文中數(shù)據(jù)集上，每種方法進行20次獨立實驗，然后計算其平均值。各方法的AUC結(jié)果如圖4所示。

測試集分別為5%、10%和20%，得到了上述結(jié)果。實驗結(jié)果采用柱狀圖表示。顯然，文中方法在酵母蛋白質(zhì)交互網(wǎng)絡(luò)獲得了最好的實驗結(jié)果。通過實驗結(jié)果發(fā)現(xiàn)，PIPM方法在蛋白質(zhì)交互網(wǎng)絡(luò)上都優(yōu)于其他方法。

4 結(jié) 語

提出一種融合社區(qū)結(jié)構(gòu)和節(jié)點度的局部路徑相似度的蛋白質(zhì)鏈接預(yù)測方法，旨在通過分析蛋白質(zhì)交互網(wǎng)絡(luò)的結(jié)構(gòu)特點，同時結(jié)合社區(qū)結(jié)構(gòu)和基于節(jié)點度的局部路徑相似度來共同預(yù)測蛋白質(zhì)交互網(wǎng)絡(luò)中潛在的鏈接。在真實的蛋白質(zhì)交互網(wǎng)絡(luò)進行試驗，表明預(yù)測節(jié)點間的缺失鏈接具有顯著效果，并且在不增加復雜性的情況下，比現(xiàn)有的經(jīng)典方法在各種真實網(wǎng)絡(luò)上表現(xiàn)更好。下一步工作擬將文獻[20]中的深度學習方法與鏈接預(yù)測相結(jié)合，進一步提高鏈接預(yù)測的準確率。