基于分子信标的逻辑门的计算模型

刘文斌　朱翔鸥　殷志祥

摘 要：基于DNA计算的布尔电路的模拟是DNA计算研究中的一个非常具有应用前景的潜在的研究方向。利用分子信标和三链核酸分子的高度特异性及稳定性，提出了一个逻辑与、逻辑或门的DNA计算模型。基于分子信标的二种状态，将逻辑门的信息处理过程分为计算和输出二个子过程，从而使得这种基于DNA分子的逻辑门具有重复可用性，为构建基于DNA分子的大规模集成电路奠定了基础。

关键词：DNA计算；逻辑门；分子信标；三链核酸

中图分类号：TP18文献标识码：A文章编号：1672-1098(2008)01-0065-05

收稿日期：2007-08-13

基金项目：国家自然科学基金资助项目(60403002，30570431)；中国博士后科学基金资助项目(2004036130)；浙江省自然科学基金资助项目(Y106654，Y405553);安徽省教育厅自然科学基金资助项目(2006kj068A,KJ2007B173);安徽省优秀人才基金，教育部新世纪优秀人才支持计划资助项目(NCET-06-0555);国家863高技术研究发展计划项目基金资助项目(2006AA01Z104)

作者简介：刘文斌(1969-)，男，陕西西安人，副教授，博士，主要从事生物信息学及DNA计算的研究。

A Computing Algorithm for Logical Gates Based on

Molecular Beacon

LIU Wen-bing1,ZHU Xiang-ou1,YIN Zhi-xiang2

(1．College of Computer Science and Engineering, Wenzhou University, WenzhouZhejiang 325027, China；2．School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China)

Abstract:Boolean Circuit simulation based on DNA computation is one of the potential development direction in DNA computation. An algorithm of DNA computation for logic “AND ” and “OR” gates based on Molecular Beacon technique and big speciality and stability of Triple Helix Nucleic Acid molecule. On the basis of both states of Molecular Beacon, information processing of logic gates is divided into two subprocess, computing and output, which makes logic gates reusable. It makes possible to construct VLSI based on DNA computation.

Key words:DNA computation; Logic gate ; Molecular Beacon; Triple Helix Nucleic Acid

DNA计算是近年来出现的一种新的方式［1］。人们在研究NP－完全问题的DNA计算模型的同时，也在开始探索新的潜在的应用，构建基于DNA的布尔电路就是其中一个研究方向。1996年，Ogihara等首次提出了基于DNA的布尔电路的模拟，并且给出了逻辑电路的DNA实现方法［2］。随后，文献［3-4］提出一种改进的逻辑与非门的DNA计算模型，并说明了如何通过这种逻辑门实现二个阶矩阵的传递闭包的计算。文献［5］提出了另一个逻辑与非门的DNA计算模型。所有这些计算模型都存在二个缺点：①由于限制性内切酶的作用，执行运算后的逻辑门也随之水解，因此不能重复利用；②这些逻辑门的DNA模型都是基于试管方式的，不利于在芯片上实现大规模的布尔逻辑电路。在文献［6］提出的“鞭子”PCR（Whiplash PCR）方法的基础上，文献［7］提出了应用这种“鞭子”PCR来实现布尔电路的思想。尽管在理论上是可行的，但是随着计算过程的进行，单链DNA分子的长度不断增加，这种“鞭子”PCR能否按照设定的程序执行就很难确定了。2004年，文献［8］提出了一个基于吡啶二聚物的诱导发夹结构的逻辑“与非”门的DNA计算模型，克服了以往每次执行完特定运算后逻辑不能重复使用的缺点。本文通过二次诱导“发夹”的形成过程来分别完成逻辑与非门的计算和输出过程，该模型具有简单、可靠性高的优点，且容易结合现在的生物芯片技术构建基于DNA的大规模集成电路。

1 布尔电路

