一种基于统计的生物网络模体发现算法

摘要

随着2003年人类基因组计划的完成,生物信息学的研究已经进入后基因组学时代,基因组信息学研究重心开始从揭示生命的所有遗传信息转移到从分子整体水平上对基因功能的研究,从整体水平上反应着基因功能的生物网络成为研究的重点。基因组学和蛋白质组学中的高通量方法为我们提供了大量的生物网络数据,最典型的是基因调控网络和蛋白质相互作用网络。目前生物信息学研究面临的一个主要挑战就是从这些生物网络的拓扑结构中解读出生物功能,网络模体是一种在给定网络中频繁出现的连通子图,一些网络模体已经被证明是基因调控网和蛋白质相互作用网络中的基本生物功能模块。
　　本文在分析已有生物网络模体发现算法的基础上,提出了一种基于统计模型的生物网络模体发现算法,并在统计模型的基础上建立了一个反应网络模体统计意义的得分函数,在该算法中我们首先利用一个高效的非树形子图挖掘算法ESN挖掘网络中所有规定大小的非树形子图,然后根据非树形子图和得分函数求得网络模体。对大肠杆菌、酵母基因调控网和人类的信号传导网络等真实生物网络数据的仿真实验,表明该算法与已有算法相比能够更高效地发现生物网络中的模体。

目录

摘要

Abstract

第一章 绪论

1.1 研究背景

1.2 生物网络模体发现的研究现状与动态

1.3 本文的研究工作和论文结构

第二章 图论与生物网络简介

2.1 图的相关定义

2.1.1 网络的图表示

2.1.2 图的同构与重叠

2.1.3 度与度分布

2.1.4 几种随机图模型

2.2 生物网络的图模型

2.2.1 基因调控网络

2.2.2 蛋白质相互作用网络

2.2.3 代谢网络

2.3 生物网络的计算分析

第三章 生物网络模体发现算法

3.1 基本概念和问题描述

3.2 生物网络模体发现算法的基本步骤

3.2.1 产生随机网络

3.2.2 子图挖掘

3.2.3 频率分析

3.3 几种生物网络模体发现算法

3.3.1 ESA算法

3.3.2 ESU算法

3.3.3 基于统计的生物网络模体发现算法

3.4 生物网络模体发现算法的问题及分析

第四章 一种基于统计的生物网络模体发现算法

4.1 问题定义

4.2 算法框架

4.3 子图挖掘

4.3.1 非树型子图

4.3.2 边扩张的子图挖掘

4.3.3 子图的局部比对

4.4 得分函数的构建

4.4.1 基于度分布的随机网络构建

4.4.2 得分函数的构造

4.5 退火算法

4.5.1 退火算法简介

4.5.2 退火算法在网络模体发现中的应用

4.6 实验结果及分析

第五章 总结与展望

致谢

参考文献

研究成果