丁玉連，雷秀娟，代 才

陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710062

模擬鴿子優(yōu)化過(guò)程的蛋白質(zhì)復(fù)合物識(shí)別算法*

丁玉連，雷秀娟+，代 才

陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710062

蛋白質(zhì)復(fù)合物的檢測(cè)對(duì)人類了解細(xì)胞組織和疾病預(yù)測(cè)起著至關(guān)重要的作用。然而，當(dāng)前的蛋白質(zhì)復(fù)合物識(shí)別方法的準(zhǔn)確率低，對(duì)噪音敏感等缺點(diǎn)導(dǎo)致其識(shí)別效果并不理想。提出了一種新的蛋白質(zhì)復(fù)合物識(shí)別方法PIOC（pigeon-inspired optimization clustering）。該方法根據(jù)蛋白質(zhì)復(fù)合物的特性提出了簇的緊密鄰接點(diǎn)概念和附件對(duì)核心的附著度概念，基于這兩個(gè)概念，PIOC通過(guò)模擬鴿子優(yōu)化算法中鴿子尋找目的地的過(guò)程來(lái)識(shí)別蛋白質(zhì)復(fù)合物；結(jié)合鴿子算法中先全局搜索再局部搜索的特性和蛋白質(zhì)復(fù)合物的核心附件結(jié)構(gòu)，先通過(guò)鴿子算法中地圖羅盤(pán)操作的全局搜索形成蛋白質(zhì)復(fù)合物的核心，再通過(guò)鴿子算法地標(biāo)操作的局部搜索將附件蛋白質(zhì)聚集到核心簇中形成蛋白質(zhì)復(fù)合物?；诮湍傅鞍踪|(zhì)相互作用網(wǎng)絡(luò)DIP上的實(shí)驗(yàn)表明，PIOC比當(dāng)前其他的蛋白質(zhì)復(fù)合物識(shí)別算法能更有效地識(shí)別蛋白質(zhì)復(fù)合物。

蛋白質(zhì)相互作用（PPI）；鴿子優(yōu)化算法；蛋白質(zhì)復(fù)合物；聚類

1 引言

在生物體中，蛋白質(zhì)不是獨(dú)立存在的，而是相互聯(lián)系在一起形成蛋白質(zhì)復(fù)合物，從而實(shí)現(xiàn)它們的生物功能[1]。因此，正確識(shí)別蛋白質(zhì)復(fù)合物在了解細(xì)胞功能機(jī)制和預(yù)測(cè)未知蛋白質(zhì)的功能中起著重要的作用[2]。生物實(shí)驗(yàn)的方法識(shí)別蛋白質(zhì)復(fù)合物昂貴且耗時(shí)，因此通過(guò)計(jì)算的方式識(shí)別蛋白質(zhì)相互作用（protein-protein interaction，PPI）網(wǎng)絡(luò)的蛋白質(zhì)復(fù)合物成為人們研究的熱點(diǎn)[3-5]。

目前，計(jì)算方式識(shí)別蛋白質(zhì)復(fù)合物的普遍做法是將蛋白質(zhì)相互作用信息表示成一個(gè)無(wú)向圖，將蛋白質(zhì)復(fù)合物對(duì)應(yīng)圖中的稠密子圖，利用各種圖聚類分析方法來(lái)識(shí)別蛋白質(zhì)復(fù)合物。一般通過(guò)聚類方法是否考慮到網(wǎng)絡(luò)的全局特性，蛋白質(zhì)復(fù)合物識(shí)別方法可以分為兩大類：一類是全局聚類方法；一類是局部聚類方法。

全局聚類方法主要是通過(guò)劃分整個(gè)PPI網(wǎng)絡(luò)為獨(dú)立的子網(wǎng)來(lái)挖掘蛋白質(zhì)復(fù)合物。例如，G-N（Girvan-Newman）[6]算法主要是通過(guò)不斷移除具有最高的介數(shù)中心性的邊來(lái)劃分網(wǎng)絡(luò)。馬爾科夫聚類（Markov clustering，MCL）[7]算法主要是通過(guò)在PPI網(wǎng)絡(luò)中模仿隨機(jī)步來(lái)檢測(cè)蛋白質(zhì)復(fù)合物。雖然這些聚類方法考慮到了PPI網(wǎng)絡(luò)的全局性，但不能識(shí)別重疊的蛋白質(zhì)復(fù)合物，而蛋白質(zhì)復(fù)合物之間是高度重疊的[8]。

