彭秀芬

( 池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，池州 247000 )

生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法研究進(jìn)展

彭秀芬

( 池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，池州 247000 )

生物網(wǎng)絡(luò)是一類(lèi)典型的復(fù)雜網(wǎng)絡(luò)，其關(guān)鍵節(jié)點(diǎn)的識(shí)別方法大多來(lái)自于其他復(fù)雜網(wǎng)絡(luò)的研究。首先舉例分析了復(fù)雜網(wǎng)絡(luò)中常用的幾種判斷節(jié)點(diǎn)關(guān)鍵性的指標(biāo)，然后總結(jié)了幾種生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識(shí)別方法，指出了生物網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)鍵性識(shí)別與其他復(fù)雜網(wǎng)絡(luò)的區(qū)別及今后研究的方向。

圖論；復(fù)雜網(wǎng)絡(luò)；中心性指標(biāo)；生物網(wǎng)絡(luò)；關(guān)鍵節(jié)點(diǎn)

隨著系統(tǒng)生物學(xué)的發(fā)展，生物學(xué)研究從單基因、單分子的功能探索發(fā)展到研究細(xì)胞組成物質(zhì)及其生命活動(dòng)對(duì)分子功能的影響。細(xì)胞組成物質(zhì)包括蛋白質(zhì)、DNA、RNA、小分子等。研究這些物質(zhì)的相互作用，可通過(guò)建立網(wǎng)絡(luò)模型來(lái)完成。常見(jiàn)的生物網(wǎng)絡(luò)有：蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)(Protein-protein interaction network, PPI network)、代謝網(wǎng)絡(luò)(Metabolic network)、基因調(diào)控網(wǎng)絡(luò)(Regulatory network)等[1-5]。這幾種網(wǎng)絡(luò)模型中，節(jié)點(diǎn)分別代表蛋白質(zhì)、代謝物及基因，邊代表其作用關(guān)系。

在生物網(wǎng)絡(luò)中，各節(jié)點(diǎn)的生物功能不同，對(duì)整個(gè)網(wǎng)絡(luò)的影響也不同。也就是說(shuō)生物網(wǎng)絡(luò)中節(jié)點(diǎn)的地位與其在細(xì)胞功能上的重要性有關(guān)，某些節(jié)點(diǎn)(關(guān)鍵節(jié)點(diǎn))的存在對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和功能具有重大意義[6-7]。例如，在蛋白質(zhì)相互作用網(wǎng)絡(luò)中高度關(guān)聯(lián)的節(jié)點(diǎn)具有重要的功能，而且其缺失與致命性有關(guān)[8]。在基因調(diào)控網(wǎng)絡(luò)中，也需要識(shí)別哪種基因控制著許多其他基因，以便其能被當(dāng)作有機(jī)體的全局調(diào)節(jié)因子進(jìn)行分析。因此，分析和研究生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)及其相互關(guān)系，對(duì)系統(tǒng)生物學(xué)研究越來(lái)越重要。然而，經(jīng)常遇到的問(wèn)題是不能明確地回答哪些節(jié)點(diǎn)是關(guān)鍵性節(jié)點(diǎn)。

生物網(wǎng)絡(luò)的結(jié)構(gòu)特性表明其是典型的復(fù)雜網(wǎng)絡(luò)[9]。為了研究這些大型的復(fù)雜網(wǎng)絡(luò)，研究者們提出了各種不同的網(wǎng)絡(luò)分析方法，也使用了其他科學(xué)領(lǐng)域的分析方法。本文首先分析了幾種以圖論為基礎(chǔ)的判斷復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)鍵性的指標(biāo)——中心性指標(biāo)，然后總結(jié)了幾種生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識(shí)別方法，分析了生物網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)鍵性識(shí)別與其他復(fù)雜網(wǎng)絡(luò)的區(qū)別，并指出了今后研究的方向。

1 節(jié)點(diǎn)的關(guān)鍵性指標(biāo)

目前，在復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識(shí)別方面，國(guó)內(nèi)外的很多研究都是以圖論為基礎(chǔ)，量化關(guān)鍵節(jié)點(diǎn)與非關(guān)鍵節(jié)點(diǎn)在拓?fù)湫再|(zhì)方面的差異，并以量化值的結(jié)果大小作為判別節(jié)點(diǎn)關(guān)鍵與否的標(biāo)準(zhǔn)[10-11]。相關(guān)圖論概念參考了文獻(xiàn)[12]。

1.1 中心性指標(biāo)

復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識(shí)別可通過(guò)對(duì)節(jié)點(diǎn)的關(guān)鍵性進(jìn)行排名來(lái)完成。一般情況下，事物的排名都是建立在某個(gè)相關(guān)數(shù)值的基礎(chǔ)上。例如，中超聯(lián)賽是根據(jù)比賽積分進(jìn)行排名。在識(shí)別復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的過(guò)程中也可以使用相同的方法對(duì)節(jié)點(diǎn)的關(guān)鍵性進(jìn)行排名。根據(jù)所研究的問(wèn)題，為每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)分配一個(gè)表示關(guān)鍵性的數(shù)值，然后依據(jù)這些數(shù)值對(duì)節(jié)點(diǎn)進(jìn)行排名。節(jié)點(diǎn)所得的數(shù)值稱(chēng)為該節(jié)點(diǎn)的中心值，而為每個(gè)節(jié)點(diǎn)分配數(shù)值的函數(shù)稱(chēng)為節(jié)點(diǎn)的中心性指標(biāo)，其定義如下：

定義1：設(shè)G=(V,E)是一個(gè)有向圖或無(wú)向圖，函數(shù)C：V→R稱(chēng)為一個(gè)中心性指標(biāo)[13]。

