一種新的圖劃分算法在PPI網(wǎng)絡(luò)模塊化中的研究

王曉芳，賈宗維

（1．晉中師范高等專科學(xué)校，山西 晉中030600；2．山西農(nóng)業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，山西 太谷030801）

隨著高通量生物蛋白質(zhì)交互作用網(wǎng)絡(luò)信息數(shù)據(jù)的不斷擴大，越來越多的研究人員投身到預(yù)測蛋白質(zhì)相互作用和蛋白質(zhì)功能這一新興的研究領(lǐng)域。眾多研究表明，細胞中的蛋白質(zhì)并不是孤立行動，而是通過彼此間的相互作用來實現(xiàn)特定的生物功能。蛋白質(zhì)間的相互作用不僅關(guān)系到生物體的新陳代謝同時也是探究許多疾病病因的關(guān)鍵所在。因此，對蛋白質(zhì)交互網(wǎng)絡(luò)的研究對于蛋白質(zhì)未知功能的預(yù)測以及了解細胞機制的結(jié)構(gòu)有著十分重要的科學(xué)研究意義［1］。從高通量的生物蛋白質(zhì)交互網(wǎng)絡(luò)中通過聚類研究提取功能模塊，有助于了解蛋白質(zhì)相互作用機理和對未知蛋白質(zhì)功能的預(yù)測。

近年來，酵母雙雜交技術(shù)［2］、質(zhì)譜分析技術(shù)［3］、蛋白質(zhì)芯片技術(shù)［4］的發(fā)展和應(yīng)用，使得高速增長的蛋白質(zhì)相互作用數(shù)據(jù)可用于進一步分析研究。研究人員提出了許多蛋白質(zhì)相互作用網(wǎng)絡(luò)的聚類算法，用以分析蛋白質(zhì)功能模塊和預(yù)測未知蛋白質(zhì)功能。它們大致分為基于層次聚類的方法、基于圖劃分和基于密度的局部搜索的聚類方法，如maximal clique方法［5］、RNSC方法［6］、MCODE方法［7］。本文在深入分析蛋白質(zhì)網(wǎng)絡(luò)的拓撲屬性和蛋白質(zhì)節(jié)點間的相互關(guān)系后，提出了一種基于蛋白質(zhì)節(jié)點相似性的度量準則，以最優(yōu)化模塊度為目標函數(shù)的圖聚類算法，用來發(fā)現(xiàn)蛋白質(zhì)交互網(wǎng)絡(luò)中的功能模塊，實驗結(jié)果表明所探測的功能模塊內(nèi)部的確是密集連接的。

1 數(shù)據(jù)及網(wǎng)絡(luò)構(gòu)建

1．1 數(shù)據(jù)來源

數(shù)據(jù)取自 Uetz等人［8］利用all－by－all篩選的技術(shù)在蛋白質(zhì)組級別構(gòu)建網(wǎng)絡(luò)，“Ito－core”網(wǎng)絡(luò)［9］及Yu等人［10］實驗建立的一個高可信度的蛋白交互網(wǎng)絡(luò)。以此3個實驗數(shù)據(jù)集來驗證算法所發(fā)現(xiàn)的蛋白功能模塊劃分的效果。

1．2 網(wǎng)絡(luò)構(gòu)建

用無向無權(quán)圖 描述蛋白質(zhì)相互作用網(wǎng)絡(luò)，即G＝（V，E），其中V表示圖中節(jié)點的集合，E表示圖中邊的集合。蛋白質(zhì)網(wǎng)絡(luò)中每個蛋白質(zhì)對應(yīng)圖中的一個節(jié)點，每條蛋白質(zhì)間的相互作用對應(yīng)圖中的一條邊。由此可以構(gòu)造蛋白質(zhì)網(wǎng)絡(luò)關(guān)聯(lián)圖的鄰接矩陣A，即

2 圖劃分聚類算法描述

蛋白質(zhì)交互網(wǎng)絡(luò)中的蛋白功能模塊可以看作是構(gòu)成完全圖的各連通子圖，探測功能模塊的方法可以通過挖掘連通子圖的圖聚類方法。本文算法通過分析圖中節(jié)點間的相互關(guān)系和節(jié)點間的最短路徑數(shù)定義了節(jié)點間的相似性度量函數(shù)，利用模塊度作為最優(yōu)化聚類目標函數(shù)，逐層聚類直至最優(yōu)解終止。

2．1 節(jié)點相似度定義

從圖中的某一個節(jié)點出發(fā)去逐層遍訪其余節(jié)點，同等時間內(nèi)不同的節(jié)點訪問的范圍不盡相同。若兩節(jié)點相似性較強，則遍訪的范圍基本一致，反之則差別太大。由此可見，兩節(jié)點是否相似，與其周圍的節(jié)點有很大關(guān)系。即兩節(jié)點若關(guān)聯(lián)的交集節(jié)點越多，則兩節(jié)點就越相似。因此，可以用如下描述來定義兩節(jié)點間的相似性度量準則。

假設(shè)蛋白質(zhì)網(wǎng)絡(luò)對應(yīng)的圖G是一個具有n各節(jié)點的無向無權(quán)圖。則節(jié)點ti和tj間的相似性定義為：

其中，tik表示從節(jié)點ti到達tk所要經(jīng)過的最短步數(shù)（邊數(shù)），由式1可獲得圖G中節(jié)點所對應(yīng)的相似度矩陣S。

2．2 目標函數(shù)定義

