DNA分子之所以能够形成双螺旋结构，是由于它含有四种不同的碱基——腺嘌呤(A)、鸟嘌呤(G)、胸腺嘧啶(T)和胞嘧啶(C)，通过碱基A与T、G与C之间的氢键结合才得以相互配对形成双链。正是由于DNA分子中包含有数目巨大的四种碱基，使得人们看到了DNA分子的巨大编码潜力。而利用DNA分子的这种巨量信息编码能力和并行操作能力开发DNA计算机就成了科学家们的一个梦想。在20世纪的最后十年里，DNA计算机终于千呼万唤地浮出了水面。

试管里的DNA计算机

用计算机去求解一个问题，首先要找到一个适合计算机运算的算法，但如果这个算法要让一台高速计算机运算上一千年才能得出结果的话，则这样的算法对于解决实际问题是无用的。而这样的例子在现实世界中随处可见，比如：用一台每0.000001秒执行一次基本运算的电子计算机计算3ⁿ这个算式，如果n=10，则需0.059秒即可解决问题，但如果n=30，则需6.5年，而当n=50时，则需2×10¹⁰年，竟超过了自大爆炸以来的宇宙年龄。所以，能够在一个多项式时间内算出结果的算法称为有效算法，而要用指数时间(如一个算法处理长度为n的输人数据时，需要2ⁿ、3ⁿ、n！步运算)才能算出结果的算法称为非有效算法。

假定有不在同一直线上的10个城市，相互之间都有直达航线相连，如果有一个旅行推销员要从一个城市出发走遍所有的这10个城市，而每个城市只经过一次，那么，如何旅行才能使总的旅程最短呢？这个问题就是著名的旅行推销员问题。

1994年，美国南加州大学的艾德曼(Adlemen)利用试管中的DNA计算了7个城市13条航线的旅行推销员问题。

首先，艾德曼分别用20个碱基长的不同的DNA序列对7个城市进行了编码。比如，第二个城市的编码(O₂)为TATCGGATCGGTATATCCGA；第三个城市的编码(O₃)为GCTATTCGAGCTTAAAGCTA。同时，合成这7个城市编码序列的互补序列，如第二个城市编码序列的互补序(Õ₂)为ATAGCCTAGCCATATAGGCT。然后，对13条航线进行编码，以城市2与城市3之间的航线O_2-3为例，编码的规则是O₂的后十个碱基作为O_2-3的前十个碱基，O₃的前十个碱基作为O_2-3的后十个碱基，即O_2-3为GTATATCCGAGCTATTCGAG。最后，用7个城市的互补DNA(Õ₁、Õ₂、Õ₃、Õ₄、Õ₅、Õ₆、Õ₇)与13条航线的不同编码DNA序列(O_1-j)在试管中进行混合。举例来说，由于Õ₃上的碱基正好是O_2-3上后十个碱基和O_3-4上前十个碱基的互补碱基，通过A-T、C-G的配对法则，Õ₃就可以像“夹板”一样将O_2-3和O_3-4连接在一起。同理，利用Õ_i为“夹板”使对应的Õ_i-j分别连接，就可以产生大量的随机连接通路。

第二步，利用O₁和Õ₇作为引物，对这些随机产生的DNA序列进行聚合酶链式反应。这样，只有那些从O₁开始到O₇为止的通路DNA序列可以被大量扩增，而其它通路因不满足扩增条件而不被扩增。

第三步，将扩增后的DNA序列进行电泳分离，选取分子质量为140个碱基的双链DNA。因为每个城市都是由20个碱基的DNA编码，连通7个城市的编码DNA应为20×7=140个碱基，所以，选取的140个碱基的DNA序列就是可以连通7个城市通路的DNA序列。

第四步，将选出的140个碱基的双链DNA序列加热变性拆分成单链，再用含有Õ₂序列的磁珠与其互补结合，选取结合了Õ₂序列的单链DNA序列，这样的序列就是由城市1连通城市2的通路。将选取的序列退火复性后，再加热变性，分别用含有Õ₃、Õ₄、Õ₅、Õ₆的磁珠进行分离提取。最后能与Õ₆结合的序列就是从城市1起始，途径城市2、3、4、5、6，终止于城市7的通路DNA序列。

第五步，将上述分离的DNA序列再次进行聚合酶链式反应，扩增的DNA序列经过电泳分离，最终得到的序列就是7个城市13条航线的旅行推销员问题的正确答案。

艾德曼的研究使得DNA计算机取得了突破性的进展。第二年，李普顿(Lipton)又将艾德曼的方法推广到求解布尔代数式变量取值的可满足性问题(SAT问题)，并证明任何NP完全性问题都可以由DNA计算途径得到解决，从此，DNA计算机的研究在不到十年的时间里得到了飞速的发展。

芯片上的DNA计算机

DNA芯片是20世纪90年代中期随着人类基因组计划而发展起来的，其实质就是在固相载片(如玻璃、硅片、塑料片)上高密度地连接不同的DNA单链，然后，在适当的条件下与待测的单链DNA按A-T、C-G配对法则进行互补杂交。杂交后的DNA芯片用激光共聚焦显微镜等检测仪器进行检测，由于待测DNA在杂交前已经用荧光物质进行了标记，所以，在检测条件下，芯片上只有杂交了待测DNA的位置上才能检测出荧光的存在，根据荧光强度的不同及有无就可进行待测DNA的分析。因为DNA芯片的可寻址性及对编码信息的高通量并行处理能力，使其在DNA计算领域有着广泛的应用前景。

