一种蛋白质相互作用网络中关键蛋白质发现方法

技术领域

本发明涉及网络技术领域，尤其涉及一种蛋白质相互作用网络中关 键蛋白质发现方法。

背景技术

蛋白质是组成人体一切细胞、组织的重要成分，在几乎所有的生命 系统、调控各种生理/病理进程中发挥重要的作用，是生命活动的主要承 担者。然而，蛋白质功能的发挥不是凭借单个蛋白质独立执行，而是依 靠蛋白质与蛋白质相互作用(protein-proteininteraction,PPI)执行其功 能。因此，蛋白质互作网络的研究已经成为蛋白质研究的热点。蛋白相 互作用网络可以通过一些高通量的实验方法得到，如酵母双杂交、免疫 沉淀串联质谱分析等。

生物系统中蛋白质发挥的作用不是等同的，少量关键蛋白质在维持 生物体正常生理过程中起着至关重要的作用。已有工作表明，一旦移除 这些关键蛋白，可能会造成相关功能模块的生物功能丧失，导致生物体 无法完成正常的生理活动。这些在生物过程中起关键作用的蛋白质的异 常可能引发许多疾病，如神经退行性疾病、癌症等。因此，发现并找到 这些在生物过程中起关键作用的蛋白质对研究细胞的生理调控机制具有 非常重要的生物意义，对药物靶标设计也具有很重要的实际价值。

在生物学领域，一般采取基因敲除、RNA干扰等生物实验的方法控 制相关蛋白质,通过观察生物体能否正常执行生命活动,来判别一个蛋白 质是否是关键蛋白。利用生物实验的方法预测关键蛋白质的方法虽然比 较准确，但是生物实验周期长而且代价高。

另一种方法是采用网络分析方法，利用蛋白质相互作用网络找出起 关键作用的蛋白质。Vinayagam等给出了一种基于控制理论计算关键节 点的方法。该方法首先计算网络的最小输入节点集合，然后将节点从网 络中删除，重新计算新网络的最小输入节点集合。如果新网络的MIS大 于原网络的MIS，则该节点是关键节点。这种方法的缺点在于需要逐个 判断网络中的节点，复杂度很高。

发明内容

(一)要解决的技术问题

本发明提出一种蛋白质相互作用网络中关键蛋白质发现方法，基于 蛋白质节点间的交错连通性，能够找出网络所有的关键蛋白质节点，极 大的提高了计算效率。

(二)技术方案

为了达到上述目的，本发明采用的主要技术方案包括：

一种节点相互作用网络中关键节点发现方法，其特征在于，所述方 法，包括：

S10、基于节点相关作用网络G(V,E)，构造二分图B(V_in,V_out,E)；其>

S20、计算二分图B(V_in,V_out,E)的最大匹配M，令V_in和V_out中的未>in和U_out；

S30、从U_in的所有未匹配节点出发寻找交错路径集合P1，令交错路>

S40、从U_out的所有未匹配节点出发寻找交错路径集合P2，令交错>

S50、令U_in’＝U_in-M-N；U_out’＝U_out-M-N；构造子图B’(U_in’,U_out’,E’)；

S60、对于U_out’中任一节点i_out，如果i_in在U_in’中且i_n不在从i_out出>in，i_out在网络G中的对应节点i为关键节>

可选地，所述步骤S10包括：

针对蛋白质相关作用网络G的节点集合V中的任意节点n，将节点n拆分成n_out,n_in两个节点，得到两个节点集合V_in,V_out；对于n的连边，>out节点，所有入边连接至n_in节点，得到二>in,V_out,E)。

可选地，所述交错路径集合P1和所述交错路径集合P2均为匹配边 和非匹配边交替出现的路径。

可选地，所述关键节点为影响所述节点相关作用网络的最小输入节 点集MDS规模的节点。

可选地，若所述节点相关作用网络G(V,E)为蛋白质相关作用网络， 则所述步骤S60中的关键节点为关键蛋白质节点。

