改进的网络模体发现算法及模体功能分析

摘要

随着生物信息学研究进入后基因组时代，序列数据的模体概念拓展到了网络层面，网络模体的概念应运而生。网络模体被定义为网络中频繁且独特的子图模式，它在目标网络中出现次数远超过随机网络。网络模体作为构建网络的重要功能模块，引起众多领域的广泛关注。对于网络模体发现问题，目前研究者们已经提出了诸多算法，在识别小规模的模体时这些算法的性能较好，但随着待搜索子图规模和网络规模的增大，子图搜索和同构子图查找的计算复杂度显著提高，很多算法都无法满足科学研究的时间需求。此外，目前关于网络模体的文献大多与模体的发现算法有关，而很少涉及到对模体的功能分析。对模体进行功能分析可以让我们对网络模体的认识更加深入，使得网络模体在认识网络和分析网络的过程中发挥重要作用。所以，当务之急是积极探索更加高效的网络模体发现算法并对模体功能进行有效分析。
　　通过分析现有算法的不足，本文提出了一种改进的网络模体发现算法。算法中提出了一种新的基于局部结构特征表示输入图的方法，能够更快速准确地提取输入图的拓扑结构特征，然后通过改进的近邻传播聚类算法对提取的特征进行聚类，并通过提出的模体判定标准对聚类结果做进一步处理以发现网络模体。论文中通过设计合理的仿真实验验证了算法发现网络模体的有效性。在来自不同研究领域的8种真实网络数据分别实验，只需要数秒的运行时间，和Kavosh、FANMOD、MFinder等多种模体发现工具及算法的实验比较，显示了本文算法的高运行效率，而且算法不仅正确识别出了目前已发现的多种模体，还发现了其他结构的模体。论文最后还介绍了GO和DAVID两个常用的功能分析工具，重点讨论了用于模体分析的两种主要方法：功能注释分析和富集分析，并在大肠杆菌转录网络调控的3种模体上进行了功能分析，分析结果表明它们都显著富集在某些特定功能。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 研究目的和意义

1.4 本文主要工作及内容安排

第二章 改进的网络模体发现算法

2.1 网络模体和模体发现算法回顾

2.2 新的局部结构特征表示法

2.3 基于特征空间的聚类

2.4 改进的网络模体发现算法步骤

2.5 本章小结

第三章 算法实验分析

3.1 实验平台

3.2 仿真数据与实验

3.3 基于真实网络的实验及与其他算法的比较

3.4 本章小结

第四章 生物模体功能分析

4.1 生物信息数据库

4.2 模体功能分析方法

4.3 大肠杆菌转录网络模体功能分析

4.4 本章小结

第五章 总结与展望

5.1 总结

5.2 展望

参考文献

致谢

作者简介