基于模體中心結(jié)構(gòu)的蛋白質(zhì)復(fù)合物識(shí)別算法

夏雪飛, 王銘杰, 吳佳楠

(1. 長春大學(xué) 量子信息實(shí)驗(yàn)室, 長春 130022； 2. 吉林交通職業(yè)技術(shù)學(xué)院 交通信息學(xué)院, 長春 130012)

蛋白質(zhì)是生命活動(dòng)的執(zhí)行者, 生物體內(nèi)蛋白質(zhì)所有相互作用組成大規(guī)模網(wǎng)絡(luò), 即蛋白質(zhì)相互作用網(wǎng)絡(luò)PPI(protein-protein interaction network)[1], 可用含點(diǎn)集和邊集的無向圖表示. 蛋白質(zhì)相互作用網(wǎng)絡(luò)具有模塊化特征, 模塊內(nèi)部的蛋白質(zhì)有緊密的拓?fù)浜凸δ苈?lián)系, 這些模塊被稱為蛋白質(zhì)復(fù)合物PC(protein complex)[2]. 在PPI網(wǎng)絡(luò)中檢測蛋白質(zhì)復(fù)合物有助于探索生命活動(dòng)過程中的未知蛋白質(zhì)功能、解釋特定的生物進(jìn)程, 對于疾病診斷和藥品研發(fā)具有重要意義[3].

通過實(shí)驗(yàn)獲得的蛋白質(zhì)復(fù)合物十分有限, 高通量技術(shù)產(chǎn)生了大量的蛋白質(zhì)相互作用數(shù)據(jù), 為使用計(jì)算方法識(shí)別蛋白質(zhì)復(fù)合物提供了極大幫助. 通常方法是將蛋白質(zhì)相互作用數(shù)據(jù)轉(zhuǎn)化為用圖描述的蛋白質(zhì)網(wǎng)絡(luò), 蛋白質(zhì)復(fù)合物對應(yīng)圖中的稠密子圖, 采用圖分析方法對蛋白質(zhì)復(fù)合物進(jìn)行識(shí)別, 例如: King等[4]提出了一種代價(jià)函數(shù)的聚類算法RNSC(restricted neighborhood search clustering), 該算法是一種典型的基于圖劃分方法； Palla等[5]提出了一種團(tuán)滲透算法CPM(clique percolation method), 該算法是一種基于密度的局部搜索方法； 文獻(xiàn)[6]中的G-N算法是一種基于層次聚類的方法. 近年, 人們基于核心-附屬蛋白質(zhì)的結(jié)構(gòu)[7]提出了一些新型算法, 如COACH(core-attachment)[8]和Core方法(a novel core-attachment based method)[9]等. 由于在靜態(tài)網(wǎng)絡(luò)上挖掘蛋白質(zhì)復(fù)合物無法充分體現(xiàn)功能模塊的內(nèi)在結(jié)構(gòu)和動(dòng)態(tài)屬性, 因此一些研究人員結(jié)合動(dòng)態(tài)生物信息構(gòu)造蛋白質(zhì)網(wǎng)絡(luò), 如Tang等[10]構(gòu)建了動(dòng)態(tài)蛋白質(zhì)網(wǎng)絡(luò)； Ouyang等[11]提出了一種時(shí)序平緩重疊復(fù)合物檢測機(jī)制, 可在動(dòng)態(tài)網(wǎng)絡(luò)中檢測瞬時(shí)的蛋白質(zhì)復(fù)合物. 但目前多數(shù)方法都在復(fù)合物中心節(jié)點(diǎn)的選擇上主要依賴于圖密度或節(jié)點(diǎn)關(guān)聯(lián)度等信息, 復(fù)合物的中心通常設(shè)定為一個(gè)單節(jié)點(diǎn), 即使算法本身具備高效的子網(wǎng)挖掘性能, 而識(shí)別的蛋白質(zhì)復(fù)合物卻常不具備顯著的生物學(xué)意義.

