自組裝DNA計(jì)算模型的研究及應(yīng)用.pdf

1、DNA計(jì)算是一種基于生化反應(yīng)機(jī)理的新型信息處理模式，與基于圖靈機(jī)思想的電子計(jì)算機(jī)原理截然不同。從DNA 計(jì)算解決問(wèn)題規(guī)模的能力來(lái)看，其發(fā)展相當(dāng)迅速。
　　 1994年，Adleman 給出了僅能處理7個(gè)頂點(diǎn)有向圖中的計(jì)算問(wèn)題實(shí)驗(yàn)，到2007年我國(guó)研制出搜索能力可達(dá)到10 28 次的圖頂點(diǎn)著色DNA 計(jì)算機(jī)，僅用了15年的時(shí)間。
　　 特別是近年來(lái)，DNA分子自組裝理論、實(shí)驗(yàn)及操控技術(shù)的快速發(fā)展，為DNA 計(jì)算機(jī)的實(shí)現(xiàn)技術(shù)

2、提供了一種新的理論和手段。正是憑借其海量存儲(chǔ)和超大規(guī)模并行運(yùn)算能力，從理論上可克服電子計(jì)算機(jī)存儲(chǔ)量與運(yùn)算速度上的不足，有望成為NP-完全問(wèn)題的潛在解決方案之一。
　　 DNA 分子自組裝是指在一定的溫度，濃度，酸堿度以及特定酶的作用下，一些帶有輸入信息的DNA 分子（比如說(shuō)，DNA Tile）根據(jù)Watson-Crick 互補(bǔ)配對(duì)原則，自組裝生成新的帶有輸出信息的DNA 分子的過(guò)程。近十年中，DNA 分子自組裝技術(shù)在分子計(jì)算、生

3、物物理、納米技術(shù)等各個(gè)方面都得到了廣泛的應(yīng)用。尤其對(duì)DNA計(jì)算的發(fā)展具有重要的指導(dǎo)意義。自組裝DNA 計(jì)算模型是通過(guò)DNA 分子間的相互作用形成特定的構(gòu)型來(lái)完成計(jì)算過(guò)程。它組合了DNA 計(jì)算、Ting 理論和DNA 納米技術(shù)，成為目前備受關(guān)注的模型之一。在計(jì)算過(guò)程中，它避免了其它DNA 計(jì)算模型所需要的眾多實(shí)驗(yàn)操作次數(shù)，減少了操作帶來(lái)的時(shí)間消耗和誤差傾向。本文在深入研究自組裝DNA 計(jì)算機(jī)理的基礎(chǔ)上，對(duì)其在NP-完全問(wèn)題和信息安全領(lǐng)域中

4、的應(yīng)用展開討論，并給出一種編碼設(shè)計(jì)方案。本文創(chuàng)新點(diǎn)如下：
　　 首先，分析了傳統(tǒng)計(jì)算中減法和除法的運(yùn)算機(jī)理，按照除法的運(yùn)算過(guò)程，將除法運(yùn)算分為比較子系統(tǒng)，復(fù)制子系統(tǒng)和減法子系統(tǒng)。借助于已有的Tile類型，將待運(yùn)算的信息通過(guò)編碼與Tile的粘性末端相關(guān)聯(lián)，用DNA Tile 自組裝技術(shù)對(duì)三個(gè)子系統(tǒng)一一給予了實(shí)現(xiàn)。最后合并這三個(gè)子系統(tǒng)，建立了基于自組裝DNA 計(jì)算的減法和除法運(yùn)算模型。
　　 其次，將自組裝DNA 計(jì)算模型應(yīng)

5、用于求解組合優(yōu)化問(wèn)題，包括0-1 規(guī)劃問(wèn)題和圖著色問(wèn)題。0-1 規(guī)劃問(wèn)題作為運(yùn)籌學(xué)中一個(gè)重要問(wèn)題，到目前為止還沒(méi)有好的算法。
　　 本文通過(guò)對(duì)0-1 規(guī)劃問(wèn)題中的約束處理機(jī)制進(jìn)行分析，將約束處理分為兩個(gè)基本操作：“與”操作和“比較”操作。并給出了“與”操作和“比較”操作的自組裝DNA 計(jì)算實(shí)現(xiàn)方案。通過(guò)組合這兩種操作，根據(jù)DNA 自組裝技術(shù)，對(duì)于任意可行解，能自動(dòng)判斷它是否滿足所有給定的約束條件。借助于DNA 計(jì)算的并行性，提出

6、了基于自組裝DNA 計(jì)算模型的0-1 規(guī)劃問(wèn)題中約束處理方案。理論分析表明，采用自組裝DNA計(jì)算模型，可以在多項(xiàng)式時(shí)間內(nèi)解決這一問(wèn)題。
　　 圖頂點(diǎn)著色問(wèn)題與現(xiàn)實(shí)生活中的時(shí)間表問(wèn)題、排序問(wèn)題和任務(wù)分配問(wèn)題等密切相關(guān)。這里根據(jù)DNA 分子自組裝的特性，引入非確定性算法，可非確定性的給定圖著色方案。利用自組裝DNA 計(jì)算的并行性優(yōu)勢(shì)，并行的驗(yàn)證所有可能著色方案，以高概率地給出問(wèn)題的解，在多項(xiàng)式時(shí)間內(nèi)解決圖頂點(diǎn)著色問(wèn)題。
　　

7、 然后，采用DNA Tile 編碼信息，借助于Tile之間的粘性末端進(jìn)行自組裝，給出了一些兩個(gè)整數(shù)的乘法運(yùn)算和兩個(gè)多項(xiàng)式乘法運(yùn)算的實(shí)現(xiàn)方案。在此基礎(chǔ)上，通過(guò)引入非確定性的指派Tile，提出了一種用自組裝DNA 計(jì)算破譯NTRU和RSA公鑰密碼系統(tǒng)的非確定性算法。通過(guò)創(chuàng)建數(shù)以億計(jì)的參與計(jì)算的DNA Tile，算法可以并行地以高概率地破譯這兩種密碼系統(tǒng)。該方法最大的優(yōu)點(diǎn)是充分利用了DNA Tile 具有的海量存儲(chǔ)能力，生化反應(yīng)的巨大并行性以

8、及組裝的自發(fā)有序性。
　　 最后，針對(duì)自組裝DNA 計(jì)算的編碼問(wèn)題給出了一個(gè)序列設(shè)計(jì)方案。編碼質(zhì)量、編碼數(shù)量、序列長(zhǎng)度與DNA 計(jì)算的可靠性、有效性、可擴(kuò)充性密切相關(guān)。優(yōu)化DNA編碼設(shè)計(jì)最本質(zhì)的規(guī)律，蘊(yùn)藏在DNA 雜交過(guò)程相互綁定時(shí)的熱動(dòng)力學(xué)之中。采用熱力學(xué)編碼約束，建立了編碼序列設(shè)計(jì)的目標(biāo)優(yōu)化數(shù)學(xué)模型。借助于IWO算法，提出了一種用于編碼序列設(shè)計(jì)的優(yōu)化算法，闡述了算法的實(shí)現(xiàn)過(guò)程。通過(guò)將本文算法產(chǎn)生的序列和Deaton等提供的D