采用隱馬爾科夫模型的蛋白質(zhì)復(fù)合物識(shí)別研究

李 鵬，羅愛(ài)靜，閔 慧，譚蓀怡，郭惠敏

1.中南大學(xué) 湘雅三醫(yī)院，長(zhǎng)沙 410006

2.湖南中醫(yī)藥大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410208

3.醫(yī)學(xué)信息研究湖南省普通高等學(xué)校重點(diǎn)實(shí)驗(yàn)室（中南大學(xué)），長(zhǎng)沙 410006

4.湖南信息職業(yè)技術(shù)學(xué)院 軟件學(xué)院，長(zhǎng)沙 410200

隨著人類基因組計(jì)劃以及對(duì)于多個(gè)物種全基因組測(cè)序工作的結(jié)束，目前生命科學(xué)研究的重點(diǎn)已經(jīng)轉(zhuǎn)移到了蛋白組學(xué)[1]。蛋白質(zhì)是生物體生命活動(dòng)的重要物質(zhì)基礎(chǔ)，沒(méi)有蛋白質(zhì)就沒(méi)有生命。一個(gè)生物體內(nèi)所有蛋白質(zhì)相互作用被稱為蛋白質(zhì)相互作用網(wǎng)絡(luò)（protein-protein interaction networks，PPIN），簡(jiǎn)稱蛋白質(zhì)網(wǎng)絡(luò)[2]。值得注意的是，蛋白質(zhì)之間的相互作用是動(dòng)態(tài)的，它會(huì)隨著時(shí)間環(huán)境、蛋白質(zhì)的存在和降解、細(xì)胞的不同生理狀態(tài)等因素的變化而變化，但由于PPIN 本身的復(fù)雜性、可利用的蛋白質(zhì)相互作用數(shù)據(jù)的不完全性和存在噪聲等眾多問(wèn)題，準(zhǔn)確且高效地衡量蛋白質(zhì)相互作用的動(dòng)態(tài)性還存在很多挑戰(zhàn)[3-4]，這也直接限制了PPIN 領(lǐng)域內(nèi)很多問(wèn)題[5-6]（復(fù)合物識(shí)別、關(guān)鍵蛋白識(shí)別、網(wǎng)絡(luò)比對(duì)等）的研究進(jìn)展。為此，本文將對(duì)動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)的構(gòu)建問(wèn)題進(jìn)行研究，并在此基礎(chǔ)上提出新的蛋白質(zhì)復(fù)合物識(shí)別方法，這有利于從微觀層面解釋細(xì)胞內(nèi)蛋白質(zhì)之間的復(fù)雜關(guān)系，為生物學(xué)家、醫(yī)學(xué)家理解生命復(fù)雜網(wǎng)絡(luò)的內(nèi)在組織和生物過(guò)程提供新的途徑，在藥物標(biāo)靶設(shè)計(jì)、疾病診治和預(yù)測(cè)等方面也具有重要的應(yīng)用價(jià)值。

1 相關(guān)工作

目前，已有眾多研究者對(duì)動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物識(shí)別問(wèn)題進(jìn)行了研究，例如雷秀娟等人[7]首先將所有蛋白質(zhì)之間的相互作用建模為一個(gè)拓?fù)鋭?shì)場(chǎng)，并以此來(lái)構(gòu)建加權(quán)的動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)。在此基礎(chǔ)上再采用馬爾科夫聚類算法在多種典型的生物數(shù)據(jù)集上進(jìn)行復(fù)合物識(shí)別。然而該方法存在復(fù)雜度較大的問(wèn)題。趙學(xué)武等人[8]分析了在靜態(tài)蛋白質(zhì)網(wǎng)絡(luò)上進(jìn)行復(fù)合物識(shí)別的局限性，提出了一種基于時(shí)序基因表達(dá)數(shù)據(jù)和蟻群聚類的復(fù)合物識(shí)別算法（identify protein complexes by integrating temporal function continue feature and ant colony clustering，IPC-TFC&ACC）應(yīng)用于動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中。該算法首先基于蛋白質(zhì)的表達(dá)活性選出復(fù)合物的種子節(jié)點(diǎn)，然后結(jié)合蛋白質(zhì)之間的功能相似性采用蟻群聚類算法來(lái)得到最終的復(fù)合物。文獻(xiàn)[9]從蛋白質(zhì)網(wǎng)絡(luò)的拓?fù)鋵傩院蜕飳W(xué)特征著手，提出了基于動(dòng)態(tài)核依附的蛋白質(zhì)復(fù)合物識(shí)別算法（dynamic core-attachment，DCA）。文獻(xiàn)[10]首先利用蛋白質(zhì)的功能注釋數(shù)據(jù)和時(shí)序基因表達(dá)數(shù)據(jù)來(lái)構(gòu)建動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)，然后基于聚類的方法得到初始的復(fù)合物，在此基礎(chǔ)上設(shè)計(jì)出蛋白質(zhì)節(jié)點(diǎn)的遷移和復(fù)合物間的融合策略，進(jìn)而提出了一種基于動(dòng)態(tài)群體決策的復(fù)合物識(shí)別算法（identifying protein complexes based on dynamic group decision，IPC-DGD）。Lei 等人[11]提出了一種改進(jìn)的花授粉算法（improved flower pollination algorithm，IFPA）以識(shí)別多關(guān)系重建的動(dòng)態(tài)PPI 網(wǎng)絡(luò)中的蛋白質(zhì)復(fù)合物。文中首先考慮了蛋白質(zhì)在尋找本質(zhì)相互作用中的重要性，然后設(shè)計(jì)了多關(guān)系重構(gòu)的動(dòng)態(tài)PPI 網(wǎng)絡(luò)，并發(fā)現(xiàn)了網(wǎng)絡(luò)中蛋白質(zhì)復(fù)合物的潛在核心。最后，提出了一種基于花授粉機(jī)制的IFPA 算法，通過(guò)模擬花粉過(guò)程生成蛋白質(zhì)復(fù)合物。該方法可在擴(kuò)充過(guò)程中允許某個(gè)蛋白質(zhì)重復(fù)出現(xiàn)，但無(wú)法識(shí)別PPI 網(wǎng)絡(luò)中非稠密的子圖結(jié)構(gòu)，識(shí)別精度還有待提高。

