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

摘要

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

目录

声明

摘要

1 绪论

1．1 生物计算的背景

1．2 DNA计算基本思想

1．3 本文结构

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．3 DNA分子的编码

2．3．1 DNA编码问题

2．3．2 DNA编码的约束条件

2．3．3 DNA编码方法

3 DNA计算模型

3．1 DNA粘贴模型

3．2 DNA剪接模型

3．3 质粒DNA模型

3．4 分子信标

3．5 DNA自组装模型

4 基本理论介绍

4．1 最小顶点覆盖问题

4．2 可满足性问题

4．3 0-1规划问题

5 最小顶点覆盖问题的DNA自组装算法研究

5．1 最小顶点覆盖问题的转化

5．2 最小顶点覆盖的DNA自组装算法

5．2．1 可满足性问题基本算法

5．2．2 生物操作步骤

5．3 实例分析

5．4 本章小结

6 基于质粒DNA模型的MVCP研究

6．1 MVCP的质粒DNA算法

6．1．1 将最小顶点覆盖问题转化成0-1规划问题

6．1．2 算法设计

6．2 实例分析

6．3 本章小结

总结和展望

参考文献

致谢

作者简介及读研期间主要科研成果