DNA计算在图论中的应用

论文摘要

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学反应作为计算工具的先例,具有广阔的应用前景。1994年,Adleman首次在Science公布了DNA计算的理论,利用DNA计算解决了图论中的哈密顿路径问题,并成功地进行了实验。Adleman的DNA计算完全是一种新的概念。它突破了传统计算机体系结构的束缚。DNA计算的基本思想是:利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码,把要运算的对象映射成DNA分子链,在生物酶的作用下,生成各种数据池（datapool）,然后按照特定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后,利用分子生物技术如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等,检测所需要的运算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其它载体上经过一定时间完成可以控制的生物化学反应,并以此来完成运算,使得从反应后的产物中能得到全部的解空间。本文主要讨论了三类图论中问题的DNA计算模型,具体如下:最小支撑树问题的DNA算法:最小支撑树问题是图论中一个重要的、应用性很强的问题。求一个给定图的最小支撑树,常见的方法是Kruskal避圈法和破圈法。但这两种方法都需要判断图的圈,这是非常繁琐的。在这一章中,我们利用最小支撑树的基本定义及DNA编码,借助生物的基本操作电泳、探针分离及测序,给出了最小支撑树的DNA算法。通过该算法,最多只需n-1步就可以找到图的最小支撑树（n为图的定点数）。图的顶点着色问题的DNA算法:利用DNA粘贴模型的巨大并行性,从图顶点着色问题的本质出发,先把图的顶点着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法以解决图的顶点着色问题。实例证明DNA粘贴算法在理论上可以实现的。无向赋权图哈密顿路径问题的DNA算法:我们通过链中G、C含量的不同来表示不同的权值,对于权值较高的边使其具有高的GC含量否则具有较低的GC含量;因为GC配对是形成三共价键其解链温度（Tm）大于AT形成的二个共价键的结合,我们就很容易的能够根据它们解链温度的不同来提取出权值低的路径。我们采用粘贴短链随机生成所有路径,提取解时采用加热变性与PCR反应同时进行的方式,首先变性的个体具有较低的权值优先得到扩增,这样的特点很好的解决了权值表示及分离的问题。权值的表示方法对于其他相关问题也很有借鉴意义。针对GC碱基对进行配对时形成的三共价键能量高于AT结合时二共价键的特对权值进行编码并利用改进的PCR反应给出了较好的解决途径。为DNA计算模型在处理权值方面提供了好的方法。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 DNA计算产生的背景
• 1.2 DNA计算的基本思想
• 1.3 DNA计算的研究现状和最新进展
• 1.4 本文的主要研究内容
• 2 DNA计算中的生物操作
• 2.1 DNA分子的结构
• 2.1 DNA计算中常用的分子操作
• 2.2.1 DNA分子的合成
• 2.2.2 DNA分子的切割和破坏
• 2.2.3 DNA分子的连接和粘贴
• 2.2.4 DNA重组
• 2.2.5 混合/合并
• 2.2.6 变性和杂交
• 2.2.7 DNA分子的扩增
• 2.2.8 DNA分子的分离和获得
• 2.2.9 DNA分子的检测和读取
• 2.3 DNA计算的实现方式
• 2.4 DNA计算的编码规则
• 2.5 本章小结
• 3 分子计算初步
• 3.1 Adleman实验
• 3.2 可满足性
• 3.3 问题与展望
• 4 最小支撑树的DNA算法
• 4.1 最小支撑树问题
• 4.2 最小支撑树问题的算法设计
• 4.3 最小支撑树问题的DNA计算模型系统
• 4.3.1 最小支撑树问题的DNA编码
• 4.3.2 最小支撑树问题的生物操作
• 4.4 实例分析
• 5 图着色问题的DNA粘贴算法
• 5.1 图着色问题
• 5.2 粘贴DNA计算
• 5.2.1 粘贴存储物
• 5.2.2 位串的操作
• 5.3 图着色问题的DNA算法
• 5.4 算法的实现
• 5.4.1 图的顶点独立集的DNA粘贴算法实现
• 5.4.2 图的顶点划分问题的DNA粘贴算法
• 5.4.3 DNA粘贴模型求解图着色问题
• 5.5 结论
• 6 无向赋权图哈密顿路径问题中的DNA计算
• 6.1 无向赋权图哈密顿路径问题描述
• 6.2 初始DNA代码设计以及生物操作
• 6.3 分子计算编程
• 6.4 实例中应用和问题推广
• 6.5 结论
• 结论
• 参考文献
• 致谢
• 作者简介及读研期间主要科研成果