鄭文萍，李晉玉，王 杰,2

1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

3.山西大學(xué) 大數(shù)據(jù)挖掘與智能技術(shù)山西省協(xié)同創(chuàng)新技術(shù)中心，太原 030006

1 引言

隨著人類基因組計(jì)劃的實(shí)施，生物醫(yī)學(xué)進(jìn)入后基因時代，系統(tǒng)全面地理解蛋白質(zhì)之間通過相互作用完成生命活動的規(guī)律成為研究熱點(diǎn)之一[1]。近年來，隨著酵母雙雜交、微陣列等高通量技術(shù)的應(yīng)用，產(chǎn)生了大量的蛋白質(zhì)互作用（protein-protein interaction，PPI）數(shù)據(jù)，這些數(shù)據(jù)可以表示為蛋白質(zhì)互作用網(wǎng)絡(luò)的形式[2]。通常將蛋白質(zhì)互作用網(wǎng)絡(luò)看作一個圖G=(V,E),其中節(jié)點(diǎn)表示蛋白質(zhì)，邊表示蛋白質(zhì)之間的相互作用。在蛋白質(zhì)互作用網(wǎng)絡(luò)中，蛋白質(zhì)復(fù)合物是指在同一時間和空間組成一個多分子機(jī)制的一組蛋白質(zhì)。從大規(guī)模蛋白質(zhì)互作用網(wǎng)絡(luò)中識別蛋白質(zhì)復(fù)合物對預(yù)測蛋白質(zhì)功能，解釋特定的生物進(jìn)程具有重要作用。蛋白質(zhì)復(fù)合物往往對應(yīng)于互作用網(wǎng)絡(luò)圖中的一些稠密子圖[3]。基于蛋白質(zhì)互作用網(wǎng)絡(luò)的圖聚類算法是識別網(wǎng)絡(luò)中復(fù)合物[4-6]的有效方法。

2005年，Palla等人[7]提出了派系過濾算法CPM（clique percolation method），并基于此設(shè)計(jì)了CFinder（clique finder）[8]工具，尋找網(wǎng)絡(luò)中所有的k-完全子圖（k-團(tuán)），合并具有k-1個公共節(jié)點(diǎn)的k-團(tuán)形成簇，作為參考蛋白質(zhì)復(fù)合物。2012年，Liu等人[9]對CPM算法進(jìn)行了改進(jìn)，提出了基于團(tuán)滲透和距離限制的蛋白質(zhì)復(fù)合物識別算法CPM-DR（clique percolation method based on distance restriction）。然而，尋找一個圖的k-完全子圖是NP（non-deterministic polynomial）困難問題。2003年，Bader和Hogue[10]提出了基于局部密度搜索的MCODE（molecular complex detection）算法，以節(jié)點(diǎn)鄰域的k-核局部網(wǎng)絡(luò)密度作為PPI網(wǎng)絡(luò)中節(jié)點(diǎn)的權(quán)重，并選擇權(quán)重最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)；以種子節(jié)點(diǎn)為初始簇中心，迭代向當(dāng)前簇中加入節(jié)點(diǎn)權(quán)重大于給定閾值的鄰居節(jié)點(diǎn)，完成簇?cái)U(kuò)展過程。MCODE算法時間復(fù)雜度為O(n)，被廣泛應(yīng)用于大規(guī)模網(wǎng)絡(luò)，然而它不能保證所發(fā)現(xiàn)的簇內(nèi)連接緊密[11]。2006年，Altaf-Ul-Amin等人[12]提出DPClus（development clustering）算法，認(rèn)為存在相互作用的兩個節(jié)點(diǎn)之間的公共鄰居數(shù)越多，則作用越強(qiáng)烈，以此對PPI網(wǎng)絡(luò)中的邊加權(quán)，并定義節(jié)點(diǎn)權(quán)重為加權(quán)度和，選擇權(quán)重最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)；DPClus還考慮了簇邊界節(jié)點(diǎn)對當(dāng)前簇的影響，給出了節(jié)點(diǎn)的簇邊界性值，與簇密度結(jié)合進(jìn)行簇?cái)U(kuò)展，對PPI網(wǎng)絡(luò)中稠密區(qū)域和稀疏區(qū)域加以區(qū)分；擴(kuò)展之后形成的稠密區(qū)域作為識別的蛋白質(zhì)復(fù)合物。2008年，李敏等人[11]對DPClus的邊界性值進(jìn)行改進(jìn)，提出了IPCA（improvement development clustering algorithm）算法，將子圖直徑和子圖密度相結(jié)合進(jìn)行簇?cái)U(kuò)展，并將子圖直徑作為蛋白質(zhì)復(fù)合物識別特征之一，可以發(fā)現(xiàn)重疊的蛋白質(zhì)復(fù)合物，提高了算法效率。2011年，王建新等人[13]給出了對加權(quán)蛋白質(zhì)互作用網(wǎng)絡(luò)中的功能模塊進(jìn)行識別的層次聚類算法HC-PIN（hierarchical clustering-protein interaction network）。2012年，Nepusz等人[14]綜合考慮簇內(nèi)緊密度和簇間分離性，提出了ClusterOne（clustering with overlapping neighborhood expansion）算法對蛋白質(zhì)復(fù)合物進(jìn)行識別。

