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