李敏，王建新，劉彬彬，陳建二

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410083)

隨著人類基因組計(jì)劃和許多物種全基因組測(cè)序的完成，生命科學(xué)研究的重點(diǎn)逐漸從基因組學(xué)轉(zhuǎn)移到蛋白質(zhì)組學(xué)[1-2]。蛋白質(zhì)是一切生命活動(dòng)的物質(zhì)基礎(chǔ)[3]。但細(xì)胞中每個(gè)蛋白質(zhì)并不是孤立存在的，而是通過(guò)與其他蛋白質(zhì)相互作用形成大的蛋白質(zhì)復(fù)合物來(lái)行使其功能的[4]。1個(gè)生物體內(nèi)所有蛋白質(zhì)相互作用被稱為蛋白質(zhì)相互作用網(wǎng)絡(luò)(Protein interaction network)。從大規(guī)模相互作用網(wǎng)絡(luò)中識(shí)別蛋白質(zhì)復(fù)合物對(duì)預(yù)測(cè)蛋白質(zhì)功能、解釋特定的生物進(jìn)程具有重要作用。目前，出現(xiàn)了一些較有效的蛋白質(zhì)復(fù)合物識(shí)別算法，如：基于圖劃分的 RNSC算法[5]，基于密度的局部搜索算法MCODE[6]，基于邊介數(shù)的G-N算法[7]和在其基礎(chǔ)上改進(jìn)的 MoNet算法[8]等。雖然這些算法各有各的優(yōu)點(diǎn)，但都存在1個(gè)共同的缺點(diǎn)，就是不能識(shí)別交疊蛋白質(zhì)復(fù)合物(Overlapping protein complexes)。而在實(shí)際的蛋白質(zhì)相互作用網(wǎng)絡(luò)中，每個(gè)蛋白質(zhì)可能屬于多個(gè)蛋白質(zhì)復(fù)合物。例如，在CYGD數(shù)據(jù)庫(kù)[9]中由2 750個(gè)蛋白質(zhì)組成的復(fù)合物中蛋白質(zhì)的數(shù)量之和為8 932。所以，研究交疊蛋白質(zhì)復(fù)合物的識(shí)別算法具有實(shí)際意義。Palla等[10]研究了一種基于團(tuán)滲透的算法(Clique percolation method，CPM)，用來(lái)分析包括蛋白質(zhì)相互作用網(wǎng)絡(luò)在內(nèi)的復(fù)雜網(wǎng)絡(luò)的交疊和嵌套結(jié)構(gòu)。2006年，該團(tuán)隊(duì)開(kāi)發(fā)了基于 CPM 算法的復(fù)雜網(wǎng)絡(luò)分析工具 CFinder[11]，這是目前識(shí)別交疊蛋白質(zhì)復(fù)合物最有效的工具。但是，算法CPM的識(shí)別結(jié)果與參數(shù)k的取值密切相關(guān)，識(shí)別的蛋白質(zhì)復(fù)合物數(shù)量有限，特別是k取值比較大時(shí)能夠識(shí)別的蛋白質(zhì)復(fù)合物數(shù)量就更少，而當(dāng)k取值較小時(shí)，CPM算法通常會(huì)產(chǎn)生規(guī)模比較龐大的復(fù)合物，而這樣的復(fù)合物往往包含了規(guī)模遠(yuǎn)大于k的團(tuán)結(jié)構(gòu)和比較稀疏的k-團(tuán)鏈。在實(shí)際應(yīng)用中，更希望將這種復(fù)合物分割成多個(gè)比較稠密的子圖。為解決這一問(wèn)題，本文作者提出了1種基于極大團(tuán)擴(kuò)展的蛋白質(zhì)復(fù)合物識(shí)別算法(IPC-MCE)，將極大團(tuán)看作蛋白質(zhì)復(fù)合物的核，通過(guò)考查核的鄰居頂點(diǎn)與核內(nèi)頂點(diǎn)的作用概率決定鄰居頂點(diǎn)是否屬于該復(fù)合物。將算法應(yīng)用于酵母蛋白質(zhì)相互作用網(wǎng)絡(luò)。實(shí)驗(yàn)結(jié)果表明：算法 IPC-MCE能夠識(shí)別較多的具有生物意義的蛋白質(zhì)復(fù)合物，且對(duì)參數(shù)不敏感。

