基于节点失效的关键蛋白质识别算法研究

许睿,张利伟

(河南科技学院,河南新乡453003)

基于节点失效的关键蛋白质识别算法研究

许睿,张利伟

(河南科技学院,河南新乡453003)

蛋白质参与了生命活动中大部分的生物过程,是生物体生长过程中重要的物质基础.由于蛋白质数量巨大,所承担的作用也各不相同,如何在蛋白质网络中准确地识别出的具有重要作用的关键蛋白质,是蛋白质组学中亟待解决的重要问题之一.针对目前蛋白质节点删除策略存在破坏蛋白质网络拓扑结构这一问题,提出基于节点失效的关键蛋白质识别算法.用蛋白质节点对之间的最短距离,来描述两个节点之间的潜在的影响能力,在衡量某个蛋白质节点是否为关键蛋白质的时候,将该节点失效处理,通过统计节点失效对于整个网络的影响程度,从而识别出相应的关键蛋白质.

节点删除法;节点失效法;蛋白质网络;关键蛋白质

在识别关键节点的算法中,基于节点删除的关键节点识别算法是一种比较简单、有效的方法.通过度量删除每一个节点后,整个网络遭到破坏的程度,区分节点的重要性程度[1].该算法利用了网络中节点对于网络的连通性的影响,以及节点对于网络拓扑结构的影响,从网络被攻击的角度考虑节点重要性.但是该算法也存在着不足,首先,基于节点删除的方法会删除重要性高的节点,这样会破坏整个网络的拓扑结构,原本连通的节点会失去联系,从而影响后续节点的评估结果;其次,在蛋白质网络中,关键蛋白质挖掘的方法大部分都是局限在对蛋白质网络中单个关键蛋白质节点的挖掘,但有时网络中的关键蛋白质节点不止一个,而是多个.

针对这些不足,本文提出基于节点失效的关键蛋白质识别算法,用基于节点失效的方法,替代传统方法中将节点直接删除的做法,在保证网络连通性不变和网络拓扑结构不变的基础上,将该蛋白质节点“失效”处理,从而可以动态的识别蛋白质网络中一系列的关键蛋白质节点.

1 相关定义说明

1.1 蛋白质网络

蛋白质网络通常可以抽象为由多个蛋白质节点和节点间的相互作用关系所形成的网络图G=(V,E),V为蛋白质节点的集合,E为蛋白质节点间相互作用的边的集合.这里,为了方便描述,用n表示网络中所有节点数,m表示网络中所有的边数.通常,网络图可以用邻接矩阵表示,如果节点间没有连接,那么就用0表示,否则为相应的数值.

对于网络图G的邻接矩阵A,对于任意有连接的节点对,如果它们之间的权重均为1,那么就称图G为无权图,否则图G为加权图.如果它们之间的权重忽略方向性,那么图G为无向图,否则图G为有向图.一般情况下,无特殊说明,所研究的蛋白质网络图为无向无权图.本文采用的也是无向无权图.

1.2 网络资本值

本文在蛋白质网络中,用节点对之间最短路径来描述某个节点潜在的相互影响力,它从局部的角度描述该节点对网络中其余节点,尤其是周边蛋白质节点的影响力,反映了该蛋白质节点与网络内其余节点之间相互作用的强弱.对整个蛋白质网络而言,还需要分析该蛋白质节点对整个蛋白质网络的全局影响力,因为一个蛋白质节点的失效,影响的不仅是其周边与其直接相连的蛋白质节点,还可能会造成其它蛋白质节点之间的连锁反应,进而影响整个蛋白质网络的功能.为此,本文定义了蛋白质网络资本NC (Network Cost),用以描述整个蛋白质网络内蛋白质节点相互作用的强弱.网络资本NC公式如下

1.3 关键蛋白质节点集合

在蛋白质网络中,蛋白质节点和蛋白质复合物之间是相互影响的,有时一个单独的关键蛋白质改变只能对该蛋白质所在的蛋白质复合物产生较大影响,但对其他蛋白质复合物和整个蛋白质网络影响较小.如果多个关键蛋白质协同作用,则会对整个蛋白质网络的功能产生很大的影响.如同现实中的交通网络堵塞,有时候是单一关键节点造成网络堵塞,有时是多个关键节点相互影响,造成一片区域堵塞.因此,关键蛋白质识别不仅要考虑每一个关键蛋白质的影响,而且要考虑到多个关键蛋白质所形成的关键蛋白质集合的协同影响[2-3].

