论文题目: DNA计算若干问题研究
论文类型: 博士论文
论文专业: 计算机软件与理论
作者: 曲惠琴
导师: 朱洪
关键词: 计算,空间复杂度,数值参数,自由码子集,层次结构
文献来源: 复旦大学
发表年度: 2005
论文摘要: 1994年,Adleman用操纵DNA分子的办法解决了一个经典的NP完全问题—哈密顿路径问题(一个包含7个顶点实例)。自此以后,生物计算作为生物与计算机科学的交叉学科迅速的发展起来。 本文探讨了生物计算中最受关注的DNA计算中的一些算法及编码问题。 在第一章中,首先介绍了一些相关的预备知识;其次,对生物计算,特别是DNA计算的不同研究方面及状况进行了简要的总结分析,例如DNA计算的模型,解决NP完全问题的算法等。 在第二章中,提出了把参数算法应用于生物计算,以减少生物计算的空间复杂度的思想。这一章首先给出了顶点覆盖问题的参数算法,和这个参数算法用DNA计算模型实现的方法,并且得出这个算法以非常接近于1的概率的输出正确结果。 本章还利用独立集和顶点覆盖问题的关系,得到了在输入参数很大的情况下,降低解决顶点覆盖问题的所需分子数目的方法。相应的,也得到了独立集问题的生物参数算法。 在第三章中,首先给出了在粘结模型下解决带有数值参数的NP完全问题—划分问题的生物算法,并分析了其正确性。在此基础上,给出了背包问题相应的算法。本章的最后,还给出了一个可以进行连续加法运算的,主要使用剪切和连接操作的方法。 DNA计算的另外一个重要的问题是什么样的编码能够减少操作所需生化反应的错误。这个问题和DNA序列的组成有密切的关系,要减少错
论文目录:
摘要
ABSTRACT(英文摘要)
第一章 引言
1.1 DNA的结构与DNA计算中常用的操作
1.1.1 DNA的结构
1.1.2 Watson-Crick互补
1.1.3 DNA计算常用的操作
1.2 DNA计算的模型
1.2.1 剪接模型
1.2.2 插删模型
1.2.3 等同判定模型
1.2.4 禁止与强迫模型
1.2.5 自动铺砖模型
1.2.6 图灵机的实现
1.3 从理论到现实
1.3.1 Adleman的实验
1.3.2 DNA计算解决可满足性问题
1.3.3 生物计算其它方面的应用
1.4 本文的结构与内容
第二章 参数算法应用于DNA计算
2.1 背景知识
2.1.1 粘结模型
2.1.2 参数算法
2.2 粘结模型下顶点覆盖的概率参数算法
2.2.1 顶点覆盖的概率参数算法
2.2.2 顶点覆盖的生物概率参数算法
2.2.3 顶点覆盖的生物参数算法应用于独立集问题
2.3 粘结模型下独立集问题的概率参数算法
2.3.1 独立集问题的概率参数算法
2.3.2 独立集问题的生物概率参数算法
2.3.3 独立集生物参数算法应用于顶点覆盖问题
2.4 总结
第三章 解决带有数值参数的问题
3.1 粘结模型下解决划分问题
3.1.1 加法
3.1.2 求任意子集和
3.1.3 选择
3.1.4 划分
3.2 解决背包问题
3.3 连续加法运算
3.3.1 双剪切操作
3.3.2 操作数DNA分子序列
3.3.3 加法的实现
3.3.4 分析
3.3.5 小结
3.4 总结
第四章 DNA计算中的若干编码问题
4.1 DNA计算编码问题简介
4.1.1 汉明距离及其变体
4.1.2 从演化分析具有良好性质的编码
4.1.3 连贯码
4.2 演化自由码子集
4.2.1 基本知识
4.2.2 自由码子集
4.2.3 演化自由码子集
4.3 演化自由码子集的应用
4.3.1 码集的层次结构
4.3.2 DNA序列的解码
4.3.3 码集的选择
4.4 总结
第五章 结论与展望
5.1 结论
5.2 进一步的工作
参考文献
参与的科研项目与发表的论文
致谢
论文独创性声明
论文使用授权声明
发布时间: 2005-09-19
参考文献
- [1].若干DNA计算粘贴模型的研究[D]. 董亚非.华中科技大学2004
- [2].基于生化反应的典型约束可满足问题求解算法研究[D]. 吴帆.湖南大学2017
相关论文
- [1].DNA计算中的编码理论与方法研究[D]. 王延峰.华中科技大学2007
- [2].自组装DNA计算模型的研究及应用[D]. 张勋才.华中科技大学2009
- [3].赋权图上优化问题的DNA计算方法研究[D]. 韩爱丽.山东大学2008