丁玉連，雷秀娟，代 才

陜西師范大學 計算機科學學院，西安 710062

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

丁玉連，雷秀娟+，代 才

陜西師范大學 計算機科學學院，西安 710062

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

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

1 引言

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

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

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

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

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

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

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

2 鴿子算法與PPI網(wǎng)絡基礎知識

2.1 鴿子算法

信鴿有著天生的歸巢能力，它們通過使用磁場、太陽和地標3個導航工具，準確找到遠方的家?；邙澴拥膶Ш叫袨?，一種新穎的群智能仿生算法鴿子優(yōu)化（pigeon-inspired optimization，PIO）算法[17]在2014年被提出。PIO算法主要通過兩個操作來模擬鴿子的導航行為，即地圖羅盤算子和地標算子。地圖羅盤算子的提出主要是基于太陽和磁場，而地標算子的提出主要基于地標。

（1）地圖羅盤算子

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

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

（2）地標算子

在地標算子中，假設鴿子都還沒有到達目的地，并且它們對地標都不熟。所有的鴿子都根據(jù)它們的適應度值排序，再通過式（3）減少一半鴿子(Np/2)：

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

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

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

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

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

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

其中，kv表示結點v的度；nv表示v的kv個鄰居結點之間存在的邊數(shù)。

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

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

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

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

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

對已有的酵母蛋白質(zhì)復合物標準庫中的蛋白質(zhì)復合物的研究表明，蛋白質(zhì)復合物存在以下3個特征：

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

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

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

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

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

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

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

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

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

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

（1）地圖羅盤操作

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

（2）地標操作

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

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

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

3.2 PIOC算法描述

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

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

算法PIOC聚類

輸入：PPI網(wǎng)絡對應的圖G=(V,E)

輸出：預測出來的蛋白質(zhì)復合物C

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

（1）初始化鴿子

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

C←the firstcnnode inSq（2）地圖羅盤算子

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

鴿子優(yōu)化算法PIO與聚類算法的對應關系如表1所示。

4 實驗結果與分析

4.1 實驗數(shù)據(jù)和評價標準

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

Table1 Corresponding relationships between PIO algorithm and clustering procedure of PPI network表1 PIO算法與PPI網(wǎng)絡中聚類過程的對應關系

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

其中，C表示預測的蛋白質(zhì)復合物；S表示標準庫中的蛋白質(zhì)復合物。

識別出來的復合物A與已知復合物B的匹配程度OS(A,B)[24]的計算公式如下：

其中，VA和VB分別表示蛋白質(zhì)復合物A和蛋白質(zhì)復合物B中的頂點集合。若兩個復合物的匹配程度OS(A,B)超過給定的閾值，則稱這兩個復合物匹配。一般對于酵母蛋白質(zhì)的數(shù)據(jù)集，取這個閾值為0.2[24]，即被檢測出來的蛋白質(zhì)復合物與標準庫中復合物的匹配程度值大于0.2時，這兩個復合物被認為是相互匹配的。當OS的值為1時被認為是完美匹配。

4.2 參數(shù)分析

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

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

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

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

將由PIOC得到的聚類結果與標準庫中的蛋白質(zhì)復合物進行比較，分析本文預測的蛋白質(zhì)復合物中正確和錯誤的蛋白質(zhì)。表2中隨機選擇PIOC識別的蛋白質(zhì)復合物中的7個復合物進行分析。從表2中可以看出，PIOC聚類方法能正確識別蛋白質(zhì)復合物中的絕大多數(shù)蛋白質(zhì)，其中個別復合物會包含錯誤蛋白質(zhì)或者漏掉個別蛋白質(zhì)，但標準蛋白質(zhì)復合物中的蛋白質(zhì)基本上都能被識別出來。

圖3可視化了表2中7號蛋白質(zhì)復合物。圖（a）表示標準庫中的蛋白質(zhì)復合物，不帶背景顏色的結點為PIOC未識別出來的蛋白質(zhì)。圖（b）表示PIOC檢測出來的蛋白質(zhì)復合物，其中不帶背景顏色的蛋白質(zhì)為被錯誤識別的蛋白質(zhì)。YIR025W和YGR-260C未被識別出來，是因為其與簇外的鄰接點鏈接更緊密。YGR225W被錯誤識別出來，是因為其只與核心簇中蛋白質(zhì)YKL022C相連。YLR451W被錯誤識別出來是因為其度為2，簇內(nèi)的鄰接點度值大于簇外的度值。

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

4.4 性能比較

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

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

由表3可以看出，PIOC識別出來的蛋白質(zhì)復合物數(shù)量和覆蓋的蛋白質(zhì)數(shù)量接近標準庫中復合物的標準，但蛋白質(zhì)復合物的平均大小偏大，這也說明PIOC識別出來的蛋白質(zhì)復合物之間有很多重疊。與之對應，F(xiàn)-MCL和DPClus等方法識別出來的蛋白質(zhì)復合物很多，覆蓋的蛋白質(zhì)數(shù)量也很大，但大多數(shù)蛋白質(zhì)是錯誤的，導致性能低。

Fig.3 Visualization of comparison圖3 可視化對比

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

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

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

5 結束語

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

[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.

附中文參考文獻：

[3]魚亮,高琳,孫鵬崗.蛋白質(zhì)網(wǎng)絡中復合體和功能模塊預測算法研究[J].計算機學報,2011,34(7):1239-1252.

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

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

[23]李敏,王建新,陳建二.基于距離測定的蛋白質(zhì)復合物識別算法[J].吉林大學學報,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—），女，陜西長安人，2005年于西北工業(yè)大學獲得博士學位，現(xiàn)為陜西師范大學教授、博士生導師，主要研究領域為智能計算，生物信息學。

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—），女，河南信陽人，陜西師范大學計算機科學學院碩士研究生，主要研究領域為數(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年于西安電子科技大學獲得博士學位，現(xiàn)為陜西師范大學講師，主要研究領域為多目標優(yōu)化。

A

：TP391

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

Received 2016-06,Accepted 2016-08.

CNKI網(wǎng)絡優(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