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

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

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

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

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

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

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