逻辑门在DNA计算中的生物实现

崔建中

(淮南联合大学 实训中心，安徽 淮南 232038)

0 引言

逻辑门是集成电路上的基本组件，是构建计算机的基础。逻辑门可以组合成逻辑电路进行复杂的逻辑运算。

摩尔定律指出集成电路上可容纳的晶体管数目约每隔18 个月便会增加一倍，性能也将提升一倍。由于一方面DNA 分子海量信息的存储能力；另一方面，两条单链DNA 可以依据简单的碱基互补配对规则形成稳定的双链DNA，且反应可以高度并行地进行。上述特点使得DNA 计算很有可能取代硅介质计算机并实现计算的途径。

本方从DNA 计算、逻辑门在DNA 计算中的生物实现两个方面做一下简要的介绍，文中阐述了Winfree 等人的最新研究成果，并对他们的方法应用于大规律逻辑运算时的优、缺点进行了讨论。

1 DNA 计算

1994年，美国加利福尼亚大学的Adleman 博士提出利用DNA（脱氧核糖核酸）对一个图论中的NP-完全问题-有向图的Hamilton 路问题进行编码，借助连接、变性、复性、PCR 扩增、电泳等生物操作可以求解出这一问题[1]。

经过二十多年的发展，关于DNA 计算领域的研究成果非常丰富。特别是近年来DNA 自组装的研究引起了学者们的兴趣，并取得了很多的研究成果。DNA 自组装是指以DNA 分子为基本材料，通过分子间的碱基氢键、范德华力等微作用力自发缔结成结构稳定的聚集体或超分子结构。1963年，Wang[2]提出了“Wang Tile”的概念，并指出Wang Tile 可以通过自组装过程，在二维平面形成周期性格局，而且该过程被证明具有图灵机等价的计算能力，然而直至20 世纪90年代，DNA自组装技术才变为现实。

2 逻辑门在DNA 计算中的实现

通用图灵机是计算机科学中一个抽象的计算模型。图灵在1936年的文章中详细描述如此的构思。现代通用电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段程序，并运行程序实现该程序所描述的算法。各种各样的逻辑门所构成的逻辑电路是现代通用电子计算机实现计算的功能单元，最常见的逻辑门有“与”、“或”、“非”，“异或”门。自Adleman 教授开创了DNA 计算以来，研究人员一直致力于DNA 计算机的研制。

1996年，Ogihara 和Ray 最先给出了基于DNA 分子的布尔电路模拟[3]。2004年，Wenbin Liu 等利用两个GGG 序列诱导的DNA 分子发夹结构模拟了NAND[4]。2006年，我们给出了基于分子信标的与门、或门的实现[5]。2011年，Science[6]报道了加州理工学院计算机系的Winfree 教授课题组在试管中利用可逆的DNA 链置换技术实现逻辑门，并模拟了含有一个3 层、6 个逻辑门的生化电路，求解了四位二进制数的平方根。该生化电路初始状态含有74 种DNA 链，当编码输入的DNA 链被加入试管后，电路被启动进行运算，此时试管中共有130种长度为15-33 个碱基的DNA 链相互作用，最后通过荧光输出计算的结果。这一成果是目前报道的利用DNA 来模拟通用计算机进行计算最好的结果，我们将在下节做详细的介绍。

3 链置换技术和逻辑门实现

2011年，Winfree 等应用的DNA 链置换原理构造了Seesaw 门并利用级联的Seesaw 门模拟逻辑门，求解了含有一个3 层、6 个逻辑门的生物电路。Seesaw 门是整个生物电路的基本组件，它由4 种DNA 链组成：输入链（Input）、门链与输出链的复合链（Complex）、Fuel 链、阈链Th（Threshold），如图1 所示。

图1 Seesaw 门示意图及DNA 链编码

