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

1、DNA計算具有高并行、高存儲密度、低耗能、計算速度快等優(yōu)點，許多用傳統(tǒng)計算機無法解決的NP問題大都可用DNA計算予以解決。近年來人們提出了許多DNA計算模型，如粘貼模型、剪接系統(tǒng)模型、分子瓦自組裝模型等，其中DNA計算自組裝模型以其簡單易行得到許多專家學者的重視。DNA計算自組裝模型是通過DNA分子間的相互配對組裝成特定的結構來完成計算的。它是DNA計算、Ting理論和DNA納米技術的一個有機組合，在解決NP完全問題上具有天然的優(yōu)勢。本

2、文以DNA計算中的自組裝模型為核心，NP問題為主要研究對象，用DNA自組裝模型對兩個NP問題進行了求解。本文的主要內容：
　　首先，在介紹DNA背景知識的基礎上，闡述DNA計算在信息安全領域中的應用，分析了目前已提出的基于DNA計算的密鑰搜索方案，討論了DNA計算在信息加密、信息隱藏及認證等方面的應用。認為現(xiàn)有DNA計算模式雖然不能對傳統(tǒng)密碼學構成真正的威脅，但為信息安全帶來了新的機遇和挑戰(zhàn)。
　　其次，研究了DNA計算的核

3、心問題——編碼問題：一個受多約束條件約束的多目標優(yōu)化問題。粒子群優(yōu)化算法規(guī)則簡單且易于編程實現(xiàn)是處理多目標優(yōu)化問題的重要工具；遺傳算法具有魯棒性，特別適于處理非線性問題，常被用于搜索更好的DNA編碼序列，但遺傳算法容易產生近親繁殖出現(xiàn)早熟而陷入局部最優(yōu)。本文提出了一種基于改進的粒子群遺傳算法的DNA編碼序列優(yōu)化方法，它將改進的粒子群算法作為基本遺傳算法的一個重要算子。仿真結果表明該混合算法性能良好。
　　再次，在研究DNA計算自組

4、裝模型基礎上，將其應用于求解0-1背包問題和最大團問題。作者分析了0-1背包問題的約束條件，并將它們轉化為兩個基本操作：“加法”和“減法”，還給出了求解0-1背包問題的非確定性實現(xiàn)方案，理論上該方案可在多項式時間內求解此問題。最大團問題是一個經典的圖論問題，其目標是找出給定圖的最大完全子圖。本文設計了一種新的運算規(guī)則和一些計算Tile，實現(xiàn)了對該問題的求解，為進一步研究最大團問題提供了一種新思路。
　　回顧DNA計算研究進展，DN