種子節(jié)點(diǎn)的選擇對于最終形成的簇有很大影響。以上各種計(jì)算方法，一旦選定權(quán)重最大的節(jié)點(diǎn)作為初始簇中心，在簇?cái)U(kuò)展過程中種子節(jié)點(diǎn)不再改變。然而在蛋白質(zhì)互作用網(wǎng)絡(luò)中，一方面，具有最大權(quán)重的節(jié)點(diǎn)往往不是唯一的；另一方面，盡管被選作簇中心的節(jié)點(diǎn)通常權(quán)重較大，但僅選擇最大權(quán)重的節(jié)點(diǎn)作為種子節(jié)點(diǎn)進(jìn)行擴(kuò)展，在一定程度上縮小了簇發(fā)現(xiàn)過程的搜索空間。此外，在簇?cái)U(kuò)展過程中，一個節(jié)點(diǎn)一旦被加入到某一個簇中，再不會被調(diào)整出簇，這種方法也縮小了簇發(fā)現(xiàn)的搜索空間。

以啟發(fā)式為代表的智能優(yōu)化算法可以通過種群進(jìn)化的方式提高簇發(fā)現(xiàn)過程的多樣性，目前已經(jīng)逐漸發(fā)展為一種有競爭力的復(fù)合物發(fā)現(xiàn)方法。在文獻(xiàn)[15-17]中，蟻群算法被用來進(jìn)行社區(qū)發(fā)現(xiàn)和蛋白質(zhì)功能模塊識別。遺傳算法作為智能優(yōu)化算法的一種，近年來已經(jīng)被用來與聚類算法相融合，進(jìn)行蛋白質(zhì)復(fù)合物識別。2012年，Mukhopadhyay等人[18]提出了基于多目標(biāo)進(jìn)化的復(fù)合物識別算法PROCOMOSS（protein complex detection using multi-objective evolutionary approach based on semantic similarity），個體表示復(fù)合物（簇），用k-means算法產(chǎn)生初始種群，為了得到內(nèi)部連通的子網(wǎng)絡(luò)作為簇，算法僅采用變異方式使種群進(jìn)化，沒有使用交叉操作。2015年，Emad等人[19]用遺傳算法對蛋白質(zhì)互作用網(wǎng)絡(luò)進(jìn)行復(fù)合物識別，個體表示一種簇劃分結(jié)果，同樣也僅通過變異操作實(shí)現(xiàn)種群進(jìn)化。2015年，Cao等人[20]提出了一種算法MOEPGA（multi-objective evolutionary programming genetic algorithm），在進(jìn)化過程中抽取非支配子圖作為預(yù)測簇，通過對兩個有公共節(jié)點(diǎn)的子圖添加邊的方式產(chǎn)生變異，調(diào)整簇的結(jié)構(gòu)。

以上基于種群進(jìn)化方法在PPI網(wǎng)絡(luò)中進(jìn)行蛋白質(zhì)復(fù)合物發(fā)現(xiàn)的算法中，直接進(jìn)行交叉操作會產(chǎn)生大量的內(nèi)部不連通的簇，因此大多僅采用了變異的種群進(jìn)化方式。本文提出一種基于遺傳算法的蛋白質(zhì)復(fù)合物識別的圖聚類算法GAGC（genetic algorithm based graph clustering），其中個體表示一種聚類結(jié)果（類別之間可能存在重疊節(jié)點(diǎn)）。首先對IPCA算法[11]進(jìn)行改進(jìn)產(chǎn)生初始種群；然后設(shè)計(jì)了基于網(wǎng)絡(luò)對齊的交叉進(jìn)化方式產(chǎn)生下一代種群；以F-measure值作為種群進(jìn)化的目標(biāo)函數(shù)。與DPClus、MCODE、IPCA、ClusterOne、HC-PIN、CFinder算法進(jìn)行了對比實(shí)驗(yàn)，結(jié)果表明GAGC算法能夠擴(kuò)大圖聚類算法的搜索空間，提高解的多樣性，進(jìn)而提高蛋白質(zhì)復(fù)合物檢測的性能。