局部聚類方法主要考慮局部的鄰居結(jié)點(diǎn)來(lái)識(shí)別蛋白質(zhì)復(fù)合物。例如，基于最大簇聚類（clusteringbased on maximal cliques，CMC）[9]算法主要是通過(guò)找最大簇來(lái)識(shí)別蛋白質(zhì)復(fù)合物。MCODE（molecular complex detection）[10]算法主要是先給結(jié)點(diǎn)加權(quán)，然后選擇權(quán)重高的結(jié)點(diǎn)作為種子，擴(kuò)充種子形成蛋白質(zhì)復(fù)合物。還有一些其他聚類算法如，DPClus（development clustering）[11]、HC-PIN（hierarchical clusteringprotein interaction network）[12]和ClusterONE（clustering with overlapping neighborhood expansion）[13]等，這些方法都忽視了蛋白質(zhì)復(fù)合物的內(nèi)部核心附件結(jié)構(gòu)。COACH（core-attachment）[14]算法基于蛋白質(zhì)復(fù)合物的核心附件結(jié)構(gòu)先形成稠密子圖作為核心，然后將附件蛋白質(zhì)聚到相應(yīng)的核心中形成復(fù)合物。局部聚類算法雖然能識(shí)別重疊蛋白質(zhì)復(fù)合物，但忽視了PPI網(wǎng)絡(luò)的全局性。

傳統(tǒng)的聚類方法識(shí)別蛋白質(zhì)復(fù)合物都存在一定的局限性，性能并不是很好。生物仿生算法為復(fù)合物識(shí)別提供了一個(gè)新視角。例如，PMABC-ACE（propagating mechanism of artificial bee colony cluster module based on aggregation coefficient of edge）[15]通過(guò)模仿人工蜂群繁殖進(jìn)行蛋白質(zhì)復(fù)合物識(shí)別。基于螢火蟲(chóng)的馬爾科夫聚類（fire fly-Markov clustering，F(xiàn)MCL）[16]通過(guò)結(jié)合MCL算法和螢火蟲(chóng)優(yōu)化算法來(lái)識(shí)別蛋白質(zhì)復(fù)合物。這些算法比傳統(tǒng)聚類算法表現(xiàn)出了更好的性能。鴿子優(yōu)化算法[17]作為一種新穎的群智能優(yōu)化算法，通過(guò)地圖指南針?biāo)阕雍偷貥?biāo)算子模擬鴿子找家的過(guò)程。它被證明比其他群智能算法的優(yōu)化特性更強(qiáng)[18]，并被廣泛應(yīng)用，例如無(wú)人機(jī)目標(biāo)探測(cè)[19]、PID控制器設(shè)計(jì)[20]等。

本文結(jié)合鴿子算法的優(yōu)化特性和蛋白質(zhì)復(fù)合物的特征提出了一種新的蛋白質(zhì)復(fù)合物識(shí)別方法PIOC（pigeon-inspired optimization clustering）。其中蛋白質(zhì)復(fù)合物的特征包括：復(fù)合物是由核心和附件構(gòu)成，復(fù)合物內(nèi)蛋白質(zhì)之間的最短距離一般不超過(guò)2，復(fù)合物是個(gè)高密度的簇等。PIOC方法先通過(guò)鴿子算法中地圖羅盤(pán)操作的全局搜索形成蛋白質(zhì)復(fù)合物的核心，再通過(guò)鴿子算法地標(biāo)操作的局部搜索將附件蛋白質(zhì)聚集到核心簇中形成蛋白質(zhì)復(fù)合物。

本文組織結(jié)構(gòu)如下：第2章主要介紹基本鴿子算法和PPI網(wǎng)絡(luò)的相關(guān)基礎(chǔ)知識(shí)；第3章描述基于鴿子優(yōu)化算法的聚類算法；第4章展示實(shí)驗(yàn)結(jié)果，并對(duì)結(jié)果加以分析；最后對(duì)本文進(jìn)行總結(jié)，并指出進(jìn)一步的研究方向。

2 鴿子算法與PPI網(wǎng)絡(luò)基礎(chǔ)知識(shí)

2.1 鴿子算法

信鴿有著天生的歸巢能力，它們通過(guò)使用磁場(chǎng)、太陽(yáng)和地標(biāo)3個(gè)導(dǎo)航工具，準(zhǔn)確找到遠(yuǎn)方的家。基于鴿子的導(dǎo)航行為，一種新穎的群智能仿生算法鴿子優(yōu)化（pigeon-inspired optimization，PIO）算法[17]在2014年被提出。PIO算法主要通過(guò)兩個(gè)操作來(lái)模擬鴿子的導(dǎo)航行為，即地圖羅盤(pán)算子和地標(biāo)算子。地圖羅盤(pán)算子的提出主要是基于太陽(yáng)和磁場(chǎng)，而地標(biāo)算子的提出主要基于地標(biāo)。

（1）地圖羅盤(pán)算子

在地圖羅盤(pán)算子中，通過(guò)計(jì)算機(jī)隨機(jī)產(chǎn)生鴿子。用Xi、Vi分別表示鴿子i的位置和速度，并且在一個(gè)d維的搜索空間里，每只鴿子的位置和速度在每次迭代中不斷更新。第i只鴿子在第t次迭代中新的位置和速度通過(guò)以下公式獲得：

其中，R是地圖羅盤(pán)算子；rand是一個(gè)隨機(jī)數(shù)（一般取0～1之間的數(shù)）；Xg是全局最優(yōu)位置。

（2）地標(biāo)算子

