基于DNA链置换反应的自然数素性判定问题研究

基于DNA链置换反应的自然数素性判定问题研究

王子成1,3，豆根生2，周小刚2，叶盟盟1

(1.郑州轻工业学院 电气信息工程学院，河南 郑州 450002；2.河南农业大学 理学院，河南 郑州 450002;3.河南省信息化电器重点实验室，河南 郑州 450002)

摘要：借助自组装DNA计算的显著优势，采用DNA链置换反应原理开展了自然数的素性判定问题研究.首先，构造了有关DNA分子逻辑门，并构建了相应的DNA分子计算模型，然后设计了用于自然数素性判定的分子逻辑电路.最后基于Visual DSD仿真平台，对分子逻辑电路进行仿真.结果表明:采用的分子逻辑电路能够实现自然数的素性判断.

关键词：DNA链置换；素性判定；逻辑电路

收稿日期:2015-06-01；

修订日期：2015-07-10

基金项目:国家自然科学基金资助项目(U1304620);河南省教育厅科学技术研究重点项目(13A413371)

作者简介:王子成(1976—), 河南永城人, 郑州轻工业学院讲师,主要从事系统建模与仿真研究，E-mail：wzch@zzuli.edu.cn.

通讯作者：周小刚(1979—),河南焦作人，河南农业大学讲师,主要从事电路与通信工程研究,E-mail：20331476@qq.com.

文章编号:1671-6833(2015)05-0096-05

中图分类号：TP384

文献标志码：A

doi:10.3969/j.issn.1671-6833.2015.05.021

Abstract:The prime number judgement is an important theoretical issue in natural number study field. Based on the significant advantages of DNA computing, the DNA strand displacement reaction is used to carry out the prime problem determination study in this paper. Firstly, the molecular logic gates are constructed, and then the corresponding molecular computing model is set up, meanwhile, the molecular logic circuit for prime number judgement is constructed. Finally, the simulation results based on Visual DSD platform show that molecular logic circuits are viable to carry out prime number judgement.

0引言

素数指大于1的自然数中，仅能被1及其自身整除的数.自然数的素性判定研究具有深远的理论意义.伴随着现代密码学的兴起，开展大数的素性判定研究已成为一个新课题，其在信息安全领域具有重要的应用价值.

基于素数理论，密码学领域可实现信息的有效加密.自然界中，多数生物体为了最大程度避免天敌，其生命周期也呈现素数性.在害虫的生长周期内，若使用素数次杀虫剂则可有效抑制病虫害.

试除法是素数判定算法中最基本的算法，此外还有AKS，Baillie-PSW和Miller-Rabin等算法.但当自然数为多位数时，计算量非常庞大.且其中Miller-Rabin算法已经被证实存在错误率.RSA公钥加密算法是目前最有影响力的加密算法，但也仅能强力破解短RSA钥匙.可见，探索用于自然数素性判定的新型算法，降低判定难度，缩短计算时间，以提高自然数的素性判定速度及效率，进而实现合数的素因子分解，具有深远的理论研究及现实意义[1].

DNA计算[2]独特的信息存储方式及巨并行计算能力使其成为了一种新颖计算模式.其中，DNA链置换反应能够在室温下进行，无需外力作用，反应周期短，最近成为一个热门研究课题[3-5].笔者基于DNA链置换反应，设计了用于四位二进制数素性判定的计算模型.该模型可在室温下进行，操作简单，易于实现，产率较高，能充分体现DNA计算优势.

1DNA链置换反应

DNA链置换反应是指单链DNA分子能够与部分互补的DNA双链结构产生反应，并能释放出原有双链结构中的单链DNA分子，生成新的双链DNA分子结构的过程[6-7].具有部分互补结构的双链DNA分子，含有悬挂形式的黏性末端，分子处于热力学非稳定状态.加入与原始双链DNA分子的长链完全匹配的单链DNA分子时，根据系统的自由能最低原理，通过单链DNA分子间的杂交匹配及替换过程，能够生成更加稳定的双链DNA分子结构.最终实现了以较长单链DNA分子为输入信号，以新的较短单链DNA分子为输出信号的信号传输过程.

