基于模體中心結構的蛋白質復合物識別算法

夏雪飛, 王銘杰, 吳佳楠

(1. 長春大學 量子信息實驗室, 長春 130022； 2. 吉林交通職業技術學院 交通信息學院, 長春 130012)

蛋白質是生命活動的執行者, 生物體內蛋白質所有相互作用組成大規模網絡, 即蛋白質相互作用網絡PPI(protein-protein interaction network)[1], 可用含點集和邊集的無向圖表示. 蛋白質相互作用網絡具有模塊化特征, 模塊內部的蛋白質有緊密的拓撲和功能聯系, 這些模塊被稱為蛋白質復合物PC(protein complex)[2]. 在PPI網絡中檢測蛋白質復合物有助于探索生命活動過程中的未知蛋白質功能、解釋特定的生物進程, 對于疾病診斷和藥品研發具有重要意義[3].

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

網絡模體(network motif)是復雜網絡演化的重要拓撲結構[12], 其代表了復雜系統中的重要功能單元, 定義為復雜網絡中在不同位置重復出現的特定相互連接模式, 出現頻次顯著地高于隨機期望[13]. 如果一個子圖在實際網絡中出現的頻次高于隨機網絡中出現的平均頻次, 則該子圖為模體. 蛋白質相互作用網絡中存在具有層次模塊化特性的模體結構[14-15]. Wuchty等[16]研究表明, 模體成員蛋白比非模體成員蛋白在進化上更具有保守性, 研究結果暗示模體可能是網絡中進化保守的拓撲單元; Lee等[17]研究表明, 不同的模體模式所承受的進化約束顯著不同, 這種綜合了拓撲和功能的模體模式能更有效地表征PPI網絡中進化保守的拓撲單元, 具有重要的生物學意義.

鑒于網絡模體具有的進化保守特性, 本文提出一種新的以網絡模體作為核心節點組的蛋白質復合物識別算法MCSS(motif central structure searching). 首先, 通過模擬數據實驗驗證該算法的可行性及計算準確性； 然后, 將本文算法應用于真實蛋白質相互作用網絡數據進行測試, 并對識別的復合物進行富集分析, 發現了一些具有顯著生物學意義的蛋白質復合物, 驗證了算法的有效性; 最后, 為更直觀地表達模體中心結構的蛋白質復合物結構體征, 將平面型二維網絡拓撲進行三維立體轉化.

1 模型及相關定義

1.1 中心模體

在蛋白質相互作用網絡中, 蛋白質對應節點, 蛋白質之間的相互作用對應節點之間的連線. 網絡模體是指出現頻次較高的子圖模式. 圖1為PPI網絡中所有可能的3階模體拓撲和4階模體拓撲. 由于蛋白質相互作用無方向性, 所以對于3節點模體, 共有2種不同的連接模式, 而對于4節點模體, 共有6種不同的連接模式.

圖1 PPI網絡中的節點模體拓撲Fig.1 Node motif topology in PPI networks

1.2 中心模體三維轉化

為更直觀地表達本文算法所識別的復合物結構體特征, 本文嘗試將二維的復合物網絡拓撲進行三維轉化, 轉化方式如圖2所示.

圖2 蛋白質復合物立體轉化示意圖Fig.2 Schematic diagram of stereo transformation of protein complexes

1.3 相關定義

將整個蛋白質相互作用拓撲抽象為一個無向圖, 即統計學中點與邊的集合M=(P,E), 其中M為蛋白質相互作用網絡圖,P為M中的任意一個點,E表示M中任意兩個點P的關聯.

定義1(中心結構體飽和度) 具有相同節點的模體拓撲中, 節點間相互作用關系最多的模體結構飽和度最高, 如圖1(B)中最后一個模體.

定義2(關聯極限值) 限定計算范圍為選定的中心節點Y和中心節點的直接鄰居節點Xn共同構成中心結構體NL； 設n為一個以Y為中心節點的蛋白質復合物NL的蛋白質節點數,N為蛋白質復合物的相互作用極限關聯值, 則飽和度最高的情形為

N=n(n-1)/2,

(1)

即復合物中每個蛋白質分子與其余蛋白質都有相互作用關系.

定義3(進化保守度) 為評估所識別蛋白質復合物的有效性, 本文為每個蛋白質復合物定義一個R值, 命名為進化保守度.R值越大則該蛋白質復合物被識別的概率越高. 設m為中心結構體NL中除中心節點外所有節點的實際相互作用關聯數, 則R可表示為

