全错位排列问题的几种DNA计算模型

论文摘要

DNA计算是一种以DNA和相关的某些生物酶作为最基本材料的,基于某种生化反应原理的新型的分子生物计算方法。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其他载体上经过一定时间完成控制的生物化学反应,以此来完成运算,使得从反应后的产物中能得到全部的解空间。DNA计算的基本思想是:利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码,把要运算的对象映射成DNA分子链,在生物酶的作用下,生成各种数据(datapool);然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程;最后,利用分子生物技术如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等,检测所需要的运算结果。它的最大优点是充分利用了DNA分子具有海量存储遗传密码以及生化反应的海量并行性。本文讨论了DNA计算在组合数学中的应用,尝试利用试管模型、表面模型和芯片模型来解决DNA计算领域内的时间复杂度转化为空间复杂度问题,给出了全错位排列问题的几种计算模型。本文提出的算法是有效和可行的,指出了各自的优点和存在的问题以及将来进一步的研究方向。

论文目录

• 摘要
• Abstract
• 引言
• 1 DNA计算的研究现状和存在的问题
• 1.1 DNA计算产生的背景
• 1.2 DNA计算的基本思想
• 1.3 DNA计算的研究现状
• 1.4 本文的主要研究内容
• 2 DNA计算的生物学基础
• 2.1 DNA分子的结构
• 2.2 操作DNA分子
• 2.2.1 DNA串的分离和结合
• 2.2.2 延长DNA
• 2.2.3 缩短DNA
• 2.2.4 剪切DNA
• 2.2.5 连接（linking）/粘贴（pasting）DNA
• 2.2.6 测量DNA分子的长度
• 2.2.7 捞出特定分子
• 2.2.8 放大（复制）DNA
• 2.2.9 读出序列
• 2.2.10 微量点样技术
• 2.3 DNA计算的实现方式
• 3 DNA计算的主要计算模型
• 3.1 单链DNA计算模型
• 3.2 双链DNA计算模型
• 3.3 单/双链混合计算模型
• 4 全错位排列问题的试管计算模型
• 4.1 全错位排列问题的数学模型
• 4.2 全错位排列问题的试管计算模型
• 4.2.1 方法概述
• 4.2.2 生物算法
• 4.2.3 生物编码
• 4.2.4 生物操作
• 4.2.5 结论
• 5 全错位排列问题的表面计算模型
• 5.1 全错位排列问题的表面计算模型一
• 5.1.1 编码
• 5.1.2 生物操作
• 5.1.3 模型分析
• 5.2 全错位排列问题的改进的表面计算模型
• 5.2.1 算法设计
• 5.2.1.1 基本算法
• 5.2.1.2 生物算法
• 5.2.2 编码和生物操作
• 5.2.2.1 编码
• 5.2.2.2 生物操作
• 5.2.3 实例分析
• 5.2.4 模型推广
• 5.2.5 模型分析
• 6 全错位排列问题的基于芯片的DNA计算模型
• 6.1 算法设计
• 6.1.1 基本算法
• 6.1.2 生物算法
• 6.2 编码和生物操作
• 6.3 模型分析
• 结论
• 参考文献
• 致谢
• 作者简介及读研期间主要科研成果
• 导师简介