資源描述：
《自組裝dna計算模型地研究與應用論文》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、華中科技大學博士學位論文摘要DNA計算是一種基于生化反應機理的新型信息處理模式，與基于圖靈機思想的電子計算機原理截然不同。從DNA計算解決問題規(guī)模的能力來看，其發(fā)展相當迅速；1994年，Adleman給出了僅能處理7個頂點有向圖中的計算問題實驗，到2007年我28國研制出搜索能力可達到10次的圖頂點著色DNA計算機，僅用了15年的時間。特別是近年來，DNA分子自組裝理論、實驗及操控技術的快速發(fā)展，為DNA計算機的實現技術提供了一種新的理論和手段。正是憑借其海量存儲和超大規(guī)模并行運算能力，從理論上可克服電子計算機存儲量與運算速度上的不足，有望成為NP-完全問題的
2、潛在解決方案之一。DNA分子自組裝是指在一定的溫度，濃度，酸堿度以及特定酶的作用下，一些帶有輸入信息的DNA分子（比如說，DNATile）根據Watson-Crick互補配對原則，自組裝生成新的帶有輸出信息的DNA分子的過程。近十年中，DNA分子自組裝技術在分子計算、生物物理、納米技術等各個方面都得到了廣泛的應用。尤其對DNA計算的發(fā)展具有重要的指導意義。自組裝DNA計算模型是通過DNA分子間的相互作用形成特定的構型來完成計算過程。它組合了DNA計算、Ting理論和DNA納米技術，成為目前備受關注的模型之一。在計算過程中，它避免了其它DNA計算模型所需要的眾多
3、實驗操作次數，減少了操作帶來的時間消耗和誤差傾向。本文在深入研究自組裝DNA計算機理的基礎上，對其在NP-完全問題和信息安全領域中的應用展開討論，并給出一種編碼設計方案。本文創(chuàng)新點如下：首先，分析了傳統(tǒng)計算中減法和除法的運算機理，按照除法的運算過程，將除法運算分為比較子系統(tǒng)，復制子系統(tǒng)和減法子系統(tǒng)。借助于已有的Tile類型，將待運算的信息通過編碼與Tile的粘性末端相關聯(lián)，用DNATile自組裝技術對三個子系統(tǒng)一一給予了實現。最后合并這三個子系統(tǒng)，建立了基于自組裝DNA計算的減法和除法運算模型。其次，將自組裝DNA計算模型應用于求解組合優(yōu)化問題，包括0-1規(guī)劃
4、問題和圖著色問題。0-1規(guī)劃問題作為運籌學中一個重要問題，到目前為止還沒有好的算法。I華中科技大學博士學位論文本文通過對0-1規(guī)劃問題中的約束處理機制進行分析，將約束處理分為兩個基本操作：“與”操作和“比較”操作。并給出了“與”操作和“比較”操作的自組裝DNA計算實現方案。通過組合這兩種操作，根據DNA自組裝技術，對于任意可行解，能自動判斷它是否滿足所有給定的約束條件。借助于DNA計算的并行性，提出了基于自組裝DNA計算模型的0-1規(guī)劃問題中約束處理方案。理論分析表明，采用自組裝DNA計算模型，可以在多項式時間內解決這一問題。圖頂點著色問題與現實生活中的時間表
5、問題、排序問題和任務分配問題等密切相關。這里根據DNA分子自組裝的特性，引入非確定性算法，可非確定性的給定圖著色方案。利用自組裝DNA計算的并行性優(yōu)勢，并行的驗證所有可能著色方案，以高概率地給出問題的解，在多項式時間內解決圖頂點著色問題。然后，采用DNATile編碼信息，借助于Tile之間的粘性末端進行自組裝，給出了一些兩個整數的乘法運算和兩個多項式乘法運算的實現方案。在此基礎上，通過引入非確定性的指派Tile，提出了一種用自組裝DNA計算破譯NTRU和RSA公鑰密碼系統(tǒng)的非確定性算法。通過創(chuàng)建數以億計的參與計算的DNATile，算法可以并行地以高概率地破譯這
6、兩種密碼系統(tǒng)。該方法最大的優(yōu)點是充分利用了DNATile具有的海量存儲能力，生化反應的巨大并行性以及組裝的自發(fā)有序性。最后，針對自組裝DNA計算的編碼問題給出了一個序列設計方案。編碼質量、編碼數量、序列長度與DNA計算的可靠性、有效性、可擴充性密切相關。優(yōu)化DNA編碼設計最本質的規(guī)律，蘊藏在DNA雜交過程相互綁定時的熱動力學之中。采用熱力學編碼約束，建立了編碼序列設計的目標優(yōu)化數學模型。借助于IWO算法，提出了一種用于編碼序列設計的優(yōu)化算法，闡述了算法的實現過程。通過將本文算法產生的序列和Deaton等提供的DNA序列進行比較和分析，證實了本文算法可產生熱力學
7、性質更穩(wěn)定的DNA序列，驗證了本文算法的有效性，拓展了IWO算法在離散空間中的應用。關鍵詞：DNA計算，Tile自組裝，算術運算，0-1整數規(guī)劃，圖著色，編碼設計，NTRU破譯，整數分解II華中科技大學博士學位論文AbstractDNAcomputingisanewinformationprocessingpattern.Itisdifferentfromelectroniccomputerprinciple,asthatelectroniccomputerprinciplebasedonTuringidea,whileDNAcomputingbasedonb
8、iochemicalreaction.
