基于DNA下推自動(dòng)機(jī)二進(jìn)制減法和乘法的實(shí)現(xiàn)

1、基于dna下推自動(dòng)機(jī)二進(jìn)制減法和乘法的實(shí)現(xiàn)程珍1) 黃玉芳1) 周康2)(華中科技大學(xué) 控制科學(xué)與工程系 武漢 430074) 2) (武漢工業(yè)學(xué)院 數(shù)理科學(xué)系 武漢 430023)摘要提出了基于dna下推自動(dòng)機(jī)二進(jìn)制減法和乘法的實(shí)現(xiàn)方法. 一位二進(jìn)制借位減法, 是通過(guò)預(yù)先構(gòu)造好的dna下推自動(dòng)機(jī)模型在一個(gè)試管中以該模型的運(yùn)行方式自動(dòng)完成運(yùn)算. m位二進(jìn)制借位減法, 是在一位二進(jìn)制減法的基礎(chǔ)上, 按照從低位到高位的順序, 將低位產(chǎn)生的借位作為高位試管操作中的輸入符號(hào)串, 從而完成高位的減法運(yùn)算. 兩位二進(jìn)制乘法中包含移位和加法操作, 在兩個(gè)試管中分別設(shè)計(jì)好dna下推自動(dòng)機(jī)模型, 分別完成被乘數(shù)

2、與乘數(shù)各位的移位操作, 同時(shí)結(jié)合相應(yīng)的生物操作, 將其作為另一個(gè)試管加法操作中的輸入符號(hào)串, 則加法操作中產(chǎn)生的結(jié)果即為所求. 在此基礎(chǔ)上, m位二進(jìn)制乘法可通過(guò)移位操作的并行性和加法操作的串行性來(lái)完成運(yùn)算. 這些實(shí)現(xiàn)方法為dna下推自動(dòng)機(jī)實(shí)現(xiàn)基本的算術(shù)運(yùn)算提供了比較完整的運(yùn)算機(jī)制.關(guān)鍵詞dna下推自動(dòng)機(jī); 借位減法; 乘法; 移位操作; dna編碼中圖法分類(lèi)號(hào)tp301 implementation of binary subtraction and multiplication based on dna push-down automatoncheng zhen1) huang yu-fa

3、ng1) zhou kang2)1) (department of control science and engineering, huazhong university of science and technology, wuhan 430074)2) (department of mathematics and physics，wuhan polytechnic university，wuhan 430023)abstract the implementations of binary borrow bit subtraction and multiplication based on

4、 dna push-down automata are proposed. the one bit binary subtraction can be automatically completed the operations in one tube by designing the dna push-down automata model preparedly in advance. based on this model, m bits subtraction can be obtained by putting the borrow bit from the low bit tube

5、to the high bit tube as the input strings. the two bits binary multiplication based on dna push-down automata model includes shift operations and addition operations, the shift operations between the string representing the multiplicand and the strands denoting each bit of the multiplier can be perf

6、ormed in two tubes synchronously combining biology operation, then the result strings are put into another tube as the input strings in the addition operation, finally the output in this operation is the solution. the m bits binary multiplication can be got by parallel shift operations and serial ad

7、dition operations. these processes provide relatively complete arithmetic mechanisms for dna automata.keywords dna push-down automata; borrow bit subtraction; multiplication; shift operation; dna-encoding1 引言自adleman 1994 年創(chuàng)立 dna 計(jì)算模型1以來(lái), dna 計(jì)算無(wú)論是在理論上, 應(yīng)用模型的建立上, 還是實(shí)驗(yàn)與檢測(cè)技術(shù)上都取得了驚人的進(jìn)步. 它的優(yōu)勢(shì)是利用dna分子具有海

8、量的存儲(chǔ)能力及生化反應(yīng)的巨大并行性等特點(diǎn)進(jìn)行計(jì)算2-3. 在dna 計(jì)算運(yùn)算系統(tǒng)的研究中, 首先取得突破性工作的是guarnieri4等人于1996年建立了dna計(jì)算的加法運(yùn)算模型, 提出了基于dna計(jì)算的二進(jìn)制正有理數(shù)的加法運(yùn)算, 解決了加法的進(jìn)位問(wèn)題, 創(chuàng)造性地完成了對(duì)dna分子生物運(yùn)算過(guò)程的構(gòu)造與控制, 同時(shí)進(jìn)行了相應(yīng)的生物實(shí)驗(yàn)操作；而后他們繼續(xù)將上述結(jié)果擴(kuò)展到一般的3進(jìn)制乃至k進(jìn)制的加法運(yùn)算5. 1999年, bernard6等人提出了一種新的dna加法模型, 這種加法運(yùn)算與guarnieri的工作相比, 其優(yōu)點(diǎn)是dna 計(jì)算中的boole邏輯的dna 分子中, 輸入串與運(yùn)算串是分離的

9、, 該加法通過(guò)對(duì)幾例實(shí)驗(yàn)操作成功顯示了具有復(fù)雜度為30個(gè)邏輯門(mén)的數(shù)字分子計(jì)算的可行性. fujiwara7等人對(duì)dna鏈進(jìn)行了邏輯操作和算術(shù)操作, 給出了可設(shè)定地址的操作程序；同時(shí), 基于dna計(jì)算的二進(jìn)制數(shù)乘法和除法可以通過(guò)相應(yīng)的生物操作程序來(lái)實(shí)現(xiàn)運(yùn)算8. 在實(shí)驗(yàn)室中進(jìn)行分子水平計(jì)算機(jī)裝置的自動(dòng)操作的實(shí)驗(yàn)比較少, 可見(jiàn)文獻(xiàn)9-11. dna計(jì)算機(jī)的研究具有突破性進(jìn)展是2001年以色列benenson研究小組12提出了一種可程序?qū)崿F(xiàn)的、自治的基于生物分子的有限狀態(tài)自動(dòng)機(jī)模型, 它的所有部件, 包括硬件、軟件、輸出都是生物分子. 酶包括限制性?xún)?nèi)切酶和連接酶是分子自動(dòng)機(jī)的硬件, 輸入分子和轉(zhuǎn)移分子