網(wǎng)絡(luò)模體(network motif)是復(fù)雜網(wǎng)絡(luò)演化的重要拓?fù)浣Y(jié)構(gòu)[12], 其代表了復(fù)雜系統(tǒng)中的重要功能單元, 定義為復(fù)雜網(wǎng)絡(luò)中在不同位置重復(fù)出現(xiàn)的特定相互連接模式, 出現(xiàn)頻次顯著地高于隨機(jī)期望[13]. 如果一個(gè)子圖在實(shí)際網(wǎng)絡(luò)中出現(xiàn)的頻次高于隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的平均頻次, 則該子圖為模體. 蛋白質(zhì)相互作用網(wǎng)絡(luò)中存在具有層次模塊化特性的模體結(jié)構(gòu)[14-15]. Wuchty等[16]研究表明, 模體成員蛋白比非模體成員蛋白在進(jìn)化上更具有保守性, 研究結(jié)果暗示模體可能是網(wǎng)絡(luò)中進(jìn)化保守的拓?fù)鋯卧? Lee等[17]研究表明, 不同的模體模式所承受的進(jìn)化約束顯著不同, 這種綜合了拓?fù)浜凸δ艿哪ｓw模式能更有效地表征PPI網(wǎng)絡(luò)中進(jìn)化保守的拓?fù)鋯卧? 具有重要的生物學(xué)意義.

鑒于網(wǎng)絡(luò)模體具有的進(jìn)化保守特性, 本文提出一種新的以網(wǎng)絡(luò)模體作為核心節(jié)點(diǎn)組的蛋白質(zhì)復(fù)合物識(shí)別算法MCSS(motif central structure searching). 首先, 通過模擬數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證該算法的可行性及計(jì)算準(zhǔn)確性； 然后, 將本文算法應(yīng)用于真實(shí)蛋白質(zhì)相互作用網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測試, 并對識(shí)別的復(fù)合物進(jìn)行富集分析, 發(fā)現(xiàn)了一些具有顯著生物學(xué)意義的蛋白質(zhì)復(fù)合物, 驗(yàn)證了算法的有效性; 最后, 為更直觀地表達(dá)模體中心結(jié)構(gòu)的蛋白質(zhì)復(fù)合物結(jié)構(gòu)體征, 將平面型二維網(wǎng)絡(luò)拓?fù)溥M(jìn)行三維立體轉(zhuǎn)化.

1 模型及相關(guān)定義

1.1 中心模體

在蛋白質(zhì)相互作用網(wǎng)絡(luò)中, 蛋白質(zhì)對應(yīng)節(jié)點(diǎn), 蛋白質(zhì)之間的相互作用對應(yīng)節(jié)點(diǎn)之間的連線. 網(wǎng)絡(luò)模體是指出現(xiàn)頻次較高的子圖模式. 圖1為PPI網(wǎng)絡(luò)中所有可能的3階模體拓?fù)浜?階模體拓?fù)? 由于蛋白質(zhì)相互作用無方向性, 所以對于3節(jié)點(diǎn)模體, 共有2種不同的連接模式, 而對于4節(jié)點(diǎn)模體, 共有6種不同的連接模式.

圖1 PPI網(wǎng)絡(luò)中的節(jié)點(diǎn)模體拓?fù)銯ig.1 Node motif topology in PPI networks

1.2 中心模體三維轉(zhuǎn)化

為更直觀地表達(dá)本文算法所識(shí)別的復(fù)合物結(jié)構(gòu)體特征, 本文嘗試將二維的復(fù)合物網(wǎng)絡(luò)拓?fù)溥M(jìn)行三維轉(zhuǎn)化, 轉(zhuǎn)化方式如圖2所示.

圖2 蛋白質(zhì)復(fù)合物立體轉(zhuǎn)化示意圖Fig.2 Schematic diagram of stereo transformation of protein complexes

1.3 相關(guān)定義

將整個(gè)蛋白質(zhì)相互作用拓?fù)涑橄鬄橐粋€(gè)無向圖, 即統(tǒng)計(jì)學(xué)中點(diǎn)與邊的集合M=(P,E), 其中M為蛋白質(zhì)相互作用網(wǎng)絡(luò)圖,P為M中的任意一個(gè)點(diǎn),E表示M中任意兩個(gè)點(diǎn)P的關(guān)聯(lián).

定義1(中心結(jié)構(gòu)體飽和度) 具有相同節(jié)點(diǎn)的模體拓?fù)渲? 節(jié)點(diǎn)間相互作用關(guān)系最多的模體結(jié)構(gòu)飽和度最高, 如圖1(B)中最后一個(gè)模體.

定義2(關(guān)聯(lián)極限值) 限定計(jì)算范圍為選定的中心節(jié)點(diǎn)Y和中心節(jié)點(diǎn)的直接鄰居節(jié)點(diǎn)Xn共同構(gòu)成中心結(jié)構(gòu)體NL； 設(shè)n為一個(gè)以Y為中心節(jié)點(diǎn)的蛋白質(zhì)復(fù)合物NL的蛋白質(zhì)節(jié)點(diǎn)數(shù),N為蛋白質(zhì)復(fù)合物的相互作用極限關(guān)聯(lián)值, 則飽和度最高的情形為

