最小顶点覆盖问题的几种DNA算法研究

发布时间：2017-10-30 03:14

  本文关键词：最小顶点覆盖问题的几种DNA算法研究

  更多相关文章： DNA计算 DNA计算模型 最小顶点覆盖 DNA自组装 质粒DNA模型

【摘要】：传统的计算机由于其自身存储量和计算能力的有限,已经不能满足日益发展的科学形势。1994年,Adleman探索性的将现代生物技术与DNA操作技术结合起来,成功解决了具有七个节点的有向赋权图的哈密尔顿路径问题(Hamilton path problem),从此打开了生物计算的大门,让DNA分子作为一种新型的计算机硬件成为可能。而DNA分子由于具有传统计算机无法比拟的海量存储量和高度的计算并行性,使得其在密码学,数学,计算机等领域得到了广泛的青睐。本文将具体阐述DNA计算的研究背景、DNA分子结构、DNA分子操作过程等基本理论,并且对DNA分子操作过程中的初始编码问题进行了具体的分析,包括初始编码问题的基本概念,初始编码的约束条件和具体的编码方法；还将简单介绍一些常用的DNA计算模型(剪接模型、分子信标、质粒DNA模型以及DNA自组装模型等)的基本操作原理及优缺点。此外,本文将具体介绍最小顶点覆盖问题、可满足性问题、线性规划问题的基本概念,并巧妙的将复杂的最小顶点覆盖表转化为形式简便的0-1规划问题和可满足性问题,这也是本文的创新之处。并在此基础上,结合DNA自组装模型、质粒DNA模型,给出基本算法和具体生物操作过程,具有一定研究意义。
【关键词】：DNA计算 DNA计算模型 最小顶点覆盖 DNA自组装 质粒DNA模型
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP38
【目录】：

• 摘要5-6
• Abstract6-11
• 1 绪论11-15
• 1.1 生物计算的背景11-12
• 1.2 DNA计算基本思想12-14
• 1.3 本文结构14-15
• 2 DNA生物计算15-26
• 2.1 DNA分子结构15-16
• 2.2 DNA分子操作16-20
• 2.2.1 DNA分子的变性与复性16-17
• 2.2.2 DNA链的自我复制17-18
• 2.2.3 DNA链的内切和外切18-19
• 2.2.4 DNA分子的连接19-20
• 2.3 DNA分子的编码20-26
• 2.3.1 DNA编码问题20-21
• 2.3.2 DNA编码的约束条件21-23
• 2.3.3 DNA编码方法23-26
• 3 DNA计算模型26-32
• 3.1 DNA粘贴模型26
• 3.2 DNA剪接模型26-27
• 3.3 质粒DNA模型27-28
• 3.4 分子信标28-30
• 3.5 DNA自组装模型30-32
• 4 基本理论介绍32-34
• 4.1 最小顶点覆盖问题32
• 4.2 可满足性问题32-33
• 4.3 0-1规划问题33-34
• 5 最小顶点覆盖问题的DNA自组装算法研究34-38
• 5.1 最小顶点覆盖问题的转化34
• 5.2 最小顶点覆盖的DNA自组装算法34-35
• 5.2.1 可满足性问题基本算法34-35
• 5.2.2 生物操作步骤35
• 5.3 实例分析35-37
• 5.4 本章小结37-38
• 6 基于质粒DNA模型的MVCP研究38-42
• 6.1 MVCP的质粒DNA算法38-39
• 6.1.1 将最小顶点覆盖问题转化成0-1规划问题38
• 6.1.2 算法设计38-39
• 6.2 实例分析39-40
• 6.3 本章小结40-42
• 总结和展望42-43
• 参考文献43-46
• 致谢46-47
• 作者简介及读研期间主要科研成果47

【参考文献】

中国期刊全文数据库 前10条

1 周康;刘朔;覃磊;易校尉;;质粒DNA计算模型的计算体系[J];华中科技大学学报(自然科学版);2011年02期

2 符友伟;吴蕾;;多肽固相合成法中的3个关键点[J];化学工业与工程;2010年04期

3 范月科;强小利;许进;;图的最大团与最大独立集粘贴DNA计算模型[J];计算机学报;2010年02期

4 羊四清;李小龙;袁辉勇;;图的最小顶点覆盖问题的DNA表面计算模型[J];计算机工程与应用;2009年06期

5 许进;谭钢军;范月科;郭养安;;DNA计算机原理、进展及难点(Ⅳ):论DNA计算机模型[J];计算机学报;2007年06期

6 赵军;贺大林;;分子信标在活细胞研究中的应用新进展[J];国际生物制品学杂志;2006年02期

7 王淑栋,刘文斌,许进;图的最小顶点覆盖问题的质粒DNA计算模型[J];华中科技大学学报(自然科学版);2004年11期

8 高琳,许进;最小顶点覆盖问题的DNA分子算法[J];系统工程与电子技术;2004年04期

9 殷志祥,张风月,许进;基于分子信标的DNA计算[J];生物数学学报;2003年04期

10 刘文斌,王淑栋,许进;DNA计算中的编码方法研究[J];计算机工程与应用;2003年27期

中国博士学位论文全文数据库 前2条

1 强小利;图顶点着色DNA计算模型及实验研究[D];华中科技大学;2008年

2 王延峰;DNA计算中的编码理论与方法研究[D];华中科技大学;2007年

中国硕士学位论文全文数据库 前1条

1 朱翔鸥;DNA计算编码研究及其算法实现[D];浙江工业大学;2006年

，

本文编号：1115860