10、是分子自動(dòng)機(jī)的軟件, 通過(guò)選擇合適的狀態(tài)轉(zhuǎn)移分子來(lái)最終產(chǎn)生以dna分子的形式代表終止?fàn)顟B(tài)的輸出分子. 在此基礎(chǔ)上, 如何提高分子自動(dòng)機(jī)的計(jì)算能力也引起了廣泛的研究13-14. 其后, cavaliere等人15提出了基于dna分子的帶有一個(gè)棧和兩個(gè)棧的下推自動(dòng)機(jī)模型, 并利用環(huán)形和線(xiàn)性的dna分子和類(lèi)限制性酶給出了dna下推自動(dòng)機(jī)執(zhí)行操作的過(guò)程. reif等人16提出了自治的基于dna分子自動(dòng)機(jī)的理論設(shè)計(jì)方案, 并將其拓展到了二維結(jié)構(gòu)的設(shè)計(jì). 李汪根等人17給出了dna自動(dòng)機(jī)二進(jìn)制加法的實(shí)現(xiàn)方法, 在上述基礎(chǔ)上, 本文提出了基于dna下推自動(dòng)機(jī)二進(jìn)制數(shù)減法和乘法的實(shí)現(xiàn)方法, 與此相關(guān)的dna計(jì)

11、算的原理可參見(jiàn)文獻(xiàn)18.基于dna下推自動(dòng)機(jī)的運(yùn)算模型, 其二進(jìn)制減法和乘法操作的運(yùn)算方式類(lèi)似于電子計(jì)算機(jī)中的運(yùn)算系統(tǒng). 在設(shè)計(jì)好轉(zhuǎn)移函數(shù)分子的基礎(chǔ)上, 比較容易完成運(yùn)算, 相對(duì)于dna計(jì)算中的運(yùn)算模型而言, 該模型操作數(shù)的編碼相對(duì)較簡(jiǎn)單. 一位二進(jìn)制減法, 只需對(duì)0 和 1進(jìn)行編碼, 就可以完成相應(yīng)的操作. 多位二進(jìn)制減法是在一位二進(jìn)制減法的基礎(chǔ)上進(jìn)行循環(huán)操作完成的. 兩位二進(jìn)制乘法包含移位操作和加法操作, 通過(guò)分別設(shè)計(jì)好相應(yīng)的轉(zhuǎn)移函數(shù)分子, 在不同的試管中完成移位操作和加法操作, 加法操作的結(jié)果即為該兩個(gè)兩位二進(jìn)制數(shù)乘法的結(jié)果. 在此基礎(chǔ)上, m位二進(jìn)制乘法可通過(guò)移位操作的并行性和加法操作

12、的串行性來(lái)完成運(yùn)算.2 dna下推自動(dòng)機(jī)自動(dòng)機(jī)是實(shí)現(xiàn)信息與信息之間轉(zhuǎn)移的一種裝置, 是數(shù)字計(jì)算機(jī)的抽象模型, 是一種描述和執(zhí)行運(yùn)算的工具. 下面介紹下推自動(dòng)機(jī)的概念, 基于dna分子的下推自動(dòng)機(jī)的特性以及文中所涉及的生物操作.2.1 下推自動(dòng)機(jī)一個(gè)下推自動(dòng)機(jī)m是如下的一個(gè)七元組(q, , , , q0, z0, f), 其中, q 是一個(gè)有窮狀態(tài)集合, 是一個(gè)字母表, 稱(chēng)為輸入字母表; 是一個(gè)字母表, 稱(chēng)為棧字母表；q0屬于q, 是初始狀態(tài)；z0屬于, 是一個(gè)特殊的符號(hào), 稱(chēng)為棧起始符號(hào)；f 包含于q是終結(jié)狀態(tài)集合；: q() q*是m的動(dòng)作函數(shù). 一個(gè)自動(dòng)機(jī)包含一個(gè)有窮控制器、一條輸入帶和一

13、個(gè)讀頭. 根據(jù)自動(dòng)機(jī)的當(dāng)前狀態(tài)以及讀頭的位置, 按照一定的轉(zhuǎn)移規(guī)則, 自動(dòng)機(jī)會(huì)自動(dòng)完成一次操作, 進(jìn)入下一個(gè)狀態(tài)以及移動(dòng)讀頭.下推自動(dòng)機(jī)就是在典型的自動(dòng)機(jī)的基礎(chǔ)上帶有棧的存儲(chǔ)操作, 它由有限狀態(tài)控制器、輸入符號(hào)串和棧三部分組成. 在執(zhí)行操作時(shí), 下推自動(dòng)機(jī)從初始狀態(tài)出發(fā), 在有限狀態(tài)控制器的控制下, 根據(jù)它的當(dāng)前狀態(tài)、輸入符號(hào)串和棧頂符號(hào)通過(guò)轉(zhuǎn)移函數(shù)進(jìn)入下一個(gè)狀態(tài), 同時(shí)修改棧頂元素, 以及決定讀頭是否移動(dòng). 當(dāng)輸入符號(hào)串處理結(jié)束時(shí), 下推自動(dòng)機(jī)處于可接受狀態(tài)集f的某一個(gè)狀態(tài), 且棧的內(nèi)容為空, 則表示自動(dòng)機(jī)接受該符號(hào)串; 否則自動(dòng)機(jī)不接受該符號(hào)串.在有窮狀態(tài)的dna自動(dòng)機(jī)中, 酶是分子自動(dòng)機(jī)