1 算法IPC-MCE

蛋白質(zhì)相互作用網(wǎng)絡(luò)可以被表示成為1個(gè)無(wú)向簡(jiǎn)單圖G=(V,E)，V和E分別為圖G的頂點(diǎn)集和邊集，圖G中的每個(gè)頂點(diǎn)表示1個(gè)蛋白質(zhì)，每條邊表示1對(duì)蛋白質(zhì)之間的相互作用。Palla等[10]提出的CPM算法將蛋白質(zhì)復(fù)合物看作圖中相互連通的若干k-團(tuán)集合。k-團(tuán)是指包含k個(gè)頂點(diǎn)的全連通圖。若2個(gè)k-團(tuán)有k-1個(gè)公共頂點(diǎn)，則稱這2個(gè)k-團(tuán)是鄰接的。一系列鄰接的k-團(tuán)組成1個(gè)k-團(tuán)鏈。若2個(gè)k-團(tuán)出現(xiàn)在1個(gè)k-團(tuán)鏈中，則稱這2個(gè)k-團(tuán)是連通的。CPM算法通過(guò)迭代遞歸得到圖中所有的k-團(tuán)，然后，建立這些團(tuán)的交疊矩陣，通過(guò)分析交疊矩陣得到各個(gè)連通的k-團(tuán)集合。顯然，k的取值越大，CPM算法得到的每個(gè)k-團(tuán)集合中所包含的k-團(tuán)個(gè)數(shù)就越少；相反，當(dāng)k取值很小時(shí)，則很容易形成巨大的k團(tuán)集合。鑒于此，本文提出了1種新的基于極大團(tuán)擴(kuò)展的蛋白質(zhì)復(fù)合物識(shí)別算法IPC-MCE。

與CPM算法不同，IPC-MCE算法將蛋白質(zhì)復(fù)合物看作1個(gè)以極大團(tuán)為核、其他頂點(diǎn)與核緊密相連的稠密子圖，并提出用作用概率來(lái)量化其他頂點(diǎn)與核連接的緊密程度，定義如下。

定義1 作用概率IPvk：頂點(diǎn)v與極大團(tuán)k的作用概率|表示極大團(tuán)的頂點(diǎn)數(shù)，|Evk|表示頂點(diǎn)v與極大團(tuán)k內(nèi)頂點(diǎn)之間存在的邊數(shù)。

算法IPC-MCE的描述如圖1所示。

圖1 IPC-MCE算法描述Fig.1 Description of IPC-MCE algorithm

算法 IPC-MCE的輸入是蛋白質(zhì)相互作用信息(PPI)。算法首先根據(jù)這些蛋白質(zhì)相互作用信息建立網(wǎng)絡(luò)圖G?？紤]到蛋白質(zhì)相互作用網(wǎng)絡(luò)中存在大量的度為1的頂點(diǎn)，而這些度為1的頂點(diǎn)只能構(gòu)成規(guī)模為2的極大團(tuán)，對(duì)其進(jìn)行擴(kuò)展只能生成以其鄰居頂點(diǎn)為中心的HUB結(jié)構(gòu)子圖。所以，IPC-MCE算法在枚舉圖中所有極大團(tuán)之前先對(duì)這些度為 1的頂點(diǎn)進(jìn)行預(yù)處理，在原圖G中刪除這些度為1的頂點(diǎn)及其連接的邊，并將這些1度頂點(diǎn)及對(duì)應(yīng)的鄰居頂點(diǎn)組成的HUB結(jié)構(gòu)子圖輸出。圖2給出了幾個(gè)HUB結(jié)構(gòu)子圖的實(shí)例。

