毛伊敏 劉銀萍 梁田 毛丁慧

摘 要：針對譜聚類融合模糊C-means（FCM）聚類的蛋白質(zhì)相互作用（PPI）網(wǎng)絡(luò)功能模塊挖掘方法準(zhǔn)確率不高、執(zhí)行效率較低和易受假陽性影響的問題，提出一種基于模糊譜聚類的不確定PPI網(wǎng)絡(luò)功能模塊挖掘（FSC-FM）方法。首先，構(gòu)建一個不確定PPI網(wǎng)絡(luò)模型，使用邊聚集系數(shù)給每一條蛋白質(zhì)交互作用賦予一個存在概率測度，克服假陽性對實驗結(jié)果的影響;

第二，利用基于邊聚集系數(shù)流行距離（FEC）策略改進譜聚類中的相似度計算，解決譜聚類算法對尺度參數(shù)敏感的問題，進而利用譜聚類算法對不確定PPI網(wǎng)絡(luò)數(shù)據(jù)進行預(yù)處理，降低數(shù)據(jù)的維數(shù)，提高聚類的準(zhǔn)確率;第三，設(shè)計基于密度的概率中心選取策略（DPCS）解決模糊C-means算法對初始聚類中心和聚類數(shù)目敏感的問題，并對預(yù)處理后的PPI數(shù)據(jù)進行FCM聚類，提高聚類的執(zhí)行效率以及靈敏度;最后，采用改進的邊期望稠密度（EED）對挖掘出的蛋白質(zhì)功能模塊進行過濾。在酵母菌DIP數(shù)據(jù)集上運行各個算法可知，F(xiàn)SC-FM與基于不確定圖模型的檢測蛋白質(zhì)復(fù)合物（DCU）算法相比，F(xiàn)-measure值提高了27.92%，執(zhí)行效率提高了27.92%;與在動態(tài)蛋白質(zhì)相互作用網(wǎng)絡(luò)中識別復(fù)合物的方法（CDUN）、演化算法（EA）、醫(yī)學(xué)基因或蛋白質(zhì)預(yù)測算法（MGPPA）相比也有更高的F-measure值和執(zhí)行效率。實驗結(jié)果表明，在不確定PPI網(wǎng)絡(luò)中，F(xiàn)SC-FM適合用于功能模塊的挖掘。

關(guān)鍵詞：不確定數(shù)據(jù);蛋白質(zhì)相互作用;譜聚類算法;模糊C-means;功能模塊;期望稠密度

中圖分類號：TP399

文獻標(biāo)志碼：A

文章編號：1001-9081（2019）04-1032-09

Abstract： Aiming at the problem that Protein-Protein Interaction （PPI） network functional module mining method based on spectral clustering and Fuzzy C-Means （FCM） clustering has low accuracy and low running efficiency， and is susceptible to false positive， a method for Functional Module mining in uncertain PPI network based on Fuzzy Spectral Clustering （FSC-FM） was proposed. Firstly， in order to overcome the effect of false positives， an uncertain PPI network was constructed， in which every protein-protein interaction was endowed with a existence probability measure by using edge aggregation coefficient. Secondly， based on edge aggregation coefficient and flow distance， the similarity calculation of spectral clustering was modified using Flow distance of Edge Clustering coefficient （FEC） strategy to overcome the sensitivity problem of the spectral clustering to the scaling parameters. Then the spectral clustering algorithm was used to preprocess the uncertain PPI network data， reducing the dimension of the data and improving the accuracy of clustering. Thirdly， Density-based Probability Center Selection （DPCS） strategy was designed to solve the problem that FCM algorithm was sensitive to the initial cluster center and clustering numbers， and the processed PPI data was clustered by using FCM algorithm to improve the running efficiency and sensitivity of the clustering. Finally， the mined functional module was filtered by Edge-Expected Density （EED） strategy. Experiments on yeast DIP dataset show that， compared with Detecting protein Complexes based on Uncertain graph model ?（DCU） algorithm， FSC-FM has F-measure increased by 27.92%， running efficiency increased by 27.92%; compared with an uncertain model-based approach for identifying Dynamic protein Complexes in Uncertain protein-protein interaction Networks （CDUN）， Evolutionary Algorithm （EA） and Medical Gene or Protein Prediction Algorithm （MGPPA）， FSC-FM also has higher F-measure and running efficiency. The experimental results show that FSC-FM is suitable for the functional module mining in the uncertain PPI network.

Key words： uncertain data; Protein-Protein Interaction （PPI）; spectral clustering algorithm; Fuzzy C-Means （FCM）; functional module;expected density

0?引言

蛋白質(zhì)組是一個在空間和時間上動態(tài)變化的整體，其功能往往通過蛋白質(zhì)之間或核酸之間的相互作用而表現(xiàn)出來，這種相互作用存在于機體細胞的生命活動過程中，相互交叉形成蛋白質(zhì)相互作用（Protein-Protein Interaction， PPI）網(wǎng)絡(luò)[1]。在一個PPI網(wǎng)絡(luò)中，不同時間和空間階段通過相互作用完成某一特定分子進程的蛋白質(zhì)集合稱為蛋白質(zhì)功能模塊[2]。大量的生物實驗和計算方法實驗產(chǎn)生了大量的蛋白質(zhì)間相互作用數(shù)據(jù)，這些數(shù)據(jù)是挖掘蛋白質(zhì)功能模塊的基石，而功能模塊對于了解細胞的功能組織結(jié)構(gòu)、執(zhí)行生理功能方面又是至關(guān)重要的[3]，因此，挖掘蛋白質(zhì)相互作用的功能模塊具有重要的意義。

迄今為止，利用計算方法進行蛋白質(zhì)功能模塊挖掘已經(jīng)是后基因組時代生物信息學(xué)領(lǐng)域中一個非常活躍的研究領(lǐng)域[4]。