模塊度是用以衡量網(wǎng)絡(luò)劃分質(zhì)量好壞的目標函數(shù)，當(dāng)一個劃分越接近真實劃分時目標函數(shù)的值就越大，反之則越小。我們的算法就是通過對蛋白質(zhì)交互網(wǎng)絡(luò)進行層次聚類，同時計算目標函數(shù)值，選取目標函數(shù)值最大時的劃分為最優(yōu)解。目標函數(shù)為：

式中，K代表劃分所得的功能模塊數(shù)，E（Vc，Vc）表示模塊C內(nèi)部蛋白質(zhì)相互作用邊數(shù)，E（Vc，V）表示網(wǎng)絡(luò)中與模塊C中蛋白質(zhì)有作用的邊數(shù)，E（V，V）表示網(wǎng)絡(luò)中的蛋白質(zhì)相互作用總邊數(shù)。

2．3 算法描述

將蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理后，得到蛋白質(zhì)的數(shù)目及蛋白質(zhì)間的相互作用情況。算法描述如下：

1）通過蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)，構(gòu)建蛋白質(zhì)網(wǎng)絡(luò)對應(yīng)圖鄰接矩陣；

2）計算圖中各節(jié)點對間的相似性值，建立相似度度量矩陣；

3）初始化網(wǎng)絡(luò)為n個社團，即每個節(jié)點為一個社團；

4）合并圖中目前相似性最大的節(jié)點對，并計算合并后的目標函數(shù)值；

5）重復(fù)執(zhí)行步驟4，不斷合并節(jié)點，直到整個網(wǎng)絡(luò)合并為一個大社團。

算法中，目標函數(shù)的值并不隨模塊數(shù)的減少成反比，算法終止后，選取目標函數(shù)值最大時為最優(yōu)，此時獲得蛋白質(zhì)網(wǎng)絡(luò)模塊功能劃分為最優(yōu)劃分。

3 實驗及分析

將算法應(yīng)用于3個數(shù)據(jù)集構(gòu)建的無向圖。算法分別獲得了0．68、0．75、0．64的目標函數(shù)最大值，模塊劃分效果較好，同時產(chǎn)生的若干功能模塊則有待進一步的研究確認，這些高密度的功能模塊能否正確的預(yù)測未知蛋白的功能還是未知數(shù)。但所發(fā)現(xiàn)的功能模塊內(nèi)部是密集連接的，說明模塊內(nèi)部很有可能存在許多蛋白復(fù)合物，許多信息都有待進一步挖掘。

對于實驗組所發(fā)現(xiàn)的蛋白質(zhì)功能模塊，能否作為下一步研究中的蛋白功能預(yù)測候選模塊，還需進一步驗證各蛋白功能模塊內(nèi)部蛋白質(zhì)相互作用密度是否符合要求。

定義蛋白相互作用密度函數(shù)來評價這些模塊是否是內(nèi)部密集連接。該指標描述如下：

子圖B?G，B包含節(jié)點i。對于B而言，節(jié)點i度數(shù)分內(nèi)外兩部分，即ki＝k（in）i（B）＋k（out）i（B），即則

表1 各蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)實驗結(jié)果Table 1 Experimental results of three data sets

通過對眾多發(fā)現(xiàn)的子圖密度計算得知，子圖的連接密度大部分位于0．5～0．8之間，可見這些子圖是完全可以作為下一步蛋白功能預(yù)測研究的可靠數(shù)據(jù)。

4 結(jié)語

采用節(jié)點相似度的圖劃分聚類算法，分析了3個蛋白質(zhì)交互作用網(wǎng)絡(luò)，對聚類得到的子圖劃分進行模塊度函數(shù)的檢測和單獨模塊的密度驗證。研究表明，得到的功能模塊劃分的確是內(nèi)部緊密連接的，能夠作為蛋白質(zhì)交互作用網(wǎng)絡(luò)分析中功能預(yù)測的候選模塊，從中挖掘相關(guān)的蛋白功能信息是下一步研究的重要任務(wù)。

［1］Yang Bo，Liu Dayou，Lin Jiming，et al．Complex network clustering algorithms［J］．Journal of Software，2009，20（1）：54－66．

［2］Fields S，Song O．A novel genetic system to detect protein－protein interactions［J］．Nature，1989，340（6230）：245－246．

［3］Ho Y，Gruhler A，Heilbut A，et al．Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry［J］．Nature，2002．415（6868）：180－183．

［4］Zhu H，Bilgin M，Bangham R，et al．Global analysis of protein activities using proteome chips［J］．Science，2001，293（5537）：2101－2105．

［5］梅娟，王正祥，石貴陽，等．復(fù)雜生物網(wǎng)絡(luò)分析的圖聚類方法研究進展［J］．食品與生物技術(shù)學(xué)報，2008，27（5）：15－20．

［6］King AD，Przulj N，Jurisica I．Protein complex prediction via cost－based clustering［J］．Bioinformatics，2004，20（17）：3013－3020．

［7］Bader GD，Hogue CW．An automated method for finding molecular complexes in large protein interaction networks［J］．BMC Bioinformatics，2003，4：2．

［8］Uetz P．A comprehensive analysis of protein－protein interactions in Saccharomyces cerevisiae［J］．Nature，2000，403（6770）：623－627．

［9］Ito T．A comprehensive two－h(huán)ybrid analysis to explore the yeast protein interactome［J］．Proc Natl Acad Sci，2001，98（8）：4569－4574．

［10］Yu H．High－quality binary protein interaction map of the yeast interactome network［J］．Science，2008，322（5898）：104－110．