葛永錱， 趙熙強(qiáng)

(中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 山東 青島 266100)

細(xì)胞之間的交互過(guò)程通常是由蛋白質(zhì)復(fù)合物而不是單個(gè)蛋白質(zhì)來(lái)完成的[1-2]。蛋白質(zhì)復(fù)合物是一組相互作用的蛋白質(zhì)，它們形成一個(gè)單獨(dú)的多分子機(jī)器[3]， 彼此之間合作來(lái)執(zhí)行它們的生物學(xué)功能?？梢哉f(shuō)，蛋白質(zhì)復(fù)合物是活細(xì)胞內(nèi)生物過(guò)程的重要功能單位。研究蛋白質(zhì)復(fù)合物，有助于人們更深入地研究生物體的生命特征、細(xì)胞系統(tǒng)的行為、疾病的發(fā)病機(jī)理等諸多生物醫(yī)學(xué)課題。

通過(guò)實(shí)驗(yàn)手段從大量的蛋白質(zhì)中尋找潛在的復(fù)合物，無(wú)疑是低效的。而隨著高通量實(shí)驗(yàn)技術(shù)的發(fā)展，使得研究人員獲得了大量的蛋白質(zhì)相互作用數(shù)據(jù)，這就使得從蛋白質(zhì)交互(PPI)網(wǎng)絡(luò)中檢測(cè)、探尋蛋白質(zhì)復(fù)合物成為了可能。

PPI網(wǎng)絡(luò)可以通過(guò)無(wú)向圖來(lái)進(jìn)行建模表示。在過(guò)去的十幾年中，人們通過(guò)對(duì)圖論、計(jì)算數(shù)學(xué)、統(tǒng)計(jì)學(xué)等學(xué)科中的方法加以研究，獲得了許多從PPI網(wǎng)絡(luò)中發(fā)現(xiàn)蛋白質(zhì)復(fù)合物的方法，例如MCL[4]、MCODE[5]、RNSC[6]、CMC[7]、COACH[8]、ClusterONE[9]、ProRank+[10]、WPNCA[11]和RWRB[12]。這些方法的主要策略是從單個(gè)蛋白質(zhì)出發(fā)，從PPI網(wǎng)絡(luò)中提取高度鏈接的節(jié)點(diǎn)以形成簇，這些簇有可能成為蛋白質(zhì)復(fù)合物的候選者。

但是，隨著PPI網(wǎng)絡(luò)中交互信息越來(lái)越多，傳統(tǒng)的從單個(gè)蛋白質(zhì)出發(fā)尋找連接度高的節(jié)點(diǎn)形成簇的方法越來(lái)越不適用。因?yàn)殡S著交互信息的增多，這種方法所形成簇的規(guī)模也越來(lái)越大，與已知的復(fù)合物匹配度也越來(lái)越低。為此需要尋找更合適的蛋白質(zhì)復(fù)合物探測(cè)方法。

本文提出了一種基于圖嵌入和布谷鳥搜索的二步蛋白質(zhì)復(fù)合物預(yù)測(cè)方法(TSSComplex)。該方法將最優(yōu)化問(wèn)題中布谷鳥搜索方法的思想引入蛋白質(zhì)復(fù)合物的搜尋中，代替?zhèn)鹘y(tǒng)的從單個(gè)蛋白質(zhì)出發(fā)的搜索方法。利用相似度和親和度來(lái)聚類蛋白質(zhì)，從而獲得候選簇。這樣可以有效控制簇的規(guī)模，從而提高匹配率。另一方面，引入圖嵌入技術(shù)，來(lái)獲得PPI網(wǎng)絡(luò)中節(jié)點(diǎn)的低維表示，并將兩個(gè)節(jié)點(diǎn)表示向量之間的距離和傳統(tǒng)的邊權(quán)結(jié)合起來(lái)，形成了新的邊權(quán)算法。之所以引入圖嵌入方法，是因?yàn)樗鼘⒚總€(gè)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)映射到低維向量表示中，可以很好地保留原始網(wǎng)絡(luò)的鄰近性[13-15]。圖嵌入方法可以從原始網(wǎng)絡(luò)中自動(dòng)發(fā)現(xiàn)有用和潛在的特征，而非人工制作的網(wǎng)絡(luò)特征。同時(shí)有研究表明，在節(jié)點(diǎn)分類[16]、鏈路預(yù)測(cè)[17]、節(jié)點(diǎn)聚類[18]等與網(wǎng)絡(luò)相關(guān)的任務(wù)中，圖嵌入方法都是非常有效的。在PPI網(wǎng)絡(luò)應(yīng)用方面，Liu Xiaoxia等就曾將圖嵌入技術(shù)用于不同物種間的PPI網(wǎng)絡(luò)整合，取得了較好的結(jié)果[19]。

