基于DNA链置换和自组装技术的图连通度计算模型的研究

发布时间：2017-07-19 00:12

  本文关键词：基于DNA链置换和自组装技术的图连通度计算模型的研究

  更多相关文章： DNA计算 DNA自组装 连通度 DNA纳米金颗粒共聚体 双链DNA结构

【摘要】：DNA计算是一种以DNA分子作为存储数据和运算媒介的新型计算模型。它突破传统计算机概念,引入生物分子作为计算材料,并且DNA分子具有高度并行性、易操作、高存储等优点,是一门具有巨大发展潜力的新型学科。随着科学技术的发展,各个专家对其构建DNA分子模型、设计实现算法和生化试验研究,可以解决图论中的NP完全问题。本文主要研究连通度问题,该问题是图论中经典的NP问题。本文主要通过构建两种DNA自组装模型并利用链置换技术解决图的连通度,还对DNA计算的基本原理及其优缺点进行了简单的阐述。本文主要选取两种计算模型对图论中的连通度进行研究,主要包括：第一,本文利用双链DNA分子构建模型。然后根据简单算法利用DNA分子进行搜索,避免了计算中试管数的指数爆炸增长。为了验证这个算法,我们以一个简单的图G为例,说明应用该算法求解连通度的整个操作过程并给出了该双链DNA分子计算模型的详细生化过程和算法语言描述。同时根据具体图形设计模型和简单算法对图G详细执行过程进行了说明,从而求出图G的连通度。由于双链DNA分子的高度并行性降低了图的连通问题的复杂度(0(n-1)n/2+m))并且提高了实验的效率。第二,本文构建DNA/AuNP共聚体的三维DNA自组装计算模型解决图的连通度。根据本文给的具体图形设计共聚体模型,然后根据非确定算法经过一系列生物实验最后求出该图的连通度。另外本文还通过了Visual DSD和NUPACK对该生物实验进行了仿真,来说明该实验的可行性。与传统算法相比,该算法所需要的实验操作方便、容易操作,更重要是降低了求解该图的复杂度,为]DNA/AuNP共聚体模型的应用提供了可行性说明。为了证明双链DNA分子和DNA/AuNP共聚体模型解决图的连通度问题的可行性,阅读大量文献对比与综合还给了该模型的实验方案以及生物技术的详细操作过程。另外,本研究利用链置换技术通过巯基化将DNA分子与金颗粒相连接,这个实验同时也说明了对纳米金颗粒的控制达到一定水平,同时这对目前DNA计算的研究具有巨大的研究价值,从理论上可以提高分子计算的可靠性和准确性,同时由于实验的操作方法灵活,准确率高,这对解决图论中NP完全问题提供新思路。不过,本文的模型需要根据具体的图设计模型结构,虽然有Visual DSD的仿真来验证实验的可行性,但是并未用具体生化实验来验证模型的可行性。
【关键词】：DNA计算 DNA自组装 连通度 DNA纳米金颗粒共聚体 双链DNA结构
【学位授予单位】：陕西师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP384
【目录】：

• 摘要3-5
• Abstract5-9
• 第一章 绪论9-17
• 1.1 研究背景及意义9-10
• 1.1.1 研究背景9-10
• 1.1.2 研究意义10
• 1.2 国内外关于本的研究现状及趋势10-14
• 1.2.1 基于链置换的DNA计算10-13
• 1.2.2 DNA自组装技术13-14
• 1.3 本文主要研究内容14-15
• 1.4 本文结构15-17
• 第二章 DNA自组装结构研究进展17-27
• 2.1 前言17
• 2.2 DNA自组装计算17-21
• 2.2.1 DNA计算17-21
• 2.2.1.1 DNA计算原理18-19
• 2.2.1.2 DNA计算特点19-21
• 2.2.2 DNA纳米技术21
• 2.3 DNA自组装计算的模型21-25
• 2.3.1 一维自组装模型21-22
• 2.3.2 二维自组装模型22-24
• 2.3.3 三维自组装模型24-25
• 2.4 本章小结25-27
• 第三章 基于DNA分子算法求解图的连通度问题中的应用27-37
• 3.1 引言27-28
• 3.2 图的连通度问题28-29
• 3.3 双链DNA分子算法求解图的连通度问题中的应用29-35
• 3.3.1 双链DNA分子模型设计31-33
• 3.3.2 DNA分子的生物算法33-35
• 3.4 本章小结35-37
• 第四章 DNA纳米颗粒共聚体在图的连通度问题中的应用37-47
• 4.1 引言37
• 4.2 DNA纳米颗粒共聚体在图的连通度问题中的应用37-44
• 4.2.1 DNA纳米金颗粒共聚体的设计38-40
• 4.2.2 DNA共聚体的算法分析及其序列设计40-42
• 4.2.3 利用Visual DSD进行可行性分析42-44
• 4.3 本章小结44-47
• 第五章 结论与展望47-49
• 5.1 结论47-48
• 5.2 展望48-49
• 参考文献49-55
• 致谢55-57
• 攻读学位期间的研究成果57

【参考文献】

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

1 ;A novel computing model of the maximum clique problem based on circular DNA[J];Science China(Information Sciences);2010年07期

2 陈智华;;基于DNA计算自组装模型的Diffie-Hellman算法破译(英文)[J];计算机学报;2008年12期

3 许进;范月科;;并行型Ramsey数DNA计算模型[J];计算机学报;2009年12期

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

5 方刚;张社民;许进;;边连通度问题的三维DNA图结构解法[J];系统工程与电子技术;2006年01期

，

本文编号：560400