圖2 蛋白質(zhì)相互作用網(wǎng)絡(luò)中的HUB結(jié)構(gòu)子圖實(shí)例Fig.2 Examples for subgraphs of protein interaction networks which have HUB structures

預(yù)處理后，IPC-MCE算法枚舉殘圖中所有的極大團(tuán)。采用Tsukiyama等[12]提出的基于深度優(yōu)先的極大團(tuán)枚舉算法，首先選擇圖中度最大的頂點(diǎn)，尋找其對(duì)應(yīng)的所有極大團(tuán)，然后選擇度次大的頂點(diǎn)，尋找其對(duì)應(yīng)的所有極大團(tuán)，依此類推。該極大團(tuán)枚舉算法可以通過(guò)橫向和縱向剪枝來(lái)提高算法效率，其時(shí)間復(fù)雜度為)(μnmΟ，其中：n為圖的頂點(diǎn)個(gè)數(shù)；m為圖邊數(shù)；μ為極大團(tuán)個(gè)數(shù)。

然后，根據(jù)定義1的作用概率IPvk，IPC-MCE算法對(duì)枚舉得到的所有極大團(tuán)進(jìn)行局部擴(kuò)展。考慮每個(gè)極大團(tuán)的一階鄰居頂點(diǎn)(即那些與極大團(tuán)內(nèi)的頂點(diǎn)有直接相互作用且不在極大團(tuán)內(nèi)的頂點(diǎn))，判斷這些鄰居頂點(diǎn)是否滿足IPvk≥t，將滿足條件的鄰居頂點(diǎn)擴(kuò)展進(jìn)來(lái)，得到擴(kuò)展后的稠密子圖。對(duì)擴(kuò)展得到的所有稠密子圖，過(guò)濾掉其中重復(fù)的稠密子圖，得到最終的稠密子圖集合DS并輸出，整個(gè)IPC-MCE算法運(yùn)行結(jié)束。

算法中步驟(1)的時(shí)間復(fù)雜度為 O(m)；步驟(2)的時(shí)間復(fù)雜度為O(n)；步驟(3)枚舉極大團(tuán)的時(shí)間復(fù)雜度為)(μnmΟ；步驟(4)極大團(tuán)擴(kuò)展的時(shí)間復(fù)雜度為Ο(nsμ)；步驟(5)的時(shí)間復(fù)雜度為Ο(μ2d2)。其中：μ為規(guī)模大于等于3的極大團(tuán)個(gè)數(shù)；s為最大的極大團(tuán)規(guī)模；d為最大的稠密子圖規(guī)模。

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

用C++語(yǔ)言實(shí)現(xiàn)IPC-MCE算法，從http://angel.elte.hu/clustering/下載基于CPM算法開(kāi)發(fā)的交疊蛋白質(zhì)復(fù)合物識(shí)別工具CFinder。這2個(gè)算法的測(cè)試是在1臺(tái)安裝了Windows XP Professional操作系統(tǒng)的工作站(Intel Pentium 1.73 GHz，內(nèi)存為512 MB)上進(jìn)行。

2.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)以酵母蛋白質(zhì)相互作用網(wǎng)絡(luò)作為研究對(duì)象，因?yàn)榻湍甘撬形锓N中蛋白質(zhì)相互作用數(shù)據(jù)最為完備的。實(shí)驗(yàn)所用的蛋白質(zhì)相互作用數(shù)據(jù)和用于評(píng)估的標(biāo)準(zhǔn)蛋白質(zhì)復(fù)合物數(shù)據(jù)集來(lái)源于MIPS數(shù)據(jù)庫(kù)[13]。在數(shù)據(jù)預(yù)處理階段，去除了蛋白質(zhì)相互作用網(wǎng)絡(luò)中自相互作用和冗余的相互作用，最終的相互作用網(wǎng)絡(luò)包括4 546個(gè)酵母蛋白質(zhì)和12 319對(duì)相互作用。將包含2個(gè)及以上蛋白質(zhì)的216個(gè)復(fù)合物作為標(biāo)準(zhǔn)復(fù)合物數(shù)據(jù)集。最小的復(fù)合物包括2個(gè)蛋白質(zhì)，最大的復(fù)合物包括81個(gè)蛋白質(zhì)，平均每個(gè)復(fù)合物包括6.31個(gè)蛋白質(zhì)。