14、的硬件, 輸入分子和轉(zhuǎn)移分子是分子自動(dòng)機(jī)的軟件, 同時(shí)還編碼了檢測(cè)分子. 設(shè)計(jì)一個(gè)dna自動(dòng)機(jī)的關(guān)鍵在于選擇合適的軟件分子. 當(dāng)輸入分子, 轉(zhuǎn)移分子以及所需的酶混合后, dna自動(dòng)機(jī)將會(huì)通過(guò)一系列的雜交、鏈接、提取、酶切等生物操作來(lái)處理輸入分子, 最終確定是否產(chǎn)生編碼dna自動(dòng)機(jī)終結(jié)狀態(tài)的檢測(cè)性輸出分子, 從而判斷該dna自動(dòng)機(jī)是否接受某個(gè)輸入字符串.基于dna的下推自動(dòng)機(jī)則是在此基礎(chǔ)上, 增加的棧元素也用dna分子表示, 通過(guò)對(duì)輸入分子實(shí)施一系列的操作, 以dna分子的形式產(chǎn)生代表 dna下推自動(dòng)機(jī)最終狀態(tài)的輸出分子, 同時(shí)通過(guò)對(duì)表示棧的dna片斷實(shí)施一系列的酶切, 綁接和連接等生物操作實(shí)現(xiàn)

15、入?；虺鰲２僮? 以修改棧頂元素.2.2 dna自動(dòng)機(jī)的相關(guān)生物操作下面我們介紹文中所需要的一些生物操作, 這些生物操作包含了對(duì)dna鏈進(jìn)行處理的一系列生化反應(yīng), 參見(jiàn)7, 8.(1)混合. 給定各含有一定數(shù)量dna鏈的兩試管溶液倒入同一試管中得到混合溶液.(2)復(fù)制. 通過(guò)聚合酶鏈反應(yīng)pcr將dna串復(fù)制.(3)檢測(cè). 若給定的試管中包含指定的dna片斷, 則輸出為“是”, 否則輸出為“否”.(4)分離. 將若干條單鏈的集合從給定含有一定數(shù)量dna鏈的試管中提取出來(lái).(5)切割. 利用限制酶在某一特定的位置切斷dna雙鏈, 在切割位點(diǎn)處被切割成兩個(gè)dna片斷.(6)退火. 將含有單鏈的溶液冷

16、卻, 互補(bǔ)的單鏈dna序列重新組合起來(lái), 形成雙鏈dna.(7)合成. 在一定長(zhǎng)度范圍內(nèi), 合成可以將a、t、c、g 4個(gè)堿基按照預(yù)定的順序排列在dna單鏈上. (8)抽提. 通過(guò)親和力, 將以包含給定序列的dna片斷作為子串的dna鏈提取出來(lái). (9)連接. 由互補(bǔ)序列經(jīng)退火形成dna雙鏈. (10)雜交. 具有互補(bǔ)粘性末端的兩個(gè)dna片斷經(jīng)退火后, 互補(bǔ)末端會(huì)綁接在一起形成雙鏈結(jié)構(gòu).3 基于dna下推自動(dòng)機(jī)二進(jìn)制減法在本節(jié)中, 首先介紹了基于dna計(jì)算一位二進(jìn)制減法的運(yùn)算法則, 通過(guò)構(gòu)造基于dna下推自動(dòng)機(jī)模型, 完成基于該模型一位二進(jìn)制借位減法的操作.然后在此基礎(chǔ)上, 給出了實(shí)現(xiàn)兩個(gè)m位

17、二進(jìn)制減法的操作過(guò)程.3.1 基于dna下推自動(dòng)機(jī)一位二進(jìn)制減法在這里我們只考慮被減數(shù)比減數(shù)大的情形. 表1是基于dna計(jì)算的一位二進(jìn)制減法的運(yùn)算法則, 通過(guò)構(gòu)造基于dna下推自動(dòng)機(jī)來(lái)實(shí)現(xiàn)這個(gè)運(yùn)算過(guò)程, 同時(shí)給出該下推自動(dòng)機(jī)的各個(gè)組成部件的dna分子編碼方式.表1 一位二進(jìn)制借位減法的運(yùn)算法則表被減數(shù)減數(shù)前位的借位差產(chǎn)生的借位0000000111010110110110010101001100011111初始狀態(tài)集合為0, 1, 分別用s0, s1代表在初始狀態(tài)時(shí), 對(duì)應(yīng)被減數(shù)分別為0, 1的情況. 終止?fàn)顟B(tài)的集合為0, 1, 分別用s0 , s1代表對(duì)應(yīng)減法的運(yùn)算結(jié)果, 即差為0, 1的情況

