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

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

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

【學(xué)位級別】：碩士

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


【參考文獻(xiàn)】：
期刊論文
[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]經(jīng)典Ramsey數(shù)DNA計(jì)算模型（Ⅱ）:基于位序列的DNA計(jì)算模型[J]. 許進(jìn),范月科.  計(jì)算機(jī)學(xué)報(bào). 2008(12)
[3]經(jīng)典Ramsey數(shù)DNA計(jì)算模型（Ⅰ）:位序列計(jì)算模型[J]. 許進(jìn),范月科.  計(jì)算機(jī)學(xué)報(bào). 2008(12)
[4]基于DNA計(jì)算自組裝模型的Diffie-Hellman算法破譯（英文）[J]. 陳智華.  計(jì)算機(jī)學(xué)報(bào). 2008(12)
[5]基于自組裝DNA計(jì)算的NTRU密碼系統(tǒng)破譯方案（英文）[J]. 張勛才,�，�,崔光照,王延峰.  計(jì)算機(jī)學(xué)報(bào). 2008(12)
[6]DNA納米結(jié)構(gòu)仿中國地圖[J]. 錢璐璐,汪穎,張釗,趙健,潘敦,張益,劉強(qiáng),樊春海,胡鈞,賀林.  科學(xué)通報(bào). 2006(24)
[7]基于線性自組裝的DNA加法[J]. 趙健,錢璐璐,劉強(qiáng),張治洲,賀林.  科學(xué)通報(bào). 2006(21)
[8]一種圖頂點(diǎn)著色DNA計(jì)算機(jī)模型[J]. 許進(jìn),強(qiáng)小利,方剛,周康.  科學(xué)通報(bào). 2006(04)
[9]圖的頂點(diǎn)著色問題的一種DNA算法[J]. 孫川,朱翔鷗,劉文斌,許進(jìn).  計(jì)算機(jī)工程與應(yīng)用. 2006(04)
[10]圖頂點(diǎn)著色問題的DNA粘貼算法[J]. 王淑棟,劉文斌,許進(jìn).  系統(tǒng)工程與電子技術(shù). 2005(03)



本文編號：3185851