在地標(biāo)算子中，假設(shè)鴿子都還沒(méi)有到達(dá)目的地，并且它們對(duì)地標(biāo)都不熟。所有的鴿子都根據(jù)它們的適應(yīng)度值排序，再通過(guò)式（3）減少一半鴿子(Np/2)：

然后在第t次迭代時(shí)剩下的鴿子里找到中心鴿子的位置(Xc)，Xc被認(rèn)為是最理想的位置，通過(guò)式（4）更新，其他鴿子的位置通過(guò)式（5）更新：

其中，fitness(Xi(t))是種群里每只鴿子的適應(yīng)度。

2.2 PPI網(wǎng)絡(luò)基本特征度量

蛋白質(zhì)相互作用完成了特定的分子功能或者進(jìn)程。PPI網(wǎng)絡(luò)可以用圖G(V,E)表示，其中V是頂點(diǎn)集，代表所有蛋白質(zhì)結(jié)點(diǎn)的集合，E為邊集，表示任意兩蛋白質(zhì)之間的相互作用集合。

結(jié)點(diǎn)的度degree表示在PPI網(wǎng)絡(luò)中直接與此結(jié)點(diǎn)相連的邊的條數(shù)，反映了當(dāng)前結(jié)點(diǎn)與其周邊結(jié)點(diǎn)的連接程度。

結(jié)點(diǎn)的聚集系數(shù)[21]（node clustering coefficient，NCC）是指與該結(jié)點(diǎn)相鄰的鄰接結(jié)點(diǎn)之間實(shí)際存在的邊的數(shù)目與可能存在的邊的數(shù)目的比例，反映了網(wǎng)絡(luò)中結(jié)點(diǎn)的聚集程度，結(jié)點(diǎn)v的聚集系數(shù)NCC(v)的計(jì)算公式為：

其中，kv表示結(jié)點(diǎn)v的度；nv表示v的kv個(gè)鄰居結(jié)點(diǎn)之間存在的邊數(shù)。

邊的聚集系數(shù)[22]（edge clustering coefficient，ECC）是指與該邊構(gòu)成的三角形個(gè)數(shù)和所有可能包括該邊的三角形個(gè)數(shù)比例，計(jì)算過(guò)程如下：

其中，Z(vi,vj)表示包含邊(vi,vj)的三角形個(gè)數(shù)；min{di-1,dj-1}表示包含邊(vi,vj)的可能存在的三角形的最大個(gè)數(shù)。

PPI網(wǎng)絡(luò)子圖G密度dens[21]的計(jì)算是用子圖中存在的邊數(shù)比上當(dāng)子圖為一個(gè)完全圖時(shí)應(yīng)該有的邊數(shù)，其計(jì)算公式如下：

其中，m表示子圖中存在的邊的條數(shù)；n表示子圖中的結(jié)點(diǎn)數(shù)。

2.3 蛋白質(zhì)復(fù)合物的基本特征

對(duì)已有的酵母蛋白質(zhì)復(fù)合物標(biāo)準(zhǔn)庫(kù)中的蛋白質(zhì)復(fù)合物的研究表明，蛋白質(zhì)復(fù)合物存在以下3個(gè)特征：

（1）蛋白質(zhì)復(fù)合物中的蛋白質(zhì)之間的平均最短路徑長(zhǎng)度小于等于2的占90％以上[23]。

（2）大部分蛋白質(zhì)復(fù)合物的密度在0.5以上[23]。

（3）蛋白質(zhì)復(fù)合物都是以一個(gè)核心多個(gè)附件構(gòu)成的[14]。

根據(jù)以上3個(gè)特征本文提出了簇的緊密鄰接點(diǎn)的定義和附件與核心簇之間附著度的定義。

定義1一個(gè)簇C的緊密鄰接點(diǎn)v為滿足SP(u,v)≤2,u∈Vc的結(jié)點(diǎn)。其中Vc為簇C內(nèi)包含的結(jié)點(diǎn)集合，SP(u,v)表示簇C的鄰接點(diǎn)v到簇C內(nèi)的任一結(jié)點(diǎn)u的最短路徑。

定義2一個(gè)附件蛋白質(zhì)結(jié)點(diǎn)v到一個(gè)核心簇C的附著度為DS(v,C)，其計(jì)算公式如下：

其中，vin表示核心簇中與v相連的結(jié)點(diǎn)集合；vout表示核心簇外與v相連的結(jié)點(diǎn)。DS(v,C)用來(lái)衡量一個(gè)結(jié)點(diǎn)v是核心C的附件的可能性，其值越大表示結(jié)點(diǎn)v屬于核心C的附件的可能性越大。

3 基于鴿子優(yōu)化算法的聚類算法PIOC

3.1 基于鴿子優(yōu)化算法的聚類模型