2 基本概念

蛋白質(zhì)互作用網(wǎng)絡(luò)可以表示為一個簡單無向圖G=(V,E)，其中節(jié)點(diǎn)集合V表示蛋白質(zhì)集合，邊集E表示蛋白質(zhì)之間相互作用集合。

節(jié)點(diǎn)v的鄰域Nv={u|(u,v)∈E}，定義節(jié)點(diǎn)v對子圖K(v?V(K))的連接概率為：

子圖K直徑D(K)表示子圖K中任意一對節(jié)點(diǎn)之間最短路徑的最大長度，子圖K的一階鄰域定義為

圖G的頂點(diǎn)子集S的導(dǎo)出子圖G[S]是由頂點(diǎn)集S和G中連接S中節(jié)點(diǎn)的邊所構(gòu)成的子圖，即V(G[S])=S,E(G[S])={(u,v)|(u,v)∈E,u∈S,v∈S}。在不引起混淆的情況下，簡記G[S]為S。

本文采用重疊分?jǐn)?shù)（overlapping score，OS）[21]衡量兩個子圖G1和G2的相似性，定義見式（2）。顯然，兩個子圖具有的公共節(jié)點(diǎn)越多，重疊分?jǐn)?shù)值越高。

如果G1和G2表示兩個蛋白質(zhì)復(fù)合物，則式（2）可以用來衡量這兩個復(fù)合物組成成分的相似性，其中V(Gi)表示組成復(fù)合物Gi的蛋白質(zhì)集合。兩個復(fù)合物擁有的公共蛋白質(zhì)越多，則它們越相似。通常會設(shè)定一個閾值ω，如果OS(G1,G2)≥ω，則兩個復(fù)合物是相匹配的。在蛋白質(zhì)復(fù)合物識別問題中通常取ω=0.2[9-13,22]。

3 基于遺傳算法的蛋白質(zhì)復(fù)合物識別算法GAGC

在蛋白質(zhì)互作用（PPI）網(wǎng)絡(luò)中進(jìn)行復(fù)合物識別，本質(zhì)上是對PPI網(wǎng)絡(luò)所對應(yīng)的圖G進(jìn)行圖聚類，最終所得的一個簇對應(yīng)一種蛋白質(zhì)復(fù)合物。圖聚類作為一種NP困難的組合優(yōu)化方法，使用啟發(fā)式搜索方法可以保證在允許的時間內(nèi)給出滿意的圖聚類結(jié)果，它的兩個關(guān)鍵環(huán)節(jié)是種子節(jié)點(diǎn)的選擇過程和簇?cái)U(kuò)展過程。遺傳算法（genetic algorithm，GA）是一種有效的全局優(yōu)化計(jì)算技術(shù)，采用群體搜索對當(dāng)前種群采用選擇、交叉、變異等基本操作，產(chǎn)生新一代種群，通過種群進(jìn)化達(dá)到或接近最優(yōu)解。本文設(shè)計(jì)了一種基于遺傳算法的圖聚類方法GAGC在蛋白質(zhì)互作用網(wǎng)絡(luò)中進(jìn)行復(fù)合物發(fā)現(xiàn)。文中一條染色體（個體）對應(yīng)一個可行的圖聚類結(jié)果，染色體由多個相互之間有重疊的基因組成，每個基因?qū)?yīng)一個可能的蛋白質(zhì)復(fù)合物，算法主要包括初始種群優(yōu)化、選擇、交叉、變異等基本過程。

3.1 目標(biāo)函數(shù)-個體適應(yīng)度