DNA链置换反应的基本过程如图1所示.含有黏性末端t*的双链DNA分子结构A中，DNA子序列x及x*部分为完全互补匹配，原始构型的DNA分子A因为具有悬挂状态的黏性末端，处于热力学非稳定状态.当输入结构为tx的单链DNA分子时，其中的子序列t能与A中的t*黏性末端通过碱基匹配而键合.之后，分子tx中的x部分逐步将A中的x部分剥离出来，最终形成具有稳定结构的双链DNA分子B，并输出单链DNA分子x，完成链置换过程.将多个DNA链置换反应结合成网络回路，可实现某个逻辑运算.

图1　DNA链置换的基本过程

近年来，DNA链置换反应在分子计算、纳米机器及疾病诊断和治疗等领域都得到深入研究，已成为纳米科学领域的重要课题.2006年，Seelig等基于链置换反应原理，设计出与门、或门、非门等逻辑模块，利用这些模块组合成逻辑电路[8].2010年，QIAN改进设计了单个的门单元，使得逻辑门的设计更加模块化和标准化[9].2011年，QIAN设计了计算四位二进制数平方根的逻辑电路，用DNA链组成四个相互联系的人工神经元，通过猜心术游戏，证明了DNA分子神经网络具有一定的逻辑推理能力[10-11].2015年，Cheulee等人基于DNA链置换反应，将核酸电路用于诊断研究[12].

2自然数素性判定的DNA计算模型

2.1逻辑电路

逻辑电路基于二进制编码机制，通过离散信号的传递和处理，最终实现数字信号的逻辑运算和操作.基本逻辑电路有与门、或门、非门、异或门及与非门等.已广泛用于计算机、数字控制、通信、自动化和仪表等诸多领域.

判定四位二进制数对应的自然数素性时，相应的逻辑电路如图2所示.图中的逻辑电路由4个与门、3个或门和3个非门组成.I0～I3分别表示四位输入信号，P为输出信号，其输出为输入数字的素性判定结果.当输出P为1时，表示输入为素数；当输出P为0时，则表示输入为非素数.如I0=1，I1=0，I2=0，I3=0时，对应的输入信号为1000，该逻辑电路用于对十进制数字8的素性进行判断.此时对应的输出信号P为0.

图2　四位二进制数的素性判定逻辑电路

2.2分子逻辑门及放大器

逻辑门为条件开关，仅当输入信号满足一定条件时，逻辑门才会“打开”，输出信号.图2中用到了3种基本逻辑门——与门、或门、非门.笔者根据3种逻辑门的“打开”条件，设计与其对应的基于DNA链置换反应的分子逻辑门.

(1)分子与门 对于2输入的与门，仅两个输入都为逻辑1时，与门才能“打开”，此时输出为逻辑1，否则，输出为逻辑0.笔者设计的分子与门见图3所示.图3(a)中，单链DNA分子ts1和ts2t对应于逻辑门中的两个输入信号，链s2ts3为输出信号链.

当仅输入为信号链ts1或ts2t时，分子与门无信号链输出.仅当同时输入信号链ts1和ts2t时，才能确保置换反应正向进行，输出正确的信号链s2ts3，最终完成逻辑运算过程.其中，输入信号链ts1用于置换出分子与门中的单链s1t.输入信号链ts2t作用有二：①防止单链s1t与链ts1之间再次产生置换反应；②通过置换反应释放分子与门中的单链s2ts3.为方便分子逻辑模型的构建，设计出分子与门的等价符号，如图3(b)所示.其中，“○”内数字表示分子与门的初始浓度，“○”外数字表示输入信号链的分子浓度.

图3　分子逻辑与门结构及符号

(2)分子或门 2输入分子或门中，当两个输入信号链中有一个逻辑值为1时，或门就可“打开”，输出为逻辑1；仅当所有输入都为逻辑0时，才能输出逻辑值0.根据或门的触发条件，笔者设计的分子或门如图4所示.

图4　分子逻辑或门结构及符号

图4(a)中，分子或门的输入信号分别为链s2ts3和链s4ts3.二者都含有部分单链s3，都能够置换出分子或门中的单链s3.图4中输入信号链的分子结构能够避免置换反应的逆过程，有利于最终输出正确的信号链，完成或逻辑运算过程.

图4(b)为分子与门的等价符号，“○”内数字表示分子或门的浓度，“○”外数字表示输入信号链的浓度.

(3) 分子非门笔者中采用两种不同链的分别表示逻辑1和逻辑0.