PIOC算法主要分為兩個(gè)階段：地圖羅盤(pán)操作階段和地標(biāo)操作階段。第一階段，先通過(guò)全局探索找到核心簇的種子結(jié)點(diǎn)，再通過(guò)地圖羅盤(pán)操作中鴿子位置的更新形成核心簇。第二階段，在地標(biāo)算子的迭代過(guò)程中將附件蛋白質(zhì)不斷聚到核心簇中最終形成蛋白質(zhì)復(fù)合物。該模型的設(shè)計(jì)中考慮的蛋白質(zhì)復(fù)合特征有3個(gè)：核心附件結(jié)構(gòu)，復(fù)合物內(nèi)部蛋白質(zhì)間最短距離不超過(guò)2，蛋白質(zhì)復(fù)合物是個(gè)高密度的簇。

（1）地圖羅盤(pán)操作

鴿子位置初始化：對(duì)整個(gè)PPI網(wǎng)絡(luò)中的結(jié)點(diǎn)按照其NCC值降序排序，取前cn個(gè)結(jié)點(diǎn)作為核心簇的種子結(jié)點(diǎn)，每個(gè)種子結(jié)點(diǎn)看成一只鴿子。確定其下一步要飛向的候選位置：對(duì)于每一只鴿子，將其對(duì)應(yīng)的核心簇的緊密鄰接點(diǎn)（即到核心簇中每個(gè)結(jié)點(diǎn)的最短距離都不超過(guò)2的鄰居結(jié)點(diǎn)）看作鴿子的候選位置。選最優(yōu)位置：選出候選位置中優(yōu)先權(quán)最高的位置作為最優(yōu)位置，優(yōu)先權(quán)是指該結(jié)點(diǎn)與簇內(nèi)結(jié)點(diǎn)形成的邊的聚集系數(shù)之和。位置更新：若最優(yōu)位置優(yōu)先權(quán)值大于0，則鴿子飛向最優(yōu)位置，將優(yōu)先權(quán)最高的緊密鄰接點(diǎn)聚到鴿子所代表的核心簇中，否則，此鴿子的迭代結(jié)束。重復(fù)迭代上述過(guò)程，更新鴿子的位置，更新鴿子候選位置，更新最優(yōu)位置，每更新一次位置就有一個(gè)最優(yōu)鄰接點(diǎn)聚到鴿子所代表的核心簇中，直到該核心簇的密度小于閾值dens_th時(shí)，結(jié)束第一階段的更新。當(dāng)每只鴿子完成地標(biāo)羅盤(pán)操作里的迭代時(shí)就形成了一個(gè)核心簇。

（2）地標(biāo)操作

對(duì)每只鴿子所代表的核心簇的緊密鄰接點(diǎn)按附著度值DS進(jìn)行排序。更新中心鴿子位置：將緊密鄰接點(diǎn)中到核心簇的附著度最大的鄰接點(diǎn)作為中心鴿子的位置。更新鴿子位置：若中心鴿子的位置處附著度DS值大于1，則更新鴿子位置，即將此緊密鄰接點(diǎn)作為該鴿子的附件蛋白質(zhì)聚到鴿子所代表的核心簇中，迭代更新中心鴿子位置和其他鴿子位置；若中心鴿子位置處的DS值小于1，則此只鴿子的地標(biāo)操作結(jié)束，此鴿子對(duì)應(yīng)的簇就是一個(gè)蛋白質(zhì)復(fù)合物。

基于鴿子優(yōu)化算法的聚類模型解決了當(dāng)前大多數(shù)蛋白質(zhì)復(fù)合物識(shí)別方法不能同時(shí)考慮網(wǎng)絡(luò)的全局性和局部性的缺點(diǎn)，并考慮到了蛋白質(zhì)復(fù)合物的內(nèi)部核心附件結(jié)構(gòu)。

鴿子算法聚類模型如圖1所示。

3.2 PIOC算法描述

PIOC算法的輸入是一個(gè)由蛋白質(zhì)頂點(diǎn)和蛋白質(zhì)相互作用邊組成的網(wǎng)絡(luò)圖G=(V,E)。該算法由三部分組成：鴿子的初始化，地圖羅盤(pán)算子和地標(biāo)算子。整個(gè)算法的描述如下。

Fig.1 Clustering model of PIOC圖1 PIOC聚類模型

算法PIOC聚類

輸入：PPI網(wǎng)絡(luò)對(duì)應(yīng)的圖G=(V,E)

輸出：預(yù)測(cè)出來(lái)的蛋白質(zhì)復(fù)合物C

初始化：計(jì)算出G圖中每個(gè)頂點(diǎn)的聚集系數(shù)NCC，計(jì)算出圖中每條邊的聚集系數(shù)ECC，Xbest表示最優(yōu)鴿子位置，Xc表示中心鴿子位置，cn表示鴿子的數(shù)量，dens_th表示密度閾值，C表示鴿子群，c表示每一只鴿子，標(biāo)記 flag初始化為0。

（1）初始化鴿子

Sq←all nodes sorted in non-increasing order based on NCCvalue

C←the firstcnnode inSq（2）地圖羅盤(pán)算子

output C;//輸出整個(gè)鴿子群，此時(shí)每只鴿子代表一個(gè)蛋白質(zhì)復(fù)合物

鴿子優(yōu)化算法PIO與聚類算法的對(duì)應(yīng)關(guān)系如表1所示。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)和評(píng)價(jià)標(biāo)準(zhǔn)

