K-臂DNA计算在最近邻聚类和MCP中的应用研究

发布时间：2017-05-08 18:05

  本文关键词：K-臂DNA计算在最近邻聚类和MCP中的应用研究，由笔耕文化传播整理发布。

【摘要】：生物分子的大小在纳米尺度，同时具有良好的可操作性和强大的信号转导能力，这为利用生物分子元件组装生物计算机的研究提供了可能。在生物计算领域，DNA计算从1994年Adleman博士成功采用生化试验解决了7顶点Hamilton问题以来，DNA计算的发展就引起了广泛的关注。DNA计算采用DNA链作为信息载体，将原始问题映射成DNA编码，采用生物酶为计算工具，分子水平的生化操作为计算方法，于生物实验室进行一些列操作而求解问题。DNA计算发展近20年来，诸多数学、生物、纳米科学和信息科学的科研人员都投身与这一领域。从目前来看，DNA计算在优化计算、信息安全，特别在求解组合优化问题中的NP问题上具有一种“天然”优势，同时无论在理论模型还是实践水平上，DNA计算都取得了很大的进展与突破，但其本身仍未成熟，仍然存在诸多理论问题和实际问题亟待解决，尤其是生物实验水平没有规范化和成熟，DNA模型的构建和使用由于其自身结构的限制而不能非常灵活。本文致力于对k-臂DNA分子模型的研究，在理论上完善该模型与发夹模型的关系，用以解决NP问题，具有十分重要的现实意义。本文的主要研究工作如下： 第一章在介绍了研究背景和意义之后，从宏观和微观两个角度，采用文献计量学的方法，对DNA计算发展近20年的状况——包括文献计量、核心期刊、核心作者等问题——进行了研究综述，为以后的研究者提供参考。 第二章介绍了DNA计算的基础理论知识，重点针对本文要使用的三类基础模型——k-臂分子模型、发夹模型、三链模型进行了阐述，并基于三者自身优势，探索了将其混合使用的可能性。即发夹模型完全可以作为k-臂分子模型的计算控制模型使用，而三链模型则是一种良性的筛选模型，可参与双链结构的筛选过程。为了充分说明DNA计算中编码水平、生物操作水平、模型发展对DNA计算会产生及其重要的推动作用，在第二章的后半部分，以三链模型为基础模型，改进原有编码水平并采用不同于原有读取解的方式，提出了对0-1规划问题的改进算法。 第三章在第二章的基础上，讨论了k-臂DNA分子中的一种特殊结构——3-臂DNA分子的特性，其可以直观表达二叉树的结构。因此，本章提出了基于3-臂分子的结构优势，结合发夹模型和三链结构的筛选，求解最近邻层次聚类问题的算法。在算法复杂性分析过程中，可看出k-臂分子在编码规模和操作复杂性上的优势。另外，该算法的提出，也拓展了k-臂DNA分子模型的应用范围，可以用来解决更多基于二叉树进行优化求解的问题。 k-臂DNA分子模型具有“天然”的表达图结构的能力，故对于图论问题的求解具有直观上的优势。图论问题中诸多问题是在寻找顶点与边满足一定关系的特殊子图或者集合，k-臂DNA分子与其控制模型——发夹模型结合，就可以有效控制k-臂分子上参与计算的边的数量和限制只有某些边才可以参与计算的实现。在该理论基础上，第四章提出了基于k-臂DNA分子模型求解最大团问题的算法。对一般情况的模拟发现，该算法所需的顶点块空间复杂性为多项式级别，优于O(（√3）n)。另外，引入进化计算的思想，给出算法流程，尝试改进解空间爆炸性问题，通过c++编写进化计算的仿真实验，检验进化计算为解空间爆炸问题的解决的贡献。 第五章给出相应的应用实例，对问题进行编码和按照算法操作步骤进行求解，通过实例验证的方式，说明所提出的算法的可行性和有效性。
【关键词】：DNA计算 k-臂DNA模型 三链模型 发夹模型 最近邻聚类 最大团问题
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：Q523;TP38
【目录】：