1 方法

基于圖嵌入和布谷鳥搜索的二步蛋白質(zhì)復(fù)合物預(yù)測(cè)方法主要分為三個(gè)步驟。第一步是利用圖嵌入技術(shù)，用低維向量表示PPI網(wǎng)絡(luò)中的蛋白質(zhì)節(jié)點(diǎn)。然后，通過(guò)節(jié)點(diǎn)的低維向量表示和節(jié)點(diǎn)本身的網(wǎng)絡(luò)結(jié)構(gòu)給PPI網(wǎng)絡(luò)中的邊賦權(quán)。第二步是通過(guò)布谷鳥搜索，獲取潛在的蛋白質(zhì)復(fù)合物。第三步是針對(duì)布谷鳥搜索之后的剩余蛋白質(zhì)節(jié)點(diǎn)，利用傳統(tǒng)搜索方法，進(jìn)行二次搜索。

1.1圖嵌入和蛋白質(zhì)的低維向量表示

圖嵌入技術(shù)是一種對(duì)網(wǎng)絡(luò)圖中的節(jié)點(diǎn)在向量空間進(jìn)行分布表示的一種技術(shù)。該技術(shù)最早來(lái)源于自然語(yǔ)言數(shù)據(jù)挖掘領(lǐng)域[20]。其最初希望通過(guò)將單詞在向量空間中進(jìn)行分布表示，以幫助學(xué)習(xí)算法對(duì)相似的單詞進(jìn)行分組，從而在自然語(yǔ)言處理任務(wù)中能夠達(dá)到更好的性能。最早使用表示形式進(jìn)行單詞研究要追溯到1986年，源于Rumelhart、Hinton和Williams[21]。此后，該方法被不斷地發(fā)展。最近，Mikolov等給出了一種Skip-gram模型，這是一種從大量非結(jié)構(gòu)化文本數(shù)據(jù)中學(xué)習(xí)高質(zhì)量的單詞向量表示的有效方法[22]。隨后，又有研究者將這種向量表示方法從線性結(jié)構(gòu)的自然語(yǔ)言處理引入到各種網(wǎng)絡(luò)結(jié)構(gòu)中。Aditya Grover等在前人的研究成果上，提出了一種成熟完善的圖嵌入算法—node2vec算法[15]。本文使用node2vec算法，將PPI網(wǎng)絡(luò)中的蛋白質(zhì)節(jié)點(diǎn)映射到低維向量空間上。

令G=(V,E)是一個(gè)給定的PPI網(wǎng)絡(luò)，V是蛋白質(zhì)節(jié)點(diǎn)集合，E是節(jié)點(diǎn)之間的邊集合，每一條邊表示一對(duì)蛋白質(zhì)交互。目標(biāo)是將每一個(gè)節(jié)點(diǎn)u∈V表示成一個(gè)低維空間Rd中的向量。即學(xué)習(xí)一個(gè)映射函數(shù)f:V→Rd，這里d?|V|，d是一個(gè)參數(shù)，指定向量表示的維數(shù)。

1.1.1 優(yōu)化函數(shù) 我們希望下面的目標(biāo)函數(shù)達(dá)到最大值，即在給定f的條件下，希望網(wǎng)絡(luò)鄰居NS(u)的對(duì)數(shù)似然概率達(dá)到最大：

(1)

式中NS(u)?V是通過(guò)鄰域采樣策略S產(chǎn)生的節(jié)點(diǎn)u的網(wǎng)絡(luò)鄰居。

為了使這個(gè)最優(yōu)化問(wèn)題易于處理，兩個(gè)標(biāo)準(zhǔn)假設(shè)是必須的[15]。

第一個(gè)假設(shè)是條件獨(dú)立性。我們假設(shè)鄰域中每個(gè)節(jié)點(diǎn)被觀察的可能性是相互獨(dú)立的，那么似然函數(shù)可以進(jìn)行因式分解，從而給定源的特征表示:

(2)

第二個(gè)假設(shè)是特征空間的對(duì)稱性。源節(jié)點(diǎn)和鄰域節(jié)點(diǎn)在特征空間中具有對(duì)稱效應(yīng)。因此，我們將每個(gè)源-鄰域節(jié)點(diǎn)對(duì)的條件似然建模為一個(gè)softmax單元，并通過(guò)其特征的點(diǎn)積進(jìn)行參數(shù)化:

(3)

則公式(1)可改寫為

(4)

