基于DNA折纸的可编程纳米计算

王 方，肖溢锐，吕姝颖，强小利* ，石晓龙**

（1.广州大学计算机科技研究院／计算机学院，广东 广州 510006；2.北京理工大学宇航学院，北京 102400）

计算工具一直是人类生活中必不可少的一部分。古往今来，人们都在尝试用各种介质与算法进行数据的存储和运算。作为20世纪最伟大的发明之一，电子计算机已经深入影响了人类社会的各个领域，无疑是信息时代不可或缺的重要工具。当今，互联网更是进入了大数据时代，庞大的数据量需要计算机的处理功能及其自身复杂性都成指数级爆炸式增长，这使得科学家们在努力突破“摩尔定律”［1］的同时，不断探寻着新的信息处理模式。另一方面，计算科学家将问题分为简单、困难与不可计算3类，电子计算机由于其顺序计算的图灵机模型，容易处理简单问题，但面对现实生活中存在的许多复杂系统问题，尤其是非确定性多项式（Nondeterministic Polynomially，NP）问题，其处理方式会使问题规模成指数增长，因此，科学家们从未停止探索新一代计算系统的脚步，量子计算机、生物计算机、光计算机等新型计算机也在这样的环境下应运而生［2－4］。

DNA计算是生物计算的一个分支，以脱氧核糖核酸链作为信息载体，借助化学反应对DNA链进行切割或整合，行使类似硅基计算机中存储器、控制器等元件的功能。运算过程在生物容器中进行，这个生化反应过程类似电子计算机的输入／输出、计算器等电子元件的工作过程。DNA链作为自然界多数高级生命体内的主要遗传物质，以4种碱基——腺嘌呤（A）、鸟嘌呤（G）、胞嘧啶（C）、胸腺嘧啶（T）的组成和排列顺序，达到编码和储存遗传信息的目的。这与电子计算机基于0和1高低电频处理信息的方式极为相似，因此DNA可以作为良好的信息处理材料，且大量DNA可以在微量液体中同时反应，高度并行的处理能力使得DNA计算获得越来越多的关注。

基于自组装的DNA纳米结构制造技术与DNA计算相辅相成，指导DNA自下而上地有序组装。自组装是指大小分子、纳米材料等结构单元，在非共价键的相互作用下自发地聚集或组织成有序而紧密结构的过程，是一种普遍存在的自然现象。DNA纳米制造技术利用DNA分子的序列编码和携带信息，指导和编程基本结构单元组装而成的大规模结构，这就赋予了DNA其生物学意义以外的价值。

基于可编程自组装建造的纳米结构往往具有稳定的性质和规则的几何外观，一些基于特定序列和缜密设计规则生产的高级纳米结构，如DNA折纸，其序列具有可寻址性。这样的纳米结构可以作为一种强大的、纳米分辨率的全编程工具，容易实现自动化，为DNA计算搭载了可靠的平台。因此，DNA折纸技术的发展也掀起了国内外学者对DNA计算的一股研究热潮。本文首先对DNA计算和以DNA折纸为代表的自组装纳米技术两方面进行简要的介绍，然后针对DNA折纸在DNA计算领域的诸多研究，包括以DNA折纸为基底的DNA计算、算法与可编程自组装、可计算折纸结构等方向的成果进行论述与展望。

1 DNA计算与DNA纳米制造

1.1 DNA计算研究现状

DNA计算首次得到验证是在1994年，Adleman［5］提出利用DNA分子解决具有7个顶点的有向Hamilton路径问题，将顶点与边的联系转化为DNA链之间的杂交，并在溶液中成功进行了实验操作，开创了DNA计算领域的先河。DNA计算多为巧妙利用生物分子自身特性和反应过程，构建基于分子结构或生物反应机理的计算模型。随后越来越多的DNA计算模型相继被提出，由Roweis等［6］最早提出的粘贴模型主要通过对单双链DNA混合、搜索的过程完成求解，已经被用于求解图顶点着色问题、可满足性问题、最大团与最大独立集问题等NP-完全问题［7－10］。Head等［11］和周康［12］则提出基于连接与切割质粒DNA分子的质粒计算模型，原理是对核酸内切酶和连接酶作用在质粒的反应进行0、1两种状态的编码，后续被用来解决了排课表问题、图的边着色问题、组合问题等。还有一些作用于其他非质粒分子的剪接模型，如基于剪接操作的可编程有穷自动机和自律式分子计算机模型［13－14］。

