基于粘贴系统的DNA计算模型问题研究

论文摘要

自从Adleman博士1994年成功地给出用DNA计算方法求解有向图的Hamilton有向路问题以来,关于DNA计算与DNA计算机的研究开始飞速的发展,无论在理论研究上,还是实验方式的研究上都取得了很大的进展。DNA计算是一种以生物分子DNA作为计算介质,以生物化学反应作为计算工具的一种新型计算方法。其主要思想是:利用DNA特殊的双螺旋结构和碱基配对规律进行信息编码,把要运算的对象映射成DNA分子链,在生物酶的作用下,生成各种数据池,然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后,利用分子生物技术如聚合链式反应PCR、超声波降解、克隆、诱变、分子纯化、电泳和磁珠分离等,检测所需的运行结果。DNA计算的最大优点是充分利用海量的DNA分子中的遗传密码,以及巨量的并行性。因而以DNA计算模型为背景而产生的所谓新一代计算机,DNA计算机,必有海量的存储和极高的运行速度。本文从DNA计算所使用的DNA分子构形角度,对目前主流的计算模型:表面计算模型、质粒计算模型、粘贴计算模型和分子信标计算模型进行了介绍。粘贴系统是建立在粘贴运算基础上的语言生成器,也是一种遵循Watson-Crick互补性质进行退火操作的DNA计算抽象模型。本文利用粘贴系统的巨大并行性,首先设计了模拟有向哈密顿路问题的粘贴系统,然后通过此粘贴系统所产生语言的性质对有向哈密顿路问题进行分析,给出了有向图的若干结构性质以及图中存在有向哈密顿路的充要条件。在我们的构造中,模拟问题的粘贴系统至多运行n-1步,其中n是模拟问题的规模。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 DNA计算产生的背景
• 1.2 DNA计算的研究现状
• 1.3 DNA计算展望及存在的主要难点
• 1.4 本文的创新之处
• 第2章 DNA计算的基本介质
• 2.1 DNA分子的基本结构
• 2.2 肤核酸
• 2.3 本章小结
• 第3章 DNA分子操作
• 3.1 DNA链的分离和结合
• 3.2 DNA分子的延长
• 3.3 DNA分子的缩短
• 3.4 DNA分子的剪切
• 3.5 DNA分子的连接和粘贴
• 3.6 DNA分子长度的测量
• 3.7 特定DNA分子的获得
• 3.8 DNA分子的扩增（复制）
• 3.9 DNA序列的读取
• 3.10 其它生物操作
• 3.11 本章小结
• 第四章 DNA计算初步
• 4.1 DNA计算的实现方式
• 4.2 DNA计算的编码规则
• 4.3 从理论到现实
• 4.3.1 Adleman的实验
• 4.3.2 DNA计算解决可满足性问题
• 4.3.3 图的顶点着色问题的粘贴算法
• 4.4 本章小结
• 第5章 目前主流DNA计算模型
• 5.1 表面计算模型
• 5.1.1 表面计算基本概念
• 5.1.2 表面计算的生物操作
• 5.1.3 小结
• 5.2 质粒计算模型
• 5.2.1 质粒体计算基本概念
• 5.2.2 质粒DNA计算模型的数学描述
• 5.2.3 小结
• 5.3 粘贴计算模型
• 5.3.1 粘贴计算基本概念
• 5.3.2 粘贴模型的生物操作
• 5.3.3 小结
• 5.4 分子信标计算模型
• 5.4.1 分子信标的基本概念
• 5.4.2 分子信标的生物操作
• 5.4.3 小结
• 5.5 本章小结
• 第6章 粘贴系统
• 6.1 形式语言简介
• 6.2 有限自动机简介
• 6.3 几个基本的概念与记号
• 6.3.1 字母表与语言
• 6.3.2 语言系统中的几个最基本的运算
• 6.3.3 几种与粘贴系统相关的类型的语言
• 6.3.4 对称关系
• 6.3.5 Watson-Crick域
• 6.3.6 不完全双链分子集合
• 6.4 粘贴系统
• 6.5 本章小结
• 第7章 基于粘贴系统的有向哈密顿路问题分析
• 7.1 粘贴系统的粘贴规则
• 7.2 有关哈密顿问题描述
• 7.3 基于粘贴系统的有向哈密顿路问题分析
• 7.4 实例分析
• 7.5 本章小结
• 结论
• 参考文献
• 致谢
• 作者简介及读研期间主要科研成果