基于DNA鏈置換反應(yīng)的自然數(shù)素性判定問題研究

基于DNA鏈置換反應(yīng)的自然數(shù)素性判定問題研究

王子成1,3，豆根生2，周小剛2，葉盟盟1

(1.鄭州輕工業(yè)學(xué)院 電氣信息工程學(xué)院，河南 鄭州 450002；2.河南農(nóng)業(yè)大學(xué) 理學(xué)院，河南 鄭州 450002;3.河南省信息化電器重點實驗室，河南 鄭州 450002)

摘要：借助自組裝DNA計算的顯著優(yōu)勢，采用DNA鏈置換反應(yīng)原理開展了自然數(shù)的素性判定問題研究.首先，構(gòu)造了有關(guān)DNA分子邏輯門，并構(gòu)建了相應(yīng)的DNA分子計算模型，然后設(shè)計了用于自然數(shù)素性判定的分子邏輯電路.最后基于Visual DSD仿真平臺，對分子邏輯電路進(jìn)行仿真.結(jié)果表明:采用的分子邏輯電路能夠?qū)崿F(xiàn)自然數(shù)的素性判斷.

關(guān)鍵詞：DNA鏈置換；素性判定；邏輯電路

收稿日期:2015-06-01；

修訂日期：2015-07-10

基金項目:國家自然科學(xué)基金資助項目(U1304620);河南省教育廳科學(xué)技術(shù)研究重點項目(13A413371)

作者簡介:王子成(1976—), 河南永城人, 鄭州輕工業(yè)學(xué)院講師,主要從事系統(tǒng)建模與仿真研究，E-mail：wzch@zzuli.edu.cn.

通訊作者：周小剛(1979—),河南焦作人，河南農(nóng)業(yè)大學(xué)講師,主要從事電路與通信工程研究,E-mail：20331476@qq.com.

文章編號:1671-6833(2015)05-0096-05

中圖分類號：TP384

文獻(xiàn)標(biāo)志碼：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引言

素數(shù)指大于1的自然數(shù)中，僅能被1及其自身整除的數(shù).自然數(shù)的素性判定研究具有深遠(yuǎn)的理論意義.伴隨著現(xiàn)代密碼學(xué)的興起，開展大數(shù)的素性判定研究已成為一個新課題，其在信息安全領(lǐng)域具有重要的應(yīng)用價值.

基于素數(shù)理論，密碼學(xué)領(lǐng)域可實現(xiàn)信息的有效加密.自然界中，多數(shù)生物體為了最大程度避免天敵，其生命周期也呈現(xiàn)素數(shù)性.在害蟲的生長周期內(nèi)，若使用素數(shù)次殺蟲劑則可有效抑制病蟲害.

試除法是素數(shù)判定算法中最基本的算法，此外還有AKS，Baillie-PSW和Miller-Rabin等算法.但當(dāng)自然數(shù)為多位數(shù)時，計算量非常龐大.且其中Miller-Rabin算法已經(jīng)被證實存在錯誤率.RSA公鑰加密算法是目前最有影響力的加密算法，但也僅能強力破解短RSA鑰匙.可見，探索用于自然數(shù)素性判定的新型算法，降低判定難度，縮短計算時間，以提高自然數(shù)的素性判定速度及效率，進(jìn)而實現(xiàn)合數(shù)的素因子分解，具有深遠(yuǎn)的理論研究及現(xiàn)實意義[1].

DNA計算[2]獨特的信息存儲方式及巨并行計算能力使其成為了一種新穎計算模式.其中，DNA鏈置換反應(yīng)能夠在室溫下進(jìn)行，無需外力作用，反應(yīng)周期短，最近成為一個熱門研究課題[3-5].筆者基于DNA鏈置換反應(yīng)，設(shè)計了用于四位二進(jìn)制數(shù)素性判定的計算模型.該模型可在室溫下進(jìn)行，操作簡單，易于實現(xiàn)，產(chǎn)率較高，能充分體現(xiàn)DNA計算優(yōu)勢.

1DNA鏈置換反應(yīng)

DNA鏈置換反應(yīng)是指單鏈DNA分子能夠與部分互補的DNA雙鏈結(jié)構(gòu)產(chǎn)生反應(yīng)，并能釋放出原有雙鏈結(jié)構(gòu)中的單鏈DNA分子，生成新的雙鏈DNA分子結(jié)構(gòu)的過程[6-7].具有部分互補結(jié)構(gòu)的雙鏈DNA分子，含有懸掛形式的黏性末端，分子處于熱力學(xué)非穩(wěn)定狀態(tài).加入與原始雙鏈DNA分子的長鏈完全匹配的單鏈DNA分子時，根據(jù)系統(tǒng)的自由能最低原理，通過單鏈DNA分子間的雜交匹配及替換過程，能夠生成更加穩(wěn)定的雙鏈DNA分子結(jié)構(gòu).最終實現(xiàn)了以較長單鏈DNA分子為輸入信號，以新的較短單鏈DNA分子為輸出信號的信號傳輸過程.