其中Zu=∑v∈Vexp(f(u)·f(v))。在大型網(wǎng)絡(luò)中該目標(biāo)函數(shù)的計(jì)算代價(jià)是昂貴的，因此可以采用負(fù)采樣方法來(lái)逼近[19]。本文采用模擬退火算法來(lái)優(yōu)化上述目標(biāo)函數(shù)。

1.1.2 鄰域采樣策略 對(duì)于線性自然語(yǔ)言文本，可使用句子中連續(xù)單詞上的滑動(dòng)窗口自然地定義單詞序列概念[22]。然而PPI網(wǎng)絡(luò)不同，它不是線性的，因此需要重新選擇一種適合節(jié)點(diǎn)鄰居的產(chǎn)生方式。常見(jiàn)的鄰域采樣策略有兩種：廣度優(yōu)先采樣(BFS)和深度優(yōu)先采樣(DFS)[15]。Aditya Grover等在node2vec算法中設(shè)計(jì)了一種靈活的鄰域采樣策略，能夠平滑地在BFS和DFS之間進(jìn)行插值[15]。因此，該方法可兼顧BFS和DFS的優(yōu)點(diǎn)。

首先，對(duì)于給定的源節(jié)點(diǎn)u，我們仿真一條固定長(zhǎng)度為l的隨機(jī)游走。令ci表示隨機(jī)游走鏈上的第i個(gè)節(jié)點(diǎn)，那么起點(diǎn)即c0=u。節(jié)點(diǎn)ci通過(guò)如下分布產(chǎn)生：

(5)

式中：πvx是節(jié)點(diǎn)v和x之間非正則化的轉(zhuǎn)移概率；Z是正則常數(shù)。

讓隨機(jī)游動(dòng)產(chǎn)生偏差的最簡(jiǎn)單方法是基于靜態(tài)邊權(quán)值對(duì)下一個(gè)節(jié)點(diǎn)進(jìn)行采樣，即πvx=wvx。然而，這并不利于解釋網(wǎng)絡(luò)結(jié)構(gòu)。為此，定義基于兩個(gè)參數(shù)p和q的一個(gè)二階隨機(jī)游走?？紤]一個(gè)隨機(jī)游走穿過(guò)邊(t,v)且現(xiàn)在停駐在點(diǎn)v?，F(xiàn)在隨機(jī)游走需要決定下一步的方向，因此需要評(píng)估由v引導(dǎo)的邊(v,x)的轉(zhuǎn)移概率πvx。我們令非正則化的轉(zhuǎn)移概率為πvx=αpq(t,x)·wvx，這里

(6)

且dtx記錄了節(jié)點(diǎn)t和x之間的最短距離。注意到dtx一定是{0,1,2}之一，因此兩個(gè)參數(shù)是必要的，并且足夠指導(dǎo)隨機(jī)游走。

通過(guò)將節(jié)點(diǎn)映射成低維向量的圖嵌入技術(shù)，可以將相似的蛋白質(zhì)節(jié)點(diǎn)嵌入到一起，因此能夠捕獲PPI網(wǎng)絡(luò)的內(nèi)部關(guān)系。

1.2 布谷鳥搜索

布谷鳥搜索算法(Cuckoo search， CS)是Yang Xinshe等提出的一種最優(yōu)化搜索算法[23]。自然界中，布谷鳥不會(huì)自己搭建巢穴，而是隨機(jī)尋找鳥巢來(lái)孵化自己的蛋，布谷鳥的蛋與宿主巢穴中的鳥蛋越相似，就越不容易被宿主發(fā)現(xiàn)，從而也就越不容易被宿主拋棄。布谷鳥搜索算法正是模擬這一生物現(xiàn)象而提出的一種問(wèn)題尋優(yōu)算法。Gao Yin等又將CS算法的搜尋機(jī)理用在PPI網(wǎng)絡(luò)復(fù)合物預(yù)測(cè)中，并在酵母PPI網(wǎng)絡(luò)中對(duì)蛋白質(zhì)復(fù)合物進(jìn)行預(yù)測(cè)，取得了較好的結(jié)果[24]。本文也借鑒了Gao Yin等的想法。

首先對(duì)PPI網(wǎng)絡(luò)中的邊進(jìn)行賦權(quán)。Wang等[25]和Peng等[11]引入了一種名為ECC(Edge clustering coefficient)的邊聚類系數(shù)，來(lái)為網(wǎng)絡(luò)中的邊加權(quán)。

(7)