2.2 性能評(píng)價(jià)

目前，對(duì)蛋白質(zhì)復(fù)合物識(shí)別算法的性能主要是從算法標(biāo)識(shí)已知復(fù)合物的能力，以及算法的敏感度和特異性這幾個(gè)方面進(jìn)行評(píng)價(jià)[6,11]。下面從這幾個(gè)方面對(duì)算法IPC-MCE和CFinder的性能進(jìn)行對(duì)比分析。

2.2.1 已知蛋白質(zhì)復(fù)合物被標(biāo)識(shí)的數(shù)量

算法識(shí)別的蛋白質(zhì)復(fù)合物（Predicted complexes,Pc）與已知蛋白質(zhì)復(fù)合物(Known complexes, Kc)的匹配程度OS(Pc, Kc)的計(jì)算公式[5,9-10]為：

其中：a和b分別表示Pc和Kc所包含的蛋白質(zhì)個(gè)數(shù)，i表示Pc和Kc中公共蛋白質(zhì)個(gè)數(shù)。

若 2個(gè)蛋白質(zhì)復(fù)合物的匹配程度 OS(Pc,Kc)超過(guò)給定的閾值，則稱這2個(gè)復(fù)合物匹配。對(duì)于標(biāo)準(zhǔn)復(fù)合物數(shù)據(jù)集中的已知復(fù)合物，若識(shí)別出的復(fù)合物與之匹配程度OS(Pc, Kc)超過(guò)給定閾值，則稱該已知復(fù)合物被標(biāo)識(shí)，若OS(Pc, Kc)=1，則稱該已知復(fù)合物被完全標(biāo)識(shí)。算法標(biāo)識(shí)的已知復(fù)合物數(shù)量越多，說(shuō)明算法識(shí)別復(fù)合物的能力越強(qiáng)。

圖 3描述了不同匹配閾值下已知復(fù)合物被 IPCMCE算法和CFinder標(biāo)識(shí)的數(shù)量。圖3中CFinder (k=3)和CFinder (k=4)分別表示CFinder在參數(shù)k為3和4時(shí)標(biāo)識(shí)的已知復(fù)合物數(shù)量；IPC-MCE(DS, t=*)表示算法IPC-MCE在參數(shù)t取不同值時(shí)輸出的稠密子圖標(biāo)識(shí)的已知復(fù)合物數(shù)量。IPC-MCE(HUB&DS, t=0.8)表示算法IPC-MCE在參數(shù)t=0.8時(shí)輸出的HUB結(jié)構(gòu)子圖和稠密子圖一起標(biāo)識(shí)的已知復(fù)合物數(shù)量。

圖3 不同匹配閾值下已知復(fù)合物被標(biāo)識(shí)的數(shù)量Fig.3 Number of matched known complexes with respect to different overlapping score thresholds

從圖3可以看出：在不同匹配程度閾值下，算法IPC-MCE在t=0.6，0.7，0.8和0.9時(shí)產(chǎn)生的稠密子圖結(jié)果數(shù)據(jù)集標(biāo)識(shí)的已知復(fù)合物數(shù)量相差不多，說(shuō)明算法的結(jié)果數(shù)據(jù)集對(duì)輸入的參數(shù)不敏感。