中心性指標(biāo)為每個(gè)節(jié)點(diǎn)分配的實(shí)數(shù)值可以進(jìn)行兩兩比較，例如，任意兩節(jié)點(diǎn)x和y，若C(x)>C(y)，則表明節(jié)點(diǎn)x比節(jié)點(diǎn)y更重要。

1.1.1 度(Degree)中心性指標(biāo)

網(wǎng)絡(luò)中任意節(jié)點(diǎn)x都有自己的度值d(x)。根據(jù)這些度值，可以對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行排名，因而可以形成了一個(gè)中心性指標(biāo)——度中心性指標(biāo)，記為Cdeg。計(jì)算任意節(jié)點(diǎn)x的度指標(biāo)中心值的公式如下[14]：

Cdeg(x)=d(x)

(1)

度指標(biāo)是一種基于本地的中心性指標(biāo)，考慮的是相鄰節(jié)點(diǎn)的情況，反映了節(jié)點(diǎn)與周?chē)?jié)點(diǎn)之間建立直接關(guān)系的能力。節(jié)點(diǎn)的度中心值越高，與之相鄰的節(jié)點(diǎn)就越多，其在網(wǎng)絡(luò)中的地位和功能相對(duì)來(lái)說(shuō)就可能更重要。任何網(wǎng)絡(luò)都可使用該中心性指標(biāo)對(duì)節(jié)點(diǎn)進(jìn)行排名。在有向網(wǎng)絡(luò)中，度指標(biāo)根據(jù)邊的方向又分為入度指標(biāo)和出度指標(biāo)。

1.1.2 離心率(Eccentricity)中心性指標(biāo)

在網(wǎng)絡(luò)模型中，常利用節(jié)點(diǎn)間的通信來(lái)模擬其所表示的對(duì)象之間的相互關(guān)系。在研究過(guò)程中，通常的做法是假設(shè)節(jié)點(diǎn)間的通信是通過(guò)它們之間的最短路徑來(lái)完成的。分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，可以發(fā)現(xiàn)其他任意節(jié)點(diǎn)都能以較短的距離到達(dá)居于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中心的點(diǎn)。根據(jù)這個(gè)思想，Hage和Harary在研究社會(huì)網(wǎng)絡(luò)時(shí)，提出了離心率中心性指標(biāo)[15]。該中心性指標(biāo)首先要計(jì)算節(jié)點(diǎn)的離心率。而節(jié)點(diǎn)的離心率為當(dāng)前節(jié)點(diǎn)到其他所有節(jié)點(diǎn)之間的最短路徑長(zhǎng)度中的最大值。節(jié)點(diǎn)x的離心率記為ecc(x)，其離心率越大，就越偏離網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的中心，其地位也就越低。根據(jù)中心性指標(biāo)的定義，取節(jié)點(diǎn)的離心率的倒數(shù)作為其中心值，記為Cecc。計(jì)算任意節(jié)點(diǎn)x的離心率指標(biāo)中心值的公式如下[16]：

Cecc(x)=1/ecc(x)

(2)

其中，ecc(x)=max{dist(x,y):y∈V}，dist(x,y)為節(jié)點(diǎn)x和y之間的最短路徑長(zhǎng)度。

離心率指標(biāo)以整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的中心為基準(zhǔn)，考慮了每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的權(quán)益。哪個(gè)節(jié)點(diǎn)離網(wǎng)絡(luò)中心越近，對(duì)其他任意節(jié)點(diǎn)來(lái)說(shuō)，該節(jié)點(diǎn)傳遞信息的速度就比較快，其在網(wǎng)絡(luò)中的地位也就越高。在解決實(shí)際問(wèn)題時(shí)，雖然有些問(wèn)題要考慮每個(gè)節(jié)點(diǎn)的權(quán)益(例如醫(yī)院選址)，但有些問(wèn)題則要考慮整體效益(例如商場(chǎng)選址)。

1.1.3 緊密度(Closeness)中心性指標(biāo)

有研究指出，處于網(wǎng)絡(luò)節(jié)點(diǎn)密集中心的點(diǎn)到其他節(jié)點(diǎn)的平均最短路徑長(zhǎng)度最短，其能夠更快地將信息傳達(dá)到整個(gè)網(wǎng)絡(luò)，在網(wǎng)絡(luò)通信中起到了關(guān)鍵作用。如何找到這樣的關(guān)鍵節(jié)點(diǎn)呢？學(xué)者們提出了緊密度中心性指標(biāo)，記為Cclo。

利用緊密度中心性指標(biāo)為每個(gè)節(jié)點(diǎn)分配中心值時(shí)，先要計(jì)算每個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑長(zhǎng)度的總和。這樣，居于節(jié)點(diǎn)密集區(qū)域中心的節(jié)點(diǎn)會(huì)得到一個(gè)較低值(總和越小，平均長(zhǎng)度就越小)。根據(jù)中心性指標(biāo)定義，中心值越大的節(jié)點(diǎn)其地位越重要，所以將最短路徑長(zhǎng)度總和的倒數(shù)作為節(jié)點(diǎn)的中心值。計(jì)算任意節(jié)點(diǎn)x的緊密度指標(biāo)中心值公式如下[18]：

Cclo(x)=1/∑y∈Vdist(x,y)

(3)

其中，dist(x,y)為節(jié)點(diǎn)x和y之間的最短路徑長(zhǎng)度。

