子集积问题的DNA计算机算法研究

论文摘要

1994年,Adleman用操纵DNA分子的办法解决了一个经典的NP完全问题—哈密顿路径问题(一个包含7个顶点实例)。自此以后,生物计算作为生物与计算机科学的交叉学科迅速的发展起来。随着DNA计算研究的逐渐深入,现有基于穷举方法的DNA计算机算法中存在的解空间指数爆炸问题日益突出,已成为限制DNA超级计算应用的瓶颈因素,如何减少DNA计算机求解NP完全问题中以问题输入纯指数增长的DNA链数,已成为DNA计算研究的重要内容之一。现有DNA计算模型的并发操作难以达到电子计算机并行处理操作的自如程度,因此,不管基于DNA计算的何种模型,目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式,而DNA计算模型上的不可扩展是求解NP问题算法上难于扩展的原因。因此考虑将传统电子计算机并行处理的策略、方法和技术引入DNA超级计算是降低DNA链数的重要途径之一。这一问题源于现有DNA计算模型的不可扩展性。本文考虑将传统电子计算机中的并行策略应用于DNA计算中,采用理论分析和生物实践相结合的方法,解决DNA计算中限制DNA计算的瓶颈的DNA链数问题。具体将分治策略应用于DNA计算领域中,提出了基于分治策略的求解子集积问题的DNA计算机算法,并通过对现有算法中存在的时间复杂度过高的问题,提出一种具有较好可扩展性的改进质粒模型,并将分治策略应用于子集积问题的DNA分子算法设计中,提出一种求解子集积问题的新的DNA计算机算法。本文提出的算法的DNA链数均可达到亚指数的O(1.414n),其中n为子集积问题的维数。将提出的算法与已有文献结论进行的对比分析表明:本算法在不改变算法操作复杂性的条件下,将穷举算法中的DNA链数从O(2n)减少至O(1.414n),因此利用本算法在试管级水平上能将可破解的背包公钥的维数从60提高到120。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 DNA 计算的概念与原理
• 1.2.1 DNA 的生物知识
• 1.2.2 DNA 的代数结构
• 1.2.3 Adleman 实验
• 1.2.4 DNA 计算机原理和基本思想
• 1.3 DNA 计算和DNA 计算机的研究意义及进展
• 1.3.1 DNA 计算的优势
• 1.3.2 DNA 计算机理论模型
• 1.3.3 DNA 计算的应用
• 1.3.4 DNA 计算与DNA 计算机的研究的意义
• 1.3.5 当前DNA 计算机研究的主要方面和发展方向
• 1.3.6 评述和展望
• 1.4 本文主要工作
• 1.5 本文组织结构
• 第2章 DNA 计算模型
• 2.1 引言
• 2.2 粘贴DNA 计算模型
• 2.2.1 选用粘贴模型的原因
• 2.2.2 粘贴模型的编码步骤
• 2.2.3 粘贴模型的生物操作
• 2.2.4 生物操作的物理实现
• 2.2.5 粘贴计算
• 2.2.6 两种扩展的粘贴模型
• 2.2.7 小结
• 2.3 质粒DNA 计算模型
• 2.3.1 质粒DNA 计算的生物学模型
• 2.3.2 质粒DNA 计算的数学描述
• 2.3.3 小结
• 2.4 结论与展望
• 第3章 基于分治的子集积问题DNA 计算机算法
• 3.1 引言
• 3.2 Adleman-Lipton 模型
• 3.3 子集积问题的DNA 计算机算法
• 3.4 DNA 计算机子算法设计
• 3.5 子集积问题的DNA 计算机算法
• 3.6 模拟实验结果
• 3.6.1 DNA 编码
• 3.6.2 算法求解过程
• 3.7 结论
• 第4章 基于改进质粒模型的子集积的DNA 计算机算法
• 4.1 引言
• 4.2 二表算法及 DNA 计算模型
• 4.2.1 基于粘贴模型的DNA 计算机算法
• 4.2.2 改进的质粒模型
• n）链数的DNA 计算机算法'>4.2.3 O（1.414ⁿ）链数的DNA 计算机算法
• 4.3 算法实现
• 4.4 结论
• 结论
• 参考文献
• 致谢
• 附录 攻读硕士期间发表的论文