王金哲， 王遠(yuǎn)威， 王紅梅

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

0 引 言

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

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

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

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

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

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

1 相關(guān)理論

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

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

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

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

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

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

3)重復(fù)2)直到平均每步編碼長(zhǎng)度不再變化；

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

1.2 相似度方法

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

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

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

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

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

2) 計(jì)算每個(gè)社區(qū)的緊密度指標(biāo);

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

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

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

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

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

2.2 社區(qū)緊密度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 方法流程

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

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

輸出：未鏈接節(jié)點(diǎn)間的相似性分?jǐn)?shù)。

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

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

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

4)結(jié)合社區(qū)緊密度和DLP計(jì)算未連接節(jié)點(diǎn)間的相似度分?jǐn)?shù)。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

3.3 評(píng)價(jià)指標(biāo)

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

3.4 實(shí)驗(yàn)結(jié)果與分析

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

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

4 結(jié) 語(yǔ)

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