雖然上述方法各有優(yōu)點(diǎn)，在某些生物數(shù)據(jù)集上表現(xiàn)出較好的計(jì)算性能和準(zhǔn)確性，但這些算法只是單獨(dú)對(duì)每個(gè)時(shí)刻的蛋白質(zhì)網(wǎng)絡(luò)快照進(jìn)行蛋白質(zhì)復(fù)合物識(shí)別，忽略了動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中不同時(shí)刻之間的影響關(guān)系。在動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中，當(dāng)前時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)信息與前一時(shí)刻或者前幾個(gè)時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)信息是相關(guān)的，前一時(shí)刻的蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物對(duì)當(dāng)前時(shí)刻蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物存在著影響，而之前的動(dòng)態(tài)算法忽略了歷史信息對(duì)當(dāng)前時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)的影響，使得復(fù)合物識(shí)別的準(zhǔn)確性和穩(wěn)定性偏低。針對(duì)上述識(shí)別算法存在的問(wèn)題，文中借鑒隱馬爾科夫模型（hidden Markov model，HMM）[12]在處理復(fù)雜網(wǎng)絡(luò)上的優(yōu)勢(shì)，提出一種基于HMM 的蛋白質(zhì)復(fù)合物識(shí)別算法（HMM-PC）。該方法首先引入HMM 描述蛋白質(zhì)復(fù)合物結(jié)構(gòu)與網(wǎng)絡(luò)中蛋白質(zhì)個(gè)體間的相互作用，將網(wǎng)絡(luò)中的復(fù)合物結(jié)構(gòu)和蛋白質(zhì)節(jié)點(diǎn)信息分別采用狀態(tài)鏈和觀察鏈表示。然后通過(guò)求解HMM 中的最優(yōu)狀態(tài)序列實(shí)現(xiàn)動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物識(shí)別。最后通過(guò)在多個(gè)生物數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了HMM-PC 算法的有效性。

2 動(dòng)態(tài)加權(quán)蛋白質(zhì)網(wǎng)絡(luò)的構(gòu)建

蛋白質(zhì)網(wǎng)絡(luò)具有偏好連接特性，且隨著網(wǎng)絡(luò)規(guī)模的增加，不同節(jié)點(diǎn)間的連接數(shù)差異呈現(xiàn)著增加的趨勢(shì)。因此本文通過(guò)構(gòu)建加權(quán)的動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)來(lái)反映真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)，在此基礎(chǔ)之上識(shí)別蛋白質(zhì)復(fù)合物。

2.1 初始蛋白質(zhì)網(wǎng)絡(luò)的構(gòu)建

一般而言，蛋白質(zhì)網(wǎng)絡(luò)可用無(wú)向圖進(jìn)行建模，設(shè)G=(V,E) 表示蛋白質(zhì)網(wǎng)絡(luò)，V表示G中的蛋白質(zhì)集合，|V|表示G中的蛋白質(zhì)總數(shù)；E表示G中的蛋白質(zhì)與蛋白質(zhì)之間相互作用的集合，|E|表示G中的相互作用的總數(shù)?？紤]到蛋白質(zhì)只有在活性狀態(tài)下才能與其他蛋白質(zhì)發(fā)現(xiàn)相互作用，文中引入文獻(xiàn)[13]提出的3-sigma法則來(lái)判斷在一個(gè)時(shí)間序列中哪些蛋白質(zhì)是活性的，然后利用蛋白質(zhì)之間的基因共表達(dá)特性來(lái)構(gòu)建初始蛋白質(zhì)網(wǎng)絡(luò)。文獻(xiàn)[14]對(duì)酵母菌株的生長(zhǎng)過(guò)程進(jìn)行了耗氧量測(cè)定，驗(yàn)證了周期基因表達(dá)的存在，可以將蛋白質(zhì)36 個(gè)時(shí)刻的基因表達(dá)分為3個(gè)周期，每12 個(gè)時(shí)刻為一個(gè)周期。設(shè)每個(gè)蛋白質(zhì)的基因表達(dá)平均水平為：

