最小支撑树的DNA凝胶电泳算法

DNA计算是解决困难问题的一种很重要的方法。应用DNA计算解决图论中的最小支撑树问题。利用DNA的热力学特性,根据边的权长不同,给它们设计不同溶解温度的DNA链。根据温度的不同,电泳时DNA分子的形状不同,电泳的速度也不同,从而根据电泳速度分离出最小支撑树的所有边。在这里给出了5个顶点的赋权图为例来求它的最小支撑树,说明了该方法的简便性。

中国邮递员问题的DNA荧光标记检测

本文给出了中国邮递员问题的一种基于DNA计算的解的检测方法,运用了较为简单的编码形式,然后结合PCR及凝胶电泳,和基于表面的荧光标记等技术,并通过给定的例题,证明了该方法的可行性,最终得到中国邮递员问题的最优解,该方法法简单明了,易于解读结果,便于操作。

基于分子信标的图的最小顶点覆盖问题

生物芯片技术和DNA计算分别是近几年来生命科学与信息科学的新兴研究领域,DNA计算在求解NP问题上存在着硅计算无法比拟的先天优越性。而图的最小顶点覆盖问题是图论中的一个重要问题,目前还没有好的算法。在DNA计算和DNA计算芯片的基础上,采用分子信标编码策略,利用观察荧光来确定图的最小顶点覆盖问题的可行解。利用分子信标模型来解决图的最小顶点覆盖问题,和其它DNA计算方法相比,该方法操作起来更加方便。