18、. 輸入符號(hào)的集合為0, 1, 代表減數(shù)分別是0, 1的情況. 棧頂符號(hào)的集合為0, 1, 分別代表產(chǎn)生的借位為0, 1的情況. 用表示當(dāng)前狀態(tài)是q, 棧頂符號(hào)是z, 當(dāng)前輸入符號(hào)是a, 在控制器的控制下, 自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)變?yōu)閠, 棧頂符號(hào)變?yōu)閍. 所設(shè)計(jì)的dna下推自動(dòng)機(jī)的所有可能狀態(tài)轉(zhuǎn)移函數(shù)的集合是： 下面來(lái)描述基于dna下推自動(dòng)機(jī)的各個(gè)組成部分dna分子的編碼方式以及相應(yīng)的生物操作過(guò)程. 圖1為一位二進(jìn)制減法的試管體系.所構(gòu)造的自動(dòng)機(jī)的輸入符號(hào)串, 為代表被減數(shù)及減數(shù)所組成的dna片斷, 以及棧元素中代表低位減法中產(chǎn)生借位的dna片斷. 將以上預(yù)先合成的dna片斷按照自動(dòng)機(jī)的規(guī)則合成在一

19、起. 其中, 棧的元素在合成片斷的左邊, 右邊是輸入符號(hào)串, 中間是foki酶的識(shí)別位點(diǎn), 通過(guò)其來(lái)實(shí)現(xiàn)對(duì)棧和輸入符號(hào)串進(jìn)行生物操作. 在合成的dna片斷的右端包含一個(gè)4bp的粘性末端, 用于連接從低位減法操作中產(chǎn)生的借位片斷. 同時(shí)預(yù)先設(shè)計(jì)好轉(zhuǎn)移函數(shù)分子, 它的粘性末端剛好與foki酶切后的片斷的末端互補(bǔ). 在自動(dòng)機(jī)運(yùn)行結(jié)束后, 加入檢測(cè)分子, 同時(shí)利用內(nèi)切酶bsmfi酶來(lái)進(jìn)行酶切操作, 以檢測(cè)出代表差的片斷以及借位的片斷, 加入smii酶進(jìn)行分離操作, 即可得到代表差的dna片斷和代表借位的dna片斷. 相應(yīng)的操作步驟如下:步驟: 先預(yù)先合成好被減數(shù)和減數(shù)的dna片斷, 以及棧頂元素為0的

20、片斷和代表借位的dna片斷, 中間是foki酶的識(shí)別位點(diǎn), 在試管ta中對(duì)這幾個(gè)片斷進(jìn)行連接操作, 同時(shí)加入預(yù)先設(shè)計(jì)好的代表轉(zhuǎn)移函數(shù)分子的dna片斷以及t4連接酶.步驟二: 在試管ta中進(jìn)行自動(dòng)機(jī)的操作. 首先,合成好了的dna片斷經(jīng)foki酶進(jìn)行了酶切操作, 將合適的轉(zhuǎn)移函數(shù)片斷與酶切下的片斷進(jìn)行雜交.然后將雜交后的片斷通過(guò)t4連接酶連接起來(lái), 在foki酶的作用下, 繼續(xù)進(jìn)行酶切操作, 直到?jīng)]有合適的轉(zhuǎn)移函數(shù)片斷與酶切下的片斷雜交.步驟三: 加入檢測(cè)分子, 檢測(cè)分子與最后酶切下的片斷經(jīng)連接后形成報(bào)告分子.步驟四: 報(bào)告分子經(jīng)bsmfi酶酶切后, 可以得到代表差的片斷和代表借位的片斷. 同時(shí)

21、加入smii酶, 將酶切后的片斷進(jìn)行分離, 就可以得到代表差的dna片斷和代表借位的dna片斷, 并分別放在另外兩個(gè)試管tb, tc中. 圖1所示為兩個(gè)一位二進(jìn)制減法的試管體系. 圖1 一位二進(jìn)制減法的試管體系3.2 基于dna下推自動(dòng)機(jī)的m位二進(jìn)制減法m位二進(jìn)制的減法, 則是在一位二進(jìn)制數(shù)減法的基礎(chǔ)上, 進(jìn)行循環(huán)操作得到的. 這里也只考慮被減數(shù)比減數(shù)大的情形. 利用m個(gè)類(lèi)似的試管按照從低位到高位的順序組成串行計(jì)算方式, 得到低位試管運(yùn)算結(jié)果的同時(shí), 分離出代表差的dna片斷和代表借位的dna片斷, 然后將低位減法操作產(chǎn)生的代表借位的dna片斷作為高位下推自動(dòng)機(jī)的一個(gè)輸入符號(hào)串, 即能完成高位

22、的減法操作.如下圖所示為基于dna下推自動(dòng)機(jī)m位二進(jìn)制減法的操作圖, 將被減數(shù)與減數(shù)對(duì)應(yīng)位相減, 并作為一個(gè)下推自動(dòng)機(jī)的模型在一個(gè)試管中完成運(yùn)算. 從圖2可看到, 將每個(gè)自動(dòng)機(jī)運(yùn)算的結(jié)果片斷分別用檢測(cè)分子檢測(cè)出來(lái), 從而可以讀出片斷對(duì)應(yīng)的二進(jìn)制數(shù). 其中, b0, b1, , bn-2分別表示低位向高位的借位, 最后一位沒(méi)有借位. d0, d1, , dm-1分別表示從低位向高位每次自動(dòng)機(jī)運(yùn)行后分離出差的結(jié)果. 圖2 兩個(gè)m位二進(jìn)制減法的試管體系4 基于dna下推自動(dòng)機(jī)的二進(jìn)制乘法基于dna計(jì)算二進(jìn)制乘法, 主要是進(jìn)行移位操作和加法操作. 下面按照這兩個(gè)操作來(lái)進(jìn)行設(shè)計(jì)dna下推自動(dòng)機(jī)模型. 首