根據(jù)計算機制的不同，挖掘蛋白質(zhì)功能模塊的算法大體分為：基于密度的聚類方法[5-6]、基于層次的聚類方法[7-8]、基于劃分的聚類方法[9-10]和基于譜分析的聚類方法等。其中：基于密度的聚類方法很難對網(wǎng)絡(luò)中大量的稀疏節(jié)點進行聚類，算法挖掘的功能模塊的準(zhǔn)確率不高;基于層次的聚類方法難以檢測出節(jié)點交疊的功能模塊，聚類結(jié)果對網(wǎng)絡(luò)的噪聲非常敏感;基于劃分的聚類方法需要事先確定聚類數(shù)目，不能檢測出重疊的功能模塊;而基于圖論的譜聚類算法實現(xiàn)簡單，不局限于原始數(shù)據(jù)的分布形狀，可以收斂于全局最優(yōu)解[11]，因此，目前譜聚類算法已成功應(yīng)用于PPI網(wǎng)絡(luò)功能模塊挖掘，成為該領(lǐng)域的研究熱點。

Madani等[12]提出了一種新的基于譜聚類的功能模塊挖掘算法，用于挖掘整個PPI網(wǎng)絡(luò)最相似的功能模塊。Qin等[13]利用譜聚類方法對PPI網(wǎng)絡(luò)模塊識別進行了研究，提出一種基于PPI網(wǎng)絡(luò)屬性確定模塊數(shù)的方法，并且進行了相關(guān)驗證。Inoue等[14]提出了一種可調(diào)擴散矩陣譜聚類（Adjustable Diffusion Matrix-based Spectral Clustering， ADMSC）方法，該方法用于PPI網(wǎng)絡(luò)模塊劃分挖掘。這些算法根據(jù)譜聚類算法中的特征向量將數(shù)據(jù)劃分到不相交的類中，屬于且僅屬于一個類，可以自動確定聚類數(shù)目，是一種硬劃分方法，不能準(zhǔn)確反映樣本間的實際關(guān)系;另計算相似度矩陣時，實驗結(jié)果容易受到尺度參數(shù)的影響，導(dǎo)致功能模塊挖掘過程中不能充分考慮節(jié)點的局部一致性和全局一致性，進而使得算法的運行效率降低以及準(zhǔn)確性不高。為了解決譜聚類算法的硬劃分問題，文獻[15-16]提出將模糊C-means（Fuzzy C-Means， FCM）與譜聚類算法相結(jié)合用于蛋白質(zhì)模塊挖掘，利用FCM算法中的模糊因子改進譜聚類的硬劃分問題，不斷更新聚類中心隸屬度來劃分簇;但劃分結(jié)果存在對初始聚類中心以及聚類數(shù)目敏感的問題，導(dǎo)致功能模塊挖掘的過程中容易陷入局部最優(yōu)，算法的預(yù)測精度降低以及特異性和靈敏度不高。然而上述研究都是將PPI網(wǎng)絡(luò)有效地用無向圖模型來描述，只關(guān)注于精確的、完全的確定圖，忽略了生物信息學(xué)中的PPI網(wǎng)絡(luò)數(shù)據(jù)以及其他的一些生物數(shù)據(jù)常常會由于實驗檢測方法的局限性而呈現(xiàn)出不確定性[17]，實驗結(jié)果容易受到假陽性的影響，因此，將PPI網(wǎng)絡(luò)作為不確定圖來研究更為合理。

目前從不確定性的數(shù)據(jù)中挖掘蛋白質(zhì)功能模塊信息越來越受到人們的關(guān)注?；诓淮_定模型，Zhang等[18]提出了一種在動態(tài)蛋白質(zhì)相互作用網(wǎng)絡(luò)中識別復(fù)合物的方法（an uncertain model-based approach for identifying Dynamic protein Complexes in Uncertain protein-protein interaction Networks， CDUN）用于識別蛋白質(zhì)功能模塊;Zhao等[19]提出了一種基于不確定圖模型的檢測蛋白質(zhì)復(fù)合物（Detecting protein Complexes based on Uncertain graph model， DCU）算法;Halim等[20]提出了一種從不確定蛋白質(zhì)網(wǎng)絡(luò)概率圖中聚類子圖模塊的演化算法（Evolutionary Algorithm， EA）;Bano等[21]在不確定數(shù)據(jù)基礎(chǔ)上提出了醫(yī)學(xué)基因或蛋白質(zhì)預(yù)測算法（Medical Gene or Protein Prediction Algorithm， MGPPA）應(yīng)用于蛋白質(zhì)簇的挖掘。這些方法克服了假陽性對實驗結(jié)果的影響，有很好的預(yù)測精度和很強的魯棒性，但是聚類結(jié)果的靈敏度和準(zhǔn)確率不高。雖然基于不確定PPI網(wǎng)絡(luò)的功能模塊挖掘取得了一定的成效，但是如何有效地構(gòu)建不確定PPI，如何克服譜聚類融合FCM算法對尺度參數(shù)、聚類中心和聚類數(shù)目敏感等導(dǎo)致的準(zhǔn)確率、靈敏度不高以及執(zhí)行效率低等缺陷，仍是亟待解決的問題。

針對以上問題，本文提出了基于模糊譜聚類的不確定PPI網(wǎng)絡(luò)功能模塊挖掘（Functional Module mining in uncertain PPI network based on Fuzzy Spectral Clustering， FSC-FM）方法。 本文主要工作為：1）利用邊聚集系數(shù)構(gòu)建不確定PPI網(wǎng)絡(luò);2）結(jié)合邊聚集系數(shù)和流行距離，提出了邊聚集系數(shù)流行距離（Flow distance of Edge Clustering coefficient， FEC）策略來計算蛋白質(zhì)節(jié)點之間的相似度矩陣，克服了譜聚類算法對尺度參數(shù)的敏感的缺陷;3）根據(jù)基于密度的概率中心優(yōu)化策略（Density-based Probability Center Selection， DPCS），優(yōu)化FCM算法對初始聚類中心的選取，降低離群數(shù)據(jù)對整個數(shù)據(jù)的影響，確定聚類數(shù)目，進而提高算法的運行效率;4）利用改進的邊期望稠密度（Edge-Expected Density， EED）度量來對挖掘出的模塊進行過濾。實驗結(jié)果表明本文方法收斂快、聚類精度高、運行效率高，聚類結(jié)果的準(zhǔn)確率以及靈敏度較高。

1?基本概念

由于PPI網(wǎng)絡(luò)可以模型化為一個圖，節(jié)點代表蛋白質(zhì)，邊代表蛋白質(zhì)之間的相互作用，因此，具有不確定性的PPI網(wǎng)絡(luò)可用不確定圖來表示，下面給出基本概念。

2?本文FSC-FM算法

2.1?模糊譜聚類算法