CFinder在k=3時(shí)標(biāo)識(shí)的已知復(fù)合物數(shù)量最大，隨著k增大，CFinder在不同匹配程度閾值下能夠標(biāo)識(shí)的已知復(fù)合物數(shù)量逐漸下降。這是因?yàn)殡S著k增大，基本的拓?fù)鋯卧猭-團(tuán)隨之減少，能夠識(shí)別的蛋白質(zhì)復(fù)合物數(shù)量也隨之減少。ZHANG等[14-15]利用 CFinder分析蛋白質(zhì)相互作用網(wǎng)絡(luò)也給出了相同的結(jié)論。在實(shí)驗(yàn)中，CFinder在k=3，4，5，6和7時(shí)識(shí)別出來(lái)的蛋白質(zhì)復(fù)合物數(shù)量分別為178，61，18，9和8。從圖3可以看出：算法 IPC-MCE標(biāo)識(shí)的已知復(fù)合物數(shù)量明顯高于Cfinder標(biāo)識(shí)的數(shù)量。此外，算法IPC-MCE預(yù)處理產(chǎn)生的 HUB結(jié)構(gòu)子圖對(duì)標(biāo)識(shí)已知復(fù)合物也有貢獻(xiàn)。幾乎所有 CFinder能夠識(shí)別的蛋白質(zhì)復(fù)合物IPC-MCE都能夠準(zhǔn)確地識(shí)別出來(lái)。圖4給出了幾個(gè)具體的實(shí)例。

圖4(a)中，算法IPC-MCE 在t=0.8時(shí)完全標(biāo)識(shí)的1個(gè)規(guī)模為10的蛋白質(zhì)復(fù)合物，CFinder在k=3時(shí)識(shí)別的與該已知復(fù)合物最佳匹配程度OS(Pc,Kc) =0.556。對(duì)圖4(a)中CFinder識(shí)別的復(fù)合物，算法IPC-MCE將其分割為幾個(gè)相互交疊的復(fù)合物。

圖4(b)中算法IPC-MCE 在t=0.8時(shí)識(shí)別的1個(gè)規(guī)模為 14的蛋白質(zhì)復(fù)合物與已知復(fù)合物的匹配程度OS(Pc, Kc)=0.875，CFinder在k=3時(shí)識(shí)別的所有復(fù)合物與該已知復(fù)合物匹配程度OS(Pc, Kc)＜0.1，在k=4時(shí)識(shí)別的復(fù)合物與該已知復(fù)合物最佳匹配程度OS(Pc,Kc) =0.583。這說(shuō)明CFinder識(shí)別的復(fù)合物的稠密程度與k的取值密切相關(guān)，隨著k增大，CFinder更容易識(shí)別比較稠密的復(fù)合物。

圖4(c)中算法IPC-MCE 在t=0.5時(shí)識(shí)別的1個(gè)規(guī)模為 7的蛋白質(zhì)復(fù)合物與已知復(fù)合物的匹配程度OS(Pc, Kc)= 0.735，CFinder在k=3時(shí)識(shí)別的與該已知復(fù)合物最佳匹配程度 OS(Pc, Kc)=0.643。這說(shuō)明：對(duì)于比較稀疏的復(fù)合物，算法IPC-MCE比CFinder更有效地識(shí)別。

為進(jìn)一步測(cè)試算法IPC-MCE和CFinder識(shí)別復(fù)合物的能力，將這2個(gè)算法識(shí)別的復(fù)合物與Gavin等[16-18]使用串聯(lián)親和純化和大規(guī)模質(zhì)譜分析等系統(tǒng)分析方法得到的復(fù)合物進(jìn)行對(duì)比分析。Gavin，Ho和 Krogan所得的數(shù)據(jù)集分別包含232，552和91個(gè)蛋白質(zhì)復(fù)合物。在判斷2個(gè)復(fù)合物是否匹配時(shí)，通常將匹配程度OS(Pc, Kc)的閾值設(shè)置為0.2[6]。圖5描述了MIPS等數(shù)據(jù)集中被算法IPC-MCE和CFinder識(shí)別的復(fù)合物所匹配(OS(Pc, Kc)≥0.2)的已知復(fù)合物數(shù)量。從圖5可以看出：算法IPC-MCE不僅能夠標(biāo)識(shí)出大量的MIPS數(shù)據(jù)庫(kù)中人工注釋的蛋白質(zhì)復(fù)合物，而且也能夠標(biāo)識(shí)出比較多的大規(guī)模系統(tǒng)分析得到的蛋白質(zhì)復(fù)合物，并且算法IPC-MCE在t=0.8時(shí)識(shí)別的復(fù)合物所匹配的4個(gè)數(shù)據(jù)集中復(fù)合物的數(shù)量遠(yuǎn)高于CFinder在k=3時(shí)識(shí)別的復(fù)合物所匹配的數(shù)量。這說(shuō)明：算法 IPC-MCE比CFinder 具有更強(qiáng)的蛋白質(zhì)復(fù)合物識(shí)別能力。

