论文部分内容阅读
Adleman博士通过对含有7个顶点的有向哈密顿路的顶点进行编码,得到相应的DNA链,再通过生物操作：连接,变性,PCR扩增,电泳等等求解出了这一难题。实验的成功,开启了分子计算,尤其是DNA计算的新篇章。DNA链作为遗传信息的载体,其自身的含有大量的遗传密码,及其计算时巨大的并行性不仅仅对解决像：可满足性问题,顶点覆盖问题,团问题,和独立集问题等NP-完全问题提供了新思路,也吸引着专家学者们将DNA计算与其他学科或算法相结合用于解决更多的实际问题。本文首先介绍了最小生成树和可满足性问题的一些背景知识,及现在的研究现状,其次对DNA计算的编码及一些常用的计算模型进行了总结。然后,详细介绍了用凝胶电泳的方法求解最小支撑树的相关问题。利用DNA的热力学特性,根据图的边权长不同,给它们设计不同的DNA链,这些DNA链的溶解温度也不同。根据温度的不同,进行电泳时DNA分子的形状不同,电泳的速度也不同。再根据电泳速度分离出最小支撑树的所有边。以五个顶点的赋权图为例并求它的最小支撑树,用来说明该方法的简便性。接着,介绍了用基于DNA自组装模型求解可满足性问题。先通过编码可满足性问题变量的特殊补链,使其自组装成分子信标结构；再与数据池中初始DNA链发生杂交反应,通过反应前后分子信标的荧光的变化来判断是否是可满足性问题的解。若是可行解会产生荧光,通过拍照即可记录可行解。该方法操作简单,便于观察。最后,总结全文,以DNA计算模型在图论与离散数学中为例,讨论了DNA计算模型的应用,并展望DNA计算及DNA计算机的发展前景。