DNA计算机：数学与生命的交融的论文.docVIP

DNA计算机：数学与生命的交融的论文 DNA计算机：数学与生命的交融的论文 摘要：本文在简单介绍了dna计算机理论的基础上，论述了由dna计算机所引发的计算方式的变革和生命观的变革，并最后指出，或许整个世界的进化过程就是一个计算复杂性不断增长的过程。 关键词：dna计算机；计算方式；生命观 1 dna计算的理论、特点和问题 1994年11月美国计算机科学家 l．阿德勒曼（l．adleman）在《科学》上公布了dna计算机的理论，并成功的运用dna计算机解决了一个有向哈密尔顿路径问题[1]。这一成果迅速在国际上产生了巨大反响[2]，同时也引起了国内学者的关注[3]。一些人相信，dna计算蕴含的理念可使计算的方式产生“进化”。另一些人则看到dna计算的理念将有助于揭示生命的本质与演化。总之，这一全新的计算理论，将在数学与生命科学中产生极其深远而广大的影响。同时它也提出了一系列值得我们深思的哲学性问题。 dna计算机目前尚处在理论研究阶段，一旦它在实用意义上获得成功，dna计算将彻底改变计算机硬件的性质。在过去的半个世纪里，计算机完全就是物理芯片的同义词。但阿德勒曼dna计算机则是一种化学反应计算机[4]。它的基本构想是：以dna碱基序列作为信息编码的载体，利用现代分子生物学技术，在试管内控制酶作用下的dna序列反应，作为实现运算的过程；这样，以反应前dna序列作为输入的数据，反应后的dna序列作为运算的结果。阿德勒曼具体应用哈密尔顿有向图这个经典npc问题，详细描述了他的理论。 dna计算机的提出，产生于这样一个发现，即生物与数学的相似性：①生物体异常复杂的结构是对由dna序列表示的初始信息执行简单操作（复制、剪接）的结果；②可计算函数f（w）的结果可以通过在w上执行一系列基本的简单函数而获得。阿德勒曼不仅意识到这两个过程的相似性，而且意识到可以利用生物过程来模拟数学过程，更确切地说是，dna串可用于表示信息，酶可用于模拟简单的计算。这是因为：①dna是由称作核苷酸的一些单元组成，这些核苷酸随着附在其上的化学组或基的不同而不同。共有四种基：腺瞟吟、鸟瞟吟、胞嘧啶和胸腺嘧啶，分别用a、g、c、t表示。一些单个的核苷酸顺序连在一起形成dna链。单链dna可以看作是由符合a、g、c、t组成的字符串。从数学上讲，这意味着我们可以用一个含有四个字符的字符集∑＝a、g、c、t来为信息编码（电子计算机仅使用0和1这两个数字）。②dna序列上的一些简单操作需要酶的协助，不同的酶发挥不同的作用。起作用的有四种酶：a．限制性内切酶，主要功能是切开包含限制性位点的双链dna；b．dna连接酶，它主要是把一个dna链的端点同另一个链连接在一起；c．dna聚合酶，它的功能包括dna的复制与促进dna的合成；d．外切酶，它可以有选择地破坏双链或单链dna分子。正是基于这四种酶的协作实现了dna计算。 自阿德勒曼用dna计算机解决了哈密尔顿有向图问题，随后很快便有人用dna计算机相继解决了其他一些疑难问题（npc完全问题），如可满足性问题等。与电子计算机相比，dna计算机有明显的优势。不过，这些还仅仅是利用分子技术解决的几个特定问题，是为解决特定问题而进行的一次性实验。dna计算机还没有一个固定的程式。由于问题的多样性导致所采用的分子生物学技术的多样性，具体问题需要设计具体的实验方案。于是，便引出了两个根本性的问题，阿德勒曼最早就意识到了它们：①dna计算机可以解决哪些问题？确切地说，dna计算机是完备的吗？即通过操纵dna能完成所有的（图灵机）可计算函数吗？②是否可设计出可编程序的dna计算机？即是否存在类似于电子计算机的通用计算模型——图灵机——那样的通用dna系统（模型）？目前，人们正处在对这两个根本性问题的研究过程之中。在我们看来，这就类似于在电子计算机诞生之前的20世纪三四十年代——理论计算机的研究阶段。如今，已经提出了多种dna计算模型，但各有千秋，公认的dna计算机的“图灵机”还没有诞生。相对而言，一种被称为“剪接系统”的dna计算机模型较为成功[5]。 由于dna链可以比作在四字符集上的串，为dna计算建模的自然方式就是利用专门处理字符和字符串的形式语言理论。建模的关键就是要将实际的dna重组抽象为数学上的剪接操作。实际的dna重组，就是在前面所提到的四种“工具酶”的作用下，对dna链的切割和粘贴的组合过程。其数学抽象称为剪接操作。大体可做如下描述：给定字符集∑（其元素为符号）及其上的两个字符串x、y，利用剪接规则r剪接x和y的过程可以分为：①在由剪接规则r决定的位置上切割x和y；②分别将结果中x的前段和y的后段、y的前段和x的后段连在一起。∑ 的剪接规则 r是形如α1#β1$α2#β2的词，其中α1、β1、α2、β2是∑的串，＃和$是∑外的标