在可计算性理论中，布尔电路与图灵机是相等价的并行计算模型［9］。一个有玭个输入m个输出的限定型布尔电路实际上可以看作一个有向无圈图G，其中包含二类节点：入度为1的n个输入节点；入度为2出度为1的m个逻辑门节点。有向边代表了电路中信息的传输方向。因此，一个有n个输入m个输出布尔电路实际上就是计算如下的布尔函数

f(X璶)∶＜0.1＞n→＜0.1＞m（1）

常见的逻辑门主要有：与门（AND）、或门（OR）、与非门（NAND）、异或门（XOR）等。逻辑门的完全基就是一个能够表示任何一个布尔电路的最少的逻辑门的集合。常见的或门（OR）和与门（AND）就是一个完全基，即Ω=｛∨，∧｝。数学上已经证明，任何一个布尔电路都可以在多项式时间转化为一个标准的层状结构（即每层为单一的一种逻辑门）［10］(见图1)。衡量布尔电路规模通常的二个指标为：逻辑门的层数和总数。

图1 布尔函数玣(x1,x2,x3,x4)=(x1∨x2)∧(x3∨x4)的

布尔电路2 分子信标及三链核酸

2.1 分子信标

“发夹”结构是一种在单链分子DNA或RNA分子中经常出现的二级结构，当DNA分子或RNA分子上存在相互互补的序列时，在适当的条件下它们就会杂交从而形成“发夹”结构。 分子信标是一种特定的“发夹”结构，主要由二部分组成：环部（Loop）和径杆（Stem）部分。当径杆部分解链后“发夹”就会打开从而变成单链分子(见图2)。通常有二种方法打开“发夹”结构：（1）加热或加入尿素（Urea）等碱性试剂；（2）如果存在一个和环部序列互补的DNA分子，并且它们杂交后的氢键结合力远大于径部杂交的结合力，环部杂交后产生的张力就会破坏径杆部分的氢键结合力使得径杆部分解链。因此通过设计适当的环部序列和径杆序列的长度，GC含量就可以对“发夹”的形成与打开进行有效的控制。尽管在DNA计算中我们希望尽量避免“发夹”结构的产生，但是通过精心设计的发夹结构却有很多特殊的应用（如文献［11］的可满足问题的计算模）。此外，由于“发夹”具有结构简单，易于控制等优点，已经广泛的应用于生物传感器和分子的自组装等方面［12-13］。

图2 “发夹”的闭合与打开示意图

在通常情况下，DNA分子中是AT相互配对，GC相互配对。但是，在吡啶二聚物（Naphthyridine Dimmer）分子出现的情况下，也可以实现二个GG之间配对。原因是吡啶二聚物的二臂上分别有三个氢键结合位，它们可以分别和鸟嘌呤（Guanine）上的三个氢键结合，从而使得G－G配对［14］。利用这种性质，E. Smith等在镀金的表面设计了一种通过吡啶二聚物分子诱导形成的“发夹”结构的分子信标［15］。其环部序列长度为16bp，径部序列为

5′-AAAGGGTTTGGGT-3′

3′-TTTGGGAAAGGGA-5′

其中包含二组－GGG－序列。当在表面上加入吡啶二聚物时，在它的作用下这6对G-G相互配对，从而大大增强了径部序列的结合力，于是和环部杂交的序列解链，“发夹”结构形成。当从表面上清除掉吡啶二聚物时，“发夹”结构就会打开。由于吡啶二聚物可以很容易的从表面上清洗掉，所以“发夹”闭合与打开非常容易控制。这种“发夹”的开与关和通常电子电路中的开关非常相似。因此，通过分子信标模拟逻辑门具有很大的优势。

2.2 三链核酸