式中：Zuv是節(jié)點(diǎn)u和v的公共鄰居集合；d(u)表示節(jié)點(diǎn)u的度。為了進(jìn)一步刻畫兩個(gè)相鄰節(jié)點(diǎn)u和v的共同領(lǐng)域之間的連通性，Ma Chengyu等引入了一種新的邊聚類系數(shù)NECC(New edge clustering coefficient)[26]。該思想是用進(jìn)一步分層的方式估計(jì)u和v的鄰域連通性。NECC的定義如下：

(8)

其中

(9)

顯然，NECC更廣泛地考慮了兩個(gè)相鄰節(jié)點(diǎn)的整個(gè)鄰域的連通性，可以更好地確定某個(gè)蛋白質(zhì)是否屬于一個(gè)復(fù)合物。

再結(jié)合通過(guò)圖嵌入技術(shù)將蛋白質(zhì)節(jié)點(diǎn)映射成的低維向量，本文定義了屬于自己的邊加權(quán)方式，即兩個(gè)相鄰節(jié)點(diǎn)u和v之間的邊權(quán)為

Wuv=Dist(u,v)·NECC(u,v) 。

(10)

式中Dist(u,v)是節(jié)點(diǎn)u和v之間通過(guò)表示向量計(jì)算的歐氏距離。這種賦權(quán)方式既考慮了PPI網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，又考慮了節(jié)點(diǎn)的空間結(jié)構(gòu)，從而能夠更準(zhǔn)確地衡量節(jié)點(diǎn)之間的相似度。

之后可以開(kāi)始正式進(jìn)行布谷鳥搜索。布谷鳥搜索算法主要分為四步。

第一步，確定聚類的中心點(diǎn)。我們根據(jù)式(1)計(jì)算節(jié)點(diǎn)的加權(quán)度：

(11)

然后選擇加權(quán)度大于閾值的節(jié)點(diǎn)作為聚類的中心點(diǎn)。不同于Gao Yin等以所有節(jié)點(diǎn)的平均加權(quán)度為閾值，本文采用所有非0加權(quán)度的中位數(shù)作為閾值，之所以采用這種閾值取法，是為了避免一些極端值(比如孤立點(diǎn)以及一些度特別大的點(diǎn))對(duì)整體取值的影響。

第二步，獲取初始簇。對(duì)于一個(gè)聚類中心u，判斷每一個(gè)與其有交互的蛋白質(zhì)節(jié)點(diǎn)v與該中心u的相似度(即邊權(quán))，若相似度大于閾值，則將v歸入到以u(píng)為中心的簇里。待所有與u有交互的節(jié)點(diǎn)都判斷完成后，則形成一個(gè)以u(píng)為中心的初始簇。對(duì)每一個(gè)聚類中心，按此法形成若干個(gè)大小不同的初始簇。這里的閾值取法如下：將所有邊權(quán)從小到大排列，去掉0值之后，取剩下數(shù)值的上四分位數(shù)作為閾值，之所以取上四分位數(shù)，是因?yàn)檫@時(shí)能夠相對(duì)更好地控制一個(gè)復(fù)合物的規(guī)模。

第三步，簇的擴(kuò)充。對(duì)于還未屬于任一個(gè)簇的蛋白質(zhì)節(jié)點(diǎn)，判斷其與每一個(gè)簇的親和度，并將其歸入到親和度大于閾值的簇中。蛋白質(zhì)節(jié)點(diǎn)u和簇C之間的親和度計(jì)算方法如下：

(12)

且親和度的閾值一般取2。待所有節(jié)點(diǎn)判斷完成，則獲得了所有潛在的蛋白質(zhì)復(fù)合物。

第四步，合并與剔除。我們用重疊得分OS(A,B)來(lái)度量?jī)蓚€(gè)蛋白質(zhì)復(fù)合物之間的相似度。如果兩個(gè)蛋白質(zhì)復(fù)合物之間的重疊得分OS(Overlapping score)大于給定的閾值，則將兩個(gè)復(fù)合物合并。兩個(gè)復(fù)合物A和B的重疊得分計(jì)算方式如下：

(13)

式中VA表示A復(fù)合物中蛋白質(zhì)集合。顯著的，這種重疊得分已經(jīng)被用在許多以往的研究中，來(lái)判斷一個(gè)預(yù)測(cè)的復(fù)合物與一個(gè)已知的復(fù)合物是否匹配[5,8,11,27-28]。代表性的，如果OS(A,B)≥0.2，則復(fù)合物A和B被視為匹配的。這個(gè)閾值同樣適用于判斷兩個(gè)預(yù)測(cè)的蛋白質(zhì)復(fù)合物需不需要合并。