緊密度中心性指標(biāo)反映的是當(dāng)前節(jié)點(diǎn)與其他節(jié)點(diǎn)之間連接的密切程度，其最早被用于社會(huì)網(wǎng)絡(luò)中心性的研究。Wuchty等用緊密度中心性指標(biāo)探討了復(fù)雜網(wǎng)絡(luò)中心性問(wèn)題，闡明了地方設(shè)施選址問(wèn)題[18]。在生物網(wǎng)絡(luò)研究領(lǐng)域，這種中心性指標(biāo)應(yīng)用也很廣泛。

1.1.4 最短路徑介數(shù)(Shortest path betweenness)中心性指標(biāo)

在網(wǎng)絡(luò)通信中，有些節(jié)點(diǎn)扮演了通信“樞紐”的角色，這些節(jié)點(diǎn)被刪除或破壞，部分節(jié)點(diǎn)間的通信會(huì)被中斷，甚至整個(gè)網(wǎng)絡(luò)會(huì)陷入癱瘓。因此，從通信量的角度考慮，節(jié)點(diǎn)的通信量越大，其在網(wǎng)絡(luò)中的地位就越重要。因此，可以利用網(wǎng)絡(luò)中所有最短路徑中經(jīng)過(guò)某個(gè)節(jié)點(diǎn)的路徑的數(shù)目占最短路徑總數(shù)的比例，來(lái)衡量該節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位[19]。

網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的最短路徑上的其他節(jié)點(diǎn)都承擔(dān)了這兩點(diǎn)間的通信流量。服務(wù)對(duì)象越多的節(jié)點(diǎn)(即經(jīng)過(guò)該節(jié)點(diǎn)的其他節(jié)點(diǎn)間的最短路徑越多的節(jié)點(diǎn))，其對(duì)于整個(gè)網(wǎng)絡(luò)的通信來(lái)說(shuō)就越重要。計(jì)算經(jīng)過(guò)一個(gè)節(jié)點(diǎn)的通信流量，并將這個(gè)數(shù)值作為度量其是否是關(guān)鍵節(jié)點(diǎn)的指標(biāo)，就得出了一個(gè)中心性指標(biāo)定義——基于最短路徑的介數(shù)中心性指標(biāo)，記為Cspb。

設(shè)節(jié)點(diǎn)y是節(jié)點(diǎn)x和z之間最短路徑上的內(nèi)部節(jié)點(diǎn)(y≠x且y≠z)，計(jì)算節(jié)點(diǎn)y的基于最短路徑介數(shù)指標(biāo)中心值公式如下[21]：

(4)

其中δxz(y)表示節(jié)點(diǎn)y所承擔(dān)的節(jié)點(diǎn)x到z的通信比率，其值為σxz(y)/σxz。而σxz表示兩節(jié)點(diǎn)x和z之間的最短路徑數(shù)目，σxz(y)表示兩節(jié)點(diǎn)x和z之間的經(jīng)過(guò)節(jié)點(diǎn)y的最短路徑數(shù)目。如果x和z之間沒(méi)有最短路徑存在(σxz=0)，則δxz(y)=0。

利用介數(shù)指標(biāo)可以確定信息負(fù)載繁重的網(wǎng)絡(luò)節(jié)點(diǎn)。節(jié)點(diǎn)介數(shù)中心值越大，其對(duì)網(wǎng)絡(luò)通信功能的影響就越大。

1.1.5 特征向量(Eigenvector)中心性指標(biāo)

之前介紹的中心性指標(biāo)描述的是一個(gè)節(jié)點(diǎn)對(duì)其他節(jié)點(diǎn)的影響，但在有些情況下，節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位和功能與其鄰居的中心性有很大關(guān)聯(lián)。若一個(gè)節(jié)點(diǎn)擁有高中心值的鄰居，該節(jié)點(diǎn)也會(huì)有比較高的中心值[20]。這種中心性思想是菲利普·玻納西奇提出的，他不僅考慮了節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，而且考慮了相鄰節(jié)點(diǎn)的反饋信息。這種思想被形式化為一組線性方程，該方程組的最大特征值λ所對(duì)應(yīng)的特征向量就是各個(gè)節(jié)點(diǎn)的中心值，記為Ceiv。對(duì)于任意節(jié)點(diǎn)vi，其特征向量中心值計(jì)算公式如下[21]：

(5)

其中，aij表示所分析的網(wǎng)絡(luò)的鄰接矩陣A的相應(yīng)元素。如果節(jié)點(diǎn)vi和vj之間沒(méi)有邊存在，則這個(gè)元素之為0，其與Ceiv(vj)相乘后，相應(yīng)的項(xiàng)消除。

特征向量指標(biāo)從節(jié)點(diǎn)的地位和影響力角度考慮，把單個(gè)節(jié)點(diǎn)的影響力歸結(jié)為所有其他節(jié)點(diǎn)影響力的線性組合，不僅能夠體現(xiàn)節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中的地位，更能反映節(jié)點(diǎn)的長(zhǎng)期影響力。

1.2 幾種中心性指標(biāo)比較分析

為了更好地了解以上介紹的幾種中心性指標(biāo)及其優(yōu)缺點(diǎn)，下面使用了一個(gè)網(wǎng)絡(luò)示例圖(如圖1所示)，用以展示不同中心性指標(biāo)對(duì)應(yīng)的各個(gè)節(jié)點(diǎn)的中心值(如表1所示)。

圖1 網(wǎng)絡(luò)示例圖

節(jié)點(diǎn)CdegCeccCcloCspbCeivA30.3330.1001.50.505B30.5000.11180.454C20.2500.07700.384D40.3330.1116.50.558E10.2500.07100.202F10.2500.05900.068G20.3330.08350.188

