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

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

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

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

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

收稿日期:2015-06-01；

修訂日期：2015-07-10

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

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

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

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

中圖分類號(hào)：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引言

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

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

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

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

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

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

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

圖1　DNA鏈置換的基本過(guò)程

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

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

2.1邏輯電路

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

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

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

2.2分子邏輯門及放大器

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

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

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

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

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

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

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

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

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

2.3分子放大器

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

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

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

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

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

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

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

3分子邏輯電路

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

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

4仿真結(jié)果

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

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

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

第一階段：加入4種輸入信號(hào)鏈，先與對(duì)應(yīng)的分子放大器發(fā)生鏈置換反應(yīng)，剛開始反應(yīng)物濃度高，反應(yīng)速度快.因?yàn)樵摲肿幽Ｐ偷姆磻?yīng)是逐級(jí)進(jìn)行的，此時(shí)并無(wú)鏈P生成；

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

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

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

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

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

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

5結(jié)論

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

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

參考文獻(xiàn)：

[1]楊學(xué)慶, 柳重堪. 基于DNA有窮自動(dòng)機(jī)的素性測(cè)試法[J]. 通信學(xué)報(bào),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ì)算模型[J]. 科學(xué)通報(bào),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