1957年，文献［16］首次提出了三链核酸的概念，即某些基因中包含特定的同聚嘌呤或嘧啶序列，在适当条件下由三链形成寡核苷酸占据在双链大沟处，通过与双链碱基特异性产生Hoogsteen 或反Hoogsteen 氢键而连接，从而形成三螺旋结构即三链DNA。1963 年和1964 年，文献［17-18］分别报道了质子化poly(rC)和poly(rG)•poly(rC)双螺旋能发生相互作用而形成三螺旋RNA。1987 年，Mirkin［19］等在一种酸性质粒中发现了一种三螺旋DNA，为三链DNA 可能在体内存在提供了强有力的证据。由于期间发生C→C+质子转化，故此他将这种结构称为H-DNA。三螺旋DNA的研究有助于深入理解细胞过程，揭示某些基因疾病的形成机理，为建立新的基因疗法提供全新的思路。长期以来, 对三链核酸的研究是与探索其潜在的生物学功能联系在一起的。目前在体内和体外环境形成三链已不是一件困难的事。

一般来讲，要形成三链核酸，寡聚脱氧核苷酸（ODN）的长度应不少于10个核苷酸，根据条件的不同对寡聚脱氧核苷酸长度的要求也有变化。文献［20］发现在大肠杆菌RecA蛋白及ATPγS的存在下, 寡聚脱氧核苷酸要形成平行三螺旋, 识别其同源双螺旋DNA，至少要有15个核苷酸, 但其中只要有8个是同源序列就够了。如同源序列含有26个核苷酸, 即使除去RecA蛋白, 它们之间仍能保持彼此结合的状态［21］。2004年，文献［22］发现寡聚脱氧核苷酸在RecA蛋白及ATPγS的存在下，与线性双螺旋DNA可形成稳定的三链结构。在形成的过程中，首先寡聚脱氧核苷酸在ATPγS的存在下与RecA蛋白结合，然后在目标双螺旋DNA上寻找同源序列，这一过程非常迅速并且不打开DNA双链。同源的双链找到后，寡聚脱氧核苷酸在RecA蛋白的介导下与目标双螺旋DNA形成三链DNA（见图3）。经证实由RecA蛋白介导形成的三链DNA是相当稳定的［23］。

3 逻辑与门和或门的计算模型

为了克服文献［2-5,8,9］中与非门计算模型的缺点，将逻辑门的工作过程分为二个过程：计算过程和输出过程。在计算过程中逻辑门对其输入进行计算，计算结果是通过分子信标的状态，即是“发夹”结构还是线性结构；输出过程是通过加入特定的输出单链分子形成三链核酸DNA分子，来判断并输出最终的输出结果。

图3 RecA蛋白介导下三链DNA的形成过程3.1 逻辑门的编码方法

表示逻辑门的DNA分子的5端固定在固体表面上，主要由二部分组成：表示变量玿1,x2的序列和在其二边的长度为k的径杆序列s和s，s和s将在适当的条件下形成“发夹”的部分。逻辑门的二个输入变量x1,x2分别用长度为2l的DNA序列表示。我们约定输出变量珃的编码由变量x1后半部分和x2的前半部分的补序列构成。为了将表示逻辑门的DNA序列和固体表面隔开，与非门的DNA分子的5端有一段隔开序列（见图4）。

图4 固定在表面上的DNA逻辑门的示意图径杆部分的作用主要是对输入执行计算功能，对于序列玸和s的编码要求为：①具有一定数量的－GGG－序列对，使得只有在吡啶二聚物（Naphthyridine Dimmer）存在的条件下，它们才有可能互补杂交；②对于逻辑与门，径杆部分杂交时的结合力要大于环部任意长度为2l的序列杂交时的结合力， 而小于长度为4l的序列杂交时的结合力； ③对于逻辑或门， 径杆部分杂交时的结合力要小于环部任意长度为2l的序列杂交时的结合力。

3.2 算法步骤

（1） 将编码逻辑门的DNA分子固定在经过化学修饰的固体表面（见图5）。

（2） 当输入变量玿璱(i=1,2)为“1”时，在表面加入表示与其互补序列的DNA分子，它们就会和逻辑门上的对应序列杂交；而输入为“0”时则不加入任何分子。同时，加入DNA连接酶，当二个输入同时为“1”时它会将二个输入序列连接起来（见图5中的与门）。杂交反应完成后用缓冲液清洗干净表面。