2.3分子放大器

DNA链置换反应过程中存在如下几种影响反应速率和产率的因素

(1)输入信号链DNA分子，不可能全部参与置换反应；

(2)随着反应进程的推进，输入信号链分子浓度逐渐降低，从而降低反应速度；

(3)单链DNA分子在置换过程中，会出现碱基错配和降解现象.

含有多个链置换反应的计算模型中，上述因素将会影响到输出产物的数量，甚至产物的正确性.为了确保链置换反应的顺利进行，提高输出信号链在反应产物中的比例，笔者设计了基于DNA链置换反应的分子信号放大器，用于提高输出信号链的浓度.其结构与工作原理如图5所示.

图5(a)为分子放大器模型.单链ts5为输入信号链，单链s5t为燃料链，单链s5ts6则为输出信号链.DNA链置换反应是在溶液中进行的，为了表述方便笔者设定输入信号链ts5的分子数量为1倍浓度(图中标注为“I = 1×”)，双链结构的DNA分子数量为2倍浓度(图中标注为“A=2×”)，燃料链s5t为4倍浓度(图中标注为“F=4×”).加入输入信号链ts5前，双链结构和燃料链s5t间无反应.信号链输入前，双链结构和燃料链间无反应.加入输入信号链ts5后生化反应过程，如图5(c)所示.实线箭头表示正反应方向，虚线箭头表示逆反应方向.输入信号链ts5就像一个“打开”信号，触发了位于顶部位置的链ts5、链s5ts6及链s5t和位于底部位置的链t*s5*t*之间的反应.因此，即便有少量的输入信号链，只要提高燃料链对底部链t*s5*t*的占有率，就可以得到较多的输入信号链.分子放大器结构中，可以通过提高双链结构和燃料链的浓度来提高输出信号链的产量，从而达到信号放大的作用.图5(b)为分子放大器的等价符号.

图5　分子放大器及其反应过程

3分子逻辑电路

笔者构建了自然数素性判定的分子逻辑电路，如图6所示.该逻辑电路能对四位二进制数的素性进行判断.图中标注的数字分别表示各种DNA分子的分子浓度.

图6中输入信号的逻辑1和0分别对应两种单链DNA，因此，共有8种输入信号链，分别表示为I00、I10…I03、I13，通过对应的8个分子放大器将输入信号放大.输入信号I0=1和I3=0对输出结果无影响，但为了保留逻辑电路的完整性，确保分子逻辑电路的鲁棒性，分子逻辑电路中仍然保留这两个信号.图中P为输出信号.在分子逻辑电路中，当分子逻辑电路中有信号链输出时，P的取值为1，此时，所输入的自然数判定为素数；反之，输出P取值为0，所输入的自然数判定为非素数.

4仿真结果

图6所示的分子逻辑电路，可实现自然数的素性判断.笔者在Visual DSD软件平台中，对分子逻辑电路的运算过程进行仿真，验证了本分子逻辑电路的可行性与运算结果的准确性.Visual DSD是由Matthew Lakin等人[13-14]设计，主要用于构建和分析DNA链置换计算模型.采用图6中的分子逻辑电路，以1 ～ 15之间自然数的素性判定为例，Visual DSD的仿真结果如图7所示.

图6　用于四位二进制数素性测试的分子逻辑电路

在分子逻辑电路运算过程中，4条输入信号链和输出信号链P的分子浓度变化曲线体现出非常明显的阶段性特征.

第一阶段：加入4种输入信号链，先与对应的分子放大器发生链置换反应，刚开始反应物浓度高，反应速度快.因为该分子模型的反应是逐级进行的，此时并无链P生成；

第二阶段：随着链置换反应的逐步深入，输入信号链的浓度趋于稳定，有些输入情况中有链P产生，并且链P的产率不断增加；

第三阶段：输入信号链浓度平稳，有链P产生情况中，链P的生产速率逐渐降低，最后趋于平缓，如图7所示.

图7中，用于表征纵坐标的信号链分子浓度比是指输出信号链的分子浓度所占整个反应体系中所有分子浓度的比值，仿真实验中反应时间单位为1 000 s.若输入信号链对应的自然数为2, 3, 5, 7, 11, 13，有信号链P输出，对应自然数1～15内的素数，证明了分子计算模型的正确性.在链P有浓度变化的情况中，链P的浓度变化曲线呈“S”形.这与反应物的浓度有关.

