文档介绍：作者:李敏,陈建二,王建新,胡斌,陈刚 一种基于距离测定的蛋白质复合物识别算法概述?本文的算法IPCA是一种基于距离的蛋白质复合物识别算?法。首先选择权重最大的节点作为种子节点,然后在一定条件下?,把优先权最大的邻居节点依次扩展进来。通过这种方法得到一?个一个以种子节点为中心的簇,这里簇也即是蛋白质复合物。? 实验证明本算法比其他已知的蛋白质识别算法具有更强的识?别能力。相关背景及定义 1、网络直径 在蛋白质网络中对应子图的所有顶点对之间最短路径长度的最大值。 上述统计分析的结果表明,蛋白质复合物内蛋白质顶点之间的最短作用距离一般都比较小,绝大多数不超过 2。 2、扩展节点与子图K的作用概率INvk INvk= 其中, mvK 是指顶点v与子图 K的顶点之间存在的边数,nK是指子图 K的顶点数。 K vKn m两个直径相同,拓扑结构不相同的图,为了区分它们我们引入了作用概率的概念。(a) 中任意一个顶点与剩下的五个节点组成的图K ’的作用概率都为4/5。(b)中下面的任意一个节点与剩下的五个节点组成的图K ’的作用概率为 1/5。 3、蛋白质复合物扩充的条件:给定一个蛋白质顶点v和一个蛋白质复合物K ,该蛋白质顶点v若属于该蛋白质复合物K必须满足如下两个条件: INvK ?Tin; SP(K+v) ?d. ?计算顶点的权重?选择种子?扩充簇 IPCA算法 1、IPCA算法的三个步骤计算顶点权重 1)计算出网络图 G中每条边的权重,边权重定义为边的两个顶点 的公共邻居节点个数; 2)将每个顶点连接的边的权重求和,计算出网络图 G中所有顶点 的权重; 3)按照权重从大到小对这些顶点进行排序。?将队列Sq的首个顶点,即权重最大的顶点作为种子,并将该种子?作为识别的蛋白质复合物(称为“簇")的初始状态进行扩充。每扩?充完一个簇,队列Sq中对应的该簇的顶点被移除。新簇的种子从?剩余队列Sq中产生。队列岛为空时,整个算法结束。选择种子对簇的每个邻居节点进行考虑。簇的每个邻居节点都拥有一个被扩充的优先权, 由该节点与簇内顶点连接的边数以及这些边的权重之和决定,连接的边数越多, 权重和越大,优先权越高。进行簇扩充时,首先考虑优先权最高的邻居节点作为候选的扩充节点。符合扩充条件的候选扩充节点才能被加入簇。一旦有一个新的候选扩充节点被加入簇,簇的邻居节点就进行更新,并重新计算其优先权。扩充簇