DNA鏈置換反應(yīng)的基本過程如圖1所示.含有黏性末端t*的雙鏈DNA分子結(jié)構(gòu)A中，DNA子序列x及x*部分為完全互補匹配，原始構(gòu)型的DNA分子A因為具有懸掛狀態(tài)的黏性末端，處于熱力學(xué)非穩(wěn)定狀態(tài).當(dāng)輸入結(jié)構(gòu)為tx的單鏈DNA分子時，其中的子序列t能與A中的t*黏性末端通過堿基匹配而鍵合.之后，分子tx中的x部分逐步將A中的x部分剝離出來，最終形成具有穩(wěn)定結(jié)構(gòu)的雙鏈DNA分子B，并輸出單鏈DNA分子x，完成鏈置換過程.將多個DNA鏈置換反應(yīng)結(jié)合成網(wǎng)絡(luò)回路，可實現(xiàn)某個邏輯運算.

圖1　DNA鏈置換的基本過程

近年來，DNA鏈置換反應(yīng)在分子計算、納米機器及疾病診斷和治療等領(lǐng)域都得到深入研究，已成為納米科學(xué)領(lǐng)域的重要課題.2006年，Seelig等基于鏈置換反應(yīng)原理，設(shè)計出與門、或門、非門等邏輯模塊，利用這些模塊組合成邏輯電路[8].2010年，QIAN改進(jìn)設(shè)計了單個的門單元，使得邏輯門的設(shè)計更加模塊化和標(biāo)準(zhǔn)化[9].2011年，QIAN設(shè)計了計算四位二進(jìn)制數(shù)平方根的邏輯電路，用DNA鏈組成四個相互聯(lián)系的人工神經(jīng)元，通過猜心術(shù)游戲，證明了DNA分子神經(jīng)網(wǎng)絡(luò)具有一定的邏輯推理能力[10-11].2015年，Cheulee等人基于DNA鏈置換反應(yīng)，將核酸電路用于診斷研究[12].

2自然數(shù)素性判定的DNA計算模型

2.1邏輯電路

邏輯電路基于二進(jìn)制編碼機制，通過離散信號的傳遞和處理，最終實現(xiàn)數(shù)字信號的邏輯運算和操作.基本邏輯電路有與門、或門、非門、異或門及與非門等.已廣泛用于計算機、數(shù)字控制、通信、自動化和儀表等諸多領(lǐng)域.

判定四位二進(jìn)制數(shù)對應(yīng)的自然數(shù)素性時，相應(yīng)的邏輯電路如圖2所示.圖中的邏輯電路由4個與門、3個或門和3個非門組成.I0～I(xiàn)3分別表示四位輸入信號，P為輸出信號，其輸出為輸入數(shù)字的素性判定結(jié)果.當(dāng)輸出P為1時，表示輸入為素數(shù)；當(dāng)輸出P為0時，則表示輸入為非素數(shù).如I0=1，I1=0，I2=0，I3=0時，對應(yīng)的輸入信號為1000，該邏輯電路用于對十進(jìn)制數(shù)字8的素性進(jìn)行判斷.此時對應(yīng)的輸出信號P為0.

圖2　四位二進(jìn)制數(shù)的素性判定邏輯電路

2.2分子邏輯門及放大器

邏輯門為條件開關(guān)，僅當(dāng)輸入信號滿足一定條件時，邏輯門才會“打開”，輸出信號.圖2中用到了3種基本邏輯門——與門、或門、非門.筆者根據(jù)3種邏輯門的“打開”條件，設(shè)計與其對應(yīng)的基于DNA鏈置換反應(yīng)的分子邏輯門.

(1)分子與門 對于2輸入的與門，僅兩個輸入都為邏輯1時，與門才能“打開”，此時輸出為邏輯1，否則，輸出為邏輯0.筆者設(shè)計的分子與門見圖3所示.圖3(a)中，單鏈DNA分子ts1和ts2t對應(yīng)于邏輯門中的兩個輸入信號，鏈s2ts3為輸出信號鏈.