為了保證候選復(fù)合物的高質(zhì)量，我們采用加權(quán)邊密度進(jìn)行評(píng)估。邊密度的概念最先由Coleman和More提出[29]，Ma Chengyu等對(duì)其進(jìn)行了拓展[26]。給定一個(gè)圖G=(V,E,W),加權(quán)邊密度(Density，den)的定義如下：

(14)

對(duì)于一個(gè)蛋白質(zhì)復(fù)合物C，同樣可以計(jì)算其加權(quán)邊密度。我們剔除那些加權(quán)邊密度小于閾值(這里一般取0.1，這是由于CORUM參考復(fù)合物集合中的復(fù)合物其加權(quán)邊密度基本大于0.1)的或只包含一個(gè)蛋白質(zhì)的復(fù)合物。保留下來(lái)的，即為通過(guò)布谷鳥搜索預(yù)測(cè)獲得的預(yù)測(cè)蛋白質(zhì)復(fù)合物。

當(dāng)然在這一步中，涉及一些閾值的選取問(wèn)題，不同的閾值設(shè)置肯定會(huì)對(duì)結(jié)果產(chǎn)生一定的影響，什么樣的閾值設(shè)置是最好的，是我們還在繼續(xù)研究的內(nèi)容。

1.3 二次搜索

布谷鳥搜索方法以加權(quán)度大于閾值的節(jié)點(diǎn)作為聚類中心，這樣很容易略掉一些由加權(quán)度不大的蛋白質(zhì)構(gòu)成的復(fù)合物，尤其是一些小型復(fù)合物。因此，在布谷鳥搜索結(jié)束后，還需對(duì)未被納入復(fù)合物當(dāng)中的蛋白質(zhì)進(jìn)行二次搜索。我們參考NEOComplex算法[25]，構(gòu)造二次搜索方法。

將通過(guò)布谷鳥搜索獲得的復(fù)合物中包含的蛋白質(zhì)及其相關(guān)的交互邊從PPI網(wǎng)絡(luò)中刪除，在剩下的子圖網(wǎng)絡(luò)G1中進(jìn)行二次搜索。二次搜索過(guò)程如下：以G1中的一個(gè)蛋白質(zhì)節(jié)點(diǎn)v1為種子節(jié)點(diǎn)，從G1的與v1有邊相連的節(jié)點(diǎn)中選取邊權(quán)最大的節(jié)點(diǎn)v2，加到v1的簇中；再?gòu)腉1的與v2有邊相連的節(jié)點(diǎn)中選取邊權(quán)最大的節(jié)點(diǎn)v3，加到{v1,v2}的簇中，以此類推，直至簇的加權(quán)邊密度小于閾值0.1為止。以G1的每一個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，分別按照上述規(guī)則進(jìn)行搜索，均可以獲得一個(gè)潛在的蛋白質(zhì)復(fù)合物。再將這些潛在的蛋白質(zhì)復(fù)合物按照布谷鳥搜索中第四步的合并與剔除規(guī)則進(jìn)行合并與剔除處理，保留下來(lái)的蛋白質(zhì)復(fù)合物就是二次搜索獲得的預(yù)測(cè)蛋白質(zhì)復(fù)合物。

兩次搜索獲得的預(yù)測(cè)蛋白質(zhì)共同構(gòu)成了我們二步搜索算法探測(cè)得到的蛋白質(zhì)復(fù)合物。

1.4 主要算法

對(duì)于給定的蛋白質(zhì)交互網(wǎng)絡(luò)(PPI網(wǎng)絡(luò))G=(V,E)，完整的復(fù)合物探測(cè)算法TSSComplex如下。

TSSComplex算法

步驟1. 準(zhǔn)備工作

步驟1.1 根據(jù)G=(V,E)，計(jì)算每條邊的邊聚類系數(shù)NECC。

步驟1.2 以NECC為初始邊權(quán)，根據(jù)隨機(jī)游走策略，確定每個(gè)頂點(diǎn)的鄰居NS(u)。

步驟1.3 根據(jù)圖嵌入技術(shù)，最優(yōu)化目標(biāo)函數(shù)，將每個(gè)蛋白質(zhì)節(jié)點(diǎn)映射到低維向量空間。

步驟1.4 根據(jù)Wuv=Dist(u,v)·NECC(u,v)更新邊權(quán)。

步驟2. 第一步搜索：布谷鳥搜索

步驟2.1 計(jì)算每個(gè)蛋白質(zhì)節(jié)點(diǎn)的加權(quán)度。

步驟2.2 將加權(quán)度大于閾值的節(jié)點(diǎn)作為初始簇中心。

步驟2.3 對(duì)于每一個(gè)簇中心，判斷與該簇中心相連接的節(jié)點(diǎn)與簇中心的相似度是否大于閾值，將大于閾值的節(jié)點(diǎn)歸入該簇。