其中，tv(i)表示蛋白質(zhì)v在時(shí)刻i的基因表達(dá)值。計(jì)算出所有蛋白質(zhì)的基因表達(dá)平均水平后，根據(jù)3-sigma 法則來(lái)判斷各個(gè)蛋白質(zhì)在12 個(gè)時(shí)刻的活性狀態(tài)。如果蛋白質(zhì)u和蛋白質(zhì)v在第i(1 ≤i≤12)個(gè)時(shí)刻同時(shí)處于活性狀態(tài)，則認(rèn)為u、v之間在時(shí)刻i存在相互作用。即有：

為了構(gòu)建第i個(gè)時(shí)刻的蛋白質(zhì)網(wǎng)絡(luò)，采用如下的思路進(jìn)行構(gòu)建：統(tǒng)計(jì)第i個(gè)時(shí)刻同時(shí)處于活性狀態(tài)的所有蛋白質(zhì)的數(shù)目，并采用鄰接矩陣進(jìn)行存儲(chǔ)，然后根據(jù)式（2）確定鄰接矩陣中對(duì)應(yīng)位置的元素的值，從而可以得到一個(gè)無(wú)向圖來(lái)表示蛋白質(zhì)網(wǎng)絡(luò)。

2.2 網(wǎng)絡(luò)加權(quán)

通過(guò)基因表達(dá)數(shù)據(jù)構(gòu)建得到的初始蛋白質(zhì)網(wǎng)絡(luò)只能衡量節(jié)點(diǎn)之間的連接關(guān)系，但不能反映出節(jié)點(diǎn)間的偏好連接特性。動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)可由多個(gè)時(shí)刻的靜態(tài)蛋白質(zhì)網(wǎng)絡(luò)表示，本文將動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)按照時(shí)間粒度劃分為多個(gè)網(wǎng)絡(luò)快照。有如下的定義：

定義1（時(shí)序圖時(shí)序圖表示在時(shí)刻t內(nèi)具有相互作用的所有蛋白質(zhì)構(gòu)成的蛋白質(zhì)網(wǎng)絡(luò)。動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)可以用時(shí)序圖的集合來(lái)描述：

文中在2.1 節(jié)構(gòu)建得到的12 個(gè)初始蛋白質(zhì)網(wǎng)絡(luò)的基礎(chǔ)上，考慮進(jìn)一步利用蛋白質(zhì)的生物信息數(shù)據(jù)和拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)來(lái)對(duì)網(wǎng)絡(luò)進(jìn)行加權(quán)。文中首先對(duì)酵母物種中部分已知的蛋白質(zhì)復(fù)合物與蛋白質(zhì)功能注釋的關(guān)系進(jìn)行了統(tǒng)計(jì)分析，結(jié)果如圖1 所示?？梢钥吹?，隨著不同蛋白質(zhì)之間共享功能注釋數(shù)目的增加，能夠識(shí)別的蛋白質(zhì)復(fù)合物數(shù)量的比例和蛋白質(zhì)復(fù)合物規(guī)模的比例都在呈現(xiàn)上升的趨勢(shì)，這表明蛋白質(zhì)間的共享功能注釋信息有助于識(shí)別蛋白質(zhì)復(fù)合物，可以應(yīng)用到復(fù)合物的識(shí)別中。為此，本文給出了如下的定義2 作為對(duì)蛋白質(zhì)網(wǎng)絡(luò)加權(quán)的因子之一。

定義2（共享功能注釋）對(duì)于PPIN 中的任意兩個(gè)蛋白質(zhì)u和v表示u的功能注釋集合；表示v的功能注釋集合；表示u和v的相同功能注釋集合。則有：

Fig.1 Functional annotation of protein vs protein complex圖1 蛋白質(zhì)復(fù)合物vs蛋白質(zhì)的功能注釋

考慮到大部分物種中蛋白質(zhì)的已知功能注釋數(shù)量不一，為了保證復(fù)合物識(shí)別的準(zhǔn)確性，本文認(rèn)為，如果某個(gè)蛋白質(zhì)的功能注釋數(shù)目小于2，則認(rèn)為利用該功能注釋來(lái)對(duì)網(wǎng)絡(luò)加權(quán)無(wú)意義，不做考慮。

定義3（共享結(jié)構(gòu)域[15]）對(duì)于PPIN 中的任意兩個(gè)蛋白質(zhì)u和v，表示u的結(jié)構(gòu)域集合；表示v的結(jié)構(gòu)域集合；表示u和v的相同結(jié)構(gòu)域集合。則有：

定義4（連接強(qiáng)度）對(duì)于PPIN 中的任意兩個(gè)蛋白質(zhì)u和v，dcuv是u和v之間直接相連的邊的數(shù)量；nb(u)是蛋白質(zhì)u擁有的鄰居節(jié)點(diǎn)數(shù)；du是蛋白質(zhì)u的度。則有：

聯(lián)立定義2～4 可知，動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中任意兩個(gè)蛋白質(zhì)u和v之間邊的權(quán)值為：

綜上所述，本文提出的動(dòng)態(tài)加權(quán)蛋白質(zhì)網(wǎng)絡(luò)構(gòu)建過(guò)程如算法1 所示。