本文定义一个关键蛋白质集合的概念.关键蛋白质集合是指使蛋白质网络的网络资本值下降到一定程度(阈值Tmin)时失效节点的集合.f(G)为蛋白质网络资本值下降函数,Gc为G去掉节点集合c后的子网,△fNC(Gc)为G变成Gc后网络资本的改变值,使△fNC(Gc)→Tmin的网络元素集合L=C.对于不同的蛋白质网络,它们的拓扑结构有很大的差异,因此阈值Tmin必须根据具体的蛋白质网络来进行确定,本文将阈值Tmin设置为0.3.

1.4 蛋白质节点删除法

复杂网络中的关键节点识别大多采用节点删除法[4-5].节点删除法首先统计网络中所有节点的度,然后按序选取一定比例的、度数较高的节点,依次进行删除.每删除一个节点,就评估该节点删除后对于蛋白质网络造成的破坏程度,破坏程度越大,表明该节点越重要,说明该节点就是关键节点.在蛋白质网络中,蛋白质节点删除法对蛋白质网络的整体连通状况存在三个方面破坏.首先,被删除的蛋白质节点与剩余蛋白质节点不再连通;其次,被删除的蛋白质节点相互之间不再连通;第3,剩余蛋白质节点中部分蛋白质节点之间的路径可能由于该蛋白质节点的删除而增长甚至不再连通.用这3种损失之和表示蛋白质节点删除后对整个网络连通状况的总破坏程度,也就是被删除的蛋白质节点的重要性指标.

如果节点的删除会使得原本互联互通的网络不再连通,将严重影响对网络节点重要性的正确评估，如图1所示.

图1由8个节点组成一个无向连通图,节点之间重要性测度都为1,其中节点3和节点6的度数最高,在删除节点6之后,网络拓扑结构发生变化,原来的连通图变为非连通图,形成3个非连通分量,对于孤立的节点7和节点8而言,两个节点的重要性的测度都将变为0,没有办法对二者的重要性进行比较.

图1 节点删除法对比Fig.1 Comparison ofeliminatingnode“6”

2 基于节点失效的关键蛋白质识别算法描述

鉴于节点删除法存在的弊端,本文对蛋白质网络中关键蛋白质的识别采用蛋白质节点失效法.节点动态失效是指在评估蛋白质节点重要性时,并不删除该蛋白质节点,而是保持该蛋白质节点在网络拓扑结构中的相对位置不变,但认为该蛋白质节点已经“失效”.实际上,对于一个蛋白质网络来说,当采用最短路径算法计算节点对之间联系程度时,任意两个蛋白质节点之间相互影响(或作用)值的最小值是网络直径的倒数.网络直径(Network diameter)是指图G中所有蛋白质节点对之间最短路径长度的最大值,可记为D.当评估蛋白质节点j重要性时,将所有到节点j的节点的最短路径长度dij重新定义为

由于网络直径是蛋白质网络中所有蛋白质节点对之间最短路径的最大值,经过重新定义后,蛋白质网络中所有到蛋白质节点j的蛋白质节点最短路径长度已经超过了网络直径,而蛋白质节点j的可达性为dij的倒数,这些蛋白质节点对蛋白质节点j的影响力将大幅下降,因而可将蛋白质节点j认为是处于失效状态,但在蛋白质网络拓扑结构图中,蛋白质节点j仍然存在,并不影响网络的拓扑结构,不会导致其他关键蛋白质的重要性丧失,也不会出现前述的蛋白质网络解体现象的发生,从而避免了蛋白质节点删除法的弊端.

当某一个蛋白质节点j失效时,将与蛋白质节点j直接连接的最短路径值d(i,j)和d(j,i)增加D,即d(i,j)→d(i,j)+D,j≠i∈V,d(j,i)→d(j,i)+D,j≠i∈V.在图2中,网络直径D等于4,度数最高的节点是节点3和节点6,节点6的度数为4.当节点6失效后,与节点6直接相连的节点4、节点5、节点7和节点8,它们到节点5的最短路径长度都将增加为1+4=5.如此,某个节点失效前后,蛋白质网络的拓扑结构并未发生改变.

