本文關(guān)鍵詞：K-臂DNA計算在最近鄰聚類和MCP中的應(yīng)用研究，由筆耕文化傳播整理發(fā)布。

【摘要】：生物分子的大小在納米尺度，同時具有良好的可操作性和強(qiáng)大的信號轉(zhuǎn)導(dǎo)能力，這為利用生物分子元件組裝生物計算機(jī)的研究提供了可能。在生物計算領(lǐng)域，DNA計算從1994年Adleman博士成功采用生化試驗解決了7頂點Hamilton問題以來，DNA計算的發(fā)展就引起了廣泛的關(guān)注。DNA計算采用DNA鏈作為信息載體，將原始問題映射成DNA編碼，采用生物酶為計算工具，分子水平的生化操作為計算方法，于生物實驗室進(jìn)行一些列操作而求解問題。DNA計算發(fā)展近20年來，諸多數(shù)學(xué)、生物、納米科學(xué)和信息科學(xué)的科研人員都投身與這一領(lǐng)域。從目前來看，DNA計算在優(yōu)化計算、信息安全，特別在求解組合優(yōu)化問題中的NP問題上具有一種“天然”優(yōu)勢，同時無論在理論模型還是實踐水平上，DNA計算都取得了很大的進(jìn)展與突破，但其本身仍未成熟，仍然存在諸多理論問題和實際問題亟待解決，尤其是生物實驗水平?jīng)]有規(guī)范化和成熟，DNA模型的構(gòu)建和使用由于其自身結(jié)構(gòu)的限制而不能非常靈活。本文致力于對k-臂DNA分子模型的研究，在理論上完善該模型與發(fā)夾模型的關(guān)系，用以解決NP問題，具有十分重要的現(xiàn)實意義。本文的主要研究工作如下： 第一章在介紹了研究背景和意義之后，從宏觀和微觀兩個角度，采用文獻(xiàn)計量學(xué)的方法，對DNA計算發(fā)展近20年的狀況——包括文獻(xiàn)計量、核心期刊、核心作者等問題——進(jìn)行了研究綜述，為以后的研究者提供參考。 第二章介紹了DNA計算的基礎(chǔ)理論知識，重點針對本文要使用的三類基礎(chǔ)模型——k-臂分子模型、發(fā)夾模型、三鏈模型進(jìn)行了闡述，并基于三者自身優(yōu)勢，探索了將其混合使用的可能性。即發(fā)夾模型完全可以作為k-臂分子模型的計算控制模型使用，而三鏈模型則是一種良性的篩選模型，可參與雙鏈結(jié)構(gòu)的篩選過程。為了充分說明DNA計算中編碼水平、生物操作水平、模型發(fā)展對DNA計算會產(chǎn)生及其重要的推動作用，在第二章的后半部分，以三鏈模型為基礎(chǔ)模型，改進(jìn)原有編碼水平并采用不同于原有讀取解的方式，提出了對0-1規(guī)劃問題的改進(jìn)算法。 第三章在第二章的基礎(chǔ)上，討論了k-臂DNA分子中的一種特殊結(jié)構(gòu)——3-臂DNA分子的特性，其可以直觀表達(dá)二叉樹的結(jié)構(gòu)。因此，本章提出了基于3-臂分子的結(jié)構(gòu)優(yōu)勢，結(jié)合發(fā)夾模型和三鏈結(jié)構(gòu)的篩選，求解最近鄰層次聚類問題的算法。在算法復(fù)雜性分析過程中，可看出k-臂分子在編碼規(guī)模和操作復(fù)雜性上的優(yōu)勢。另外，該算法的提出，也拓展了k-臂DNA分子模型的應(yīng)用范圍，可以用來解決更多基于二叉樹進(jìn)行優(yōu)化求解的問題。 k-臂DNA分子模型具有“天然”的表達(dá)圖結(jié)構(gòu)的能力，故對于圖論問題的求解具有直觀上的優(yōu)勢。圖論問題中諸多問題是在尋找頂點與邊滿足一定關(guān)系的特殊子圖或者集合，k-臂DNA分子與其控制模型——發(fā)夾模型結(jié)合，就可以有效控制k-臂分子上參與計算的邊的數(shù)量和限制只有某些邊才可以參與計算的實現(xiàn)。在該理論基礎(chǔ)上，第四章提出了基于k-臂DNA分子模型求解最大團(tuán)問題的算法。對一般情況的模擬發(fā)現(xiàn)，該算法所需的頂點塊空間復(fù)雜性為多項式級別，優(yōu)于O(（√3）n)。另外，引入進(jìn)化計算的思想，給出算法流程，嘗試改進(jìn)解空間爆炸性問題，通過c++編寫進(jìn)化計算的仿真實驗，檢驗進(jìn)化計算為解空間爆炸問題的解決的貢獻(xiàn)。 第五章給出相應(yīng)的應(yīng)用實例，對問題進(jìn)行編碼和按照算法操作步驟進(jìn)行求解，通過實例驗證的方式，說明所提出的算法的可行性和有效性。
【關(guān)鍵詞】：DNA計算 k-臂DNA模型 三鏈模型 發(fā)夾模型 最近鄰聚類 最大團(tuán)問題
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：Q523;TP38
【目錄】：

