胡嘉偉，吳云志，樂　毅，張友華

(安徽農(nóng)業(yè)大學(xué) 信息與計(jì)算機(jī)學(xué)院，合肥 230036)

?

基于改進(jìn)LF算法的PPI網(wǎng)絡(luò)聚類方法

胡嘉偉，吳云志，樂毅，張友華

(安徽農(nóng)業(yè)大學(xué) 信息與計(jì)算機(jī)學(xué)院，合肥 230036)

研究蛋白質(zhì)相互作用(Protein-Protein Interaction, PPI)網(wǎng)絡(luò)是理解生命活動(dòng)的重要途徑之一，運(yùn)用數(shù)據(jù)挖掘中的聚類分析方法去研究蛋白質(zhì)相互作用已經(jīng)成為生物信息學(xué)的熱門領(lǐng)域.作為一種在PPI網(wǎng)絡(luò)聚類分析中新興的智能優(yōu)化算法,蟻群聚類算法因其固有的簡(jiǎn)單性、靈活性和魯棒性顯示出了巨大應(yīng)用潛力.將蟻群聚類算法應(yīng)用到PPI網(wǎng)絡(luò)聚類中，并進(jìn)行了改進(jìn)，提出了一種新的PPI網(wǎng)絡(luò)聚類算法.算法引入邊關(guān)聯(lián)強(qiáng)度的概念并以邊關(guān)聯(lián)強(qiáng)度作為相似度參數(shù)，對(duì)蟻群聚類算法中的拾起/放下策略加以改進(jìn).算法在MIPS數(shù)據(jù)庫中的PPI數(shù)據(jù)集上進(jìn)行了聚類測(cè)試，實(shí)驗(yàn)結(jié)果表明新算法的聚類效果和運(yùn)行效率都較為理想.

PPI網(wǎng)絡(luò)；蟻群聚類算法；邊關(guān)聯(lián)強(qiáng)度；聚類分析

0　引　言

人類基因組測(cè)序的完成標(biāo)志著一個(gè)新的生物學(xué)研究時(shí)代-后基因組時(shí)代的來臨， 與此同時(shí)產(chǎn)生了海量的基因組測(cè)序數(shù)據(jù)，傳統(tǒng)的生物學(xué)分析方法在大規(guī)格的基因組數(shù)據(jù)研究上已經(jīng)顯現(xiàn)出不足，運(yùn)用數(shù)據(jù)挖掘中的聚類分析方法研究蛋白質(zhì)相互作用日益成為生物信息學(xué)的研究熱點(diǎn)[1].

近年來，因自身的簡(jiǎn)單性、靈活性和魯棒性等優(yōu)勢(shì)的群智能優(yōu)化算法在蛋白質(zhì)網(wǎng)絡(luò)聚類分析中得到了較好的應(yīng)用前景.本文在Lumer和Faieta提出的LF蟻群聚類算法基礎(chǔ)上引入邊關(guān)聯(lián)強(qiáng)度，對(duì)螞蟻的拾起規(guī)則做了相應(yīng)改進(jìn)，進(jìn)一步提出了改進(jìn)的LF聚類算法，該算法在減少算法時(shí)間開銷的同時(shí)還可提升對(duì)PPI網(wǎng)絡(luò)的聚類效果.

1　基本理論

1.1蟻群聚類算法

Lumer和Faieta提出的蟻群聚類算法主要思想描述如下[2]：

將待聚類的數(shù)據(jù)隨機(jī)分布在一個(gè)二維平面上，并隨機(jī)產(chǎn)生虛擬螞蟻，螞蟻在平面移動(dòng)的過程中會(huì)對(duì)自身所背負(fù)的數(shù)據(jù)信息與周圍數(shù)據(jù)進(jìn)行相似性判斷，根據(jù)拾起放下策略判斷拾起或放下數(shù)據(jù)，最終產(chǎn)生數(shù)據(jù)聚類效果.

該算法首先將數(shù)據(jù)隨機(jī)分布在一個(gè)m×m的網(wǎng)格中,設(shè)螞蟻所處的位置為r，能見度為S，螞蟻在地點(diǎn)r觀察要比對(duì)的對(duì)象i，對(duì)象在地點(diǎn)與周圍物體的相似度計(jì)算公式為：

(1)

式中d(i，j)是i和j兩個(gè)數(shù)據(jù)對(duì)象之間的空間距離，α為衡量相似程度的參數(shù).在LF算法中，螞蟻選擇拾起或放下一個(gè)數(shù)據(jù)對(duì)象的概率如下式計(jì)算：

(2)

(3)

