DNA计算：重构生命的算法

DNA的学名是脱氧核糖核酸，是一切生物细胞中都具有的遗传物质。在生物遗传中，生物机体的遗传信息编码在DNA分子上，并通过DNA的复制由亲代传递给子代。在后代的生长发育过程中，遗传信息由DNA转录给RNA，然后翻译成特异的蛋白质，以执行各种生命功能，使后代表现出与亲代相似的遗传性状。DNA是一种高分子化合物，组成它的基本单位是脱氧核苷酸，每一分子的脱氧核苷酸是由一分子磷酸、一分子脱氧核糖和一分子含氮碱基组成的（其中含氮碱基共有四种，分别为腺嘌呤（A）、鸟嘌呤（G）、胞嘧啶（C）和胸腺嘧啶（T））。这是DNA的化学组成。DNA的组成结构非常完美，它是由两条双向平行的脱氧核苷酸长链围绕一个共同的纤维轴旋转而成的（其内部是通过碱基配对形成的有规则的双螺旋结构，其中腺嘌呤（A）与胸腺嘧啶（T）配对，鸟嘌呤（G）与胞嘧啶（C）配对，组成DNA分子的碱基虽然有四种，但配对方式只有两种）。由于碱基对是可重复排列的，所以DNA分子具有多样性。

近年来，人们在研究生物遗传的同时，也发现DNA可以用于遗传学以外的其他领域，如信息科学领域。1994年，Adleman等科学家实现了世界上首次DNA计算，解决了一个7节点有向汉密尔顿回路问题。这一结果表明利用DNA计算特定问题是可行的，此算法的新颖性并不仅仅在于算法和计算的并行性，而在于此方法是完全通过生物技术实现的，也体现了DNA这种物质作为计算媒体潜在的并行性。此后，有关DNA计算的研究不断深入，所获得的计算能力也不断增强。1995年，Lipton在Adleman的基础上解决了更有趣的NP完全问题。1997年，Ouyang等人又利用DNA计算解决了另一个NP完全问题（图的最大团问题）。2000年，美国威斯康辛（Wisconson）大学的Liu等人介绍了一种基于表面计算的SAT问题的解决方法。到了2002年，Adleman用DNA计算机解决了一个有20个变量、24个子句、100万种可能的3-SAT问题，这是一个NPC问题。(www.xing528.com)

DNA算法解决计算问题的基本思想是：利用DNA特殊的双螺旋结构和碱基互补配对原则，对计算问题进行编码，把要运算的对象映射成DNA分子链，在DNA溶液的试管里，在生物酶的作用下，生成各种数据池；然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程；最后利用分子生物技术（如聚合酶链反应（PCR）、聚合重叠放大技术（POA）、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等分子生物学技术）获得最终运算结果。简言之：以DNA碱基序列作为信息编码的载体，在试管内控制酶的作用下进行DNA的序列反应来实现运算。以反应前的DNA序列作为输入数据，反应后的DNA序列作为运算结果。DNA具有超大规模并行性、超高容量的存储密度以及超低的能量消耗，非常适用于信息领域。利用DNA，人们有可能生产出新型的超级计算机，它们具有前所未有的超大规模并行计算能力，其并行性远超过现有的电子计算机。这将给人们带来惊人的计算能力，引发一场新的信息革命。