適應(yīng)度是遺傳算法的重要指標(biāo)，用來衡量種群中個體的優(yōu)劣程度，其函數(shù)值大小影響到種群中每個個體的生存幾率的大小，對算法的性能和收斂速度有很大影響。GAGC選用F-measure作為個體的適應(yīng)度評價(jià)函數(shù)，其綜合了精準(zhǔn)率（Precision）和召回率（Recall）兩個指標(biāo)。精準(zhǔn)率是算法正確識別的復(fù)合物數(shù)與算法得到的復(fù)合物總數(shù)之比，召回率是標(biāo)準(zhǔn)數(shù)據(jù)庫中蛋白質(zhì)復(fù)合物被識別的準(zhǔn)確率，如式（3）～（7）所示。其中，重疊分?jǐn)?shù)（OS）[21]計(jì)算復(fù)合物的匹配情況。通常，對于復(fù)合物P1和P2，如果OS(P1,P2)≥0.2，則可以認(rèn)為兩個復(fù)合物是相匹配的[9-13,22]。

令P表示算法得到的蛋白質(zhì)復(fù)合物集合，B表示標(biāo)準(zhǔn)數(shù)據(jù)集中蛋白質(zhì)復(fù)合物的集合。定義：

利用式（3），定義算法精準(zhǔn)率如式（5）所示。

利用式（4），定義算法召回率如式（6）所示。

根據(jù)式（5）、（6），可以得到某個體的F-measure值。

本文采用F-measure值作為算法GAGC的適應(yīng)度函數(shù)來衡量個體的優(yōu)劣。

3.2 初始種群產(chǎn)生過程

本文采用算法IPCA[11]產(chǎn)生一組可行的圖聚類結(jié)果作為初始種群。IPCA算法首先對網(wǎng)絡(luò)的節(jié)點(diǎn)權(quán)重進(jìn)行定義，選擇權(quán)重最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)并擴(kuò)展成為簇。僅選擇最大權(quán)重節(jié)點(diǎn)作為種子節(jié)點(diǎn)進(jìn)行簇?cái)U(kuò)展，無法保證初始種群的多樣性。因此，本文對IPCA算法進(jìn)行改進(jìn)，選擇種子節(jié)點(diǎn)的過程中加入輪盤賭機(jī)制，一個節(jié)點(diǎn)權(quán)重越大，成為種子節(jié)點(diǎn)的概率越大。這樣，既可以保證選擇的種子節(jié)點(diǎn)在概率意義下有較大權(quán)重，也可以確保種子節(jié)點(diǎn)選擇的多樣性，并最終擴(kuò)展得到圖聚類的多個可行解作為初始種群。

初始種群的產(chǎn)生過程如算法1所示。

算法1初始種群構(gòu)造子過程InitialPopulation

輸入：圖G=(V,E)，參數(shù)Tin和直徑參數(shù)d，種群大小k(默認(rèn)k=50)。

輸出：初始種群P={P1,P2,…,Pk}。

步驟1令t=1，根據(jù)式（8）和式（9）分別計(jì)算G中邊權(quán)重EW(u,v)和頂點(diǎn)權(quán)重NW(u)，并將頂點(diǎn)按權(quán)重值非遞增排序。

步驟2令候選種子節(jié)點(diǎn)集合HS=V,Pt=?。

步驟3若HS非空，轉(zhuǎn)步驟4；若節(jié)點(diǎn)vi∈HS，則其被選擇成為種子節(jié)點(diǎn)的概率是

步驟4按照輪盤賭機(jī)制選擇HS中的一個節(jié)點(diǎn)v作為種子節(jié)點(diǎn)，令K={v},HS=HS-{v}。

步驟5在子圖K的一階鄰域NK中，如果存在節(jié)點(diǎn)u滿足IN(u,K)＞Tin且D(G[K?{v}])≤d，則令K=K?{u}和HS=HS-{u}，轉(zhuǎn)步驟5；若不存在節(jié)點(diǎn)u，令pt=pt?{K}，轉(zhuǎn)步驟3。

步驟6t=t+1,如果t≤k,轉(zhuǎn)步驟2；否則，結(jié)束并輸出初始種群P。

3.3 選擇策略

為了體現(xiàn)遺傳算法適者生存的思想，使得優(yōu)質(zhì)個體參與進(jìn)化，從當(dāng)前種群中選擇個體去產(chǎn)生下一代個體，此處選擇適應(yīng)度值較高的個體進(jìn)行進(jìn)化并成為下一代種群中的個體。如果單純按照適應(yīng)度值從高到低順序選擇，會降低種群的多樣性，使得遺傳算法早熟，因此此處采用輪盤賭方式，選擇成為下一代個體的概率與節(jié)點(diǎn)的適應(yīng)度成正比。設(shè)種群大小為n，每個個體的適應(yīng)度為fi，則i被選中的概率為。這樣優(yōu)秀個體會以更大概率被選擇，選擇的方法是：

