博文
造一台 DNA 计算机应该注意什么——关于计算的那些事（二）
|
注：本文不同章节之间相对独立，读者们可根据个人喜好选择性阅读：
0. 引子；
1. DNA 简介（中学生物知识回顾）；
2. DNA 和计算科学的关系；
3. 用 DNA 计算解决一个实际问题（数学部分）；
4. 总结。
两周前，小编一时心血来潮，突然想用光子制造出一台计算机（《造一台光子计算机应该注意什么》），以免电脑过热之虞。心潮涌动后自当风平浪静，此时回头略一思忖，便不难发现此中诸多困难之处：
1. 光子器件设计繁琐，最简单的单光纤共振仪就令人头大；
2. 就算器件设计简单，材料也不一定好找；
3. 就算材料好找，它可能会占用过多空间；
4. 就算材料小巧玲珑，设计出的计算机并行计算性能依然有限；
5. ……
那么有没有其他种类的计算机能解决上面这些问题呢？小编曾苦思良久，也没有点子。不料在近日的睡梦中偶得灵感，醒来后将梦中所感记录下来，这便写成了本文的卷首诗《光、分子与计算机》。
这和新的计算机设计思路有什么关系呢？从这首诗中读者们不难感受到，光和分子是两种完全不同的概念——光是视觉的载体，世界上没有光的话，我们就缺少了最重要的感官。不过从另一个角度看来，就算没有光，我们也有办法生存下去，毕竟世界上所有物质都是由分子（或原子）构成的。
这个道理看似简单，但足以给予我们新的思路：要想构造一个计算机，直接从分子出发就行了，何必一定要借助光和电呢？这就是分子计算机（Molecular Computer）的设计初衷。
有了设计理念，接下来我们就需要选择用什么分子了。根据计算机之父图灵等人的理论，一台计算机需要具有储存和处理数据的能力，因此我们所选的分子必须满足上面两种性质。如此一来， DNA 分子便以其独一无二的结构脱颖而出，成为了组件分子计算机的天选之子。
1. DNA —— 天然的海量数据库
我们都知道，DNA 长这样：
就像旋转扶梯一样，它的每一级台阶都是结构都很相似，叫做核苷酸。核苷酸的基本组成单位又有三个：磷酸、脱氧核糖（五碳糖）和碱基：
图片来自 http://mis.wlgsh.tp.edu.tw
其中磷酸是生物分子中的常见化学基团，可以广泛影响分子的化学活性；五碳糖起到支架作用，它使得 DNA 分子排布成为双螺旋结构；碱基则是 DNA 的核心所在，一共有 A、T（RNA 中由鸟嘌呤 U 代替 T）、C、G 四种，这四种碱基决定了生命体的所有遗传信息，并且会影响几乎所有代谢过程。
这乍一听很不可思议，因为生命种类如此繁多，数量如此庞大，而所有生物的遗传都跻身于这四种碱基上。这是怎么做到的呢？简而言之，这四种碱基的不同排列组合能指挥核糖体合成出不同的氨基酸，从而创造出功能各异的蛋白质。蛋白质的多样性是生物多样性的物质保证。
核糖体把信使 RNA 上的碱基转录为氨基酸，并合成多肽（蛋白质的组成部分）。动图来自网络
截止 2003 年，人类基因组计划已经发现了人类染色体（将 DNA 包装起来的东西）上的两万多个基因，每个基因又由大量碱基构成。至今没有人准确知道人类 DNA 上大约有多少个碱基，不过可以预料，这个数量将至少是以亿为单位。
由此可见，DNA 的储存效率比所有芯片都高好几个数量级，是一个纯天然的海量数据库，正是这个海量数据库造就了丰富多彩的生命世界。如果我们用 DNA 来代替芯片，效率会不会高很多呢？我们来看看这个点子的可能性。
2. DNA 登上计算舞台
我们知道，电子计算机中所有数据都是由 0 和 1 组成的，因此用 DNA 来代替芯片，本质上就是要用 A、T、C、G 来代替 0 和 1 。这便是计算科学家、DNA 计算之父伦纳德·阿德曼（Leonard Adleman，图灵奖获得者）的灵感来源。
阿德曼在1994年首次将 DNA与计算科学相结合 [2]。简要说来，他的办法是把具有 20 个碱基的单链 DNA 片段作为一个计算单位，并把大量单链 DNA 放入试管中任他们发生链接反应（Ligation reaction，对应 DNA 片段间在 DNA 连接酶的作用下结合在一起）[1]，反应后的生成物就是计算的结果。
DNA 片段之间的反应生成物可能有很多很多，如何才能分辨出想要的结果呢？阿德曼采用了琼脂糖凝胶电泳（Agarose gel electrophoresis，本质上就是利用不同长度 DNA 分子的带电性不同）的方法，用以区分具有不同数量碱基对（base pair，简称 bp）的 DNA ，并筛选出相应 bp 数的 DNA 作为最终结果。
用电泳法找到哈密顿圈问题（下一节会继续提及）的解。图片来自网络
可想而知， DNA 计算方法的出现立马就受到大量关注，不少人首次意识到原来电脑还可以有这种炫酷的设计方法。此外，由于初始 DNA 数量众多，所以这样设计出来的 DNA 计算机有极强的并行计算性能（可以同时处理多项计算任务，更多内容可参考《让 GPU 也参加到计算中来》），这也让整日沉浸在半导体世界中的计算机专家们耳目一新。
不过话说回来，新奇归新奇，它的实用性总是需要经过三昧真火考验才行。细心的读者或许会发现，琼脂糖凝胶电泳法对相同 bp （碱基对数量）的 DNA 一视同仁，没办法确定 DNA 序列到底长什么样。因此可想而知，阿德曼设计的实验只能解决某些特定的问题，例如一笔画问题（哈密顿圈问题）等。
后来的科学家们针对这个问题进行了不少修正。例如让 DNA 计算解决更多组合问题 [3]、设计出基于 DNA 的电路 [4] 以及在细胞内使用 DNA 计算 [5] 等等。阿德曼本人也在两年后用更加严谨的数学语言提出了 DNA 计算的大框架，并总结在文献 [6] 中。
3. 小试牛刀
为了简单说明 DNA 计算是如何运作的，小编哈密顿圈问题为例。哈密顿圈问题是旅行者问题的一个特例：
一个旅行者要坐飞机游览 n 个城市，每两个城市之间可能有双向航班，可能只有单向航班，还可能没通航班；另一方面，他有在所到之处乱刻“到此一游”的习惯，为避免被警察抓住，他只能在每个城市逗留一次。问如何规划他的行程？
上述问题可以用有向图的方法进行建模，它是一个著名的 NP-完全问题（可以理解为算法效率不高的问题）：
上图中数字代表城市，箭头代表航班
要靠 DNA 的合成反应来解决这个问题，我们首先必须想办法用 DNA 来描述出这个问题。在上个问题中，我们可以把每个城市用相同 bp （碱基对数）的单链 DNA 片段来表示；若存在从城市 1 和城市 3 的航班，那么就认为城市 1 对应的单链 DNA 可以和城市 2 对应的单链 DNA 反应，这可以通过加入与城市 1 和城市 3 对应的 DNA 连接酶和 DNA 剪切酶来完成。例如，如果我们用 10 bp 的单链 DNA 来表示每个城市的话：
如此这般，我们便可以利用 DNA 聚合酶反应（Polymerase chain reaction）技术不断合成出长链 DNA。再从算法的角度看来，要想寻找一个哈密顿圈，我们只需筛选出所有 5 x 7 = 35 （反应片段数 x 城市数）个 bp 的 DNA 就行了！不难看出，每个具有 35 bp 的 DNA 片段一定是一个哈密顿圈！
由于 DNA 计算机纯粹依赖于 DNA 的分子特性，因此要想提高 DNA 计算机的效率，需要采用更为精细的生物技术，例如通过加热的方法提取单链 DNA 等等，有兴趣的读者可以参考文献 [2] 或 [6]。
附：下图是小编使用遗传算法对 n = 50 的旅行者问题（哈密顿圈问题的推广）进行的优化模拟：
上面每个点都服从二维均匀分布。当 n 增加时，迭代次数（iteration）呈指数增长。因此当 n 很大时，由于分子数众多（一个试管中的 DNA 就可达到 10^13 以上数量级）， DNA 计算的效率会远远超过传统计算机。
总结
DNA 是遗传信息的载体，是生物世界的主宰；另一方面，计算机却是基于半导体材料的电子设备。生物和非生物世界之间似乎总是存在一条看不见的鸿沟，不过相信经过本文的介绍后，不少读者已经体会到，这条鸿沟似乎并没有那么难以逾越。
当然，DNA 计算只是分子计算（Molecular computing）和有机计算（Organic computing）的一个分支。后面两个分支隶又属于合成生物学。和一般生命科学从现象到本质的研究途径不同，合成生物学反其道而行之——它致力于以单个分子或细胞为零件，一步步构建出以生命科学为基础的工业殿堂。
人脑就是一个复杂的有机计算机，因此弄明白人脑的工作原理是有机计算的一个重要课题
不过话说回来，本文只是介绍了 DNA 计算机的一种可行性，它的普及还有很长的路要走。什么时候才能看到第一台商业化的 DNA 计算机呢？这不是某个个体或团队能独立完成的，还需要靠不同领域的科学家共同努力。
参考文献
[1] Bruce Albert et. al, Essential cell biology (4th edition), Garland Science.
[2] Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science. 266 (5187): 1021–1024.
[3] Lila Kari; Greg Gloor; Sheng Yu (2000). Using DNA to solve the Bounded Post Correspondence Problem. Theoretical Computer Science. 231 (2): 192–203.
[4] Tyagi S, Kramer FR (1996) Probes that fluoresce upon hybridization. Nature Biotech 14:303–308.
[5] Ehrenfeucht A, Harju T, Petre I, Prescott D, Rozenberg G (2004) Computing in Living Cells. Springer, Heidelberg.
[6] Adleman L (1996) On constructing a molecular computer. DIMACS 27:1–21.
往期精彩回顾：
欢迎大家关注我的公众号“科普最前线”（id:kpzqxyxg），对话前沿科学！每篇文章都由笔者亲自完成或修改，希望和大家一起交流！
https://blog.sciencenet.cn/blog-3364297-1321504.html
上一篇：同一个细胞，不同的你
