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

一类图的控制集问题的DNA算法研究

作　者: 涂旭东
导　师: 刘琼荪
学　校: 重庆大学
专　业: 应用数学
关键词: DNA计算 控制集 粘贴模型 表面模型 DNA编码
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 43次
引　用: 0次
阅　读: 论文下载
 

内容摘要


近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透和相互促进。随着计算机技术和分子生物技术的迅速发展,DNA计算作为一种新兴的交叉学科已经成为当今研究的热点。图论中的许多问题都是组合优化问题,也是NP完全问题。目前有关图论中许多问题,如Hamilton路、最大团、最小覆盖、图的顶点或边的着色等问题,都通过建立DNA计算模型得以有效求解和发展,同时也倍受学者们的关注和研究。本文主要针对图的一类控制(支配)集问题展开了DNA计算模型的研究。具体有以下几方面的工作:①介绍了DNA计算产生的生物背景、发展现状、DNA计算的数学理论、生物学基础以及DNA计算的机理,并对近年来有关DNA计算的研究成果进行了综述。②建立了基于图论中最小独立控制集问题的DNA表面模型,并进行了实例仿真,验证了算法的可行性和有效性。③构建了图论中的最小控制集、全控制集、独立控制集、连通控制集、完美控制集、约束控制集、双控制集、k控制集等NP完全问题的DNA粘贴模型,并证明了在DNA计算模型下,它们的算法时间复杂度是多项式阶的,并通过实例仿真对算法进行了可行性的验证。最后,本文对全文进行了全面的总结,并展望今后继续研究的方向。

全文目录


摘要  3-4
ABSTRACT  4-7
1 绪论  7-14
  1.1 DNA 计算的背景和意义  7-8
  1.2 DNA 计算的产生  8-9
  1.3 DNA 计算的原理  9-10
  1.4 DNA 计算的研究现状  10-12
  1.5 本文的主要研究内容和结构  12-14
2 DNA 计算理论简介  14-26
  2.1 引言  14
  2.2 DNA 的结构  14-17
  2.3 DNA 计算的数学机理  17
  2.4 DNA 计算的编码  17-19
    2.4.1 DNA 编码的影响因素  18-19
  2.5 DNA 计算的操作  19-23
    2.5.1 分解和连接DNA 链  19-20
    2.5.2 DNA 分子的自复制  20-21
    2.5.3 PCR 扩增  21-22
    2.5.4 DNA 序列的读取  22
    2.5.5 其它生物操作  22-23
  2.6 DNA 计算的实现途径  23-25
    2.6.1 基于溶液反应的DNA 分子计算  23
    2.6.2 基于表面的DNA 计算  23-24
    2.6.3 基于DNA 芯片的DNA 计算  24-25
  2.7 DNA 计算的研究成果  25
  2.8 本章小结  25-26
3 DNA 表面模型求解最小独立控制集问题  26-34
  3.1 引言  26
  3.2 最小独立控制集的问题描述  26-27
  3.3 归纳推理  27-28
  3.4 表面算法的生物实现  28-29
    3.4.1 D NA 编码  28-29
    3.4.2 算法的生物实现步骤  29
  3.5 算法实例与分析  29-33
  3.6 本章小结  33-34
4 一类图的控制集问题的DNA 粘贴模型及算法  34-55
  4.1 引言  34
  4.2 DNA 粘贴模型  34-36
    4.2.1 DNA 编码  34-35
    4.2.2 粘贴模型的生物操作  35-36
  4.3 最小控制集  36-37
    4.3.1 最小控制集的DNA 算法  37
  4.4 独立控制集  37-39
    4.4.1 独立控制集的DNA 算法  37-39
  4.5 连通控制集  39-41
    4.5.1 连通控制集的DNA 算法  39-41
  4.6 完美控制集  41-43
    4.6.1 完美控制集的DNA 算法  41-43
  4.7 完美控制集的扩展  43
  4.8 全控制集  43-45
    4.8.1 全控制集的DNA 算法  44-45
  4.9 约束控制集  45-47
    4.9.1 约束控制集的DNA 算法  45-47
    4.9.2 全约束控制集  47
  4.10 双控制集  47-49
    4.10.1 双控制集的DNA 算法  48-49
  4.11 k-控制集问题  49-52
    4.11.1 基于k-控制集问题DNA 算法的思想  50
    4.11.2 k-控制集问题的DNA 算法设计  50-52
  4.12 DNA 算法模拟实验  52-53
    4.12.1 DNA 编码  52
    4.12.2 算法求解过程  52-53
  4.13 本章小结  53-55
5 结论与展望  55-57
  5.1 全文总结工作  55
  5.2 未来展望  55-57
致谢  57-58
参考文献  58-61
附录  61

相似论文

  1. DNA自组装模型在组合优化问题中的应用研究,TP399-C8
  2. 基于量子计算的DNA编码方法研究,Q75
  3. 基本恒定类表面模型及操作算子的研究,P228.4
  4. 真正射影像制作中有关算法的研究,P23
  5. DNA计算机中数据结构的设计与研究,TP311.12
  6. 数字路面模型的建立及其任意轨迹特征参数的提取,TP391.41
  7. DNA计算中若干问题的研究,TP301
  8. DNA计算中若干理论的研究,TP301.6
  9. 基于0-1规划的DNA计算模型的设计与实现,TP3
  10. 遗传算法在DNA计算中的研究与应用,TP18
  11. 三维层状地质体可视化建模及分析研究,TP391.41
  12. 基于依存语法的统计机器翻译研究,TP391.2
  13. 无线网络中能量高效的拓扑控制算法研究,TN929.5
  14. 利用DNA长度编码实现分子计算,Q523
  15. 算术运算的生物计算方法,TP301.6
  16. 无线传感器网络最小集合覆盖问题的DNA算法研究,TP301.6
  17. 基于新一代GPS的形状公差规范设计方法研究,TN967.1
  18. 可扩展DNA计算模型的研究与应用,TP301.6
  19. 多级分离技术及若干问题的DNA算法研究,TP301.6
  20. 若干问题的DNA计算算法研究,TP301.6

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com