随着应用场景的多元化与生物计算的进步，DNA计算也不单用于解决组合优化等算法问题，而是向着逻辑计算的方向发展。早期由Stojanovic等［15］提出基于DNA酶的逻辑门，并构造了与门、异或门等简单布尔逻辑门。2006年，Seelig等［16］开发了基于DNA链置换反应的逻辑门，实现了容易扩展的与门、或门、非门等基础逻辑门。随着基于链置换DNA计算的发展，已经可以实现包含更多层级级联的大规模逻辑电路，或是分子结构更精密的复杂逻辑电路［17－19］。DNA分子更是可以与RNA、蛋白质、酶、纳米颗粒等更多材料结合，共同构建可用于生物传感和递送的多组分逻辑电路［20］。

DNA计算和传统电子计算机相比，具有高度并行性、极大的存储容量、低能耗、高计算速度等显著优势。DNA计算的独特之处在于，可以通过排除伪解在操作上的便利来优化初始解空间，降低求解复杂度。同时，DNA计算可以通过分子间的反应与相互作用，在生物化学体系中提供嵌入和控制，扩展了在纳米尺度的精确计算手段。然而，在DNA编码、结果的检测与表征、非解排除的彻底性、解空间指数爆炸等方面存在的问题依然亟待优化与解决［21］。总而言之，总体研究处于起步阶段的DNA计算已经在NP困难问题求解、大规模图像信息处理、信息存储、系统加密与破译、药物递送控制等方面取得了研究成果，并尽可能在信息科学、基础科学、生命医药研究等领域提供技术服务与支撑。

1.2 DNA自组装纳米制造

最初将DNA作为纳米材料的想法由Seeman教授提出［22］，通过合理设计称为“四臂结”的十字叉状的类Holiday结构，作为一个瓷砖（Tile）结构单元，多个Tile可以通过对DNA序列进行编码，控制粘性末端杂交组装成二维结构，这种组装方式称为Tile组装。随着合成技术的发展，为了获得分子结构更稳定，以及组装产物更可控的纳米单元，大量形形色色的DNA可编程结构相继被设计。Seeman团队随后在四臂结的基础上进行改进，提出更稳定的“双交叉”（Double Crossover，DX）Tile结构，该结构拥有沿螺旋轴方向的4个编码位点，如图1（a）所示［23］。类似基于DNA链交叉的Tile结构相继被设计，LaBean等［24］设计了包含3排双螺旋区域的“三交叉”（Triple Crossover，TX）模块，Seeman［25］和Yan等［26］设计了同极性链构成的“平行交叉”PX模块，以及用于构建可控纳米器械的JX2变体，如图1（b）所示。2012年，Wei等［27］提出一种名为“单链瓦片”（Single Stranded Tile，SST）的自组装策略，多个Tile之间通过碱基特异性识别，连接成交错的双链结构，进而组装出大面积的二维平面“分子画布”，如图1（c）所示。Shi等［28］构建了一种可以组装得到3，4和6臂结的微型Tile（subtile），并通过分层组装策略，可以生产多种二次组装产物。

图1 DNA纳米结构Fig.1 DNA nanostructures

DNA Tile的自组装过程往往相对复杂且产率并不高，源于其生物表征过程中涉及大量短的DNA序列，要求它们在合适的实验条件下以合理的浓度配比反应，才能形成完整结构，且复杂纳米结构的组装过程涉及较多的纯化步骤，这就一定程度上制约了基于Tile的自组装结构的规模和应用。DNA折纸技术的出现解决了这些问题，为自组装纳米技术的发展开拓了更广袤的空间。

1.3 DNA折纸技术及应用

作为自组装纳米技术的一个分支，DNA折纸技术的概念在2006年首次被Rothemund［29］提出，这是一项能够指导DNA链自下而上组装构建几十至数百纳米尺寸范围内特定形状结构的实用技术。这一技术基于沃森-克里克碱基配对原则，通过人为编码设计数百个短ssDNA（称为订书钉链，staples），将一条通常长度约7 000nt的单链环状DNA骨架（称为脚手架链，scaffold）折叠并绑定为预设形状。这种高度可寻址且易于表征技术的出现，改善了Tile自组装中涉及大量短链的问题，在纳米制造史上具有里程碑意义。

