异或门的DNA步行者计算模型

刘璐璐，殷志祥，唐 震

（1.安徽理工大学 数学与大数据学院，安徽 淮南 232001；2.上海工程技术大学 数理与统计学院，上海 201620）

自Adleman开创性引入DNA计算成功解决了7个顶点的哈密尔顿有向路问题[1]，DNA计算逐渐进入人们的视野。DNA计算机将会带领我们走向一个新的计算时代。2004年，Dirks提出了杂交链式反应（hybridization chain reactions，HCR），实现了放大信号的目的[2]。这种方法在组合优化，分析化学，生物传感器和医用信号检测中得到广泛的应用。2006年，Rothemund首次提出DNA折纸术[3]。同年，运用DNA折纸技术，Qian等人建立了一个直径约为150 nm的非对称模拟中国地图[4]。基于DNA折纸术组建一种独特的可编程支架，用于控制分子元件的排列，这种手段被广泛应用于单分子检测[5-6]和逻辑操作等领域[7-8]。在折纸基底上DNA步行者的研究已经证实了具有空间约束的DNA系统中，可以连续发生多步反应。这种主要由酶催化驱动的DNA步行者已经从需要少量外部触发的步骤发展到可在折纸基底上沿着铺设的轨道自主移动[9-10]。2017年，《Nature》杂志发表了一篇关于DNA折纸术的论文，引起了广大学者的关注。Tikhomirov等人提出具有任意图案的微米尺度DNA折纸阵列的分形组装的方法。文中使用表面具有图案的正方形DNA折纸瓦片作为基本构建单元，构造了如蒙娜丽莎、公鸡等图案。这个组装方法的构建和成功实现，说明了DNA折纸术的可寻址性[11]。2018年，晁洁等人设计了一种单分子DNA导航仪，并用来解决迷宫问题。以2D折纸术模型为基底，在基底上以杂交链式反应的近端链交换级联反应进行单向扩增，最后通过原子力显微镜观察得到迷宫问题的正确路线[12]。2019年，唐震设计了基于杂交链式反应的与非门模型，该模型反应部分存在于折纸基底上，与非门结果通过观察金纳米粒子是否从DNA折纸基底上脱落来得到[13]。

文献[14]设计了三手四足的DNA步行者，利用链置换驱动DNA步行者沿轨道顺时针行走，运输金纳米颗粒。文献[15]将DNA步行者应用于解决Petri网问题。文献[16-19]主要将DNA步行者应用到传感器中，能够实现信号的放大作用。文献[20-21]详细介绍了DNA步行者的研究进展与新兴生物分析应用。

本文基于DNA折纸基底设计了一个动态的异或门模型，模型中构造好的DNA折纸基底和辅助链在试管中大量共存。DNA折纸基底上排列了两条路径，每条路径以纳米金颗粒为分界点。将输入值设计成具有不同编码的DNA链，一旦有值输入，即对应的DNA链进入系统，由于编码的不同，它只会在特定的路径上进行链置换反应。待反应完全结束后，两个纳米金颗粒仍保留在DNA折纸基底上，则结果是真；两个纳米金颗粒动态地分离出折纸基底，则结果是假。文中应用的DNA折纸结构和步行者已被证明是可实现的。

1 异或门

异或门被广泛应用于数字信号传输的纠错电路及计算电路中。实际应用中可用来实现模2加法器或奇偶发生器，还可以用作异或密码、可控反相器等。异或门作为基本逻辑电路，使用DNA计算构建异或门对DNA计算机的实现有着不可或缺的作用。在异或门中，若两个输入值不同，则输出为1；若两个输入值相同，则输出值为0。逻辑表达式为：F=A⊕B（⊕为“异或”运算符），真值表见表1。

表1 异或门真值表

2 动态DNA折纸计算模型

2.1 DNA步行者的设计及行走

该模型由四部分组成，分别为DNA折纸基底、纳米金颗粒、固定在基底上的DNA发夹结构和添加的辅助链如图1。折纸基底图1(a)是由许多短的订书钉链将一条M13长链折叠而成的矩形结构，在折纸基底上有带有粘性末端的延伸单链，用来固定DNA链。

图1(b)中每条直线的中间都有一颗15 nm的纳米金颗粒，每颗纳米金颗粒上附着了两条DNA单链，分别记为N10，N11，N20，N21。

图1(c)为异或门模型中的三种辅助链，分别auxL、auxN0、auxN1为这三种辅助链没有固定在折纸基底上，而是大量存在于溶液中，与折纸基底不反应，稳定共存。auxL用来辅助DNA步行者行走。auxN0和auxN1用来辅助金纳米颗粒的脱落。

图1(d)为动态折纸基底模型，两条直线路径分别记为L1、L2，每条直线路径由两条子路径组成，以中间的纳米金颗粒为分界点，分别从左到右（记为 L10，L20），从右到左（记为 L11，L21）两个部分，四个路径的不同之处在于入口处和纳米金颗粒附着链的设计。子路径L10的连通方式是从左到右依次排列成HA0sta→H10→HA0→…→HA0→HA0end。子路径L11的连通方式是从右到左依次排列成HA1sta→H11→HA1→…→HA1→HA1end。子路径L20连通方式是从左到右，在折纸基底上依次排列成HB0sta→H20→HB0→…→HB0→HB0end。子路径L21的连通方式是从右到左依次排列成HB1sta→H21→HB1→…→HB1→HB1end。

