許睿,李琳芳,白林峰

（河南科技學院,河南新鄉(xiāng)453003）

基于節(jié)點關(guān)聯(lián)性的關(guān)鍵蛋白質(zhì)識別算法研究

許睿,李琳芳,白林峰

（河南科技學院,河南新鄉(xiāng)453003）

為提高蛋白質(zhì)網(wǎng)絡中關(guān)鍵蛋白質(zhì)識別的效率,提出一種基于節(jié)點關(guān)聯(lián)性的關(guān)鍵蛋白質(zhì)識別方法.方法在保持蛋白質(zhì)網(wǎng)絡拓撲結(jié)構(gòu)完整性的基礎(chǔ)上,兼顧了蛋白質(zhì)網(wǎng)絡局部特性,從蛋白質(zhì)節(jié)點關(guān)聯(lián)性的角度,具體衡量蛋白質(zhì)節(jié)點重要性,并采用節(jié)點失效法進行關(guān)鍵蛋白質(zhì)的識別.實驗分析證明了方法的有效性.

節(jié)點關(guān)聯(lián)性；蛋白質(zhì)網(wǎng)絡；關(guān)鍵蛋白質(zhì)；節(jié)點重要性

在蛋白質(zhì)網(wǎng)絡中,蛋白質(zhì)節(jié)點之間往往聯(lián)系密切,且關(guān)鍵蛋白質(zhì)不是唯一的,他們構(gòu)成一個集合,共同完成某種生命活動.隨著關(guān)鍵蛋白質(zhì)研究的深入,人們發(fā)現(xiàn)各種生物個體的蛋白質(zhì)網(wǎng)絡中,存在著一些共性,如生物體有自我修復的機制,少量的關(guān)鍵蛋白質(zhì)的缺失可能會致病,經(jīng)過細胞的自我修復可以恢復部分功能,但是大量的關(guān)鍵蛋白質(zhì)的缺失則后果嚴重,導致生物體致死或者致殘,無法恢復.可見,在蛋白質(zhì)網(wǎng)絡中,任何連通的蛋白質(zhì)節(jié)點之間都存在著相互依賴的關(guān)系.這種依賴關(guān)系普遍存在,但是有強弱之分,比如相鄰的蛋白質(zhì)節(jié)點之間依賴關(guān)系會比中心節(jié)點和邊緣節(jié)點之間依賴關(guān)系強很多,隨著蛋白質(zhì)節(jié)點對之間的路徑的增加,這種依賴關(guān)系逐漸減弱.因此,這種依賴關(guān)系最直接地反映在直接相連的鄰居蛋白質(zhì)節(jié)點之間.

在復雜網(wǎng)絡領(lǐng)域中,對于網(wǎng)絡中節(jié)點重要性的評價標準,主要是從兩個方面進行考慮：一是從局部特性的角度,主要的依據(jù)是節(jié)點的連接屬性,常用的測度有度中心性、聚集系數(shù)等；二是從全局特性的角度,主要的依據(jù)是節(jié)點的位置特性,比較典型的測度有特征向量中心性、信息中心性、介數(shù)中心性等.本文提出一個新的算法,利用蛋白質(zhì)節(jié)點之間的關(guān)聯(lián)性,通過兼顧局部和全局兩個方面的特性,進行關(guān)鍵蛋白質(zhì)的識別.

1 相關(guān)定義說明

1.1 度中心性

節(jié)點的度中心性（Degree Centrality,DC）也就是節(jié)點的連接度,表示與該節(jié)點直接相鄰的其他節(jié)點的數(shù)目[1].

式（1）中,Cij表示蛋白質(zhì)網(wǎng)絡鄰接矩陣中節(jié)點j到節(jié)點i的對應元素值.節(jié)點的度是最簡單、最直觀的中心性測度,當節(jié)點度越大時,反映出該節(jié)點參與的相互作用越多,則該節(jié)點對于整個蛋白質(zhì)網(wǎng)絡產(chǎn)生的影響也越大.

1.2 接近度中心性

節(jié)點的接近度中心性（Closeness Centrality,CC）通過衡量該節(jié)點對于其他節(jié)點的依賴程度,反映該節(jié)點在整個網(wǎng)絡中所處的中心程度[2],接近度中心性定義如下

1.3 介數(shù)中心性

節(jié)點的介數(shù)中心性（Betweenness Centrality,BC）指的是蛋白質(zhì)網(wǎng)絡中經(jīng)過某個節(jié)點v的最短路徑在所有最短路徑數(shù)中所占有的比例[3],公式如下

1.4 特征向量中心性

2 節(jié)點重要性評估及算法描述

