学位论文 > 优秀研究生学位论文题录展示

频繁子图挖掘算法及其在生物网络中的应用

作　者: 董安国
导　师: 巨永锋
学　校: 长安大学
专　业: 交通信息工程及控制
关键词: 数据挖掘 频繁子图 同构 模体 算法 Hamilton子图
分类号: TP311.13
类　型: 硕士论文
年　份: 2009年
下　载: 140次
引　用: 0次
阅　读: 论文下载
 

内容摘要


人类基因组计划的基本完成表明后基因组时代的到来。人类积累的大量的生物信息数据为揭开生命奥秘提供了数据基础,生物学研究的热点由对细胞内个别基因或蛋白质功能的局部性研究,转移到以细胞内全部的基因、蛋白质及代谢产物为整体对象的系统研究。对基因调控网络、蛋白质相互作用网络、代谢路径网络等结构及功能模块的检测技术的研究,逐步把分子生物学推入系统生物学时代。基因与蛋白质通过网状的相互作用产生更高一级的功能模块,所以,通过数学建模来设计有效的算法,在生物网络中进行功能模块的挖掘和分析,将有助于更好地研究生物体自身的功能和不同生物体之间的进化关系,为分析理解生命基本规律提供依据。本文对基于图论的经典频繁子图挖掘算法进行了系统的研究和全面的总结,在此基础上提出了一种新的挖掘频繁子图的算法,该算法包含子图的搜索算法及同构分类算法。对子图搜索问题,提出了环分布的概念,并构造了基于环分布的子图搜索算法ESR(EnumerateSubgraphs based on Ring);对子图同构问题,利用度序列和特征值构造了两种算法,分别用于对有向图和无向图的同构判别;利用同构算法对搜索出的子图进行同构分类,根据分类结果得到频繁子图。当网络规模比较大时,子图数量非常庞大,同构分类的工作量很大,为此又提出了随机归类算法和Hamilton子图的挖掘算法,以减少同构分类的运算量。随机归类算法是通过从子图集中随机地抽取一定数量的子图进行同构分类,是一种近似的算法;Hamilton子图的挖掘算法旨在挖掘特定类型(具有Hamilton回路)的子图,以减少搜索结果集。最后对5个真实生物网络进行了仿真实验研究,找出了不同规模的频繁子图,实验结果表明本文提出的算法优于现有的算法。

全文目录


摘要  4-5
Abstract  5-8
第一章 绪论  8-13
  1.1 研究背景  8-9
  1.2 研究现状  9-10
  1.3 研究的意义和目的  10-12
    1.3.1 研究的意义  10-11
    1.3.2 研究的目标  11-12
  1.4 研究内容  12-13
第二章 生物网络的图论模型  13-19
  2.1 生物网络  13-14
    2.1.1 基因调控网络  13
    2.1.2 蛋白质相互作用网络  13-14
    2.1.3 代谢路径网络  14
  2.2 图及相关概念  14-16
    2.2.1 图、子图、路径  15
    2.2.2 图的同构  15-16
    2.2.3 频繁子图  16
  2.3 随机网络  16-18
    2.3.1 复杂网络  16-17
    2.3.2 复杂网络研究的简史  17
    2.3.3 复杂网络的重要的统计性质  17
    2.3.4 随机网络模型  17-18
  2.4 生物网络的图论描述  18
    2.4.1 模块  18
    2.4.2 模体  18
  2.5 总结  18-19
第三章 频繁子图挖掘算法  19-36
  3.1 图模式挖掘算法的类型  19
  3.2 基于Apriori思想的频繁子图挖掘  19-21
  3.3 基于FP-Growth思想的频繁子图挖掘  21-26
    3.3.1 gSpan算法  21-22
    3.3.2 CloseGraph算法  22-23
    3.3.3 FFSM算法  23-26
  3.4 基于节点环分布的子图挖掘算法  26-30
    3.4.1 相关定义及环分布类型的确定  26-27
    3.4.2 基于环分布的子图搜索算法  27-30
  3.5 图同构算法  30-34
    3.5.1 定义及同构理论  30-31
    3.5.2 图的同构算法  31-34
  3.6 子图频率及频繁子图  34-35
    3.6.1 精确算法  34
    3.6.2 基于随机抽样的近似算法  34-35
  3.7 本章小结  35-36
第四章 Hamilton子图的有效挖掘算法  36-42
  4.1 定义和符号  36-37
  4.2 k-路径连接矩阵的计算及k-路径的确定  37-39
  4.3 搜索算法  39-40
    4.3.1 4个节点的Hamilton子图的搜索算法  39
    4.3.2 6个节点Hamilton子图的搜索  39-40
  4.4 有向图的拟Hamilton子图的搜索  40-41
  4.5 计算复杂度分析  41-42
    4.5.1 4节点情形  41
    4.5.2 6节点情形  41-42
第五章 仿真试验研究  42-47
  5.1 子图搜索速度比较  42-43
  5.2 子图同构分类  43
  5.3 频繁子图的搜索  43-45
  5.4 Hamilton子图搜索实验  45-47
第六章 总结与展望  47-49
参考文献  49-51
研究成果  51-53
致谢  53

相似论文

  1. 基于差分进化算法的JSP环境下成套订单研究,F273
  2. 基于图的标志SNP位点选择算法研究,Q78
  3. 高灵敏度GNSS软件接收机的同步技术研究与实现,P228.4
  4. 天然气脱酸性气体过程中物性研究及数据处理,TE644
  5. 基于Thermo-Calc三元共晶合金凝固路径的耦合计算,TG111.4
  6. 压气机优化平台建立与跨音速压气机气动优化设计,TH45
  7. 多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
  8. 基于感性负载的车身网络控制系统,U463.6
  9. 基于蚁群算法的电梯群优化控制研究,TU857
  10. 高精度激光跟踪装置闭环控制若干关键问题研究,TN249
  11. 半导体激光器热电控制技术研究,TN248.4
  12. AES算法及其DSP实现,TN918.1
  13. 基于UWB脉冲信号的测距定位技术,TN929.5
  14. 基于TS101的DFT输出子集算法研究及软件实现,TN911.72
  15. 高光谱图像空—谱协同超分辨处理研究,TN911.73
  16. DBF接收机用于二维测向算法的研究,TN851
  17. 电视制导系统中视频图像压缩优化设计及实现研究,TN919.81
  18. IEEE802.16e信道编译码算法研究,TN911.22
  19. LDPC码译码算法的研究,TN911.22
  20. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  21. 基于人眼检测的驾驶员疲劳状态识别技术,TP391.41

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com