• 目錄4-6
• 摘要6-8
• ABSTRACT8-10
• 第一章 緒論10-25
• 1.1 DNA 計算產(chǎn)生的背景和意義10-11
• 1.1.1 研究背景10-11
• 1.1.2 研究意義11
• 1.2 文獻(xiàn)綜述11-22
• 1.2.1 DNA 計算文獻(xiàn)計量11-20
• 1.2.2 DNA 計算研究現(xiàn)狀20-22
• 1.3 本文的研究內(nèi)容與創(chuàng)新點22-23
• 1.3.1 本文的研究內(nèi)容與框架22-23
• 1.3.2 本文的創(chuàng)新點23
• 1.4 本文的組織結(jié)構(gòu)23-25
• 第二章 DNA 計算建模25-35
• 2.1 DNA 計算理論基礎(chǔ)25-29
• 2.1.1 DNA 分子結(jié)構(gòu)25-26
• 2.1.2 DNA 計算編碼問題26-27
• 2.1.3 生物操作27-29
• 2.2 DNA 計算基礎(chǔ)模型29-31
• 2.2.1 DNA 發(fā)夾模型構(gòu)建29-30
• 2.2.2 三鏈 DNA 分子模型構(gòu)建30
• 2.2.3 k 臂 DNA 分子模型構(gòu)建30-31
• 2.3 基于三鏈 DNA 結(jié)構(gòu)的 0 1 規(guī)劃改進(jìn)算法31-34
• 2.3.1 0 1 整數(shù)規(guī)劃問題31-32
• 2.3.2 改進(jìn)算法32-33
• 2.3.3 算法分析33-34
• 2.4 本章小結(jié)34-35
• 第三章 基于 3 臂 DNA 分子模型求解最近鄰聚類問題35-39
• 3.1 最近鄰聚類問題的分析與轉(zhuǎn)化35-36
• 3.2 基于 3 臂 DNA 分子結(jié)構(gòu)的 DNA 算法36-38
• 3.2.1 DNA 編碼36
• 3.2.2 生物算法36-38
• 3.3 算法復(fù)雜性討論38
• 3.3.1 時間復(fù)雜度（操作復(fù)雜度）38
• 3.3.2 編碼序列規(guī)模38
• 3.3.3 空間復(fù)雜性38
• 3.4 本章小結(jié)38-39
• 第四章 基于 k 臂 DNA 分子模型求解最大團(tuán)問題(MCP)39-48
• 4.1 最大團(tuán)問題39
• 4.2 基于 k 臂 DNA 分子模型的算法39-42
• 4.2.1 結(jié)構(gòu)塊（Building Block）編碼39-40
• 4.2.2 頂點塊預(yù)處理算法40-41
• 4.2.3 算法實現(xiàn)41-42
• 4.3 算法復(fù)雜性42-43
• 4.3.1 時間復(fù)雜性（操作復(fù)雜性）42
• 4.3.2 編碼序列規(guī)模42-43
• 4.4 最大團(tuán)問題的三維 DNA 圖結(jié)構(gòu)進(jìn)化算法43-46
• 4.4.1 DNA 計算與進(jìn)化計算43-44
• 4.4.2 進(jìn)化計算改進(jìn)解空間規(guī)模算法44
• 4.4.3 進(jìn)化算法與 DNA 計算的結(jié)合算法44-45
• 4.4.4 仿真實驗45-46
• 4.5 本章小結(jié)46-48
• 第五章 最近鄰聚類和 MPC 的 DNA 算法實例分析48-55
• 5.1 三鏈 DNA 分子模型應(yīng)用實例48-50
• 5.1.1 問題描述48
• 5.1.2 基于三鏈模型的求解過程48-50
• 5.2 基于 3 臂 DNA 分子模型的層次聚類算法應(yīng)用實例50-52
• 5.3 基于 k 臂 DNA 分子模型的最大團(tuán)問題算應(yīng)用實例52-54
• 5.4 本章小結(jié)54-55
• 第六章 結(jié)論與展望55-58
• 6.1 研究工作總結(jié)55-56
• 6.2 后續(xù)研究及展望56-58
• 6.2.1 后續(xù)研究及問題56
• 6.2.2 DNA 計算展望56-58
• 參考文獻(xiàn)58-62
• 致謝62-63
• 碩士期間發(fā)表的論文和參與的項目63-64
• 附錄一64-79
• 附錄二79-85

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 周康;劉朔;覃磊;易校尉;;基于粘貼模型的最大團(tuán)問題算法[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2010年09期

2 李肯立;姚鳳娟;李仁發(fā);許進(jìn);;基于分治的背包問題DNA計算機(jī)算法[J];計算機(jī)研究與發(fā)展;2007年06期

3 張社民;方剛;;連通度問題的三維DNA結(jié)構(gòu)進(jìn)化算法[J];計算機(jī)工程與應(yīng)用;2007年07期

4 楊靜;殷志祥;;基于抗原中介三鏈DNA結(jié)構(gòu)的0-1整數(shù)規(guī)劃[J];計算機(jī)工程與應(yīng)用;2008年02期

5 王立霞;淮曉永;;基于語義的中文文本關(guān)鍵詞提取算法[J];計算機(jī)工程;2012年01期

6 薛潔;劉希玉;;基于DNA計算的層次圖聚類算法[J];計算機(jī)工程;2012年12期

7 李汪根;丁永生;;DNA計算機(jī)中隊列數(shù)據(jù)結(jié)構(gòu)的設(shè)計及實現(xiàn)[J];計算機(jī)學(xué)報;2007年06期

8 李肯立;周旭;鄒舒婷;;一種改進(jìn)的最大團(tuán)問題DNA計算機(jī)算法(英文)[J];計算機(jī)學(xué)報;2008年12期

9 李汪根;丁永生;任立紅;;DNA計算機(jī)中廣義表數(shù)據(jù)結(jié)構(gòu)的設(shè)計與實現(xiàn)(英文)[J];計算機(jī)學(xué)報;2008年12期

10 張成;楊靜;王淑棟;;DNA計算中熒光技術(shù)的應(yīng)用及其發(fā)展[J];計算機(jī)學(xué)報;2009年12期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 張鴻雁;基于DNA計算的聚類算法研究[D];山東師范大學(xué);2011年

  本文關(guān)鍵詞：K-臂DNA計算在最近鄰聚類和MCP中的應(yīng)用研究，，由筆耕文化傳播整理發(fā)布。

本文編號：351595