（3）在[0,1]之間產(chǎn)生一個隨機(jī)數(shù)rand，若rand≤prob1，則個體1被選中，若probi-1＜rand≤probi，則選擇第i個個體。

重復(fù)以上操作n0次，則產(chǎn)生了n0個個體構(gòu)成的新的種群，本文取初始種群規(guī)模n0=50。

除此之外，為了保留每一代種群中的最優(yōu)個體，在產(chǎn)生了新的用于進(jìn)化下一代的種群后，如果當(dāng)前種群中的最優(yōu)個體的適應(yīng)度值低于上一代最優(yōu)個體的適應(yīng)度值，則使用上一代中的最優(yōu)個體替換當(dāng)前所選種群中的最差個體。

3.4 基于染色體對齊的交叉策略

交叉操作是遺傳算法中最重要也是最基本的遺傳操作。本文算法中，如果直接選擇兩個染色體進(jìn)行交叉，可能使得交叉結(jié)果中存在大量節(jié)點(diǎn)沒有簇歸屬，影響聚類效果。為了更有效地進(jìn)行交叉操作，本文算法首先根據(jù)重疊分?jǐn)?shù)將兩個染色體中的基因?qū)R，使兩個等位基因表示的子圖有比較多的重復(fù)節(jié)點(diǎn)。交叉操作應(yīng)該在等位基因上進(jìn)行，這樣可以盡可能保證基因交叉后產(chǎn)生的新子圖是連通的。

3.4.1 染色體對齊機(jī)制

GAGC算法中的一個染色體（個體）代表一個圖聚類結(jié)果，染色體的每個基因代表一個簇，即一個頂點(diǎn)子集。此處采用式（2）定義的重疊分?jǐn)?shù)OS作為兩條染色體對齊的依據(jù)。

設(shè)S=(s1s2…sx)和R=(r1r2…ry)是兩個長度分別為x和y的染色體。首先構(gòu)造S和R的相似矩陣Mx×y,其元素mi,j=OS(si,rj)。

不失一般性，假設(shè)x≥y，具體算法描述如下。

染色體對齊算法Alignment(S,R,x,y)：

1.ints1[x],r1[y];//初始化為0

2.For(i=1;i＜=x;i++)

3.{

4.intmaxi=0;

5.For(j=1;j＜=y;j++)

6.{k=0;

7. if(OS(s[i],r[j])＞maxi&&r1[j]==0)

8. {maxi=OS(s[i],r[j]);k=j;}

9.}

10.if(maxi＞=0.8){s1[i]=k;r1[k]=1;}

11.}

12.For(j=1;j＜=x;j++)

13.if(s1[j]!=0)tempr[j]=r[s1[j]];

14.For(j=1;j＜=y;j++)

15.r[j]=tempr[j];

選擇兩條染色體中長度較長的染色體（假設(shè)為染色體s）作為參照染色體，對s的每一個基因si，在染色體r中選擇未被使用過的OS(si,rj)≥0.8且重疊分?jǐn)?shù)最大的基因作為si的等位基因。如果等位基因不存在，則用空位表示。

對圖1（1）中的染色體1和染色體2執(zhí)行對齊操作的過程如下。

首先，根據(jù)重疊分?jǐn)?shù)定義，構(gòu)建兩個染色體的相似矩陣M：然后，以較長的染色體1為參照，進(jìn)行對齊。對染色體1的每個基因pi，遍歷相似矩陣，得到與該基因重疊分?jǐn)?shù)值最高且尚未對齊的染色體2中的基因q，稱q為pi的等位基因。將q在染色體2中移動到與pi對應(yīng)的位置。

如果染色體1中某個基因無法在染色體2中找到等位基因，則將其移動到染色體1的末尾位置。

圖1（2）給出了兩個染色體對齊后的結(jié)果圖。

3.4.2 交叉策略

遺傳算法的交叉機(jī)制是優(yōu)化的關(guān)鍵環(huán)節(jié)。為了擴(kuò)大可行解的搜索空間，增加個體多樣性，GAGC算法主要通過交叉操作改變?nèi)旧w上的等位基因（復(fù)合物）。本文選用傳統(tǒng)遺傳算法的單點(diǎn)交叉機(jī)制，交叉時每次都以種群中具有最高適應(yīng)度的個體作為父本，從剩余的個體中隨機(jī)選擇母本與其進(jìn)行交叉。交叉方式為：首先將選擇的兩個個體染色體對齊，然后隨機(jī)產(chǎn)生一個交叉位，個體染色體交叉位前后互換染色體片段，即等位基因互換。如圖2所示，來自父本的染色體和來自母本的染色體交叉時，產(chǎn)生的交叉點(diǎn)為染色體的位置1，此時將父本與母本的染色體交叉位置之后的染色體片段互換，形成兩個新的子代。