23、先介紹基于dna下推自動(dòng)機(jī)兩個(gè)兩位二進(jìn)制乘法, 然后在兩個(gè)兩位二進(jìn)制乘法基礎(chǔ)上, 介紹兩個(gè)m位二進(jìn)制乘法. 將移位操作的并行計(jì)算和加法操作的串行計(jì)算相結(jié)合, 經(jīng)過(guò)循環(huán)操作, 即可得相應(yīng)乘法的結(jié)果.4.1 基于dna下推自動(dòng)機(jī)兩位二進(jìn)制乘法在兩個(gè)兩位二進(jìn)制乘法中, 對(duì)應(yīng)的移位操作和加法操作均分步驟分別在不同的試管中進(jìn)行.(1)移位操作初始狀態(tài)的集合設(shè)為q, 令q=00, 01, 10, 11, 終止?fàn)顟B(tài)的集合設(shè)為f, 令f=00, 01, 10, 11, 輸入符號(hào)的集合為0, 1. 棧符號(hào)集合10, 11, 01, 12, 同時(shí)把棧中的兩個(gè)字符當(dāng)作一個(gè)整體來(lái)看, 棧中字符是來(lái)記錄移位運(yùn)算中輸入符

24、號(hào)在乘數(shù)中的位置, 以及所得結(jié)果在另外兩個(gè)數(shù)中的存儲(chǔ)位置. 初始狀態(tài)集合00, 01, 10, 11分別代表在初始狀態(tài)時(shí)被乘數(shù)分別對(duì)應(yīng)為00, 01, 10, 11的情況；終止?fàn)顟B(tài)集合00, 01, 10, 11分別代表在終止?fàn)顟B(tài)時(shí), 被乘數(shù)分別與乘數(shù)的個(gè)位與十位相乘的結(jié)果；輸入符號(hào)的集合0, 1分別代表乘數(shù)的個(gè)位與十位分別為0, 1的情況. 棧頂符號(hào)的集合中, 10代表輸入的是乘數(shù)的個(gè)位, 11代表輸入的是乘數(shù)的十位, 01代表將被乘數(shù)與乘數(shù)的個(gè)位所得的結(jié)果放在第二個(gè)數(shù)的個(gè)位與十位, 12代表將被乘數(shù)與乘數(shù)的十位所得的結(jié)果放在第三個(gè)數(shù)的十位與百位. 在移位操作中,所設(shè)計(jì)的下推自動(dòng)機(jī)模型所有可

25、能狀態(tài)轉(zhuǎn)移函數(shù)的集合是： .對(duì)于兩個(gè)兩位二進(jìn)制數(shù)的乘法, 如果乘數(shù)的某一位是0, 則所得的結(jié)果為00. 如果乘數(shù)的某一位是1, 則將被乘數(shù)的dna片斷復(fù)制到相應(yīng)的位子, 結(jié)合相應(yīng)的生物操作, 預(yù)先設(shè)計(jì)好被乘數(shù)的dna片斷, 以及分別代表0和1的dna片斷. 現(xiàn)將代表被乘數(shù)的dna片斷與代表乘數(shù)個(gè)位的dna片斷放在一個(gè)試管中按照下推自動(dòng)機(jī)模型完成運(yùn)算, 在所得結(jié)果片斷的左邊與代表0的片斷進(jìn)行連接操作, 此為加法操作中的一個(gè)輸入串. 把代表被乘數(shù)的dna片斷與代表乘數(shù)十位的dna片斷在第二個(gè)試管中得到相應(yīng)的結(jié)果, 按照相應(yīng)的狀態(tài)轉(zhuǎn)移函數(shù)操作, 實(shí)現(xiàn)了移位操作, 即將所得結(jié)果向左移了一位, 這是通過(guò)

26、設(shè)計(jì)好的狀態(tài)轉(zhuǎn)移函數(shù)片斷完成的操作, 同時(shí)在所得結(jié)果的片斷右邊與代表0的片斷進(jìn)行連接操作. 這兩個(gè)過(guò)程是并行完成的, 此為第三個(gè)試管中加法操作的另一個(gè)輸入串, 加法操作的過(guò)程比較簡(jiǎn)單, 即可得兩個(gè)兩位二進(jìn)制數(shù)乘法的結(jié)果. (2)加法操作在不同于上述試管中進(jìn)行加法操作, 輸入串即為在第一步進(jìn)行的移位操作后的結(jié)果, 同時(shí)把棧頂元素置為0, 然后按照加法操作中設(shè)置的狀態(tài)轉(zhuǎn)移函數(shù)來(lái)實(shí)現(xiàn)狀態(tài)的轉(zhuǎn)移, 加法操作完成后所得的結(jié)果即為兩個(gè)兩位二進(jìn)制乘法的結(jié)果. 圖3是基于dna自動(dòng)機(jī)兩位二進(jìn)制乘法試管體系. 其中s0, s1, s2, s3分別為加法操作中分離出代表個(gè)位的和, 十位的和, 百位的和的dna片斷

27、, c0為加法操作中代表進(jìn)位的棧元素dna片斷. 可利用檢測(cè)分子分別檢測(cè)出s0, s1, s2, s3, c0所對(duì)應(yīng)的片斷代表的二進(jìn)制數(shù), 則c0s3s2s1s0為兩位二進(jìn)制乘法的運(yùn)算結(jié)果.圖3 兩位二進(jìn)制乘法的試管體系 下面, 我們描述基于dna自動(dòng)機(jī)各個(gè)組成部分的dna分子的編碼方式以及相應(yīng)的生物操作過(guò)程.步驟一: 所設(shè)計(jì)的自動(dòng)機(jī)進(jìn)行如下操作, 預(yù)先合成好代表0, 1, 2的編碼, 利用它們的編碼合成好代表被乘數(shù)和乘數(shù)的編碼, 轉(zhuǎn)移函數(shù)分子, 以及代表結(jié)果位置的棧頂元素的編碼. 在試管a中加入被乘數(shù)與乘數(shù)個(gè)位的片斷, 轉(zhuǎn)移函數(shù)分子集合, 棧元素集合片斷, 中間是foki酶的識(shí)別位點(diǎn), 通過(guò)

