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

若干问题的DNA计算算法研究

作　者: 李红
导　师: 马季兰
学　校: 太原理工大学
专　业: 计算机应用技术
关键词: DNA计算多级分离粘贴模型 0-1整数规划背包问题
分类号: TP301.6
类　型: 硕士论文
年　份: 2008年
下　载: 162次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,随着生物技术的飞速发展,一个新的研究领域——DNA计算随之产生。DNA计算是一种新的计算模式,它以DNA(deoxyribonucleicacid,脱氧核糖核酸)为“原料”,以生化实验为工具进行计算。由于DNA计算机所具有的巨大并行性、海量存储以及低能耗等优点,因此将有望在某些领域弥补现有电子计算机的不足。自1994年美国南加州大学的Adleman教授用生化实验解决了七个顶点的有向哈密尔顿路径问题(Directed Hamilton Path Problem,DHPP)以来,有关DNA计算的科研工作迅速在许多国家展开。虽然已取得了可喜的成果,但有许多经典的图论问题、数学问题等还未有DNA算法;有些问题虽有DNA计算方法,但仍有可改进之处。粘贴系统是建立在粘贴运算基础上的语言生成器,也是一种遵循Watson-Crick互补性质进行退火操作的DNA计算抽象模型。粘贴模型所使用的DNA链具有固定的长度,操作时不需要扩展DNA链,也无需酶的参与,而且它的材料在理论上可以重复使用。因此,有关粘贴模型的研究开展得比较快,许多问题的粘贴DNA算法也被相继提出。由于粘贴模型仅采用原有的四种基本操作,实验操作步骤较多,耗费了大量时间,本文求解问题时采用了多级分离装置,可以实现DNA计算中的多种基本操作,并能实现“多级分离”操作,大大减少实验步骤,成倍提高解题效率。本文介绍了基于表面的DNA计算求解0-1整数规划问题的算法,并且在此算法的基础上把未知数的取值范围扩充到从-2到+2的范围,从而扩展了此表面算法的适用范围。定义了两种约束补链,给出了求解此类整数规划问题的DNA表面计算求解算法。本文给出了一个实例的求解步骤,证明此算法的思想和可行性。本算法中采用荧光猝灭的有关技术,通过观察荧光来排除非解,具有读解、编码简单和错误率低的特点。运用此种增加变量的方法来代替未知数的取值思维方法同样可以适用未知数取+3,-3,+4,-4……等的规划问题中。本文应用多级分离技术解决了以下两个问题:(1)0-1整数规划问题。文中给出了利用多级分离装置基于溶液求解0-1整数规划问题的DNA算法。此种解法克服了表面求解方法的编码和荧光数受限的缺点,且使用了多级分离操作,大大减少实验步骤,成倍提高解题效率。(2)背包问题。本文给出了背包问题的一种新解法,即将其转化为0-1整数规划问题进行求解,在求解中利用了多级分离装置,使实验步骤减少,解题效率提高。在解决以上两个问题时,文中都给出了具体的实例,并通过模拟试验得到了具体的解决方案,说明了算法的可行性和有效性。

全文目录

摘要  3-5
ABSTRACT  5-10
第一章绪论  10-16
  1.1 DNA计算的产生背景  10-11
  1.2 DNA计算的发展及研究现状  11-14
  1.3 目前存在的问题  14
  1.4 本文的内容  14-16
第二章 DNA计算的生物基础  16-27
  2.1 DNA的分子结构  16-18
  2.2 DNA计算常用的酶  18
  2.3 DNA计算的基本思想  18-19
  2.4 DNA分子的生物操作  19-25
    2.4.1 DNA链的变性和复性  19-20
    2.4.2 合并  20
    2.4.3 特定DNA分子的提取  20
    2.4.4 PCR扩增  20-22
    2.4.5 凝胶电泳分离  22-23
    2.4.6 DNA链的外切  23
    2.4.7 DNA链的内切  23-24
    2.4.8 DNA链的连接  24-25
    2.4.9 DNA序列的检测  25
  2.5 DNA计算的实现途径  25-26
  2.6 本章小结  26-27
第三章粘贴模型及多级分离技术  27-34
  3.1 粘贴模型  27-31
    3.1.1 粘贴模型的编码方式  27-28
    3.1.2 粘贴模型的生物操作  28-29
    3.1.3 基本操作的物理实现  29-30
    3.1.4 粘贴计算  30-31
  3.2 多级分离技术  31-33
    3.2.1 多级分离的定义  31
    3.2.2 多级分离装置模型  31-32
    3.2.3 多级分离装置可实现的操作  32-33
  3.3 本章小结  33-34
第四章 DNA解法求解整数规划问题研究  34-57
  4.1 问题描述  34
  4.2 0-1整数规划问题DNA计算算法研究进展  34-41
    4.2.1 基于溶液的DNA计算模型解决0-1整数规划问题  34-38
      4.2.1.1 基本算法  34-35
      4.2.1.2 生物算法  35-38
    4.2.2 基于DNA芯片的DNA计算模型解决0-1整数规划问题  38-41
      4.2.2.1 生物算法  38-39
      4.2.2.2 基于DNA芯片求解0-1整数规划问题的DNA计算模型  39-41
  4.3 基于表面的DNA计算模型求解一类整数规划问题  41-48
    4.3.1 问题描述与转化  41-42
    4.3.2 基本算法  42
    4.3.3 相关定义(正2约束补链，负2约束补链)  42-43
    4.3.4 生物算法  43-45
    4.3.5 实例分析  45-48
  4.4 基于多级分离技术求解0-1整数规划问题的算法  48-56
    4.4.1 问题转化  49-50
    4.4.2 基于多级分离技术求解0-1整数规划问题的算法  50-51
    4.4.3 应用实例  51-56
      4.4.3.1 问题描述  51
      4.4.3.2 算法描述  51-54
      4.4.3.3 模拟实验  54-56
  4.5 本章小结  56-57
第五章基于多级分离技术求解背包问题  57-66
  5.1 问题描述  57
  5.2 背包问题的DNA算法研究进展  57-58
    5.2.1 问题描述及转化  57
    5.2.2 生物算法及步骤  57-58
  5.3 基于多级分离技术求解0-1背包问题  58-65
    5.3.1 问题描述及转化  58-59
    5.3.2 解决方案  59
    5.3.3 应用实例  59-63
    5.3.4 模拟实验  63-65
  5.4 本章小结  65-66
第六章总结  66-68
参考文献  68-72
致谢  72-73
攻读学位期间发表的学术论文  73

若干问题的DNA计算算法研究

内容摘要

全文目录

相似论文