交叉算法過程如算法2所示。

算法2交叉子過程GAGC-CROSSOVER

輸入：父本染色體F和母本染色體M。

輸出：新的染色體son1、son2。

步驟1按照輪盤賭方式選擇當(dāng)前種群個體適應(yīng)度最高的個體作為父本F，再從當(dāng)代種群中隨機(jī)選擇另外一個個體作為母本M。

步驟2對M和F執(zhí)行染色體對齊算法Alignment。

步驟3隨機(jī)產(chǎn)生一個交叉點(diǎn)T；交換兩條染色體T位置之前和之后的基因（復(fù)合物）。

圖2給出了父本和母本交叉操作示意圖。

3.5 變異策略

Fig.1 Schematic diagram of chromosome alignment圖1 染色體對齊示意圖

交叉操作產(chǎn)生的子代個體除了繼承父代個體的信息外，還會按一定的概率發(fā)生變異，這體現(xiàn)了生物遺傳的多樣性。變異操作是以固定概率Pm進(jìn)行的。變異時，首先隨機(jī)產(chǎn)生一個變異位，對應(yīng)于該染色體上的一個基因（簇）C。隨機(jī)選擇該復(fù)合物中的一個蛋白質(zhì)g，考慮g在對應(yīng)互作用網(wǎng)絡(luò)中的鄰域Ng。若Ng-C≠?，則隨機(jī)選擇節(jié)點(diǎn)v∈Ng-C，將v加入該復(fù)合物中；如果Ng-C=?，則刪除g。圖3給出了某蛋白質(zhì)的變異過程示意圖。

Fig.2 Schematic diagram of crossover operation圖2 交叉操作示意圖

Fig.3 Schematic diagram of variation operation圖3 變異操作示意圖

3.6 基于遺傳算法的圖聚類算法GAGC

GAGC算法的流程如下所示。

算法3基于遺傳算法的蛋白質(zhì)復(fù)合物識別圖聚類算法GAGC

輸入：G=(V,E),種群規(guī)模n0=50,k=100,Pm=0.3(變異率)，最大迭代次數(shù)y=50。

輸出：復(fù)合物集合C。

令t=0;

步驟1使用算法InitialPopulation產(chǎn)生100個初始個體。

步驟2執(zhí)行3.3節(jié)所述的選擇策略，選擇n0個個體作為當(dāng)前種群。

步驟3在當(dāng)前種群中，執(zhí)行n0次交叉操作GAGC-GROSSCOVER，產(chǎn)生2n0個子代個體。

步驟4對每個子代個體，隨機(jī)產(chǎn)生（0,1）的數(shù)Rf，如果Rf＜Pm,則該個體執(zhí)行變異操作。

步驟5t=t+1，若t＜y，則轉(zhuǎn)步驟2。

步驟6輸出當(dāng)前種群最優(yōu)個體C作為最終聚類結(jié)果。

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

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

本文互作用網(wǎng)絡(luò)數(shù)據(jù)來自于DIP[23]和GAVIN[24]兩個釀酒酵母蛋白質(zhì)互作用網(wǎng)絡(luò)，在移除自環(huán)和重復(fù)的互作用后，DIP網(wǎng)絡(luò)最終包含4 930個節(jié)點(diǎn)和17 201條邊，GAVIN數(shù)據(jù)集包括1 430個節(jié)點(diǎn)和6 531條邊。采用的復(fù)合物標(biāo)準(zhǔn)集為CYC2008[25]標(biāo)準(zhǔn)集，其中包含由1 628個蛋白質(zhì)構(gòu)成的408個蛋白質(zhì)復(fù)合物。

為了評估算法檢測出的蛋白質(zhì)的性能，本文采用重疊分?jǐn)?shù)OS、精準(zhǔn)率、召回率和F-measure指標(biāo)進(jìn)行算法評價(jià)。其中重疊分?jǐn)?shù)OS是用來衡量兩個復(fù)合物的匹配效果的度量方式。以上4種評價(jià)方式在個體適應(yīng)度計(jì)算模塊中均已介紹。除此之外，選用Accuracy作為算法的評價(jià)指標(biāo)。Accuracy由敏感度（Sn）和真陽性預(yù)測值（PPV）構(gòu)成。敏感度（Sn）表示識別的在標(biāo)準(zhǔn)復(fù)合物中覆蓋蛋白質(zhì)的多少，真陽性預(yù)測值（PPV）表示識別的蛋白質(zhì)復(fù)合物成為真陽性的可能性。其定義如下：

