基于標準結構熵的ＰＰＩ網絡可靠性研究
2009-01-01 00:00:00李敏陳建二王建新
計算機應用研究 2009年1期
（中南大學 信息科學與工程學院， 長沙 410083）
摘 要：由蛋白質相互作用構成的PPI網絡的拓撲特性分析是后基因組時代最重要的研究課題之一。應用標準網絡結構熵對DIP數據庫中七個物種的八個PPI網絡的異質性和可靠性進行分析與研究。分析結果表明，這些PPI網絡具有典型的無尺度特性，對隨機移除不超過10%的頂點都具有很好的魯棒性，但對有選擇地移除2%的高度頂點就開始表現出極弱的抗攻擊性。
關鍵詞：系統生物學; 蛋白質相互作用網絡； 魯棒性； 脆弱性； 熵
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)01009702
Research on robustness of PPI networks based onnormalized entropy
LI Min， CHEN Jianer， WANG Jianxin
(School of Information Science Engineering， Central South University， Changsha 410083， China)
Abstract:Analysis of the topology characters of PPI network composed of proteinprotein interactions is one of the most important issues in the postgenomic era. This paper analyzed the heterogeneity and robustness of 8 PPI networks of 7 species in DIP database by using ormalized entropy. Analysis shows that these PPI networks are all scalefree， which are robust against the random removal of not more than 10% nodes， but are vulnerable to the removal of 2% nodes of high degree.
Key words：system biology; proteinprotein interaction network; robustness; lethality; entropy
蛋白質是生命活動的物質基礎，其相互作用在生命活動中起核心作用。隨著蛋白質相互作用測定技術的發展，大量的蛋白質相互作用數據被獲得。根據獲得的蛋白質相互作用數據可以在基因組范圍內呈現所有蛋白質之間的關系，即蛋白質相互作用網絡，簡稱PPI網絡。
目前，已有研究者對酵母(S.cerevisiae)的PPI網絡進行了拓撲分析，并發現了其不同于隨機網絡的小世界特性和無標度特性[1~4]。從本質上講，PPI網絡的無標度特性就是一種非同質性，是與其他復雜網絡一樣涌現出的一種序，其特征表現為網絡中的每個頂點與其他k個頂點相連的概率P(k)近似地服從冪規律分布，即P(k)～k-r。參數r通常被用來刻畫復雜網絡的非同質性，r越大，冪規律分布的曲線下降越快，即網絡的非同質性越明顯。但是，文獻[5]的分析結果表明大腸桿菌(E.coli)等真核生物的PPI網絡的度分布曲線有寬尾現象，并不是一條嚴格遞減的曲線。此外，r是對度分布曲線擬合得到的一個估計參數，非常不精確，并且計算復雜。本文基于網絡結構熵理論[6，7]， 對包括酵母在內的七個物種的八個PPI網絡的無標度特性進行研究，并對其魯棒性和脆弱性進行深入分析。
1 PPI網絡與網絡結構熵
1.1 PPI網絡
PPI網絡可以定義為一個無向、無權重的簡單圖G(V，E)，由一個頂點集V(G)和一個邊集E(G)組成。邊集E(G)中的每條邊ei有V(G)中的一對頂點(u，v)與之對應。圖G中的每個頂點表示一個蛋白質，每條邊表示一對蛋白質之間的相互作用。
1.2 網絡結構熵
熵作為描述復雜系統結構的物理量，近年來在復雜網絡的研究中得到了廣泛的應用。熵是系統能量分布均勻性的一種度量，可以表示物體所處狀態是否穩定及系統變化的方向。系統能量分布越均勻，其熵越大；反之，則熵越小。
定義1[6，7] 若圖G中的頂點數為N， ki為第i個頂點的連接度，則第i個頂點的重要度Ii為
Ii=ki/∑Ni=1ki(1)
定義2[6，7] 若圖G中的頂點數為N，Ii為第i個頂點的重要度，則圖G的網絡結構熵為
E=-∑Ni=1Iiln Ii(2)
不難證明，當網絡完全均勻，即Ii=1/N時，E取最大值：
Emax=-∑Ni=1（1/N） ln （1/N）=ln N(3)
當網絡結構為星型（即網絡中所有頂點都與某一中心節點相連）時網絡最不均勻，網絡結構熵最?。邯?/p>
Emin=（-1/2） ln （1/2）-∑Ni=2[1/2(N-1)] ln [1/2(N-1)]=
[ln 4(N-1)]/2(4)
為了消除頂點數量對網絡結構熵E的影響，可以將網絡結構熵進行歸一化。歸一化后的網絡結構熵稱為標準網絡結構熵，其計算公式如下：
NE=(Emax -E)/(Emax-Emin)(5)
1.3 PPI網絡的標準結構熵
本文從DIP(database of interacting proteins)[8]數據庫中下載得到相互作用多于200的七個物種的八個最新數據集(其中酵母分為全集和核心集兩個數據集)。對于下載得到的蛋白質相互作用數據集，首先過濾掉其中重復的相互作用和自相互作用，最終得到的用于實驗分析的樣本數據集的基本信息如表1所示。為了描述方便，在表1中給出了各個物種的標記符號(marker)，如酵母的數據全集被記做YS、酵母的核心數據集被記做YSC、線蟲被記做CE。
本文計算八個PPI網絡的標準網絡結構熵。作為比較，針對每個PPI網絡構造了具有相同頂點數和邊數的隨機網絡，并計算出每個生成的隨機網絡的標準結構熵。具體計算結果如表2所示。
從表2可以看出，每個PPI網絡的標準網絡結構熵都明顯高于其對應生成的隨機網絡的標準網絡結構熵，并且都介于0和1之間。根據標準網絡結構熵的定義可知，當一個網絡為規則網絡時，其對應的標準網絡結構熵為0；當一個網絡為星型結構時，其對應的標準網絡結構熵為1。從表2可以看出，四種不同類型的網絡的異質性排序為：星型網絡＞PPI網絡＞隨機網絡＞規則網絡。PPI 網絡所具有的高標準網絡結構熵充分說明了PPI網絡具有高的異質性。在星型網絡中只有一個中心節點，而在PPI網絡中有若干個中心節點，這些節點在網絡的連通中起著重要作用。下面將對PPI網絡的可靠性進行分析。
2 PPI網絡可靠性分析
近年來針對復雜網絡的研究成果表明，很多真實網絡兼具極強的容錯能力和極弱的抗攻擊性。極強的容錯能力表現為網絡對隨機移除一定比例的頂點具有很強的魯棒性；極弱的抗攻擊性表現為網絡對有選擇地移除某些關鍵的頂點非常脆弱。本文通過隨機移除和有選擇地移除一定比例(0~10%，按2個百分點間隔)的頂點來分析八個PPI網絡的魯棒性和脆弱性。
2.1 隨機移除實驗
隨機移除一定比例(0~10%，按2個百分點間隔)的頂點后各物種PPI網絡的標準網絡結構熵的變化曲線如圖1所示。可以看出，隨機移除不超過10%的頂點后，網絡的標準結構熵幾乎沒有變化。圖1的變化曲線充分說明PPI網絡對隨機攻擊具有相當強的魯棒性。
2.2 有選擇的移除實驗
在本節實驗中，選擇移除一定比例(0~10%，按2個百分點間隔)的高度頂點。這些高度的頂點通常被稱為hub節點，被認為是復雜網絡中的關鍵節點。各物種PPI網絡在移除一定比例的高度頂點后，其標準結構熵的變化曲線如圖2所示。
從圖2可以看出，有選擇地移除一定比例的高度頂點后，各物種PPI網絡的標準結構熵明顯下降。根據標準結構熵的定義可知，當一個網絡具有無標度特性時，其值會相對較大，此時網絡的連通性也較好，其小世界性就會越明顯。當然網絡受到確定性攻擊分裂為幾個隨機子網絡或多數頂點處于非連通狀態時其標準結構熵的值就會變小，從一個節點到達另一個節點的最短路徑就會變長，甚至是根本無法到達。圖2的變化曲線充分說明，PPI網絡對有選擇的確定性攻擊相當脆弱。
3 結束語
本文應用標準網絡結構熵對包括酵母在內的七個物種的八個PPI網絡的異質性和可靠性進行了深入分析，研究結果表明這些物種的PPI網絡較隨機網絡具有更高的標準網絡結構熵，并且這些PPI網絡對隨機移除不超過10%的頂點都具有很好的魯棒性，但對有選擇地移除2%的高度頂點就開始表現出極弱的抗攻擊性。
本文的分析表明標準網絡結構熵作為評估PPI網絡拓撲特性的一個度量，較好地體現了這些PPI網絡的本質特性，不僅為進一步研究PPI網絡、分析生物進化過程中的關鍵蛋白質奠定了基礎，也為研究其他復雜網絡的可靠性提供了新的思路。
參考文獻：
［1］JEONG H， MASON S， BARABASI A， et al. Lethality and centrality in protein networks[J]. Nature， 2001，411（6833）:4142.
[2]YOOK S H， OLTVAI Z N， BARABASI A N. Functional and topological characterization of protein interaction networks[J]. Proteomics， 2004，4(4):928942.
[3]PRZULJ N， WIGLE DA， JURISICA I. Functional topology in a network of protein interactions[J]. Bioinformatics， 2004，20(3):3408.
[4]WUCHTY S， ALMAAS E. Peeling the yeast protein network[J].Proteomics， 2005，5(2):444449.
[5]GOH K， KAHNG B， KIM D. Graph theoretic analysis of protein interaction networks of eukaryotes[J]. Physica A， 2005，357:501512.
[6]譚躍進， 吳俊. 網絡結構熵及其在非標度網絡中的應用[J]. 系統工程理論與實踐，2004，24(6):13.
[7]WU Jun， TAN Yuejin， DENG Hongzhong， et al. Normalized entropy of rank distribution: a novel measure of heterogeneity of complex networks[J]. Chinese Physics， 2007，16(6):15761580.
[8][EB/OL].http://dip.doembi.ucla.edu/.
