下载掌阅APP，畅读海量书库
立即打开
从 1994 年至今，DNA 计算的研究已有三十年的历史。这些年来，DNA计算主要用于求解NP完全问题、研发DNA计算机。另外，从DNA计算的研究过程中衍生出来的DNA分子自组装技术，促进了DNA纳米器件领域的研究，为用于肿瘤诊断与药物递呈的纳米机器人的研发提供了条件。
在生物计算研究领域内，DNA 计算异军突起的主要原因是：目前对DNA分子及相关生化技术的操控比RNA和蛋白质容易实现，且DNA计算具有如下四大优势 [4-8] 。
（1）并行性高。DNA计算中的“数据”是DNA分子，数据间的“运算”是双链 DNA（double-stranded DNA，dsDNA）的解链、单链DNA（single-stranded DNA，ssDNA）的连接和切割等基本运算，这些基本运算可并行处理。特别是DNA分子的海量性，使得DNA计算的并行性极高。
（2）信息存储量巨大。由于组成DNA分子的4个碱基（A、C、G、T，详见3.1.1小节）的平均长度仅为0.34nm，按每条DNA序列有1000bp
计算，长度也仅有340nm。可以粗略地估计，1m
3
DNA可存储1万亿亿个二进制数据，远超当前全球所有电子计算机的总存储量。
（3）能耗极低。粗略估计，DNA计算求解一个问题所消耗的能量仅为一台电子计算机完成同样计算所消耗能量的十亿分之一。
（4）算子丰富。DNA计算中的算子众多，如dsDNA分子的解链运算、两个ssDNA之间的连接运算、将一个DNA分子切割成两个或多个的切割运算、DNA链的复制运算（聚合酶）等。此外，还包括已有生化仪器的运算，如PCR扩增运算等。
DNA计算的上述优势吸引了不同领域（如生物工程、计算机科学、数学、物理、化学、控制科学等）的许多研究人员开展相关研究。
DNA 计算的研究目标是研发出实用的 DNA 计算机。研究进展显示，DNA计算距实用化越来越近。例如，在搜索一个赋权图中两个顶点间的所有路径时，只需要将这两个顶点所代表的DNA链作为引物，实施一次PCR扩增运算，即可获得所有路径。又如，伦纳德·阿德曼（Leonard M. Adleman）组在2002年求解可满足性 （Satisfiability，SAT） 问题时，搜索次数是2 20 次 [10] 。文献[11]建立了求解图顶点着色问题的DNA计算模型，给出了61个顶点3-着色的所有解，搜索次数已达3 59 次，这是截至本书成稿之日生物计算中搜索规模最大的实例，此例也证明了DNA计算的巨大潜力。
NP完全问题有很多，但斯蒂芬·阿瑟·库克（Stephen Arthur Cook）在1971年证明了所有NP完全问题在多项式时间内均可相互归约（Cook凭此项证明于1982年获得图灵奖）。这就意味着，所有的NP完全问题均可转化为图着色这个典型的NP完全问题。而DNA计算在求解图着色问题的进展已凸显出它在求解NP完全问题上的优势，为求解NP完全问题提供了新思路。NP完全问题的每一点进步，都会给当今社会发展带来不可估量的贡献。例如，蛋白质结构预测、列车调度、航迹规划等NP完全问题有望取得突破，基础科学领域（特别是数学、运筹学与理论计算机科学）中的一些难题有望得到解决。
按模型特点的不同，DNA计算的研究可分如下4个方向。
（1）枚举型DNA计算模型（1994—2005年）。DNA计算处于起步阶段，许多工作处于探索期。该方向主要针对一些困难的NP完全问题，研究如何基于DNA分子的特性构建计算模型，怎样对DNA链进行编码；如何进行生化实验，如何实施解的检测[怎样把问题的解从生物化学反应（简称生化反应）池中找出来]等。因此，在这段时间，绝大多数研究人员误以为DNA计算可利用DNA分子的微小性，以空间换时间。枚举型DNA计算模型将在第6章介绍。
（2）非枚举型图顶点着色DNA计算模型（始于2006年）。很容易算出，若用枚举型DNA计算模型求解200个顶点的4-着色问题，所需的DNA分子质量比地球质量还大。因此，DNA计算必须走非枚举型之路。作者团队首先提出非枚举型DNA计算模型，相关研究将在第7章详细介绍。
（3）并行型图顶点着色DNA计算模型（简称并行DNA计算模型）（始于2007年）。在非枚举型DNA计算模型的基础上，作者团队于2007年提出并行DNA计算模型。该模型的创新点在于并行性：将一个给定的图划分为若干个子图，并求出每个子图的着色；在求解每个子图着色的过程中，给出一种并行PCR连续删除非可行解（简称非解）技术；最后，将所有子图解连接起来，采用类似删除子图的非可行解法，删除整图中其余非可行解。并行DNA计算模型将在第8章详细介绍。
（4）探针机（始于2002年）。在建立图顶点着色DNA计算模型时，作者团队发现了一种仅通过一次运算就可获得一个图的全部 k -色图的方法，并由此提出了一种全并行的新型DNA计算模型——探针机。探针机相关研究及应用将在第9章简要介绍。
[1] FEYMAN R P. There’s plenty of room at the bottom[J]. NY: Minaturization, 1961. 282-296.
[2] BENNETT C H. On constructing a molecular computer[J]. IBM Journal of Research and Development, 1973, 17: 525-532.
[3] ADLEMAN L M. Molecular computation of solutions to combinatorial problems[J]. Science, 1994, 266(5187): 1021-1024.
[4] 许进, 张雷. DNA 计算机原理，进展及难点 (Ⅰ)：生物计算系统及其在图论中的应用[J]. 计算机学报, 2003, 26(1): 1-11.
[5] 许进, 黄布毅. DNA 计算机：原理，进展及难点 (Ⅱ)：计算机“数据库”的形成——DNA 分子的合成问题[J]. 计算机学报, 2005, 28(10): 1583-1591.
[6] 许进, 张社民, 范月科, 等. DNA 计算机原理、进展及难点(Ⅲ)：分子生物计算中的数据结构与特性[J]. 计算机学报, 2007, 30(6), 869-880.
[7] 许进, 谭钢军, 范月科, 等. DNA 计算机：原理、进展及难点(Ⅳ)：论DNA计算模型[J]. 计算机学报, 2007, 30(6): 881-893.
[8] 许进，李菲. DNA计算机原理、进展及难点(Ⅴ)：DNA分子的固定技术[J]. 计算机学报, 2009, 2283-2299.
[9] XU J. Probe machine[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(7): 1405-1416.
[10] BRAICH R S, CHELYAPOV N, JOHNSON C, et al. Solution of a 20-variable 3-SAT problem on a DNA computer[J]. Science, 2002, 296(5567): 499-502.
[11] XU J, QIANG X, ZHANG K, et al. A DNA computing model for the graph vertex coloring problem based on a probe graph[J]. Engineering, 2018, 4(1): 61-77.