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

第四章 算法设计与实现

25 4.1 算法的一些关键步骤及其实现.25 4.1.1 拓扑结构的表示方式.26 4.1.2 出现记录表的建立.28 4.1.3 模式增长的具体过程.32 4.1.4 重复模式的发现.36 4.1.5 其他涉及的重要函数.38 4.2 算法的详细框架.41 4.3 根据PPI网络的特点对算法进行改进.43 4.3.1 树模式挖掘阶段的规范标记.44 4.3.2 图模式挖掘阶段的规范标记.51 4.4 实际算法的时间代价分析.52 4.4.1 树模式挖掘阶段的时间代价.53 4.4.2 图模式挖掘阶段的时间代价.53

第五章 实验结果与分析

54 5.1 实验数据说明.54 5.2 实验结果描述与分析.56

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

第六章 算法在Pathway系统中的实际应用

64 6.1 Pathway系统简介.64 6.2 Pathway系统的设计与实现.64 6.2.1 系统的整体架构.65 6.2.2 数据预处理模块.65 6.2.3 挖掘算法模块.66 6.2.4 图形化表示模块.66 6.3 算法在Pathway系统上的实际应用效果.67

第七章 总结与展望

69 参考文献

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

第一章 绪论 蛋白质相互作用网络(Protein-Protein Interaction Network)是一类重要的生 物网络.生物学研究表明,不同物种的蛋白质相互作用网络之间所共有的保守子 结构(即拓扑结构,后文将详细介绍和定义)可能反映了不同生物之间的某种同 源相似性,因而寻找这些公共子结构对于研究生物的起源与进化,以及生物功能 的比较与预测等,都有着特别重要的意义.然而,实际的蛋白质相互作用网络往 往规模巨大, 因此单纯依靠人工方法来进行网络间的比对进而发现保守子结构是 不现实的,必须借助于计算机这一工具.而在计算机科学领域,数据挖掘技术尤 其是图挖掘技术的发展使得寻找有效的计算机算法来解决上述问题成为了可能. 在这一章里,我们先简要地介绍一下数据挖掘领域特别是图挖掘领域的研究 背景,然后我们将对蛋白质相互作用网络的挖掘问题进行一个概念上的描述(问 题的精确定义将在 3.1 节给出) ,最后我们将对本文的研究对象和组织结构进行 一个说明. 1.1 数据挖掘领域的研究背景 数据挖掘(Data Mining)是从大量的、不完全的、有噪声的、模糊的、随机 的数据中提取隐含在其中的、事先不为人所知的、但又是潜在有用的信息和知识 的过程. 对数据挖掘技术的研究兴起于上世纪

80 年代后期.当时,关系数据库模型 已经确立,数据库技术经过数十年的发展已经逐渐趋于成熟,越来越多的企业和 组织已经习惯于采用数据库来存储和查询信息.另一方面,互联网(Internet) 开始进入一个飞速发展的阶段, 人们开始习惯于通过互联网来实现信息的传递和 资源的共享. 数据库和互联网技术飞速发展的一个直接结果就是信息量的迅猛膨 胀.但是,对于某一个个体而言,他并不一定能从增加的信息量中获益,理由是 随着信息量的增加,如何从中提取对自己有价值的信息(或者说是知识)将变得 更为困难.数据挖掘研究就是在这样的背景下产生和发展起来的. 数据挖掘所要处理的数据对象是多种多样的:根据信息存储格式,用于挖掘 的对象有关系数据库、 面向对象数据库、 数据仓库、 文本数据源、 多媒体数据库、 空间数据库、时态数据库、异质数据库以及 Internet 等.即使是同样的数据对象, 也存在着诸如规模,完整性,可靠性等差异. 数据挖掘的任务主要有:模式挖掘、关联分析、聚类分析、分类、预测、时5从大规模蛋白质相互作用网络中挖掘频繁拓扑结构 序模式和偏差分析等. 目前,数据挖掘的许多子领域已经进行了比较深入的研究,得到了许多经典 的算法和结果.但是,随着信息技术的高速发展,数据量的急剧增长,出现了许 多新的需求,一些原有的结论和方法在这些新的需求上会变得不太适用.特别是 一些新的复杂的数据对象和挖掘任务的出现,迫切需要新的方法来进行处理. 1.2 图(结构化)数据集上的频繁模式挖掘工作 首先简单地介绍一下频繁模式挖掘的概念.频繁模式挖掘是指对给定的数据 集, 找出其中出现频率 (或相应的频次) 高于某个给定的支出度阈值的那些模式, 而具体模式的形式则是多种多样的. (比如说对于一个给定的文本数据集,我们 可以要求寻找出所有出现频率超过 10%的单词,这里的单词就可以视为一个模 式. )这些挖掘出来的频繁模式往往包含着有意义的信息, (比如上面的例子中抽 取出的单词可能就包含着关于该文本数据集内容的重要信息)更多的情况下,这 些模式常常可以作为后续挖掘工作的坚实基础 (比如关联分析的第一步就是频繁 模式挖掘) ,因此,进行频繁模式挖掘的研究是具有现实意义的. 近年来,在数据挖掘领域,越来越多的研究者将自己的研究兴趣投入到结构 化数据集上的频繁模式挖掘工作中来.结构化数据集的例子有:化学合成物,生 物蛋白质,社会关系网络,XML 数据集等等.由于这些数据通常都可以用图来 建模,所以目前主要的研究集中在频繁子图的挖掘算法上. (关于子图的概念将 在2.1 节介绍) 然而,在现实世界的不少应用中,比如生物网络(包括我们下面将要介绍的 蛋白质相互作用网络) ,社会关系网络,远程通讯网络等,挖掘出图的频繁拓扑 结构(定义将在 2.3 节给出)往往比普通的频繁子图更有价值.比如,在分析社 会关系网络或远程通讯网络时, 许多时候我们并不关心直接相邻的两个顶点之间 的联系,而是更关注这样的模式:几个顶点通过相互独立的路径进行相互联系. 但是,想直接通过现有的频繁子图挖掘算法来得到这样的模式是相当困难的,这 就需要寻找新的途径.我们将在 3.3 节详细介绍在图数据集上进行频繁模式挖掘 方面的相关研究工作.