DNA自组装计算模型研究及其在图着色问题中的应用

摘要

快速、强大且通用的DNA计算模型是DNA计算机实现的基础。利用DNA自组装执行计算的想法已从实验上被证明具有可行性。基于DNA自组装的计算模型由于其通用性正被广泛研究，已有多种理论模型被提出以解决各种NP问题。DNA自组装凭借其自治性与可编程性被认为是实现DNA计算芯片化的可行手段。因此，对DNA自组装计算模型进行研究具有理论与实际意义。 本文首先研究了线性自组装、树状自组装及二维自组装的计算能力。回顾了几个通过形式语言表示法已经被证明的理论：线性自组装等价于正则语言；树状自组装等价于上下文无关语言；二维自组装等价图灵可识别语言。 本文的主要工作有： 1．本文提出了一种三维DNA自组装计算模型。首先，从实验的角度描述了三维DNA瓦片构造的可行性；其次，在二维瓦片组装模型的基础上，完善了三维模型的数学理论与形式化表示方法，为模型的进一步应用打下基础。 2．本文提出了一种枚举型的三维DNA自组装图着色模型。首先，引入一种简单的图着色非确定性算法；其次，根据算法设计不同种类的DNA瓦片；最后，说明自组装过程并对模型复杂性进行讨论。分析表明模型的组装时间为在线性，组装所需的瓦片种类数为常数。对于3着色问题，瓦片种类数为“20”。 3．本文提出了一种非枚举型的三维DNA自组装图着色模型。首先，设计一种带剪枝策略的图着色非确定性算法，算法可以降低自组装模型的解空间；其次，设计瓦片组装系统以实现这一算法：最后，通过理论证明，该瓦片组装系统可以非确定性地对任意图进行k可着色判断，并从成功的组装中输出可行的k着色方案。分析表明系统所需瓦片种类数与问题规模无关，组装时间为线性。对于3着色问题，瓦片种类数为“62”。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章 绪论

1.1选题背景及意义

1.2国内外研究现状和已有成果

1.2.1 DNA计算国际研究进展

1.2.2 DNA计算国内研究进展

1.2.3 DNA自组装技术研究进展

1.2.4二维DNA瓦片组装模型研究进展

1.2.5图着色问题的DNA计算方法研究进展

1.3论文的研究思路和主要工作

1.4论文的结构

第2章DNA自组装计算模型研究

2.1 Adleman的开创性实验

2.2 DNA自组装的形式语言文法定义

2.3线性自组装等价于正则语言

2.4树状自组装等价于上下文无关语言

2.5二维自组装等价于图灵可识别语言

2.6一种二维自组装抽象模型

2.6.1 Wang的瓦片覆盖理论

2.6.2瓦片组装模型的形式化表示

2.7本章小结

第3章 一种三维DNA自组装计算模型

3.1三维DNA瓦片构造

3.2模型的抽象几何结构

3.3模型的数学表示

3.4本章小结

第4章枚举型三维DNA自组装图着色模型

4.1图着色问题

4.2图着色非确定性算法

4.3邻接表与着色表

4.4三维瓦片设计

4.5自组装过程

4.5.1种子配置

4.5.2成功组装示例

4.5.3失败组装示例

4.6模型正确性分析

4.7模型复杂性分析

4.8本章小结

第5章 非枚举型三维DNA自组装图着色模型

5.1图着色问题

5.2自组装算法设计

5.2.1剪枝回溯图着色算法

5.2.2基于有序邻居的顶点排序算法

5.2.3带剪枝策略的非确定性图着色算法

5.3算法模拟

5.4自组装系统设计

5.4.1有限瓦片集合

5.4.2粘结强度函数

5.4.3阀值温度

5.5自组装系统验证

5.6模型复杂性分析

5.7本章小结

结 论

参考文献

附录A攻读学位期间所发表的学术论文目录

致 谢