R=(m/N)×100%.

(2)

2 蛋白質復合物識別算法

MCSS算法將模體作為蛋白質復合物的中心結構體, 并基于中心結構體進行二層節點擴充. 算法步驟如下：

1) 數據預處理, 構建PPI網絡拓撲；

2) 模體中心節點篩選；

3) 中心結構體識別；

4) 二層節點擴充；

5) 蛋白質復合物識別.

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

(3)

其中v和k需滿足

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

(4)

INvk≥Tin,

(5)

式中SP(v,u)表示蛋白質v和u之間的最短距離,Vc表示復合物內的蛋白質節點集,l為用戶設置的正整數；Tin取值區間為(0,1).

算法包括3個子過程： 計算節點權重、選擇種子和擴充簇. 先計算圖中每條邊的權重, 對每個節點所有連接邊的權重求和, 得出節點權重, 并根據權重排序, 形成種子隊列； 逐個擴充每個種子節點, 擴充的優先權由連接邊數和邊的權重和決定, 邊數越多, 權重和越大, 優先權越高[18]. MCSS算法過程描述如下.

算法1MCSS算法.

輸入:M=(P,E) //蛋白質相互作用網絡

輸出: var center_noden//中心節點n

var struct_listn//中心結構體除中心節點外的所有節點集合

var extension_listn//中心結構體擴展節點集合

varRn//中心節點n對應的鄰居節點的實際關聯值與關聯極限值的比率

Result={ center_noden: {

struct_listn: [node1,node2,…,noden,

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

Rn}}

Program:

1) func neibhbor(node) //計算當前節點node的鄰居節點集合

2) varRmax//中心節點的鄰居節點的關聯極限值

3) var node //普通節點

4) var neib_node //中心節點的鄰居節點集合

5) var center_node //中心節點

6) for center_nodeiinMdo

7)n=length(neib_node) //中心節點的鄰居節點數

8)m=length(neib_edage) //中心節點的鄰居節點的關聯數

9) ifn< 3 do

10) continue

11) else

12)Rmax=(n2-n)/2 //中心節點的鄰居節點的關聯極限值

13) Result[center_nodei].Ri=m/Rmax//關聯比率

14) Result[center_nodei].struct_listi=neib_node //中心節點的鄰居節點集合

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 實 驗

3.1 模擬數據實驗

創建模擬數據集SimuPPIData1用MCSS算法進行計算, 共得到32個有效復合物, 篩選保守度排名前10的復合物(飽和度大于50%)轉化為三維結構, 如表1所示, 其中紅色節點和黃色節點共同組成中心結構體, 藍色節點為二層擴展節點,R值為進化保守度.

為驗證MCSS算法的計算有效性, 參照PPI數據結構特征, 創建模擬數據集SimuPPIData2, 抽取部分數據生成PPI網絡拓撲如圖3所示. 圖3中包含了8個特征顯著的中心結構體, 4個高飽和度, 4個低飽和度, 經計算均被算法識別.

表1 SimuPPIData中排名前10的復合物結構

圖3 SimuPPIData網絡拓撲Fig.3 SimuPPIData network topology

3.2 真實數據實驗

為驗證算法的有效性, 本文使用酵母蛋白質數據對算法進行測試驗證, 實驗數據源于STRING數據庫(https://string-db.org), 整組數據共9 687個節點, 168 974對關聯, 經MCSS計算, 共識別出復合物集團1 128個, 對排名前5的復合物進行富集分析, 結果列于表2.

表2 排名前5的酵母復合物數據

生物數據庫系統會為每個蛋白質復合物集團返回一個p值, 如果p值較小, 則表示該集團具有顯著的生物學意義.p值計算公式為

(6)

其中N為蛋白質相互作用網絡的規模,C為蛋白質復合物中的蛋白質數,k為蛋白質復合物中含有某個功能的蛋白質數量,F為蛋白質相互作用網絡中含有該功能的蛋白質數量[18]. 實驗結果表明, 進化保守度R值越大集團p值越小, 對應的集團生物學意義越顯著, 間接有效地證明了本文算法的有效性.

綜上所述, 本文提出了一種新的以網絡模體作為核心節點組的蛋白質復合物識別算法, 該算法根據蛋白質相互作用網絡的拓撲特性, 將模體作為蛋白質復合物的中心結構體, 并基于中心結構體進行二層節點擴充, 能準確有效地識別蛋白質復合物. 通過模擬數據和酵母蛋白數據驗證了算法的計算準確性和識別有效性.