另外，还提供一种电子设备，包括存储器、处理器、总线以及存储 在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程 序时实现如上方法任意一项的步骤。

一种计算机存储介质，其上存储有计算机程序，所述程序被处理器 执行时实现如上方法任意一项的步骤。

(三)有益效果

本发明在实际应用于蛋白质交互网络中用于关键蛋白质的判定具有 切实的实际意义，通过搜索节点在交错路径中的连通关系找出关键蛋白 值，不仅提高了判定的效率，避免了逐个删除节点比较最小输入节点集 大小的复杂运算，而且也为关键蛋白质之间的关联提供了明确的图形化 解释。除了蛋白质相互作用网络外，本算法也适合于任意种类的大规模 网络中关键节点的判定。

附图说明

图1为本发明一个实施例提供的一种人类蛋白质相互作用网络的示 意图；

图2为本发明一个实施例提供的一种二分图匹配的示意图；

图3为本发明一个实施例提供的一种n⁺和n^-之间有交错路径的例子>

图4为本发明一个实施例提供的基于可控性方法的节点分类示意图。

具体实施方式

为了更好的解释本发明，以便于理解，下面通过具体实施方式，对 本发明作详细描述。

现有技术中的另一种方法是从网络分析的角度，基于蛋白质相互作 用网络来进行预测和发现关键蛋白质。复杂网络控制理论是分析蛋白质 相互作用网络的有力工具，从网络控制的角度可以找出在生物过程中起 关键作用的蛋白质。为了控制复杂网络，需要向网络中的部分节点输入 控制信号，通过节点间边的连接，驱动网络的所有节点达到期望的状 态，这些用来输入控制信号的节点称为输入节点。为了完全控制网络所 有节点的状态，所需的最少的输入节点集合称为最小输入节点集 (MIS)。如果在网络中删除一个蛋白质及其交互作用后，控制网络所需 的MIS集合大小增加，那么该蛋白质就称为关键蛋白质。现有工作已经 发现，采用控制理论发现的关键蛋白，大多与癌症相关、或者是病毒和 药物的靶点。

考虑网络G(V,E)，其中V为节点集合，E为边集合。匹配边集M是 一个独立的边集，即边与边之间不共享节点。对于一个节点，如果它是 一条匹配边的终点，那么该节点为匹配节点；否则，为非匹配节点。边 数最多的匹配边集被称为图的一个最大匹配。如果图中所有的节点都是 匹配节点，那么该图中的最大匹配就称为完美匹配。

将网络G(V,E)的最大匹配边集的大小记作|M^*|，那么最小输入定理>I或最小输入节点数N_D为1；否则，等于>

N₁＝N_D＝max{N-|M^*|,1}

也就是说，对于非匹配节点数不为0的网络，输入节点数即为非匹 配节点数，且非匹配节点即为输入节点的一种情况。对于非匹配节点数 为0的完美匹配的网络，输入节点数为1，网络中任一节点均可定义为 输入节点。

为了完全地控制一个网络，需要的最少输入是由网络的最大匹配决 定的。匹配节点由它的前驱节点控制，而未匹配节点则必须由一个外部 输入来控制，故未匹配节点即为网络的输入节点。一旦为每个输入节点 进行输入，那么网络中的节点均拥有了自己的前驱，即网络是完全可控 的。

下面给出关于最大匹配的若干概念。

定义1给定一个二分图G＝(V,E)，在G的一个子图M中，M的边集 中的任意两条边都不依附于同一个顶点，则称M是二分图的一个匹配。

二分图的最大匹配，如图2所示，即是在给定的二分图G＝(V,E)的所 有匹配中，把其中包含的边数最多的匹配找出来。如果一个匹配中，图 中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作 完美匹配。

图2(a)为一个二分图，图2(b)表示该二分图的一个匹配，但非其最大 匹配，图2(c)为二分图的一个最大匹配，图2(d)表示一个完美匹配，图中 的每个顶点均被匹配上了。

