IPCA算法.ppt

《IPCA算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、作者：李敏，陈建二，王建新，胡斌，陈刚一种基于距离测定的蛋白质复合物识别算法概述本文的算法ＩＰＣＡ是一种基于距离的蛋白质复合物识别算法。首先选择权重最大的节点作为种子节点，然后在一定条件下，把优先权最大的邻居节点依次扩展进来。通过这种方法得到一个一个以种子节点为中心的簇，这里簇也即是蛋白质复合物。实验证明本算法比其他已知的蛋白质识别算法具有更强的识别能力。相关背景及定义１、网络直径在蛋白质网络中对应子图的所有顶点对之间最短路径长度的最大值。上述统计分析的结果表明，蛋白质复合物内蛋白质顶点之间的最短作用距离一般

2、都比较小，绝大多数不超过2。２、扩展节点与子图Ｋ的作用概率ＩＮｖｋＩＮｖｋ＝其中，mvK是指顶点ｖ与子图K的顶点之间存在的边数，ｎＫ是指子图K的顶点数。两个直径相同，拓扑结构不相同的图，为了区分它们我们引入了作用概率的概念。（ａ）中任意一个顶点与剩下的五个节点组成的图Ｋ’的作用概率都为４／５。（ｂ）中下面的任意一个节点与剩下的五个节点组成的图Ｋ’的作用概率为１／５。３、蛋白质复合物扩充的条件：给定一个蛋白质顶点ｖ和一个蛋白质复合物Ｋ，该蛋白质顶点ｖ若属于该蛋白质复合物Ｋ必须满足如下两个条件：ＩＮｖＫＴｉｎ；

3、ＳＰ（Ｋ＋ｖ）ｄ．计算顶点的权重选择种子扩充簇ＩＰＣＡ算法１、ＩＰＣＡ算法的三个步骤计算顶点权重１）计算出网络图G中每条边的权重，边权重定义为边的两个顶点的公共邻居节点个数；２）将每个顶点连接的边的权重求和，计算出网络图G中所有顶点的权重；３）按照权重从大到小对这些顶点进行排序。将队列Ｓｑ的首个顶点，即权重最大的顶点作为种子，并将该种子作为识别的蛋白质复合物(称为“簇")的初始状态进行扩充。每扩充完一个簇，队列Ｓｑ中对应的该簇的顶点被移除。新簇的种子从剩余队列Ｓｑ中产生。队列岛为空时，整个算法结束。选择种子

4、对簇的每个邻居节点进行考虑。簇的每个邻居节点都拥有一个被扩充的优先权，由该节点与簇内顶点连接的边数以及这些边的权重之和决定，连接的边数越多，权重和越大，优先权越高。进行簇扩充时，首先考虑优先权最高的邻居节点作为候选的扩充节点。符合扩充条件的候选扩充节点才能被加入簇。一旦有一个新的候选扩充节点被加入簇，簇的邻居节点就进行更新，并重新计算其优先权。扩充簇实验一、参数Ｔｉｎ对实验结果的影响分析实验二、与ＭＩＰＳ数据库中的已知蛋白质复合物比较主要从匹配程度、敏感度、特异性、综合评价几方面考察匹配程度：ＯＳ（Ｐｃ，Ｋｃ

5、）＝敏感度：Ｓｎ＝指已知蛋白质复合物中被算法标识出来的部分所占比重特异性：Ｓｐ＝指算法识别的蛋白质复合物中识别正确的部分所占比重综合评价：ｆ－ｍｅａｓｕｒｅ＝覆盖率：Ｃｏｖ（Ｋｃ）＝当Ｔｉｎ＞０．５时，ＩＰＣＡ产生的蛋白质复合物的敏感度大于０.８，接近０．９，算法的特异性比较低，原因可能是，已知蛋白质复合物的不完整性造成的。我们也可以看出使用ＳＰ的参数要比ＡＳＰ要大一点。实验三、蛋白质网络与随机网络的比较为了进一步说明算法IPCＡ识别的蛋白质复合物很难随机得到，我们将算法IPCＡ应用于随机网络，该随机网络是原

6、酵母蛋白质网络经过随机化处理得到的，与原酵母蛋白质网络具有相同的节点度分布。算法IPCＡ从随机网络和酵母蛋白质网络中标识的已知蛋白质复合物数量的比较结果如图所示说明：从酵母蛋白质网络中识别的蛋白质复合物的大小从２到２５之间；而从随机网络中是别的蛋白质复合物大小从２到１０。为了考察随机网络中识别的小复合物是否有意义，我们把它们与已知蛋白质复合物进行了比较，结果如图６所示说明：从图中可知，当匹配阈值ＯＳ＞０．２时，酵母蛋白质网络识别的复合物超过１００个与已知蛋白质匹配；而随机网络中识别的蛋白质复合物为０。这说明随

7、机网络破坏了蛋白质相互作用中的生物本质特性。实验四、ＩＰＣＡ与其它算法的比较到目前为止，每一种实验技术或计算方法预测出来的蛋白质相互作用数据都不可避免地具有一定程度的假阳性和假阴性。所以，好的蛋白质复合物识别方法应该对蛋白质网络中存在的假阳性和假阴性具有很好的健壮性。这里我们用随机增加和移除一定比例的边来模拟蛋白质网络的假阳性和假阴性。随机增加边的比例从10％到100％，从这些具有高的假阳性的数据中进行蛋白质复合物识别，并将识别出来的结果与已知蛋白质复合物进行匹配，匹配的结果如图所示实验五、算法的健壮性图（ａ

8、）：随着假阳性的增强，算法IPCＡ能够标识出来的已知蛋白质复合物数量几乎没有下降多少，说明其具有相当高的抗噪能力；图（ｂ）：只要移除边的比例小于50％，算法IPCＡ能够标识出来的已知蛋白质复合物数量下降的很少。实验六、运行时间的分析