2.1 節(jié)點重要性評估

在蛋白質(zhì)網(wǎng)絡中,可以作這樣的假設(shè),分化前細胞中的蛋白質(zhì)的部分功能會被分化后細胞中的蛋白質(zhì)繼承過去,會造成前者的重要性的部分減弱,后者的重要性相應的增強.在具體網(wǎng)絡中,后者的重要性之和可以用它們之間連線的多少來衡量,如果這些蛋白質(zhì)節(jié)點對之間的部分直接連接,則前者按照比例減少部分重要性；如果所有節(jié)點對之間都存在著直接連接,則可以完全替代前者的作用,前者的重要性會降到零.因此在蛋白質(zhì)網(wǎng)絡中,節(jié)點的重要性可以用公式（5）來表示.

2.2 算法描述

算法描述如下：

3 實驗及結(jié)果分析

實驗選取酵母蛋白質(zhì)網(wǎng)絡作為測試對象,該測試數(shù)據(jù)集包含2 361個節(jié)點和7 182對相互作用[5],將Essential Proteins數(shù)據(jù)集作為關(guān)鍵蛋白質(zhì)標準數(shù)據(jù)集,該標準數(shù)據(jù)集是收集和整理4個常用的生物數(shù)據(jù)庫（MIPS[6]、SGD[7]、DEG[8]、SGDP[9]）的數(shù)據(jù)得來的,包含有1 285個關(guān)鍵蛋白質(zhì).首先對Yeast數(shù)據(jù)集進行預處理,去除數(shù)據(jù)集中蛋白質(zhì)的自相互作用和冗余相互作用,得到該網(wǎng)絡的實驗數(shù)據(jù).之后,使用4種測度算法（度中心性DC、接近度中心CC、介數(shù)中心性BC和特征向量中心性EC）和本算法分別對于實驗所選取的Yeast數(shù)據(jù)集進行關(guān)鍵蛋白質(zhì)識別.5種不同的算法得到不同的蛋白質(zhì)節(jié)點的重要性排序,每一個算法得到的結(jié)果按照降序排列,選擇不同規(guī)模的蛋白質(zhì)節(jié)點作為預測關(guān)鍵蛋白質(zhì),與關(guān)鍵蛋白質(zhì)標準數(shù)據(jù)集Essential Proteins進行對比,從而發(fā)掘該算法在不同規(guī)模下的預測準確率.

5種不同算法分別針對Yeast數(shù)據(jù)集進行節(jié)點重要性評價,選取TOP 1%的蛋白質(zhì)節(jié)點,即前24個蛋白質(zhì)節(jié)點,其編號如表1所示.

表1 DC、CC、BC、EC和本算法預測得到的TOP 1%蛋白質(zhì)節(jié)點編號Tab.1 Top 1%protein nodes predicted by DC,CC,BC,EC and the algorithm

在表1中,將5種不同算法得到的前24個蛋白質(zhì)節(jié)點編號與關(guān)鍵蛋白質(zhì)標準集進行匹配,得到5種算法的預測準確率分別為62.5%、41.67%、50%、33.3%、50%,本算法的預測準確率略低于DC,和BC的準確率相同,同時高于CC、EC.5種不同算法預測得到的前100個關(guān)鍵蛋白質(zhì)的交集見表2.

表2 依據(jù)不同算法得到的前100個預測關(guān)鍵蛋白質(zhì)交集的預測準確率Tab.2 The intersection of Top 100 essential proteins predicted by different algorithms%

由表2可知,5種算法預測的前100個蛋白質(zhì)與標準關(guān)鍵蛋白質(zhì)集進行比較,預測準確率分別為52%、48%、48%、43%、56%.本算法預測準確率高于其他4個算法,分別高出了4、8、8、13個百分點.且本算法的初步設(shè)想是兼顧蛋白質(zhì)節(jié)點在蛋白質(zhì)網(wǎng)絡中表現(xiàn)出的局部和全局兩方面的特性進行關(guān)鍵蛋白質(zhì)識別,根據(jù)蛋白質(zhì)網(wǎng)絡局部特性識別關(guān)鍵蛋白質(zhì)的諸多算法中,DC、BC算法是基于局部特性的經(jīng)典算法,DC算法度量的是節(jié)點參與相互作用的數(shù)量,BC算法度量的是節(jié)點保持網(wǎng)絡緊密連接的能力,并反映該蛋白質(zhì)節(jié)點是否處在蛋白質(zhì)網(wǎng)絡的樞紐位置.在表2中,可以發(fā)現(xiàn)本算法與DC、BC算法得到蛋白質(zhì)的重合率有所提高,反映出本算法在兼顧蛋白質(zhì)網(wǎng)絡的局部特性方面有所提高,完成了本實驗的初始設(shè)想.5種算法分別得到的蛋白質(zhì)個數(shù)見圖1,縱坐標表示各個算法識別出的關(guān)鍵蛋白質(zhì)的個數(shù),圖1-a～圖1-e表示由各個算法得到前24、120、240、360、480個蛋白質(zhì).