模糊譜聚類是將譜聚類與FCM算法融合在一起所得到的，其中譜聚類算法是建立在譜圖劃分理論基礎(chǔ)上，將數(shù)據(jù)點看成是一個無向圖G=（V，W）的頂點V，邊權(quán)重的集合W={Uij}表示基于高斯核函數(shù)度量的兩個數(shù)據(jù)點之間的相似度，U表示待聚類數(shù)據(jù)點間的相似度矩陣，其本質(zhì)是利用相似度矩陣的特征向量以及結(jié)合FCM完成聚類。劃分的準(zhǔn)則是：子圖內(nèi)的相關(guān)性最大，各個子圖間的相關(guān)性最小[28]。FCM算法[29]的基本思想是基于目標(biāo)函數(shù)的隸屬度矩陣來確定每個樣本與所有簇的關(guān)聯(lián)強度，不斷更新聚類中心和隸屬度將樣本劃分到與其關(guān)聯(lián)強度最大的簇中完成聚類。目前，大量研究者將模糊譜聚類應(yīng)用到蛋白質(zhì)網(wǎng)絡(luò)中，用于功能模塊挖掘[15]24，[16]112。由于蛋白質(zhì)相互作用網(wǎng)絡(luò)本身存在的不確定性，功能模塊挖掘容易受到假陽性的影響;譜聚類算法中的數(shù)據(jù)降維處理效率受到尺度參數(shù)影響較大以及FCM聚類結(jié)果受初始聚類中心、聚類數(shù)目敏感。為提高算法的執(zhí)行效率、準(zhǔn)確率、靈敏度以及避免假陽性的影響，本文提出了一種有效的挖掘蛋白質(zhì)功能模塊方法FSC-FM。FSC-FM方法包括：不確定PPI網(wǎng)絡(luò)的構(gòu)建、相似度改進的FEC策略、概率密度中心的DPCS策略和期望稠密度優(yōu)化的EED度量。

2.2?FSC-FM方法的優(yōu)化策略

2.2.1?不確定PPI網(wǎng)絡(luò)的構(gòu)建

由于受到實驗檢測條件的局限性以及蛋白質(zhì)網(wǎng)絡(luò)的拓?fù)涮匦?，蛋白質(zhì)相互作用網(wǎng)絡(luò)和生物信息學(xué)中的一些生物數(shù)據(jù)存在不確定性，實驗結(jié)果容易受到假陽性的影響。為了降低實驗結(jié)果受假陽性的影響，融合不確定數(shù)據(jù)處理技術(shù)提高PPI網(wǎng)絡(luò)功能模塊預(yù)測的準(zhǔn)確率，本文將PPI網(wǎng)絡(luò)用不確定圖來表示。通過計算PPI網(wǎng)絡(luò)圖中連接每條邊的兩個節(jié)點的公共鄰居節(jié)點數(shù)以及選取這兩個節(jié)點度的最小值，利用邊聚集系數(shù)定義公式來測度每一組相互作用，構(gòu)建不確定PPI網(wǎng)絡(luò)。圖1描述了如何將一個PPI網(wǎng)絡(luò)構(gòu)建成一個不確定網(wǎng)絡(luò)，其中：圖1（a）給出包含8個蛋白質(zhì)和18個蛋白質(zhì)間相互作用;圖1（b）是構(gòu)造的不確定網(wǎng)絡(luò)，每一個相互作用的測度通過邊聚集系數(shù)計算得到。構(gòu)造的不確定網(wǎng)絡(luò)由218個可能的實例網(wǎng)絡(luò)組成。

2.2.2?相似度改進的FEC策略

針對譜聚類算法采用傳統(tǒng)的高斯核函數(shù)來度量蛋白質(zhì)節(jié)點間的相似性，僅僅能反映聚類結(jié)構(gòu)的局部一致性特征，而且構(gòu)造相似度矩陣時對尺度參數(shù)比較敏感，計算復(fù)雜度較高，導(dǎo)致執(zhí)行效率和準(zhǔn)確率降低。為了解決這問題，在不確定PPI網(wǎng)絡(luò)中，根據(jù)蛋白質(zhì)網(wǎng)絡(luò)的拓?fù)涮匦约淳奂潭纫约傲餍芯嚯x來改進相似性度量，提出了FEC策略。

因此式（5）滿足度量空間定義的基本條件，是距離度量公式。

2.2.3?概率密度中心的DPCS策略

針對FCM算法融合譜聚類用于蛋白質(zhì)功能模塊的挖掘，利用FCM算法中的模糊因子改進譜聚類算法的硬劃分問題，不斷更新聚類中心以及隸屬度來劃分簇，劃分結(jié)果卻存在對初始聚類中心以及聚類數(shù)目敏感的問題。若初始聚類中心選擇存在偏差，可能會導(dǎo)致聚類結(jié)果與實際情況存在較大差異，挖掘功能模塊容易陷入局部最優(yōu)解，算法的精度以及準(zhǔn)確率降低。本文通過計算樣本數(shù)據(jù)間的幾何分布緊密程度得到相應(yīng)的密度中心，并將得到的樣本數(shù)據(jù)密度中心代入FSC-FM算法近似模擬全體數(shù)據(jù)的初始聚類中心，對使用FEC策略的譜聚類算法預(yù)處理后的數(shù)據(jù)實現(xiàn)蛋白質(zhì)功能模塊的挖掘。該方法可以避免FCM算法陷入局部最優(yōu)并且減少算法迭代次數(shù)，能夠提高算法的運行效率和精度。DPCS策略算法思想如下：

由式（8）可看出，距離聚類中心點越近，對應(yīng)的概率更新值就越小。當(dāng)D*c<δD*1迭代停止，這樣可以得到K個全局密度較大的數(shù)據(jù)點作為聚類的初始聚類中心，利用FCM聚類算法進行功能模塊挖掘。如此過程，高密度樣本而非邊緣離群點處于類別的中心處，使得選取的類中心點盡量屬于不同的類別，可以得到K個初始類別中心點，降低噪聲點對實驗結(jié)果的影響。根據(jù)FCM目標(biāo)函數(shù)來不斷迭代更新聚類中心以及隸屬度，優(yōu)化FCM算法對初始聚類中心敏感的問題，進而挖掘蛋白質(zhì)功能模塊。

2.2.4?期望稠密度優(yōu)化的EED度量