其中，式(2)、式(3)分別是計(jì)算螞蟻拾起和放下數(shù)據(jù)的概率，k1、k2為兩個(gè)常數(shù).如上所示，LF算法需要隨機(jī)產(chǎn)生一個(gè)概率與拾起或放下概率作比較，符合策略時(shí)才會(huì)執(zhí)行相應(yīng)的操作[3].

1.2邊關(guān)聯(lián)強(qiáng)度

在數(shù)據(jù)挖掘中，聚類分析通常以對(duì)象間距離或相似性度量為基礎(chǔ)，目標(biāo)是使類內(nèi)緊密而類間稀疏.網(wǎng)絡(luò)圖結(jié)點(diǎn)間基于結(jié)構(gòu)等價(jià)性的相似性度量應(yīng)用最廣泛的是Jaccard相似度，如式(4)所示：

(4)

Jaccard的假設(shè)認(rèn)為：若網(wǎng)絡(luò)圖中2個(gè)結(jié)點(diǎn)間的公共鄰接點(diǎn)越多，這2個(gè)結(jié)點(diǎn)在結(jié)構(gòu)上越相似或相等.但當(dāng)2個(gè)相鄰結(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)差異性較大時(shí)，該度量不能很好地反應(yīng)結(jié)點(diǎn)之間的連接傾向性[4].如圖1所示，圖1中Jaccard(AB)均為2/9，但是明顯可以看出圖1(a)中的結(jié)點(diǎn)A、B在網(wǎng)絡(luò)中更加緊密.

圖1　2個(gè)網(wǎng)絡(luò)實(shí)例

因此，對(duì)于不同的拓?fù)浣Y(jié)構(gòu)，王杰等人基于結(jié)點(diǎn)間的鄰域定義了關(guān)聯(lián)強(qiáng)度來描述網(wǎng)絡(luò)圖中結(jié)點(diǎn)之間邊連接的緊密程度，其定義如下[5]：

對(duì)圖G中的邊uv∈E，假設(shè)結(jié)點(diǎn)度d(vi)≤d(vj)，N(vi)、N(vj)分別為結(jié)點(diǎn)vi、vj的鄰居集合，則邊vivj∈E(G)的關(guān)聯(lián)強(qiáng)度w(vivj)為：

(5)

w(vivj)的取值范圍為[0,1]，當(dāng)vi與vj間不存在葉子結(jié)點(diǎn)且不存在任何共同鄰居時(shí)w(vivj)=0，當(dāng)結(jié)點(diǎn)vi和vj是對(duì)方的唯一鄰居時(shí)，則w(vivj)=1.以圖1為例，圖1(a)中w(AB)=2/3，圖1(b)中w(AB)=2/4，體現(xiàn)了兩者在拓?fù)浣Y(jié)構(gòu)上的差異，以此使得聚類效果更加有效.

2　改進(jìn)的蟻群聚類算法描述

2.1算法思想

根據(jù)對(duì)LF算法的描述，可知LF算法中的拾起和放下概率是隨機(jī)的，螞蟻在對(duì)數(shù)據(jù)進(jìn)行拾起放下操作時(shí)可能會(huì)導(dǎo)致反復(fù)操作，這樣會(huì)降低算法的運(yùn)行效率，并且初始節(jié)點(diǎn)的選取，也會(huì)對(duì)算法的效率影響明顯[6].

改進(jìn)算法在LF算法思想的基礎(chǔ)上，首先調(diào)整了螞蟻對(duì)數(shù)據(jù)的拾起策略，從上文得知邊關(guān)聯(lián)強(qiáng)度能更好的反應(yīng)聚類效果，且計(jì)算方式相對(duì)簡(jiǎn)單，因此采用了邊關(guān)聯(lián)強(qiáng)度來代替隨機(jī)概率作為螞蟻的拾起放下策略；其次在初始結(jié)點(diǎn)的選取上，螞蟻的初始位置從較優(yōu)數(shù)據(jù)中隨機(jī)選取而來；最后考慮到PPI網(wǎng)絡(luò)的小世界性，還對(duì)螞蟻的移動(dòng)范圍(距離初始位置的距離)進(jìn)行了控制.改進(jìn)后的蟻群聚類算法步驟如下：

輸入：PPI網(wǎng)絡(luò)數(shù)據(jù)，圖G=(V,E)；參數(shù)L為螞蟻的移動(dòng)范圍；ε為邊關(guān)聯(lián)強(qiáng)度設(shè)定的閾值.

輸出：聚類結(jié)果.

