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

DNA自组装计算模型的应用研究

作　者: 宋勃升
导　师: 殷志祥
学　校: 安徽理工大学
专　业: 应用数学
关键词: DNA计算可满足性问题矩阵加法 Tile自组装
分类号: O242.1
类　型: 硕士论文
年　份: 2011年
下　载: 41次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,量子计算机、生物计算机、DNA计算等领域的创新工作引起了世人的广泛关注。其中,以DNA计算(DNA computing)为主的生物计算因具有超大规模并行计算能力和潜在的巨大数据存储能力等优势,使其成为发展非传统高性能计算的重要途径之一,备受科学界的关注。DNA计算是一种模拟生物分子结构并借助于分子生物技术进行计算的新方法,开创了以生化反应作为计算工具的先例,它是解决一类难以计算问题的一种新方法,特别是它在解决NP难问题时显示出其巨大的潜力。DNA分子自组装是DNA计算领域的一个重要研究分支,指在一定的温度,浓度,酸碱度以及特定酶的作用下,一些带有输入信息的DNA分子,根据Watson-Crick互补配对原则,自组装生成新的带有输出信息的DNA分子的过程。自组装DNA计算模型组合了DNA计算、Tiling理论和DNA纳米技术,成为目前备受关注的模型之一。本文的创新点如下：首先,将DNA Tile自组装计算模型应用于求解NP-完全问题。对一个只含3个变量的3-可满足性问题进行讨论,把它分为“非”运算子系统和“或”运算子系统。同时分别给出“非”操作和“或”操作的DNA Tile自组装计算实例。通过组合这两个操作,根据DNA Tile自组装的运算规则,对于任一给定的一组解,能自动的判断它是否满足该范式。由于DNA计算具有高度的并行性,所以对于可满足性问题的所有解能同时进行判断。其次,在实际的计算科学中,对一个可满足性问题,它的范式中的每个子句,变量的个数往往是随机的。因此,在上述思想的基础上,先列出该范式中所包含的全部变量,然后在每个子句中加入该子句所没有的变量,使之成为含有n个变量的k-可满足性问题。对于加入的变量进行特殊的标记,它们在运算的过程中不影响该范式的真值解。第三,讨论应用DNA Tile自组装计算模型求解矩阵的加法。对于矩阵的加法,主要是对两个数加法运算的延拓。先通过一个实例来说明两个数加法的运算过程,然后以一个矩阵中的所有数作为初始行,另一个矩阵中的所有数作为初始列,进行加法运算。在本文的最后部分,应用DNA的分子自组装来解决可满足性问题。其原理主要是在碱基互补配对的基础上,通过相应DNA链发夹结构的不断形成与展开,利用凝胶电泳操作将各种不同长度的DNA链分离出来,最终得到所求问题的解。

全文目录

摘要  5-7
Abstract  7-13
引言  13-15
1 DNA计算基本理论  15-26
  1.1 DNA分子结构  15-16
  1.2 DNA计算原理  16-17
  1.3 DNA计算的生物操作  17-23
    1.3.1 变性和退火DNA链  17-18
    1.3.2 DNA分子的延长和缩短  18-19
    1.3.3 DNA链的切割和粘贴  19-21
    1.3.4 聚合酶链式反应  21-22
    1.3.5 并行重叠组装技术及其他  22-23
  1.4 DNA计算研究概况  23-24
  1.5 DNA自组装的研究现状  24-25
  1.6 本文的主要研究内容  25-26
2 基于DNA Tile自组装的可满足性问题计算模型  26-42
  2.1 引言  26-27
  2.2 Tile组装结构  27
  2.3 DNA Tile自组装的基础知识  27-28
  2.4 Tile自组装模型的形式化表示  28-30
  2.5 Tile系统配置  30-32
  2.6 可满足性问题  32-41
    2.6.1 "非"运算系统  33-35
    2.6.2 "或"运算系统  35-36
    2.6.3 K个变量的K-可满足性问题的DNA Tile自组装计算模型  36-40
    2.6.4 复杂度分析  40-41
  2.7 本章小结  41-42
3 一般可满足性问题的DNA Tile自组装模型  42-50
  3.1 引言  42-43
  3.2 求解一般可满足性问题的DNA Tile自组装计算模型  43-49
    3.2.1 "恒等"系统  43-45
    3.2.2 子系统间的优化组合  45-46
    3.2.3 一般可满足性问题的DNA Tile自组装模型  46-49
    3.2.4 复杂度分析  49
  3.3 本章小结  49-50
4 矩阵加法的DNA Tile自组装计算模型  50-58
  4.1 引言  50
  4.2 矩阵加法的概念  50-51
  4.3 两个数的加法系统  51-54
    4.3.1 8个Tile加法模型  51-52
    4.3.2 L-配置加法模型  52-54
  4.4 矩阵加法模型  54-57
  4.5 本章小结  57-58
5 DNA分子自组装的可满足性问题模型  58-63
  5.1 引言  58
  5.2 可满足问题的基本算法  58-59
  5.3 算法的具体实例  59-61
  5.4 本章小结  61-63
结论  63-65
参考文献  65-70
致谢  70-71
作者简介及读研期间主要科研成果  71

DNA自组装计算模型的应用研究

内容摘要

全文目录

相似论文