隨著數(shù)據(jù)的逐漸增多，圖的規(guī)模也相應(yīng)地增加，不確定圖所蘊含的確定圖數(shù)目呈指數(shù)形式增加，不確定圖蘊含的確定圖的期望密度的計算量是指數(shù)級的，導(dǎo)致子圖模式在不確定圖中的期望稠密度的計算十分復(fù)雜。針對此問題，基于2.1.1節(jié)邊聚集系數(shù)構(gòu)建的不確定PPI網(wǎng)絡(luò)圖，提出了子圖在不確定圖中的期望稠密度優(yōu)化EED度量，充分考慮節(jié)點的鄰域信息以及PPI網(wǎng)絡(luò)內(nèi)部聚集程度，降低計算復(fù)雜度，進而提高計算效率。本文利用EED優(yōu)化策略對算法挖掘出的功能模塊進行過濾，將低于EED閾值T的模塊過濾掉，避免重復(fù)劃分，提高算法的預(yù)測率。

運用這個定理，本文把指數(shù)級的期望稠密度計算量降低到了線性級。

2.3?FSC-FM方法

FSC-FM方法的具體實現(xiàn)步驟：步驟1?利用邊聚集系數(shù)計算PPI網(wǎng)絡(luò)中每組相互作用間的概率，從而構(gòu)建不確定PPI網(wǎng)絡(luò)圖。

步驟2?根據(jù)式（5）計算PPI網(wǎng)絡(luò)中的蛋白質(zhì)節(jié)點間的相似度，計算PPI網(wǎng)絡(luò)中每組相互作用的相似度矩陣，并采用改進相似度度量后的譜聚類算法預(yù)處理PPI數(shù)據(jù)，得到維數(shù)較低的矩陣Y。

步驟3?通過DPCS方法，獲取K個初始聚類中心;以初始聚類中心為起點，不斷迭代根據(jù)式（10）～（11）更新聚類中心以及隸屬度，根據(jù)式（9）計算目標(biāo)函數(shù)，實現(xiàn)網(wǎng)絡(luò)功能模塊的劃分，直到所有的節(jié)點都被遍歷完或與上次目標(biāo)函數(shù)值進行比較的出的變化量小于閾值ε。

步驟4?根據(jù)式（12）計算挖掘的模塊的密度，過濾邊期望稠密度小于閾值T的模塊。本文設(shè)定T=0.1。

2.4?方法分析

FSC-FM方法的計算復(fù)雜度由以下幾個步驟構(gòu)成：采用邊聚集系數(shù)構(gòu)建不確定PPI網(wǎng)絡(luò)的時間復(fù)雜度為O（|E|）;采用FEC策略改進相似性度量的譜聚類算法的時間復(fù)雜度主要取決于計算相似度矩陣以及特征分解，其中計算相似度矩陣的時間復(fù)雜度為O（N2），計算特征分解的時間復(fù)雜度為O（N），譜聚類算法的整體時間復(fù)雜度為O（N）;采用DPCS策略選取初始聚類中心的FCM算法的時間復(fù)雜度主要取決于計算概率密度函數(shù)以及搜索最大值，其中計算概率密度函數(shù)的時間復(fù)雜度為O（N），搜索最大值的時間復(fù)雜度為O（N），F(xiàn)CM算法的整體時間復(fù)雜度為O（N2+N）即O（N2）;采用EED度量過濾蛋白質(zhì)功能模塊的時間復(fù)雜度為O（K）。因此， FSC-FM方法的時間復(fù)雜度為O（|E|+N3+N2+K）即O（N3）。而在CDUN算法中，算法的時間復(fù)雜度主要取決于基于基因表達數(shù)據(jù)和PPI高通量數(shù)據(jù)構(gòu)建的不確定PPI網(wǎng)絡(luò)檢測候選蛋白質(zhì)模塊以及刪除高度重疊蛋白質(zhì)模塊，即O（KLN3）;在DCU算法中，算法的時間復(fù)雜度主要取決于產(chǎn)生候選蛋白質(zhì)集以及候選附件蛋白質(zhì)，即O（KN3）;在EA中，算法的時間復(fù)雜度主要取決于種群演化以及初始化算法，即O（αN3R）;在MGPPA中，算法的時間復(fù)雜度主要取決于蛋白質(zhì)簇形成的過程，即O（KθN3）。上述提及的L、α、R和θ分別表示基因表達時刻數(shù)、集群個數(shù)、迭代次數(shù)和數(shù)據(jù)庫屬性數(shù)目值。

3?實驗與結(jié)果分析

3.1?實驗環(huán)境

FSC-FM方法實驗的編程環(huán)境為Python3.5.2;操作系統(tǒng)為Windows 10家庭中文版;內(nèi)存12GB; CPU為Intel Core i5-4200H 2.8GHz。

3.2?實驗數(shù)據(jù)集

為驗證本文方法的有效性，選用蛋白質(zhì)相互作用數(shù)據(jù)相對完整和可靠的酵母蛋白質(zhì)相互作用網(wǎng)絡(luò)數(shù)據(jù)作為實驗數(shù)據(jù)。具體實驗數(shù)據(jù)如下所示：1）酵母PPI網(wǎng)絡(luò)數(shù)據(jù)來源于DIP數(shù)據(jù)庫[30]，去除重復(fù)的相互作用，該數(shù)據(jù)庫包含4995個蛋白質(zhì)和21554對相互作用。

2）本文采用CYC2008[31]作為已知蛋白質(zhì)功能模塊集，CYC2008包含408個通過生物實驗預(yù)測得到的功能模塊。

3）Krogan數(shù)據(jù)[32]是用串聯(lián)親和純化來處理4562不同標(biāo)簽酵母蛋白質(zhì)，去除自相互作用和重復(fù)相互作用后，該網(wǎng)絡(luò)中包含3672個蛋白質(zhì)和14317條可靠的相互作用。

3.3?評價指標(biāo)

3.3.1?特異性、靈敏度和F-measure度量

本文使用文獻[33]中的特異性（Specificity， Sp）、靈敏度（Sensitivity， Sn）和F-measure指標(biāo)來進行算法評價對比。特異性是指算法識別的功能模塊中成功匹配的模塊在挖掘出的模塊數(shù)目中所占比例，其定義為：

靈敏度是指匹配成功的功能模塊在基準(zhǔn)模塊中所占比例，其定義為：