2.2.2 算法的特異性和敏感度

算法的特異性P和敏感度R是用來(lái)評(píng)估蛋白質(zhì)復(fù)合物識(shí)別算法的另外 2個(gè)重要指標(biāo)[6]。特異性是指算法識(shí)別的蛋白質(zhì)復(fù)合物中識(shí)別正確的部分所占比例，如式(2)所示；敏感度是指已知蛋白質(zhì)復(fù)合物中被算法識(shí)別出來(lái)的部分所占比例，如式(3)所示。式中：T (True positive)表示算法識(shí)別的復(fù)合物中與已知復(fù)合物匹配程度值OS(Pc, Kc)≥0.2的個(gè)數(shù)；F (False positive)等于識(shí)別的復(fù)合物總數(shù)減去T；N (False negative)表示已知復(fù)合物中沒(méi)有識(shí)別的復(fù)合物與之匹配程度OS(Pc, Kc)≥0.2的個(gè)數(shù)。

圖4 算法IPC-MCE和CFinder在參數(shù)不同取值下識(shí)別的復(fù)合物以及標(biāo)識(shí)出來(lái)的已知復(fù)合物Fig.4 Examples for protein complexes identified by IPC-MCE and CFiner and corresponding matched known complexes

圖5 OS(Pc, Kc)≥0.2時(shí)已知復(fù)合物被標(biāo)識(shí)的數(shù)量Fig.5 Number of matched known complexes with respect to OS(Pc, Kc)≥0.2

Li等[19]綜合考慮敏感度和特異性2個(gè)方面，提出綜合評(píng)價(jià)指標(biāo)f，其計(jì)算公式[19]如下：

算法IPC-MCE和CFinder的特異性P、敏感度R和綜合評(píng)價(jià)f的比較結(jié)果如表1所示。

從表1可以看出：算法IPC-MCE在t=0.6，0.7，0.8和0.9時(shí)識(shí)別的復(fù)合物的敏感度在0.8以上，說(shuō)明識(shí)別出來(lái)的復(fù)合物與已知復(fù)合物匹配閾值大于等于0.2的數(shù)量(T)遠(yuǎn)高于已知復(fù)合物在該閾值下沒(méi)有被標(biāo)識(shí)的數(shù)量(N)，前者是后者的4倍多。T越大，N越小，敏感度就越高，說(shuō)明算法識(shí)別出來(lái)的復(fù)合物可靠性越高。CFinder的敏感度最高只有0.213 6。算法IPC-MCE在t=0.6，0.7，0.8和0.9時(shí)識(shí)別的復(fù)合物的特異性大于0.23，而CFinder的特異性都大于0.24，明顯高于算法IPC-MCE的特異性。雖然CFinder的特異性高于IPC-MCE的特異性，但CFinder識(shí)別的復(fù)合物中與已知復(fù)合物匹配的數(shù)量(T)卻遠(yuǎn)小于 IPC-MCE匹配的數(shù)量。此外，由于目前試驗(yàn)測(cè)定的已知蛋白質(zhì)復(fù)合物數(shù)據(jù)不完整，算法識(shí)別的蛋白質(zhì)復(fù)合物中可能存在一定比例的復(fù)合物還未被試驗(yàn)測(cè)定但是真實(shí)存在。從2個(gè)算法的綜合評(píng)價(jià)指標(biāo)f可以看出：算法IPC-MCE的f值要遠(yuǎn)高于Cfinder的f值，說(shuō)明算法IPC-MCE在識(shí)別蛋白質(zhì)復(fù)合物方面比CFinder的性能好。

