试管里的巨变：DNA计算机

www.quantumac.com

前言：半导体工业数十年来都遵循着摩尔定律而迅猛发展，然而作为半导体工业的基石——“硅”，由于材料自身所受到的物理局限，可以预见在未来以硅为主要材料的半导体工业终将放慢它的脚步，因此科学家们也在不断的探索采用新的材料和有别于目前“冯.诺依曼”体系的全新计算机，如量子计算机，光子计算机等等，而随着生物工程学的日新月异，一种全新的计算机和全新的计算模式正呈现不可阻挡的发展势头，在本文中，笔者将结合一个著名的数学命题介绍这一计算机发展的全新领域——DNA计算机！

1994年Leonard M. Adleman用一种非同寻常的方式解决了一个原本很简单的问题。这个问题普通人只要几分钟就可以轻松的解决，而如果采用一般的台式电脑只要花费数秒的时 间。而Leonard M. Adleman却花费了整整七天才找到答案。因为他使用了DNA来解决这个问题。而这个实验在分子计算领域却有着里程碑式的意义。

Adleman解决了一个非常著名的问题。这个问题的正式名称叫做哈密尔敦直接路径问题。但是更通俗的叫法是：“售货员旅游问题”。（以下简称JST）： 假定有一个售货员他必须向他经过的每一座城市推销产品，但是为了节约时间，每座城市他只能途经一次，而路径不能重复，而这个问题就是让你为这个推销员设计 这样一条路径。随着城市的增加，问题会变的越来越困难。随着难度的增加，要搜索到正确的路径就需要更加强大的计算能力。同时，大量计算所花费的时间也会越 来越多。问题最终会复杂到需要动用目前最先进的超级计算机。Adleman的实验仅仅解决了7座城市的问题，而要解决这么简单的问题甚至只需要动用你的直 觉。然而这个问题的解决，在许多方面都有着非凡的意义，在下文中作者会向大家解释其中的原因：

这个实验的成功向我们证明了通过利用DNA来计算，使用传统的计算方法，以前很难解决或根本无法解决的问题将变的轻而易举。它开创了在分子水平进行计算的 先例。它突破了硅工业领域在未来永远也达不到的材料尺寸限制。它证明了DNA作为一种数据存储结构的独特应用前景。它还证明了DNA可以以大量的并行方式 工作。

DNA:一种独特的数据结构

DNA的数据密度是领人惊讶的，它就像一条采用0和1编码的数据链。而一条DNA实际上是采用了四个遗传因子编码的：用字母表示分别为：A, T, C,和G。这四个遗传因子（又叫做核苷），以彼此间隔0.35毫微米（十亿 分之一米）沿着DNA分子链排列。这种结构使的DNA有着每英寸接近18M比特的令人不可思议的数据密度。在二 维的角度上看，假设每平方毫微米上只有一种遗传因子，那么数据的密度将超过一百万兆比特每平方毫微米。 相比较目前典型的高性能硬盘每平方英寸7G比特的数据密度，DNA的存储因子只是它的十万分之一。

DNA的另一个重要的特点是它的双链结构属性。遗传因子A和T,C和G能够彼此结合在一起，组成双螺旋结构。所以每个DNA的次序都有一个自然的互补结 构，假定一条S链的次序是ATTACGTCG，那么与之对应的S'的次序就是TAATGCAGC。 S链和S'链会结合（杂交），形成双螺旋DNA形态。这种互补的特性和独特的数据存储结构为它在电脑应用领域提供许多可利用的空间，例如：错误纠正， DNA出错有许多的原因，有时侯DNA酶会发生错误，它会错误的切下一个遗传因子，或错误的加入T将G结合。DNA也会被热量或来自太阳的紫外线给破坏。 如果一条DNA链发生错误，那么修复酶将会参考另一条与之对应互补的DNA链来修补受破坏的那条DNA链。双螺旋结构酷似现在我们采用的RAID 1磁盘阵列。数据在二个硬盘上产生镜像，如果第一个硬盘上的数据发生错误，那么将很快的可以从第二块硬盘上恢复数据。在生物学系统中，这种错误纠正的机制 使得出错的概率变得非常之低。在DNA复制的过程中每10的九次方的复制才可能发生一次的错误，换而言之就是出错的概率仅为10负九次方分之一。

