資源描述：
《基于粘貼模型的圖頂點(diǎn)著色問(wèn)題的dna算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、維普資訊http://www.cqvip.com第26卷第l2期計(jì)算機(jī)應(yīng)用Vo1．26No．122006年l2月ComputerApplicationsDee．2006文章編號(hào)：1001—9081(2006)12—299803基于粘貼模型的圖頂點(diǎn)著色問(wèn)題的DNA算法馬季蘭，楊玉星(太原理工大學(xué)計(jì)算機(jī)與軟件學(xué)院，山西太原030024)(jade—star@163．CO1TI)摘要：為了用生化實(shí)驗(yàn)的方法解決圖的頂點(diǎn)著色問(wèn)題，基于粘貼模型的巨大并行性，將著色問(wèn)題轉(zhuǎn)化為可滿足性問(wèn)題，提出一個(gè)基于粘貼模型的DNA算法。通過(guò)一個(gè)實(shí)例給出了操作步驟
2、，并對(duì)生化反應(yīng)過(guò)程進(jìn)行了模擬，得出具體的著色方案，證明了該算法的可行性。關(guān)鍵詞：DNA計(jì)算；粘貼模型；NP完全問(wèn)題；圖頂點(diǎn)著色中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)識(shí)碼：ADNAalgorithmofgraphvertexcoloringproblembasedonstickermodelMaJi．1anYangYuxing(CollegeofComputerandSoftware，TaiylmnUniversityofTechnology，Taly~,anShar~i030024，China)Abstract：Inordertosolve
3、thegraphve~ex—coloringproblem，aDNAalgorithmbasedonstickermodelwasproposed，whichconve~edthecoloringproblemtosatisfiabilityproblemonthebasisofthevastparallelism．TheoperationstepswereVenthroughaninstance+AndasimulationexperimentWaScarriedouttoillustratethebiochemicalproced
4、ures．Thefinalcoloringschemesweregot．Consequently，thefeasibilityofthealgorithmisproved．Keywords：DNAcomputing；stickermodel；NP··completeproblem；vertex--coloringofgraph存儲(chǔ)合成物中的某一個(gè)位元為單鏈時(shí)表示O，為雙鏈時(shí)表示0引言1。如圖1所示是子鏈數(shù)為4，子鏈長(zhǎng)度為5個(gè)堿基的位串。由于解決NP(Non-deterministicPolynomial，非確定多項(xiàng)式復(fù)雜程度)完全問(wèn)題
5、的精確算法的時(shí)間復(fù)雜度隨著問(wèn)題的規(guī)模成指數(shù)級(jí)增長(zhǎng)，因此，傳統(tǒng)計(jì)算機(jī)對(duì)這一類問(wèn)題顯得力不從心。隨著DNA計(jì)算與DNA計(jì)算機(jī)研究的展開(kāi)，一些NP完全圖1一個(gè)位串實(shí)例問(wèn)題、NP難問(wèn)題的計(jì)算模型被相繼提出J。圖1中的位串對(duì)應(yīng)的二進(jìn)制串是：0110。計(jì)算模型的研究一直是DNA計(jì)算領(lǐng)域的研究熱點(diǎn)之一，粘貼模型在位串上定義了四種基本操作：至今已有不少的計(jì)算模型被提出，其中，近幾年的研究熱門是合并：定義存儲(chǔ)合成物的集合。與的合并為，其中，剪接模型和粘貼模型]。其中，粘貼模型是文獻(xiàn)[5]首次提T=T。u。出的DNA計(jì)算模型，粘貼模型有著與剪接模型同樣的
6、計(jì)算能分離：根據(jù)存儲(chǔ)合成物中第i個(gè)位元的狀態(tài)(即單、雙鏈)力，而且具有不需要延伸DNA鏈、不需要酶的參與以及材料將存儲(chǔ)合成物的集合分解為兩個(gè)集合：+(T，i)和一(T，i)，可以重復(fù)利用等優(yōu)點(diǎn)。目前，研究者們基于粘貼模型已經(jīng)解其中+(T，i)為該位元為“1”的位串的集合，一(，f)為該位決了不少NP類問(wèn)題。例如：3-SAT問(wèn)題(3-satisfiability，3可元為?0’的位串的集合。滿足性問(wèn)題)J、旅行商問(wèn)題(TravelingSalesmanProblem，設(shè)置：對(duì)存儲(chǔ)合成物的集合中的所有位串的某～特定TsP)?、k一團(tuán)與k一
7、獨(dú)立集問(wèn)題等。文獻(xiàn)[9]根據(jù)顏色將位置i的位元，Set(T，i)的含義是：若其狀態(tài)為“0”，將其狀態(tài)頂點(diǎn)編碼成k個(gè)長(zhǎng)度不同的單鏈DNA，給出了求圖的頂點(diǎn)設(shè)置為“1”。k一著色問(wèn)題的一種DNA算法；文獻(xiàn)[10]中提出了一種圖的清除：對(duì)存儲(chǔ)合成物的集合中的所有位串的某～特定頂點(diǎn)著色問(wèn)題的粘貼算法，其主要思想是將著色問(wèn)題分解成位置i的位元，Clear(T，i)的含義是：若其狀態(tài)為?1’，將其狀頂點(diǎn)獨(dú)立集問(wèn)題和頂點(diǎn)劃分問(wèn)題進(jìn)行解決；本文是將圖的頂態(tài)設(shè)置為“0”。點(diǎn)著色問(wèn)題轉(zhuǎn)化為SAT問(wèn)題進(jìn)行解決。基于粘貼模型的計(jì)算模式就是將問(wèn)題的所有可能解用
8、位1粘貼模型串來(lái)編碼，得到一個(gè)“數(shù)據(jù)池”，對(duì)該數(shù)據(jù)池中的位串通過(guò)上在粘貼模型中用單、雙鏈DNA分子進(jìn)行編碼，分別對(duì)應(yīng)述操作的某一種或者幾種操作的排列組合，篩選出結(jié)果串，如于傳統(tǒng)計(jì)算機(jī)的0和1。在粘貼模型的存儲(chǔ)區(qū)中，放置著