在布尔代数中，变量的取值只能为0或1，其运算有“与”(∧)、“或”(∨)、“非”三种。比如：当布尔变量x=0、y=1时，x与y的“与”运算x∧y=0∧1=0；而x与y的“或”运算x∨y=0∨1=1；x的“非”运算x¯=1，y的“非”运算y¯=0。

2000年，刘(Liu)等在芯片上解决了布尔代数式中变量取值的可满足性问题。该问题如下所示：F=(w∨x∨y)∧(w∨y¯∨z)∧(x¯∨y)∧(w¯∨y¯)；，式中w、x、y、z均为布尔变量，式中共4个子句(w∨x∨y)、(w∨y¯∨z)、(x¯∨y)和(w¯∨y¯)，子句中的变量间均为“或”运算关系，4个子句之间又呈“与”运算关系。现在所要求的问题是当w、x、y、z取何值时，F=1？从F的表达式中可以看出只有当4个子句的“或”运算结果都等于1时，F才能等于1。由于每个变量都有0、1两个可能的取值，因此，4个变量共有2⁴=16种可能的取值组合。该问题的实质就是从这16种可能的取值组合中找出能满足F=1的组合来。

刘等首先用8个碱基的DNA序列对这16种可能的取值进行编码，比如：w=0、x=0、y=0、z=0即(0000)这一组合，可用S₁=CAACCCAA来编码。然后，将这16种编码DNA序列随机连接在固相载片上构成DNA芯片。同时，分别合成与这16种编码序列互补的DNA序列，如：S₁的互补序列S₁¯=GTTGGGTT。

第二步，用能使第一子句等于1的互补DNA序列与芯片上的编码序列进行互补杂交形成双链DNA序列。而芯片上未杂交的编码序列仍为单链。

第三步，用外切核酸酶切除芯片上未杂交的单链编码序列。然后，再加热使芯片上的杂交双链重新恢复原来的单链状态。

第四步，重复第二、三两个步骤，分别用能使第二、三、四子句等于1的互补DNA序列与芯片，上剩余的单链编码序列进行杂交，并除去未杂交的编码单链。最后，芯片上只剩下S₄(0011)、S₈(0111)、S₉(1000)和S₁₀(1001)4个编码序列即为问题的答案。如：S₄(0011)(0011)为w=0、x=0、y=1、z=1，代入F的表达式F=(0∨0∨1) ∧(0∨0∨1) ∧(1∨1) ∧(1∨0)=1∧1∧1∧1=1，满足要求。

在线性约束条件下，求目标函数的最优整数解的问题称为整数规划问题，其中变量的取值仅限于0或1的整数规划问题又称为0-1规划问题。采用穷举法，找出变量取值为0或1的所有不同组合，比较目标函数以求得最优解是求解0-1规划问题的最基本算法。但这些变量的组合却有2ⁿ种，所以，这也是一个典型的指数时间问题。

最近，华中科技大学的张凤月等人给出了一个利用DNA芯片求解0-1规划问题的DNA计算模型。作为一个例子是在约束条件x+z≤1；x+y+z≥2；y+z≤1；x、y、z=0、1下，求目标函数u=2x+y+3z最小值的问题。他们首先是用8个碱基长的DNA序列对变量x、y、z分别进行编码。同时合成这三种编码序列的互补序列，之后，再将x、y、z的互补序列分为两组，其中一组用荧光物质进行标记。

第二步，将x、y、z的编码序列按一定的排列方式连接到固相载片上，x、y、z共有2ⁿ=2³=8种不同的组合方式，以此构成DNA芯片。

第三步，将荧光标记和非标记的互补序列在合适的条件下与DNA芯片杂交。

第四步，检测杂交结果，芯片上凡是有荧光的位置都是杂交了荧光标记序列的双链DNA，表示该位置对应的变量取值为1，而无荧光的位置都是杂交了非荧光标记序列的双链DNA，表示该位置对应的变量为0。对于约束条件x+z≤1，x、y、z的取值只能是(110)、(100)、(011)、(010)、(001)和(000)，即x和z不能同时取值为1。同理，对约束条件2、3进行分析，可知满足要求的解只能是(110)，对应的目标函数最小值为3。

从上述两个例子可以看出，较之试管里的DNA计算机，芯片上的DNA计算机具有可高密度集成编码序列及可实现自动化操作等优点。对于100个城市的旅行推销员问题来说，如果每一条通路都要用一个分子来编码的话，则至少需要2¹⁰⁰即约等于10³⁰个分子，而1克水中的水分子数量最多不超过10²³个，因此，要求出100个城市的旅行推销员问题至少需要10⁷克即10吨的水，这是极不方便的事情，而且操作复杂、出错率高。所以，芯片上的DNA计算机才是DNA计算机走向实用的发展方向。那么，DNA计算机真的会成为明日的计算机吗？