本文采用DIP數(shù)據(jù)庫(kù)中20140427的酵母菌S.cerevisiae數(shù)據(jù)集測(cè)試PIOC算法的性能。靜態(tài)的DIP蛋白質(zhì)相互作用網(wǎng)絡(luò)包含4 997個(gè)蛋白質(zhì)結(jié)點(diǎn)和21 554對(duì)相互作用，網(wǎng)絡(luò)的平均度是8.626 8。采用的標(biāo)準(zhǔn)數(shù)據(jù)集是CYC2008標(biāo)準(zhǔn)數(shù)據(jù)集，其中包含408個(gè)蛋白質(zhì)復(fù)合物，1 628個(gè)蛋白質(zhì)結(jié)點(diǎn)。

Table1 Corresponding relationships between PIO algorithm and clustering procedure of PPI network表1 PIO算法與PPI網(wǎng)絡(luò)中聚類過(guò)程的對(duì)應(yīng)關(guān)系

為了評(píng)估檢測(cè)出的蛋白質(zhì)復(fù)合物的性能，本文使用常見(jiàn)的3種統(tǒng)計(jì)評(píng)估方法：準(zhǔn)確率Precision、查全率Recall和調(diào)和平均值F-measure[21]。Precision評(píng)估了預(yù)測(cè)的蛋白質(zhì)復(fù)合物與標(biāo)準(zhǔn)庫(kù)中已知蛋白質(zhì)復(fù)合物相比的準(zhǔn)確率；Recall評(píng)估了標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中蛋白質(zhì)復(fù)合物被識(shí)別出來(lái)的準(zhǔn)確率；F-measure顯示了準(zhǔn)確率和查全率兩者的調(diào)和平均值。這3個(gè)評(píng)價(jià)方法的計(jì)算公式如下所示：

其中，C表示預(yù)測(cè)的蛋白質(zhì)復(fù)合物；S表示標(biāo)準(zhǔn)庫(kù)中的蛋白質(zhì)復(fù)合物。

識(shí)別出來(lái)的復(fù)合物A與已知復(fù)合物B的匹配程度OS(A,B)[24]的計(jì)算公式如下：

其中，VA和VB分別表示蛋白質(zhì)復(fù)合物A和蛋白質(zhì)復(fù)合物B中的頂點(diǎn)集合。若兩個(gè)復(fù)合物的匹配程度OS(A,B)超過(guò)給定的閾值，則稱這兩個(gè)復(fù)合物匹配。一般對(duì)于酵母蛋白質(zhì)的數(shù)據(jù)集，取這個(gè)閾值為0.2[24]，即被檢測(cè)出來(lái)的蛋白質(zhì)復(fù)合物與標(biāo)準(zhǔn)庫(kù)中復(fù)合物的匹配程度值大于0.2時(shí)，這兩個(gè)復(fù)合物被認(rèn)為是相互匹配的。當(dāng)OS的值為1時(shí)被認(rèn)為是完美匹配。

4.2 參數(shù)分析

PIOC聚類算法中涉及兩個(gè)參數(shù)：第一個(gè)是初始化鴿子時(shí)選取前cn個(gè)結(jié)點(diǎn)作為鴿子群體，則鴿子的群體數(shù)量cn是個(gè)針對(duì)不同PPI網(wǎng)絡(luò)設(shè)置不同值的參數(shù)；第二個(gè)是核心簇的密度閾值dens_th，其在地圖羅盤(pán)算子里控制迭代次數(shù)也控制著核心簇的大小。根據(jù)以前的研究工作，參數(shù)dens_th一般設(shè)為0.7[11]。當(dāng)cn取由100到800的不同值時(shí)得到不同的聚類結(jié)果。圖2顯示了cn的取值與聚類結(jié)果性能之間的變化關(guān)系。

Fig.2 Influence of parametercnon clustering evaluation圖2 參數(shù)cn對(duì)聚類結(jié)果的影響

由圖2可以看出，隨著參數(shù)cn的增大，準(zhǔn)確度Precision呈現(xiàn)遞減的趨勢(shì)，而查全率Recall卻呈現(xiàn)先增加再減小的趨勢(shì)。因?yàn)楫?dāng)cn很小時(shí)，簇所取的核心種子結(jié)點(diǎn)都具有很高的點(diǎn)聚集系數(shù)，所以產(chǎn)生的蛋白質(zhì)復(fù)合物都是很緊密的簇，具有很高的準(zhǔn)確率。但與此同時(shí)，識(shí)別出來(lái)的蛋白質(zhì)復(fù)合物對(duì)蛋白質(zhì)的覆蓋量少，因此查全率比較小。當(dāng)cn越大，后面種子結(jié)點(diǎn)的聚集系數(shù)越小，故準(zhǔn)確率下降。但隨著蛋白質(zhì)復(fù)合物數(shù)量的增加，其查全率也增加，當(dāng)增加到一定值時(shí)，由于后面很多性能不好的種子結(jié)點(diǎn)的加入，產(chǎn)生很多錯(cuò)誤蛋白質(zhì)復(fù)合物，降低了查全率。由調(diào)和平均值F-measure可以看出，當(dāng)cn取450左右時(shí)其總體性能最好。