表1 算法 IPC-MCE與CFinder的敏感度R、特異性P和綜合評(píng)價(jià)f的比較結(jié)果Table 1 Comparison of IPC-MCE and CFinder under Sensitivity, Specificity, and f-measure

2.3 功能富集分析

很多研究者根據(jù)超幾何聚集分布的 P-value來(lái)注釋識(shí)別復(fù)合物的主要功能，其計(jì)算式[8]如下：

其中：n1和n2分別表示識(shí)別的復(fù)合物和功能注釋復(fù)合物的規(guī)模；i表示他們交集的規(guī)模；N表示網(wǎng)絡(luò)的規(guī)模。

P-value 體現(xiàn)了識(shí)別復(fù)合物中蛋白質(zhì)功能富集的概率。一般，將 P-value的最小值對(duì)應(yīng)的功能作為該復(fù)合物的主要功能。但很多蛋白質(zhì)復(fù)合物的注釋功能至少對(duì)應(yīng)于2種功能類。這里，采取文獻(xiàn)[5, 14]中所用的Pol計(jì)算方法，通過(guò)最小化識(shí)別復(fù)合物與功能注釋復(fù)合物的隨機(jī)交疊概率來(lái)獲得識(shí)別復(fù)合物的最佳匹配功能注釋復(fù)合物：

其中：n1和n2分別表示識(shí)別的復(fù)合物和功能注釋復(fù)合物的規(guī)模；i表示他們交集的規(guī)模；N表示網(wǎng)絡(luò)的規(guī)模。

將IPC-MCE算法在t=0.8時(shí)識(shí)別的規(guī)模大于5的442個(gè)蛋白質(zhì)復(fù)合物與功能注釋復(fù)合物進(jìn)行比較，計(jì)算Pol，發(fā)現(xiàn)超過(guò)98.4%的Pol小于0.01，其中約86.2%的Pol小于0.001，超過(guò)72.6%的Pol更小，小于1×10-10。CFinder在k=3時(shí)識(shí)別的規(guī)模大于5的蛋白質(zhì)復(fù)合物只有 29個(gè)，Pol小于 0.01的占 93.1%，而 Pol小于1×10-10的僅有16個(gè)，占55.2%。上述分析說(shuō)明算法IPC-MCE識(shí)別的蛋白質(zhì)復(fù)合物不僅從統(tǒng)計(jì)上證明是具有生物意義的，并且較 CFidner具有更強(qiáng)的生物意義。

3 結(jié)論

(1) 與交疊蛋白質(zhì)復(fù)合物識(shí)別工具 CFinder的識(shí)別結(jié)果比較，提出的 IPC-MCE算法在相同條件下能夠更精確地標(biāo)識(shí)已知蛋白質(zhì)復(fù)合物。在最優(yōu)參數(shù)設(shè)置下，IPC-MCE算法標(biāo)識(shí)的已知蛋白質(zhì)復(fù)合物數(shù)量是CFinder標(biāo)識(shí)的已知蛋白質(zhì)復(fù)合物數(shù)量的2倍多，說(shuō)明算法IPC-MCE具有更好的識(shí)別性能。

(2) 基于Pol的統(tǒng)計(jì)分析表明：算法IPC-MCE能夠識(shí)別出蛋白質(zhì)網(wǎng)絡(luò)中具有生物意義的蛋白質(zhì)復(fù)合物。統(tǒng)計(jì)分析規(guī)模大于5的蛋白質(zhì)復(fù)合物的Pol發(fā)現(xiàn)，98.4%的Pol小于0.01。