图7Visual DSD平台下分子逻辑电路的仿真结果

Fig.7The simulations of logic circuit based on Visual DSD

图中输入信号链定义为1倍浓度，而信号链P的最终输出浓度约为输入信号链浓度的2倍，表现出分子放大器的信号放大作用.输入信号链的浓度之所以在平稳后出现波动性变化，且变化幅度不大，是因为输入信号放大器中大部分的底部链被燃料链占据，使得分子计算模型后续生化反应对输入信号链的浓度影响不大.

5结论

DNA链置换反应在常温下自发进行，成本低，操作简单.笔者将DNA链置换反应用于自然数的素性判定问题研究.设计了可执行逻辑运算的DNA分子逻辑门以及具有信号放大作用的DNA分子放大器.构造了用于自然数素性判定的分子逻辑电路.反应过程中，可对目标信号链浓度进行扩增，便于输出信号链的提取，能够有效实现信号传输与处理，保证了传输信号的安全性与有效性.

利用DSD平台对1～15之间的自然数的素性判定进行了仿真，结果表明，笔者设计的分子逻辑电路能够有效地用于自然数的素性判定.通过扩大该分子逻辑电路的规模，可进行更大自然数的素性判定研究.

参考文献：

[1]杨学庆, 柳重堪. 基于DNA有穷自动机的素性测试法[J]. 通信学报,2006,27(10):80-85.

[2]ADLEMAN L M. Molecular computation of solutions to combinatorial problems[J]. Science, 1994, 266(5187): 1021-1024.

[3]LAKIN M R, YOUSSEF S, CARDELLI L, et al. Abstractions for DNA circuit design[J]. The Royal Society Interface, 2012, 9(68):470-486.

[4]ZHANG D Y, WINFREE E. Control of DNA strand displacement kinetics using toehold exchange[J]. J Am Chem Soc, 2009, 131(47):17303-17314.

[5]CHEN Y J,DALCHAU N, SRINIVAS N, et al. Programmable chemical controllers made from DNA[J]. Nature nanotechnology, 2013, 8(10):755-762.

[6]LAKIN M R, PARKER D,CARDELLI L, et al. Design and Analysis of DNA Strand Displacement Devices using Probabilistic Model Checking[J]. The Royal Society Interface, 2012, 7(72): 1470-1485.

[7]张成, 马丽娜, 董亚非,等. 自组装DNA链置换分子逻辑计算模型[J]. 科学通报,2012,57(31): 2909-2915.

[8]SEELIG G, SOLOVEICHIK D, ZHANG D Y, et al. Enzyme-free nucleic acid logic circuits[J]. Science, 2006, 314(5805): 1585-1588.

[9]QIAN Lu-lu, WINFREE E. A simple DNA gate motif for synthesizing large-scale circuits[J]. Journal of the Royal Society Interface, 2011, 8(62):1281-1297.

[10]QIAN Lu-lu, WINFREE E. Scaling up digital circuit computation with DNA strand displacement cascades[J]. Science, 2011, 332(6034): 1196-1201.

[11]QIAN Lu-lu, WINFREE E, BRUCK J. Neural network computation with DNA strand displacement cascades[J]. Nature, 2011, 475(7356): 368-372.

[12]CHEULEE J, ANDREW D. ELLINGTON. Diagnostic applications of nucleic acid circuits[J]. Accounts of Chemical Research, 2014, 47(6): 1825-1835.

[13]LAKIN M R, YOUSSEF S, POLO F, et al. Visual DSD: a design and analysis tool for DNA strand displacement systems[J]. Bioinformatics, 2011, 27(22): 3211-3213.

[14]PHILLIPS A, CARDELLI L. A programming language for composable DNA circuits[J]. Royal Society Interface, 2009, 6(11): 419-436.

Research of Prime Number Judgement Based on DNA Strand Displacement Reaction

WANG Zi-cheng1,3, DOU Gen-sheng2， ZHOU Xiao-gang2， YE Meng-meng1

(1.School of Electrical and Electronic Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China； 2.College of Sciences, Henan Agricultural University, Zhengzhou 450002, China; 3.Henan Key Laboratory of Information Appliances, Zhengzhou 450002, China)

Key words: DNA strand displacement； prime number judgement； logic circuit