什么叫生物计算机？
生物计算机：试管里的奇迹
周游
编者按:本文是2004年7月26日出版的《计算机世界》周报第28期产品与技术版 “新一代计算机”系列专题文章之一，另两篇文章分别为“纳米计算机：承上启下”、“量子计算机：颠覆传统”
1994年， Leonard M。 Adleman用一种不平常的技术解决了一个平常的计算问题。这是个一个人只用一会儿时间，普通桌面计算机只需一眨眼功夫，就可以解答的问题。可是，Adleman用了7天才找到答案。那么，这项工作为什么不同寻常呢？因为他利用DNA解决了这个问题。 这是一次里程碑式的分子级计算演示。
Adleman求解的问题是一个著名问题。它的正式名字叫定向哈密尔...全部
生物计算机：试管里的奇迹
周游
编者按:本文是2004年7月26日出版的《计算机世界》周报第28期产品与技术版 “新一代计算机”系列专题文章之一，另两篇文章分别为“纳米计算机：承上启下”、“量子计算机：颠覆传统”
1994年， Leonard M。
Adleman用一种不平常的技术解决了一个平常的计算问题。这是个一个人只用一会儿时间，普通桌面计算机只需一眨眼功夫，就可以解答的问题。可是，Adleman用了7天才找到答案。那么，这项工作为什么不同寻常呢？因为他利用DNA解决了这个问题。
这是一次里程碑式的分子级计算演示。
Adleman求解的问题是一个著名问题。它的正式名字叫定向哈密尔顿路径（HP）问题，但人们更多地称它为“货郎担问题”。在Adleman版的货郎担问题（TSP）中，一位货郎试图找到一条穿越几个城市的道路，而且他只到每个城市一次。
随着城市数量的增加，问题变得越来越困难，直至问题的答案无法用解析分析法求解，必须采用蛮力搜索法。城市数量巨大的TSP的计算成本会变得很高，以致在最新型的超级计算机上求解都不切实际。Adleman的演示只涉及7个城市，因此答案甚至可以用肉眼观察就轻松地得到。
但是，他的工作却由于多种理由而意义重大。
它显示了利用DNA解决一类难于或不可能利用传统计算方法解决的问题的可能性；它是分子级计算的例子，而半导体行业可能永远达不到分子级水平；它展示了DNA作为一种数据结构的独特方面；它证明了DNA计算可以以大规模并行方式运行。
DNA：一种独特的数据结构
人们在过去40年里积累了大量有关DNA分子生物学的信息。因此，为避免被DNA的生物化学和生物学细节搞得焦头烂额，我们将只探讨与DNA计算有关的信息。
DNA的数据密度大得惊人。
正像一串二进制数据用“0”和“1”编码一样，一串DNA用4个用字母A、T、C和G代表的脱氧核糖核酸基盐编码。在DNA分子上的脱氧核糖核酸基盐（也叫核苷酸）之间的间隙为0。35纳米，从而使DNA具有了每英寸近18 Mbits的不同寻常的数据密度。
在两维空间中，如果假设每平方纳米有一个核苷酸的话，数据密度超过每平方英寸1百万Gbits。与数据密度约为每平方英寸7 Gbits的典型高性能硬盘相比，DNA数据密度超过它10万倍以上。
DNA的另一个重要属性是其双链性质。
核苷酸A、T、C和G可以粘合在一起，形成核苷酸对。因此每个DNA序列都具有一个天然的补序列。例如，如果序列S为ATTACGTCG，那么其补序列S'为TAATGCAGC。S和S'将混合在一起（或杂交）形成双链DNA。
这种互补性使DNA成为一种独特的计算结构，可以以多种方式加以利用。其中的一个例子就是纠错。由于种种因素，DNA中会出现错误。DNA酶偶尔也会犯错误，在不应该断开的地方断开，或在本该插入G的地方插入T。
太阳发出的紫外线和热量也会损坏DNA。如果错误发生在双链DNA的某一段上，修复酶可以利用补序列串作为参考，恢复正确的DNA序列。从这个意义上说，双链DNA类似于一台RAID 1阵列，即第二块硬盘是第一块硬盘的镜像，如果第一块硬盘发生错误，数据可以从第二块硬盘中恢复。
在生物系统中，这种纠错能力意味着错误率相当低。例如，在DNA复制时，每复制10^9个核苷酸发生一次错误，换句话说，错误率为10^-9（相比之下，采用Reed-Solomon纠错时，硬盘的读错误率只有10^-13）。
并行操作
在细胞中，DNA由不同的酶以生物化学方式进行修改。酶是微小的蛋白质，它按照大自然的设计，读取和处理DNA。这类在分子级上处理DNA的“运行的”蛋白质的种类和数量都非常多。例如，既有切断DNA的酶，又有将它们再粘在一起的酶。
一些酶发挥复印机的作用，另一些酶承担修理工的职责。
分子生物学、生物化学和生物工艺学开发出了使我们能够在试管中完成这些细胞功能的许多功能的技术。正是这种细胞组织以及一些合成化学品，构成了一套可用于计算的操作。
CPU有一套加、移位、逻辑算子等基本组成的操作集合，这些操作使CPU可以执行最复杂的计算。正像CPU一样，DNA也具有切断、复制、粘贴、修理以及其它许多操作。
需要注意的是，在试管中，酶并不是顺序地工作，一次处理一个DNA，而是酶的很多副本同时处理许多的DNA分子。
这正是DNA计算的威力所在：可以以大规模并行方式运行。
与硅计算机的比较
DNA凭借其独特的数据结构和执行很多并行操作的能力，使人们能够从不同的角度研究计算问题。基于晶体管的计算机通常以顺序方式处理操作。
当然，现在出现了多处理器计算机，而且现代CPU具有一定的并行处理能力，但一般而言，在基本的von Neumann架构计算机中，指令是顺序执行的。一台von Neumann机器(所有的现代CPU都属于von Neumann机器)基本上一次又一次地重复同样的“读取和执行周期”，它从主内存中读取指令和相应的数据，然后再执行指令。
它非常非常快地、许多许多次地顺序执行这些操作。而DNA计算机不是von Neuman机器，它是随机的机器，它在解决不同类型的问题时，以不同于普通计算机的方式进行计算。
一般来说，提高硅计算机的性能，意味着更快的时钟速度（和更宽的数据通道），此时强调的是CPU速度，而不是内存的大小。
然而，对于DNA计算来说，其力量来自内存容量和并行处理。假如被迫执行顺序操作的话，DNA将失去它的吸引力。以DNA的读/写速度为例。在细菌中，DNA可以以每秒大约500对核苷酸的速度进行复制。
从生物学角度看，速度相当快（比人类细胞快9倍），而且考虑到低错误率，这是个很了不起的成就。但是，这只是1000 bps，与一般硬盘的数据吞吐量相比，等于是蜗牛爬。
首先，复制酶甚至在完成复制第一个DNA串之前，就可以开始复制第二个DNA串。
因此，数据速度猛增到了2000 bps。DNA串的数量指数级增加(n次迭代后数量为2^n)。每增加一串DNA，数据速率就增加1000 bps。因此在10次迭代后，DNA的复制速度约为1M bps，30次迭代后，增加到1000G bps。
这超过了最快速硬盘的持续数据速率。
现在让我们来比较一下用传统计算机和DNA计算机解决非平凡的货郎担问题(城市数量> 10)的情况。在使用传统的冯·诺伊曼计算机时，一种原始的方法是建立搜索树，然后顺序测量每一个完整的分支，并保留最短的路线。
这种方法可利用更好的搜索算法加以改进。一种肯定不会使用的方法是首先生成所有可能的路线，然后搜索整个路线表。为什么呢？因此对于20个城市的货郎担问题，整个路线表理论上将占用4千5百万GB的内存！对于一台运算速度100 MIPS的计算机，仅生成所有的路径就需要两年时间(假设一条指令周期生成一条路线中的一个城市)。
然而在使用DNA计算机时，这种方式却变得可行了！10^15对于生物化学来说，是很小的数量。此外，路线也不再顺序搜索了。操作都是以并行方式完成的。
Adleman的试验
让我们利用Adleman演示的DNA方式来解决我们自己的定向哈密尔顿路线问题。
为叙述方便起见，我们对例子进行了简化。
假设你住在洛杉矶，需要访问4个城市：芝加哥、达拉斯、迈阿密和纽约，其中纽约是最后的目的地。你所选择的航空公司的转接班机限制了你能选择的路由(例如，有从洛杉矶到芝加哥的航班，但没有迈阿密到芝加哥的飞机)。
如果你希望只访问每个城市一次，该怎么走呢？
图1
Adleman的步骤是：
生成所有可能的路由；
选择从起点城市开始到终点城市结束的路线；
选择具有正确城市数量的路线；
选择包含每个城市只出现一次的路线。
以上所有步骤都可以利用标准的分子生物技术完成。
第一步：生成所有可能的路由
策略：用短DNA序列为城市名编码。通过连接存在路由的不同城市序列，对路线编码。DNA可以当做数据串对处理。
例如，每个城市可以用六个核苷酸成组的“字”来代表：
洛杉矶：GCTACG
芝加哥：CTAGTA
达拉斯：TCGTAC
迈阿密：CTACGG
纽约： ATGCCG
整条路线的编码可通过将这些代表具体城市的DNA序列串起来完成。
例如，从洛杉矶-->芝加哥-->达拉斯-->迈阿密-->纽约的路线表示为GCTACGCTAGTATCGTACCTACGGATGCCG，也可以等价地用这条序列的补序列形式表示。
那么，我们怎样生成这条序列呢？人工合成短单链DNA现在是一种常规方法，因此，城市名编码十分简单。
一种叫做DNA合成器的设备可以制作这些分子，也可以从第三方定制。然后，按正确的次序将城市名编码连接在一起来生成路线。在完成这项工作时，我们可以利用DNA与其补序列杂交的事实。例如，我们可以通过对起始城市的后一半字母(后三个字母)和到达城市的前一半字母(前三个字母)的补序列进行编码，对城市间路由编码。
例如，迈阿密(CTACGG)与纽约(ATGCCG)之间的路由可以用迈阿密编码的后一半(CGG)和纽约编码的前一半(ATG)组成，即CGGATG。取补后，得到GCCTAC。GCCTAC不仅惟一表示了从迈阿密到纽约的路由，而且还通过把代表迈阿密和纽约的DNA与CGG和ATG杂交，连接将它们连接在一起。
(见图 g)
随机路线可以通过将城市编码与路线编码混合起来生成。最后，这些DNA串可以用一种叫做连接酶的酶连接在一起。这时我们得到的是代表示具有任意数量的城市和任意路由集合的路线的DNA串。
(见图 g)
利用大量的DNA编码(比如，10^13个每个城市和城市间每条路由的副本)，我们肯定得到所有可能的组合,一个正确的组合就包括在这些组合中。
第二步：选择从起点城市开始到终点城市结束的路线
策略：利用聚合酶链反应，有选择地只复制和放大开始于洛杉矶并结束于纽约的DNA部分。
完成第一步后，我们得到了一只装满代表路线编码的各种长度的DNA的试管。我们需要的是从洛杉矶到纽约的路线。为此，我们可以使用一种叫做聚合酶链反应(PCR)的技术。PCR使我们可以生产出某一DNA序列的大量副本。
聚合酶将复制开始于引分子(primer)位置的一段单链DNA。引分子是一小截DNA，与我们感兴趣的那段DNA的一端互补。通过选择位于我们希望放大的那段DNA两侧的引分子，聚合酶优先放大这些引分子间的DNA，将包含这一序列的DNA的数量增加一倍。
经过多次PCR后，DNA被放大了指数级倍。在有选择地放大我们感兴趣的路线时，我们使用与洛杉矶和纽约互补的引分子。在PCR后，我们最后得到的是一只装满不同长度、代表着从洛杉矶起到纽约止的路线编码的双链DNA的试管。
第三步：选择具有正确城市数量的路线
策略：根据长度分类DNA，选择长度对应5个城市的DNA。
经过第二步后，试管中路线DNA编码尽管代表着始于洛杉矶止于纽约的路线，但经过城市的数量却不同。
我们现在希望选择只经过五个城市的路线。为此，我们可利用一种叫做凝胶电泳的技术。凝胶电泳法是一种用于解决DNA长度的通用过程。
凝胶电泳法的基本原理是利用电场，迫使DNA经过一个凝胶矩阵。在多数条件下，DNA为负电荷分子，因此如果放置在电场中，将被吸引到正电位上。
但是由于DNA的电荷密度恒定不变，悬浮在液体中的长DNA段与短DNA段运动速度一样快。这就是为什么要使用凝胶矩阵的原因。凝胶由形成细丝网的聚合体构成。DNA被迫穿过细丝间的微小空间，细丝降低了DNA的移动速度，速度降低多少取决于DNA的长度。
最后得到许多DNA带子，每个带子对应于某个长度。然后，我们可以切掉我们感兴趣的带子，分离出特定长度的DNA。由于我们知道每个城市用6对DNA编码，因此，掌握路线的长度就使我们掌握了城市的数量。
在本例中，我们将分离具有30对核苷酸长度(5个城市X 6对核苷酸)的DNA。（ g）
第四步：选择包含每个城市只出现一次的路线
策略：按城市连续过滤DNA分子，每次一个城市。由于我们处理的DNA包括五个城市，我们将得到每个城市只编码一次的DNA序列。
我们可以利用一项叫做亲和纯化的技术，从DNA样本中纯化出包含特定序列的DNA。我们可以通过将DNA序列的补序列连接到一种基质上(如磁珠)，完成这项工作。磁珠然后与DNA混在一起。这时，包含我们所需要序列的DNA将与磁珠上的补序列杂交。
然后，这些磁珠被取出，分离出DNA。
我们进行5次亲和纯化，每次使用一个不同的城市补序列。例如，第一次时，使用带有洛杉矶补序列的磁珠，来分离包含洛杉矶编码的DNA序列。如此反复5次，我们就得到了从洛杉矶开始、只访问每个城市一次、结束于纽约的所有路线。
读取答案
一种找到结果的可能方法是对DNA序列排序。不过，由于我们已经有了城市编码的序列，因此我们可以使用一种叫做渐变PCR的方法。这时我们利用对应于洛杉矶的引分子，接着使用对应于每个城市的不同引分子，进行一系列PCR放大。
通过测量每个PCR结果得到的不同DNA长度，我们可以将路线中的最终城市序列拼凑出来。例如，我们知道DNA路线开始于洛杉矶，具有30对核苷酸长度，因此如果洛杉矶和达拉斯引分子的PCR结果为24对核苷酸长，可知达拉斯是路线中的第四个城市(24被6除)。
最后，如果我们在DNA处理中十分仔细的话，试管中留下的惟一DNA应当中代表洛杉矶、芝加哥、迈阿密、达拉斯和纽约路线编码的DNA。因此，如果使用的引分子顺序是洛杉矶与芝加哥、洛杉矶与迈阿密、洛杉矶与达拉斯和洛杉矶与纽约，那么我们将得到长度为12、18、24和30对核苷酸的PCR结果。
几点说明
Adleman的试验解决了7个城市的问题，但是有两大缺点阻止扩大其计算的规模。当使用一种不同的解法时，货郎担问题的复杂度并没有消失：复杂度仍以指数级增长。就Adleman的方法而言，指数级增长的东西不是计算时间，而是DNA的数量。
不幸的是，这给可以求解的城市数量带来了一些硬性限制。在Adleman的文章发表后，很多人指出使用他的方法求解200个城市的HP问题，需要的DNA的重量将比地球还要重。
限制Adleman方法的另一个因素是每次操作的错误率。
由于这些操作并不是确定性而是随机驱动的(我们是在做化学试验)，每一步都包含统计错误，因而限制了在产生错误的概率超过产生正确结果的概率前我们所能连续迭代的次数。例如，1%的错误率可进行10次迭代，这时的错误率小于10%，而在进行100次迭代后，错误率增长为63%。
“试管”的未来
那么DNA能被用于解决城市数量超过传统计算机能力的货郎担问题吗？鉴于目前传统计算机的记录是13,509个城市，这肯定不能用上述过程求解。传统计算机求解这个问题只用了3个月时间，当时动用了3台Digital AlphaServer 4100s(共有12个处理器)和一个由32台Pentium-II PC组成的群集。
此问题的求解不是由于计算能力，而是由于人们使用了一些效率非常高的分支规则。Adleman的第一次DNA计算演示采用了一种不太高明的算法，但是随着DNA计算形式的不断细化，新算法也许有一天将使DNA超过传统计算机，创造新记录。
在“硬件方面”(或者应当说“湿件”)，生物技术的改进正在以类似于半导体行业的进步速度发展。以DNA排序为例，曾需要一位研究生用5年时间完成的工作，现在只需要一天。鉴于政府投入到基因研发大量资金和来自利润丰厚的制药和医疗相关市场的潜在巨额回报，这种情况并不让人感到吃惊。
人类基因组项目正在排序技术方面迅速取得创新。DNA处理的未来是速度、自动化和小型化。
不难想像，总有一天我们将拥有制造利用DNA或DNA式的生物高聚物作为计算基础的小型集成桌面机的工具和人材以及各种设计酶(designer enzymes)。
也许DNA计算机不会被用于玩“Quake IV”或上网冲浪(这些事情是传统机所善长的)，而肯定可以被用于研究逻辑、加密、基因编程与算法、自动控制、语言系统以及很多现在还没有发明出来的其它有趣的事。
。收起