其中，n表示標(biāo)準(zhǔn)集中復(fù)合物的個數(shù)；m表示算法識別的復(fù)合物個數(shù)；Tij表示第i個標(biāo)準(zhǔn)復(fù)合物與第j個算法所識別的復(fù)合物之間公共蛋白質(zhì)數(shù)目。

4.2 實(shí)驗(yàn)結(jié)果

為了分析加入遺傳算法的GAGC與IPCA的效果。本文分別比較了兩個算法在Tin取值0.1至0.9時F-measure和Precision的變化曲線圖。從圖4和圖5中可知，兩個算法Tin的變化趨勢大致相同，在Tin為0.5時，二者的F-measure均達(dá)到最大值，在Tin為0.4時，二者的Precision均達(dá)到最大值，但GAGC在不同參數(shù)的Precision和F-measure值均高于IPCA的取值，并且在F-measure值上提升近5%，在Precision值上提升近10%。這也就表明了加入遺傳算法對IPCA的改進(jìn)效果是明顯的。在GAVIN數(shù)據(jù)上F-measure值和Precision如圖4和圖5所示。

Fig.4 F-measurevalues of GAGC and IPCAon GAVIN data圖4GAGC與IPCA在GAVIN數(shù)據(jù)上的F-measure值

Fig.5 Precisionvalues of GAGC and IPCAon GAVIN data圖5GAGC與IPCA在GAVIN數(shù)據(jù)上的Precision值

Table 1 Performance comparison of different methods with GAGC on GAVIN data表1 幾種算法與GAGC算法在GAVIN數(shù)據(jù)上的對比分析

為了分析GAGC算法的性能，本文對比了DPClus、MCODE、IPCA、HC-PIN、ClusterOne、CFinder算法在DIP數(shù)據(jù)和GAVIN數(shù)據(jù)上的8個指標(biāo)Ncb、Ncp、Precision、Recall、F-measure、Sn、PPV、Accuracy的值。這里GAGC和IPCA的參數(shù)Tin=0.5，其他算法的參數(shù)根據(jù)作者給定的最優(yōu)參數(shù)值。由于遺傳算法是一種隨機(jī)算法，這里GAGC在相同參數(shù)下重復(fù)進(jìn)行30次實(shí)驗(yàn)，計(jì)算每個指標(biāo)的均值與標(biāo)準(zhǔn)差，與其他算法進(jìn)行對比，結(jié)果如表1和表2所示。從表1、表2可知GAGC在Recall上與IPCA相同，均為最高，并且在F-measure值上GAGC高于IPCA、DPClus、MCODE、CFinder、HC-PIN、ClusterOne算法，但精準(zhǔn)率相對較低。其主要原因?yàn)镚AGC算法在發(fā)現(xiàn)蛋白質(zhì)復(fù)合物時并未進(jìn)行后期的處理，即將所聚類的簇都看作是蛋白質(zhì)復(fù)合物，這樣就會導(dǎo)致算法產(chǎn)生的蛋白質(zhì)復(fù)合物數(shù)目偏大，從而精確率會低于其他算法。并且在其他3個指標(biāo)上，GAGC也與其他6種算法效果相當(dāng)。

Table 2 Performance comparison of different methods with GAGC on DIP data表2 幾種算法與GAGC算法在DIP數(shù)據(jù)上的對比分析

5 結(jié)束語

本文提出了一種基于遺傳算法的蛋白質(zhì)復(fù)合物識別算法GAGC。為了擴(kuò)大算法的搜索空間，首先改進(jìn)了IPCA算法，產(chǎn)生初始種群；為了能夠?qū)⑦z傳算法的交叉操作運(yùn)用到復(fù)合物識別中，設(shè)計(jì)了基于重疊分?jǐn)?shù)OS的染色體對齊方式；然后通過設(shè)計(jì)交叉方式，擴(kuò)大簇形成的搜索空間，從而提高算法識別蛋白質(zhì)復(fù)合物的精度。該算法框架也可以擴(kuò)展到其他聚類算法，通過選擇合適的適應(yīng)度函數(shù)，提升聚類算法的性能。