图5 DNA逻辑与门、或门的四种输入情况示意图（3） 在表面上加入吡啶二聚物分子。对于与门，除第一种情况之外其它三种输入都会形成“发夹”结构；而对于或门，除前三种输入情况保持部分双链不变外，最后一种情况形成“发夹”结构。到此为止，二种DNA逻辑门的计算过程就已经完成。计算结果为“1” 为线性双链分子，结果为“0”的形成“发夹”结构（见图6）。

对于或门为了方便结果输出，在表面同时加入与二个输入变量互补序列的DNA分子及DNA连接酶，这时，第一、第四种输入情况的分子不会有变化，而第二、第三种输入情况的DNA分子会变成和第一种输入情况相同。

图6 诱导“发夹”结构的形成（即计算过程）（4） 清洗表面残余物及吡啶二聚物分子，“发夹”结构就会打开变成单链DAN分子（见图7）。

图7 “发夹”结构打开示意图（5） 在表面上重新加入吡啶二聚物分子，只有单链状态的逻辑门的状态会恢复“发夹”状（见图8)。图8 单链状态恢复“发夹”状态示意图（6） 将输出序列珃与RecA蛋白，ATPγS混合，在适宜的条件下哺育，使RecA蛋白包裹输出序列形成RecA蛋白-珃复合体。当这些RecA蛋白-珃复合体加到表面后会与线性状态的双链DNA分子在特定的位置形成稳定的三链DNA结构（见图7）。此时，所有输出为“1”的逻辑门都会形成三链核酸DNA分子。

（7） 通过降低盐浓度的梯度解离三链DNA结构，输出分子被洗脱下来，对其进行脱蛋白、纯化等处理就可以做为下一级与逻辑门的输入或者整个布尔电路的一个输出。同时，由于清洗“发夹”结构径杆部分的吡啶二聚物分子也会被清除，从而打开“发夹”结构。

（8） 对表面加热或者加入尿素等碱性溶剂， 解链的在计算过程中形成的双链DNA分子。 最后， 清洗干净表面后就可以在下一次逻辑计算中重新使用。

4 结论

本文给出了一个基于诱导“发夹”型的逻辑与门、或门的DNA计算模型，和现有的计算模型相比，优点如下：①由于逻辑门的整个处理过程分为计算过程和输出过程，因此，在完成每次逻辑计算后与非门可以重复使用；②这种诱导“发夹”对DNA分子间杂交反应具有很高的特异性，因此，大大提高了DNA逻辑门计算过程的可靠性；③三链核酸分子具有很高的稳定性和特异性，从而保证了输出过程具有很高的可靠性；④逻辑门的计算过程及结果输出只需二次发夹结构的形成就可完成，因此操作非常方便；最后，因为这种诱导“发夹”型的DNA逻辑门的计算模型是基于表面方式的，因此随着生物芯片技术的飞速发展，构建这种基于DNA逻辑门的计算芯片将成为可能。

参考文献：

［1］ ADLEMAN L.Molecular computations to combinatorial problems［J］.Science,1994,266:1 021-1 024.

［2］ OGIHARA M,RAY A.Simulating Boolean circuits on a DNA computer［J］.Algorithmica,1999,25:239-250.

［3］ AMOS M,DUNNE P E,GIBBONS A.DNA Simulation of Boolean Circuits［M］.Proceedings of the Third Annual Conference,July 22-25,1998,University of Wisconsin,Madison,Wisconsin,San Francisco,CA：679-683.

［4］ DUNNE P E,AMOS M,GIBBONS A.Boolean Tra-

nsitive Closure in DNA.In Computing with Bio-Molecules:Theory and Experiments［R］.George Paun (Ed.),Springer-Verlag,Singapore,1998.

［5］ MULAWKA J J,WASIEWICZ P,PLUCIENNICZ-

AK A.Another Logical Molecular NAND Gate System［M］.Seventh International Conference on Microelectronics for Neural,Fuzzy and Bio-Inspired Systems,Granada,Spain 1999：340-346.

