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