定义2未匹配点：设V_i是图G的一个顶点，如果V_i不与任意一条>i是一个未匹配点。

交错路径：如果G中存在这样一条路径，该路径上匹配边和非匹配 边交替出现，那么这个路径称为交错路径。增广路径是端点均为非匹配 点的交错路径。一条交错路径上的两节点i,j，称i和j是交错连通的。

关键节点：如果从网络中移除一个节点后，最小输入节点集MDS的 规模(|MDS|)增大，则称该节点是关键节点。

如图4所示，(a)显示了一个简单有向网络，根据结构可控性的计 算结果，MDS是{1,2,6}，|MDS|＝3。(b)、(c)和(d)分别表示移除 一个节点后，|MDS|的变化情况；(b)表示移除节点4后，|MDS|增加 了1，节点4是关键节点；

控制可达集：节点n的控制可达集是连接n的交错路径上所有节点 的集合。

邻接定理：

(1)对于任意的MDS，每个输入节点的控制可达集包含着所有可 能成为驱动节点的节点；

(2)如果一个节点不属于任何输入节点的控制可达集，则该节点一 定不属于任何最小输入节点集，即不会作为网络G的输入节点。

实施例1

考虑有向蛋白质相互作用网络G(V,E),其中V为节点集合，表示蛋 白质；E为边集合，表示蛋白质之间的相互作用。现有工作发现，网络 控制理论可以用来发现关键蛋白质节点，即删除该节点后使控制网络所 需的最小输入节点集大小增加的节点。这些蛋白质节点已经被证实与癌 症相关，并且是药物或病毒的靶点。本发明提出一种关键蛋白质的判定方法，具体过程如下：

1、首先基于蛋白质相关作用网络G(V,E)，构造二分图 B(Vin,Vout,E)。具体过程为，将网络G的节点集合V中的任意节点n， 将其拆分成n_out,n_in两个节点，这样会得到两个节点集合V_in,V_out；对于n>out节点，所有入边连接至n_in节点，这样>in,V_out,E)；

2、计算二分图B的最大匹配M，令Vin和Vout中的未匹配节点分 别为集合U_in和U_out；

3、从U_in的所有未匹配节点出发寻找第一类交错路径集合P1，令交>

4、从U_out的所有未匹配节点出发寻找第二类交错路径集合P2，令>

5、令U_in’＝U_in-M-N；U_out’＝U_out-M-N；构造子图B’(U_in’,U_out’,E’)；

6、对于U_out’中任一节点i_out，如果i_in在U_in’中且i_in不在从i_out出发的>in，i_out在网络G中的对应节点i为关键蛋白质>

7、对于U_out’中的所有节点，重复上述步骤6，使得U_out’中的所有节>

本实施例中通过搜索节点在交错路径中的连通关系找出关键蛋白 值，不仅提高了判定的效率，避免了逐个删除节点比较最小输入节点集 大小的复杂运算，而且也为关键蛋白质之间的关联提供了明确的图形化 解释。除了蛋白质相互作用网络外，上述方法也适合于任意种类的大规 模网络中关键节点的判定。

验证例

为了说明本发明的有效性，在人类蛋白质相互作用网络上进行了验 证。蛋白质交互网络的数据选取自论文“A.Vinayagam et al.,“A directed protein interactionnetwork for investigating intracellular signal transduction,”Sci.Signal.,vol.4,no.189,2011”。该网络包括6339 个蛋白质，34813条相互作用有向边。

