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