算法1動(dòng)態(tài)加權(quán)蛋白質(zhì)網(wǎng)絡(luò)構(gòu)建算法

輸入：蛋白質(zhì)相互作用數(shù)據(jù)，基因表達(dá)數(shù)據(jù)。

輸出：動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)G。

1.首先根據(jù)式（1）計(jì)算所有蛋白質(zhì)的基因表達(dá)水平，然后采用3-sigma 法則判斷各個(gè)蛋白質(zhì)在第i(1 ≤i≤12)個(gè)時(shí)刻的活性狀態(tài)；

2.i=1，根據(jù)式（2）找出在同一時(shí)刻存在相互作用的所有蛋白質(zhì)對(duì)，構(gòu)建得到第1 個(gè)時(shí)刻的初始蛋白質(zhì)網(wǎng)絡(luò)G′；

3.對(duì)G′中的所有邊進(jìn)行如下處理：

3.1 根據(jù)式（4）計(jì)算G′中所有蛋白質(zhì)的共享功能注釋信息；

3.2 根據(jù)式（5）計(jì)算G′中所有蛋白質(zhì)的共享結(jié)構(gòu)域信息；

3.3 根據(jù)式（6）計(jì)算G′中所有蛋白質(zhì)的連接強(qiáng)度信息；

3.4 根據(jù)式（7）對(duì)G′中所有邊進(jìn)行賦權(quán)。

4.i=i+1；

5.重復(fù)執(zhí)行2～3，直到所有12 個(gè)時(shí)刻的網(wǎng)絡(luò)都賦權(quán)完畢，則算法結(jié)束。

3 基于HMM 的蛋白質(zhì)復(fù)合物識(shí)別

3.1 HMM 介紹

隱馬爾科夫模型（HMM）是一種用來(lái)描述隨機(jī)過(guò)程統(tǒng)計(jì)特性的概率模型，它是一個(gè)關(guān)于時(shí)序的概率模型，描述由一個(gè)隱藏的馬爾科夫鏈隨機(jī)生成不可觀測(cè)的狀態(tài)隨機(jī)序列，再由各個(gè)狀態(tài)生成一個(gè)觀測(cè)而產(chǎn)生觀測(cè)隨機(jī)序列的過(guò)程。HMM 由初始狀態(tài)概率向量、狀態(tài)轉(zhuǎn)移概率矩陣和觀測(cè)概率矩陣組成，如圖2 所示。其中，x表示隱藏狀態(tài)，y是觀測(cè)狀態(tài)。

Fig.2 Example of HMM圖2 HMM 示例

假定相鄰時(shí)刻的蛋白質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)，對(duì)不同時(shí)刻蛋白質(zhì)網(wǎng)絡(luò)中復(fù)合物結(jié)構(gòu)的關(guān)系可用一階Markov 鏈描述，由于蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物結(jié)構(gòu)不能被直接觀察到，文中在考慮前一時(shí)刻蛋白質(zhì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息對(duì)當(dāng)前時(shí)刻蛋白質(zhì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息影響的前提下，引入HMM 將不同時(shí)刻蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物結(jié)構(gòu)建模為HMM 中的狀態(tài)鏈。將蛋白質(zhì)網(wǎng)絡(luò)中每個(gè)蛋白質(zhì)節(jié)點(diǎn)的節(jié)點(diǎn)度分布建模為觀察鏈。采用HMM 描述動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物發(fā)現(xiàn)問(wèn)題，通過(guò)求解HMM 中的最優(yōu)狀態(tài)序列得到蛋白質(zhì)復(fù)合物，可以更好地理解動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物結(jié)構(gòu)演變情況。為了便于描述，先給出文中用到的如下幾個(gè)定義：

定義5（狀態(tài)序列SS）基于定義1 所示的動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)G，定義G中各個(gè)時(shí)刻的蛋白質(zhì)復(fù)合物為HMM 中的狀態(tài)序列SS。其中，SS=(C1,C2,…,Ct,…,CN)，N表示狀態(tài)總數(shù)，Ct表示蛋白質(zhì)節(jié)點(diǎn)在時(shí)刻t的狀態(tài)。

定義6（可觀察序列OS）基于定義1 所示的動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)G，定義HMM 中的觀察序列為G中每個(gè)蛋白質(zhì)節(jié)點(diǎn)的節(jié)點(diǎn)度大小。其中，OS=(d1,d2,…,dt,…,dM)，M表示從每一狀態(tài)可能輸出的不同的觀察值數(shù)目，dt表示在時(shí)刻t的某個(gè)蛋白質(zhì)節(jié)點(diǎn)的度。

3.2 基于HMM 的復(fù)合物識(shí)別建模

式中，aij表示在時(shí)刻t的狀態(tài)為Ci，時(shí)刻t+1 的狀態(tài)為Cj的概率；為狀態(tài)j的觀察概率矩陣，(bj(k))，表示狀態(tài)j輸出相應(yīng)觀察值的概率，其中：