本发明在该网络上运行本发明给出的算法即方法，共找出1330个关 键蛋白质。网络结构与关键蛋白质如图1所示。将这些蛋白质与其他数 据库进行比较，包括OnlineMendelian Inheritance in Man(OMIM) (https://www.omim.org/)，DrugBank(https://www.drugbank.ca/)，结果表明 本发明方法找出的关键蛋白质大多与疾病基因、药物靶点相关，说明了 本发明方法的有效性。部分关键蛋白质列表如表1所示，图1中黑色节 点表示本发明方法找出的关键蛋白质节点。

表1.部分关键蛋白质列表

下面证明本发明的算法即方法的正确性。如图3所示，首先证明引 理1。

引理1：G(V,E)对应的二分图B(V⁺,V^-,E)中，删除n⁺和n^-后，若形>

证明：反证法，假设节点n是关键节点，并且删除节点n会形成一 条增广路径。节点n至多有1条匹配入边和匹配出边，删除后最大匹配 数最多减少2，发现增广路径匹配数再加1，总的最大匹配最多减少1， 与删除关键节点最大匹配数减2的特征不相符。

关键节点判定定理：对于有向图G(V,E)，令其对应的二分图为 G(V⁺,V^-,E)，最大匹配为M^*，令节点n在二分图中的对应节点为n⁺和>-，节点n是关键节点，当且仅当同时满足如下条件：

(1)n⁺和n^-均有匹配边；

(2)n⁺到V⁺中的未匹配节点、n^-到V^-中的未匹配节点之间均不存在>

(3)从n⁺匹配边出发到n^-不存在交错路径。

证明：

对于二分图G(V⁺,V^-,E)中的n⁺和n^-，

首先证明条件1：a)根据关键节点的定义，删除n⁺和n^-，匹配数应>+和n^-均无匹配边，则删除节点后没有匹配边被移除，匹>+或n^-有一个没有匹配边，删除节点后至多有一条匹配>+和n^-均有匹配边。条件(1)证>

然后证明条件2：b)反证法。假设n⁺到V⁺中的未匹配节点、n^-到V^-中的未匹配节点不存在交错路径，分为以下两种情况：(1)n^-与V^-中的>-中的未匹配节点是输入节点，>-在输入节点的控制可达集中。根据邻接定理，n有可能成为输入节>+到V⁺中的未匹配节点存在交错路径。此情况下，V⁺中的未匹>+在未饱和节点的未饱和可达集中。根据邻接定>

证明条件3：c)n⁺到未饱和节点之间不存在交错路径且n^-到未匹配节>+和n^-在同1条匹配交错>+和n^-不在同1条交错路径上。在情况i)的条件下，n⁺和>-之间若存在交错路径，n⁺到n^-的路径长度一定是奇数的。交错路径的>+和n^-之后，会形成1条增广路径，根据引理，n不可能是关键节点，>+和2^-之间有匹配路径>-,1⁺,4^-,5⁺,3-,2⁺}，且2⁺和2-的匹配边(2⁺,3^-)和(1⁺,2^-)均在该路径上；(b)>

如果n⁺到n^-的交错路径两端是非匹配的，删除n⁺和n^-后不会形成增>+匹配边出发的交错路径，>-中的匹配节点，或V^-中的未匹配节点，也可能交错>+本身。这三种情况下，删除n⁺，>+非匹配边出发的匹配交错路径，由于删>+会移除一条非匹配边，一定不会形成增广路径。同理，删除n^-也不>+和3^-之间有匹配路径{3^-,5⁺,4^-,3⁺}，且2⁺和2^-的匹配>

另外，本发明实施例还提供一种电子设备，包括存储器、处理器、 总线以及存储在存储器上并可在处理器上运行的计算机程序，所述处理 器执行所述程序时实现如上述方法任意一项的步骤。

此外，本发明实施例还提供一种计算机存储介质，其上存储有计算 机程序，所述程序被处理器执行时实现如上述方法任意一项的步骤。

最后应说明的是：以上所述的各实施例仅用于说明本发明的技术方 案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明， 本领域的普通技术人员应当理解：其依然可以对前述实施例所记载的技 术方案进行修改，或者对其中部分或全部技术特征进行等同替换；而这 些修改或替换，并不使相应技术方案的本质脱离本发明各实施例技术方 案的范围。