聚类算法研究及其在网络模块性分析中的应用

论文摘要

随着信息化社会的发展,大多数复杂系统都可以建模成一个网络模型（图模型）,通过对该网络模型的研究,可以有利地帮助我们理解复杂系统的功能。复杂系统的一个重要特性就是“模块性”（Modularity）,这种特性表现为模块内部的节点连接比较稠密,模块间的节点连接比较稀疏。在社会网络中称之为“社团结构”（Community Structure）,生物网络中称之为“功能模块”（Functional Modules）。通过对这种特性的研究可以更好的帮助我们理解复杂系统的机能和特性,且对复杂系统的控制、预测、变化和发展都具有至关重要的意义。针对复杂网络系统的模块性,本文着重研究网络模块性分析的聚类算法及其在真实网络中的应用:（1）提出一种基于模糊聚类的网络模块性分析方法。与现有算法不同之处在于,该算法不再通过一个图模型上的遍历搜索来寻找模块,即社团结构,而是把网络建模成一个模糊关系模型,通过模糊关系的运算（模糊关系的合成）来达到识别社团结构的目的。基于社团结构与等价类的共性（自反性、对称性、传递性）,建立起两者间的一一对应关系,即把社团结构映射为满足某一等价关系的等价类。在人工网络与真实网络中的测试结果表明,该算法可以有效地识别网络中的已知社团,也可以用来识别重叠社团。（2）基于上述建立的模糊关系模型,提出一种基于最小熵聚类的网络模块性分析方法。融合网络拓扑和熵的特性,利用一种基于熵的测度来刻画节点间的关系,且熵越小,节点间越相似,社团越稳定。然后提出一种新的模糊关系的合成规则,并通过该规则来完成节点间最小熵的传递。在人工网络与真实网络中的测试结果表明,该算法可以有效地识别网络中的已知社团。（3）由于派系过滤算法（CPM）在识别蛋白质相互作用网络（Protein-Protein Interaction, PPI）中的功能模块时,没有考虑到派系对节点度的要求。针对这一点,提出一种基于派系过滤的快速迭代式聚类算法（ICPM）。该算法充分考虑到派系对节点度的要求,即k-派系里的节点的度至少为k-1,同时把识别k-派系转化为（k-1）-派系,通过递归的方式来实现从小派系到大派系的识别过程。与CPM算法相比,该算法减小了网络上识别社团的搜索空间,提高了效率。（4）针对不同物种间PPI网络功能模块的保守性,提出一种基于模块比对的方法来识别物种间的保守功能模块。与传统的网络比对方法相比,模块比对先利用聚类算法把PPI网络进行模块化分解以此来降低问题的复杂度,然后通过不同物种蛋白质间的序列相似性,建立起不同物种模块间的映射关系,从而达到识别保守模块的目的。该算法识别出来的保守模块在功能注释上具有很高的一致性,且从MCL算法分解的模块中识别出来的保守模块优于其它算法。但是,由于对网络进行了分解,破坏了整个网络结构,导致有些保守模块难以识别。（5）导致相似疾病的基因其蛋白质产物会在PPI网络中表现出很紧密的交互性,这也可近似为模块性。针对这一特性,提出一种基于聚类分析的PPI网络中疾病相关模块的预测方法。通过一种集成多个生物证据的概率化模型来刻画疾病相关模块,且得分越高与疾病的关联性越大。结果表明CPM算法分解的模块做为候选的疾病相关模块优于MCL算法与MCODE算法,同时还发现大多数疾病相关模块都由Tissue-Specific Genes组成,且只在少部分人类组织（Human Tissues）共表达（Co-Expressed）,少数疾病相关模块由House Keeping Genes （Maintenance Genes）组成,且在大部分人类组织共表达。本文研究网络模块性分析的聚类算法及其在真实网络中的应用,特别是PPI网络中功能模块的识别以及疾病相关模块的预测。此外对于其它具有相似结构的复杂网络本文所讨论的算法也具有适用性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题来源与研究意义
• 1.2 研究背景
• 1.2.1 聚类分析的进展
• 1.2.2 网络模块性分析的进展
• 1.3 本文的研究思路及主要贡献
• 1.4 本文的组织结构
• 第二章 理论背景概述
• 2.1 相关的图理论
• 2.2 复杂网络
• 2.2.1 社会网络
• 2.2.2 蛋白质相互作用网络
• 2.2.3 其它网络
• 2.3 复杂网络的模块性
• 2.4 相关工作
• 2.4.1 GN算法
• 2.4.2 Spectral算法
• 2.4.3 D-value算法
• 2.4.4 CPM算法
• 2.4.5 MCODE算法
• 2.4.6 MCL算法
• 2.4.7 RNSC算法
• 2.5 小结
• 第三章 基于模糊聚类的网络模块性分析方法研究
• 3.1 引言
• 3.2 理论基础
• 3.2.1 模糊聚类
• 3.2.2 节点间的相似性
• 3.3 模糊聚类算法
• 3.4 实验结果分析
• 3.4.1 人工网络
• 3.4.2 参数分析
• 3.4.3 各种算法性能比较
• 3.4.4 真实网络
• 3.5 小结
• 第四章 基于最小熵聚类的网络模块性分析方法研究
• 4.1 引言
• 4.2 理论基础
• 4.2.1 熵变换
• 4.2.2 最小熵传递标准
• 4.2.3 基于最小熵传递标准的聚类
• 4.3 最小熵传递方法
• 4.4 实验结果分析
• 4.5 小结
• 第五章 基于聚类分析的PPI网络模块性分析研究
• 5.1 基于派系过滤的迭代式快速模块识别算法
• 5.1.1 引言
• 5.1.2 基于派系过滤的迭代式算法
• 5.1.3 人工网络的时间效率
• 5.1.4 识别PPI网络中的功能模块
• 5.2 基于模块比对的保守模块识别算法
• 5.2.1 引言
• 5.2.2 模块比对理论
• 5.2.3 基于模块比对的识别算法
• 5.2.4 实验结果分析
• 5.3 小结
• 第六章 基于聚类分析的PPI网络疾病相关模块预测研究
• 6.1 引言
• 6.2 生物数据
• 6.3 评价指标
• 6.4 基于概率化模型的预测方法
• 6.5 实验结果分析
• 6.5.1 识别疾病相关模块
• 6.5.2 交叉验证
• 6.5.3 统计分析
• 6.5.4 分析疾病相关模块
• 6.6 小结
• 第七章 结束语
• 7.1 总结
• 7.2 展望
• 参考文献
• 攻读博士学位期间已发表的论文
• 攻读博士学位期间参加的科研项目
• 致谢