4.3 與已知蛋白質(zhì)復(fù)合物比較

將由PIOC得到的聚類結(jié)果與標(biāo)準(zhǔn)庫(kù)中的蛋白質(zhì)復(fù)合物進(jìn)行比較，分析本文預(yù)測(cè)的蛋白質(zhì)復(fù)合物中正確和錯(cuò)誤的蛋白質(zhì)。表2中隨機(jī)選擇PIOC識(shí)別的蛋白質(zhì)復(fù)合物中的7個(gè)復(fù)合物進(jìn)行分析。從表2中可以看出，PIOC聚類方法能正確識(shí)別蛋白質(zhì)復(fù)合物中的絕大多數(shù)蛋白質(zhì)，其中個(gè)別復(fù)合物會(huì)包含錯(cuò)誤蛋白質(zhì)或者漏掉個(gè)別蛋白質(zhì)，但標(biāo)準(zhǔn)蛋白質(zhì)復(fù)合物中的蛋白質(zhì)基本上都能被識(shí)別出來(lái)。

圖3可視化了表2中7號(hào)蛋白質(zhì)復(fù)合物。圖（a）表示標(biāo)準(zhǔn)庫(kù)中的蛋白質(zhì)復(fù)合物，不帶背景顏色的結(jié)點(diǎn)為PIOC未識(shí)別出來(lái)的蛋白質(zhì)。圖（b）表示PIOC檢測(cè)出來(lái)的蛋白質(zhì)復(fù)合物，其中不帶背景顏色的蛋白質(zhì)為被錯(cuò)誤識(shí)別的蛋白質(zhì)。YIR025W和YGR-260C未被識(shí)別出來(lái)，是因?yàn)槠渑c簇外的鄰接點(diǎn)鏈接更緊密。YGR225W被錯(cuò)誤識(shí)別出來(lái)，是因?yàn)槠渲慌c核心簇中蛋白質(zhì)YKL022C相連。YLR451W被錯(cuò)誤識(shí)別出來(lái)是因?yàn)槠涠葹?，簇內(nèi)的鄰接點(diǎn)度值大于簇外的度值。

Table2 Analysis of 7 protein complexes in results表2 結(jié)果中7個(gè)蛋白質(zhì)復(fù)合物的分析

4.4 性能比較

為了測(cè)試PIOC的性能，將PIOC的聚類結(jié)果與MCL[7]、CMC、MCODE、DPClus、HC-PIN、Clsuter-ONE、COACH[9-14]、F-MCL[16]這些典型算法的聚類結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果的獲得都是基于DIP靜態(tài)PPI網(wǎng)絡(luò)和MIPS網(wǎng)絡(luò)，并且被比較的算法都取各自的最優(yōu)參數(shù)。PIOC的參數(shù)cn取450，核心密度dens_th取0.7。

表3展示了上面幾種聚類算法得到的結(jié)果詳情，表4對(duì)比了幾種算法結(jié)果性能。

由表3可以看出，PIOC識(shí)別出來(lái)的蛋白質(zhì)復(fù)合物數(shù)量和覆蓋的蛋白質(zhì)數(shù)量接近標(biāo)準(zhǔn)庫(kù)中復(fù)合物的標(biāo)準(zhǔn)，但蛋白質(zhì)復(fù)合物的平均大小偏大，這也說(shuō)明PIOC識(shí)別出來(lái)的蛋白質(zhì)復(fù)合物之間有很多重疊。與之對(duì)應(yīng)，F(xiàn)-MCL和DPClus等方法識(shí)別出來(lái)的蛋白質(zhì)復(fù)合物很多，覆蓋的蛋白質(zhì)數(shù)量也很大，但大多數(shù)蛋白質(zhì)是錯(cuò)誤的，導(dǎo)致性能低。

Fig.3 Visualization of comparison圖3 可視化對(duì)比

表4顯示了蛋白質(zhì)復(fù)合物性能比較?？梢钥闯鯬IOC在Precision、Recall和F-measure評(píng)價(jià)標(biāo)準(zhǔn)上都優(yōu)于其他蛋白質(zhì)復(fù)合物識(shí)別方法，也就是說(shuō)PIOC比其他蛋白質(zhì)復(fù)合物識(shí)別方法更能有效地識(shí)別蛋白質(zhì)復(fù)合物。

Table3 Clusters description of several clustering algorithms表3 幾種聚類算法的聚類結(jié)果展示

Table4 Performance comparison of different clustering algorithms with PIOC表4 幾種聚類算法與PIOC的性能比較

5 結(jié)束語(yǔ)