采用的蛋白质节点动态失效策略,当蛋白质网络中重要性高的蛋白质节点失效后,会导致整个蛋白质网络资本值减少,通过计算蛋白质节点失效前后的网络资本值之间差值,与失效前该蛋白质节点的网络资本值的比值,可以作为衡量该蛋白质节点是否是蛋白质网络中关键蛋白质的评价指标.

图2 节点6失效对比Fig.2 Comparison ofinvalidingnode“6”

3 验证及分析

为了验证蛋白质节点失效法和蛋白质节点删除法在识别关键蛋白质时的效率,本文以Yeast数据集[6]为测试对象进行实验,Yeast数据集包含2 361个节点,7 182条边,其构建的网络中平均度值为6,大部分节点的度值为1.首先,蛋白质节点失效法和蛋白质节点删除法同时对于Yeast数据集进行处理,观察两种算法中各个节点失效或者删除后网络资本值的变化情况.其结果如图3所示.

图3 Yeast蛋白质网络资本值下降图Fig.3 The decline ofthe network capital in Yeast PPI network

在图3中,实线表示节点失效法,虚线表示节点删除法,横坐标表示删除或者失效的蛋白质节点的数量,纵坐标表示网络资本值.在相同的网络资本水平上,节点失效法得到的节点数量均小于节点删除法得到的蛋白质节点数量,说明节点失效法在识别关键节点时,得到的关键蛋白质节点的集合更小,从而可以更加准确的找到关键蛋白质节点.在失效节点数量达到480左右时,节点失效法对应的网络资本已经趋近于0,基于网络资本评估的节点失效算法终止,而对于节点删除法需要在失效节点数量达到700左右时,基于网络资本评估的节点删除算法才会终止,节点失效法在识别关键蛋白质节点时比节点删除法收敛效率提高了45%;由于二者都是采用网络资本评价识别关键蛋白质,因此两种方法得到关键蛋白质数量基本一致,但显然节点失效法比节点删除法的网络资本下降更快,因而算法收敛的速度更快.由此可见,在相同实验条件下,节点失效法在识别关键蛋白质时比节点删除法更加准确,效率更高.

4 小结

本文提出了基于节点失效的关键蛋白质识别算法,在保存蛋白质网络拓扑结构完整性的前提下,通过评价节点失效前后蛋白质网络的受损程度识别蛋白质网络中的关键蛋白质节点,避免了节点删除法的缺陷.实验结果表明:采用蛋白质节点失效法不仅可以避免破坏蛋白质网络的拓扑结构,而且蛋白质网络资本收敛速度更快,能够比蛋白质节点删除法更快的识别关键蛋白质.

[1]许进.一种研究系统的新方法:核与核度法[J].系统工程与电子技术,1994,17(6):1-10.

[3]Spirin V,Mirny L A.Protein complexes and functional modules in molecular networks[J].Proc Natl Acad Sci.,2003,100(21): 12123-12128.

[4]陈勇,胡爱群,胡俊,等.通信网中最重要节点的确定方法[J].高技术通讯,2004,14(1):21-24.

[5]李鹏翔,任玉晴,席酉民.网络节点(集)重要性的一种度量指标[J].系统工程,2004,22(4):13-20.

[6]Pajek.Protein-protein interaction network in budding yeast[DB/OL].(2003-07-25)[2015-05-12].http://vlado.fmf.uni-lj. si/pub/networks/data/bio/Yeast/Yeast.htm.

（责任编辑：卢奇）

Node importance ranking of proteins based on network capital assessment

XU Rui,ZHANG Liwei
(Henan Institute ofScience and Technology,Xinxiang453003,China)

Proteins are involved in most of biological processes of living life activities,which are the core material basis during the growth of organism.In protein network,there are huge quantities of proteins,which assume different roles.This is one of the important issues to be solved in proteomics,which is how to accurately identify essential proteins in the protein network.The traditional elimination of protein node method has the problem of destroying network topology.A new algorithm based on the invalidation of protein node method was developed and the shortest distance between a pair of protein nodes was used to describe potential influence of protein nodes in this paper.Finally,the essential proteins in protein network identified by analyzing the declining extent of influence degree before and after invalidating protein node.

elimination of protein node method;invalidation of protein node method;protein networks;essential protein

TP301.6

A

1008-7516（2015）06-0053-04

10.3969/j.issn.1008-7516.2015.06.010

2015-08-06

许睿(1987―),男,河南新乡人,硕士,助教.主要从事数据挖掘和生物信息学研究.