基于圖嵌入和布谷鳥搜索的二步蛋白質(zhì)復(fù)合物預(yù)測方法?

葛永錱， 趙熙強

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

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

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

PPI網(wǎng)絡(luò)可以通過無向圖來進行建模表示。在過去的十幾年中，人們通過對圖論、計算數(shù)學(xué)、統(tǒng)計學(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]。這些方法的主要策略是從單個蛋白質(zhì)出發(fā)，從PPI網(wǎng)絡(luò)中提取高度鏈接的節(jié)點以形成簇，這些簇有可能成為蛋白質(zhì)復(fù)合物的候選者。

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

本文提出了一種基于圖嵌入和布谷鳥搜索的二步蛋白質(zhì)復(fù)合物預(yù)測方法(TSSComplex)。該方法將最優(yōu)化問題中布谷鳥搜索方法的思想引入蛋白質(zhì)復(fù)合物的搜尋中，代替?zhèn)鹘y(tǒng)的從單個蛋白質(zhì)出發(fā)的搜索方法。利用相似度和親和度來聚類蛋白質(zhì)，從而獲得候選簇。這樣可以有效控制簇的規(guī)模，從而提高匹配率。另一方面，引入圖嵌入技術(shù)，來獲得PPI網(wǎng)絡(luò)中節(jié)點的低維表示，并將兩個節(jié)點表示向量之間的距離和傳統(tǒng)的邊權(quán)結(jié)合起來，形成了新的邊權(quán)算法。之所以引入圖嵌入方法，是因為它將每個節(jié)點的拓撲結(jié)構(gòu)映射到低維向量表示中，可以很好地保留原始網(wǎng)絡(luò)的鄰近性[13-15]。圖嵌入方法可以從原始網(wǎng)絡(luò)中自動發(fā)現(xiàn)有用和潛在的特征，而非人工制作的網(wǎng)絡(luò)特征。同時有研究表明，在節(jié)點分類[16]、鏈路預(yù)測[17]、節(jié)點聚類[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ù)測方法主要分為三個步驟。第一步是利用圖嵌入技術(shù)，用低維向量表示PPI網(wǎng)絡(luò)中的蛋白質(zhì)節(jié)點。然后，通過節(jié)點的低維向量表示和節(jié)點本身的網(wǎng)絡(luò)結(jié)構(gòu)給PPI網(wǎng)絡(luò)中的邊賦權(quán)。第二步是通過布谷鳥搜索，獲取潛在的蛋白質(zhì)復(fù)合物。第三步是針對布谷鳥搜索之后的剩余蛋白質(zhì)節(jié)點，利用傳統(tǒng)搜索方法，進行二次搜索。

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

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

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

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

(1)

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

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

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

(2)

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

(3)

則公式(1)可改寫為

(4)

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

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

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

(5)

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

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

(6)

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

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

1.2 布谷鳥搜索

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

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

(7)

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

(8)

其中

(9)

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

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

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

(10)

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

之后可以開始正式進行布谷鳥搜索。布谷鳥搜索算法主要分為四步。

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

(11)

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

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

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

(12)

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

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

(13)

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

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

(14)

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

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

1.3 二次搜索

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

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

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

1.4 主要算法

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

TSSComplex算法

步驟1. 準備工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟3.2 對G1中的每一個節(jié)點重復(fù)進行步驟3.1，共獲得|V1|個簇。

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

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

算法的簡易流程見圖1。

2 實驗與分析

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

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

人類PPI網(wǎng)絡(luò)通過聯(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個蛋白質(zhì)節(jié)點和339 054條交互(邊)。

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

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

2.2 性能標準

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

(15)

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

(16)

F-measure是精確度和召回率的調(diào)和平均值，表示預(yù)測結(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])做了比較(見表1)。

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

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

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

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

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

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

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

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

(18)

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

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

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

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

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

綜上三個原因，雖然TSSComplex算法在性能指標上可能并不太理想，但其依然具有研究的價值。

3 結(jié)語

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

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