28、它實(shí)現(xiàn)對(duì)棧和輸入符號(hào)串進(jìn)行生物操作. 同時(shí), 預(yù)先設(shè)計(jì)好轉(zhuǎn)移函數(shù)分子的編碼, 它的粘性末端剛好與foki酶酶切后的片斷的末端互補(bǔ). 在自動(dòng)機(jī)運(yùn)行結(jié)束后, 首先經(jīng)foki酶進(jìn)行了酶切操作, 將合適的轉(zhuǎn)移函數(shù)片斷與酶切下的片斷進(jìn)行雜交, 將雜交后的片斷通過(guò)t4連接酶連接起來(lái), 在foki酶的作用下, 繼續(xù)進(jìn)行酶切操作, 直到?jīng)]有合適的轉(zhuǎn)移函數(shù)片斷與酶切下的片斷雜交.步驟二: 在試管a中加入檢測(cè)代表結(jié)果的檢測(cè)分子, 將代表0的片斷與代表結(jié)果的片斷在其左邊進(jìn)行連接操作. 將連接操作后的片斷代表的二進(jìn)制數(shù)讀出來(lái), 并按照加法操作中的編碼方式重新對(duì)0, 1編碼, 將編碼好的片斷放入試管c中.步驟三: 在試

29、管b中放入被乘數(shù)與乘數(shù)十位的片斷, 加入轉(zhuǎn)移分子以及棧元素集合片斷, 中間是foki酶的識(shí)別位點(diǎn). 在該試管中發(fā)生酶切操作, 類(lèi)似于試管a中的反應(yīng)方式.步驟四: 在試管b中加入檢測(cè)代表結(jié)果的檢測(cè)分子, 將代表0的片斷與代表結(jié)果的片斷在其右邊進(jìn)行連接操作. 將連接操作后的片斷代表的二進(jìn)制數(shù)讀出來(lái), 并按照加法操作中的編碼方式重新對(duì)0, 1編碼, 把該編碼好的片斷放入試管c中.步驟五: 在試管c中加入轉(zhuǎn)移函數(shù)分子及酶分子進(jìn)行加法操作. 加法操作過(guò)程詳見(jiàn)17.步驟六: 將結(jié)果進(jìn)行分離操作, 得到代表加法操作中三位的結(jié)果, 以及代表進(jìn)位的片斷. 通過(guò)檢測(cè)分子, 分別檢測(cè)這些片斷代表的二進(jìn)制數(shù), 從而讀

30、出相應(yīng)的運(yùn)算結(jié)果.4.2 基于dna下推自動(dòng)機(jī)m位二進(jìn)制乘法對(duì)于m位二進(jìn)制數(shù)相乘, 類(lèi)似于兩位二進(jìn)制數(shù)相乘. 當(dāng)乘數(shù)增加了一位時(shí), 在進(jìn)行并行移位操作時(shí), 只需多用一個(gè)試管完成被乘數(shù)的dna片斷與乘數(shù)的這一位dna片斷的移位運(yùn)算, 這個(gè)過(guò)程是并行計(jì)算的, 同時(shí)結(jié)合生物操作, 將代表被乘數(shù)的片斷與乘數(shù)每一位的片斷分別在m個(gè)試管中按照乘數(shù)從低位到高位的順序進(jìn)行移位操作, 即在第一個(gè)試管中所得結(jié)果片斷的左邊通過(guò)連接酶連接預(yù)先設(shè)計(jì)好的代表m個(gè)0的dna片斷, 在第二個(gè)試管中所得結(jié)果片斷的右邊通過(guò)連接酶連接代表0的dna片斷, 在其左邊連接代表 (m-1) 個(gè)0的dna片斷, 如此類(lèi)推, 將代表被乘數(shù)的

31、dna片斷與乘數(shù)每一位的dna片斷的運(yùn)算結(jié)果作為新的試管中加法操作中輸入的dna片斷, 然后進(jìn)行相應(yīng)的加法操作, 即可得到m位二進(jìn)制相乘的運(yùn)算結(jié)果.初始狀態(tài)的集合為被乘數(shù)(m位)；終止?fàn)顟B(tài)的集合為被乘數(shù)(m位, 當(dāng)乘數(shù)的某一位為1時(shí))以及0(m位, 當(dāng)乘數(shù)的某一位為0時(shí))；輸入符號(hào)集合為0, 1(乘數(shù)的某一位為0或者1)；棧元素集合為表示被乘數(shù)與乘數(shù)的某一位所得結(jié)果移位后所放的位置. 兩個(gè)m位二進(jìn)制數(shù)乘法如圖4所示, 在試管ta , tb , . , tm-1 中, 分別表示被乘數(shù)的dna片斷與乘數(shù)各位的dna片斷按照乘數(shù)的低位到高位的順序以自動(dòng)機(jī)的方式并行完成移位運(yùn)算, 同時(shí)結(jié)合如上所述的生