N=n(n-1)/2,

(1)

即復(fù)合物中每個(gè)蛋白質(zhì)分子與其余蛋白質(zhì)都有相互作用關(guān)系.

定義3(進(jìn)化保守度) 為評(píng)估所識(shí)別蛋白質(zhì)復(fù)合物的有效性, 本文為每個(gè)蛋白質(zhì)復(fù)合物定義一個(gè)R值, 命名為進(jìn)化保守度.R值越大則該蛋白質(zhì)復(fù)合物被識(shí)別的概率越高. 設(shè)m為中心結(jié)構(gòu)體NL中除中心節(jié)點(diǎn)外所有節(jié)點(diǎn)的實(shí)際相互作用關(guān)聯(lián)數(shù), 則R可表示為

R=(m/N)×100%.

(2)

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

MCSS算法將模體作為蛋白質(zhì)復(fù)合物的中心結(jié)構(gòu)體, 并基于中心結(jié)構(gòu)體進(jìn)行二層節(jié)點(diǎn)擴(kuò)充. 算法步驟如下：

1) 數(shù)據(jù)預(yù)處理, 構(gòu)建PPI網(wǎng)絡(luò)拓?fù)洌?/p>

2) 模體中心節(jié)點(diǎn)篩選；

3) 中心結(jié)構(gòu)體識(shí)別；

4) 二層節(jié)點(diǎn)擴(kuò)充；

5) 蛋白質(zhì)復(fù)合物識(shí)別.

對于步驟4)中二層節(jié)點(diǎn)的擴(kuò)充計(jì)算, 主要采用基于距離測定的蛋白質(zhì)復(fù)合物識(shí)別算法(IPC-DM)的理念[18], 調(diào)整后融入本文算法. 該算法核心思想如下： 用|Vk|表示復(fù)合物內(nèi)部蛋白質(zhì)總量； |Evk|表示v與k作用邊數(shù)目, 則蛋白質(zhì)v與復(fù)合物k的相互作用概率為

(3)

其中v和k需滿足

SP(v,u)≤l,u∈Vc,

(4)

INvk≥Tin,

(5)

式中SP(v,u)表示蛋白質(zhì)v和u之間的最短距離,Vc表示復(fù)合物內(nèi)的蛋白質(zhì)節(jié)點(diǎn)集,l為用戶設(shè)置的正整數(shù)；Tin取值區(qū)間為(0,1).

算法包括3個(gè)子過程： 計(jì)算節(jié)點(diǎn)權(quán)重、選擇種子和擴(kuò)充簇. 先計(jì)算圖中每條邊的權(quán)重, 對每個(gè)節(jié)點(diǎn)所有連接邊的權(quán)重求和, 得出節(jié)點(diǎn)權(quán)重, 并根據(jù)權(quán)重排序, 形成種子隊(duì)列； 逐個(gè)擴(kuò)充每個(gè)種子節(jié)點(diǎn), 擴(kuò)充的優(yōu)先權(quán)由連接邊數(shù)和邊的權(quán)重和決定, 邊數(shù)越多, 權(quán)重和越大, 優(yōu)先權(quán)越高[18]. MCSS算法過程描述如下.

算法1MCSS算法.

輸入:M=(P,E) //蛋白質(zhì)相互作用網(wǎng)絡(luò)

輸出: var center_noden//中心節(jié)點(diǎn)n

var struct_listn//中心結(jié)構(gòu)體除中心節(jié)點(diǎn)外的所有節(jié)點(diǎn)集合

var extension_listn//中心結(jié)構(gòu)體擴(kuò)展節(jié)點(diǎn)集合

varRn//中心節(jié)點(diǎn)n對應(yīng)的鄰居節(jié)點(diǎn)的實(shí)際關(guān)聯(lián)值與關(guān)聯(lián)極限值的比率

Result={ center_noden: {

struct_listn: [node1,node2,…,noden,

extension_listn: [node1,node2,…,noden],

Rn}}

Program:

1) func neibhbor(node) //計(jì)算當(dāng)前節(jié)點(diǎn)node的鄰居節(jié)點(diǎn)集合

2) varRmax//中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的關(guān)聯(lián)極限值

3) var node //普通節(jié)點(diǎn)

4) var neib_node //中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合

5) var center_node //中心節(jié)點(diǎn)

6) for center_nodeiinMdo

7)n=length(neib_node) //中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)

