蛋白质相互作用网络分析的图聚类方法研究进展

《蛋白质相互作用网络分析的图聚类方法研究进展》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、蛋白质相互作用网络分析的图聚类方法研究进展2012.09.08CXW《计算机工程与科学》COMPUTERENGINEERING＆SCIENCE2012年第34卷第l期Vol.34，No.1，2012中南大学、佐治亚州立大学（美国）1、PPI网络的图聚类方法2、聚类分析方法评估3、图聚类方法的应用4、PPI网络聚类分析的挑战及关键问题5、未解决的问题1、PPI网络的图聚类方法1.1PPI数据及PPI网络的图模型1.2识别稠密子图的聚类方法1.3层次化的聚类方法1.4其他启发式图聚类方法1.5融合多元数据的图聚类方法1.1PPI数据及PPI网络

2、的图模型一个PPI网络可以用一个无向图G(V,E)来表示，图中的顶点表示蛋白质，边表示蛋白质之间的相互作用。也有极特殊的情况，将一个PPI网络表示为一个有向图，其中边的方向用来表示一个蛋白质对另一个蛋白质的调节。对无向图模型，根据其边取值的差异，又可以分为非加权图模型和加权图模型。非加权图模型，两个蛋白质之间的关系可以简单地用二进制值：0和1来表示。其中，1表示两个蛋白质之间存在相互作用，而0则表示这两个蛋白质问不存在相互作用。加权图模型中，边的取值位于0到1之间。边权值的大小代表了该相互作用真实存在的可能性。目前，大部分PPI网络分析的图

3、聚类算法都是基于无向图模型的，其中有些方法是基于非加权图的，有些方法是基于加权图的，还有些方法既可以用于加权图又可用于非加权图。根据识别出的cluster是否允许交叠情况又可以将聚类算法分为识别非交叠cluster的图聚类算法和识别交叠cluster的图聚类算法；根据聚类算法查找目标的不同又可以分为用于识别稠密子图的聚类算法和其他可识别不同密度子图的聚类算法等。1.2识别稠密子图的聚类方法（1）识别稠密子图的聚类方法将目标cluster看作稠密子图，并采用密度来衡量一个子图是否稠密。密度ds定义为ds=2m／(n(一1))，其中n和m分别表

4、示cluster中包含的蛋白质个数和相互作用对数。枚举PPI网络中所有的极大团超顺磁性聚类算法SPC、蒙特卡洛模拟算法MC；局部团合并算法LCMA基于团渗透的算法CPM基于极大团扩展的蛋白质复合物识别算法利用谱分析方法（2）另一大类获取稠密子图的方法：基于种子—扩充模型的聚类方法三个步骤：(1)计算种子；(2)将种子初始化为一个cluster，并进行扩充；(3)输出扩充得到的cluster，然后重复步骤(1)和(2)。最早的基于种子—扩充模型：MCODE算法缺点：不能保证得到的cluster是稠密的，因为权值大的节点彼此之间的连接不一定是

5、稠密的。DPClus算法：在挖掘非交叠蛋白质复合物的基础上，通过扩展其在原图中的邻居节点来实现交叠模块的挖掘；在密度的基础上引入了距离作为复合物识别的参数，提出了基于距离测定的蛋白质复合物识别算法IPCA；结合迭代的加权计分方法提出了应用于加权蛋白质相互作用网络聚类算法CMC；双杂交聚类算法、基于局部密度与随机游走的算法、参数化局部相似性蛋白质复合物挖掘算法miPAILM基于图密度的局部搜索算法优点：①能够识别相对稠密子图，符合蛋白质复合物和功能模块内部蛋白质趋向于密切联系的生物特性；②在扩充搜索的过程中允许某个蛋白质重复出现，能够实现同一

6、个蛋白质属于多个不同功能模块的目标；缺点：不是所有的蛋白质复合物的网络图结构都是稠密的，基于密度的局部搜索方法无法挖掘蛋白质相互作用网络中那些非稠密网络子图。1.3层次化的聚类方法层次化聚类方法通过定义任意两个蛋白质节点之间相似度或距离来量化表示两个蛋白质节点位于同一个cluster的可能性。根据树状结构形成的方式，层次化聚类方法可以进一步分为分裂法(DivisiveMethod)和凝聚法(AgglomerativeMethod)。分裂法是一种自顶向下的方法首先将整个PPI网络看做一个完整的cluster，然后不断地将该网络按照一定的规则进

7、行分割，直到所有的节点都属于不同的cluster为止。最经典的分裂法：G—N算法基本思想：不同cluster的节点之间最短路径必经过连接两个cluster的边，而这样的边具有比较高的介数。通过不断移除网络中的高介数来分裂网络。缺点：①很难确定分裂要进行到哪一步为止；②分析过程中需要重复地计算边介数，计算复杂度高。针对缺点一：用Modularity来评估网络划分质量针对缺点二：自包含的G—N算法。还有人提出应用基于图连通性的HCS(HighlyConnectedSub—graph)算法来分析蛋白质相互作用网络的模块化结构，HCS算法通过反复迭

8、代，不断地移除图中的最小割集，进而将整个网络分割成若干个独立的cluster。凝聚法是一种自底向上的层次聚类方法首先将每个蛋白质节点看做一个单独cluster，然后依据节点间的相