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

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

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

?

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

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

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

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

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

0　引　言

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

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

1　基本理論

1.1蟻群聚類算法

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

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

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

(1)

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

(2)

(3)

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

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

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

(4)

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

圖1　2個網(wǎng)絡(luò)實例

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

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

(5)

w(vivj)的取值范圍為[0,1]，當(dāng)vi與vj間不存在葉子結(jié)點且不存在任何共同鄰居時w(vivj)=0，當(dāng)結(jié)點vi和vj是對方的唯一鄰居時，則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ù)對LF算法的描述，可知LF算法中的拾起和放下概率是隨機(jī)的，螞蟻在對數(shù)據(jù)進(jìn)行拾起放下操作時可能會導(dǎo)致反復(fù)操作，這樣會降低算法的運行效率，并且初始節(jié)點的選取，也會對算法的效率影響明顯[6].

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

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

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

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

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

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

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

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

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

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

3　仿真實驗及結(jié)果分析

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

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

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

3.2評價準(zhǔn)則

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

(6)

(7)

(8)

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

3.3結(jié)果分析

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

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

表2　聚類結(jié)果

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

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

4　結(jié)　論

本文提出的基于邊關(guān)聯(lián)強度的蟻群優(yōu)化聚類算法可以應(yīng)用在蛋白質(zhì)相互作用網(wǎng)絡(luò)中并能取得較好的聚類效果，時間空間復(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] 雷秀娟，黃旭，吳爽，等.基于連接強度的PPI網(wǎng)絡(luò)蟻群優(yōu)化聚類方法[J].北京：電子學(xué)報，2012，40(4): 695-702.

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

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

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

[7] 李敏，王建新，陳建二，等.基于距離測定的蛋白質(zhì)復(fù)合物識別算法[J].長春：吉林大學(xué)學(xué)報，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