在這些中心性指標(biāo)中，度指標(biāo)直接使用了網(wǎng)絡(luò)中節(jié)點(diǎn)的度信息，反映了一個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)建立直接聯(lián)系的能力，未考慮節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的影響力。實(shí)際研究中也表明，僅僅從度值的角度判斷關(guān)鍵節(jié)點(diǎn)不是很準(zhǔn)確。例如圖1中，節(jié)點(diǎn)A的度中心值比節(jié)點(diǎn)G的大，說(shuō)明節(jié)點(diǎn)A比G更重要，但刪除節(jié)點(diǎn)A后(如圖2所示)，網(wǎng)絡(luò)仍然是連通的，而刪除節(jié)點(diǎn)G后(如圖3所示)，網(wǎng)絡(luò)被分解成兩個(gè)互不連通的部分。從這個(gè)網(wǎng)絡(luò)連通角度考慮，顯然節(jié)點(diǎn)G比節(jié)點(diǎn)A重要，是維護(hù)網(wǎng)絡(luò)連通性的關(guān)鍵節(jié)點(diǎn)之一。

圖2 刪除節(jié)點(diǎn)A的示例圖

圖3 刪除節(jié)點(diǎn)G的示例圖

離心率、緊密度和最短路徑介數(shù)等中心性指標(biāo)都利用了網(wǎng)絡(luò)圖的最短路徑信息，區(qū)別在于離心率和緊密度中心性指標(biāo)使用的是兩點(diǎn)間的最短路徑長(zhǎng)度，其中，離心率指標(biāo)考慮的是單一通信距離，反映了當(dāng)前節(jié)點(diǎn)與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中心的遠(yuǎn)近關(guān)系。由表1可知，圖1網(wǎng)絡(luò)中的節(jié)點(diǎn)B的度雖然比節(jié)點(diǎn)D的小，但它更接近于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的中心。緊密度指標(biāo)關(guān)注的是節(jié)點(diǎn)與所有其他節(jié)點(diǎn)的平均通信距離，其反映了當(dāng)前節(jié)點(diǎn)與網(wǎng)絡(luò)節(jié)點(diǎn)密集區(qū)域中心的距離關(guān)系。例如，圖1網(wǎng)絡(luò)中節(jié)點(diǎn)B的緊密度中心值與節(jié)點(diǎn)D的相同，說(shuō)明這兩個(gè)節(jié)點(diǎn)與密集中心的距離相同，即在這種指標(biāo)下，節(jié)點(diǎn)B和D具有同等的關(guān)鍵性。最短路徑介數(shù)指標(biāo)使用的是經(jīng)過(guò)節(jié)點(diǎn)的最短路徑數(shù)目，計(jì)算節(jié)點(diǎn)所承擔(dān)的通信量。這種指標(biāo)關(guān)注的是節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)連通性的影響。圖1中，節(jié)點(diǎn)A和B的度都是3，但節(jié)點(diǎn)B能影響到整個(gè)網(wǎng)絡(luò)的連通性，且比節(jié)點(diǎn)D的影響更大。

特征向量指標(biāo)是利用鄰居節(jié)點(diǎn)的反饋信息，衡量一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中的地位及其影響力。對(duì)于任意節(jié)點(diǎn)，其鄰居節(jié)點(diǎn)的特征向量中心值越高或者鄰居越多，該節(jié)點(diǎn)的中心值也就越高。圖1網(wǎng)絡(luò)中的節(jié)點(diǎn)E和F，都是度為1的節(jié)點(diǎn)，即網(wǎng)絡(luò)邊緣節(jié)點(diǎn)。由于E的鄰居D比F的鄰居G的中心值要高，因此E得到一個(gè)相對(duì)高一點(diǎn)的特征向量中心值。

通過(guò)以上分析可見(jiàn)，不同的中心性指標(biāo)是根據(jù)所研究的特定問(wèn)題而定義的。對(duì)于同一個(gè)網(wǎng)絡(luò)，應(yīng)用不同的中心性指標(biāo)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行排序時(shí)，得到的結(jié)果會(huì)有很大差異。因此，即使是同一個(gè)網(wǎng)絡(luò)，不同中心性指標(biāo)的中心值之間沒(méi)有可比較性。另外，對(duì)于不同的網(wǎng)絡(luò)，同一種中心性指標(biāo)的中心值也沒(méi)有可比性。在研究不同的生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)時(shí)，也應(yīng)根據(jù)具體的問(wèn)題選擇合適的中心性指標(biāo)，可以結(jié)合多種中心性指標(biāo)，從不同的角度分析其節(jié)點(diǎn)的關(guān)鍵性。

2 生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識(shí)別方法

在生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別研究中，研究者利用網(wǎng)絡(luò)模型模擬生物體細(xì)胞內(nèi)的物質(zhì)活動(dòng)。這些網(wǎng)絡(luò)模型大多數(shù)情況下表現(xiàn)出了小世界特性和無(wú)標(biāo)度特性，因此，研究者們直接使用或擴(kuò)展了其他復(fù)雜網(wǎng)絡(luò)的研究方法，用以識(shí)別其關(guān)鍵節(jié)點(diǎn)。

2.1 生物網(wǎng)絡(luò)模型

