生物学网络中完全子网的抽取及网络间关系映射

摘要

随着各种实验手段和技术的发展，我们可以获得大量的分子生物学网络。这些网络中的拓扑结构对于我们研究分子结构、功能团和进化保守性有着重要的指导意义；而完全子网是我们研究网络拓扑中最重要的结构之一，它最有可能揭示我们所感兴趣的问题。虽然通过图论知识，我们知道寻找最大完全子网问题是NP-完全问题，但是，我们根据生物学网络的无尺度特点，并且利用了动态规划算法的思想，采用了两个有针对性的算法，从而可以快速的抽取出网络中的全部完全子网；之后完成这些子网间的匹配关系并建立了映射关系。我们针对DIP(Database of Interacting Proteins)数据库中提供的啤酒酵母(Saccharomyces cerevisiae)蛋白质互作分子生物学网络(2007/4/1版本)，抽取出了全部的完全子网，其中最大规模的完全子网含有10个蛋白质节点。根据映射关系，我们预测了8个新的重要互作关系，并在BioGrid数据集(2007/6/1版本)和其它文献中得到了证实，从而将最大完全子网规模扩大到14个节点，同时完善了DIP数据集(2007/6/3版本数据集仍然不包含我们预测的互作关系)。我们得到的完全子网，可以通过KEGG(Kyoto Encyclopedia of Genes and Genomes)来进行功能等方面的进一步分析研究和结果解释。对于同一物种的两个生物学网络，抽取出来的完全子网，可以发现网络特征、蛋白复合物或预测基因功能等；对于不同物种的两个生物学网络，匹配和映射后的完全子网，可以从系统进化的层面上，研究某些结构是否具有保守性，这对完全子网来讲是一个很好的特性。所以，本文论述的方法应用前景十分广阔。

目录

摘要

Abstract

第1章 绪论

1.1 课题背景

1.2 国内外在该方向的发展现状及分析

1.3 本课题的任务及论文的主要工作

1.3.1 本课题的任务

1.3.2 本课题的主要工作

第2章 完全子网抽取、匹配和映射的总体分析

2.1 问题的总体描述

2.2 数据模型

2.2.1 生物学网络的表示

2.2.2 生物学网络信息的挖掘

2.3 总体分析流程

2.3.1 完全子网抽取的分析流程

2.3.2 完全子网完全匹配的分析流程

2.3.3 完全子网间的映射的分析流程

2.4 本章小结

第3章 完全子网抽取、匹配和映射的方法

3.1 生物学网络中完全子网的抽取

3.1.1 总体流程图

3.1.2 生成最小完全子网的快速算法

3.1.3 递推生成K阶完全子图的算法

3.1.4 删除等价的K阶完全子图

3.2 完全匹配两个生物网络中的K阶完全子图

3.3 映射两个生物网络中的K阶完全子图

3.4 团和核的区分

3.5 算法分析

3.6 本章小结

第4章 方法的具体实现过程

4.1 实现方法的概要设计

4.2 实现方法的总体设计

4.2.1 数据预处理

4.2.2 抽取完全子网

4.3 完全匹配完全子网

4.4 建立完全子网间的映射

4.5 具体实现程序说明

4.5.1 Oracle类包

4.5.2 Data类包

4.5.3 manage类包

4.5.4 Method类包

4.6 计算结论

4.7 本章小结

第5章 完全子网抽取、匹配和映射的实验结果

5.1 所使用的两个生物网络

5.1.1 生物学网络的来源

5.1.2 生物学网络介绍

5.2 生物学网络的规范化和标准化

5.3 生物学网络的计算

5.4 在KEGG中的结果验证和解释

5.5 结果分析和讨论

5.6 本章小结

结论

参考文献

攻读学位期间发表的学术论文

致谢