定義7（核心節(jié)點(diǎn)）給定任意的蛋白質(zhì)復(fù)合物Ct，設(shè)W(t,i)表示蛋白質(zhì)t和蛋白質(zhì)i相連的邊的權(quán)值，則選取復(fù)合物Ct中具有最大權(quán)值之和的蛋白質(zhì)節(jié)點(diǎn)為核心節(jié)點(diǎn)，即有：

其中，r表示復(fù)合物Ct中的蛋白質(zhì)總數(shù)；l表示與Ct中某一蛋白質(zhì)i存在相互作用的蛋白質(zhì)數(shù)目；W(k,i)表示蛋白質(zhì)k和蛋白質(zhì)i之間的權(quán)值。

定義8（相似度）設(shè)時(shí)序圖GS

i中的蛋白質(zhì)節(jié)點(diǎn)表示為，則中任意兩個(gè)蛋白質(zhì)節(jié)點(diǎn)和之間的相似度為：

定義10（歸屬度）設(shè)動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)用鄰接矩陣A表示，rij為A中的元素，則蛋白質(zhì)網(wǎng)絡(luò)中的某一蛋白質(zhì)節(jié)點(diǎn)u歸屬于復(fù)合物Ct的程度可表示為：

定義11（觀察概率）給定蛋白質(zhì)網(wǎng)絡(luò)中任意蛋白質(zhì)節(jié)點(diǎn)u與復(fù)合物Ct之間的歸屬度M(u,Ct),t∈(1,N)，觀察概率為：

3.3 蛋白質(zhì)復(fù)合物識(shí)別算法

本文提出的蛋白質(zhì)復(fù)合物識(shí)別算法充分考慮了動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中前一時(shí)刻網(wǎng)絡(luò)拓?fù)鋵?duì)當(dāng)前時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)的影響以及網(wǎng)絡(luò)中節(jié)點(diǎn)和復(fù)合物的固有特點(diǎn)，建立HMM 來(lái)解決動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物識(shí)別問(wèn)題。在當(dāng)前時(shí)刻受到前一時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)影響的前提下，基于HMM 描述蛋白質(zhì)復(fù)合物與網(wǎng)絡(luò)個(gè)體間的相互關(guān)系，采用狀態(tài)鏈和觀察鏈分別表示蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物和節(jié)點(diǎn)信息，通過(guò)求解HMM 中的最優(yōu)狀態(tài)序列得到動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物。蛋白質(zhì)復(fù)合物識(shí)別的具體過(guò)程如算法2 所示。

算法2基于HMM 的蛋白質(zhì)復(fù)合物識(shí)別（HMMPC）

輸入：動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)G=

輸出：蛋白質(zhì)復(fù)合物。

1.基于IPC-MCE 算法[16]對(duì)進(jìn)行蛋白質(zhì)復(fù)合物的識(shí)別，得到初始的蛋白質(zhì)復(fù)合物C-ini；

3.在時(shí)刻t(2 ≤t≤T)，對(duì)構(gòu)建矩陣，并根據(jù)式（10）計(jì)算得到每個(gè)蛋白質(zhì)復(fù)合物的核心節(jié)點(diǎn)

5.根據(jù)式（12）計(jì)算時(shí)刻t的各個(gè)狀態(tài)轉(zhuǎn)移概率

6.根據(jù)式（13）計(jì)算時(shí)刻t的每個(gè)蛋白質(zhì)與各個(gè)復(fù)合物之間的歸屬度；

7.根據(jù)式（14）計(jì)算時(shí)刻t的每個(gè)蛋白質(zhì)與各個(gè)復(fù)合物之間的觀察概率；

8.采用維特比算法[17]來(lái)得到最優(yōu)狀態(tài)序列，即中的蛋白質(zhì)復(fù)合物；

9.令t=t+1，轉(zhuǎn)3。直到t>12 時(shí)，算法結(jié)束。

為了便于理解，下面給出關(guān)于算法2的細(xì)節(jié)說(shuō)明：

（1）在步驟1 中，IPC-MCE 算法是一種基于極大團(tuán)擴(kuò)展的蛋白質(zhì)復(fù)合物識(shí)別算法，主要應(yīng)用于靜態(tài)蛋白質(zhì)網(wǎng)絡(luò)中。該算法首先找到蛋白質(zhì)網(wǎng)絡(luò)中存在的極大團(tuán)（即全連通圖），并將其看作蛋白質(zhì)復(fù)合物的核心，然后通過(guò)定義核心與周圍鄰居節(jié)點(diǎn)的作用概率來(lái)對(duì)極大團(tuán)進(jìn)行擴(kuò)展，進(jìn)而識(shí)別出更多具有生物意義的蛋白質(zhì)復(fù)合物，該算法對(duì)輸入?yún)?shù)不敏感，且易于實(shí)現(xiàn)。

（2）在步驟2 中，假定任意的蛋白質(zhì)節(jié)點(diǎn)其初始狀態(tài)概率分布為隨機(jī)分布，即認(rèn)為該節(jié)點(diǎn)在初始時(shí)刻進(jìn)入到某個(gè)蛋白復(fù)合網(wǎng)的概率是隨機(jī)的。

