论文部分内容阅读
DNA计算技术是现代科学界一个新的研究范畴,它主要是以DNA作为计算工具,巧妙的利用DNA计算的强大并行能力,成功而方便地解决了诸如最小支撑树、最大Clique等NP难题。DNA计算的创始人是美国南加州大学的莱昂那多·阿德莱曼教授,是他在1994年利用DNA计算方法首次解决了一个著名的数学问题,即“7个顶点的哈密尔顿路径问题”。现在,科学家又开始了新的研究课题,利用DNA计算来创造生物计算机,把DNA分子放在人体或动物体内,对它进行操作和研究,其计算结果可通过荧光蛋白技术的实验来读取。本文主要说明了荧光技术的应用和对三类问题的DNA表面计算模型的具体剖析,对它们的基本算法、表面算法、误差以及由此引起的种种问题,都进行了说明。较为全面地介绍了表面DNA计算模型的概况,具体内容如下:哈密尔顿问题的表面DNA计算:哈密尔顿问题是我们经常会遇到的一类问题,它属于图论范畴。求一个给定顶点的哈密尔顿问题,传统的方法是在溶液状态下的DNA计算,通过生化反应的高效性和快速性的特点,生成问题的所有可能解。它的显著优点是充分反映了DNA计算的高度并行性。但是,它的缺点就在于不容易控制错配率和伪解的产生以及最终解。而表面即固体状态下的DNA计算一般是把编码的链固定到表面上,通过生化操作找出代表问题解的DNA链。可满足性问题的表面DNA计算:利用荧光技术对DNA分子表面进行标记,通过DNA固定化和杂交技术,将代表所有可能存在解的不同DNA序列固定在固相表面,然后通过多次的杂交以及降解过程来筛选出正确的解,通过荧光标记可以检测每次和最终计算的结果。0-1规划问题的表面DNA计算:首先针对每一个约束不等式,行进编码组合,然后在其表面上加入已经标记了的相应DNA补链,这时我们会发现,满足不等式的解的相应的链将与具有荧光标记的相应的补链进行杂交,从而产生不同颜色的荧光,最后通过荧光成像技术,进行操作,观察其实验结果并记录下可行解。现如今,虽然DNA计算已近广泛的应用到了科学的各个领域,但它还存在着许多的不足和缺点,像计算误差和编码错乱等一系列问题,还需要我们去改进。本文最后部分,对DNA计算以及DNA表面计算作了总结,指出一些需要改进的地方,这就为我们下一步的研究明确了方向。