其中：TP表示算法識別的功能模塊中與已知功能模塊匹配程度OS（A，B）≥0.2的數(shù)量;FP表示預(yù)測功能模塊中沒有匹配成功的數(shù)量;FN表示基準(zhǔn)模塊中沒有被成功匹配的數(shù)量。

為評估算法的有效性，對于算法挖掘出來的功能模塊A和已知功能模塊B之間的匹配程度通過OS（A，B）=|A∩B|2|A||B|計算得到。若識別出的功能模塊A與已知功能模塊B的匹配程度超過給定閾值，則稱該已知功能模塊被標(biāo)識，本文根據(jù)文獻[33]將該閾值設(shè)置為0.2。若OS（A，B）=1，則稱該已知功能模塊被完全標(biāo)識。為了避免靈敏度和特異性所帶來的偏見，采用F-measure綜合評價指標(biāo)來評估整體算法的性能，其計算公式如式（18）所示：

3.3.2?P值度量

隨著蛋白質(zhì)組學(xué)研究的深入，使得一個蛋白質(zhì)與其功能注釋向?qū)?yīng)成為可能，蛋白質(zhì)簇發(fā)生對于一個給定功能注釋在統(tǒng)計學(xué)上的意義就可以通過一個超幾何分布的等式來進行計算[34]：

3.4?參數(shù)影響分析

3.4.1?參數(shù)δ和ε的影響分析

FSC-FM方法中，由于參數(shù)δ和ε的取值影響實驗的聚類效果，因此本文在15組δ和ε的參數(shù)取值上獨立運行20次實驗，取20次實驗的平均值進行分析。實驗使用到的參數(shù)設(shè)置如下：m=2， ρ=3。表1給出了具體參數(shù)設(shè)置情況，其中Seti代表第i組參數(shù)，Q值表示不同的F-measure值或匹配的蛋白質(zhì)功能模塊比例。

實驗結(jié)果如圖2所示。

實驗結(jié)果表明，隨著δ從0～0.3逐漸增大，F(xiàn)-measure的值在ε不同取值之下也逐漸增大，實驗挖掘出的功能模塊和已知的功能模塊的匹配比例也逐漸增加;隨著δ從0.3～0.5逐漸增大，F(xiàn)-measure的值在ε不同取值之下逐漸降低，實驗挖掘出的功能模塊和已知的功能模塊的匹配比例也逐漸降低。這是因為采用DPCS策略選取合適的初始聚類中心時，算法需要多次迭代達到收斂效果，需要運行很長時間;且存在初始聚類中心選擇不理想，滿足條件的相互作用減少，模塊識別的覆蓋率降低，能夠匹配的功能模塊要求更加嚴(yán)格，功能模塊識別的數(shù)量較少，算法的精確度增加，導(dǎo)致F-measure值和匹配比例先增加后降低。通過觀察發(fā)現(xiàn)存在一對合理取值即ε=0.00015，δ=0.3使F-measure達到最大值0.59且匹配比例達到68.8347%。

3.4.2?閾值T的分析

FSC-FM算法中，根據(jù)改進的期望稠密度EED對挖掘出的蛋白質(zhì)功能模塊進行過濾，引入自定義參數(shù)T描述模塊的EED閾值，由定理2，T∈[0，1]。圖3顯示了T取不同值，F(xiàn)SC-FM算法的F-measure值的變化情況。

由圖3可看出，當(dāng)T=0.1時，F(xiàn)SC-FM方法可以得到最高的F-measure值，為此，本文設(shè)定T=0.1。

3.5?FEC策略的有效性分析

為了驗證FSC-FM方法使用改進的相似度FEC策略的有效性，分別基于使用FEC策略改進相似度計算的FSC-FM方法和未使用FEC策略的FSC-FM方法，在DIP數(shù)據(jù)庫上進行功能模塊的挖掘，實驗得到的F-measure和匹配比例如圖4所示。

由圖4顯示，使用改進相似度FEC策略的FSC-FM方法在Sn、Sp、F-measure取值和匹配的蛋白質(zhì)功能模塊比例都比未使用FEC策略的取值要高。具體Sn的取值比未使用FEC策略提高15.29%，Sp的取值比未使用FEC策略提高17.27%，F(xiàn)-measure的取值比未使用FEC策略提高5.12%，匹配的蛋白質(zhì)模塊比未使用FEC策略提高12.39%。實驗結(jié)果說明，使用改進的FEC策略的方法的聚類效果得到了提高。

3.6?DPCS和EED策略的有效性分析

為了驗證FSC-FM方法使用改進的相似度DPCS策略和EED度量的有效性，分別基于DPCS策略以及過濾模塊的EED度量的FSC-FM方法和未使用這兩種策略的FSC-FM方法，在DIP數(shù)據(jù)庫獨立執(zhí)行20次進行功能模塊的挖掘，實驗檢測結(jié)果如圖5所示。

圖5顯示的是使用DPCS和EED策略的FSC-FM方法在Sn、Sp、F-measure取值和匹配的蛋白質(zhì)功能模塊比例與未使用這兩種策略的對比情況，其中使用這兩種策略的Sn的取值比未使用這兩種策略提高12.50%，Sp的取值比未使用這兩種策略提高30.86%，F(xiàn)-measure的取值比未使用這兩種策略提高9.63%，匹配的蛋白質(zhì)模塊比未使用這兩種策略提高7.05%。這是因為，未使用DPCS策略和EED度量的算法挖掘出的功能模塊的預(yù)測結(jié)果存在過度的重疊特性，這種過度的重疊特性造成了預(yù)測結(jié)果太大而無法與一些較小的真實功能模塊相匹配;相反采用DPCS選擇初始聚類中心進行功能模塊挖掘，對得到的功能模塊采用EED度量進行模塊過濾，可以避免網(wǎng)絡(luò)數(shù)據(jù)噪聲對聚類結(jié)果造成的影響，避免過度重疊劃分，方法的聚類結(jié)果的特異性、靈敏度和F-measure值都較高，挖掘出的無用模塊數(shù)目以及重復(fù)劃分模塊數(shù)目較少。實驗結(jié)果說明，使用這兩種策略的方法的聚類效果較優(yōu)。

3.7?算法性能的比較分析