步驟2.4 對(duì)于剩余的節(jié)點(diǎn)，計(jì)算其與每一個(gè)簇的親和度，并將其歸入親和度大于閾值的簇。

步驟2.5 合并重疊得分OS≥0.2的簇。

步驟2.6 刪除邊密度小于0.1或僅包含一個(gè)蛋白質(zhì)的簇。

步驟3. 第二步搜索：二次搜索

將步驟2中獲得的復(fù)合物中所包含的蛋白質(zhì)及其相關(guān)的邊從PPI網(wǎng)絡(luò)中移除，剩下的節(jié)點(diǎn)與邊構(gòu)成子圖G1=(V1,E1)，在G1中進(jìn)行二次搜索。

步驟3.1 以G1中任意一點(diǎn)v1為種子節(jié)點(diǎn)，在G1中尋找與v1相連且邊權(quán)最大的節(jié)點(diǎn)v2加入該簇，再尋找與v2相連且邊權(quán)最大的v3加入該簇，直至簇的邊密度小于0.1。

步驟3.2 對(duì)G1中的每一個(gè)節(jié)點(diǎn)重復(fù)進(jìn)行步驟3.1，共獲得|V1|個(gè)簇。

步驟3.3 根據(jù)合并與剔除規(guī)則處理步驟3.2中獲得的簇。

步驟4. 將步驟2和步驟3中保留下來(lái)的簇輸出。其每一個(gè)簇即為一個(gè)通過(guò)TSSComplex算法獲得的蛋白質(zhì)復(fù)合物。

算法的簡(jiǎn)易流程見(jiàn)圖1。

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

我們將TSSComplex算法應(yīng)用于人類的PPI網(wǎng)絡(luò)，與其他幾種蛋白質(zhì)復(fù)合物探測(cè)方法作比較，同時(shí)結(jié)合數(shù)據(jù)集的特征，作綜合分析，以評(píng)估算法的性能。

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

人類PPI網(wǎng)絡(luò)通過(guò)聯(lián)合HPDR(Human Protein Refe-rence Database)[30]和BioGRID(version 3.5.173)[31]數(shù)據(jù)共同構(gòu)建。最終獲得的人類PPI網(wǎng)絡(luò)中一共包含18 004個(gè)蛋白質(zhì)節(jié)點(diǎn)和339 054條交互(邊)。

為評(píng)估預(yù)測(cè)的蛋白質(zhì)復(fù)合物，我們使用CORUM(Comprehensive Resource of Mammalian)作為蛋白質(zhì)復(fù)合物參考集[32]。該集合具有較高的可靠性。它一共收錄了2 916個(gè)蛋白質(zhì)復(fù)合物，其中有2 643個(gè)復(fù)合物包含2個(gè)及以上的蛋白質(zhì)。我們將這2 643個(gè)復(fù)合物作為參考集。這些復(fù)合物一共涉及3 627個(gè)蛋白質(zhì)和93 884條交互。

圖1 TSSComplex算法的流程圖Fig.1 Flow chart of TSSComplex algorithm

2.2 性能標(biāo)準(zhǔn)

為評(píng)估我們預(yù)測(cè)結(jié)果的質(zhì)量，我們計(jì)算了兩個(gè)在文獻(xiàn)中廣泛使用的統(tǒng)計(jì)指標(biāo)：精確度和召回率。精確度是與至少一個(gè)已知復(fù)合物相匹配的預(yù)測(cè)復(fù)合物的數(shù)量與所有預(yù)測(cè)復(fù)合物的數(shù)量的比值：

(15)

式中：PC(Prediction complex)是預(yù)測(cè)的復(fù)合物集合；RC(Reference complex)是CORUM提供的參考復(fù)合物集合。召回率是已知復(fù)合物中符合至少一個(gè)預(yù)測(cè)復(fù)合物的比例：

(16)

F-measure是精確度和召回率的調(diào)和平均值，表示預(yù)測(cè)結(jié)果的總體表現(xiàn)，即

(17)

2.3 性能比較

我們將TSSComplex算法的性能和8種蛋白質(zhì)鑒定技術(shù)(MCL[4]、MCODE[5]、CMC[7]、COACH[8]、ClusterONE[9]、ProRank+[10]、PEWCC[32]和NEOComplex[26])做了比較(見(jiàn)表1)。

表1 9種方法的性能比較Table 1 Performance comparison of nine methods

表1報(bào)告了包括TSSComplex在內(nèi)的所有競(jìng)爭(zhēng)方法的比較結(jié)果。如果僅從數(shù)值上看，TSSComplex算法并不是特別理想，但TSSComplex算法依然有其研究的價(jià)值，其理由主要有以下三個(gè)原因。