从形貌层面的二维对称到三维不对称，再到组装方式层面的二次组装、动态组装和对其他规模折纸的探索。DNA折纸结构形貌方面的复杂度在不断增加，实验实现的手段也在不断优化与创新。如图1（d）所示，纳米烧瓶、DNA拼图、DNA画像等引人注目的成果的出现都意味着DNA折纸技术构建纳米结构方面的能力不断被证实［30－32］。

近年对DNA折纸的研究范围仍在不断扩大，DNA折纸表面近10 000 nm2的区域包含约200个可寻址位点，这样的全局寻址特性使之可以作为精确到纳米级分辨率的定位模板或框架，在组织空间方面成效明显［33－34］，也能用于更多其他物质和材料的定点修饰［35］，其具体应用触及抗体检测、生物传感与递送、纳米电路板与分子计算、超分辨荧光成像、光采集、单分子研究等方方面面［36－39］，如图1（e）所示。同时，对DNA折纸组装条件及其动力学成因方面的研究揭示了很多自组装过程的细节，帮助使用者对纳米结构形成进一步了解［40］。诸多对相关模拟仿真工具的研究方便了使用者对DNA折纸的深入理解［41－42］，许多针对突破规模限制、稳定性与生产能力的研究为DNA折纸的广泛应用提供了更强的技术保障［43－44］，而这只是DNA折纸发展至今20年内，在设计、构建与应用方面的一小部分研究成果。

2 基于DNA折纸的计算

DNA作为一种可以携带信息，且具有高度热力学和动力学性质的分子，长期被作为体外信号网络和分子计算的流行底物。通常对算法的编码与优化最终落实在合理的序列设计上，这导致了DNA计算模型流程复杂，且计算速度随着这种耗散电路规模的扩大受到限制［45］。而可寻址结构DNA折纸的引入为电路元件分割、共定位提供一个框架，给DNA电路的发展带来新思路。

针对当时主流的DNA计算主要依赖于自由扩散分子随机相互作用的现状，一些理论研究认为可以利用空间受限制的DNA电路架构方法，来优化计算速度和电路规模。Muscat等［46］最初在2013年讨论了一种DNA链置换电路的计算架构，提出可以通过一种实用的纳米组件——DNA折纸进行空间隔离，从而更容易设计基于DNA的电路。2015年，Dalchau等［47］提出了一种基于DSD的DNA局部电路概率仿真分析方法，分析结果显示，对于计算4比特数平方根的电路，其DNA折纸上的局部化电路方案在5～9 min完成了75%反应，而其复杂的混合电路方案需要5～9 h，意味着局部化电路在速度方面的性能优于混合电路。Teichmann等［48］则通过在折纸平台固定“发送端”和“接收端”的方式研究了共定位电路的鲁棒性，研究发现中间栅距≈20 nm的级联表现出更快的动力学和更小的折纸内泄露反应。

Seelig团队在2017年成功将可伸缩的DNA逻辑门及其传输通道搬运至以矩形DNA折纸为基底的平台上，通过将独立发夹固定在DNA折纸表面的方式，完成电路元件的共定位［49］。折纸对发夹逻辑门的排列和空间组织使得反应优先发生在“邻居”间，这使得信号传输（导线）沿着发夹的布设进行，如图2（a）所示。同时，相同的发夹可以在整个电路中重复使用，这克服了分子电路工程中一部分速度和规模限制。和扩散元件的分子电路相比，定位电路将一加法模型的计算时间从几小时减少到了几分钟。次年，Bui等［50］构建了由6个DNA元件参与杂交的折纸表面链式反应，证明了局部杂交反应的执行速度比非局部DNA更快，该研究运用了AFM、TIRF、集成荧光光谱等多种方式来确认发生在折纸表面的局部DNA杂交反应。

图2 折纸表面的DNA计算Fig.2 DNA calculation on the surface of origami