不同的生物網(wǎng)絡(luò)，其物質(zhì)之間的作用關(guān)系有所不同，因此，在分析研究各種生物網(wǎng)絡(luò)時(shí)所使用的具體的網(wǎng)絡(luò)模型也有所區(qū)別。例如，在研究細(xì)胞中蛋白質(zhì)的作用時(shí)，各種蛋白質(zhì)被看作一個(gè)節(jié)點(diǎn)。由于蛋白質(zhì)與蛋白質(zhì)之間會(huì)相互影響，代表蛋白質(zhì)的節(jié)點(diǎn)與節(jié)點(diǎn)之間就具有相互影響的關(guān)系，這種關(guān)系被看作一條無(wú)向邊，因此形成了用無(wú)向圖所表示的蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)(圖4)；代謝網(wǎng)絡(luò)中，節(jié)點(diǎn)之間具有先后的轉(zhuǎn)換關(guān)系，其通常使用的是有向圖(圖5)；基因調(diào)控網(wǎng)絡(luò)的各節(jié)點(diǎn)之間具有調(diào)控和被調(diào)控的關(guān)系，所以也使用有向圖進(jìn)行分析。

圖4 酵母蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)模型[22]

圖5 Buchnera aphidicola代謝網(wǎng)絡(luò)模型[23]

在使用中心性方法分析識(shí)別生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)時(shí)，有的中心性指標(biāo)要求網(wǎng)絡(luò)模型必須是(強(qiáng))連通圖。但通常所獲取的生物網(wǎng)絡(luò)模型并非是連通的，會(huì)存在一些獨(dú)立的點(diǎn)或者有一些互不連接的連通子圖。一種方法是將不連接的兩個(gè)點(diǎn)之間的最短路徑長(zhǎng)度定義為無(wú)窮大。另一種方法是根據(jù)連通性將網(wǎng)絡(luò)分解為幾個(gè)連通分支，再將每個(gè)分支作為一個(gè)獨(dú)立的網(wǎng)絡(luò)進(jìn)行分析。

2.2 中心性分析法

中心性分析法是根據(jù)某種中心性指標(biāo)計(jì)算各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的中心值，并根據(jù)該值對(duì)節(jié)點(diǎn)進(jìn)行排序，然后根據(jù)節(jié)點(diǎn)的排名判斷節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位和功能，確定其是否是關(guān)鍵節(jié)點(diǎn)。這種網(wǎng)絡(luò)元素排序方法在識(shí)別生物過(guò)程中的關(guān)鍵參與者特別有用，可以幫助了解潛在的生物過(guò)程。

Jeong等利用度中心性分析了酵母菌的蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)，討論了高中心性值的蛋白質(zhì)淘汰后對(duì)生物體的影響，并證明了高度值的蛋白質(zhì)成為生物體必需品的可能性要比低度值的蛋白質(zhì)大[24]。Bergmann等在研究釀酒酵母、大腸桿菌和秀麗隱桿線蟲(chóng)的基因共表達(dá)網(wǎng)絡(luò)(Gene co-expression network)過(guò)程中也使用了度中心性指標(biāo)，發(fā)現(xiàn)對(duì)有機(jī)體來(lái)說(shuō)度高的基因可能更重要[25]。Ma和Zeng[26]根據(jù)稍微修改的緊密度中心性方法，識(shí)別出了大腸桿菌代謝網(wǎng)絡(luò)中排第八和第十的代謝物是糖酵解和檸檬酸酸循環(huán)通路的一部分。

Joy[27]等在識(shí)別酵母關(guān)鍵蛋白質(zhì)時(shí)，發(fā)現(xiàn)介數(shù)中心值高的蛋白質(zhì)的度中心值有高有低。特別是具有高介數(shù)值和低度值的蛋白質(zhì)，他們可能維護(hù)著網(wǎng)絡(luò)結(jié)構(gòu)的完整性。Potapov等[28]將介數(shù)中心化方法用于研究哺乳動(dòng)物轉(zhuǎn)錄調(diào)控網(wǎng)絡(luò)，并指出在不同元素的生物學(xué)意義方面介數(shù)是最具有代表性的拓?fù)涮卣鳌?/p>

有時(shí)為了更準(zhǔn)確地分析和識(shí)別生物網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，研究人員會(huì)同時(shí)使用多種中心性指標(biāo)。Hahn等[29]選取了酵母、蠕蟲(chóng)和蒼蠅的蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)，并利用度、緊密度和介數(shù)指標(biāo)分析比較了這3個(gè)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，結(jié)果顯示關(guān)鍵節(jié)點(diǎn)的平均中心值明顯高于非關(guān)鍵節(jié)點(diǎn)的中心值。Estrada[30]利用應(yīng)用度、緊密度、介數(shù)、特征向量等多種中心性指標(biāo)，分析了酵母的蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)，其研究表明中心性指標(biāo)能夠比隨機(jī)選擇策略更好地識(shí)別關(guān)鍵蛋白質(zhì)。

2.3 其他識(shí)別法分析

由于中心性指標(biāo)是根據(jù)特定的問(wèn)題定義一個(gè)函數(shù)，為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)分配一個(gè)中心值，因此單一的中心性指標(biāo)所提供的生物信息比較有限。生物網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的功能及其相互關(guān)系比較復(fù)雜，單獨(dú)使用這些指標(biāo)參數(shù)所獲得的關(guān)鍵節(jié)點(diǎn)的生物學(xué)意義比較低，且存在一些缺陷。為此，一些研究者提出了使用綜合參數(shù)識(shí)別生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的方法，也有一些人另辟蹊徑。

