一种在PPI网络中基于遗传算法识别关键蛋白质的方法

摘要

本发明涉及一种在PPI网络中基于遗传算法识别关键蛋白质的算法。本发明在蛋白质相互作用网络中产生初始种群，对个体的适应度计算，赌轮的方法选择操作，在随机挑选的个体对之间进行交叉操作，变异操作，对多个个体解进行局部优化。本发明克服了已有的方法各自存在的缺陷。本发明对该指标进行优化，融合了生物信息，可靠性更高，减少了许多不必要的计算，而且能够对预测出来的关键蛋白质进行局部优化，提高在关键蛋白质识别方面的效率，扩展了该技术在生物信息领域的应用范围和实用性。

说明书

技术领域

本发明属于生物信息技术领域，主要是在蛋白质相互作用网络中通过遗传算法识别关键蛋白质的技术，特别涉及一种在PPI网络中基于遗传算法识别关键蛋白质的算法。

背景技术

关键蛋白质是指那些生命有机体所必须的蛋白质，敲除关键蛋白质可能会导致生命体无法生存。对关键蛋白质的识别在生物体生存、药物标靶设计、疾病治疗等方面有着重要的应用价值。

在关键蛋白质识别领域，最初是通过生物实验来识别，比如单基因敲除，但是需要花费大量的人力、物力和时间。随着高通量技术的发展，如酵母双杂交、串联亲和纯化等，这些实验产生了大量的蛋白质相互作用关系，所以出现了许多基于蛋白质相互作用网络的识别关键蛋白质的方法。但是这些方法大多都是只考虑了蛋白质相互作用网络拓扑结构，而没有考虑生物信息，或者只考虑了一种生物信息，导致识别出来的关键蛋白质准确率较低。

在本发明作出之前，在已有的方法中，大多都是要计算出所有的关键蛋白质，然后在识别出来的关键蛋白质中取它度较大的P个，这样识别关键蛋白质的缺点是：(1)在实际应用中只关心哪P个的指标较大，关键程度高，而没有必要增加计算量来将蛋白质的某种指标逐一计算，然后对其进行排序，取其中较大的P个。(2)就单个蛋白质而言某种指标较高，但就指标最高的P个而言，其关键性在PPI网络中整体的程度未必最高，也可能只是某一局部顶点的代表，特别是一些采用局部链接指标，或者是采用连接密切度逐步扩大的算法，这样更容易导致最优解的局部性。

发明内容

本发明的目的就是要克服上述缺陷，提供一种在PPI网络中基于遗传算法识别关键蛋白质的算法。

本发明的技术方案是：

一种在PPI网络中基于遗传算法识别关键蛋白质的方法，其主要技术特征在于，包括如下步骤：

(1)在蛋白质相互作用网络中产生初始种群；

(2)对个体的适应度计算：对种群中的个体，通过适应度函数计算其适应度值；

(3)选择操作：对种群中的个体，按其适应度值采用赌轮的方法选择其参加下一代的种群；

(4)交叉操作：交叉操作是按一定概率在随机挑选的个体对之间进行；

(5)变异操作：变异操作是按一定的概率在随机挑选的个体上进行的，在进行变异时，随机挑选新个体中的d个蛋白质，将替换成随机挑选的其他蛋白质；

(6)局部优化：对多个个体解进行局部优化。

本发明的优点和有益效果在于提出了一种衡量Top-P关键蛋白质的整体性指标，并对该指标进行优化，该方法在考虑网络拓扑的基础上也融合了生物信息，使得预测结果更加的准确，可靠性更高。同时本发明提出的方法能够整体度量P个蛋白质的关键性，从而减少了许多不必要的计算，而且能够对预测出来的关键蛋白质进行局部优化。该技术可以提高在关键蛋白质识别方面的效率，扩展了该技术在生物信息领域的应用范围和实用性。

附图说明

图1——本发明流程示意图。

图2——识别出来的关键蛋白质的个数示意图，其中a是取前5％的蛋白质时正确识别出来的关键蛋白质的数量图，b是取前10％的蛋白质时正确识别出来的关键蛋白质的数量图，c是取前15％的蛋白质时正确识别出来的关键蛋白质的数量图，d是取前20％的蛋白质时正确识别出来的关键蛋白质的数量图，e是取前25％的蛋白质时正确识别出来的关键蛋白质的数量图。

图3——识别的准确率比较示意图。

具体实施方式

一、步骤描述

下面结合附图和具体实施方式对本发明进行详细说明。

先输入PPI网络和生物信息，然后

步骤(1)：产生初始蛋白质种群

由于蛋白质的关键性与相应顶点度有密切的关系，以顶点度最高的P个蛋白质为基础产生初始种群，并对蛋白质进行编码，为了防止种群的局部化，增加其多样性，在初始种群中再随机替换一部分蛋白质。设U为蛋白质集合V中P个最高度数的顶点集合，U中顶点的最大的度为maxd，最小的度为mind；设每个蛋白质v的度为d_v，定义h_v＝(maxd-d_v)/(maxd-mind)，产生(0，1)间随机数r，若r＜h_v，则在V-U中选取随机顶点加入U中来替换v。