除了针对确定性算法进行策略优化，DNA折纸的表面定位也可以改变随机算法的适用性。Thubagere等［51］建立的货物分拣机器人，可以在二维折纸表面行走，同时捡起最初处于无序位置的两种货物，直到所有分子被分类并运送到指定目的地。该机器人的设计是在没有能量供应的情形下，行为由它们周围的局部场景来引导。Chao等［52］在2019年构建了单分子DNA迷宫导航器，其导航原理依靠一个折纸表面的链置换级联反应进行，触发后反应沿着DNA发夹定义的路径自动前进，通过单分子对某一可能路径的探索，从折纸导航器集合中获取两点的具体解决路径，如图2（b）所示。最终可以在DNA折纸平台上定义的十顶点有根树上执行并行的深度优先搜索。没有DNA折纸对分子群的准确定位与组织，这些应用不易实现。

DNA折纸的组织能力不仅仅局限于表面定位。Winfree团队报告了一种可以执行多种算法的基于DNA自组装分子自动机，DNA折纸作为种子组织者提供迭代布尔电路的输入面板及SST作为逻辑门和导线周期性地重复电路层来计算，最终在DNA折纸－瓦片混合的2D阵列上显示计算过程与结果［53］。

Yin等［54］还提出了一种可满足问题的通用DNA计算模型，对公式中每个子句设计一个DNA装置，该装置在DNA折纸表面沿辅助线组合，生成边缘构建图案，由此并行地完成对满足子句赋值的搜索过程。次年，该组引入纳米金颗粒作为顶点标识放大光电信号，用荧光标记的分子信标作为锚链并固定在DNA折纸基板上，建立了求解最小生成树的可视化计算模型［55］。由于折纸纳米分辨率的组织，通过荧光检测技术可以观察到反应路径，这让计算过程的读取更加直观，如图2（c）所示。Yang等［56］提出了对一种NP-完全问题－背包问题的折纸表面计算模型，通过选择映射为DNA折纸基底上的有向路径，将问题的解映射为找到一条使背包价值最大的有向路径的方式，引入荧光检测找到满足约束的解。该模型在Visual DSD模拟下验证了有效性，但其局限性在于受制于底座的尺寸，只能解决规模较小的0-1背包问题。

近期，Liu等［57］则利用折纸共定位电路开发了一种双输入DNA有限状态机（FSM）。折纸的空间限制带来更简单的设计、更小的泄漏反应和最小的正交组件集的同时，被空间所约束的反应顺序也帮助解码时间上的输入信息，最终部署了这个无酶和外源燃料试剂参与的时序链置换电路，并被验证可以感知两种MicroRNA的顺序，如图2（d）所示。这是一个利用DNA局部电路来感知时间事件的例子，强调了DNA纳米器件在生物过程的时间分辨率方面的潜力。

折纸参与定位计算元件的DNA计算系统优势在于：①电路元件间的相互作用被局限到近端之间，导致了更快的反应；②空间定位导致电路组分的有效浓度高于混合溶液中组分的有效浓度，有助于调节化学计量；③由于信息流不再依靠序列特异性控制，各组分之间序列允许重用；④可以在同一试管中分割不同的功能模块，方便某些应用场景。

3 可编程自组装

3.1 算法自组装

随着Tile分子从简单的十字结构发展到各种模块构成的复杂DNA纳米图形，在王氏Tile的基础上，算法自组装的概念应运而生。最初，Winfree等［58］阐述了可以通过Tile自组装来执行计算，这个构想中每个瓷砖被看作独立逻辑门，例如DX Tile的一侧粘端可以编码为0或1，对应输入；另一侧编码粘端对应输出。代表异或（XOR）逻辑的DX一维自组装在2000年已经被实现［59］。根据二元函数XOR逻辑计算并生长的分形图案——谢尔宾斯基三角形（Sierpinski Triangle）之后也被算法自组装实现，在原子力显微镜（Atomic Force Microscope，AFM）下可以清楚观察到分型三角形是如何生长，尽管还不是十分完美，有组装错误的存在［60－61］。由于组装过程中瓷砖不单单与错误瓷砖竞争插槽，还要面对半正确瓷砖的竞争，算法自组装的实现过程比传统自组装更困难［62］。通过算法组装，构造复杂而尺寸可控的DNA晶格也成为可能，规模从2×2到8×8，多种有限尺寸的DNA自组装阵列被实现［63］。还有类Lego积木的有限编码3D系统，有目的性的增添或删除特定的SST组件，可以实现类似积木搭建方式的任意形状的自组装［64］。

