生物网络关键节点识别方法研究进展
彭秀芬
【摘 要】生物网络是一类典型的复杂网络,其关键节点的识别方法大多来自于其他复杂网络的研究.首先举例分析了复杂网络中常用的几种判断节点关键性的指标,然后总结了几种生物网络关键节点的识别方法,指出了生物网络节点关键性识别与其他复杂网络的区别及今后研究的方向.%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.
【期刊名称】《生物学杂志》
【年(卷),期】2017(034)004
【总页数】6页(P104-109)
【关键词】图论;复杂网络;中心性指标;生物网络;关键节点
【作 者】彭秀芬
【作者单位】池州学院 数学与计算机学院,池州 247000
【正文语种】中 文
【中图分类】Q811.4
随着系统生物学的发展,生物学研究从单基因、单分子的功能探索发展到研究细胞组成物质及其生命活动对分子功能的影响。细胞组成物质包括蛋白质、DNA、RNA、小分子等。研究这些物质的相互作用,可通过建立网络模型来完成。常见的生物网络有:蛋白质-蛋白质相互作用网络(Protein-protein interaction network, PPI network)、代谢网络(Metabolic network)、基因调控网络(Regulatory network)等[1-5]。这几种网络模型中,节点分别代表蛋白质、代谢物及基因,边代表其作用关系。
在生物网络中,各节点的生物功能不同,对整个网络的影响也不同。也就是说生物网络中节点的地位与其在细胞功能上的重要性有关,某些节点(关键节点)的存在对网络结构和功能具有重大意义[6-7]。例如,在蛋白质相互作用网络中高度关联的节点具有重要的功能,而且其缺失与致命性有关[8]。在基因调控网络中,也需要识别哪种基因控制着许多其他基因,以便其能被当作有机体的全局调节因子进行分析。因此,分析和研究生物网络关键节点及其相互关系,对系统生物学研究越来越重要。然而,经常遇到的问题是不能明确地回答哪些节点是关键性节点。
生物网络的结构特性表明其是典型的复杂网络[9]。为了研究这些大型的复杂网络,研究者们提出了各种不同的网络分析方法,也使用了其他科学领域的分析方法。本文首先分析了几种以图论为基础的判断复杂网络节点关键性的指标——中心性指标,然后总结了几种生物网络关键节点的识别方法,分析了生物网络节点关键性识别与其他复杂网络的区别,并指出了今后研究的方向。
目前,在复杂网络关键节点的识别方面,国内外的很多研究都是以图论为基础,量化关键节点与非关键节点在拓扑性质方面的差异,并以量化值的结果大小作为判别节点关键与否的标准[10-11]。相关图论概念参考了文献[12]。
1.1 中心性指标
复杂网络关键节点的识别可通过对节点的关键性进行排名来完成。一般情况下,事物的排名都是建立在某个相关数值的基础上。例如,中超联赛是根据比赛积分进行排名。在识别复杂网络关键节点的过程中也可以使用相同的方法对节点的关键性进行排名。根据所研究的问题,为每个网络节点分配一个表示关键性的数值,然后依据这些数值对节点进行排名。节点所得的数值称为该节点的中心值,而为每个节点分配数值的函数称为节点的中心性指标,其定义如下:
定义1:设G=(V,E)是一个有向图或无向图,函数C:V→R称为一个中心性指标[13]。
中心性指标为每个节点分配的实数值可以进行两两比较,例如,任意两节点x和y,若C(x)>C(y),则表明节点x比节点y更重要。
1.1.1 度(Degree)中心性指标
网络中任意节点x都有自己的度值d(x)。根据这些度值,可以对网络中的节点进行排名,因而可以形成了一个中心性指标——度中心性指标,记为Cdeg。计算任意节点x的度指标中
心值的公式如下[14]:
Cdeg(x)=d(x)
度指标是一种基于本地的中心性指标,考虑的是相邻节点的情况,反映了节点与周围节点之间建立直接关系的能力。节点的度中心值越高,与之相邻的节点就越多,其在网络中的地位和功能相对来说就可能更重要。任何网络都可使用该中心性指标对节点进行排名。在有向网络中,度指标根据边的方向又分为入度指标和出度指标。
1.1.2 离心率(Eccentricity)中心性指标
在网络模型中,常利用节点间的通信来模拟其所表示的对象之间的相互关系。在研究过程中,通常的做法是假设节点间的通信是通过它们之间的最短路径来完成的。分析网络拓扑结构,可以发现其他任意节点都能以较短的距离到达居于网络拓扑结构中心的点。根据这个思想,Hage和Harary在研究社会网络时,提出了离心率中心性指标[15]。该中心性指标首先要计算节点的离心率。而节点的离心率为当前节点到其他所有节点之间的最短路径长度中的最大值。节点x的离心率记为ecc(x),其离心率越大,就越偏离网络拓扑结构的中心,
其地位也就越低。根据中心性指标的定义,取节点的离心率的倒数作为其中心值,记为Cecc。计算任意节点x的离心率指标中心值的公式如下[16]:
Cecc(x)=1/ecc(x)
其中,ecc(x)=max{dist(x,y):y∈V},dist(x,y)为节点x和y之间的最短路径长度。
离心率指标以整个网络结构的中心为基准,考虑了每个节点在网络中的权益。哪个节点离网络中心越近,对其他任意节点来说,该节点传递信息的速度就比较快,其在网络中的地位也就越高。在解决实际问题时,虽然有些问题要考虑每个节点的权益(例如医院选址),但有些问题则要考虑整体效益(例如商场选址)。
1.1.3 紧密度(Closeness)中心性指标
有研究指出,处于网络节点密集中心的点到其他节点的平均最短路径长度最短,其能够更快地将信息传达到整个网络,在网络通信中起到了关键作用。如何到这样的关键节点呢?学者们提出了紧密度中心性指标,记为Cclo。
利用紧密度中心性指标为每个节点分配中心值时,先要计算每个节点到其他节点的最短路径长度的总和。这样,居于节点密集区域中心的节点会得到一个较低值(总和越小,平均长度就越小)。根据中心性指标定义,中心值越大的节点其地位越重要,所以将最短路径长度总和的倒数作为节点的中心值。计算任意节点x的紧密度指标中心值公式如下[18]:
Cclo(x)=1/∑y∈Vdist(x,y)
其中,dist(x,y)为节点x和y之间的最短路径长度。
紧密度中心性指标反映的是当前节点与其他节点之间连接的密切程度,其最早被用于社会网络中心性的研究。Wuchty等用紧密度中心性指标探讨了复杂网络中心性问题,阐明了地方设施选址问题[18]。在生物网络研究领域,这种中心性指标应用也很广泛。
1.1.4 最短路径介数(Shortest path betweenness)中心性指标
在网络通信中,有些节点扮演了通信“枢纽”的角,这些节点被删除或破坏,部分节点间的通信会被中断,甚至整个网络会陷入瘫痪。因此,从通信量的角度考虑,节点的通信量越大,其在网络中的地位就越重要。因此,可以利用网络中所有最短路径中经过某个节点的
路径的数目占最短路径总数的比例,来衡量该节点在网络中的地位[19]。
网络中任意两节点间的最短路径上的其他节点都承担了这两点间的通信流量。服务对象越多的节点(即经过该节点的其他节点间的最短路径越多的节点),其对于整个网络的通信来说就越重要。计算经过一个节点的通信流量,并将这个数值作为度量其是否是关键节点的指标,就得出了一个中心性指标定义——基于最短路径的介数中心性指标,记为Cspb。
设节点y是节点x和z之间最短路径上的内部节点(y≠x且y≠z),计算节点y的基于最短路径介数指标中心值公式如下[21]:
其中δxz(y)表示节点y所承担的节点x到z的通信比率,其值为σxz(y)/σxz。而σxz表示两节点x和z之间的最短路径数目,σxz(y)表示两节点x和z之间的经过节点y的最短路径数目。如果x和z之间没有最短路径存在(σxz=0),则 δxz(y)=0。
利用介数指标可以确定信息负载繁重的网络节点。节点介数中心值越大,其对网络通信功能的影响就越大。
1.1.5 特征向量(Eigenvector)中心性指标
之前介绍的中心性指标描述的是一个节点对其他节点的影响,但在有些情况下,节点在网络中的地位和功能与其邻居的中心性有很大关联。若一个节点拥有高中心值的邻居,该节点也会有比较高的中心值[20]。这种中心性思想是菲利普·玻纳西奇提出的,他不仅考虑了节点在网络中的位置,而且考虑了相邻节点的反馈信息。这种思想被形式化为一组线性方程,该方程组的最大特征值λ所对应的特征向量就是各个节点的中心值,记为Ceiv。对于任意节点vi,其特征向量中心值计算公式如下[21]:
其中,aij表示所分析的网络的邻接矩阵A的相应元素。如果节点vi和vj之间没有边存在,则这个元素之为0,其与Ceiv(vj)相乘后,相应的项消除。
特征向量指标从节点的地位和影响力角度考虑,把单个节点的影响力归结为所有其他节点影响力的线性组合,不仅能够体现节点在网络结构中的地位,更能反映节点的长期影响力。
1.2 几种中心性指标比较分析
未识别的网络