32、物操作, 從而得到加法操作中的輸入串. s0表示ta , tb中移位運(yùn)算后前兩個(gè)輸入串完成加法運(yùn)算所得和的片斷, 同時(shí)再與第三個(gè)試管中移位操作后的輸入串作和的運(yùn)算得到s1, 如此類(lèi)推, 即可得到最后一個(gè)試管中為所有加法操作中輸入串的和的片斷sm-1, 利用檢測(cè)分子, 檢測(cè)該片斷代表的二進(jìn)制數(shù), 從而讀出相應(yīng)的運(yùn)算結(jié)果.圖4 m位二進(jìn)制數(shù)乘法的試管體系5編碼實(shí)例及復(fù)雜度分析dna限制性?xún)?nèi)切酶特異性結(jié)合于一段稱(chēng)為限制性酶識(shí)別序列的特殊dna序列之內(nèi)或其附近的特異位點(diǎn)上, 并在此切割雙鏈dna. 它可分為三類(lèi).在dna計(jì)算中, 類(lèi)和類(lèi)限制性酶都不常用. 類(lèi)限制修飾系統(tǒng)是由兩種酶分子組成的二元系統(tǒng),

33、其中一種常用的限制性?xún)?nèi)切酶, 它切割某一特異性的脫氧核苷酸系統(tǒng). dna被限制性?xún)?nèi)切酶切割后, 在切割處可以形成粘性末端和平頭末端兩種不同的結(jié)構(gòu). 不同的限制性?xún)?nèi)切酶所形成的粘性末端往往是不同的. 有相同的粘性末端而來(lái)源不同的dna片斷之間可以通過(guò)互補(bǔ)配對(duì)的堿基重新形成氫鍵. 類(lèi)限制修飾系統(tǒng)在本文中, 起著實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移的作用.foki酶的識(shí)別位點(diǎn)為5 -ggatg- 3, 剪切位點(diǎn)是(9, 13) . bsmfi酶的識(shí)別位點(diǎn)為5 -gggac- 3, 剪切位點(diǎn)是(10, 14). smii酶的識(shí)別位點(diǎn)為5 -atttaaat- 3, 剪切位點(diǎn)是識(shí)別位點(diǎn)內(nèi)部1/ 2 位置.5.1二進(jìn)制減法的編碼

34、實(shí)例為了驗(yàn)證基于dna自動(dòng)機(jī)的二進(jìn)制串行減法的可行性, 我們給出了一位二進(jìn)制減法運(yùn)算過(guò)程中所需分子的編碼. 表2為0, 1及結(jié)束時(shí)終止符t的編碼. 表3為轉(zhuǎn)移函數(shù)分子的編碼. 表4為檢測(cè)分子的編碼. 表20, 1及結(jié)束時(shí)終止符t的編碼01tgaccga ctggctcgcagc gcgtcgtatgcaatacgt表3轉(zhuǎn)移函數(shù)分子的編碼轉(zhuǎn)移函數(shù)對(duì)應(yīng)轉(zhuǎn)移函數(shù)分子的編碼gatccggatgtgactaggcctacacttggcgatccggatgtgctaggcctacaccgtcgatccggatgtg ctaggcctacaccgtcgatccggatgtgactaggcctacactcgt

35、cgatccggatgtgactaggcctacactgtcggatccggatgtgactaggcctacactggctgatccggatgtgactaggcctacactggctgatccggatgtgctaggcctacacgtcg表4 檢測(cè)結(jié)果的檢測(cè)分子的dna編碼終止?fàn)顟B(tài)棧頂元素對(duì)應(yīng)檢測(cè)分子的編碼s00gaccgatatgcatggtcccatttaaatgggacctatacgtaccagggtaaatttaccctgs01cagcgatatgcatggtcccatttaaatgggacctatacgtaccagggtaaatttaccctgs10gaccgatatgcatggtc

36、ccatttaaatgggacctatacgtaccagggtaaatttaccctgs11cagcgatatgcatggtcccatttaaatgggacctatacgtaccagggtaaatttaccctg5.2二進(jìn)制乘法的編碼實(shí)例為了驗(yàn)證基于dna自動(dòng)機(jī)的二進(jìn)制串行乘法的可行性, 我們給出了兩位二進(jìn)制乘法運(yùn)算過(guò)程中所需分子的編碼. 表5為00,01,10,11,12,0,1及結(jié)束時(shí)終止符t的編碼. 表6為轉(zhuǎn)移函數(shù)分子的編碼. 表7為檢測(cè)分子的編碼. 表5 00,01,10,11,12,0,1及結(jié)束時(shí)終止符t的編碼00gcaggccgtccg01acggactgcctg10gaagcgc

37、ttcgc11gacagcctgtcg12gcgaaccgcttc0caagcagttcgt1aagccgttcggctcatgtagtacat表6轉(zhuǎn)移函數(shù)分子的編碼轉(zhuǎn)移函數(shù)對(duì)應(yīng)轉(zhuǎn)移函數(shù)分子的編碼cagtcggatgtgagtcagcctacactcgtccagtcggatgtggtcagcctacacgtcccagtcggatgtg gtcagcctacactccgcagtcggatgtgagtcagcctacactgtcccagtcggatgtgagtcagcctacactcgtccagtcggatgtgagtcagcctacacttgcccagtcggatgtgagtcagcctacac

38、tcgtccagtcggatgtggtcagcctacacgcctcagtcggatgtggtcagcctacactccgcagtcggatgtggtcagcctacaccttccagtcggatgtggtcagcctacaccgtccagtcggatgtggtcagcctacactcgccagtcggatgtggtcagcctacaccgtccagtcggatgtggtcagcctacacctgtcagtcggatgtggtcagcctacactccgcagtcggatgtggtcagcctacactgtc表7 檢測(cè)結(jié)果的檢測(cè)分子的dna編碼終止?fàn)顟B(tài)棧頂元素對(duì)應(yīng)檢測(cè)分子的編碼0001acgg

