求解Ramsey数的DNA计算模型

摘要

经典Ramsey数问题是一个NP完全问题,使用传统的电子计算机求解该问题,面临着计算时间复杂度指数爆炸问题。既然传统的电子计算机求解NP完全问题显得无能为力,那么就有必要提出新的计算方法。DNA计算具有高度并行性、高密度存储空间的显著优点。所以,DNA计算用于求解NP完全问题具有理论上的可行性。论文对经典Ramsey数的DNA计算模型进行了研究和探讨。全文主要研究工作如下:
　　1)给出了求解经典Ramsey数问题的一种新思路,它是建立经典Ramsey数DNA计算机模型的基础。首先,建立了表示一个图序列的编码方法,并指出该编码方法所存在的问题,即存在大量图的同构问题;其次,讨论了标定与非标定子图的集合问题,重点是序列表示方法;再次,给出了删除非解的思想、方法与步骤,目的是将非解消灭在萌芽状态,并且给出了算法实例。
　　2)求解经典Ramsey数问题的一个关键的问题是计算图的最大团与最大独立集,图的最大团问题与最大独立集问题是两个经典的NP完全问题。论文建立了求解图的最大团与最大独立集问题两种DNA计算模型。首先,详细地介绍了求解图的最大团与最大独立集算法研究概况,重点介绍了求解经典Ramsey数问题的DNA计算模型;其次,建立了基于粘贴模型求解图的最大团与最大独立集问题的DNA计算模型。该模型是一种理论模型,实验操作具有一定的难度,可行性很大程度上受到生物技术的影响;最后,建立了一种所谓并行型最大团与最大独立集 DNA计算模型,这是一种已经可以实用的DNA计算模型,论文详细地给出了该模型的具体方法、步骤,并给出了实现每个步骤的生化操作方法。
　　3)建立了所谓的基于加位序列的经典Ramsey数DNA计算模型。该模型由存储子系统、运算子系统和解的检测子系统构成,应该是一个新颖的求解经典Ramsey数问题DNA计算模型。首先,给出了存储中的编码方法、步骤,诸如约束条件问题、编码算法、探针设置等;其次,建立了运算子系统,重点是以PCR技术进行生化操作的方法、步骤;最后,描述了该模型解的检测子系统。
　　4)建立了并行型经典Ramsey数DNA计算模型。该模型的基本思想是将一个给定图所转换的位序列进行分段,然后分别按照各个小段删除非解,再逐步逐位进行合并。具体地说,首先介绍了模型的基本思想、算法步骤;然后,给出了分段方法及相应的编码技术;接着,介绍了每个初始解空间建立的方法、步骤以及非解的删除;最后,给出了子段间的合成方法与生物实现,并且给出了一个具体的算法实例。
　　简言之,论文建立了求解经典Ramsey数的DNA计算模型,给出了加位序列Ramsey数DNA计算模型和并行型Ramsey数DNA计算模型。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪 论

1.1经典Ramsey数研究进展

1.2 DNA计算研究综评

1.3研究内容

1.4论文创新点

2 预备知识

2.1图的概念与基本理论

2.2 Ramsey数的概念与有关理论

2.3 DNA计算的基础知识与生物操作

3 求解经典Ramsey数位序列计算模型

3.1序列编码

3.2 p-阶子图的集合

3.3非解的删除问题

3.4实际例子：求解r(3,4)的计算实例

4 最大团与最大独立集DNA计算模型

4.1引言

4.2并行型最大团DNA计算模型

4.3求解图最大团的DNA计算模型

4.4图的最大团与最大独立集粘贴DNA计算模型

4.5总结

5 基于加位序列的DNA计算模型

5.1引言

5.2存储子系统中编码问题的研究

5.3运算子系统

5.4检测子系统

5.5总结

6 并行型Ramsey数DNA计算模型

6.1引言

6.2求解Ramsey数的基本方法思路

6.3并行型Ramsey数DNA计算模型

6.4结论

7 全文总结与研究展望

致谢

参考文献

附录1 攻读博士学位期间发表的论文目录

附录2 发表论文和学位论文的对应关系

附录3 攻读博士学位期间参加的项目和奖项