图1A 给出了Seesaw 门的示意图，图1B 中给出了构成Seesaw 门的DNA 链的编码及构形，Complex 为稳态的部分双链DNA。这里要注意的是，输出链（Output）在链置换反应发生前是杂交在门链上形成部分双链的复合物（Complex），在图B 中表示为3T2（5’→3’方向）。阈链Th 也是稳态的部分双链DNA，由于阈链Th 中1*T*2* 的长度大于门链T*2*，当输入链2T1 被加入时，它们首先和阈链发生链置换，直至阈链完全反应，剩余的输入链才会和复合链发生链置换。阈链的作用是控制参与链置换的输入链的数目。输入链Input 和输出链Output 为DNA 单链，它们分别由门的编码和输入、输出编码两部分构成，当Seesaw 门的输入或者输出多于2 个时，输入、输出链长度不变，只要对应修改输入或输出的编码而其它结构无需改动。Fuel 链4T2 也是DNA 单链，它不是Seesaw 门必选的组件，由于链置换是可逆的过程，输出链也会置换输入链，它与输出链竞争，通过设置浓度大于输入出链，则可以实现对链置换方向的控制，被反向置换的输入链再次置换输出链又可实现置换结果的放大。

逻辑门由两个Seesaw 门级联构成（图2B），左侧第一个Seesaw 门3 用于接受逻辑门的输入链3T1、3T2，右侧第二个Seesaw 门4 受第一个Seesaw 门链置换后的输出链4T3，设置吸收该链的阈链的浓度控制第二个Seesaw 门参与置换的链来实现逻辑门的功能，若逻辑门的计算结果为1，则能检测到第二个Seesaw 门的输出链5T4，为保证有效地检测到输出链，第二个Seesaw 门设置了Fuel 链6T4。

图2 Seesaw 门级联实现逻辑门

逻辑与门、或门结构相同，区别在阈链浓度不一样。为了便于讨论，我们分别用符号C（浓度）表示参与链置换反应的DNA 链的浓度，ANDTh表示与门的阈链，ORTh 表示或门的阈链，一般而言，C（ANDTh）=2 C（ORTh），C（InputN）＞C（ORTh），N=1，2。当逻辑门的输入Xi=1(i=1，2)时，加入代表Xi=1 的输入链3T1、3T2；反之，若Xi=0(i=1，2)，不加入输入链。显然，对于逻辑与门而言，若C（Input1）+C（Input2）>C（ANDTh），则必然能够检测到第二个Seesaw门的输出链，而这一条件只有当输入变量均为1、对应输入链均被加入才能成立；对于或门而言，若C（Input1）+C（Input2）>C（ORTh），则必然能够检测到第二个Seesaw 门的输出链，而这一条件只须任一输入变量为1、对应输入链被加入就能成立。

4 讨论

DNA 计算自1994年出现，经历将近二十年的发展，在计算理论、生物技术可靠性上都已取得丰富的成果。虽然目前DNA 计算在运算速度上还不具备优势，虽然目前还不清楚DNA 计算机能否代替传统计算机，但对DNA 计算机的研究必定会促进计算机科学、信息学和分子生物学等相关学科的发展、必定会深化人们对生命现象本质的认识。

［1］Adleman L..Molecular Computation of Solution to Combinatorial problems[J].Science，1994，66（11）：1021-1024.

［2］Wang H.Dominoes and AEA case of th decision problem[C]//Proceeding of the symposium Mathematical Theory of Automata.New York，1963：23-55.

［3］Ogihara.M，Ray.Simulation Boolean Circuits ON a DNA computer [J].Algorithmica，1999（25）：239-250.

［4］Wenbin Liu，Xiaolong，Shi，Shenmin Zhang，Xiangrong Liu，Jin Xu，A new DNA computing model for NAND gate based on induced hairpin formation[J].Biosystem，2004，77：87-92.

［5］Cui Jianzhong，Yin Zhixiang，Wang Wei，et .al..Towards Reliable Simulation of Bounded Fan-in Boolean Circuits Using Molecular Beacon [C]//Proceedings of the 6th World Congress on Control and Automation，June 21－23，2006，Dalian，China，5：3910-3914.

［6］Lulu Qian，Winfree E.Scaling up digital circuit computation with DNA strand displacement cascades[J].Science，2011，332：1196－1201.