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

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

種子節(jié)點(diǎn)的選擇對(duì)于最終形成的簇有很大影響。以上各種計(jì)算方法，一旦選定權(quán)重最大的節(jié)點(diǎn)作為初始簇中心，在簇?cái)U(kuò)展過(guò)程中種子節(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)過(guò)程的搜索空間。此外，在簇?cái)U(kuò)展過(guò)程中，一個(gè)節(jié)點(diǎn)一旦被加入到某一個(gè)簇中，再不會(huì)被調(diào)整出簇，這種方法也縮小了簇發(fā)現(xiàn)的搜索空間。

以啟發(fā)式為代表的智能優(yōu)化算法可以通過(guò)種群進(jìn)化的方式提高簇發(fā)現(xiàn)過(guò)程的多樣性，目前已經(jīng)逐漸發(fā)展為一種有競(jìng)爭(zhēng)力的復(fù)合物發(fā)現(xiàn)方法。在文獻(xiàn)[15-17]中，蟻群算法被用來(lái)進(jìn)行社區(qū)發(fā)現(xiàn)和蛋白質(zhì)功能模塊識(shí)別。遺傳算法作為智能優(yōu)化算法的一種，近年來(lái)已經(jīng)被用來(lái)與聚類算法相融合，進(jìn)行蛋白質(zhì)復(fù)合物識(shí)別。2012年，Mukhopadhyay等人[18]提出了基于多目標(biāo)進(jìn)化的復(fù)合物識(shí)別算法PROCOMOSS（protein complex detection using multi-objective evolutionary approach based on semantic similarity），個(gè)體表示復(fù)合物（簇），用k-means算法產(chǎn)生初始種群，為了得到內(nèi)部連通的子網(wǎng)絡(luò)作為簇，算法僅采用變異方式使種群進(jìn)化，沒有使用交叉操作。2015年，Emad等人[19]用遺傳算法對(duì)蛋白質(zhì)互作用網(wǎng)絡(luò)進(jìn)行復(fù)合物識(shí)別，個(gè)體表示一種簇劃分結(jié)果，同樣也僅通過(guò)變異操作實(shí)現(xiàn)種群進(jìn)化。2015年，Cao等人[20]提出了一種算法MOEPGA（multi-objective evolutionary programming genetic algorithm），在進(jìn)化過(guò)程中抽取非支配子圖作為預(yù)測(cè)簇，通過(guò)對(duì)兩個(gè)有公共節(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)行交叉操作會(huì)產(chǎn)生大量的內(nèi)部不連通的簇，因此大多僅采用了變異的種群進(jìn)化方式。本文提出一種基于遺傳算法的蛋白質(zhì)復(fù)合物識(shí)別的圖聚類算法GAGC（genetic algorithm based graph clustering），其中個(gè)體表示一種聚類結(jié)果（類別之間可能存在重疊節(jié)點(diǎn)）。首先對(duì)IPCA算法[11]進(jìn)行改進(jìn)產(chǎn)生初始種群；然后設(shè)計(jì)了基于網(wǎng)絡(luò)對(duì)齊的交叉進(jìn)化方式產(chǎn)生下一代種群；以F-measure值作為種群進(jìn)化的目標(biāo)函數(shù)。與DPClus、MCODE、IPCA、ClusterOne、HC-PIN、CFinder算法進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果表明GAGC算法能夠擴(kuò)大圖聚類算法的搜索空間，提高解的多樣性，進(jìn)而提高蛋白質(zhì)復(fù)合物檢測(cè)的性能。

2 基本概念

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

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

子圖K直徑D(K)表示子圖K中任意一對(duì)節(jié)點(diǎn)之間最短路徑的最大長(zhǎng)度，子圖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}。在不引起混淆的情況下，簡(jiǎn)記G[S]為S。

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

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

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

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

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

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

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

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

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

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

算法1初始種群構(gòu)造子過(guò)程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中的一個(gè)節(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ì)個(gè)體參與進(jìn)化，從當(dāng)前種群中選擇個(gè)體去產(chǎn)生下一代個(gè)體，此處選擇適應(yīng)度值較高的個(gè)體進(jìn)行進(jìn)化并成為下一代種群中的個(gè)體。如果單純按照適應(yīng)度值從高到低順序選擇，會(huì)降低種群的多樣性，使得遺傳算法早熟，因此此處采用輪盤賭方式，選擇成為下一代個(gè)體的概率與節(jié)點(diǎn)的適應(yīng)度成正比。設(shè)種群大小為n，每個(gè)個(gè)體的適應(yīng)度為fi，則i被選中的概率為。這樣優(yōu)秀個(gè)體會(huì)以更大概率被選擇，選擇的方法是：

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

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

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

3.4 基于染色體對(duì)齊的交叉策略

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

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

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

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

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

染色體對(duì)齊算法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];

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

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

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

如果染色體1中某個(gè)基因無(wú)法在染色體2中找到等位基因，則將其移動(dòng)到染色體1的末尾位置。

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

3.4.2 交叉策略

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

交叉算法過(guò)程如算法2所示。

算法2交叉子過(guò)程GAGC-CROSSOVER

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

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

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

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

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

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

3.5 變異策略

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

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

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

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

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

GAGC算法的流程如下所示。

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

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

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

令t=0;

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

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

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

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

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

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

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

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

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

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

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

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

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

為了分析GAGC算法的性能，本文對(duì)比了DPClus、MCODE、IPCA、HC-PIN、ClusterOne、CFinder算法在DIP數(shù)據(jù)和GAVIN數(shù)據(jù)上的8個(gè)指標(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ì)算每個(gè)指標(biāo)的均值與標(biāo)準(zhǔn)差，與其他算法進(jìn)行對(duì)比，結(jié)果如表1和表2所示。從表1、表2可知GAGC在Recall上與IPCA相同，均為最高，并且在F-measure值上GAGC高于IPCA、DPClus、MCODE、CFinder、HC-PIN、ClusterOne算法，但精準(zhǔn)率相對(duì)較低。其主要原因?yàn)镚AGC算法在發(fā)現(xiàn)蛋白質(zhì)復(fù)合物時(shí)并未進(jìn)行后期的處理，即將所聚類的簇都看作是蛋白質(zhì)復(fù)合物，這樣就會(huì)導(dǎo)致算法產(chǎn)生的蛋白質(zhì)復(fù)合物數(shù)目偏大，從而精確率會(huì)低于其他算法。并且在其他3個(gè)指標(biāo)上，GAGC也與其他6種算法效果相當(dāng)。

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

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

本文提出了一種基于遺傳算法的蛋白質(zhì)復(fù)合物識(shí)別算法GAGC。為了擴(kuò)大算法的搜索空間，首先改進(jìn)了IPCA算法，產(chǎn)生初始種群；為了能夠?qū)⑦z傳算法的交叉操作運(yùn)用到復(fù)合物識(shí)別中，設(shè)計(jì)了基于重疊分?jǐn)?shù)OS的染色體對(duì)齊方式；然后通過(guò)設(shè)計(jì)交叉方式，擴(kuò)大簇形成的搜索空間，從而提高算法識(shí)別蛋白質(zhì)復(fù)合物的精度。該算法框架也可以擴(kuò)展到其他聚類算法，通過(guò)選擇合適的適應(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]郭茂祖,代啟國(guó),徐立秋,等.一種蛋白質(zhì)復(fù)合體模塊度函數(shù)及其識(shí)別算法[J].計(jì)算機(jī)研究與發(fā)展,2014,51(10):2178-2186.

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

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