DNA折纸技术的出现则为传统自组装纳米结构提供了更多可能，在算法自组装领域突出表现为，为DNA短链的生长提供种子（Seed）序列的规范化区域组织［65］。近期，Winfree等开发了基于SST与DNA折纸的混合生长的DNA元胞自动机模型，在2D平铺阵列上将算法行为嵌入了分子自组装过程，如图3（a）所示，并实验展示了20余种电路，可以执行复制、随机游走、排序、回文识别、倍数判断等命令［66］。

图3 基于DNA折纸的可编程自组装Fig.3 DNA origami-based programmable self-assembly

3.2 编码寻址的自组装

由于掣肘于通用脚手架链约7 000 nt的长度，大多数DNA折纸结构单体的尺寸被限制在50～200 nm左右。若要制造突破尺寸限制的DNA折纸结构，一种方法是在单个DNA结构中划分一部分序列作为功能性连接区域，通过编码连接区的碱基序列，让小尺寸折纸以对应的编码策略放大为大面积结构。

编码可以以特定的几何状态呈现，例如Rajendran等［67］提出的拼图状自组装折纸，沿螺旋轴方向以榫卯相接的方式完成特定堆叠，最终以35%的产量组装得到3×3的拼图阵列，如图3（b）所示。

更多情况下编码连接以两条反平行粘性末端碱基互补或堆积的方式实现。Tikhomirov等［68］著名的“蒙娜丽莎”画像便是基于粘端编码边缘并建立组装规则，通过分层组装的方式，生产了规模8×8，尺寸达到微米级的完全可寻址纳米阵列。对编码策略做出改变还可以构建出拥有其他功能的组装系统，该组还以可控的方式构建了具有随机组装功能的平面阵列——包括实现了微米级随机环图案、迷宫和树，如图3（c）所示［69］。Kang等［70］提出的动态开关编码方案则是通过添加过量阻断链的方式，控制不同折纸单元以图形输出的方式实现布尔函数。

结构间的组装也可以依靠其自身形状特性和连接处的编码共同完成。例如Wang等［71］构建了多种六边形折纸，通过编码和结构自身的机械性能，控制它们组装成微米级的蜂窝状晶格和管。Wagenbauer等［72］构造的3D自限制性齿轮，讨论了单个折纸的几何形状细节，对高阶组装物中拷贝数、位置、方向等产生的影响和控制。Wang等［73］对线框DNA折纸引入了与螺旋轴平行的粘端，由六边形线框的形状和边上的编码共同限制组装过程，合成闭合的有限阵列。

编码组装同样适用于非平面的DNA折纸结构。例如Wickham等［74］展示了不同直径（30～120 nm）的模块化的DNA折纸桶装纳米钉板，并演示了其3D-Exchange动画中构建的“小黄人”图案，以展示自组装桶的精细可寻址性，如图3（d）所示。

分子可编程组装的实现为生物系统的探索和设计提供了新思路［75］。无论分子来自人为设计或自然，可以独特寻址的自组装阵列们都像一张分子画布一样，让原本无序散落在溶液里的大小分子变得容易通过建立算法去操作。

4 可计算结构

DNA折纸由于其高度完整性、稳定性以及优异的抗酶消化能力，被广泛用作分子机器人、信号传递、逻辑计算等功能性模板［76］。

一个经典的例子是Douglas等［77］提出的DNA折纸六边形纳米机器人盒子，该设备可以装载材料，借助适配体编码的逻辑门有效感知环境中的线索并做出反应，对细胞信号实现了AND逻辑计算，如图4（a）所示。之后，Amir等［78］将这种可计算逻辑问题的纳米机器人转移到了生物体内。这些机器人可以接收溶液中的某些信号，作为继电器开关分子有效载荷或关闭，或是相互作用产生逻辑输出。这个纳米计算系统被用来创建了AND、OR、XOR、半加器等逻辑门，并在活蟑螂体内用来控制针对他们细胞的分子。

图4 用于计算的DNA折纸Fig.4 DNA origami for computing

DNA折纸在运算系统中还可以充当显示装置，提供电化学读出以外的其他结果读出手段。Liu等［79］建立了一个查找系统，将两个任意输入组合成一个查找表来提供输出，让DNA折纸充当组合手段来形成立即显示的结果输出，并展示了以乘法为例的折纸表面七段式阿拉伯数字显示计算器，如图4（b）所示。

