复杂生物网络中的稠密子图挖掘算法研究

论文摘要

复杂生物网络中的频繁模式在揭示生物体的功能、进化以及疾病等方面有着重要的意义。由于生物网络的规模较大,传统的网络聚类算法有着很高的时间复杂度,如何快速从大规模生物网络中探测稠密子图成为亟待解决的一个难题。直觉上,在一个稠密子图中,其中的任意一条边都与其近邻边之间紧密相连。本文提出了一种新的测度——边稠密度系数,它能够较好的识别一条边是否位于一个稠密子图。结果表明:这一测度与边的中介性具有较好的反相关性。由于边稠密度系数的计算非常简单,利用它进行单个网络中的稠密子图的挖掘,可以明显降低计算的复杂度。在此基础上,我们研究了网络集中的频繁稠密点集的挖掘问题,基本的思想是将该问题分为二个子问题:候选网络子集的确定与每个网络子集中的频繁稠密点集的识别。算法的主要思想是:通过迭代过程逐步求精摘要图。仿真实验结果表明:该算法具有简单、时间复杂度低和一定的鲁棒性等优点。最后,本文集成了有关酵母的基因表达谱数据,建立了20个共表达网络,每个网络包含5672个基因;并将我们的算法应用到此真实生物数据的挖掘,利用GOEAST工具对计算结果进行了GO分析,结果显示该算法找到的频繁稠密点集所包含的基因在若干生物组件、功能或过程中显著富集,这些基因之间相互联系紧密。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 复杂网络简介
• 1.2 生物网络简介
• 1.3 复杂网络聚类算法综述
• 1.3.1 基于凝聚思想的算法
• 1.3.2 基于分解思想的算法
• 1.4 本文的组织结构
• 第二章 图论及相关知识介绍
• 2.1 图论的相关基本概念
• 2.2 度与度分布
• 2.3 图中常见的几种测度
• 2.3.1 割、最小割和规范割
• 2.3.2 点中介性和边中介性
• 2.3.3 聚类系数
• 2.3.4 边聚类系数
• 2.3.5 模块性
• 2.4 小结
• 第三章 稠密子图挖掘研究
• 3.1 边稠密度系数
• 3.2 三种测度之间的相关性
• 3.3 三种测度的聚类效果比较
• 3.4 小结
• 第四章 频繁稠密点集挖掘研究
• 4.1 问题描述与现有算法
• 4.1.1 引出问题
• 4.1.2 CODENSE 算法
• 4.1.3 NeMo 算法
• 4.1.4 CODENSE 和NeMo 的优缺点
• 4.2 基于边稠密度系数的挖掘算法
• 4.2.1 聚类中心
• 4.2.2 频繁稠密点集
• 4.3 实验结果
• 4.3.1 实验数据
• 4.3.2 参数m、p 的调节
• 4.3.3 测试结果
• 4.4 相似聚类中心对频繁稠密点集的影响
• 4.5 小结
• 第五章 酵母基因表达数据集的测试与分析
• 5.1 生物数据处理与建模
• 5.2 关于GO
• 5.2.1 GO 简介
• 5.2.2 GOEAST 简介
• 5.3 实验结果与GO 分析
• 5.3.1 实验步骤
• 5.3.2 GO 分析
• 5.3.3 基因功能预测
• 第六章 总结与展望
• 6.1 本文总结
• 6.2 后续研究展望
• 参考文献
• 附录A
• 致谢
• 攻读硕士学位期间取得的研究成果