自組裝DNA計算模型的研究及應用.pdf

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

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

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

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

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

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

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

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