圖1 由DC、CC、BC、EC和本算法分別得到的關(guān)鍵蛋白質(zhì)個數(shù)Fig.1 The number of essential proteins detected by DC,CC,BC,EC and the Algorithm

由圖1可知,本算法在以上5個規(guī)模的樣本上預測準確率分別為50%、55.8%、52.9%、54.1%、53.1%.在TOP 5%、TOP 10%、TOP 15%、TOP 20%數(shù)據(jù)中,本算法的預測準確率均高于其他4種算法.一些研究表明有效的挖掘重要性前20%的數(shù)據(jù)對于準確預測關(guān)鍵蛋白質(zhì)是非常重要的[10],可見本算法在識別關(guān)鍵蛋白質(zhì)方面是可行的.

4 小結(jié)

本文在蛋白質(zhì)節(jié)點失效算法的基礎(chǔ)上,結(jié)合蛋白質(zhì)網(wǎng)絡節(jié)點的關(guān)聯(lián)性,提出基于節(jié)點關(guān)聯(lián)性的關(guān)鍵蛋白質(zhì)識別算法.在保存蛋白質(zhì)網(wǎng)絡拓撲結(jié)構(gòu)完整性基礎(chǔ)上,兼顧了蛋白質(zhì)網(wǎng)絡局部特性,改進了網(wǎng)絡中蛋白質(zhì)節(jié)點重要性的評價標準,該標準反映了生物細胞分化時蛋白質(zhì)節(jié)點的功能傳遞這一過程.實驗結(jié)果表明本算法對于關(guān)鍵蛋白質(zhì)的識別具有比較好的效果.

[1]Jeong H,Mason S P,Barabási A L,et al.Lethality and centrality in protein networks[J].Nature,2001,411（6833）：41-42.

[2]Wuchty S,Stadler P F.Centers of complex networks[J].Journal of Theoretical Biology,2003,223（1）：45-53.

[3]Wuchty S.Interaction and domain networks of yeast[J].Proteomics,2002,2（12）：1715-1723.

[4]Bonacich P.Power and centrality：A family of measures[J].The American Journal of Sociology,1987,92（5）：1170-1182.

[5]Pajek.Protein-protein interaction network in budding yeast[DB/OL].（2003-07-25）[2015-12-12].http：//vlado.fmf.uni-lj. si/pub/networks/data/bio/Yeast/Yeast.htm

[6]Mewes H W,Frishman D,Mayer K F X,et al.MIPS：analysis and annotation of proteins from whole genomes in 2005[J].Nucleic Acids Research,2006,34（Database issue）：D169-D172.

[7]Cherry J M,Adler C,Ball C,et al.SGD：Saccharomyces Genome Database[J].Nucleic Acids Research,1998,26（1）：73-79.

[8]Zhang R,Lin Y.DEG 5.0,a data base of essential genes in both prokaryotes and eukaryotes[J].Nucleic Acids Research,2009,37（Database issue）：D455-D458.

[9]Saccharomyces genome deletion project[DB/OL].[2015-12-12].http：//www-sequence.stanford.edu/group/yeast_deletion_project.

[10]Estrada E.Virtual identification of essential proteins within the protein interaction network of yeast[J].Proteomics,2006,6（1）：35-40.

（責任編輯：盧奇）

Identification of essential proteins based on network node correlation

XU Rui,LI Linfang,BAI Linfeng
（Henan Institute of Science and Technology,Xinxiang 453003,China）

To improve the efficiency of identification of essential proteins in protein networks,a new method for identification of essential proteins was proposed based on network node correlation.This method considers the local characteristics of protein networks on the basis of maintaining the topological structure of protein network,measure the importance of protein nodes from the perspective of protein node correlation and use the invalidation of protein node method to identify essential proteins in protein networks.Finally,the validity of the proposed method was verified by experiments.

node correlation；protein networks；essential protein；node importance

TP301.6

A

1008-7516（2016）02-0068-05

10.3969/j.issn.1008-7516.2016.02.016

2016-01-09

許睿（1987—）,男,河南新鄉(xiāng)人,碩士,助教.主要從事數(shù)據(jù)挖掘和生物信息學研究.