用DNA分子自动机模拟有穷自动机

论文摘要

DNA计算属于生物化学,数学以及计算机等学科的一个交叉领域,其研究的内容涉及到数学,医学,计算机等各个领域。自从Adleman教授开创了这一新的领域以来,DNA计算的一些思想和方法被广泛的应用于解决一些图论,网络,优化等问题。由于DNA计算具有高度的并行性,因此,研究者也把目光投向了用DNA分子自动机来模拟电子计算机。DNA分子自动机模拟电子计算机是DNA计算领域内一个重要的内容。研究者已经提出了用DNA分子自动机来模拟图灵机的一步转移规则,有穷自动机的转移规则以及下推自动机的转移规则。DNA分子自动机模拟电子计算机是一个内容相当丰富的课题,目前所取得的成就与之相比还存在很大的差距。基于这一现状,我们将继续探讨用分子自动机模拟电子计算机的思想,方法和意义。在DNA分子自动机中,酶是分子自动机的硬件,输入分子和转移分子是分子自动机的软件,同时还编码了检测分子。设计一个DNA分子自动机的关键在于选择合适的软件分子。我们对现有的用DNA分子自动机模拟电子计算机的思想和方法进行分析和研究,在此基础上提出了一些用DNA分子自动机模拟有穷自动机的新的方法。其中设计环形分子链来模拟有穷自动机的转移规则是我们研究的核心部分。虽然用DNA分子自动机模拟有穷自动机在实验条件下的实现还受到一定的限制,但这种思想将对DNA计算领域的发展产生重大的影响。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 前言
• 1.2 DNA 的结构
• 1.3 DNA 计算
• 1.3.1 DNA 计算的特点
• 1.3.2 目前DNA 计算的发展状况
• 1.3.3 常用的生物操作技术
• 1.4 DNA 计算的应用
• 1.5 研究内容及研究意义
• 1.6 本章小结
• 第2章 现有的有穷自动机及其分析
• 2.1 最简单的NFA 的应用
• 2.1.1 实例
• 2.1.2 将NFA 中的一个接受状态推广到多个接受状态
• 2.1.3 结构特点
• 2.1.4 功能分析
• 2.2 Whiplash PCR 方法
• 2.2.1 WPCR 的过程
• 2.2.2 结构特点
• 2.3 两个状态的分子自动机
• 2.3.1 Shapiro 用DNA 模拟DFA
• 2.3.2 Benenson 的两个状态的分子自动机
• 2.3.3 结构分析
• 2.3.4 功能分析
• 2.4 J.A.Rose 用分子自动机来模拟有穷状态自动机
• 2.4.1 实例
• 2.4.2 结构分析
• 2.4.3 功能分析
• 2.5 本章小结
• 第3章 DNA 计算模拟DFA（NFA）的新方法
• 3.1 对J.A.Rose 模型的推广
• 3.1.1 设计的思想与方法
• 3.1.2 实例
• 3.1.3 结构特点及功能分析
• 3.2 能读出转移路径的设计模型
• 3.2.1 设计的思想与方法
• 3.2.2 实例
• 3.2.3 结果分析
• 3.3 对复杂自动机的模拟
• 3.3.1 基本的思路
• 3.3.2 对复杂自动机的模拟
• 3.3.3 实例
• 3.3.4 分析
• 3.4 识别的语言
• 3.5 本章小结
• 第4章 借助环形的分子链设计分子自动机
• 4.1 设计的思想与方法
• 4.2 编码方式及操作步骤
• 4.3 实例
• 4.4 推广
• 4.5 识别的语言
• 4.6 误差分析
• 4.7 本章小结
• 结论
• 参考文献
• 致谢