作为一种序列高度可编程的纳米结构，DNA折纸也可以被设计与其他结构互动并执行计算过程。俞洋等［80］通过组装DNA折纸瓦片的方式，提出了解决给定有向图哈密顿路径问题的计算模型。次年，俞洋等［81］又使用DNA折纸结构编码无向图顶点，提出了解决图着色问题的模型。Xu等［82］提出使用DNA折纸结构作为代理的计算模型，用来并行计算图的着色问题，如图4（c）所示。折纸“代理”们根据承载的图形数据在三维空间中组合，这里解决了一个六顶点三着色问题。其优势与其他可计算结构相同，通过修饰将颜色信息分配给不同的折纸结构，使得计算结果在AFM下高度可视化。

Zhang等［83］则考虑了自组装结构自身的结构潜力，将DNA折纸用于隐写，DNA折纸密码体系见图4（d）。通过对支架链引入特定的生物素修饰链的方式，将信息加密为连续的斑点图案，二者的结合过程实现了加密，添加特定密钥订书钉链后的完整结构的组装过程则完成解密。该研究尝试对字母A-Z和数字0～9生成折纸密文并传输，最终包含样品处理及AFM扫描识别的解密过程需要约1～2 h。虽然相较于电子计算机耗时较长，但该过程符合信息安全的“CIA三位一体”（保密性、完整性、可获得性），也为信息加密提供了一种新颖的分子解决方案。

5 总结与展望

作为一种高度可编程的纳米结构，DNA折纸使得很多精确依赖分子几何、分子动力学模型和工程成为可能。通过在特定位置修饰的方式，一些依赖分子精确放置和操控及运行过程依靠分子组织的系统工程，原则上都可以在DNA折纸平台上受益，本文所提到的基于DNA折纸的DNA计算系统也是得益于序列特异性赋予的可寻址性与可编程性。然而在计算场景下的DNA折纸展现其力量的同时，也揭示了充分发挥其潜力面临的挑战：①设计难题。目前大量DNA折纸相关的设计和仿真工具被开发，其中不乏许多优秀软件将折纸的设计过程简化为黑箱操作，用户容易将几何模型转化为DNA折纸设计。然而，DNA计算对定位分辨率一般要求精确至碱基，这就需要用户理解折纸模型并计算或输入更多结构参数，以避免不合理的设计导致计算无法进行或是扭曲整体结构，这是设计人员在系统的功能性与稳定性之间寻找平衡面临的挑战。②环境问题。DNA计算与DNA纳米结构独有的意义在于同时拥有生物特性与承载信息能力，在生物细胞或活体内与生理环境对接是其独特的优势。如何让DNA计算在复杂生理环境中运行是一大难点。③规模问题。被支架序列长度限制规模的DNA折纸通常可以通过两种策略改变规模：生物技术手段改造支架或是编码组装堆叠为大型结构，两种方法都会牺牲产量，且让DNA计算系统模板的制作流程更加繁琐。

根据DNA折纸运用在DNA计算问题中面临的问题，未来结合纳米技术与DNA计算的可编程计算系统在发展过程中，一方面，需要着力于对底层组装原理的更深层研究，因为分子自动化和序列可编程化是DNA计算得以运行的基础，对自组装机制清晰地描述和展示，是运用自组装技术设计动态结构或稳定组合结构所需要的；另一方面，就像Cadnano系列软件催化了DNA折纸的发展一样，基于纳米结构的DNA计算系统期待“分子编程”辅助工具的支持，这将催生更多沙盒模式下更复杂或更具创造性的计算系统，当然这一点的具体实现依然依赖对分子自组装机制更清晰的探索和稳定表征。Young等［84］近期开发的多尺度分析框架，可以在近原子分辨率预测结构单体到分层组装产物的三维形状、动力学特性和机械刚性，对约7 000碱基对组成的折纸结构分析时间不到15 min。这些动力学模拟手段可以帮助研究者更快捷地迭代DNA组装物的设计－分析－修订工作。因此，期待DNA计算建模、纳米结构合成与自组装技术之间会建立更紧密的联系，产生更多自动化的、稳定的复合模型服务于信息科学、生物医药等领域。