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

1、蛋白质相互作用网络分析的图聚类方法研究进展,2012.09.08,CXW,计算机工程与科学 COMPUTER ENGINEERING SCIENCE 2012年第34卷第l期 Vol.34，No.1，2012 中南大学、 佐治亚州立大学（ 美国）,1、PPI网络的图聚类方法 2、聚类分析方法评估 3、图聚类方法的应用 4、PPI网络聚类分析的挑战及关键问题 5、未解决的问题,1、PPI网络的图聚类方法,1.1 PPI数据及PPI网络的图模型 1.2 识别稠密子图的聚类方法 1.3 层次化的聚类方法 1.4 其他启发式图聚类方法 1.5 融合多元数据的图聚类方法,1.1 PPI数据及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分别表示cluster中包含的蛋白质个数和相互作用对数。 枚举PPI网络中所有的极大团

4、超顺磁性聚类算法SPC、蒙特卡洛模拟算法MC；局部团合并算法LCMA 基于团渗透的算法CPM 基于极大团扩展的蛋白质复合物识别算法 利用谱分析方法,（2）另一大类获取稠密子图的方法：基于种子扩充模型的聚类方法 三个步骤： (1)计算种子； (2)将种子初始化为一个cluster，并进行扩充； (3)输出扩充得到的cluster，然后重复步骤(1)和(2)。,最早的基于种子扩充模型：MCODE算法 缺点：不能保证得到的cluster是稠密的，因为权值大的节点彼此之间的连接不一定是稠密的。 DPClus算法：在挖掘非交叠蛋白质复合物的基础上，通过扩展其在原图中的邻居节点来实现交叠模块的挖掘； 在密

5、度的基础上引入了距离作为复合物识别的参数，提出了基于距离测定的蛋白质复合物识别算法IPCA； 结合迭代的加权计分方法提出了应用于加权蛋白质相互作用网络聚类算法CMC； 双杂交聚类算法、基于局部密度与随机游走的算法、参数化局部相似性蛋白质复合物挖掘算法miPAILM,基于图密度的局部搜索算法 优点： 能够识别相对稠密子图，符合蛋白质复合物和功能模块内部蛋白质趋向于密切联系的生物特性； 在扩充搜索的过程中允许某个蛋白质重复出现，能够实现同一个蛋白质属于多个不同功能模块的目标； 缺点： 不是所有的蛋白质复合物的网络图结构都是稠密的，基于密度的局部搜索方法无法挖掘蛋白质相互作用网络中那些非稠密网络子图

6、。,1.3 层次化的聚类方法,层次化聚类方法通过定义任意两个蛋白质节点之间相似度或距离来量化表示两个蛋白质节点位于同一个cluster的可能性。 根据树状结构形成的方式，层次化聚类方法可以进一步分为分裂法(Divisive Method)和凝聚法(Agglomerative Method)。,分裂法是一种自顶向下的方法 首先将整个PPI网络看做一个完整的cluster，然后不断地将该网络按照一定的规则进行分割，直到所有的节点都属于不同的cluster为止。 最经典的分裂法：GN算法 基本思想：不同cluster的节点之间最短路径必经过连接两个cluster的边，而这样的边具有比较高的介数。通过

7、不断移除网络中的高介数来分裂网络。,缺点：很难确定分裂要进行到哪一步为止； 分析过程中需要重复地计算边介数，计算复杂度高。 针对缺点一：用Modularity来评估网络划分质量 针对缺点二：自包含的GN算法。 还有人提出应用基于图连通性的HCS(Highly Connected Subgraph)算法来分析蛋白质相互作用网络的模块化结构，HCS算法通过反复迭代，不断地移除图中的最小割集，进而将整个网络分割成若干个独立的cluster。,凝聚法是一种自底向上的层次聚类方法 首先将每个蛋白质节点看做一个单独cluster，然后依据节点间的相似度或距离循环地合并cluster，每次将两个相似度最高或

8、者距离最近的cluster进行合并，直到所有的节点属于同一个cluster为止。 代表算法：在GN算法基础上提出的MoNet算法： 利用GN算法得到边从网络中被移除的顺序，并根据这个顺序的逆序建立一个列表，以确定网络中节点合并的顺序。并给出功能模块的定义，以明确凝聚过程中的终止条件。 基于局部变量边聚集系数的快速层次聚类算法HCPIN。,层次化的聚类方法 优点：能够用于挖掘任意形状的cluster，并且能够以树状结构呈现整个PPI网络的层次化组织。 缺点： 对噪声非常敏感，而目前能够获得的蛋白质相互作用数据都不可避免地存在着噪声。 在对蛋白质相互作用网络进行分析时很难获取交叠的功能模块，即很难

9、将一个蛋白质节点划分到多个cluster中。,1.4 其他启发式图聚类方法,基于随机流的快速聚类算法MCL 一种基于代价函数的图划分算法RNSC，通过使用代价函数来探索最优的网络划分。 过程：随机地将蛋白质网络划分成 k 个独立cluster，通过不断地将一个cluster内的蛋白质节点移至另一个cluster来降低整体成本，当这种移动次数超过事先设定的阈值而没有使整体成本下降时，整个算法结束。 缺点：算法的结果质量与算法开始生成的k个cluster的质量密切相关。,结构化聚类算法SCAN ： 基本思想：两个顶点是否应该出现在同一个cluster中取决于它们共享的邻居节点，SCAN是一个基于共

10、邻居节点的方法 贡献点：不仅能够从蛋白质相互作用网络中获取有效的聚类结果，而且能够识别hubs以及outliers 其他方法： 用谱划分和贪婪优化质量评估参数Q来划分cluster 功能模块识别算法STM,1.5 融合多元数据的图聚类方法,目的：为了减少或者降低数据本身带来的影响，提高聚类算法的鲁棒性。,2、聚类分析方法评估,2.1 基于标准数据集的分析 2.2 功能富集分析 2.3 其他评估方法分析,2.1 基于标准数据集的分析,将算法预测出的cluster与已知的标准数据集进行匹配最直接、最有效的方法 常用的标准数据集： MIPS中的已知蛋白质复合物数据 Nature和Science公开发

11、表的实验方法或者系统分析方法得到的蛋白质复合物 GO数据库中的功能注释信息等,算法识别出的cluster(记作Pc)与已知蛋白质复合物(记作Kc)的匹配程度OS(Pc,Kc）:,3、图聚类方法的应用,3.1 预测蛋白质功能 3.2 PPI预测及假阳性过滤 3.3 预测关键蛋白质,4、PPI网络聚类分析的挑战及关键问题,4.1 PPI网络数据的预处理 4.2 面向动态PPI网络的图模型和聚类算法 4.3 聚类结果的评估,5、未解决的问题,PPI网络数据的可靠性问题； PPI网络的层次化结构与模块化结构之间的关系； PPI网络分析过程中如何实现交叠cluster的识别，cluster之间的交叠机制是怎样的? 随着PPI数据的不断增加，如何面向大规模PPI数据集设计快速而有效的聚类方法? 如何构建动态的PPI网络模型，体现真实蛋白质相互作用自身的动态特性，并基于此进一步研究面向动态PP