黃海濱等[31]在相關(guān)研究中，將關(guān)鍵蛋白質(zhì)識(shí)別看成是一類(lèi)特殊的模式識(shí)別，以分子之間的量化關(guān)系(拓?fù)鋮?shù))為依據(jù)，利用復(fù)合參數(shù)來(lái)識(shí)別蛋白質(zhì)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。對(duì)于蛋白質(zhì)網(wǎng)絡(luò)中的任意節(jié)點(diǎn)vi，他們將各種中心性指標(biāo)得到的中心值，作為該節(jié)點(diǎn)的拓?fù)鋮?shù)集，并將所有節(jié)點(diǎn)的拓?fù)鋮?shù)集組成一個(gè)矩陣——關(guān)鍵節(jié)點(diǎn)識(shí)別矩陣，其元素就是節(jié)點(diǎn)在對(duì)應(yīng)的中心性指標(biāo)下的中心值。在分析了各參數(shù)與節(jié)點(diǎn)關(guān)鍵性的相關(guān)性和參數(shù)之間的相關(guān)性后，選擇合適的參數(shù)組成復(fù)合參數(shù)。根據(jù)復(fù)合參數(shù)中的一個(gè)參數(shù)對(duì)關(guān)鍵節(jié)點(diǎn)識(shí)別矩陣進(jìn)行排序，篩選出若干節(jié)點(diǎn)，然后再根據(jù)其他參數(shù)進(jìn)行識(shí)別。其實(shí)踐表明這種復(fù)合參數(shù)異步識(shí)別法的性能明顯高于獨(dú)立參數(shù)識(shí)別法。

楊汀依[32]在以往識(shí)別方法的基礎(chǔ)上，提出了灰色關(guān)聯(lián)分析法和熵權(quán)法來(lái)建立各種中心性指標(biāo)之間的關(guān)系，綜合考慮多個(gè)中心性指標(biāo)，從而確立網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)?；疑P(guān)聯(lián)分析法是依據(jù)各因素間發(fā)展趨勢(shì)的相異或者相似程度，期望通過(guò)特殊的方法，尋找它們之間的數(shù)值關(guān)系，這種關(guān)系指的是中心性指標(biāo)關(guān)聯(lián)系數(shù)和節(jié)點(diǎn)的關(guān)聯(lián)度。節(jié)點(diǎn)的關(guān)聯(lián)度越大，說(shuō)明其越重要。在信息論中，熵表示的是不確定性的量度，其值越小，信息的效用值就越大，反之，信息的效用值就越小。將節(jié)點(diǎn)和指標(biāo)值矩陣作為信息的載體——判斷矩陣，并以此計(jì)算出各個(gè)中心性指標(biāo)的熵權(quán)值[32]。在利用灰色關(guān)聯(lián)分析法分析計(jì)算每個(gè)節(jié)點(diǎn)的關(guān)聯(lián)度時(shí)，引入熵權(quán)值，提高了節(jié)點(diǎn)關(guān)聯(lián)度的準(zhǔn)確性。

Ulitsky和Shamir[33]擴(kuò)展了Kelley和Ideker的將遺傳網(wǎng)絡(luò)和物理網(wǎng)絡(luò)一起分析的方法，將蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)和對(duì)應(yīng)的遺傳網(wǎng)絡(luò)結(jié)合起來(lái)，開(kāi)發(fā)了獨(dú)特的分析工具，在物理環(huán)境下分析遺傳交互。在該研究中，蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)中的一個(gè)連通子圖被定義為路徑(pathway)，通過(guò)貪婪算法獲得遺傳網(wǎng)絡(luò)中相互之間有密集交互的兩個(gè)不同路徑，這種關(guān)系定義為關(guān)聯(lián)路徑模式(Between-pathway-model,BPM)。他們通過(guò)該方法獲得了140種模式，同時(shí)確定了與所在模式中的兩條路徑都有許多物理交互的“樞紐”蛋白質(zhì)，并發(fā)現(xiàn)了其中的關(guān)鍵蛋白質(zhì)。

陸聿[34]將基礎(chǔ)物理學(xué)中的“勢(shì)場(chǎng)”概念運(yùn)用到蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)中，提出了一種基于拓?fù)鋭?shì)的蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法。該方法的基本思想是將網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都當(dāng)作一個(gè)物理粒子，在它周?chē)嬖谝粋€(gè)虛擬的作用場(chǎng)，由此網(wǎng)絡(luò)中所有節(jié)點(diǎn)的相互作用就聯(lián)合形成了一個(gè)勢(shì)場(chǎng)；采用高斯勢(shì)函數(shù)來(lái)描述網(wǎng)絡(luò)中節(jié)點(diǎn)間的相互作用，其對(duì)應(yīng)的場(chǎng)就是拓?fù)鋭?shì)場(chǎng)；通過(guò)對(duì)每一個(gè)節(jié)點(diǎn)的拓?fù)鋭?shì)的值進(jìn)行定義和計(jì)算，就能夠獲得一個(gè)基于網(wǎng)絡(luò)拓?fù)鋭?shì)的反映節(jié)點(diǎn)關(guān)鍵性的精確排序。

丁德武和彭秀芬[35]提出了從節(jié)點(diǎn)對(duì)社團(tuán)貢獻(xiàn)的角度來(lái)識(shí)別關(guān)鍵節(jié)點(diǎn)的方法。該方法首先采用復(fù)雜網(wǎng)絡(luò)鏈接聚類(lèi)算法從生物網(wǎng)絡(luò)中提取富含生物學(xué)功能意義的社團(tuán)。這些社團(tuán)是相互交疊的，網(wǎng)絡(luò)中某些節(jié)點(diǎn)可能屬于多個(gè)社團(tuán)，因此可以根據(jù)這一點(diǎn)來(lái)評(píng)價(jià)節(jié)點(diǎn)的關(guān)鍵性。研究人員分別從激酶與磷酸酶交互網(wǎng)絡(luò)和小RNA調(diào)控網(wǎng)絡(luò)提取了10個(gè)和14個(gè)富含生物學(xué)功能意義的社團(tuán)，并識(shí)別了其中連接最多社團(tuán)數(shù)量的節(jié)點(diǎn)。這種方法不僅分析了生物網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，還研究了節(jié)點(diǎn)對(duì)生物網(wǎng)絡(luò)功能關(guān)系的影響，依據(jù)節(jié)點(diǎn)對(duì)生物網(wǎng)絡(luò)功能的貢獻(xiàn)值，識(shí)別出了具有生物學(xué)意義的關(guān)鍵節(jié)點(diǎn)。