步骤(2)：计算个体的适应度

因为运用多种生物信息可以有效的提高识别的准确率，所以对蛋白质之间的相似度衡量，通过综合利用蛋白质在PPI网络中及在生物方面的相似度，主要有共同邻居相似度(NTE)，基因表达相似度(GES)，GO语义相似度(GOS)，域交互程度(DS)，系统发育谱相似度(PPS)，通过对这五种相似度进行加权平均，从而形成蛋白质之间的相似度，即：

w_ij＝α₁NTE_ij+α₂GES_ij+α₃GOS_ij+α₄DS_ij+α₅PPS_ij

其中，w_ij为两个蛋白质i和j之间的相似度，权重α_i(i＝1，2，3，4，5)满足α_i∈(0，1)，

如果蛋白质与其他节点联系越紧密，就越有可能成为关键蛋白质，定义紧密程度与蛋白质之间的相似度w_ij有关：

其中，p_ij为蛋白质之间的转移概率或影响力，它反映蛋白质之间联系的紧密程度。

通过选取候选解的方法来识别关键蛋白质，其中每一个候选解含有P个蛋白质，整体度量这P个蛋白质的关键性，通过这些蛋白质与其他蛋白质的联系的紧密度来衡量其关键性，设P个顶点的集合U＝{v₁，v₂，…v_p}，每一个v_i为一个蛋白质，记N_k(U)为距U中顶点的最短距离为k的顶点的集合，即：

|I_u，v|为u到v的最短路径的长度。其中N₀(U)＝U。

定义集合U的关键度，也就是适应度函数：

这里，α_k为系数，α₁，α₂，…α_k递减，α_i∈(0，1)，因为随着路径的增加，邻居间紧密程度会降低，所以为不同的紧密程度附上权值，例如，可设：α_k＝α^k(α∈(0，1))。关键度实际上对U中所有顶点的1至k阶邻居顶点的影响力进行综合评价，在实际计算中，取L为3即可。

步骤3：对个体进行选择操作

本步骤是为了挑选出合适的个体，设V为蛋白质集合，P为关键蛋白质个数，首先为了缩小搜索关键蛋白质的范围，将度最小的若干个顶点去除掉，保留其中V′(V′＜V)个顶点，然后产生m个初始个体，构成初始种群W，每个个体为长度为P的向量，对W中的每一个个体通过适应度函数计算其适应度值，最后根据个体适应度值，采用“赌轮法”选择一个个体，即对个体进行选择操作。

步骤4：对所选择的两个个体实施交叉操作

本步骤是对两个个体之间进行交叉，随机选择两个个体，对每一个个体产生[1，P]间的随机数，以确定交叉的位置，产生j个交叉位置，以p_c的概率对所选择的两个个体在交叉位置上进行交叉操作。对于两个个体V、W，在它的编码的不相同的顶点中随机挑出C个进行互换，例如：

设

其中阴影部分为相同顶点。设交换的长度C＝1，我们在V的不相同部分随机挑选“7”在W中随机挑选“8”进行交换，结果为：

步骤5：按一定概率对随机选择的个体进行变异操作

该操作是按一定的概率在随机挑选的个体上进行的，在个体中产生[1，P]间的随机数，以确定变异的位置，重复d次，挑选出新个体中的d个蛋白质，在[1，V]间选择随机数作为随机挑选的用于替换的蛋白质，以p_m的概率将变异位置上的蛋白质替换成随机挑选的其他蛋白质。

步骤6：多个个体解局部优化

对上述步骤2、3、4、5进行多次迭代操作，可以获得多个个体解，对多个个体解进行局部优化的基本思想是：采用贪婪法，设个体U＝{v₁，V₂，…V_p，}，依次对v_i(i＝1，2，…，p)用N(v_i)＝{v|(V，v_i)∈E}中的结点分别代替v_i，构成新的个体U^*＝{v₁，v₂，…v_p，}，如果ESS(U^*)≥ESS(U)，则用U^*代替U。

二、实施例

识别出来的关键蛋白质的个数

图2中，图a、b、c、d、e分别是取排序靠前的5％、10％、15％、20％、25％的蛋白质作为预测关键蛋白质的候选集，然后再与酵母PPI数据中的关键蛋白质相比较求交集，得出候选关键蛋白质中真实的关键蛋白质的数量。从图中可以看出，EPGA方法能获得比其他关键蛋白质识别方法更好的效果，无论是在取前5％、10％、15％、20％还是取前25％的蛋白质，其正确识别的关键蛋白质的数量与DC、CC、BC、SC、EC、IC、LAC和NC比较，均比这些方法好。

识别的准确率比较

图3是识别蛋白质的准确率的比较，EPGA方法不仅识别关键蛋白质的数量较其他方法要多，而且识别关键蛋白质的准确率(accuracy rate)与DC、CC、BC、SC、EC、IC、LAC和NC相比较，可以看出本发明所提供的方法能够有更高的识别准确率。