• 目录4-6
• 摘要6-8
• ABSTRACT8-10
• 第一章 绪论10-25
• 1.1 DNA 计算产生的背景和意义10-11
• 1.1.1 研究背景10-11
• 1.1.2 研究意义11
• 1.2 文献综述11-22
• 1.2.1 DNA 计算文献计量11-20
• 1.2.2 DNA 计算研究现状20-22
• 1.3 本文的研究内容与创新点22-23
• 1.3.1 本文的研究内容与框架22-23
• 1.3.2 本文的创新点23
• 1.4 本文的组织结构23-25
• 第二章 DNA 计算建模25-35
• 2.1 DNA 计算理论基础25-29
• 2.1.1 DNA 分子结构25-26
• 2.1.2 DNA 计算编码问题26-27
• 2.1.3 生物操作27-29
• 2.2 DNA 计算基础模型29-31
• 2.2.1 DNA 发夹模型构建29-30
• 2.2.2 三链 DNA 分子模型构建30
• 2.2.3 k 臂 DNA 分子模型构建30-31
• 2.3 基于三链 DNA 结构的 0 1 规划改进算法31-34
• 2.3.1 0 1 整数规划问题31-32
• 2.3.2 改进算法32-33
• 2.3.3 算法分析33-34
• 2.4 本章小结34-35
• 第三章 基于 3 臂 DNA 分子模型求解最近邻聚类问题35-39
• 3.1 最近邻聚类问题的分析与转化35-36
• 3.2 基于 3 臂 DNA 分子结构的 DNA 算法36-38
• 3.2.1 DNA 编码36
• 3.2.2 生物算法36-38
• 3.3 算法复杂性讨论38
• 3.3.1 时间复杂度（操作复杂度）38
• 3.3.2 编码序列规模38
• 3.3.3 空间复杂性38
• 3.4 本章小结38-39
• 第四章 基于 k 臂 DNA 分子模型求解最大团问题(MCP)39-48
• 4.1 最大团问题39
• 4.2 基于 k 臂 DNA 分子模型的算法39-42
• 4.2.1 结构块（Building Block）编码39-40
• 4.2.2 顶点块预处理算法40-41
• 4.2.3 算法实现41-42
• 4.3 算法复杂性42-43
• 4.3.1 时间复杂性（操作复杂性）42
• 4.3.2 编码序列规模42-43
• 4.4 最大团问题的三维 DNA 图结构进化算法43-46
• 4.4.1 DNA 计算与进化计算43-44
• 4.4.2 进化计算改进解空间规模算法44
• 4.4.3 进化算法与 DNA 计算的结合算法44-45
• 4.4.4 仿真实验45-46
• 4.5 本章小结46-48
• 第五章 最近邻聚类和 MPC 的 DNA 算法实例分析48-55
• 5.1 三链 DNA 分子模型应用实例48-50
• 5.1.1 问题描述48
• 5.1.2 基于三链模型的求解过程48-50
• 5.2 基于 3 臂 DNA 分子模型的层次聚类算法应用实例50-52
• 5.3 基于 k 臂 DNA 分子模型的最大团问题算应用实例52-54
• 5.4 本章小结54-55
• 第六章 结论与展望55-58
• 6.1 研究工作总结55-56
• 6.2 后续研究及展望56-58
• 6.2.1 后续研究及问题56
• 6.2.2 DNA 计算展望56-58
• 参考文献58-62
• 致谢62-63
• 硕士期间发表的论文和参与的项目63-64
• 附录一64-79
• 附录二79-85

【参考文献】

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

1 周康;刘朔;覃磊;易校尉;;基于粘贴模型的最大团问题算法[J];华中科技大学学报(自然科学版);2010年09期

2 李肯立;姚凤娟;李仁发;许进;;基于分治的背包问题DNA计算机算法[J];计算机研究与发展;2007年06期

3 张社民;方刚;;连通度问题的三维DNA结构进化算法[J];计算机工程与应用;2007年07期

4 杨静;殷志祥;;基于抗原中介三链DNA结构的0-1整数规划[J];计算机工程与应用;2008年02期

5 王立霞;淮晓永;;基于语义的中文文本关键词提取算法[J];计算机工程;2012年01期

6 薛洁;刘希玉;;基于DNA计算的层次图聚类算法[J];计算机工程;2012年12期

7 李汪根;丁永生;;DNA计算机中队列数据结构的设计及实现[J];计算机学报;2007年06期

8 李肯立;周旭;邹舒婷;;一种改进的最大团问题DNA计算机算法(英文)[J];计算机学报;2008年12期

9 李汪根;丁永生;任立红;;DNA计算机中广义表数据结构的设计与实现(英文)[J];计算机学报;2008年12期

10 张成;杨静;王淑栋;;DNA计算中荧光技术的应用及其发展[J];计算机学报;2009年12期

中国博士学位论文全文数据库 前1条

1 张鸿雁;基于DNA计算的聚类算法研究[D];山东师范大学;2011年

  本文关键词：K-臂DNA计算在最近邻聚类和MCP中的应用研究，，由笔耕文化传播整理发布。

本文编号：351595