當(dāng)僅輸入為信號鏈ts1或ts2t時，分子與門無信號鏈輸出.僅當(dāng)同時輸入信號鏈ts1和ts2t時，才能確保置換反應(yīng)正向進(jìn)行，輸出正確的信號鏈s2ts3，最終完成邏輯運算過程.其中，輸入信號鏈ts1用于置換出分子與門中的單鏈s1t.輸入信號鏈ts2t作用有二：①防止單鏈s1t與鏈ts1之間再次產(chǎn)生置換反應(yīng)；②通過置換反應(yīng)釋放分子與門中的單鏈s2ts3.為方便分子邏輯模型的構(gòu)建，設(shè)計出分子與門的等價符號，如圖3(b)所示.其中，“○”內(nèi)數(shù)字表示分子與門的初始濃度，“○”外數(shù)字表示輸入信號鏈的分子濃度.

圖3　分子邏輯與門結(jié)構(gòu)及符號

(2)分子或門 2輸入分子或門中，當(dāng)兩個輸入信號鏈中有一個邏輯值為1時，或門就可“打開”，輸出為邏輯1；僅當(dāng)所有輸入都為邏輯0時，才能輸出邏輯值0.根據(jù)或門的觸發(fā)條件，筆者設(shè)計的分子或門如圖4所示.

圖4　分子邏輯或門結(jié)構(gòu)及符號

圖4(a)中，分子或門的輸入信號分別為鏈s2ts3和鏈s4ts3.二者都含有部分單鏈s3，都能夠置換出分子或門中的單鏈s3.圖4中輸入信號鏈的分子結(jié)構(gòu)能夠避免置換反應(yīng)的逆過程，有利于最終輸出正確的信號鏈，完成或邏輯運算過程.

圖4(b)為分子與門的等價符號，“○”內(nèi)數(shù)字表示分子或門的濃度，“○”外數(shù)字表示輸入信號鏈的濃度.

(3) 分子非門筆者中采用兩種不同鏈的分別表示邏輯1和邏輯0.

2.3分子放大器

DNA鏈置換反應(yīng)過程中存在如下幾種影響反應(yīng)速率和產(chǎn)率的因素

(1)輸入信號鏈DNA分子，不可能全部參與置換反應(yīng)；

(2)隨著反應(yīng)進(jìn)程的推進(jìn)，輸入信號鏈分子濃度逐漸降低，從而降低反應(yīng)速度；

(3)單鏈DNA分子在置換過程中，會出現(xiàn)堿基錯配和降解現(xiàn)象.

含有多個鏈置換反應(yīng)的計算模型中，上述因素將會影響到輸出產(chǎn)物的數(shù)量，甚至產(chǎn)物的正確性.為了確保鏈置換反應(yīng)的順利進(jìn)行，提高輸出信號鏈在反應(yīng)產(chǎn)物中的比例，筆者設(shè)計了基于DNA鏈置換反應(yīng)的分子信號放大器，用于提高輸出信號鏈的濃度.其結(jié)構(gòu)與工作原理如圖5所示.

圖5(a)為分子放大器模型.單鏈ts5為輸入信號鏈，單鏈s5t為燃料鏈，單鏈s5ts6則為輸出信號鏈.DNA鏈置換反應(yīng)是在溶液中進(jìn)行的，為了表述方便筆者設(shè)定輸入信號鏈ts5的分子數(shù)量為1倍濃度(圖中標(biāo)注為“I = 1×”)，雙鏈結(jié)構(gòu)的DNA分子數(shù)量為2倍濃度(圖中標(biāo)注為“A=2×”)，燃料鏈s5t為4倍濃度(圖中標(biāo)注為“F=4×”).加入輸入信號鏈ts5前，雙鏈結(jié)構(gòu)和燃料鏈s5t間無反應(yīng).信號鏈輸入前，雙鏈結(jié)構(gòu)和燃料鏈間無反應(yīng).加入輸入信號鏈ts5后生化反應(yīng)過程，如圖5(c)所示.實線箭頭表示正反應(yīng)方向，虛線箭頭表示逆反應(yīng)方向.輸入信號鏈ts5就像一個“打開”信號，觸發(fā)了位于頂部位置的鏈ts5、鏈s5ts6及鏈s5t和位于底部位置的鏈t*s5*t*之間的反應(yīng).因此，即便有少量的輸入信號鏈，只要提高燃料鏈對底部鏈t*s5*t*的占有率，就可以得到較多的輸入信號鏈.分子放大器結(jié)構(gòu)中，可以通過提高雙鏈結(jié)構(gòu)和燃料鏈的濃度來提高輸出信號鏈的產(chǎn)量，從而達(dá)到信號放大的作用.圖5(b)為分子放大器的等價符號.

圖5　分子放大器及其反應(yīng)過程

3分子邏輯電路

筆者構(gòu)建了自然數(shù)素性判定的分子邏輯電路，如圖6所示.該邏輯電路能對四位二進(jìn)制數(shù)的素性進(jìn)行判斷.圖中標(biāo)注的數(shù)字分別表示各種DNA分子的分子濃度.