39、gacatgtatggtcccatttaaatgggacctgtacataccagggtaaatttaccctg0012cgaagacatgtatggtcccatttaaatgggacctgtacataccagggtaaatttaccctg0101acgggacatgtatggtcccatttaaatgggacctgtacataccagggtaaatttaccctg0112cgaagacatgtatggtcccatttaaatgggacctgtacataccagggtaaatttaccctg1001acgggacatgtatggtcccatttaaatgggacctgtacataccagggt

40、aaatttaccctg1012cgaagacatgtatggtcccatttaaatgggacctgtacataccagggtaaatttaccctg1101acgggacatgtatggtcccatttaaatgggacctgtacataccagggtaaatttaccctg1112cgaagacatgtatggtcccatttaaatgggacctgtacataccagggtaaatttaccctg5.3復(fù)雜度分析基于dna下推自動(dòng)機(jī)m位二進(jìn)制減法, 每一位的運(yùn)算過(guò)程中, 包括dna下推自動(dòng)機(jī)的操作, 及對(duì)應(yīng)的兩次分離操作, 因此總共操作次數(shù)是2m次, 那么該操作的時(shí)間復(fù)雜度為o(m).

41、 在運(yùn)算過(guò)程中, 只需要對(duì)0, 1, 終止符號(hào), 以及轉(zhuǎn)移函數(shù)分子和檢測(cè)分子編碼. 因此, 需要dna鏈的條數(shù)沒(méi)有隨二進(jìn)制數(shù)的位數(shù)增多而增多, 則該算法的空間復(fù)雜度為 o(1) .基于dna下推自動(dòng)機(jī)兩個(gè)m位二進(jìn)制減法運(yùn)算過(guò)程中, 包括移位操作和加法操作, 移位操作有m次, 同時(shí)有連接操作 (2m-1)次, 加法操作m(m-1)次, 因此該操作的時(shí)間復(fù)雜度是o(m2). 在此過(guò)程中, 在移位操作中, 需要對(duì)0, 1 以及轉(zhuǎn)移函數(shù)分子編碼, 在加法操作中需要重新對(duì)0, 1進(jìn)行編碼, 以及對(duì)相應(yīng)的轉(zhuǎn)移函數(shù)分子編碼, 可以看到, 需要不超過(guò) o(m)條dna鏈, 則該算法的空間復(fù)雜度為 o(m) .

42、6結(jié)論與展望 提出了基于dna下推自動(dòng)機(jī)二進(jìn)制減法及乘法的實(shí)現(xiàn)方法, 給出了相應(yīng)的運(yùn)算模型, 操作步驟, 以及復(fù)雜度分析. 該模型操作數(shù)簡(jiǎn)單, 具有可行性, 只需對(duì)dna下推自動(dòng)機(jī)的硬件分子及軟件分子編碼好, 即可完成相應(yīng)的運(yùn)算操作. 除此之外, 還可以考慮減法運(yùn)算中, 差是負(fù)數(shù)的情形, 同時(shí)還可將其應(yīng)用到矩陣運(yùn)算等, 可以看到該模型的提出對(duì)研究dna計(jì)算機(jī)的運(yùn)算系統(tǒng)有重大意義.參考文獻(xiàn)1 adleman l m. molecular computation of solutions to combinatorial problems. science, 1994, 66 (11): 1021

43、-10242 pan l q, xu j, liu y c. a surface-based dna algorithm for the minimal vertex problem. progress in natural science, 2003, 13: 81-843 pan l q, liu g w, xu j. solid phase based dna solution of the coloring problem. progress in natural science, 2004, 14: 104-1074 guarnieri f, fliss m, bancroft c.

44、 making dna add. science, 1996, 273: 220-2235 guarnieri f, bancroft c. use of a horizontal chain reaction for dna-based addition. dimacs series in discrete mathematical theoretical computer science, 1999, 44: 105-1116 bernard y, allen p, siu l et al. dna implementation of addition in which the input

45、 strands are separate from the operator strands. biosystems, 1999, 52: 165-1747 fujiwara a, matsumoto k, chen w. procedures for logic and arithmetic operations with dna strands. international journal of foundations of computer science, 2004, 15 (3): 461- 4748 fukagawa h, fujiwara a. procedures for m

46、ultiplication and division in dna computing. fcs 2006: 95-1019 chang w l, guo m y, michael shan-hui ho. fast parallel molecular algorithms for dna-based computation: factoring integers. ieee transactions on nanobioscience, 2005, 4(2): 149-16310 winfree e, liu f et al. design and self-assembly of two

47、-dimensional dna crystals. nature, 1998, 394: 539-54411 mao c, labean t h et al. logical computation using algorithmic self-assembly of dna triple-crossover molecules. nature, 2000, 407: 93- 49612 benenson y, paz-elizur t, adar r et al. programmable and autonomous computing machine made of biomolecu

48、les. nature, 2001, 414: 430- 434 13 shi x l, zhang z et al. improve capability of dna automaton: dna automaton with three internal states and tape head move in two directions, lectnotes comput sc. 2005, 3645: 71-7914 zhang z, xu j, liu j et al. programmable pushdown store base on dna computing springer-verlag berlin heidelberg, 2006, 286-29315 cavaliere m, jonoska n, yogev s et al. biomolecule implementation of computing devices with unbounded memory. springer verlag berlin heidelberg, 2005, 3384: 35- 4916 peng y, turberfie