（3）在步驟3 中，構(gòu)建矩陣的目的是為了描述出蛋白質(zhì)節(jié)點(diǎn)與復(fù)合物之間的關(guān)系。具體而言，對(duì)于來(lái)說(shuō)，矩陣中第i行第j列的元素取值為：

3.4 算法復(fù)雜度分析

如算法2 所示，假設(shè)n為蛋白質(zhì)子網(wǎng)中蛋白質(zhì)節(jié)點(diǎn)的數(shù)目，m為蛋白質(zhì)子網(wǎng)中邊的數(shù)目，N為初始蛋白質(zhì)復(fù)合物的數(shù)目。首先，根據(jù)文獻(xiàn)[16]可知，在步驟1 中采用IPC-MCE 算法識(shí)別初始蛋白質(zhì)復(fù)合物C-ini的復(fù)雜度為O(nmμ+μ2d2)，其中μ是規(guī)模大于等于3 的全連通圖的個(gè)數(shù)，d是最大的稠密子圖規(guī)模；步驟2～步驟3 的復(fù)雜度為O(n)；步驟4 針對(duì)每個(gè)蛋白質(zhì)復(fù)合物進(jìn)行操作，但最終仍是對(duì)每個(gè)蛋白質(zhì)節(jié)點(diǎn)進(jìn)行處理，其復(fù)雜度仍為O(n)；步驟5～步驟7 的復(fù)雜度為O(n×N)；步驟8 中的Viterbi 算法采用遞歸調(diào)用來(lái)得到最優(yōu)序列，其復(fù)雜度為O(n2×lgn)；步驟9 中對(duì)步驟3～步驟8 中的操作重復(fù)進(jìn)行11 次，該步驟的復(fù)雜度為一常數(shù)。綜上所述，本文提出的蛋白質(zhì)復(fù)合物識(shí)別算法（HMM-PC）的復(fù)雜度為O(nmμ+μ2d2)+O(n)+O(n×N)+O(n2×lgn)，它屬于多項(xiàng)式時(shí)間，這表明HMM-PC 算法完全可以高效地識(shí)別大規(guī)模蛋白質(zhì)網(wǎng)絡(luò)中的復(fù)合物。

4 實(shí)驗(yàn)

用Python 語(yǔ)言實(shí)現(xiàn)了HMM-PC 算法，在一臺(tái)8核16 線程的計(jì)算機(jī)上進(jìn)行了實(shí)驗(yàn)。其中，處理器為Intel CoreTMi5-1035G1 CPU@1.00 GHz，內(nèi)存為8 GB，操作系統(tǒng)為64 位的Windows10 家庭中文版。為了驗(yàn)證HMM-PC 的有效性，在多個(gè)數(shù)據(jù)集上將HMM-PC算法與目前較為典型的蛋白質(zhì)復(fù)合物識(shí)別算法IPCTFC&ACC[8]、DCA[9]、IPC-DGD[10]和IFPA[11]進(jìn)行了性能比較。為了保證不同算法之間識(shí)別結(jié)果對(duì)比的客觀性和有效性，這些典型算法中涉及到的相關(guān)參數(shù)沿用原文作者在論文實(shí)驗(yàn)中的設(shè)置，在此不做任何修改。

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

本文采用了DIP 數(shù)據(jù)集、MIPS 數(shù)據(jù)集[18]和CYC2008 數(shù)據(jù)集[19]作為測(cè)試對(duì)象。其中，DIP 數(shù)據(jù)使用的是DIP20170205 版本。去掉自相互作用和重復(fù)相互作用后，該網(wǎng)絡(luò)中有4 995 個(gè)蛋白質(zhì)和21 554 條邊，如圖3 所示；MIPS 數(shù)據(jù)集在去除了其中包含的自相互作用和冗余的相互作用后，最終的相互作用網(wǎng)絡(luò)包括4 546 個(gè)酵母蛋白質(zhì)和12 319 對(duì)可靠的相互作用。CYC2008 數(shù)據(jù)中則包含了408 個(gè)通過(guò)生物方法預(yù)測(cè)到的蛋白質(zhì)復(fù)合物，每個(gè)復(fù)合物包含兩個(gè)或兩個(gè)以上的蛋白質(zhì)，可用于評(píng)估挖掘的蛋白質(zhì)復(fù)合物。

4.2 評(píng)價(jià)指標(biāo)

為了綜合衡量HMM-PC 算法的優(yōu)越性，本文采用如下的幾種指標(biāo)來(lái)評(píng)價(jià)多種不同的蛋白質(zhì)復(fù)合物識(shí)別算法的性能：

（1）查全率（Recall）、查準(zhǔn)率（Precision）和F-measure值的計(jì)算公式如下：

Fig.3 Example of protein network in DIP圖3 DIP 中的蛋白質(zhì)網(wǎng)絡(luò)示例

其中，ER表示HMM-PC 算法識(shí)別的蛋白質(zhì)復(fù)合物；RR表示通過(guò)生物實(shí)驗(yàn)技術(shù)測(cè)得的蛋白質(zhì)復(fù)合物；MNM(ER,RR)表示ER和RR之間的最大匹配數(shù)目。綜合考慮查全率和查準(zhǔn)率兩方面，可得F-measure 的計(jì)算公式為：

