資源描述：
《基于DNA計(jì)算的NP問(wèn)題研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、摘要捅要DNA計(jì)算是一種模擬生物分子DNA的結(jié)構(gòu)并借助分子生物技術(shù)進(jìn)行計(jì)算的新方法，DNA計(jì)算主要分為兩步：第一步是生成問(wèn)題的所有可能解，第二步是解的檢測(cè)。它作為一門新興的交叉學(xué)科正逐漸發(fā)展起來(lái)，在解決大規(guī)模并行計(jì)算問(wèn)題上，特別是在解決NP一完全問(wèn)題上有其不可估量的優(yōu)勢(shì)。1994年，Adleman利用DNA計(jì)算解決了圖論中的哈密頓路徑問(wèn)題，并成功地進(jìn)行了實(shí)驗(yàn)。其目標(biāo)是產(chǎn)生以DNA計(jì)算模型為背景、具有海量的存儲(chǔ)遺傳密碼以及極快運(yùn)行速度的新一代計(jì)算機(jī)。DNA計(jì)算的基本思想是：利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對(duì)規(guī)律進(jìn)行信息編碼，把要運(yùn)算的對(duì)象映射成DNA分子鏈，在生物酶的作用下
2、，生成各種數(shù)據(jù)池(datap001)，然后按照特定的規(guī)則將原始問(wèn)題的數(shù)據(jù)運(yùn)算高度并行地映射成DNA分子鏈的可控的生化過(guò)程。最后，利用分子生物技術(shù)如聚合鏈反應(yīng)PCR、超聲波降解、親和層析、克隆、誘變、分子純化、電泳、磁珠分離等，檢測(cè)所需要的運(yùn)算結(jié)果。DNA計(jì)算的核心問(wèn)題是將經(jīng)過(guò)編碼后的DNA鏈作為輸入，在試管內(nèi)或其它載體上經(jīng)過(guò)一定時(shí)間完成可以控制的生物化學(xué)反應(yīng)，并以此來(lái)完成運(yùn)算，使得從反應(yīng)后的產(chǎn)物中能得到全部的解空間。在DNA計(jì)算系統(tǒng)中，DNA分子中的密碼作為存儲(chǔ)的數(shù)據(jù)，當(dāng)DNA分子間在某種酶的作用下瞬間完成某種生物化學(xué)反應(yīng)時(shí)，可以從一種基因代碼變?yōu)榱硪环N基因代碼。DNA計(jì)算實(shí)際
3、也就是通過(guò)對(duì)DNA雙螺旋進(jìn)行豐富的精確可控的化學(xué)反應(yīng)，包括標(biāo)記、擴(kuò)增或者破壞原有鏈來(lái)完成各種不同的運(yùn)算過(guò)程。本文從DNA計(jì)算所使用的DNA分子結(jié)構(gòu)角度，對(duì)目前DNA編碼問(wèn)題及其在解決NP一完全問(wèn)題方面的應(yīng)用進(jìn)行了介紹。對(duì)于TSP問(wèn)題，利用DNA序列表示權(quán)值大小、熔點(diǎn)溫度控制編碼、粘帖系統(tǒng)等三種方式實(shí)現(xiàn)算法：提出了一種基于可滿足解空間的最小頂點(diǎn)覆蓋問(wèn)題的DNA計(jì)算模型：在對(duì)騎士問(wèn)題處理中利用粘貼模型，它是應(yīng)用DNA鏈作為信息表示的物理基礎(chǔ)，它的計(jì)算是基于Watson-Crick的補(bǔ)碼變化規(guī)律。圖【34】表【4】參【79】關(guān)鍵詞：DNA計(jì)算，NP．完全問(wèn)題，DNA編碼，粘貼模型分類
4、號(hào)：TPl3摘要AbstractTheDNAcomputingisanewmethodthatsimulatesthestructureDNAofbiologymoleculeanddoesthecomputingbymoleculebiologicaltechnology．TheDNAcomputingmainlydividesintotwosteps：FirststepproducesallpossiblesolutionsofthequestionandnextstepdoesSolutionexamination．Itisanmerginginterdisciplina
5、rystudiesthatdevelopsgradually．Ithasinestimablesuperiorityinsolvinginthemassivelyparallelestimationproblem，speciallyinsolvinginaNPcompleteproblem．In1994，AdlemanhassolvedHmiltonwayprobleminthegraphtheoryusingtheDNAcomputation,andhasdonetheexperimentssuccessfully．Ttsgoalistoproduceanewgenerati
6、oncomputerwhichtakestheDNAcomputingmodelasthebackgroundandhasthemagnanimousmemorygeneticcodeandtheextremelyquickrunningrate．ThebasictheoryofDNAcomputingis：EncodeinformationusingthespecialstructureofDNAdoublehelixandnucleotidesmatchrule，andmappingtheobjecttooperatingtoDNAmoleculesstrands，andu
7、nderthecontrolofenzymebuildadatapool，thenusetherulesappointedmappingtheDNAmoleculesstrandstoahighspeedparalleldatacomputingbio-ehemistryprocedure．Atlast,usingmoleculebiologytechnologysuchaspolymerizationchainreaction(PCR)，ultrasonicdegradation,hybr
