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

发布时间：2021-05-14 15:00

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

【文章来源】：湖南大学湖南省 211工程院校 985工程院校 教育部直属院校

【文章页数】：66 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第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 本章小结
结论
参考文献
致谢


【参考文献】：
期刊论文
[1]Arithmetic computation using self-assembly of DNA tiles:subtraction and division[J]. Xuncai Zhang a,b, Yanfeng Wang b, Zhihua Chen a, Jin Xu a,*, Guangzhao Cui b a The Key Laboratory of Image Processing and Intelligent Control, Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China b School of Electrical and Electronic Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China.  Progress in Natural Science. 2009(03)
[2]经典Ramsey数DNA计算模型（Ⅱ）:基于位序列的DNA计算模型[J]. 许进,范月科.  计算机学报. 2008(12)
[3]经典Ramsey数DNA计算模型（Ⅰ）:位序列计算模型[J]. 许进,范月科.  计算机学报. 2008(12)
[4]基于DNA计算自组装模型的Diffie-Hellman算法破译（英文）[J]. 陈智华.  计算机学报. 2008(12)
[5]基于自组装DNA计算的NTRU密码系统破译方案（英文）[J]. 张勋才,牛莹,崔光照,王延峰.  计算机学报. 2008(12)
[6]DNA纳米结构仿中国地图[J]. 钱璐璐,汪颖,张钊,赵健,潘敦,张益,刘强,樊春海,胡钧,贺林.  科学通报. 2006(24)
[7]基于线性自组装的DNA加法[J]. 赵健,钱璐璐,刘强,张治洲,贺林.  科学通报. 2006(21)
[8]一种图顶点着色DNA计算机模型[J]. 许进,强小利,方刚,周康.  科学通报. 2006(04)
[9]图的顶点着色问题的一种DNA算法[J]. 孙川,朱翔鸥,刘文斌,许进.  计算机工程与应用. 2006(04)
[10]图顶点着色问题的DNA粘贴算法[J]. 王淑栋,刘文斌,许进.  系统工程与电子技术. 2005(03)



本文编号：3185851