原因1：隨著PPI網(wǎng)絡(luò)中蛋白質(zhì)交互信息的不斷增多，其他方法將逐漸失效。

以其他8種算法中性能最好的NEOComplex算法為例，NEOComplex算法的PPI網(wǎng)絡(luò)數(shù)據(jù)來(lái)自HPRD和BioGRID(version 3.2.109)，共包含15 459個(gè)蛋白質(zhì)和144 895條交互。而本文使用的來(lái)自HPRD和BioGRID(version 3.5.173)，共包含了18 004個(gè)蛋白質(zhì)和339 054條交互。可以發(fā)現(xiàn)，蛋白質(zhì)數(shù)量增長(zhǎng)了不到20%(僅增長(zhǎng)了16.46%)，但蛋白質(zhì)之間的交互數(shù)量卻增長(zhǎng)了一倍多(增長(zhǎng)了134%)。交互信息的大量增多，使得各種搜索方法產(chǎn)生的復(fù)合物容量越來(lái)越大。我們?cè)诒疚牡臄?shù)據(jù)集上測(cè)試了NEOComplex算法，發(fā)現(xiàn)該算法獲得的復(fù)合物容量基本在500以上，一個(gè)復(fù)合物里包含了500個(gè)以上的蛋白質(zhì)。而根據(jù)匹配規(guī)則，兩個(gè)復(fù)合物之間的重疊率要達(dá)到0.2才算匹配成功。以一個(gè)容量為500的復(fù)合物A計(jì)算，若一個(gè)復(fù)合物B能與其匹配成功，該復(fù)合物B的容量至少為100。而CORUM提供的人類2 643個(gè)蛋白質(zhì)復(fù)合物中，僅有兩個(gè)復(fù)合物的容量超過(guò)了100。也就是說(shuō)，在交互信息增長(zhǎng)了一倍多的條件下，NEOComplex算法的召回率已經(jīng)近乎于0，不再是表1中顯示的0.47。同樣，這時(shí)NEOComplex算法的精確率也會(huì)下降到近乎為0。因此，隨著蛋白質(zhì)間交互信息的不斷增多，NEOComplex算法已經(jīng)失去效應(yīng)。

原因2：TSSComplex算法能夠有效地控制復(fù)合物。

NEOComplex算法之所以會(huì)失效，就是因?yàn)樗鼪](méi)有一個(gè)有效的手段來(lái)控制預(yù)測(cè)復(fù)合物的大小，而TSSComplex算法還可以繼續(xù)使用，得益于它們所采用的布谷鳥搜索算法可以控制預(yù)測(cè)復(fù)合物的規(guī)模。布谷鳥搜索在獲取聚類中心后，只有與中心點(diǎn)相連的節(jié)點(diǎn)，才有可能通過(guò)相似度的篩選，進(jìn)入初始簇，因此這些點(diǎn)與中心點(diǎn)之間的最短路徑長(zhǎng)度均為1。而在第二步初始簇的擴(kuò)充中，若一個(gè)點(diǎn)與初始簇內(nèi)任何點(diǎn)均不相連，該點(diǎn)是不會(huì)被擴(kuò)充進(jìn)初始簇的。而一個(gè)點(diǎn)如果可能被擴(kuò)充進(jìn)初始簇，那么它必然至少與初始簇中的一個(gè)點(diǎn)相連，這時(shí)它與簇中心之間的最短路徑長(zhǎng)度的集合中最大值只能是2，而簇中最遠(yuǎn)的兩個(gè)點(diǎn)之間最短路徑長(zhǎng)度的集合中最大值也僅可能為4，正是因?yàn)槿绱?，布谷鳥搜索能夠控制簇的規(guī)模。而NEOComplex算法，只要邊密度不小于0.009，就一直可以有節(jié)點(diǎn)加入，加入的節(jié)點(diǎn)和初始種子節(jié)點(diǎn)之間的距離可以非常遠(yuǎn)，從而無(wú)法控制簇的規(guī)模。

原因3：TSSComplex算法可以有效縮小蛋白質(zhì)復(fù)合物搜索的范圍。

這里，我們?yōu)镃ORUM中的已知蛋白質(zhì)復(fù)合物定義了最優(yōu)重合率。一個(gè)復(fù)合物c∈RC，它的最優(yōu)重合率(Optimal overlapping score，OOS)為

(18)