（2）功能富集程度。文中通過(guò)計(jì)算蛋白質(zhì)復(fù)合物的P-value 值來(lái)衡量它對(duì)某個(gè)功能的富集程度，其計(jì)算公式[20]為：

其中，N表示蛋白質(zhì)網(wǎng)絡(luò)的規(guī)模；PN表示蛋白質(zhì)復(fù)合物中的蛋白質(zhì)數(shù)量；λ表示蛋白質(zhì)復(fù)合物中具有某項(xiàng)功能的蛋白質(zhì)數(shù)量；F表示PPIN 中具有該功能的蛋白質(zhì)數(shù)量。一般而言，P-value 值越小，則表明識(shí)別的蛋白質(zhì)復(fù)合物是隨機(jī)具有這種功能的概率越低，即蛋白質(zhì)復(fù)合物更具有生物學(xué)意義。

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

4.3.1 HMM-PC 算法與其他算法的比較

為了準(zhǔn)確地分析HMM-PC 算法在文中構(gòu)建的動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)上識(shí)別復(fù)合物的性能，將HMM-PC 算法與IPC-TFC&ACC 算法、DCA 算法、IPC-DGD 算法和IFPA 算法在DIP 數(shù)據(jù)集和MIPS 數(shù)據(jù)集上進(jìn)行了性能比較。文中對(duì)每一種算法都在所構(gòu)建的每個(gè)動(dòng)態(tài)子網(wǎng)上進(jìn)行復(fù)合物識(shí)別，對(duì)于最終識(shí)別得到的復(fù)合物都采用文獻(xiàn)[19]的后處理方式進(jìn)行過(guò)濾，去掉重復(fù)的、包含蛋白質(zhì)數(shù)量少于2 的復(fù)合物。表1 和表2分別列出了各種算法在DIP 數(shù)據(jù)集和MIPS 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。

Table 1 Performance comparison of each algorithm on DIP data set表1 各個(gè)算法在DIP 數(shù)據(jù)集上的性能比較

Table 2 Performance comparison of each algorithm on MIPS data set表2 各個(gè)算法在MIPS 數(shù)據(jù)集上的性能比較

從表1 和表2 的結(jié)果可以看到，HMM-PC 算法在兩種數(shù)據(jù)集上的查全率和查準(zhǔn)率都要優(yōu)于另外的四種算法。在DIP數(shù)據(jù)集上，HMM-PC算法的F-measure值要比IPC-TFC&ACC、DCA、IPC-DGD 和IFPA 分別高約43%、32%、23%和11%。在MIPS 數(shù)據(jù)集上，HMM-PC 算法的F-measure 值要比IPC-TFC&ACC、DCA、IPC-DGD 和IFPA 分別高約41%、35%、28%和14%。這主要是因?yàn)椋海?）文中在采用基因表達(dá)數(shù)據(jù)構(gòu)建12 個(gè)動(dòng)態(tài)蛋白質(zhì)子網(wǎng)的基礎(chǔ)上，進(jìn)一步使用了共享功能注釋、共享結(jié)構(gòu)域和連接強(qiáng)度等因子來(lái)對(duì)蛋白質(zhì)網(wǎng)絡(luò)進(jìn)行加權(quán)，更為準(zhǔn)確地衡量了蛋白質(zhì)之間的真實(shí)相互作用關(guān)系；（2）HMM-PC 算法將蛋白質(zhì)復(fù)合物的識(shí)別問(wèn)題轉(zhuǎn)為隱馬爾科夫模型中的最優(yōu)序列發(fā)現(xiàn)問(wèn)題，通過(guò)蛋白質(zhì)復(fù)合物核心節(jié)點(diǎn)的計(jì)算、狀態(tài)轉(zhuǎn)移概率、觀察概率和歸屬度等的計(jì)算，有效地刻畫了蛋白質(zhì)在其整個(gè)動(dòng)態(tài)變化生命周期過(guò)程中的歸屬情況，降低了噪聲數(shù)據(jù)和網(wǎng)絡(luò)動(dòng)態(tài)變化對(duì)復(fù)合物識(shí)別帶來(lái)的影響，因此取得了比其他算法更優(yōu)的識(shí)別結(jié)果。

4.3.2 魯棒性分析

下面以DIP 數(shù)據(jù)集為例來(lái)測(cè)試HMM-PC 算法的魯棒性。在實(shí)驗(yàn)中通過(guò)隨機(jī)地增加和刪除蛋白質(zhì)網(wǎng)絡(luò)中邊的數(shù)目來(lái)模擬DIP 數(shù)據(jù)中包含的假陽(yáng)性和假陰性，實(shí)驗(yàn)結(jié)果如圖4 所示。其中，圖4 左邊的Y軸表示在增加邊的比例（假陽(yáng)性）情況下測(cè)得的Fmeasure 值；右邊的Y軸表示在刪除邊的比例（假陰性）情況下測(cè)得的F-measure 值。從圖4 可以看到，隨著數(shù)據(jù)中包含的假陽(yáng)性和假陰性的增加，HMM-PC算法的F-measure 值雖然有微弱的下降，但下降幅度不超過(guò)2%，這表明HMM-PC 算法具有較好的抗噪能力，魯棒性較強(qiáng)。