丁德武[36]還提出了利用主成分分析法來(lái)研究代謝網(wǎng)絡(luò)的中心化問(wèn)題。該方法是選取節(jié)點(diǎn)的P個(gè)指標(biāo)(x1,x2,…,xp)，并對(duì)其進(jìn)行標(biāo)準(zhǔn)化。然后，根據(jù)標(biāo)準(zhǔn)化后的數(shù)據(jù)矩陣建立相關(guān)系數(shù)矩陣R，求出R的特征值及其對(duì)應(yīng)的特征向量，并由累積方差貢獻(xiàn)率確定主成分的個(gè)數(shù)及各個(gè)主成分。最后，選取累積貢獻(xiàn)率最高的主成分，并根據(jù)對(duì)應(yīng)的線性方程分析主成分的值，以確定各個(gè)節(jié)點(diǎn)的排名。

上述關(guān)鍵節(jié)點(diǎn)識(shí)別方法都是通過(guò)特定的方法為節(jié)點(diǎn)賦值，并根據(jù)該值對(duì)節(jié)點(diǎn)進(jìn)行排序，并據(jù)此確定關(guān)鍵節(jié)點(diǎn)。研究表明生物網(wǎng)絡(luò)節(jié)點(diǎn)的關(guān)鍵性不僅僅由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)決定，還受到節(jié)點(diǎn)自身生物學(xué)功能意義和細(xì)胞物質(zhì)遺傳特性的影響[37-39]。

3 結(jié)語(yǔ)

生命科學(xué)的發(fā)展帶動(dòng)了生物網(wǎng)絡(luò)相關(guān)研究的進(jìn)步，分析研究生物網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)及其相互關(guān)系，可以從生物信息學(xué)角度為醫(yī)藥發(fā)展提供有價(jià)值的理論和方法。本文從復(fù)雜網(wǎng)絡(luò)理論和圖論出發(fā)，討論和分析了幾種用于節(jié)點(diǎn)關(guān)鍵性排序的指標(biāo)和識(shí)別關(guān)鍵節(jié)點(diǎn)的方法。這些生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識(shí)別方法各有所長(zhǎng)，共同點(diǎn)都是以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)，分析研究節(jié)點(diǎn)間的相互關(guān)系以確定節(jié)點(diǎn)的關(guān)鍵性。生物網(wǎng)絡(luò)與其他復(fù)雜網(wǎng)絡(luò)的區(qū)別在于其節(jié)點(diǎn)具有生物學(xué)意義，在今后的研究中應(yīng)更多地考慮細(xì)胞物質(zhì)的生物學(xué)信息，才能更準(zhǔn)確地識(shí)別具有實(shí)際生物學(xué)意義的關(guān)鍵節(jié)點(diǎn)。

[1]RUAL J F, VENKATESAN K, HAO T, et al. Towards a proteome-scale map of the human protein-protein interaction network [J]. Nature, 2005, 437(7062):1173-1178.

[2]STELZL U, WORM U, LALOWSKI M, et al. A human protein-protein interaction network: a resource for annotating the proteome [J]. Cell, 2005, 122(6):957-968.

[3]JEONG H, TOMBOR B, ALBERT R, et al. The large-scale organization of metabolic networks[J]. Nature, 2000, 407 (6804):651-654.

[4]DUARTE N C, BECKER S A, JAMSHIDI N, et al. Global reconstruction of the human metabolic network based on genomic and bibliomic data[J]. Proc Natl Acad Sci USA, 2007, 104 (6): 1777-1782.

[5]CARNINCI P, KASUKAWA T, KATAYAMA S, et al. The transcriptional landscape of the mammalian genome[J]. Science, 2005, 309 (5740): 1559-1563.

[6]GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. Proc Natl Acad Sci USA, 2002, 99(12): 7821-7826.

[7]CRUCITTI P, LATORA V, MARCHIORI M, et al. Error and attack tolerance of complex networks[J]. Nature, 2000, 406(6803): 378-382.

[9]YAMADA T, BORK P. Evolution of biomolecular networks-lessons from metabolic and protein interactions [J]. Nature Reviews Molecular Cell Biology, 2009, 10(11): 791-803.

[10]丁德武,陸克中,須文波, 等. 基于SAA的蘇云金桿菌代謝網(wǎng)絡(luò)功能模塊[J]. 計(jì)算機(jī)工程, 2010, 36(13): 162-163.

[11]DING D W, HE X R, PENG X F, et al. Functional modules and central proteins in ROS network[J]. Computers and Applied Chemistry, 2012, 29(6): 749-752.

[12]徐俊明.圖論及其應(yīng)用[M]. 合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,2004:1-5.

[13]JUNKER B H, SCHREIBER F. Analysis of biological networks [M]. Hoboken:Wiley, 2008:65-67.

[14]JUNKER B H, SCHREIBER F. Analysis of biological networks [M]. Hoboken:Wiley, 2008:69.

[15]HAGE P, HARARY F. Eccentricity and centrality in networks [J]. Social Networks, 1995, 17(1):57-63.

