• 基于图密度的局部搜索算法 • 优点：
• ①能够识别相对稠密子图，符合蛋白质复合物和功能模块内部蛋白质 趋向于密切联系的生物特性； • ②在扩充搜索的过程中允许某个蛋白质重复出现，能够实现同一个蛋 白质属于多个不同功能模块的目标；
• 缺点：
• 不是所有的蛋白质复合物的网络图结构都是稠密的，基于密度的局部 搜索方法无法挖掘蛋白质相互作用网络中那些非稠密网络子图。
• 层次化的聚类方法 优点：能够用于挖掘任意形状的cluster，并且能够以树状 结构呈现整个PPI网络的层次化组织。 缺点： ①对噪声非常敏感，而目前能够获得的蛋白质相互作用数 据都不可避免地存在着噪声。 ②在对蛋白质相互作用网络进行分析时很难获取交叠的功 能模块，即很难将一个蛋白质节点划分到多个cluster中。
1.3 层次化的聚类方法
• 层次化聚类方法通过定义任意两个蛋白质节点之间相似度 或距离来量化表示两个蛋白质节点位于同一个cluster的可 能性。
• 根据树状结构形成的方式，层次化聚类方法可以进一步分 为分裂法(Divisive Method)和凝聚法(Agglomerative Method)。
• 如何构建动态的PPI网络模型，体现真实蛋白质相互作用自身的 动态特性，并基于此进一步研究面向动态PPI网络的构建可靠的PPI网络。多元是指与蛋白质相关的不同 类型的信息，例如基因表达数据、蛋白质结构域信息、蛋 白质功能注释信息、亚细胞定位信息等等.
• 结构化聚类算法SCAN ： 基本思想：两个顶点是否应该出现在同一个cluster中取决于它们共享的 邻居节点，SCAN是一个基于共邻居节点的方法 贡献点：不仅能够从蛋白质相互作用网络中获取有效的聚类结果，而 且能够识别hubs以及outliers 其他方法： • 用谱划分和贪婪优化质量评估参数Q来划分cluster • 功能模块识别算法STM
1.2 识别稠密子图的聚类方法
（1）识别稠密子图的聚类方法将目标cluster看作稠密子图， 并采用密度来衡量一个子图是否稠密。 密度 ds定义为 ds=2m／(n( 一1))，
其中n和m分别表示cluster中包含的蛋白质个数和相互作用对数。
• 枚举PPI网络中所有的极大团 超顺磁性聚类算法SPC、蒙特卡洛模拟 算法MC；局部团合并算法LCMA • 基于团渗透的算法CPM • 基于极大团扩展的蛋白质复合物识别算法 • 利用谱分析方法
1.4 其他启发式图聚类方法
• 基于随机流的快速聚类算法MCL • 一种基于代价函数的图划分算法RNSC，通过使用代价函数来探 索最优的网络划分。 过程：随机地将蛋白质网络划分成 k 个独立cluster，通过不断地 将一个cluster内的蛋白质节点移至另一个cluster来降低整体成本， 当这种移动次数超过事先设定的阈值而没有使整体成本下降时， 整个算法结束。 缺点：算法的结果质量与算法开始生成的k个cluster的质量密切 相关。
• 缺点：①很难确定分裂要进行到哪一步为止； ②分析过程中需要重复地计算边介数，计算复杂度高。 • 针对缺点一：用Modularity来评估网络划分质量 • 针对缺点二：自包含的G—N算法。 • 还有人提出应用基于图连通性的HCS(Highly Connected Sub— graph)算法来分析蛋白质相互作用网络的模块化结构，HCS算法 通过反复迭代，不断地移除图中的最小割集，进而将整个网络 分割成若干个独立的cluster。
• 3、图聚类方法的应用
• 4、PPI网络聚类分析的挑战及关键问题 • 5、未解决的问题
1、PPI网络的图聚类方法
1.1 PPI数据及PPI网络的图模型 1.2 识别稠密子图的聚类方法 1.3 层次化的聚类方法 1.4 其他启发式图聚类方法 1.5 融合多元数据的图聚类方法
1.1 PPI数据及PPI网络的图模型
• DPClus算法：在挖掘非交叠蛋白质复合物的基础上，通过 扩展其在原图中的邻居节点来实现交叠模块的挖掘； • 在密度的基础上引入了距离作为复合物识别的参数，提出 了基于距离测定的蛋白质复合物识别算法IPCA； • 结合迭代的加权计分方法提出了应用于加权蛋白质相互作 用网络聚类算法CMC； • 双杂交聚类算法、基于局部密度与随机游走的算法、参数 化局部相似性蛋白质复合物挖掘算法miPAILM
1.5 融合多元数据的图聚类方法
• 目的：为了减少或者降低数据本身带来的影响，提高聚类算法的鲁棒 性。
2、聚类分析方法评估
2.1 基于标准数据集的分析 2.2 功能富集分析 2.3 其他评估方法分析
2.1 基于标准数据集的分析
• 将算法预测出的cluster与已知的标准数据集进行匹配—— 最直接、最有效的方法
• 如何通过对这些多元信息的复杂关联关系的分析，进而构 建它们之间的关联模型，并用于构建可靠的PPI网络.
• 结合特定疾病进行基于网络水平的诊断分析。
• 目前，大部分PPI网络分析的图聚类算法都是基于无向图 模型的，其中有些方法是基于非加权图的，有些方法是基 于加权图的，还有些方法既可以用于加权图又可用于非加 权图。 • • 根据识别出的cluster是否允许交叠情况又可以将聚类算法 分为识别非交叠cluster的图聚类算法和识别交叠cluster的 图聚类算法； • • 根据聚类算法查找目标的不同又可以分为用于识别稠密子 图的聚类算法和其他可识别不同密度子图的聚类算法等。
• 凝聚法是一种自底向上的层次聚类方法
• 首先将每个蛋白质节点看做一个单独cluster，然后依据节点间的相似 度或距离循环地合并cluster，每次将两个相似度最高或者距离最近的 cluster进行合并，直到所有的节点属于同一个cluster为止。 • 代表算法：在G—N算法基础上提出的MoNet算法： • 利用G—N算法得到边从网络中被移除的顺序，并根据这个顺序的逆序 建立一个列表，以确定网络中节点合并的顺序。并给出功能模块的定 义，以明确凝聚过程中的终止条件。 • 基于局部变量边聚集系数的快速层次聚类算法HC—PIN。
• 常用的标准数据集： • MIPS中的已知蛋白质复合物数据 • Nature和Science公开发表的实验方法或者系统分析方法得 到的蛋白质复合物 • GO数据库中的功能注释信息等
• 算法识别出的cluster(记作Pc)与已知蛋白质复合物(记作Kc) 的匹配程度OS(Pc,Kc）:
3、图聚类方法的应用
• 一个PPI网络可以用一个无向图G( V,E)来表示，图中的顶点表示蛋白质， 边表示蛋白质之间的相互作用。也有极特殊的情况，将一个PPI网络表 示为一个有向图，其中边的方向用来表示一个蛋白质对另一个蛋白质 的调节。
• 对无向图模型，根据其边取值的差异，又可以分为非加权图模型和加 权图模型。 • 非加权图模型，两个蛋白质之间的关系可以简单地用二进制值：0和1 来表示。其中，1表示两个蛋白质之间存在相互作用，而0则表示这两 个蛋白质问不存在相互作用。 • 加权图模型中，边的取值位于0到1之间。边权值的大小代表了该相互 作用真实存在的可能性。
• 分裂法是一种自顶向下的方法
• 首先将整个PPI网络看做一个完整的cluster，然后不断地将该网络按照 一定的规则进行分割，直到所有的节点都属于不同的cluster为止。 • 最经典的分裂法：G—N算法 • 基本思想：不同cluster的节点之间最短路径必经过连接两个cluster的 边，而这样的边具有比较高的介数。通过不断移除网络中的高介数来 分裂网络。
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数据集设计快速而 有效的聚类方法?
蛋白质相互作用网络分析的 图聚类方法研究进展
CXW
2012.09.08
• 《计算机工程与科学》 COMPUTER ENGINEERING ＆SCIENCE • 2012年第34卷第l期 Vol.34，No.1，2012 • 中南大学、 佐治亚州立大学（ 美国）
• 1、PPI网络的图聚类方法
• 2、聚类分析方法评估
（2）另一大类获取稠密子图的方法：基于种子—扩充模型 的聚类方法 • 三个步骤： (1)计算种子； (2)将种子初始化为一个cluster，并进行扩充； (3)输出扩充得到的cluster，然后重复步骤(1)和(2)。
最早的基于种子—扩充模型：MCODE算法 • 缺点：不能保证得到的cluster是稠密的，因为权值大的节 点彼此之间的连接不一定是稠密的。