[1]Garrels J I.Yeast genomic databases and the challenge of the post-genomic era[J].Functional&Integrative Genomics,2002,2(4):212-237.

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

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

[4]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-1251.

[5]Li Xueyong,Wang Jianxin,Zhao Bihai,et al.Identification of protein complexes from multi-relationship protein interaction networks[J].Human Genomics,2016,10(S2):61-70.

[6]Li Min,Wu Xuehong,Wang Jianxin,et al.Towards the identification of protein complexes and functional modules by integrating PPI network and gene expression data[J].BMC Bioinformatics,2012,13(1):1-15.

[7]Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[8]Adamcsek B,Palla G,Farkas I J,et al.CFinder:locating cliques and overlapping modules in biological networks[J].Bioinformatics,2006,22(8):1021-1023.

[9]Liu Binbin,Li Min,Wang Jianxin,et al.An algorithm for identifying protein complexes based on clique percolation and distance restriction[J].System Engineering-Theory and Practice,2012,32(2):389-397.

[10]Bader G D,Hogue C W V.An automated method for finding molecular complexes in large protein interaction networks[J].BMC Bioinformatics,2003,4(2):20-29.

[11]Li Min,Chen Jian'er,Wang Jianxin,et al.Modifying the DPClus algorithm for identifying protein complexes based on new topological structures[J].BMC Bioinformatics,2008,9(1):1-16.

[12]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(1):207-219.

[13]Wang Jianxin,Li Min,Chen Jian'er,et al.A fast hierarchical clustering algorithm for functional modules discovery in protein interaction networks[J].IEEE/ACM Transactions on Com-putational Biology&Bioinformatics,2011,8(3):607-620.

[14]Nepusz T,Yu Haiyuan,Paccanaro A.Detecting overlapping protein complexes in protein-protein interaction networks[J].Nature Methods,2012,9(5):471-476.

[15]Liu Yan,Wang Qingxian,Wang Qiang,et al.Email community detection using artificial ant colony clustering[C]//LNCS 4537:Proceedings of the 2007 International Workshops Advances in Web and Network Technologies,and Information Management,Huangshan,Jun 16-18,2007.Berlin,Heidelberg:Springer,2007:287-298.

[16]Ji Junzhong,Liu Zhijun,Zhang Aidong,et al.HAM-FMD:mining functional modules in protein-protein interaction networks using ant colony optimization and multi-agent evolution[J].Neurocomputing,2013,121(18):453-469.

[17]Chang Honghao,Feng Zuren,Ren Zhigang.Community detection using ant colony optimization[C]//Proceedings of the 2013 IEEE Congress on Evolutionary Computation,Cancun,Jun 20-23,2013.Piscataway:IEEE,2013:3072-3078.

[18]Mukhopadhyay A,Ray S,De M.Detecting protein complexes in a PPI network:a gene ontology based multi-objective evolutionary approach[J].Molecular Biosystems,2012,8(11):3036-3048.

[19]Emad R,Ahmed N,Moataz A.Protein complexes predictions within protein interaction networks using genetic algorithms[J].BMC Bioinformatics,2016,17(S7):481-543.

[20]Cao Buwen,Luo Jiawei,Liang Cheng,et al.MOEPGA:a novel method to detect protein complexes in yeast proteinprotein interaction networks based on multiobjective evolutionary programming genetic algorithm[J].Computational Biology&Chemistry,2015,58:173-181.

[21]Brohée S,Helden J V.Evaluation of clustering algorithms for protein-protein interaction networks[J].BMC Bioinformatics,2006,7(1):1-19.

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

[23]Xenarios I,Salwínski L,Duan X J,et al.DIP,the database of interacting proteins:a research tool for studying cellular networks of protein interactions[J].Nucleic Acids Research,2002,30(1):303-305.

[24]Gavin A C,Aloy P,Grandi P,et al.Proteome survey reveals modularity of the yeast cell machinery[J].Nature,2006,440(7084):631-636.

[25]Pu Shuye,Wong J,Turner B,et al.Up-to-date catalogues of yeast protein complexes[J].Nucleic Acids Research,2009,37(3):825-831.

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

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

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

[9]劉彬彬,李敏,王建新,等.基于團(tuán)滲透和距離限制的蛋白質(zhì)復(fù)合物識別算法[J].系統(tǒng)工程理論與實(shí)踐,2012,32(2):389-397.