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