本文將鴿子優(yōu)化算法與蛋白質(zhì)復(fù)合物的特性相結(jié)合，提出了一種蛋白質(zhì)復(fù)合物識(shí)別算法PIOC。該算法將鴿子的全局尋優(yōu)搜索和局部尋優(yōu)搜索特性應(yīng)用到PPI網(wǎng)絡(luò)中尋找更優(yōu)蛋白質(zhì)復(fù)合物問(wèn)題上，先通過(guò)全局搜索形成蛋白質(zhì)復(fù)合物的核心，再通過(guò)局部搜索將附件蛋白質(zhì)聚集到核心簇中形成蛋白質(zhì)復(fù)合物。與傳統(tǒng)的聚類算法相比，PIOC不僅考慮到PPI網(wǎng)絡(luò)的全局性和局部性，還考慮到蛋白質(zhì)復(fù)合物的核心-附件結(jié)構(gòu)。與其他蛋白質(zhì)復(fù)合物識(shí)別方法的性能比較顯示，PIOC能更有效地識(shí)別蛋白質(zhì)復(fù)合物。但是該算法的聚類數(shù)目需要人為控制以及蛋白質(zhì)復(fù)合物間的重疊過(guò)多，這些問(wèn)題還有待進(jìn)一步研究。

[1]Spirin V,Mirny LA.Protein complexes and functional modules in molecular networks[J].Proceedings of the National Academy of Sciences of the United States of America,2003,100(21):12123-12128.

[2]DangerR,Pla F,MolinaA,et al.Towards a protein-protein interaction information extraction system:recognizing named entities[J].Knowledge-Based Systems 2014,57:104-118.

[3]Yu Liang,Gao Lin,Sun Penggang.Research on algorithms for complexes and functional modules prediction in proteinprotein interaction networks[J].Chinese Journal of Computers,2011,34(7):1239-1252.

[4]Guo Maozu,Dai Qiguo,Xu Liqiu,et al.One protein complexes identifying algorithm based on the novel modularity function[J].Journal of Computer Research and Development,2014,51(10):2178-2186.

[5]Tang Dongming,Zhu Qingxin,Yang Fan,et al.Efficient cluster analysis method for protein sequences[J].Journal of Software,2011,22(8):1827-1837.

[6]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[7]EnrightA J,Van Dongen S,Ouzounis CA.An efficient algorithm for large-scale detection of protein families[J].Nucleic Acids Research,2002,30(7):1575-1584.

[8]Li Xiaoli,Wu Min,Kwoh C K,et al.Computational approaches for detecting protein complexes from protein interaction networks:a survey[J].BMC Genomics,2010,11(1):S3.

[9]Liu Guimei,Wong L,Chua H N.Complex discovery from weighted PPI networks[J].Bioinformatics,2009,25(15):1891-1897.

[10]BaderGD,Hogue C W.An automated method for finding molecular complexes in large protein interaction networks[J].BMC Bioinformatics,2003,4:1-13.

[11]Altaf-Ul-Amin M,Shinbo Y,Mihara K,et al.Development and implementation of an algorithm for detection of protein complexes in large interaction networks[J].BMC Bioinformatics,2006,7:207-228.

[12]Wang Jianxin,Li Min,Chen Jian'er,et al.Afast hierarchical clustering algorithm for functional modules discovery in protein interaction networks[J].IEEE/ACM Transactionson Computational Biology and Bioinformatics,2011,8(3):607-620.

[13]Nepusz T,Yu Haiyuan,PaccanaroA.Detecting overlapping protein complexes in protein-protein interaction networks[J].Nature Methods,2012,9(5):471-472.

[14]Wu Min,Li Xiaoli,Kwoh C K,et al.Acore-attachment based method to detect protein complexes in PPI networks[J].BMC Bioinformatics,2009,10(1):169-185.

[15]Lei Xiujuan,Tian Jianfang,Ge Liang,et al.The clustering model and algorithm of PPI network based on propagating mechanism of artificial bee colony[J].Information Sciences,2013,247(15):21-39.

[16]Lei Xiujuan,Wang Fei,Wu Fangxiang,et al.Protein complex identification through Markov clustering with firefly algorithm on dynamic protein-protein interaction networks[J].Information Sciences,2016,329(6):303-316.

[17]Li Honghao,Duan Haibin.Bloch quantum-behaved pigeoninspired optimization for continuous optimization problems[C]//Proceeding of the Chinese Guidance,Navigation and Control Conference,Yantai,China,Aug 8-10,2014.Piscataway,USA:IEEE,2014:2634-2638.

[18]Duan Haibin,Qiao Peixin.Pigeon-inspired optimization:a new swarm intelligence optimizer for air robot path planning[J].International Journal of Intelligent Computing and Cybernetics,2014,7(1):24-37.

[19]Li Cong,Duan Haibin.Target detection approach for UAVs via improved pigeon-inspired optimization and edge potential function[J].Aerospace Science and Technology,2014,39:352-360.

[20]Sun hang,Duan Haibin.Member S:PID controller design based on prey-predator pigeon-inspired optimization algorithm[C]//Proceedings of the 2014 International Conference on Mechatronics and Automation,Tianjin,China,Aug 3-6,2014.Piscataway,USA:IEEE,2014:1416-1421.

