聚类算法及研究和在网络模块性分析中应用.pdf

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