breakout:when bulls or bears get organized
基于拓扑结构的生物网络关键节点识别研究进展
生物网络
第 30 卷 第 3 期 2009 年 Vol.30 No.3 玉林师范学院学报（自然科学） JOURNAL OF YULIN NORMAL UNIVERSITY (Natural Science) 基于拓扑结构的生物网络 关键节点识别研究进展 □黄海滨1，邵 平2 （1. 玉林师范学院 数学与计算机科学系 博士 副教授，广西 玉林 537000） （2. 玉林师范学院 物理与信息科学系 博士 教授，广西 玉林 537000） 【摘 要】与生物学实验方法及其它方法相比，基于拓扑结构的生物信息学方法在生物网络关 键节点识别上有独特优势. 本文从节点的中心性测度、网络的拓扑参数及层次结构等几方面总结了生 物网络的主要拓扑特征；比较了蛋白质网络、代谢网络及基因调控网络关键节点识别的主要方法；分 析了相关的一些算法. 最后指出存在的一些主要问题，并提出解决的思路及进一步研究的方向. 【关键词】关键节点；生物网络；识别；拓扑结构；复杂网络 【中图分类号】0189 【文献标识码】 A 【文章编号】1004-4671（2009）03-0006-05 数 学 研 究 Progress of Essential Nodes Identification in Bionetworks Based on Topological Structure HUANG Hai-bin1，SHAO Ping2 (1. Associate Professor, Ph. D, Dept. of Math & Computer Science，Yulin Normal University, Yulin, Guangxi 537000) (2. Professor, Ph. D, Dept. Physics and Information Science, Yulin Normal University, Yulin, Guangxi 537000) Abstract: Compared with other methods such as biological experiments, bioinformatics methods based on topological structure possess particular advantage in the identification of essential nodes in bionetworks. The main characteristics of bionetworks are summarized from the central measures, the topological parameter and the structure of the nodes; the main techniques and algorithms relation to the identification are analyzed. While pointing out problems standing in the process, this paper gives ideas to the solutions and brings forward several directions to further studies at last. Key words: essential nodes; bionetworks; identification; topological structure; complex networks 1 引言命活动是生物体内大量相互作用的产物， 大多数生物学特征本质上是由细胞内蛋白 质、DNA、RNA、小分子之间复杂相互 作用的生物网络(基因调控网络、新陈代谢网络、 生 蛋白质交互网络等)的外在表现. 从复杂系统的观点 出发，利用生物信息学方法分析大量的生物实验数 据来反向分析和挖掘特定生物分子之间的关联信 息、揭示其复杂的作用机理等成为生物信息学研究 的热点. 大量观察表明节点在生物网络拓扑结构中 黄海滨，邵 平 基于拓扑结构的生物网络关键节点识别研究进展 越大. (5)偏心度(eccentricity eccentricity)：网络G中 节点v的偏心度是从v到其他节点距离中的最大值， 即 ε G(v) = maxu∈V(G)d(u, v)；G中所有节点的偏心度 的最小值即为G的半径，即rad(G)=minu∈V(G)ε (u)，同 时有rad(G) # diam(G) # 2rad(G). (6)特征向量 (Eigenvector centrality)：该测度要 在网络总体结构中找到最居核心的节点；节点的测 度值越大意味着与它邻接的其它节点的测度值也较 高，说明该节点越居于核心. (7)点覆盖性 (Vertex cover centrality)[40]：出现 在所有最小点覆盖集中的节点集为骨干点覆盖集， 认为这些节点的拓扑重要性最大；在所有最小点覆 盖集中均不出现的节点集为非覆盖集，节点的拓扑 重要性最小；而非骨干覆盖集内的节点出现在最小 覆盖集/非覆盖集皆有可能，其拓扑重要性在前两 者之间. 此外，节点凝聚度[41]和节点的其它测度[42]也可 以提供节点重要性一般意义上的依据，运用在生物 网络上还必须结合更多具体的结构信息进行分析和 研究. . 网络主要参数及其特征 把生物体内的各种相互作用抽象成复杂网络 来进行研究是生物学信息重要的研究方向. 关于 复杂网络的研究近年来发展很快，1998年Watts和 Strogatz在结合规则网和随机网特点的基础之上，建 立了介于它们之间的小世界网络 [4]，小世界网络同 时具备规则网络和随机网络的特点；1999年Barabasi 和Albert又提出了没有明显特征长度的具有无标度 特征的BA模型，指出现实中建立的很多复杂网络 都是无标度的[5]. 细胞内分子相互作用网络的结构特 性，包括度分布、最短路径、聚集性等与其它复杂 系统网络在很大程度上是一致的，说明可能存在相 似的法则控制着多数现实中的复杂网络系统. (1)度分布(degree distribution)：2000年Jeong等 [7] 人 对43种生物体组织新陈代谢过程的研究表明大 多数真实生物网络的节点度遵循幂律分布，即P(k) ∝k-γ，其中P(k)是节点度值为k的概率，幂指数γ是 大于0的常数(通常在2.0~2.4之间). (2)聚集系数(clustering coefficient) [4]：度为ki的 节点i的ki个邻居之间实际存在的边数Ei与它们之间 最多可能边数ki(ki-1)/2之比即为i的聚集系数，即 Ci=2Ei/(ki(ki-1)) 的地位与它在细胞内功能上的重要性有关，外界环 境变化或者内部冲突作用于具有不同拓扑特性的节 点会导致网络表现出不同程度的鲁棒性或脆弱性 [1-2]. 当外界选择特定的网络关键部分进行破坏时，少数 关键节点的移除将把系统分裂成一些小而孤立的节 点群，甚至可能观察到系统的相变和整个网络的解 体，这是网络脆弱性的表现. 基于拓扑结构的生物网络关键节点的研究通过 揭示关键节点与相关拓扑特性的关系，为描述和理 解活细胞内部相互作用的拓扑结构与动力学特征以 及功能的复杂性提供有效的方法和手段；通过发现 关键分子及其相互关系，从系统水平上为疾病诊 治、药物设计等 [3]从生物信息学的角度提供有价值 的理论和方法；通过引入新的计算理论和方法改进 现有模型和算法，探索更有效的关键节点识别技 术，深化信息技术在生命科学领域的应用. 本文的其余部分主要从生物网络的拓扑参数及 特征、基于拓扑结构关键节点识别技术等几方面总 结了现有的研究成果，指出存在的主要问题，最后 提出进一步研究的思路. 数 学 研 究 2 生物网络的拓扑特征 . 节点的中心性测度 节点的中心测度衡量节点在网络中影响能力的 大小，通过网络的拓扑属性可了解该对象获得、 控制信息及资源的能力. 节点度是最常用的中心测 度，此外常用的节点测度还包括紧密度、介数、核 数、子图数、偏心度、特征向量等[6]. (1)紧密度(closeness centrality)：表示当前节点 与所有其它节点连接关系的密切程度，它反比于该 节点与其它节点距离之和. (2)介数(betweenness centrality)：介数定义为 网络所有的最短路径中经过当前节点的数目，它反 映节点在特定网络拓扑结构中所处位置的枢纽程 度，通过它可以有效地区别出模块内、外的边. (3)核数(core centrality)：网络的中k-核 (k-core)是指反复去掉度小于或等于k的节点后，所 剩余的子图. 若一个节点存在于k-核而在(k+1)-核 中被移去，那么该节点的核数为k. (4)子图数(subgraph centrality)：表示节点出现 在不同子图中的次数. 由于回路与网络中的子图有 关，子图数实际上就是网络中节点参与的回路数， 并且长度越短的回路的权重越大，即子图越小权重 2009 年 玉林师范学院学报 第3期 一个节点的聚集系数刻画了这个节点周围的节点彼 此之间联系的紧密程度，整个网络的聚集系数C就 是所有节点聚集系数的平均值. (3)特征路径长度(characteristic path length) [4]： 网络的平均路径长度L定义为所有两节点之间距离 的平均值，即 L= 1 dij N (N - 1) /2 !j i$ 其中N为网络节点数，L也称为网络的特征路径长度 (characteristic path lenth). 细胞内部的小世界特性(短 的平均最短路径L和大的平均聚集系数C)最先在新 陈代谢中发现[7]. 3 关键节点研究与DNA处于整个生物遗传信息传递与表达过程 中的核心地位相适应，基因调控网络在生物网络中 也起着核心作用，蛋白质网络及代谢网络都与它有 着密不可分的联系. 由于它们各自有不同的特性， 在研究上有不同的侧重，在关键节点的研究和识别 方法上也有所区别. 3. 生物网络的节点及其连接方式 几种生物网络都是通过节点和边来对生物问题 进行抽象而得到相应的图(网络)模型，这些模型在 大多数情形下都呈现某种程度的小世界特性和无标 度特性，因而可以应用图论及复杂网络的研究方法 对它们的关键节点问题进行研究. 节点及其连接(边) 在这些网络中分别定义为： (1)在蛋白质网络、代谢网络和基因调控网络 中，节点分别表示蛋白质分子、代谢物和基因； (2)蛋白质网络以无向边表示分子间的相互作 用，代谢网络一般以有向边表示代谢物之间的转化 关系(反应或酶)，基因调控网络也以有向边表示基 因之间的调控关系. 3. 蛋白质网络的特性及其关键节点 蛋白质关键节点的研究目前大多集中在节点度 的大小上，生物学上通过对S.cerevisiae和E.Coli的移 除分析已经证实，一个蛋白质参与交互作用的多少 与它在网络中的重要性有关，关键蛋白质通常比其 它具有更多的交互数量[2]. 文献[14]从由4743个酶母蛋白质及其23294种交 互所构成的网络中，按节点度从高到低取的1061个 节点作为中枢节点(hubs)，发现其中的43%属于关键 节点，显著高于随机选择20%的期望值，同时还发 现蛋白质网络关键节点的度大概是非关键节点的2 数 学 研 究 倍. 通过对聚集系数及特征路径长度的分析发现， 该网络中的关键节点倾向于具有更高的聚集度，相 互之间也显现出更密切的关联. 文献[6]研究显示， 从酵母蛋白质组中移除某个蛋白质引起的致命性与 节点在网络的中心性测度的大小有关，这些测度 包括蛋白质的度、介数以及子图数等，它们在识别 关键蛋白质时显著优于随机选择方法. 尤其是子图 数，它从结构上提供了关于蛋白质个体在网络中所 扮演角色的重要信息，按它的值从高到低取1%的节 点时最多可以包含有60%的关键蛋白质. 文献[15]把 蛋白质网络和对应的遗传网络综合起来识别关键节 点. 他们把蛋白质的交互作用作为物理交互(physical interactions,PIs)，把影响到表现型(致命或病态)的并 且它们之间具有交互作用的任意两个遗传扰动当 作遗传交互(genetic interaction, GI)，同时定义路径 (pathway)为蛋白质网络中的一个连通子图而关联路 径模式(between -pathway-model, BPM)定义为在 GI网络中相互之间有密集交互的两个不同路径， 这些关系通过贪婪算法获得. 他们从BioGRID数据 库收集了由1869个基因的12850种交互所组成的GI 网络，从多种来源中收集了涵盖6184种蛋白质的 68172种交互构成的PI网络. 通过BPM分析获得140 种模式及124种与各自所在模式的两条路径都有密 集关联的枢纽(pivot)蛋白质，结果显示BPM路径与 对应表现型的相关度显著高于实际网络同一尺度下 随机连接的对照组. 在这些枢纽点中发现其中的72 个是关键节点，大大高于预期的22.6个. 文献[17]从 关键交互作用的角度对由4126个节点和7356条边构 成的酵母蛋白质网络进行了研究，他们首先按一定 的方法估计出节点间的交互作用中有大约2.92%是 关键的，其中大概有43%的关键蛋白质与关键交互 作用有关. 3.3 代谢网络的特性及其关键节点 代谢网络是生物体内发生的多个化学反应的总 和，常用的模型是将代谢物抽象成网络中的节点， 它们之间的有向边表示反应(酶). Jeong等 [7]的研究 表明代谢网络也呈现出小世界特性和无标度特性. Palumbo等 [18]发现致命性缘于因酶缺失而导致网络 中连接相关节点的可选择路径的缺失，这些酶通常 位于代谢模块的边缘并将不同的功能体连系成为一 个相对完整的实体，在这里酶的缺失意味着网络中 对应边的消失. 他们认为关键酶倾向位于那些很小 的代谢模块(2-3个反应)[19]：位于巨大连通分量外面 且具有低邻接度的节点对维持整个系统功能起最关 8 黄海滨，邵 平 基于拓扑结构的生物网络关键节点识别研究进展 系；此外，代谢网络中还存在关键边(即关键酶)的 问题. 针对这些生物网络的不同特点，相应地在各 自关键节点的研究上也有不同的方法：(1)对蛋白 质网络而言，关键节点识别度的提高主要有两条途 径：一是发现与关键蛋白质关系更密切的参数，二 是要充分挖掘现有参数的信息并对多个参数进行有 效整合；(2)代谢网络主要通过研究与维持代谢网络 功能相对完整性有关的路径，分析路径中特定节点 或边的存在与否与一个或多个其它节点的可达性来 判断其关键性；(3)基因调控网络一方面要分析节点 的静态特性，如各个主要拓扑参数的大小、节点的 出度与入度的不同权重等，另一方面要研究节点的 动态特性，如基因表达水平的高低、所处局部结构 的动力学变化等. 键作用. 其研究虽然只引用了酵母静态表示的代谢 网络(目前还缺乏动力学数据)，获得的系统映象的 限制比较大，但纯粹拓扑意义上的分析在很大程度 上还是显现出对生物特性较强的预见能力. Lemke 等[20]的研究了大肠杆菌代谢网络，将某个酶的破坏 性指数d定义为网络中由于该酶的缺失而不能合成 的下游代谢物的数量，发现大多酶的d值很小，只 有少数(9%)的d值较大( $ 5)，且其中包含50%以上的 致命酶. 他们对6种支原体(mycoplasmas)代谢网络关 键酶的预测，得到的结果大都也是一致的[21]. 3.4 基因调控网络的特性及其关键节点 不少研究认为蛋白质交互网络的拓扑特性与基 因的关键性乃至细胞的鲁棒性有强烈的关系 [2,23]， Hsuan从E.coli的蛋白质交互作用和代谢网络对关键 与非关键基因进行了比较分析，发现关键基因有着 比非关键基因更显著的邻接度，关键基因还与其它 拓扑特性如聚集系数、特征路径长度、网络直径及 介数等有关. 文献[22]指出节点的致命性与其邻接度的相关 度很弱，一些高邻接度蛋白质节点的移除对表型并 没有显著影响，同时网络的拓扑对预测基因对环境 扰动的反应只起到很微小作用，认为：(1)基因的邻 接度与它被移除后对适应性影响的大小取决于它处 于平衡状态下的表达水平；(2) 基因的邻接度与遗 传变异的关系基本上不存在，然而当具有相同结构 的多个网络进行独立演化时，一些节点持续地显现 出或高或低的多态性；(3)某些基因在进行独立演化 时表现出较低的多态性而较高的分岐度. 他们把这 些归因于实际生物网络与理论上理想网络的潜在区 别以及进化过程中的意外，或者说细节起了决定作 用. Haiyuan等[14]他们发现调控对象越多的调控因子 (蛋白质)成为关键节点的可能性就越大；就基因的 关键性而言，只有一个转录调控因子基因的可能性 最大，具有较少(2-9)转录调控因子基因的可能性 次之，具有较多( $ 10) 转录调控因子基因的可能性 最低；基因的功能越多就越有可能成为网络中的关 键节点. 文献[23]指出基因的关键性与相应蛋白质度 的关系很弱，认为蛋白质网络的拓扑结构对特定基 因的关键性影响很少. 另外，最近的其它研究指出 [16] ，关键性与真核基因的进化保守有关. 一般来说，蛋白质网络的关键节点倾向于具有 较大的节点度、较多的子图数，而代谢网络中那些 位于巨大连通分量外面且节点度小的节点成为关键 节点的可能性比较大，基因调控网络的关键节点与 节点度等拓扑参数在不同的情形下呈现出不同的关 4 总结与展望基于拓扑结构的生物网络关键节点的研究及识 别依赖于网络及节点的拓扑特征，它们是识别过程 的关键所在，目前的研究在取得很大进展的同时仍 然面临着诸多困难和挑战，主要表现在：关键节点 的识别率低，还不足50%；分析依据不充分，仅依 赖少数已有的特征量并不能全面地刻画结构非常复 杂的真实网络；各个参数在识别过程中所处的地位 及作起的作用不明确，不同研究得出的结论并不完 全一致甚至互相矛盾；孤立或者零碎地使用少数参 数或特性分析关键节点，对节点缺乏从全局和整体 上的把握；研究环节上有脱节现象，只利用生物网 络的一些拓扑参数“自上而下”地推断关键节点， 没有结合由生物学实验确定的已知关键节点的拓扑 特性进行分析；算法设计的针对性不足，没有融入 生物网络拓扑结构的特点，对关键节点分析与识别 过程的动态性也缺乏考虑，随着的效率迅速下降. 因此，下面几点是今后进一步研究的方向：(1) 多方位观察并发现生物网络其它拓扑特性，充分挖 掘拓扑结构方面的其它信息，引进更多的能有效反 映网络拓扑结构的参数；(2)从已有生物实验数据中 挖掘出已知关键节点的拓扑特征，通过理论和实际 分析的结合找出各个网络参数与关键节点相关程度 的大小，全面有效地评估包括关键节点在内的不同 类型节点在各自网络结构中的地位及相互关系；(3) 针对生物数据的可靠性和完整性明显不足的现实， 有必要研究数据的处理和使用方法以保证不同实验 结果的一致性和有效性；(4)引入先进的算法理论和 方法，结合生物网络的特点改进现有的各种算法并 发展新的算法，提高关键节点的识别率、精确度及 数 学 研 究 2009 年 玉林师范学院学报 第3期 运行速度；(5)蛋白质网络、代谢网络及基因网络虽 然各有特点，更多的是它们之间不可分割的联系，在 分别把握各类网络关键节点问题的基础上，有必要探 讨多种复杂网络关系背景下的关键节点问题.