圖6中輸入信號的邏輯1和0分別對應(yīng)兩種單鏈DNA，因此，共有8種輸入信號鏈，分別表示為I00、I10…I03、I13，通過對應(yīng)的8個分子放大器將輸入信號放大.輸入信號I0=1和I3=0對輸出結(jié)果無影響，但為了保留邏輯電路的完整性，確保分子邏輯電路的魯棒性，分子邏輯電路中仍然保留這兩個信號.圖中P為輸出信號.在分子邏輯電路中，當(dāng)分子邏輯電路中有信號鏈輸出時，P的取值為1，此時，所輸入的自然數(shù)判定為素數(shù)；反之，輸出P取值為0，所輸入的自然數(shù)判定為非素數(shù).

4仿真結(jié)果

圖6所示的分子邏輯電路，可實現(xiàn)自然數(shù)的素性判斷.筆者在Visual DSD軟件平臺中，對分子邏輯電路的運算過程進(jìn)行仿真，驗證了本分子邏輯電路的可行性與運算結(jié)果的準(zhǔn)確性.Visual DSD是由Matthew Lakin等人[13-14]設(shè)計，主要用于構(gòu)建和分析DNA鏈置換計算模型.采用圖6中的分子邏輯電路，以1 ～ 15之間自然數(shù)的素性判定為例，Visual DSD的仿真結(jié)果如圖7所示.

圖6　用于四位二進(jìn)制數(shù)素性測試的分子邏輯電路

在分子邏輯電路運算過程中，4條輸入信號鏈和輸出信號鏈P的分子濃度變化曲線體現(xiàn)出非常明顯的階段性特征.

第一階段：加入4種輸入信號鏈，先與對應(yīng)的分子放大器發(fā)生鏈置換反應(yīng)，剛開始反應(yīng)物濃度高，反應(yīng)速度快.因為該分子模型的反應(yīng)是逐級進(jìn)行的，此時并無鏈P生成；

第二階段：隨著鏈置換反應(yīng)的逐步深入，輸入信號鏈的濃度趨于穩(wěn)定，有些輸入情況中有鏈P產(chǎn)生，并且鏈P的產(chǎn)率不斷增加；

第三階段：輸入信號鏈濃度平穩(wěn)，有鏈P產(chǎn)生情況中，鏈P的生產(chǎn)速率逐漸降低，最后趨于平緩，如圖7所示.

圖7中，用于表征縱坐標(biāo)的信號鏈分子濃度比是指輸出信號鏈的分子濃度所占整個反應(yīng)體系中所有分子濃度的比值，仿真實驗中反應(yīng)時間單位為1 000 s.若輸入信號鏈對應(yīng)的自然數(shù)為2, 3, 5, 7, 11, 13，有信號鏈P輸出，對應(yīng)自然數(shù)1～15內(nèi)的素數(shù)，證明了分子計算模型的正確性.在鏈P有濃度變化的情況中，鏈P的濃度變化曲線呈“S”形.這與反應(yīng)物的濃度有關(guān).

圖7Visual DSD平臺下分子邏輯電路的仿真結(jié)果

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

圖中輸入信號鏈定義為1倍濃度，而信號鏈P的最終輸出濃度約為輸入信號鏈濃度的2倍，表現(xiàn)出分子放大器的信號放大作用.輸入信號鏈的濃度之所以在平穩(wěn)后出現(xiàn)波動性變化，且變化幅度不大，是因為輸入信號放大器中大部分的底部鏈被燃料鏈占據(jù)，使得分子計算模型后續(xù)生化反應(yīng)對輸入信號鏈的濃度影響不大.

5結(jié)論

DNA鏈置換反應(yīng)在常溫下自發(fā)進(jìn)行，成本低，操作簡單.筆者將DNA鏈置換反應(yīng)用于自然數(shù)的素性判定問題研究.設(shè)計了可執(zhí)行邏輯運算的DNA分子邏輯門以及具有信號放大作用的DNA分子放大器.構(gòu)造了用于自然數(shù)素性判定的分子邏輯電路.反應(yīng)過程中，可對目標(biāo)信號鏈濃度進(jìn)行擴增，便于輸出信號鏈的提取，能夠有效實現(xiàn)信號傳輸與處理，保證了傳輸信號的安全性與有效性.

利用DSD平臺對1～15之間的自然數(shù)的素性判定進(jìn)行了仿真，結(jié)果表明，筆者設(shè)計的分子邏輯電路能夠有效地用于自然數(shù)的素性判定.通過擴大該分子邏輯電路的規(guī)模，可進(jìn)行更大自然數(shù)的素性判定研究.

參考文獻(xiàn)：

[1]楊學(xué)慶, 柳重堪. 基于DNA有窮自動機的素性測試法[J]. 通信學(xué)報,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]. 科學(xué)通報,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