以并行的方式工作：

在细胞里，DNA可以被许多的酶改变。而酶是一种可以根据DNA的自然属性读取或处理DNA的微小蛋白质。有各种各样的可以进行这样“操作”的蛋白质。它 们在分子尺度之内操纵着DNA。例如，有的酶可以切断DNA,有的则可以将切断的DNA“粘贴”到它的背面，其它酶的功能还有复制，修复等。分子化学，生 物化学和生物工程学已经开发出各种技术，这些技术可以让我们在试管里就可以完成大部分这些细胞的功能。这个细胞“工厂”，进行这一系列的化学合成反应。这 就像是电脑的工作一样，CPU进行着基本的运算操作，如：加法运算，数位转换，逻辑操作（或，与，非）等，在DNA中甚至可以进行最复杂的运算，DNA可 以剪切，复制，粘帖，修复等等。而这一切都可以在试管中进行。酶不是在一个DNA中的某个时间起作用。而是在每个DNA分子中同时持续的发挥作用。这种强 有力的DNA计算，可以以强大的并行方式进行工作。

DNA vs. 硅

DNA由于它独特的数据结构，使它具有进行大量的并行操作的能力，同时能够使你从不同角度解决一个问题。基于晶体管的计算机，采用的都是顺序执行的办法进 行运算操作的，当然有一些多处理器电脑和现在CPU里也采用了一些并行技术。但总的来说，采用“冯.诺依曼”架构的电脑，都是以顺序执行指令的方式运作 的。一台“冯.诺依曼”电脑，也就是目前所有CPU的工作方式:基本上都是采用了“读取-执行 循环”的模式，一遍一遍的不停的重复执行；CPU读取指令，然后从内存中取得相应的数据,它速度飞快的一遍一遍，一行一行的读取并执行指令。而DNA电脑 并不是基于“冯.诺依曼”架构的，这种随机的机器可以为了解决各种不同的问题，采用了和传统的电脑不同的运算方式。

具有代表性的是，提高硅电脑的性能往往意味着加快时钟的频率（或者扩大数据的路线），提高系统性能的重点在于提高CPU的速度而非内存的容量。举例来说： 提高一倍的时钟频率比增加一倍的内存容量更能提高系统的性能。而对于DNA电脑来说，电脑的计算能力却取决于内存容量和并行处理，如果让DNA电脑强制以 顺序执行的方式运行，那它将失去它的优势。举例说明：让我们来看看DNA的读写速率吧，在细菌里：DNA可以在一秒钟内复制500对的，从化学领域来看， 这已经是非常快的速度了（是人体细胞分裂速度的10倍），而且在复制的同时它还有着极低的错误率，这已经是一个了不起的成绩了。但是它的数据传输速率只有 1000 bits/sec,和目前硬盘平均的数据传输率相比，这就好比是蜗牛的速度。当是，如果你让DNA中的大量的复制酶并行运作，一个复制酶甚至可以在还未完 成第一个链的复制工作时就开始复制下一条DNA链。所以实际的数据传输率就达到了2000 bits/sec。而在每次复制完成后，下面的复制速度又会呈指数形式的增加。每增加一条DNA链，数据的传输速率就会增加一倍，10次复制之后，DNA 的复制速率就将达到1Mbit/sec,而在复制30次之后，将达到1000 Gbits/sec。这就将大大超越目前最快硬盘的数据传输率。

