資源描述：
《基于自組裝納米顆粒探針的最小頂點(diǎn)覆蓋問(wèn)題的dna計(jì)算模型》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、基于自組裝納米顆粒探針的最小頂點(diǎn)覆蓋問(wèn)題的DNA計(jì)算模型麵艷殿志禪趙鑫月安徽理工大學(xué)數(shù)學(xué)與大勤DNA自組裝技術(shù)為DNA計(jì)算的發(fā)展帶來(lái)丫一些新的啟發(fā)。目前，解決各種NP完全問(wèn)題的方法有多種多樣的計(jì)算模型，其中有些是非常有用的，可以解決復(fù)雜的NP完全問(wèn)題。在本文中，在自組裝納米顆粒探針的基礎(chǔ)上，介紹了關(guān)于最小頂點(diǎn)覆蓋問(wèn)題的一種新的DNA計(jì)算模型。將給定問(wèn)題的變量0或1所有可能的組合，編碼在自組裝納米探針的識(shí)別區(qū)，通過(guò)靶序列的雜交來(lái)判斷其可行解。相對(duì)于傳統(tǒng)的DNA計(jì)算模型，該模型具有方便、靈敏、穩(wěn)定性高的優(yōu)點(diǎn)。
2、關(guān)鍵詞：DNA計(jì)算;自組裝;納米顆粒;最小頂點(diǎn)覆蓋問(wèn)題;基金：國(guó)家自然科學(xué)基金項(xiàng)目“基于分子信標(biāo)微流控芯片的大數(shù)據(jù)存儲(chǔ)與挖掘”(61702008):國(guó)家自然科學(xué)基金項(xiàng)目“DNA自組裝模型在生物傳感器設(shè)計(jì)中的研究與探索”(61672001)DNAComputingModelBasedonSelf-assembledNano-particleProbesSolvingtheMinimumVertexCoverageProblemGONGCheng-yanYINZhi-xiangZHAOXin-yueMathe
3、maXicsandBigDataInstitute，AnhuiUniversityofScienceandTechnology;Abstract：DNAself-assemblytechnologyhasbroughtsomenewinsightsintothedevelopmentofDNAcomputing.Atpresent,thereareavarietyofcomputationalmodelsforsolvingvariousNP—completeproblems,someofwhichare
4、veryusefulandcansolvecomplexNP-completeproblems.Inthispaper,anewDNAcomputingmodelwithminimalvertexcoverageproblemisintroducedonthebasisofself-assemblednano-particleprobes.Allthepossiblecombinationsofvariables0or1ofthegivenproblemareencodedintherecognition
5、regionoftheself-assemblednano-particleprobes,andthefeasiblesolutionisjudgedbythehybridizationofthetargetsequence.ComparedwiththetraditionalDNAcalculationmodel,themodelisconvenient,sensitiveandstable.Keyword：DNAcomputing;self-assembled;nano-particle;minimu
6、mvertexcoverageproblem;自從Adieman在哈密爾頓路徑問(wèn)題上的開創(chuàng)性I:作以來(lái)，基丁?DNA的計(jì)算領(lǐng)域已經(jīng)有了許多研宄成果。采用DNA計(jì)算方法可用來(lái)解決許多組合優(yōu)化問(wèn)題，比如可滿足問(wèn)題m、最大團(tuán)問(wèn)題m、最大獨(dú)立集問(wèn)題m等。最小頂點(diǎn)覆蓋（MVC）問(wèn)題出現(xiàn)在各種重要成用中，包括計(jì)算生物化學(xué)中的多個(gè)序列比對(duì)、信息檢索和調(diào)度問(wèn)題等，探索一種更有效的解決最小頂點(diǎn)覆蓋問(wèn)題的方法有實(shí)際意義。2004年，高林、許進(jìn)給出了解決最小頂點(diǎn)覆蓋問(wèn)題的DNA分子算法位1;2006年，周康、許進(jìn)給出了解決最小
7、頂點(diǎn)覆蓋問(wèn)題的閉環(huán)DNA算法￡61；同年，X.Xu和J.Maxw給出了解決最小頂點(diǎn)覆蓋問(wèn)題的模擬退火算法121;2008年，寧愛兵等給出了解決最小頂點(diǎn)覆蓋問(wèn)題的快速降解算法M;2010年，金婷婷等給出丫解決最小頂點(diǎn)覆蓋問(wèn)題的競(jìng)爭(zhēng)決策算法M;2011年，ZhangX等用三維自組裝模型解決最小頂點(diǎn)覆蓋問(wèn)題等0虹?；谝陨涎绣潮尘?，F(xiàn)eiLi等在自組裝納米顆粒探針的基礎(chǔ)上提出了解決0-1規(guī)劃問(wèn)題和SAT問(wèn)題的新的DNA計(jì)算模型［11-12］，也是第一次將納米顆粒與寡聚核卄酸結(jié)合到DNA計(jì)算模型中。本文在此DNA
8、計(jì)算模型基礎(chǔ)上探討最小頂點(diǎn)覆蓋問(wèn)題。1圖的最小頂點(diǎn)覆蓋問(wèn)題1.1圖的最小頂點(diǎn)覆蓋定義基本定義:給定一個(gè)簡(jiǎn)單無(wú)向圖G=（V，E），K是頂點(diǎn)集V的一個(gè)子集，并且每條邊都至少有一個(gè)頂點(diǎn)在K中，那么稱K是圖G的一個(gè)頂點(diǎn)覆蓋。如果G不存在覆蓋K’使得
9、K’
10、〈
11、K
12、，那么覆蓋K稱為G的最小頂點(diǎn)覆蓋。簡(jiǎn)而言之，圖的最小頂點(diǎn)覆蓋是指在給定的圖屮找到一個(gè)頂點(diǎn)最小集，使得其能覆蓋給定的圖的所有邊。對(duì)于任意一個(gè)有n個(gè)頂點(diǎn)、m條邊的無(wú)向圖G=（V,
