Science丨分子计算用于解决组合问题
作者：张铭芷
1959年，著名诺贝尔物理学奖得主Richard Feynman首次提出了利用纳米技术实现并行计算的概念。尽管此间计算机微型化发展取得了巨大的、里程碑式的进步，这个目标仍未实现。
1994年，Leonard M. Adleman在Science杂志发表的一篇文章首次利用DNA分子实验论证了生物分子计算的可行性。在这项开创性实验中，Adleman利用DNA分子作为信息储存媒介，利用标准生物技术诸如多聚酶链式反应（PCR）、琼脂糖凝胶电泳等做信息处理，用于求解一个小规模的Hamilton问题。
哥尼斯堡七桥问题是著名的图论与几何拓扑问题，其核心是历经图中所有边且不能重复。该问题于1736年由欧拉完成求解并提出此类问题的通用求解公式。Hamilton于1859年提出周游世界的数学问题，其核心为历经图中所有点而不经过重复的点。Hamilton问题一直是图论中的世界性难题，到目前为止仍然没有找到一个像欧拉图那样简单的充分必要条件用于判定一个图是否为Hamilton图。
在计算机领域中，一个在非确定型多项式时间内判定HAMPATH问题的非确定型图灵机解决Hamilton问题包含如下几个步骤：
令HAMPATH = {<G, s, t> | G是包含从s到t的Hamilton路径的有向图}，
1. 写一列m个数p1，p2，…，pm，m是G的节点数。列中每个数都是从1到m中非确定地挑选。
2. 在列中检查重复性，若发现有重复，则拒绝。
3. 检查s=p1和t=pm是否都成立。若有一个不成立则拒绝。
4. 对于1到m-1中的每一个i，检查（pi，pi+1）是否为G的一条边。若有一个不是，则拒绝。反之，所有检查均通过，接受。
文章中，Adleman选取的Hamilton通路如下图所示：
该图为一个起点为0终点为6的有向图，图中列举了顶点之间所有的可及路径，其中恰好包含一条Hamilton路径（0→1→2→3→4→5→6）。其计算目标是寻找一条以顶点0为起点，以顶点6为终点的Hamilton路径。
Adleman解决该问题的思路如下：
生成图中所有随机路径
1. 只保留以0为起点和以6为终点的路径
2. 只保留恰好历经7个点的路径（0-6共7个点）
3. 只保留每个点均历经的路径
4. 若有路径满足上述条件，则报告结果，反之则不存在。
为了使用DNA分子实现上述功能，Adleman使用随机的20碱基长度的DNA序列来表示每一个顶点，使用起点的后十个碱基和终点的前十个碱基来表示有向路径。若存在从顶点i到顶点j的有向路径，则它们可以通过序列的互补配对结合，在连接酶的作用下连接成完整的序列。在这个过程中，将近3×1013个副本同时参与进行Hamilton路径的编码。由于该问题中所有可能的情况远小于参与计算的副本数量，正确的路径结果会被涵盖，也就意味着计算是充分的。
包含所有结果的路径集生成后，需要校验结果是否存在。为了实现第二步，Adleman选用起点0和终点6的互补序列作为引物进行多聚酶链式反应（PCR），对所有符合起点为1终点为6的结果进行放大。为了实现第三步，需要通过琼脂糖凝胶电泳进行分子量大小的表征，对符合分子量大小的结果进行切胶回收。对于第四步，校验图中每一点都被经历，Adleman选择将顶点2，3，4，5的互补序列修饰在磁珠上进行结果回收，通过剩余产物的有无确定该顶点是否被经历，由此寻找到该问题的解。
这项分子计算的工作需要历时7天，特别是第四步的验证更是无比繁琐。但对于更为复杂的大规模的Hamilton图来说，这种可同时对无数种可能的结果进行验证操作的方法可能是更为有效且低劳动密集型的。对于计算机而言，需要对每一条可能的路径进行回溯以确认没有重复的顶点。在这个过程中，由于储存载量的原因难以进行庞大的数据交换，因而其并行运算的容量很容易被限制。而对于分子计算，每一个分子除了作为计算元件还能作为储存元件，每一个DNA序列都可记录计算环境对其本身的操作，除此之外还拥有体积小、拷贝数多的优势，更为容易地实现同时进行运算操作和结果数据筛选。
实验中还有许多局限性，第一步中的连接反应需要充足的时间，并且随着顶点数的增加，非特异性的连接反应可能会发生，而这会造成不可忽略的计算错误。而在后续的扩增和校验实验中，扩增和分离纯化都是实验技术的考量，可能会由于各种各样的原因无法实现扩增和结果的表征，如在第四步中由于没有结合而将“结果”洗去。
尽管还有许多挑战，在文中的问题求解中亦没有展现出比计算机求解拥有的更明显的优势，Adleman这个工作依然有其里程碑式的意义：它展示了分子计算的可行性，并且提供了一种实现分子计算的可行方法。
Adleman, L. Molecular Computation Of Solutions To Combinatorial Problems. Science, 1994, 266(5187):1021-1024.