本節(jié)將FSC-FM分別從功能模塊挖掘的比較分析、功能富集的比較分析以及方法運行效率的比較分析與CDUN[18]、DCU[19]、EA[20]和MGPPA[21]進行比較分析，重復(fù)迭代次數(shù)為20。實驗中使用的參數(shù)設(shè)置如下：取m=2， ε=0.00015，δ=0.3， ρ=3，T=0.1。

3.7.1?功能模塊挖掘的比較分析

為了驗證本文方法的性能，將FSC-FM方法與其他4種算法獨立運行20次，取實驗結(jié)果的平均值進行分析，得到各個算法挖掘的功能模塊基本信息以及實驗評價指標(biāo)對比分析如表2和圖6所示。

在表2中，PM表示算法挖掘出的功能模塊總數(shù)，F(xiàn)ull是指已知的功能模塊集中被完全標(biāo)識的功能模塊數(shù)。從表2可以知道，F(xiàn)SC-FM方法挖掘的功能模塊中有254個被匹配，在所有算法中匹配數(shù)量最多，相比較而言本文方法對于挖掘蛋白質(zhì)功能模塊算法具有更高的效率。

圖6顯示各種方法在DIP數(shù)據(jù)集中識別的功能模塊計算的Sn、Sp和F-measure對比分析。

由圖6顯示，本文方法具有較高的F-measure、Sp和Sn值，F(xiàn)-measure的值較CDUN、DCU、EA和MGPPA提高了192.37%、27.92%、82.98%、182.23%，本文識別的功能模塊中識別正確的部分所占比例較高，因此本文方法取得了較好的優(yōu)化效率。

圖7顯示了不同算法檢測到的Elongator holoenzyme模塊結(jié)果，它真實存在于酵母菌細胞內(nèi)。圖7（a）是該標(biāo)準(zhǔn)模塊所包含的蛋白質(zhì)相互作用情況，其他是不同算法的檢測結(jié)果。

通過圖7顯示， 本文方法能夠準(zhǔn)確地挖掘蛋白質(zhì)功能模塊;CDUN算法識別出標(biāo)準(zhǔn)復(fù)合物中的6個蛋白質(zhì)，但是也包含了4個非Elongator holoenzyme模塊內(nèi)的蛋白質(zhì);DCU算法識別出標(biāo)準(zhǔn)模塊中的6個蛋白質(zhì)，但是也包含了1個非Elongator holoenzyme模塊內(nèi)的蛋白質(zhì);EA識別出標(biāo)準(zhǔn)模塊中的6個蛋白質(zhì)，但是也包含了2個非Elongator holoenzyme模塊內(nèi)的蛋白質(zhì);MGPPA識別出標(biāo)準(zhǔn)模塊中的5個蛋白質(zhì)。實驗結(jié)果表明， 本文方法在挖掘蛋白質(zhì)功能模塊上具有較好的聚類效果。

3.7.2?功能富集的比較分析

為了測試算法挖掘的功能模塊的生物學(xué)意義，本文采用功能富集分析評價挖掘的模塊的統(tǒng)計和生物特性。挖掘的模塊的低值P-value表明該功能模塊具有很高的統(tǒng)計學(xué)意義，將P-value的最小值對應(yīng)的功能作為該功能模塊的主要功能，通過給每個挖掘的模塊賦予最小的P-value值對應(yīng)的功能，可以識別預(yù)測功能模塊的功能。若一個模塊的P-value<0.01，則認(rèn)為這個模塊是顯著的，顯著的模塊數(shù)量在挖掘出的模塊總數(shù)中所占的比例可以很好地評價各個算法的整體性。具體各個算法性能比較分析如表3所示。

在表3中：PM表示算法挖掘出的功能模塊總數(shù)，SC是具有顯著意義的模塊數(shù)目。本文方法FSC-FM挖掘的模塊數(shù)目中顯著性模塊的比例達到83.20%，相對于CDUN[18]、DCU[19]、EA[20]和MGPPA[21]分別提高了66.4%、26.54%、51.19%、63.62%，由此可見， FSC-FM方法挖掘的功能模塊具有很強的生物統(tǒng)計學(xué)意義。為了更加深入分析和全面對比，對各個算法預(yù)測得到的功能模塊根據(jù)P-value區(qū)間值進行對比分析，可分為兩個區(qū)間，即（0，E-10）和[E-10，0.01）。圖8顯示了分區(qū)間對比情況。

從圖8可看出本文方法FSC-FM挖掘的功能模塊中P-value

根據(jù)表3和圖8分析可知，F(xiàn)SC-FM方法挖掘出的功能模塊更具有生物意義。

3.7.3?算法效率的比較分析

為進一步分析比較本文方法FSC-FM的執(zhí)行效率，將其與CDUN[18]、DCU[19]、EA[20]和MGPPA[21]在各自算法優(yōu)化參數(shù)之下，在DIP數(shù)據(jù)庫上運行20次，取實驗的平均值來比較分析，得到各個算法的平均運行效率對比如表4所示。

在表4中，模塊數(shù)量是指算法挖掘的模塊規(guī)模大于3的蛋白質(zhì)數(shù)目，匹配率是挖掘的蛋白質(zhì)和基準(zhǔn)模塊匹配的數(shù)目比例。從表4可知， 本文方法挖掘蛋白質(zhì)功能模塊所需的時間相對較少，實驗運行的時間復(fù)雜度較低，是508.25s。本文方法相對其他四種算法的平均運行時間都超過600s，比DCU算法執(zhí)行效率提高了27.92%。由此可見， 本文方法可以應(yīng)用于相對規(guī)模較大的不確定PPI網(wǎng)絡(luò)，進而挖掘蛋白質(zhì)功能模塊。主要是因為， 本文方法基于不確定PPI網(wǎng)絡(luò)，使用改進相似度度量的譜聚類算法以及融合優(yōu)化初始聚類中心選取的FCM算法來挖掘蛋白質(zhì)功能模塊，進而采用不確定PPI網(wǎng)絡(luò)拓?fù)涮匦缘倪吰谕砻軄磉^濾模塊。因此， 本文方法在挖掘蛋白質(zhì)模塊具有很好的運行效率。

為進一步分析比較數(shù)據(jù)規(guī)模對個算法運行效率的影響，將FSC-FM方法與CDUN[18]、DCU[19]、EA[20]和MGPPA[21]在各自算法優(yōu)化參數(shù)之下，在Krogan數(shù)據(jù)集上運行20次，取實驗的平均值來比較分析，得到各個算法的平均運行效率對比如表5所示。

