K-臂DNA計算在最近鄰聚類和MCP中的應用研究.pdf

1、生物分子的大小在納米尺度,同時具有良好的可操作性和強大的信號轉導能力,這為利用生物分子元件組裝生物計算機的研究提供了可能。在生物計算領域,DNA計算從1994年Adleman博士成功采用生化試驗解決了7頂點Hamilton問題以來,DNA計算的發(fā)展就引起了廣泛的關注。DNA計算采用DNA鏈作為信息載體,將原始問題映射成DNA編碼,采用生物酶為計算工具,分子水平的生化操作為計算方法,于生物實驗室進行一些列操作而求解問題。DNA計算發(fā)展近2

2、0年來,諸多數(shù)學、生物、納米科學和信息科學的科研人員都投身與這一領域。從目前來看,DNA計算在優(yōu)化計算、信息安全,特別在求解組合優(yōu)化問題中的NP問題上具有一種“天然”優(yōu)勢,同時無論在理論模型還是實踐水平上,DNA計算都取得了很大的進展與突破,但其本身仍未成熟,仍然存在諸多理論問題和實際問題亟待解決,尤其是生物實驗水平?jīng)]有規(guī)范化和成熟, DNA模型的構建和使用由于其自身結構的限制而不能非常靈活。本文致力于對k-臂DNA分子模型的研究,在理

3、論上完善該模型與發(fā)夾模型的關系,用以解決NP問題,具有十分重要的現(xiàn)實意義。本文的主要研究工作如下:
　　第一章在介紹了研究背景和意義之后,從宏觀和微觀兩個角度,采用文獻計量學的方法,對DNA計算發(fā)展近20年的狀況—括文獻計量、核心期刊、核心作者等問題—進行了研究綜述,為以后的研究者提供參考。
　　第二章介紹了DNA計算的基礎理論知識,重點針對本文要使用的三類基礎模型—k-臂分子模型、發(fā)夾模型、三鏈模型進行了闡述,并基于三者自

4、身優(yōu)勢,探索了將其混合使用的可能性。即發(fā)夾模型完全可以作為k-臂分子模型的計算控制模型使用,而三鏈模型則是一種良性的篩選模型,可參與雙鏈結構的篩選過程。為了充分說明DNA計算中編碼水平、生物操作水平、模型發(fā)展對DNA計算會產(chǎn)生及其重要的推動作用,在第二章的后半部分,以三鏈模型為基礎模型,改進原有編碼水平并采用不同于原有讀取解的方式,提出了對0-1規(guī)劃問題的改進算法。
　　第三章在第二章的基礎上,討論了k-臂DNA分子中的一種特殊結

5、構—3-臂DNA分子的特性,其可以直觀表達二叉樹的結構。因此,本章提出了基于3-臂分子的結構優(yōu)勢,結合發(fā)夾模型和三鏈結構的篩選,求解最近鄰層次聚類問題的算法。在算法復雜性分析過程中,可看出k-臂分子在編碼規(guī)模和操作復雜性上的優(yōu)勢。另外,該算法的提出,也拓展了k-臂DNA分子模型的應用范圍,可以用來解決更多基于二叉樹進行優(yōu)化求解的問題。
　　k-臂 DNA分子模型具有“天然”的表達圖結構的能力,故對于圖論問題的求解具有直觀上的優(yōu)勢。

6、圖論問題中諸多問題是在尋找頂點與邊滿足一定關系的特殊子圖或者集合,k-臂DNA分子與其控制模型—發(fā)夾模型結合,就可以有效控制k-臂分子上參與計算的邊的數(shù)量和限制只有某些邊才可以參與計算的實現(xiàn)。在該理論基礎上,第四章提出了基于k-臂DNA分子模型求解最大團問題的算法。對一般情況的模擬發(fā)現(xiàn),該算法所需的頂點塊空間復雜性為多項式級別,優(yōu)于O((√3)n)。另外,引入進化計算的思想,給出算法流程,嘗試改進解空間爆炸性問題,通過c++編寫進化計算