這個(gè)最優(yōu)重合率反映了該已知復(fù)合物中有多少蛋白質(zhì)可以同時(shí)出現(xiàn)在某個(gè)預(yù)測(cè)復(fù)合物中。OOS越大，說(shuō)明一個(gè)已知復(fù)合物越能完整的包含在一個(gè)預(yù)測(cè)復(fù)合物中。

表2 參考復(fù)合物集合關(guān)于OSS的分段統(tǒng)計(jì)Table 2 A piecewise statistic for reference complexes with OSS

①Number; ②Proportion; ③Matching number； ④Matching ratio； ⑤Total.

對(duì)CORUM中的已知復(fù)合物進(jìn)行分段統(tǒng)計(jì)，表2報(bào)告了分段統(tǒng)計(jì)的結(jié)果。觀察表2中的數(shù)據(jù)可以發(fā)現(xiàn)，有55.42%的復(fù)合物，其所包含的蛋白質(zhì)可以完全在某個(gè)預(yù)測(cè)的復(fù)合物中找到。有94.78%的復(fù)合物，其所包含的蛋白質(zhì)有一半可以在某個(gè)預(yù)測(cè)的復(fù)合物中找到。這一結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于召回率18.62%。這種現(xiàn)象在越小的復(fù)合物中越明顯。之所以會(huì)出現(xiàn)這一情況，是由于隨著蛋白質(zhì)交互信息的增多，PPI網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的度也在不斷上升，蛋白質(zhì)與蛋白質(zhì)之間的聯(lián)系更緊密，使得預(yù)測(cè)到的復(fù)合物規(guī)模偏大(從表2中可以看出，包含蛋白質(zhì)個(gè)數(shù)超過(guò)5的預(yù)測(cè)復(fù)合物的比率要遠(yuǎn)高于已知復(fù)合物中該類的比率)，使得小型復(fù)合物很容易隱藏在一些大型簇中，從而無(wú)法被準(zhǔn)確地找到。從另一個(gè)角度來(lái)說(shuō)，召回率低意味著直接匹配到已知復(fù)合物的成功率低；但高最優(yōu)重合率則意味著已知復(fù)合物基本是預(yù)測(cè)到的復(fù)合物的一部分，因此可以有效地為尋找已知復(fù)合物縮小范圍，而且范圍縮小的效率要比NEOComplex算法好。這樣可以嘗試通過(guò)一些方法，在這個(gè)縮小的范圍內(nèi)尋找更精確的蛋白質(zhì)復(fù)合物。

另一方面，TSSComplex算法所獲得的預(yù)測(cè)復(fù)合物的個(gè)數(shù)與CORUM中所包含的已知復(fù)合物的個(gè)數(shù)比較接近，這使得可供進(jìn)一步搜尋的復(fù)合物個(gè)數(shù)也比較少，而不是像CMC算法那樣，即便具有很高的召回率，但在新數(shù)據(jù)集(即本文所使用的數(shù)據(jù)集)上卻能獲得近40萬(wàn)個(gè)預(yù)測(cè)復(fù)合物，這么龐大的潛在復(fù)合物數(shù)量，即使想做進(jìn)一步篩選，其難度也非常大。

綜上三個(gè)原因，雖然TSSComplex算法在性能指標(biāo)上可能并不太理想，但其依然具有研究的價(jià)值。

3 結(jié)語(yǔ)

本文提出了一種基于圖嵌入技術(shù)和布谷鳥搜索的二步蛋白質(zhì)復(fù)合物預(yù)測(cè)方法。傳統(tǒng)搜索算法在蛋白質(zhì)交互信息越來(lái)越多的情況下會(huì)逐漸失效，不同于傳統(tǒng)算法，本算法在蛋白質(zhì)交互信息增多的情況下，依然有一定的準(zhǔn)確性。但同時(shí)也反映出，蛋白質(zhì)復(fù)合物的探測(cè)技術(shù)未來(lái)不能僅依靠PPI網(wǎng)絡(luò)，還要參考其他信息，例如蛋白質(zhì)的生化性質(zhì)信息。

本算法可為進(jìn)一步精確探測(cè)復(fù)合物縮小搜索范圍。這為蛋白質(zhì)復(fù)合物搜索方法提供了一個(gè)新思路：先用搜索算法縮小復(fù)合物包含的蛋白質(zhì)范圍，再通過(guò)其他數(shù)據(jù)挖掘技術(shù)或?qū)嶒?yàn)技術(shù)，進(jìn)一步精確探測(cè)復(fù)合物。我們現(xiàn)在正在試圖構(gòu)建一些算法，以實(shí)現(xiàn)在縮小了范圍的蛋白質(zhì)簇中能更精確地探測(cè)蛋白質(zhì)復(fù)合物的目的。