一種圖頂點著色DNA計算機(jī)模型

《一種圖頂點著色DNA計算機(jī)模型》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第51卷第4期2006年2月論文一種圖頂點著色DNA計算機(jī)模型①②①①①許進(jìn)強(qiáng)小利方剛周康(①華中科技大學(xué)分子生物計算機(jī)研究所,武漢430074;②大連大學(xué)生物工程學(xué)院,大連116622.E-mail:jxu@mail.hust.edu.cn)摘要設(shè)計了一種專門用于求解圖頂點著色的DNA計算機(jī).該計算機(jī)的主體是由一個可變溫度的聚丙烯酰胺凝膠電泳構(gòu)成.可變溫度的電泳由3部分組成,分別為“解鏈區(qū)”、“非解區(qū)”和“解區(qū)”.它們對應(yīng)的可控溫度分別為Tm1,Tm2和Tm3.本文介紹了該計算機(jī)的基本結(jié)構(gòu)與基本原理,給出了存儲庫的構(gòu)建方法,特別討論

2、了編碼問題,并成功地對5個頂點的圖給出了系統(tǒng)的生物操作與生化實驗.關(guān)鍵詞DNA計算機(jī)圖頂點著色編碼[1]自從Adleman開拓了DNA計算模型以來,無本研究設(shè)計了一種用于求解圖的頂點著色問題論在理論上還是生物操作技術(shù)上,DNA計算與DNA的專用型DNA計算機(jī)模型.該計算機(jī)的主體由一個計算機(jī)的研究工作均取得了驚人的發(fā)展.目前不僅可變溫度的聚丙烯酰胺凝膠電泳構(gòu)成.另外,本研究基于DNA分子,而且基于生物酶、生物操作等,已還給出了計算機(jī)中存儲庫的具體構(gòu)造方法.這里的經(jīng)提出了不少的DNA計算模型.在已有的DNA計算存儲庫主要由兩個部分構(gòu)成:一

3、個是構(gòu)成所有可能[2]模型中,有些是理論上的模型,如Lipton建立的求著色的所謂的圖的著色方案的DNA序列鏈,簡稱為庫[3]解可滿足性問題的DNA計算模型及Roweis等人鏈;另一個是給出圖結(jié)構(gòu)信息的所謂的探針庫鏈.在本提出的粘貼DNA計算模型等.有些則通過巧妙地利研究中,我們特別指出了編碼的方法步驟,并對20個用生物操作技術(shù)建立的DNA計算模型,如Adleman頂點的一個圖給出了具體的編碼.最后,成功地對5個[4]研究組在2002年建立的求具有20個變量的3-SAT頂點的圖給出了系統(tǒng)地生物操作與生化實驗驗證.問題的DNA計算模型,

4、就是充分利用凝膠電泳和溫本研究中的圖用G表示,均指簡單無向圖.用控方法建立起來的,是目前利用非電子工具解決的V(G)及E(G)表示圖G的頂點集和邊集.圖G的一個規(guī)模最大的一個NP-完全問題.在那些基于生物實驗k-正常頂點著色,簡稱為圖的k-頂點著色,是指用k[5]的模型中,備受關(guān)注的有Sakamoto等人巧妙地利種顏色對圖G的每個頂點的一種分配,使得相鄰的用DNA發(fā)夾構(gòu)形給出的求解SAT問題的模型;頂點分配(或稱為“著”)到不同的顏色.由于本研究僅[6]Ouyang等人利用POA技術(shù)合成DNA分子來設(shè)計考慮圖的3-著色問題,故我們總是

5、假定顏色集為{r,b,DNA計算中所需要的所有數(shù)據(jù)庫,給出的求解圖的y},其中r表示紅色,b表示藍(lán)色,y表示黃色.所以,[7]最大團(tuán)問題的DNA計算模型;Liu等人給出的表面求解圖的3-著色問題可以認(rèn)為是尋找從圖的頂點集DNA計算的SAT問題的模型以及Weizman研究小V(G)到顏色集{r,b,y}的一種映射:[8,9]組給出的利用DNA計算進(jìn)行疾病診斷與治療相結(jié)f:V(G)→{r,b,y},合的DNA計算機(jī)模型和邏輯分析DNA計算模型等.使得對于?uv∈E(G),f(u)≠f(v).圖的3-著色問眾所周知,圖的著色問題是一個困難的

6、組合優(yōu)[23]題是一個NP-完全問題.化問題,具有良好的應(yīng)用背景,如工序問題、排課表容易推理,本研究結(jié)果同樣適用于k≥4的情況.[10~12]問題以及存儲問題等均有直接的應(yīng)用.然而,圖1基本結(jié)構(gòu)與基本原理著色問題是一個困難的NP-完全問題.目前,已經(jīng)有不少的算法用于研究圖的著色問題,如常規(guī)的算(ⅰ)基本結(jié)構(gòu).設(shè)計的“圖頂點著色DNA計算法[13~15]、人工神經(jīng)網(wǎng)絡(luò)算法[16,17]、遺傳算法[18]以及機(jī)模型”的基本結(jié)構(gòu)由硬件和軟件兩個部分構(gòu)成，其模擬退火算法[19]等.近年來,我們已經(jīng)提出了幾個基中的硬件主體是聚丙烯酰胺凝膠電泳,

7、該凝膠電泳于DNA計算的圖的著色問題的理論計算模型[20~22].由3個區(qū)構(gòu)成:本文所提出的這個新的圖頂點著色DNA計算機(jī)模型,(1)變性區(qū).將來自于存儲庫中的雙鏈DNA分也正是在上述研究工作所積累上提出來的.子經(jīng)過變性后變成單鏈,其中的一條單鏈被固定,而480www.scichina.com論文第51卷第4期2006年2月另一條單鏈沒有固定,可隨電泳進(jìn)行移動.固定n,且圖總是簡單無向有限圖.本研究假定對圖的頂DNA分子的方法可采用磁珠技術(shù),或者所謂的點著色是3-著色.當(dāng)然,對于k-著色問題,k≥4,其TMTMAcrydite方法等,

8、有關(guān)Acrydite方法的理論以及原理是相同的.1)較為詳細(xì)的討論參見文獻(xiàn).把存儲庫中代表頂點著色方案的所有雙鏈DNA序列置于一個板上,稱為A板.(2)非解粘貼區(qū),或簡稱為“非解區(qū)”.存放一個B板,稱為探針板.探針板上均