8)m=length(neib_edage) //中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的關(guān)聯(lián)數(shù)

9) ifn< 3 do

10) continue

11) else

12)Rmax=(n2-n)/2 //中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的關(guān)聯(lián)極限值

13) Result[center_nodei].Ri=m/Rmax//關(guān)聯(lián)比率

14) Result[center_nodei].struct_listi=neib_node //中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合

15) endif

16) for nodejin Result[center_nodei].struct_listi

17) append(Result[center_nodei].extension_listi, neibhbor(nodej))

18) end for

19) end for

20) return Result.

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

3.1 模擬數(shù)據(jù)實(shí)驗(yàn)

創(chuàng)建模擬數(shù)據(jù)集SimuPPIData1用MCSS算法進(jìn)行計(jì)算, 共得到32個(gè)有效復(fù)合物, 篩選保守度排名前10的復(fù)合物(飽和度大于50%)轉(zhuǎn)化為三維結(jié)構(gòu), 如表1所示, 其中紅色節(jié)點(diǎn)和黃色節(jié)點(diǎn)共同組成中心結(jié)構(gòu)體, 藍(lán)色節(jié)點(diǎn)為二層擴(kuò)展節(jié)點(diǎn),R值為進(jìn)化保守度.

為驗(yàn)證MCSS算法的計(jì)算有效性, 參照PPI數(shù)據(jù)結(jié)構(gòu)特征, 創(chuàng)建模擬數(shù)據(jù)集SimuPPIData2, 抽取部分?jǐn)?shù)據(jù)生成PPI網(wǎng)絡(luò)拓?fù)淙鐖D3所示. 圖3中包含了8個(gè)特征顯著的中心結(jié)構(gòu)體, 4個(gè)高飽和度, 4個(gè)低飽和度, 經(jīng)計(jì)算均被算法識(shí)別.

表1 SimuPPIData中排名前10的復(fù)合物結(jié)構(gòu)

圖3 SimuPPIData網(wǎng)絡(luò)拓?fù)銯ig.3 SimuPPIData network topology

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

為驗(yàn)證算法的有效性, 本文使用酵母蛋白質(zhì)數(shù)據(jù)對算法進(jìn)行測試驗(yàn)證, 實(shí)驗(yàn)數(shù)據(jù)源于STRING數(shù)據(jù)庫(https://string-db.org), 整組數(shù)據(jù)共9 687個(gè)節(jié)點(diǎn), 168 974對關(guān)聯(lián), 經(jīng)MCSS計(jì)算, 共識(shí)別出復(fù)合物集團(tuán)1 128個(gè), 對排名前5的復(fù)合物進(jìn)行富集分析, 結(jié)果列于表2.

表2 排名前5的酵母復(fù)合物數(shù)據(jù)

生物數(shù)據(jù)庫系統(tǒng)會(huì)為每個(gè)蛋白質(zhì)復(fù)合物集團(tuán)返回一個(gè)p值, 如果p值較小, 則表示該集團(tuán)具有顯著的生物學(xué)意義.p值計(jì)算公式為

(6)

其中N為蛋白質(zhì)相互作用網(wǎng)絡(luò)的規(guī)模,C為蛋白質(zhì)復(fù)合物中的蛋白質(zhì)數(shù),k為蛋白質(zhì)復(fù)合物中含有某個(gè)功能的蛋白質(zhì)數(shù)量,F為蛋白質(zhì)相互作用網(wǎng)絡(luò)中含有該功能的蛋白質(zhì)數(shù)量[18]. 實(shí)驗(yàn)結(jié)果表明, 進(jìn)化保守度R值越大集團(tuán)p值越小, 對應(yīng)的集團(tuán)生物學(xué)意義越顯著, 間接有效地證明了本文算法的有效性.

綜上所述, 本文提出了一種新的以網(wǎng)絡(luò)模體作為核心節(jié)點(diǎn)組的蛋白質(zhì)復(fù)合物識(shí)別算法, 該算法根據(jù)蛋白質(zhì)相互作用網(wǎng)絡(luò)的拓?fù)涮匦? 將模體作為蛋白質(zhì)復(fù)合物的中心結(jié)構(gòu)體, 并基于中心結(jié)構(gòu)體進(jìn)行二層節(jié)點(diǎn)擴(kuò)充, 能準(zhǔn)確有效地識(shí)別蛋白質(zhì)復(fù)合物. 通過模擬數(shù)據(jù)和酵母蛋白數(shù)據(jù)驗(yàn)證了算法的計(jì)算準(zhǔn)確性和識(shí)別有效性.