[16]JUNKER B H, SCHREIBER F. Analysis of Biological Networks [M]. Hoboken:Wiley, 2008:72-74.

[17]KOSCH TZKI D, SCHREIBER F. Comparison of centralities for biological networks[J]. Proc German Conf Bioinformatics(GCB 2004), 2004, 53(1):199-206.

[18]WUCHTY S, STADLER P F. Centers of complex networks [J]. Journal of Theoretical Biology, 2003, 223 (1):45-53.

[19]BARTH LEMY M. Betweenness centrality in large complex networks[J]. The European Physical Journal B, 2004, 38(2):163-168.

[20]BONACICH P, LLOYD P. Eigenvector-Like measures of centrality for asymmetric relations[J]. Social Net-works, 2001, 23(4):191-201.

[21]JUNKER B H, SCHREIBER F. Analysis of Biological Networks [M]. Hoboken:Wiley, 2008: 79.

[23]BORENSTEIN E, KUPIEC M, FELDMAN M W, et al. Large-scale reconstruction and phylogenetic analysis of metabolic environments[J]. Proc Natl Acad Sci USA, 2008, 105(38): 14482-14487.

[24]JEONG H, MASON S P, BARABASI A L, et al. Oltvai ZN: Lethality and centrality in protein networks[J]. Nature, 2001, 411(6808):41-42.

[25]BERGMANN S, IHMELS J,BARKAI N. Similarities and differences in genome-wide expression data of six organisms[J]. PLOS Biology, 2004, 2(1):E9.

[26]MA H W, ZENG A P. The connectivity structure, giant strong component and centrality of metabolic networks[J]. Bioinformatics, 2003, 19(11):1423-1430.

[27]JOY M P, BROCK A, INGBER D E, et al. High-betweenness proteins in the yeast protein interaction network[J].Journal of Biomedicine and Biotechnology, 2005(2):96-103.

[28]POTAPOV A P, VOSS N, SASSE N, et al. Topology of mammalian transcription networks[J].Genome Informatics, 2005, 16(2):270-278.

[29]HAHN M W, KERN A D. Comparative genomics of centrality and essentiality in three eukaryotic protein-interaction networks[J]. Molecular Biology and Evolution, 2005, 22(4):803-806.

[30]ESTRADA E. Virtual identification of essential proteins within the protein interaction network of yeast [J]. Proteomics, 2006, 6(1):35-40.

[31]黃海濱,楊路明,王建新,等. 基于復(fù)合參數(shù)的蛋白質(zhì)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別技術(shù)[J]. 自動(dòng)化學(xué)報(bào), 2008, 34(11): 1388-1395.

[32]楊汀依. 復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別技術(shù)研究[D]. 南京：南京理工大學(xué),2011.

[33]ULITSKY I, SHAMIR R. Pathway redundancy and protein essentiality revealed in theSaccharomycescerevisiaeinteraction networks[J]. Molecular Systems Biology, 2007, 3(1):104-110.

[34]陸 聿. 基于拓?fù)鋭?shì)的關(guān)鍵蛋白質(zhì)識(shí)別方法研究[D]. 長(zhǎng)沙:中南大學(xué), 2014.

[35]丁德武, 彭秀芬. 基于交疊社團(tuán)相似性的生物網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別[J]. 計(jì)算機(jī)與應(yīng)用化學(xué), 2014,31 (10):1213-1216.

[36]丁德武.基于主成分分析的代謝網(wǎng)絡(luò)中心化[J]. 計(jì)算機(jī)與應(yīng)用化學(xué),2015,32(3):376-378.

[37]馬 玲.基于拓?fù)浣Y(jié)構(gòu)和復(fù)合物信息的關(guān)鍵蛋白質(zhì)識(shí)別算法研究[D].長(zhǎng)沙:湖南大學(xué).2013.

[38]丁德武.基于鏈接聚類(lèi)的代謝網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)研究[J]. 計(jì)算機(jī)工程與應(yīng)用,2011,47(34):141-144.

[39]陳傳庚, 段 斌, 廖高明，等. 基于基因表達(dá)譜和生物網(wǎng)絡(luò)識(shí)別肺癌敏感基因[J]. 國(guó)際遺傳學(xué)雜志, 2015, 38(1):24-28.

Methods for the identification of key nodes in bionetworks

PENG Xiu-fen

(College of Mathematics and Computer Science, Chizhou University, Chizhou 247000, China)

Biological network is a kind of typical complex network, thus the methods for identifying of the key nodes in biological networks are mainly from general complex network methods. This paper introduces several methods for the key indicators in the general complex networks, and then sums up the methods for the identification of key nodes in biological networks. It points out the differences between the biological network key nodes recognition and other general complex networks. The research directions is also discussed.

graph theory; complex network; centrality index; biological network; key node

2016-08-15；

2016-08-19

安徽省高校省級(jí)優(yōu)秀青年人才基金重點(diǎn)項(xiàng)目(生物網(wǎng)絡(luò)的隨機(jī)Petri網(wǎng)模型構(gòu)建與分析，2013SQRL096ZD)；池州學(xué)院自然科學(xué)研究項(xiàng)目(2013ZRZ003)；安徽省教育廳自然科學(xué)重點(diǎn)項(xiàng)目(KJ2015A264)

彭秀芬, 講師, 碩士, 主要研究領(lǐng)域?yàn)樯镄畔W(xué)、計(jì)算機(jī)應(yīng)用，E-mail：xiufenpeng@qq.com

Q811.4

A

2095-1736(2017)04-0104-06

doi∶10.3969/j.issn.2095-1736.2017.04.104