下面让我们解释如何利用“硅”和DNA电脑来解决这个“售货员旅行问题”（城市的数目小于十个）。对于一台“冯.诺依曼”电脑来说，一个简单的办法是建立 一个“搜索树”，陆续的检查每个完整的分枝，保留下最短的路线。使用好的搜寻算法可以提高运算的速度，新的路线将和原来最短的路线来对比，比它长的路线将 被“砍掉”，比它短的则被保留。直到找到最短的路线为止。而另一种方法是先找出全部所有的路线，然后在在其中找出最短的一条。而要采用这种方法对于传统的 计算机来说实际上是不可能的，因为假设有20个城市，那么存储路线所需要的内存的容量将达到4千5百万G的字节。即使是运算能力达到100MIPS的电 脑，也需要运算2年的时间才能完整的遍历所有的路线。然而如果使用DNA电脑，这种办法就变得切实可行。只需要若干立方毫微米的物质，就可以进行遍历所有 路线的运算，而所有的操作都不必以顺序的方式计算，而可以以并行的方式处理的。

Adleman的实验

让我们就“哈密尔顿路线”问题，通过Adleman的实验，来一步一步具体的解释DNA电脑的运作的。（原理相同的，但是在一些细节上有所省略)

假设我住在L.A(洛杉矶)，需要访问以下四座城市:Houston(休斯敦）, Chicago(芝加哥）, Miami(迈阿密）,和NY（纽约）而NY是我最终的目的地(我的路线还受制于航空公司的飞行航线，比如：有航班从L.A到Chicago但却没有航班 从Miami到Chicago）如果我要不重复的一次就走遍所有的城市，该选择怎样一条路线？

我们只要花一点时间就可以看到，只有唯一的一条路线可以实现我们的目标，从L.A出发，途经Chicago, Dallas, Miami最终到达N.Y，而其他的路线要么不得不重复经过同一座城市，要么就得错过一座城市，或者最终的目的地不在N.Y。很明显，在这个问题上，我们 无需借用电脑的帮助，即使是城市的数目增加到5，6，甚至是8个。不过随着问城市数量的增加，问题会变得越来越棘手。而一些随机路线的增加将会使要搜寻的 路线呈指数级增长。不久以后，你就不得不依靠电脑来帮你解决问题。

而对于DNA电脑来说，问题可以迎刃而解。它只需要列出所有可能的路线，然后找出其中最适合的路线就可以了。这也就是DNA电脑的优势。DNA这些微小的 物质组合在一起，可以快速的处理许多不同的数据流，一旦DNA分子中众多的酶开始共同的工作，大量的选择处理工作就开始进行。

在Adleman的实验中:具体的计算方法如下：

1、列出所有可能的路线
2、列出出起始于出发城市终止于目的地的所有路线
3、列出包含有正确城市数目的路线
4、列出只经过所要旅行城市一次的路线

以上的全部的步骤都可以以现代标准的分子生物学技术实现。

第一步：列举出所有可能的路线

方法：利用短的DNA序列给每个城市的进行编码。通过连接每个城市的序列为每条的路线进行编码。

DNA可以简单的看作是一串数据链，举例说明：每个城市可以用一个6个基因因子的代码进行编码。

Los Angeles： GCTACG
Chicago： CTAGTA
Dallas： TCGTAC
Miami： CTACGG
New York: ATGCCG

而整条的路线可以用一条DNA代码表示的DNA链来代表 :如L.A -> Chicago -> Dallas -> Miami -> New York可以用GCTACGCTAGTATCGTACCTACGGATGCCG这条DNA代码链来表示。因为DNA具有双螺旋的互补结构，因此还可以用它 的互补结构来表示。

那么我们如何的计算所有的路线呢？合成短的单一的DNA就是常用的一种办法。因此为每个城市进行编码是很容易的，而DNA分子可以用在一种称之为“DNA 合成器”的机器产生，甚至可以通过向研究机构定购获得。路线可以通过以合适的顺序连接城市的代码中得出。例如：你可以将出发城市代码的后三个字母和到达城 市代码的前三个字母结合起来，这二者组成的代码就可以作为这二个城市之间的编码。如Miami (CTACGG)和NY (ATGCCG)之间的路线代码就可以将Miami代码的后三个字母（CGG）和NY代码的前三个字母（ATG）提取出来，得到CGGATG这个编码，而 通过互补计算得出的GCCTAC，就可以当成是Miami和NY二座城市之间路线的代码。

任意的路线可通过混合城市的代码得到，最后DNA链以会被一种叫“连接酶”的物质连接在一起，留下的大量的DNA链就代表着任意城市之间的任意的连接

我们可以认为城市之间的所有可能的路线都包含在这众多的DNA链里面，前面我们有提到DNA是一种高度紧密的数据结构。因此，计算得到的数据都包含在这体积微小物体里。

第二步：筛选出包含正确的出发和到达城市的路线

方法：通过“聚合酶链式反应”选择性的复制和增加从LA出发并抵达NY的DNA片断

在执行第一步工作之后，在试管里充满了各种不同长度的DNA，在这些DNA里面包含着城市之间的所有路线，当然也包括从从LA到NY的路线，那如何找出这 些路线了，这就需要借助一种技术我们称之为“聚合酶链式反应”（Polymerase Chain Reaction）简称为(PCR),这种技术可以让我们复制特定部分的DNA序列，PCR是借助一种称之为聚合酶的物质进行复制并且是一种能够反复循环 发生作用的连锁反应。聚合酶可以从单个DNA链的特定的位置开始复制，这个位置我们称之为初始位置，聚合酶不断的复制我们所需要复制增加的那一部分的，因 此包含有有效路线的DNA的数量不断的增加。这些DNA呈指数级的增长。当试管中充满了包含正确路线并且成倍数形式存在的大量的DNA链时,聚合酶链式反 应将中止。

第三步：选择包含正确城市数目的路线

方法：通过其长度来挑选包含5个城市的DNA链。

如上面所述，在试管中充满了包含用DNA编码的从LA到NY的路线，而在这些路线之中，包含途经城市的数目也不相同。现在我们的任务是选出包含5座城市的 路线。要完成这个任务，我们需要使用一种叫作“凝胶电泳”的技术。这是一种广泛采用于溶解DNA的技术。这种技术的基本原理就是对DNA施加电场，迫使它 通过凝胶矩阵。在大多数情况下，DNA分子带有负电荷，如果施加一个电场，那么它就将被负电所吸引。然而DNA的电荷密度是恒定的，因此当DNA链需悬浮 在试管中时，长DNA和短DNA移动的速度是一样的，所以还需要使用到凝胶体矩阵，凝胶体是一种由许多的条缕状物质形成的网状的聚合体。而我们要做的就是 施加电场让不同长度的DNA链通过这种由许多条缕状物质交织在一起的“迷宫”。由于DNA链的长度各不相同，因此他们通过的速度也不同，（长度越长，通过 的速度越慢），我们在DNA通过的不同数量凝胶体之后，设定不同的级别，每个级别代表了一个特定长度的DNA链。接着我们就可以简单的裁剪出有用的 DNA，将特定长度的DNA隔离。

第四步：选择包含完整城市的路线。

方法：在筛选出的包含有五座城市的DNA链中，最终筛选出包括有五座特定城市的路线的DNA链。

包含有特定顺序的DNA可以通过一种称之为“亲和纯化”的技术从混合的DNA链中分离出来。它可以吸附于之互补的DNA链，这就像一个“磁珠”。可以吸引 与之磁性相反的铁条。这些吸附在“磁珠”上的DNA链而后通过互补作用重新的连接在一起。最后，包含有正确路线的DNA链就被吸附在“磁珠”上：

因此经过5次的亲和纯化（每次的都是用不同的互补DNA链）例如：第一次用L.A'（L.A'表示与L.A互补的DNA链）进行“亲和纯化”，就可以得到 包含L.A.编码的DNA链，第二次我们使用Dallas'进行“亲和纯化”，第三次是 Chicago'接着是Miami'，最后是NY'。在这个过程中，“亲和纯化”的次序并不是最重要的。如果一条的路线缺少了一座城市。那么它将会在“亲 和纯化”过程中被“过滤”出来。最后我们得到的就是那些从L.A出发，途经每座城市一次，并最终抵达NY的线路了。而这条路线就是我们努力要寻找的，如果 答案真的存在，，最终的结果就将在这一步揭晓。

解读答案

我们可以通过有一种简单的方法找到答案，即排列DNA链的次序。但是如果我们已经拥有了了城市编码的顺序，那么我们就可以采用一种称之为 “graduated PCR(分级聚合酶链式反应)的方法进行解读，我们使用PCR的方法利用与L.A路线相关的DNA“摹本”进行了一系列的放大。 ，同样也利用“摹本”对对应其他城市的DNA也进行了同样的操作。通过测量每个PCR产物的DNA长度我们可以组合出在这条线路中的每座城市，例如：我们 知道从L.A出发的线路有30个DNA因子那么长。因此如果一条以LA和Dallas为“摹本”的DNA在PCR后的有24个DNA因子的长度，那么我们 就可以知道Dallas是这条路线中的第四座城市。（24除以6），我们只需要留意在试管中剩余的DNA，它们就是以 LA, Chicago, Miami, Dallas, 和NY编码的DNA链。所以如果我们使用LA和Chicago, LA和Miami, LA和Dallas, 以及LA和NY，最终经过PCR反应后得到的DNA链的长度分别为12, 18, 24, 和30个遗传因子的长度。

补充说明：

Adleman的实验解决了“7座城市”的问题，当DNA计算并非完美无缺，复杂的“售货员旅行问题”并未因此而一劳永逸。随着城市数目的增加，问题的难 度仍然会呈指数级增加。对于Adleman的计算方法来说，困难不在于计算的时间上而是计算所需要的DNA的数量。在Adleman实验论文发表之后，有 不少人指出：以“售货员旅行问题”为例，如果城市的数目有200个，那么计算所需要的DNA的重量将会超过地球的重量！而另一个DNA计算面临的问题是错 误率。在计算中每个步骤实际上都包含的统计学上出错的概率，当然在次数较少的DNA复制中，一般情况下，我们可以在错误产生之前就得到正确的答案，可是在 进行多次操作之后，出错的概率会大大的增加。

总结：

目前的计算机已经解决了有13,509座城市的 “售货员旅游问题”，这个纪录是由3台Digital AlphaServer 4100s巨型机 (包含了12个处理单元，每个节点有32台的Pentium-II PC）创造的。 这个计算结果能力并不是仅仅依靠它强大的计算能力，更多的依靠了非常有效的分支算法而得到。而DNA计算机作为一种还很原始的计算技术，改进的余地十分的 巨大，而DNA计算机计算方法的改进，有一天将会创造出新的纪录，向大家证明他优于传统计算机的独特优势。

另一方面DNA计算机的“硬件”（或者应该称之为“湿件”）技术所依托的生物工程学正呈现出和目前的半导体工业一样惊人的发展势头。在不远的将来越来越多 的国家和大企业也纷纷的投入大量的资金来进行这方面的研究，不少公司也推出了他们自己的DNA芯片，而随着“人类基因组”工程的继续开展，DNA计算机这 项技术的发展也将因此而受益。未来的DNA计算机将朝着高速，自动化和小型化的方面发展。同时DNA计算机的应用前景也十分的乐观，或许我们不会使用它来 玩“雷神之锤”的游戏，或者网上冲浪——这些采用目前的电脑就可以很好的胜任。但我们可以用它来研究逻辑，编码解码，基因编程以及自动化，语言系统等等， 甚至发明出我们从未想象到的东西。