(1)設(shè)有n個(gè)蛋白質(zhì)結(jié)點(diǎn)，為每一個(gè)蛋白質(zhì)結(jié)點(diǎn)進(jìn)行編碼，并統(tǒng)計(jì)各結(jié)點(diǎn)的度，蛋白質(zhì)結(jié)點(diǎn)集合記為S=(s1,s2,…,sn)，在初始螞蟻的選取上，為了提高算法的效率而隨機(jī)選擇度比較高的結(jié)點(diǎn)si,i∈n；

(2)螞蟻si的初始類記為Ci，Ci=(si).si可視范圍記為NSi，在可視范圍內(nèi)計(jì)算各結(jié)點(diǎn)的邊關(guān)聯(lián)強(qiáng)度w(si,sj)，sj∈NSi，若w(si,sj)≥ε，進(jìn)行拾起操作，初始類進(jìn)行擴(kuò)充，Ci=(si,sj)；

(3)當(dāng)有結(jié)點(diǎn)被拾起時(shí)，螞蟻移動(dòng)至新結(jié)點(diǎn)的位置，螞蟻的移動(dòng)范圍l++，進(jìn)入判定條件l≤L是否成立：若成立，返回第(2)步，在新結(jié)點(diǎn)位置重新進(jìn)行聚類操作；若不成立，轉(zhuǎn)至第(4)步；

(5)調(diào)整ε的值，根據(jù)放下策略放棄部分稀疏點(diǎn)數(shù)據(jù)；

(6)產(chǎn)生最終聚類結(jié)果.

2.2算法時(shí)間復(fù)雜度

如上述所示，假設(shè)PPI網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模為N，在蛋白質(zhì)聚類過程中每個(gè)蛋白質(zhì)結(jié)點(diǎn)最少會(huì)被操作一次.每個(gè)結(jié)點(diǎn)在每次的聚類中都被操作一次但是都沒有聚類成功的情況下，此時(shí)每個(gè)結(jié)點(diǎn)被操作了N次.因此算法的時(shí)間復(fù)雜度最大為O(N2)，最小為O(N).

3　仿真實(shí)驗(yàn)及結(jié)果分析

3.1實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)環(huán)境

以MIPS數(shù)據(jù)庫作為本實(shí)驗(yàn)的實(shí)驗(yàn)源數(shù)據(jù)，并以MIPS數(shù)據(jù)庫提供的信息作為本實(shí)驗(yàn)的參照標(biāo)準(zhǔn)，來判斷本文算法聚類結(jié)果的準(zhǔn)確率及運(yùn)行效率.標(biāo)準(zhǔn)庫部分信息如表1所示.

表1　標(biāo)準(zhǔn)庫信息

3.2評(píng)價(jià)準(zhǔn)則

本文在對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)的過程中，采用了如下三種比較常見的評(píng)價(jià)指標(biāo)：覆蓋率Coverage、正確率Percision和查全率Recall.假設(shè)P為算法預(yù)測(cè)的蛋白質(zhì)模塊，B為標(biāo)準(zhǔn)數(shù)據(jù)庫中存在的蛋白質(zhì)模塊，m和n分別為算法聚類蛋白質(zhì)數(shù)和標(biāo)準(zhǔn)數(shù)據(jù)庫聚類蛋白質(zhì)數(shù).覆蓋率Coverage表示最終被聚類的蛋白質(zhì)數(shù)量占整個(gè)網(wǎng)絡(luò)蛋白質(zhì)個(gè)體百分比，正確率Percision表示模塊P和B的交集結(jié)點(diǎn)個(gè)數(shù)占P中蛋白質(zhì)結(jié)點(diǎn)個(gè)數(shù)的百分比，查全率Recall則表示模塊P和B的交集結(jié)點(diǎn)個(gè)數(shù)占B中蛋白質(zhì)結(jié)點(diǎn)個(gè)數(shù)的百分比.

(6)

(7)

(8)

如上式所示，Coverage越高，表明本次實(shí)驗(yàn)保留的蛋白質(zhì)越多；Percision越高，表明模塊內(nèi)部的準(zhǔn)確性越高；而Recall越高時(shí)，則表明本次實(shí)驗(yàn)預(yù)測(cè)出的有效蛋白質(zhì)模塊的數(shù)量越多.

3.3結(jié)果分析

