PDF《从大规模蛋白质相互作用网络中 挖掘频繁拓扑结构》

从大规模蛋白质相互作用网络中挖掘频繁拓扑结构 从大规模蛋白质相互作用网络中 挖掘频繁拓扑结构 摘要 蛋白质相互作用网络(PPI 网络)是一类重要的生物网络.

通过寻找不同物 种的 PPI 网络中所共有的保守子结构 (这种保守子结构可以通过图的拓扑结构来 定义) ,可以发现不同生物之间的同源相似性,这对于研究生物的起源、进化以 及生物功能的比较和预测等,都具有重要的现实意义. 本文对在大规模 PPI 网络上进行频繁拓扑结构挖掘的问题进行了初步的探索 和研究, 基于一般标记图集上频繁模式挖掘的相关工作提出了一个分两阶段进行 挖掘的算法框架并给出了各主要部分的详细实现, 同时结合 PPI 网络自身的特点 对算法进行了不少改进和优化.另外,通过实验对算法的性能进行了深入地测试 和评估,发现了不少有价值的规律,为算法的进一步完善提供了依据.在本文的 最后,演示了算法在 Pathway 系统上的实际运行效果,证明了算法的实用价值. 关键词:蛋白质相互作用网络,图的拓扑结构,频繁模式挖掘

1 从大规模蛋白质相互作用网络中挖掘频繁拓扑结构 Abstract Protein-Protein Interaction (PPI) network is an important class of biologic networks. By finding common conserved substructures from different species'

PPI networks, (this kind of conserved substructure can be defined as graph'

s topological minor) we can discover the homologic similarities among these spieces, which are of great significance to many biological research fields such as the origin and evolution of species, the comparison and prediction of biologic functions and etc. . In this paper, we try to solve the problem of mining frequent topological structures from large scale PPI networks as mentioned above. Based on the related research work of frequent pattern mining on general labeled graph datasets, we propose a two-stage mining algorithm framework and specify every key part'

s implementation details. Meanwhile, we introduce many improvements and optimizations into our algorithm according to the special characteristics of PPI networks. Furthermore, we do many experiments to test and evaluate the performance of our algorithm, and find some valuable information and rules. We will improve both the time and space efficiency of our algorithm in the future work with respect to these experimental results. We demonstrate the algorithm'

s practicability at the end of this paper by showing the actual running effect of the Pathway system when it uses our algorithm. Keywords:PPI networks, Graph topological minor, Frequent pattern mining

2 从大规模蛋白质相互作用网络中挖掘频繁拓扑结构 目录

第一章 绪论

5 1.1 数据挖掘领域的研究背景.5 1.2 图(结构化)数据集上的频繁模式挖掘工作.6 1.3 蛋白质相互作用网络的挖掘.7 1.3.1 蛋白质相互作用网络挖掘的现实意义.7 1.3.2 蛋白质相互作用网络的图模型.7 1.4 本文的研究对象和组织结构.10

第二章 预备知识与符号定义

11 2.1 图的一些基本概念.11 2.2 图同构与子图同构.12 2.3 图的拓扑基与拓扑结构.12 2.3.1 图的拓扑基.13 2.3.2 图的拓扑结构.14 2.4 图的拓扑基和拓扑结构概念在标记图上的推广.15

第三章 问题描述与相关工作

17 3.1 问题描述.17 3.1.1 PPI网络的建模:17 3.1.2 从PPI网络图集中寻找频繁拓扑结构:17 3.2 问题的复杂性.20 3.3 相关工作.21 3.3.1 频繁子图挖掘的相关工作.21 3.3.2 频繁拓扑结构挖掘的相关工作.23