從表5可知，相對于DIP數(shù)據(jù)庫上的運行結(jié)果， 各個算法在數(shù)據(jù)規(guī)模較小的Krogan數(shù)據(jù)集上的執(zhí)行效率以及匹配率相對都有所提高。具體來說，CDUN算法挖掘模塊的匹配率提高了1.81551%，運行時間降低了1.2479%;DCU算法挖掘模塊的匹配率提高了4.4091%，運行時間降低了1.3832%;EA挖掘模塊的匹配率提高了1.9076%，運行時間降低了4.8819%;MGPPA的匹配率提高了0.5321544%，運行時間降低了0.0523%;FSC-FM方法挖掘模塊的匹配率提高了4.7119%，運行時間降低了5.176%。從表5可知，DCU算法和FSC-FM處理數(shù)據(jù)規(guī)模較大的數(shù)據(jù)集的執(zhí)行效率相對較高，而數(shù)據(jù)規(guī)模對MGPPA的執(zhí)行效率影響不大，CDUN和EA處理數(shù)據(jù)規(guī)模較小的數(shù)據(jù)集的執(zhí)行效率相對較高。

綜合分析表4～5，本文提出的挖掘功能模塊FSC-FM方法的運行效率較高。

4?結(jié)語

本文基于不確定蛋白質(zhì)相互作用網(wǎng)絡(luò)，提出一種基于模糊譜聚類的不確定PPI網(wǎng)絡(luò)功能模塊挖掘方法FSC-FM。該方法利用邊聚集系數(shù)構(gòu)建不確定蛋白質(zhì)網(wǎng)絡(luò)，提高功能模塊挖掘的準(zhǔn)確率;其次采用FEC策略改進譜聚類算法中相似矩陣計算對尺度參數(shù)敏感的缺陷;通過DPCS策略優(yōu)化FCM算法對初始聚類中心、聚類數(shù)目敏感的問題;采用EED度量過濾算法挖掘出的模塊。為了評估方法的性能，本文將FSC-FM方法與CDUN、DCU、EA和MGPPA進行了對比，實驗結(jié)果表明，F(xiàn)SC-FM方法具有更高的準(zhǔn)確率、靈敏度和執(zhí)行效率，識別的功能模塊具有更強的生物統(tǒng)計意義。對蛋白質(zhì)功能模塊挖掘今后的研究，可以從兩個方面入手：1） 深入研究PPI網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，綜合考慮蛋白質(zhì)生物信息來構(gòu)建動態(tài)蛋白質(zhì)網(wǎng)絡(luò)以降低數(shù)據(jù)噪聲的影響;2） 結(jié)合多元生物數(shù)據(jù)的方法以提升挖掘結(jié)果。

參考文獻（References）

[1] 冀俊忠， 高光軒. 基于文化算法的PPI網(wǎng)絡(luò)功能模塊檢測方法[J]. 北京工業(yè)大學(xué)學(xué)報， 2017， 43（1）： 13-21. （JI J Z， GAO G X. Detecting functional module method based on cultural algorithm in protein-protein interaction networks [J]. Journal of Beijing University of Technology， 2017， 43（1）： 13-21.）

[2] 魚亮， 高琳， 孫鵬. 蛋白質(zhì)網(wǎng)絡(luò)中復(fù)合體和功能模塊預(yù)測算法研究[J]. 計算機學(xué)報， 2011， 34（7）： 1239-1251. （YU L， GAO L， SUN P. Research on algorithms for complexes and functional modules prediction in protein-protein interaction networks [J]. Chinese Journal of Computer， 2011， 34（7）： 1239-1251.）

[3] 倪問尹， 王建新， 熊慧軍， 等. 基于不確定數(shù)據(jù)的功能模塊預(yù)測[J]. 四川大學(xué)學(xué)報（工程科學(xué)版）， 2013， 45（5）： 80-87. （NI W Y， WANG J X， XIONG H J， et al. Research of detecting functional modules based on uncertainty data[J]. Journal of Sichuan University （Engineering Science Edition）， 2013， 45（5）： 80-87.）

[4] 冀俊忠， 劉志軍， 劉紅欣， 等.蛋白質(zhì)相互作用網(wǎng)絡(luò)功能模塊檢測的研究綜述[J]. 自動化學(xué)報， 2014， 40（4）： 577-593. （JI J Z， LIU Z J， LIU H X， et al. An overview research on functional module detection for protein-protein interaction networks [J]. Acta Automatica Sinica， 2014， 40（4）： 577-593.）

[5] 李敏， 王建新， 劉彬彬， 等.基于極大團擴展的蛋白質(zhì)復(fù)合物識別算法[J]. 中南大學(xué)學(xué)報（自然科學(xué)版）， 2010， 41（2）： 560-565. （LI M， WANG J X， LIU B B， et al. An algorithm for identifying protein complexes based on maximal clique extension [J]. Journal of Central South University （Science and Technology）， 2010， 41（2）： 560-565.）

[6] KESSLER J， ANDRUSHCHENKO V， KAPITAN J， et al. Insight into vibrational circular dichroism of proteins by density functional modeling [J]. Physical Chemistry Chemical Physics， 2018， 20（7）： 4926-4935.

[7] ALDECO R， MARIN I. Jerarca： efficient analysis of complex networks using hierarchical clustering[J]. PLoS ONE， 2010， 5（7）： 11585-11591.

[8] ABEYSIRIGUNAWARDENA S C， KIM H， LAI J， et al. Evolution of protein-coupled RNA dynamics during hierarchical assembly of ribosomal complexes[J]. Nature Communications， 2017， 8（1）： 492-500.

[9] 雷秀娟， 高銀， 郭玲.基于拓?fù)鋭菁訖?quán)的動態(tài)PPI網(wǎng)絡(luò)復(fù)合物挖掘方法[J]. 電子學(xué)報， 2018， 46（1）： 145-151. （LEI X J， GAO Y， GUO L. Mining protein complexes based on topology potential weight in dynamic protein-protein interaction networks [J]. Acta Electronica Sinica， 2018， 46（1）： 145-151.）

[10] YAO X H， YAN J W， LIU K F， et al. Tissue-specific network-based genome wide study of amygdala imaging phenotypes to identify functional interaction modules [J]. Bioinformatics， 2017， 33（20）： 3250-3257.

