快速、強大且通用的DNA計算模型是DNA計算機實現(xiàn)的基礎。利用DNA自組裝執(zhí)行計算的想法已從實驗上被證明具有可行性�；贒NA自組裝的計算模型由于其通用性正被廣泛研究,已有多種理論模型被提出以解決各種NP問題。DNA自組裝憑借其自治性與可編程性被認為是實現(xiàn)DNA計算芯片化的可行手段。因此,對DNA自組裝計算模型進行研究具有理論與實際意義。本文首先研究了線性自組裝、樹狀自組裝及二維自組裝的計算能力。回顧了幾個通過形式語言表示法已經被證明的理論:線性自組裝等價于正則語言;樹狀自組裝等價于上下文無關語言;二維自組裝等價圖靈可識別語言。本文的主要工作有:1.本文提出了一種三維DNA自組裝計算模型。首先,從實驗的角度描述了三維DNA瓦片構造的可行性;其次,在二維瓦片組裝模型的基礎上,完善了三維模型的數(shù)學理論與形式化表示方法,為模型的進一步應用打下基礎。2.本文提出了一種枚舉型的三維DNA自組裝圖著色模型。首先,引入一種簡單的圖著色非確定性算法;其次,根據(jù)算法設計不同種類的DNA瓦片;最后,說明自組裝過程并對模型復雜性進行討論。分析表明模型的組裝時間為在線性,組裝所需的瓦片種類數(shù)為常數(shù)。對于3著色... 

【文章來源】：湖南大學湖南省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：66 頁

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 選題背景及意義
    1.2 國內外研究現(xiàn)狀和已有成果
        1.2.1 DNA 計算國際研究進展
        1.2.2 DNA 計算國內研究進展
        1.2.3 DNA 自組裝技術研究進展
        1.2.4 二維DNA 瓦片組裝模型研究進展
        1.2.5 圖著色問題的DNA 計算方法研究進展
    1.3 論文的研究思路和主要工作
    1.4 論文的結構
第2章 DNA 自組裝計算模型研究
    2.1 ADLEMAN 的開創(chuàng)性實驗
    2.2 DNA 自組裝的形式語言文法定義
    2.3 線性自組裝等價于正則語言
    2.4 樹狀自組裝等價于上下文無關語言
    2.5 二維自組裝等價于圖靈可識別語言
    2.6 一種二維自組裝抽象模型
        2.6.1 Wang 的瓦片覆蓋理論
        2.6.2 瓦片組裝模型的形式化表示
    2.7 本章小結
第3章 一種三維 DNA 自組裝計算模型
    3.1 三維DNA 瓦片構造
    3.2 模型的抽象幾何結構
    3.3 模型的數(shù)學表示
    3.4 本章小結
第4章 枚舉型三維 DNA 自組裝圖著色模型
    4.1 圖著色問題
    4.2 圖著色非確定性算法
    4.3 鄰接表與著色表
    4.4 三維瓦片設計
    4.5 自組裝過程
        4.5.1 種子配置
        4.5.2 成功組裝示例
        4.5.3 失敗組裝示例
    4.6 模型正確性分析
    4.7 模型復雜性分析
    4.8 本章小結
第5章 非枚舉型三維DNA 自組裝圖著色模型
    5.1 圖著色問題
    5.2 自組裝算法設計
        5.2.1 剪枝回溯圖著色算法
        5.2.2 基于有序鄰居的頂點排序算法
        5.2.3 帶剪枝策略的非確定性圖著色算法
    5.3 算法模擬
    5.4 自組裝系統(tǒng)設計
        5.4.1 有限瓦片集合
        5.4.2 粘結強度函數(shù)
        5.4.3 閥值溫度
    5.5 自組裝系統(tǒng)驗證
    5.6 模型復雜性分析
    5.7 本章小結
結論
參考文獻
致謝


【參考文獻】：
期刊論文
[1]Arithmetic computation using self-assembly of DNA tiles:subtraction and division[J]. Xuncai Zhang a,b, Yanfeng Wang b, Zhihua Chen a, Jin Xu a,*, Guangzhao Cui b a The Key Laboratory of Image Processing and Intelligent Control, Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China b School of Electrical and Electronic Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China.  Progress in Natural Science. 2009(03)
[2]經典Ramsey數(shù)DNA計算模型（Ⅱ）:基于位序列的DNA計算模型[J]. 許進,范月科.  計算機學報. 2008(12)
[3]經典Ramsey數(shù)DNA計算模型（Ⅰ）:位序列計算模型[J]. 許進,范月科.  計算機學報. 2008(12)
[4]基于DNA計算自組裝模型的Diffie-Hellman算法破譯（英文）[J]. 陳智華.  計算機學報. 2008(12)
[5]基于自組裝DNA計算的NTRU密碼系統(tǒng)破譯方案（英文）[J]. 張勛才,牛瑩,崔光照,王延峰.  計算機學報. 2008(12)
[6]DNA納米結構仿中國地圖[J]. 錢璐璐,汪穎,張釗,趙健,潘敦,張益,劉強,樊春海,胡鈞,賀林.  科學通報. 2006(24)
[7]基于線性自組裝的DNA加法[J]. 趙健,錢璐璐,劉強,張治洲,賀林.  科學通報. 2006(21)
[8]一種圖頂點著色DNA計算機模型[J]. 許進,強小利,方剛,周康.  科學通報. 2006(04)
[9]圖的頂點著色問題的一種DNA算法[J]. 孫川,朱翔鷗,劉文斌,許進.  計算機工程與應用. 2006(04)
[10]圖頂點著色問題的DNA粘貼算法[J]. 王淑棟,劉文斌,許進.  系統(tǒng)工程與電子技術. 2005(03)



本文編號：3185851