论文部分内容阅读
DNA 计算是1994年由美国加利福尼大学的Adleman博士[1]提出来的。他富有开拓性地为科学领域开创了用分子生物技术进行计算的新方法，成为人类科学发展史上的一次革命性的里程碑。在以后短短的几年里，关于DNA计算的研究已经取得了不少令人欣喜的结果。 国际上掀起了一场研究DNA计算的“热潮”。
本文首先介绍了DNA计算的基础知识，DNA计算的研究现状和DNA计算发展的光辉前景。同时我们发现现在用DNA计算方法已经解决的NP问题大多数是无权值的NP问题，而在实际生活中我们经常遇到需要解决的问题是有权值的NP问题，例如旅行商问题和最短路径问题。结合这一实际情况，我们首先介绍了Adleman-Lipton模型，然后我们利用这一模型，通过基本的生物化学实验，设计了合适的程序步骤，理论上成功地解决了上述两类NP问题，使得在电子计算机上需用指数级的时间内解决的这两类NP问题，用DNA计算在多项式的时间内能解决。
另外目前DNA计算大多数是在试管溶液中进行的，它的基本操作是将经过编码的DNA链作为输入分批置入试管中，在试管中通过设定的生物化学反应来完成运算，并从反应后的产物中得到全部的解。这种在溶液中的DNA反应虽然具有较强的灵活性，但也存在若干难以克服的困难，如中间产物分离困难、反应体系复杂、中间过程难以监控、反应的可重复性较差、与电子计算机难以实现融合等。针对这种情况，结合现在实际的操作要求，目前有人用表面计算的方法解决这类难题。在文中我们利用一种新的表面计算方法理论上成功地解决了一个NP问题——连通性问题，并以它为例详细的说明了这种方法的思路和操作过程。