［6］ HAGIYA M,ARITA M,KIGA D, et al.Towards Parallel Evaluation and Learning of Boolean u-Formulas with Molecules［M］.DNA Based Computers III,DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999：57-72.

［7］ WINFREE E.algorithmic self-assembly of dna［R］.Ph.D thesis,California Institute of Technology,1998.

［8］ LIU W B.A new DNA computing model for the NAND gate based on induced hairpin formation［J］.BioSystems,2004,77:87-92.

［9］ DUNNE P E.The Complexity of Boolean Networks［R］.Academic Press,1998.

［10］ HARRISON M A.Introduction to switching and automata theory［R］.McGraw-Hill,1965.

［11］ CUKRAS A R,FAULHAMMER D,LIPTON R J,et al.Chess games:A model for RNA-based computation［J］.Biosystems,1999,52:35-45.

［12］ NAKATANI K,SANDO S,SAITO I.Improved Selectivity for the Binding of Naphthyridine Dimer to Guanine-Guanine Mismatch［J］.Bioorg.Med.Chem.Soc.2001(9):2 381-2 385.

［13］ NAKATANI K,SANDO S,SAITO I.Scanning of guanine-guanine mismatches in DNA by synthetic ligands using surface plasmon resonance assay.Nat［J］.biotechnol.2001,19:51-55.

［14］ NAKATAN K,SANDO I S,SAITO I.Recognition of Guanine-Guanine Mismatches by Dimeric Form of 2-Amino-1,8-naphthyridine［J］.J.Am.Chem.Soc.2001,123:12 650-12 657.

［15］ SMITH E A,KYO M,KUMASAWA H.Chemically Induced Hairpin Formation in DNA Monolayers［J］.J.Am.Chem.Soc.2002,124:6 810-6 811.

［16］ FELSENFELD G.Formation of a three-stranded polynucleotide molecule［J］.J Am Chem Soc,1957,79 (7):2 023-2 024.

［17］ LIPSETT M V.Complex Formation Between Polycytidydic Acid and Guanine Oligonucleotides［J］.J.Biol.Chem.,1964,239:1 256-1 259.

［18］ HOWARD F B,FRAZIER J,LIPSETT M N.Infrared Demonstrated of Two-and Three-Strand Helix Formation Between Poly and Guanosine Mononucleotides and Oligonucleotides［J］.Biochem.Biophys.Res.Commun.,1964(17):93-102.

［19］ MIRKIN S M,LYAMICHER V I,DRUSHLYAK E.DNA Hform requires a homopurine-homepyrimidine mirror repeat［J］.Nature,1987,330 (6147):495-497.

［20］ HSIEH P,CAMERINI O.Pairing of homologous DNA sequences by proteins:evidence for three-stranded DNA［J］. Genes Dev, 1990(4): 1 951-

1 963.

［21］ 孙雪光,曹恩华.三链核酸稳定性和生物学功能的研究进展［J］.生物化学与生物物理进展,1998,25(4):319-324.

［22］ SHIGEMORI Y, OISHI M. Specific cleavage of

DNA molecules at RecA-mediated triple-stranded structure［J］.Nucleic Acids Research,2004,32(15):4 563-4 575.

［23］ RAO B J, DUTREIX M, RADDING C M. Stable

three-stranded DNA made by RecA protein［J］. Pro Natl Acad Sci USA, 1991, 88 (8): 2 984-2 988.

［24］ GUARNIERI F,FLISS M,BANCROFT C.Making DNA add［J］,Science,1996, 273(12):220-223.

［25］ BERARD Y,ALLEN P,MILLS J R,et al.DNA implementation of addition in which the input strands are seperated from the operater strands［J］.Biosystem,1999,52:165-174.

［26］ HUG H,SCHULER R.DNA-based parallel computation of simplearithmetic［M］.7th international Workshop on DNA-Based Computers,Tampa,U.S.A.,2001：159-166.

(责任编辑：李 丽)