图1 组成模型的4个部分

2.2 基本反应过程

输入链IA与固定在折纸基底上的HAsta发生链置换反应，HAsta中的发夹结构T*被打开，见图2（a）；暴露出的单链T*-e*与H0发生链置换反应，见图2（b）；H0中的发夹结构a和x均被打开，暴露出的单链与大量存在于溶液中的auxL反应，auxL中的发夹y*和c被打开，见图 2（c）；auxL的区域y*、步行者链的区域c都会与链H1反应，打开H1中的发夹结构a和x，见图2（d），从而步行者再次向右移动一步。重复步骤，步行者将继续移动，直到全部链H1反应完成。

3 异或门的实现

3.1 输入链的设计

输入A=0代表链为IA0，由两个区域组成：3'-e*-A0*-5'。输入A=1代表链即为IA1，由两个区域组成：3'-e*-A1*-5'。输入B=0代表链即为IB0，由两个区域组成：3'-e*-B0*-5'。输入B=1代表链即为IB1，由两个区域组成：3'-e-B1*-5'，见图 3。

图3 输入链的设计

3.2 异或门的实现

当输入A=0,B=0时，添加输入链IA0，IB0进异或门模型。在路径L10上发生链置换反应，IA0触发路径L10上的步行者移动，路径上的发夹结构依次被打开，直到步行者链向右移动到最后一个链HA0上，见图 4（a）～（c）。最后一个HA0上步行者链的区域c-b与链N10的c*-b*互补，y*-b*-a*与y-b-a互补，链置换反应后，链HA0end上的发夹结构被打开，此时，HA0end上的区域A0-e与添加的IA0的A0*-e*发生链置换反应，因此，链N10与HA0end分离，见图4（d）。链N10上区域n-e*与存在于溶液中的辅助链auxN0上区域n*-e互补，辅助链auxN0的发夹被打开，链auxN0中区域n*-e*-b与链N21中区域n-e-b*互补，链auxN0和N21链发生链置换反应，因此链N21与HBlend分离，见图5。在路径L20上发生链置换反应，反应过程与在路径L10上基本相同。最后一个HB0链和链IB0一起与HB0end发生链置换反应，最后一个HB0链上步行者链与链N20反应，使得链N20从HB0end上脱落，见图 4（a）～（d）。链N20与溶液中的辅助链auxN1反应，辅助链auxN1的发夹被打开，链auxN1和链N11发生链置换反应，链N11与HA1end分离。见图5。因此，两个纳米金颗粒均与折纸基底分离，结果为假。

当输入A=0,B=1时添加信号链IA0,IB1进异或门模型。在路径L10上发生的链置换反应与上述的一样，这里不重复描述，反应结束后，附着在金纳米颗粒上的N10与折纸基底分离，然而此金纳米颗粒的另一端L11仍与HAlend相连，因此金纳米颗粒仍在折纸基底上。同样的，在路径L21路径上反应完成后，金纳米颗粒的一端L20仍与HB0end相连，反应结果图显示纳米颗粒仍在折纸基底上，因此结果为真。见图6。

当输入A=1,B=0时添加信号链IA1,IB0进异或门模型。反应结束后，金纳米颗粒另一端N10仍在折纸基底上。在路径L20上反应结束后，金纳米颗粒的另一端N21仍与HB1end相连，因此金纳米颗粒仍在折纸基底上见图7。因此，两个纳米金颗粒均未与折纸基底分离，结果为真。

当A=1,B=1时添加信号链IA1,IB1进异或门模型。在L11反应结束后，N20与HB0end分离。在L21反应结束后，N10与HA0end分离见图8。因此，两颗金纳米颗粒均从折纸基底上脱落，结果为假。

图4 输入IA0和IB0两个金纳米颗粒不会脱落

图5 输入IA0和IB0两个金纳米颗粒脱落过程

图6 输入I A 0和I B 1两个金纳米颗粒不会脱落

图7 输入IA1和IB0两个金纳米颗粒不会脱落

图8 输入IA1和IB1两个金纳米颗粒脱落过程

4 小结

本文构建了一个基于DNA折纸基底的动态异或门模型，通过对纳米金颗粒的动态分离来检测输出结果的真假。该系统有如下优点：

（1）该模型实现了一定的自动化，输入链进入系统后，反应基于DNA步行者进行，不需要酶的参与，自发进行，直至反应结束。人为所需要参与的仅仅只有输入链的添加和结果的检测，这种系统的自动化对于DNA计算机逻辑计算的实现提供了一定的思路。

（2）模型运用DNA链置换反应，由于DNA链置换反应具有高效，稳定的特点，这使得模型的具有极高的可行性。

（3）模型设计不仅解决了异或门逻辑计算问题，同时也提供了一种分子逻辑门在生物计算，生物传感器，智能医药输送等方面应用的新思路。如何将分子逻辑计算应用到体内分子逻辑门的构建及生物传感等方面将是下一步的工作重点。