[21]Zhang Aidong.Protein interaction networks[M].New York:Cambridge University Press,2009.

[22]Wang Jianxin,Li Min,Wang Huan,et al.Identification of essential proteins based on edge clustering coefficient[J].IEEE/ACM Transactions on Computational Biology&Bioinformatics,2012,9(4):1070-1080.

[23]Li Min,Wang Jianxin,Chen Jian'er.Distance measure-based algorithm for identification of protein complexes[J].Journal of Jilin University,2010,40(5):1318-1323.

[24]Wang Jianxin,Peng Xiaoqing,Li Min,et al.Construction and application of dynamic protein interaction network based on time course gene expression data[J].Proteomics,2013,13(2):301-312.

附中文參考文獻(xiàn)：

[3]魚(yú)亮,高琳,孫鵬崗.蛋白質(zhì)網(wǎng)絡(luò)中復(fù)合體和功能模塊預(yù)測(cè)算法研究[J].計(jì)算機(jī)學(xué)報(bào),2011,34(7):1239-1252.

[4]郭茂祖,代啟國(guó),徐立秋,等.一種蛋白質(zhì)復(fù)合體模塊度函數(shù)及其識(shí)別算法[J].計(jì)算機(jī)研究與發(fā)展,2014,51(10):2178-2186.

[5]唐東明,朱清新,楊凡,等.一種有效的蛋白質(zhì)序列聚類分析方法[J].軟件學(xué)報(bào),2011,22(8):1827-1837.

[23]李敏,王建新,陳建二.基于距離測(cè)定的蛋白質(zhì)復(fù)合物識(shí)別算法[J].吉林大學(xué)學(xué)報(bào),2010,40(5):1318-1323.

Identification of Protein Complexes by Simulating Process of Pigeon-Inspired Optimization*

DING Yulian,LEI Xiujuan+,DAI Cai
College of Computer Science,Shaanxi Normal University,Xi’an 710062,China
+Corresponding author:E-mail:xjlei168@163.com

DING Yulian,LEI Xiujuan,DAI Cai.Identification of protein complexes by simulating process of pigeoninspired optimization.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1279-1287.

Detecting protein complexes is crucial to understand the principles of cellular organization and predict diseases.Yet up to now,the performance of existing protein complex detection algorithms is not very ideal for the deficiencies of low accuracy,sensitive to noisy data and so on.This paper proposes a novel algorithm named pigeoninspired optimization clustering(PIOC)algorithm.It puts forward the concepts of cluster's closely adjacent nodes and attachment's attachment degree on core,and identifies protein complexes by simulating the process of pigeons finding home based on these two concepts.The PIOC algorithm combines the characters of first global search then local search of pigeon-inspired optimization(PIO)algorithm and the core-attachment structure of protein complexes.Particularly,it first develops the cores of protein complexes by the global search of PIO's map and compass operator,and then forms the protein complexes by gathering in the attachment proteins to the cores based on the local search of PIO landmark operation.The experimental results on yeast protein DIP dataset demonstrate that PIOC is more effective in detecting protein complexes than the state-of-the-art complex detection algorithms.

an was born in 1975.She

the Ph.D.degree from Northwestern Polytechnical University in 2005.Now she is a professor and Ph.D.supervisor at Shaanxi Normal University.Her research interests include intelligent computing and bioinformatics. 雷秀娟（1975—），女，陜西長(zhǎng)安人，2005年于西北工業(yè)大學(xué)獲得博士學(xué)位，現(xiàn)為陜西師范大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，生物信息學(xué)。

DING Yulian was born in 1992.She is an M.S.candidate at Shaanxi Normal University.Her research interests include data mining and bioinformatics.丁玉連（1992—），女，河南信陽(yáng)人，陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，生物信息。

DAI Cai was born in 1984.He received the Ph.D.degree from Xidian University in 2014.Now he is a lecturer at Shaanxi Normal University.His research interest is multi-objective optimization.代才（1984—），男，安徽阜南人，2014年于西安電子科技大學(xué)獲得博士學(xué)位，現(xiàn)為陜西師范大學(xué)講師，主要研究領(lǐng)域?yàn)槎嗄繕?biāo)優(yōu)化。

A

：TP391

*The National Natural Science Foundation of China under Grant Nos.61502290,61401263(國(guó)家自然科學(xué)基金);the Industrial Research Project of Science and Technology in Shaanxi Province under Grant No.2015GY016(陜西省工業(yè)科技攻關(guān)項(xiàng)目);the Postdoctoral Science Foundation of China under Grant No.2015M582606(中國(guó)博士后科學(xué)基金);the Graduated Student Innovation Foundation of Shaanxi Normal University under Grant No.2015CXS030(陜西師范大學(xué)研究生創(chuàng)新基金).

Received 2016-06,Accepted 2016-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-08-15,http://www.cnki.net/kcms/detail/11.5602.TP.20160815.1659.010.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1279-09

10.3778/j.issn.1673-9418.1607034

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

Key words:protein-protein interaction(PPI);pigeon-inspired optimization algorithm;protein complex;clustering