本次實(shí)驗(yàn)需要控制的輸入?yún)?shù)有L(螞蟻的移動(dòng)范圍)、ε(邊關(guān)聯(lián)強(qiáng)度設(shè)置的閾值)，由文獻(xiàn)可知，蛋白質(zhì)復(fù)合物內(nèi)部的評(píng)價(jià)距離一般不超過2，網(wǎng)絡(luò)中結(jié)點(diǎn)的特征路徑評(píng)價(jià)長(zhǎng)度小于5[7].因此，在這里將L的值設(shè)為5.為了觀察ε值對(duì)聚類結(jié)果的影響，在實(shí)驗(yàn)中保持其他參數(shù)值不變，通過不斷調(diào)整ε值，觀察可知當(dāng)ε值為0.2～0.4時(shí)，實(shí)驗(yàn)所得聚類的個(gè)數(shù)、聚類蛋白質(zhì)數(shù)以及最大最小類與標(biāo)準(zhǔn)庫的較為接近.

結(jié)合以上分析，本實(shí)驗(yàn)室將ε設(shè)為0.3，L設(shè)為5，將算法運(yùn)行了20次，實(shí)驗(yàn)結(jié)果如表2所示；同時(shí)，我們選取現(xiàn)有的聚類算法，用相同數(shù)據(jù)庫作了實(shí)驗(yàn)結(jié)果比較，對(duì)比圖如表3所示.

表2　聚類結(jié)果

表3　聚類結(jié)果對(duì)比圖

通過上述比較可以得知：對(duì)于蛋白質(zhì)相互作用網(wǎng)絡(luò)中的聚類分析，基于邊關(guān)聯(lián)強(qiáng)度的蟻群聚類優(yōu)化算法可以有效找出聚類結(jié)果，而且算法的效率高，時(shí)間復(fù)雜度低.

4　結(jié)　論

本文提出的基于邊關(guān)聯(lián)強(qiáng)度的蟻群優(yōu)化聚類算法可以應(yīng)用在蛋白質(zhì)相互作用網(wǎng)絡(luò)中并能取得較好的聚類效果，時(shí)間空間復(fù)雜度得到了降低，但是在后續(xù)工作中還有優(yōu)化的空間，以期能應(yīng)用到更大規(guī)模的蛋白質(zhì)相互作用網(wǎng)絡(luò).

[1] Aidong Zhang.Protein Interaction Networks [M].New York: Cambridge University Press, 2009: 44-47.

[2] Lumer E, Faieta B. Diversity and Adaptation in Populations of Clustering Ants[A].Proceedings of the 3rd International Conference on Simulation of Adaptive Behavior:From Animal to Animals [C]. Cambridge, MA: MIT Press, 1994: 499-508.

[3] 雷秀娟，黃旭，吳爽，等.基于連接強(qiáng)度的PPI網(wǎng)絡(luò)蟻群優(yōu)化聚類方法[J].北京：電子學(xué)報(bào)，2012，40(4): 695-702.

[4] 王杰，梁吉業(yè)，鄭文萍，等.一種面向蛋白質(zhì)復(fù)合體檢測(cè)的圖聚類方法[J].北京：計(jì)算機(jī)研究與發(fā)展，2015，52(8): 1784-1793.

[5] 牛永杰.LF算法中蟻群移動(dòng)策略的研究[J].西安：航空計(jì)算技術(shù)，2013，43(4): 18-21.

[6] 金弟，劉大有，楊博,等.基于局部探測(cè)的快速復(fù)雜網(wǎng)絡(luò)聚類算法[J].北京：電子學(xué)報(bào)，2011，39(11): 2540-2546.

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

PPI Network Clustering Method Based on Improved LF Algorithm

HU Jia-wei，WU Yun-zhi，YUE Yi，ZHANG You-hua

(School of Information & Computer, Anhui Agricultural University, Anhui 230036, China)

Protein-Protein interactions network research is one the most important ways to understand of life activities. Using the clustering analysis method in data mining to study protein interactions has become popular in the field of bioinformatics. In PPI network clustering analysis, ant colony clustering algorithm as a new intelligent optimization algorithm, shows great potential for application because of its inherent simplicity, flexibility and robustness. Ant colony clustering is introduced into PPI network clustering, and is improved.A new PPI network clustering method is presented.This method modifies the pickup/drop rules of Ant colony algorithm by means of introducing the concept of edge intensity, which regards the edge intensity as similarity paramter to cluster the PPI network.Finally the algorithm is tested on the PPI data in MIPS database.The simulation results show that the new algorithm has better clustering effect and running efficiency.

PPI network; Ant colony clustering method; edge intensity; clustering analysis

2016-04-05

胡嘉偉(1991-)，男，碩士研究生，研究方向：生物信息.

張友華(1966-)，男，博士，教授，研究方向：農(nóng)業(yè)信息工程.

TP301.6

A

1671-119X(2016)03-0056-04