(3) 算法IPC-MCE不需要其他任何輔助信息，簡(jiǎn)單有效，且對(duì)輸入?yún)?shù)不敏感，能夠?yàn)榈鞍踪|(zhì)復(fù)合物識(shí)別和蛋白質(zhì)功能預(yù)測(cè)提供有益的參考。

[1] Graves P R, Haystead T A. Molecular biologist’s guide to proteomics[J]. Microbiol Mol Biol Rev, 2002, 66(1): 39-63.

[2] 向亞莉, 易紅, 李萃, 等. 鼻咽癌細(xì)胞系5-8F和6-10B的差異蛋白質(zhì)組學(xué)研究[J]. 中南大學(xué)學(xué)報(bào): 醫(yī)學(xué)版, 2007, 32(6):978-984.XIANG Ya-li, YI Hong, LI Cui, et al. Differential proteomic analysis of naspharyngeal carcinoma cell lines 5-8F and 6-10B[J]. Journal of Central South University: Medicine Science,2007, 32(6): 978-984.

[3] CHENG Yun-hui, WANG Zhang, XU Shi-ying. Antioxidant properties of wheat germ protein hydrolysates evaluated in vitro[J]. Journal of Central South University of Technology,2006, 13(2): 160-165.

[4] Gavin A C, Superti-Furga G. Protein complexes and proteome organization from yeast to man[J]. Curr Opin Chem Biol, 2003,7(1): 21-27.

[5] King A D, Pr?ulj N, Jurisica I. Protein complex prediction via cost-based clustering[J]. Bioinformatics, 2004, 20(17):3013-3020.

[6] Bader G D, Hogue C W. An automated method for finding molecular complexes in large protein interaction networks[J].BMC Bioinformatics, 2003, 4: 2.

[7] Girvan M, Newman M. Community structure in social and biological networks[J]. PNAS, 2002, 99: 7821-7826.

[8] LUO Feng, YANG Yue-feng, CHEN Chin-fu, et al. Modular organization of protein interaction networks[J]. Bioinformatics,2007, 23(2): 207-214.

[9] Güldener U, Münsterk?tter M, Kastenmüller G, et al. CYGD: the comprehensive yeast genome database[J]. Nucleic Acids Res,2005, 33: D364-D368.

[10] Palla G, Dernyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.

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

[12] Tsukiyama S, Ide M, Ariyoshi H, et al. A new algorithm for generating all the maximal independent sets[J]. SIAM Journal on Computing, 1977, 6(3): 505-517.

[13] Mewes H W. MIPS: analysis and annotation of proteins from whole genome in 2005[J]. Nucleic Acid Research, 2006, 34:169-172.

[14] ZHANG Shi-hua, NING Xue-mei, ZHANG Xing-sun.Identification of functional modules in a PPI network by clique percolation clustering[J]. Computational Biology and Chemistry.2006, 30(6): 445-451.

[15] Jonsson P, Cavanna T, Zicha D, et al. Cluster analysis of networks generated through homology: Automatic identification of important protein communities involved in cancer metastasis[J]. BMC Bioinformatics, 2006, 7: 2.

[16] Gavin A C, Bosche M, Krause R, et al. Functional organization of the yeast proteome by systematic analysis of protein complexes[J]. Nature, 2002, 415: 141-147.

[17] Ho Y, Gruhler A, Heilbut A, et al. Systematic identification of protein complexes in saccharomyces cerevisiae by mass spectrometry[J]. Nature, 2002, 415: 180-183.

[18] Krogan N J, Peng N J, Cagney G, et al. High-definition macromolecular composition of yeast RNA- processing complexes[J]. Molecular Cell, 2004, 13: 225-239.

[19] Li X L, Tan S H, Foo C S, et al. Interaction graph mining for protein complexes using local clique merging[J]. Genome Informatics, 2005, 16(2): 260-269.