《IPCA算法》PPT课件

作者：李敏，陈建二，王建新，胡斌，陈刚,一种基于距离测定的蛋白质复合物识别算法,概述,本文的算法是一种基于距离的蛋白质复合物识别算法。首先选择权重最大的节点作为种子节点，然后在一定条件下，把优先权最大的邻居节点依次扩展进来。通过这种方法得到一个一个以种子节点为中心的簇，这里簇也即是蛋白质复合物。实验证明本算法比其他已知的蛋白质识别算法具有更强的识别能力。,相关背景及定义,、网络直径在蛋白质网络中对应子图的所有顶点对之间最短路径长度的最大值。,上述统计分析的结果表明，蛋白质复合物内蛋白质顶点之间的最短作用距离一般都比较小，绝大多数不超过2。,、扩展节点与子图的作用概率其中，mvK是指顶点与子图K的顶点之间存在的边数，是指子图K的顶点数。,两个直径相同，拓扑结构不相同的图，为了区分它们我们引入了作用概率的概念。（）中任意一个顶点与剩下的五个节点组成的图的作用概率都为。（）中下面的任意一个节点与剩下的五个节点组成的图的作用概率为。,、蛋白质复合物扩充的条件：给定一个蛋白质顶点和一个蛋白质复合物，该蛋白质顶点若属于该蛋白质复合物必须满足如下两个条件：；（）,计算顶点的权重选择种子扩充簇,算法,、算法的三个步骤,计算顶点权重,）计算出网络图G中每条边的权重，边权重定义为边的两个顶点的公共邻居节点个数；）将每个顶点连接的边的权重求和，计算出网络图G中所有顶点的权重；）按照权重从大到小对这些顶点进行排序。,将队列的首个顶点，即权重最大的顶点作为种子，并将该种子作为识别的蛋白质复合物(称为“簇)的初始状态进行扩充。每扩充完一个簇，队列中对应的该簇的顶点被移除。新簇的种子从剩余队列中产生。队列岛为空时，整个算法结束。,选择种子,对簇的每个邻居节点进行考虑。簇的每个邻居节点都拥有一个被扩充的优先权，由该节点与簇内顶点连接的边数以及这些边的权重之和决定，连接的边数越多，权重和越大，优先权越高。进行簇扩充时，首先考虑优先权最高的邻居节点作为候选的扩充节点。符合扩充条件的候选扩充节点才能被加入簇。一旦有一个新的候选扩充节点被加入簇，簇的邻居节点就进行更新，并重新计算其优先权。,扩充簇,实验一、参数对实验结果的影响分析,实验二、与数据库中的已知蛋白质复合物比较,主要从匹配程度、敏感度、特异性、综合评价几方面考察,匹配程度：（，）,敏感度：指已知蛋白质复合物中被算法标识出来的部分所占比重,特异性：指算法识别的蛋白质复合物中识别正确的部分所占比重,综合评价：,覆盖率：（）,当时，产生的蛋白质复合物的敏感度大于.，接近，算法的特异性比较低，原因可能是，已知蛋白质复合物的不完整性造成的。我们也可以看出使用的参数要比要大一点。,实验三、蛋白质网络与随机网络的比较,为了进一步说明算法IPC识别的蛋白质复合物很难随机得到，我们将算法IPC应用于随机网络，该随机网络是原酵母蛋白质网络经过随机化处理得到的，与原酵母蛋白质网络具有相同的节点度分布。算法IPC从随机网络和酵母蛋白质网络中标识的已知蛋白质复合物数量的比较结果如图所示,说明：从酵母蛋白质网络中识别的蛋白质复合物的大小从到之间；而从随机网络中是别的蛋白质复合物大小从到。,为了考察随机网络中识别的小复合物是否有意义，我们把它们与已知蛋白质复合物进行了比较，结果如图所示,说明：从图中可知，当匹配阈值时，酵母蛋白质网络识别的复合物超过个与已知蛋白质匹配；而随机网络中识别的蛋白质复合物为。这说明随机网络破坏了蛋白质相互作用中的生物本质特性。,实验四、与其它算法的比较,到目前为止，每一种实验技术或计算方法预测出来的蛋白质相互作用数据都不可避免地具有一定程度的假阳性和假阴性。所以，好的蛋白质复合物识别方法应该对蛋白质网络中存在的假阳性和假阴性具有很好的健壮性。这里我们用随机增加和移除一定比例的边来模拟蛋白质网络的假阳性和假阴性。随机增加边的比例从10到100，从这些具有高的假阳性的数据中进行蛋白质复合物识别，并将识别出来的结果与已知蛋白质复合物进行匹配，匹配的结果如图所示,实验五、算法的健壮性,图（）：随着假阳性的增强，算法IPC能够标识出来的已知