Fig.4 Robustness analysis of HMM-PC algorithm圖4 HMM-PC 算法的魯棒性分析

4.3.3 HMM-PC 算法的功能富集分析

為了進(jìn)一步驗(yàn)證HMM-PC 算法識(shí)別的蛋白質(zhì)復(fù)合物是否具有生物學(xué)意義，借助于TermFinder[21]工具（https://omictools.com/go-termfinder-tool）來(lái)計(jì)算文中構(gòu)建的12 個(gè)時(shí)刻蛋白質(zhì)子網(wǎng)中的蛋白質(zhì)復(fù)合物的Pvalue 值。為了保證對(duì)比的公平性，僅考慮至少包含10個(gè)蛋白質(zhì)的蛋白質(zhì)復(fù)合物。表3分別給出了五種不同算法識(shí)別的蛋白質(zhì)復(fù)合物的P-value 在[0，1E-10]，(1E-10，1E-5]，(1E-5，1E-2]和(1E-2，1E+0]區(qū)間分布的百分比情況。從表3 可以看到，IPC-TFC&ACC 算法、DCA 算法、IPC-DGD 算法和IFPA 算法識(shí)別的蛋白質(zhì)復(fù)合物位于區(qū)間[0，1E-5]的比例分別為85.4%、75.1%、79.9%和87.7%，而HMM-PC 算法識(shí)別的蛋白質(zhì)復(fù)合物位于區(qū)間[0，1E-5]的比例高達(dá)93%。由此可見(jiàn)，與其他四種算法相比，通過(guò)HMM-PC 算法識(shí)別的蛋白質(zhì)復(fù)合物在生物意義方面具有明顯的優(yōu)勢(shì)。

Table 3 Functional enrichment analysis of protein complexes identified by different algorithms表3 不同算法識(shí)別的蛋白質(zhì)復(fù)合物的功能富集性分析

4.3.4 HMM-PC 算法的效率分析

最后，為了進(jìn)一步衡量HMM-PC 算法的優(yōu)越性，對(duì)各種蛋白質(zhì)復(fù)合物識(shí)別的運(yùn)行時(shí)間在DIP 數(shù)據(jù)集和MIPS 數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果如圖5 所示。

Fig.5 Comparison of running time of each algorithm圖5 各個(gè)算法的運(yùn)行時(shí)間比較

從圖5 可以看到，IPC-DGD 算法的運(yùn)行時(shí)間最長(zhǎng)，DCA 算法次之。而本文提出的HMM-PC 算法在兩種數(shù)據(jù)集上的運(yùn)行時(shí)間大多要遠(yuǎn)遠(yuǎn)低于其他四種算法，僅有IFPA 算法在DIP 數(shù)據(jù)集上的效率略高于HMM-PC 算法。這主要是因?yàn)镠MM-PC 算法采用動(dòng)態(tài)規(guī)劃的思路來(lái)識(shí)別復(fù)合物，它將蛋白質(zhì)復(fù)合物問(wèn)題建模為最優(yōu)序列發(fā)現(xiàn)問(wèn)題，通過(guò)多種概率的計(jì)算來(lái)確定蛋白質(zhì)所屬?gòu)?fù)合物的歸屬，避免了大量重復(fù)計(jì)算。此外，HMM-PC 算法在運(yùn)行過(guò)程中沒(méi)有涉及到額外參數(shù)的反復(fù)調(diào)整，使得算法的計(jì)算量較低，并使用整個(gè)序列的上下文來(lái)做判斷，從而對(duì)包含“噪音”的序列也能進(jìn)行良好的分析?？偟膩?lái)說(shuō)，HMMPC 算法具有不錯(cuò)的運(yùn)行效率，可以快速準(zhǔn)確地識(shí)別蛋白質(zhì)復(fù)合物，可以推廣應(yīng)用到解決其他復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)、子圖挖掘等問(wèn)題，具有普適意義。

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

在動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)中如何準(zhǔn)確且高效地識(shí)別蛋白質(zhì)復(fù)合物是目前生物信息學(xué)研究中的熱點(diǎn)之一。文中首先利用蛋白質(zhì)的基因表達(dá)值、共享功能注釋信息、共享結(jié)構(gòu)域信息和連接強(qiáng)度來(lái)構(gòu)建加權(quán)的動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)；然后在此基礎(chǔ)上將蛋白質(zhì)復(fù)合物識(shí)別問(wèn)題建模為基于隱馬爾科夫模型的最優(yōu)序列發(fā)現(xiàn)問(wèn)題，并采用維特比算法進(jìn)行求解；最后在多個(gè)生物數(shù)據(jù)集上驗(yàn)證了本文算法的有效性。在下一步工作中，將對(duì)未知蛋白質(zhì)的功能進(jìn)行預(yù)測(cè)研究，考慮到圖卷積理論在處理大圖數(shù)據(jù)上的優(yōu)勢(shì)，擬提出一種基于圖卷積神經(jīng)網(wǎng)絡(luò)的蛋白質(zhì)功能預(yù)測(cè)算法。