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

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

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

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

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

5、構(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)勢。

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