[11] 范子靜， 羅澤， 馬永征. 一種基于模糊核聚類的譜聚類算法[J]. 計算機工程， 2017， 43（11）： 161-165. （FAN Z J， LUO Z， MA Y Z. A spectral clustering algorithm based on fuzzy kernel clustering [J]. Computer Engineering， 2017， 43（11）： 161-165.）

[12] MADANI S， FAEZ K， AMINGHAFARI M. Identifying similar functional modules by a new hybrid spectral clustering method [J]. IET Systems Biology， 2012， 6（5）： 175-186.

[13] QIN G M， GAO L. Spectral clustering for protein complexes in Protein-Protein Interaction （PPI） networks [J]. Mathematical and Computer Modelling， 2010， 52（11/12）： 2066-2074.

[14] INOUE K， LI W J， KURATA H. Diffusion model based spectral clustering for protein-protein interaction networks [J]. PLoS ONE， 2010， 5（9）： 12623-12632.

[15] 那第爾.識別蛋白質(zhì)相互作用網(wǎng)絡(luò)中的復(fù)合物[D]. 長沙： 中南大學(xué)， 2012： 22-34. （NA D E. Exploiting fuzzy spectral clustering in protein-complex detection [D]. Changsha： Central South University， 2012： 22-34.）

[16] TRIVODALIEV K， CINGOVSKA I， KALAJDZISKI S. Protein function prediction by spectral clustering of protein interaction network [C]// Proceedings of the 2011 Database Theory and Application， Bio-Science and Bio-Technology. Berlin： Springer， 2011： 108-117.

[17] ZOU Z N， LI J Z， GAO H， et al. Mining frequent subgraph patterns from uncertain graph data [J]. IEEE Transactions on Knowledge and Data Engineering， 2010， 22（9）： 1203-1218.

[18] ZHANG Y J， LIN H F， YANG Z H， et al. An uncertain model-based approach for identifying protein complexes in uncertain protein-protein interaction networks [J]. BMC Genomics， 2017， 18（7）： 743-752.

[19] ZHAO B H， WANG J X， LI M. Detecting protein complexes based on uncertain graph model [J]. IEEE/ACM Transactions on Computational Biology & Bioinformatics， 2014， 11（3）： 486-497.

[20] HALIM Z， WAQAS M， HUSSAIN S F. Clustering large probabilistic graphs using multi-population evolutionary algorithm[J]. Information Sciences， 2015， 317（1）： 78-95.

[21] BANO R， RAO K. Graph based gene/protein prediction and clustering over uncertain medical databases [J]. Journal of Theoretical and Applied Information Technology， 2015， 82（3）： 347-352.

[22] GAO Y J， MIAO X Y， CHEN G， et al. On efficiently finding reverse k-nearest neighbors over uncertain graphs [J]. VLDB Journal， 2017， 26（4）： 1-26.

[23] 李敏， 張含會， 費耀平. 融合PPI和基因表達數(shù)據(jù)的關(guān)鍵蛋白質(zhì)識別方法[J]. 中南大學(xué)學(xué)報（自然科學(xué)版）， 2013， 44（3）： 1024-1039. （LI M， ZHANG H H， FEI Y P. Essential protein discovery method based on integration of PPI and gene expression data [J]. Journal of Central South University （Science and Technology）， 2013， 44（3）： 1024-1039.）

[24] 黃鏈， 鄧?yán)?擬-偏b-度量空間中α-φ-壓縮映象不動點的存在性[J]. 西南大學(xué)學(xué)報（自然科學(xué)版）， 2018， 40（3）： 115-120. （HUANG L， DENG L. α-φ-contractive mappings on quasi-partial b-metric spaces [J]. Journal of Southwest University （Natural Science Edition）， 2018， 40（3）： 115-120.）

[25] 朱镕， 鄒兆年， 李建中.不確定圖上的Top-k稠密子圖挖掘算法[J]. 計算機學(xué)報， 2016， 39（8）： 1570-1582. （ZHU R， ZOU Z N， LI J Z. Mining Top-k dense subgraphs from uncertain graphs [J]. Chinese Journal of Computers， 2016， 39（8）： 1570-1582.）

[26] 胡賽， 熊慧軍， 陳治平， 等.基于不確定網(wǎng)絡(luò)的關(guān)鍵蛋白質(zhì)識別[J]. 四川大學(xué)學(xué)報（工程科學(xué)版）， 2014， 46（5）： 116-120. （HU S， XIONG H J， CHEN Z P， et al. Identification of essential proteins based on uncertain networks [J].

Journal of Sichuan University （Engineering Science Edition）， 2014， 46（5）： 116-120.）

[27] 王玲， 薄列峰， 焦李成. 密度敏感的譜聚類[J]. 電子學(xué)報， 2007， 35（8）： 1577-1581. （WANG L， BO L F， JIAO L C. Density-sensitive spectral clustering [J]. Acta Electronica Sinica， 2007， 35（8）： 1577-1581.）

[28] RAFAILIDIS D， CONSTANTINOU E， MANOLOPOULOS Y. Landmark selection for spectral clustering based on weighted PageRank [J]. Future Generation Computer Systems， 2017， 68（3）： 465-472.

[29] KESEMEN O， TEZEL O， OZKUL E. Fuzzy C-means clustering algorithm for directional data （FCM4DD） [J]. Expert Systems with Applications， 2016， 58： 76-82.

[30] XENARIOS I， SALWINSKI 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.

[31] PU S， WONG J， TURNER B， et al. Up-to-date catalogues of yeast protein complexes[J]. Nucleic Acids Research， 2009， 37（3）： 825-831.

[32] KROGAN N， CAGNEY G， YU H， et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae [J]. Nature， 2006， 440（7084）： 637-643.

[33] 胡賽， 熊慧軍， 李學(xué)勇， 等.多關(guān)系蛋白質(zhì)網(wǎng)絡(luò)構(gòu)建及其應(yīng)用研究[J]. 自動化學(xué)報， 2015， 41（12）： 2155-2163. （HU S， XIONG H J， LI X Y， et al. Construction of multi-relation protein networks and its application[J]. Acta Automatica Sinica， 2015， 41（12）： 2155-2163.）

[34] LEI X J， WU S， LIANG G， et al. Clustering and overlapping modules detection in PPI network based on IBFO [J]. Proteomics， 2013， 13（2）： 278-290.