資源描述：
《試論基于dna計(jì)算的求解背包問題的方法研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、武漢科技大學(xué)碩士學(xué)位論文基于DNA計(jì)算的求解背包問題的方法研究姓名：劉毅申請學(xué)位級別：碩士專業(yè)：控制理論與控制工程指導(dǎo)教師：宋玉階20070520武漢科技大學(xué)碩士學(xué)位論文第1頁摘要近年來，隨著生物技術(shù)的飛速發(fā)展，一個新的研究領(lǐng)域一DNA計(jì)算隨之產(chǎn)生。其標(biāo)志為Adleman于1994年在Science上發(fā)表的文章“MolecularComputationofSolutionstoCombinatorialProblems”。由于DNA計(jì)算機(jī)所具有的巨大并行性、海量存儲以及低能耗等優(yōu)點(diǎn)，因此將有望在某些領(lǐng)域彌補(bǔ)現(xiàn)有電子計(jì)算機(jī)的不足。本文介紹了DNA計(jì)算的原理和生
2、物基礎(chǔ)，分析了DNA計(jì)算在組合優(yōu)化中的典型應(yīng)用，在此基礎(chǔ)上重點(diǎn)研究了基于DNA計(jì)算的求解背包問題的方法，提出了多維背包問題(MDKP)并11收縮背包問題(CKV)ff勺DNA計(jì)算模型。首先，針對多維背包問題提出了兩種計(jì)算模型，第一種是兩階段計(jì)算模型，依據(jù)該模型建立的算法分為試管階段和表面階段兩個階段；第二種是表面計(jì)算模型，在分解處理約束方程組后利用表面方式結(jié)合熒光標(biāo)記的有關(guān)技術(shù)求解。然后，針對收縮背包問題提出了一種計(jì)算模型，在該模型中，先將問題的約束條件進(jìn)行分解，再通過鏈接反應(yīng)、凝膠電泳、探針檢測和放射自顯影技術(shù)來求解。本文對提出的每個求解背包問題的DNA計(jì)
3、算模型的具體實(shí)現(xiàn)過程都用實(shí)例進(jìn)行了詳細(xì)說明，并分析了每個計(jì)算模型中采用的生物技術(shù)，指出了其在算法執(zhí)行過程中的優(yōu)勢與局限。關(guān)鍵詞：DNA計(jì)算，組合優(yōu)化，多維背包問題，收縮背包問題第1I頁武漢科技大學(xué)碩士學(xué)位論文AbstractWiththerapiddevelopmentofbiologicaltechniques，anewdiscipline-DNAcomputing-hascomeintobeing．In1994，Adlemanpresentedhisseminalpaper”MolecularComputationofSolutionstoCombina
4、torialProblems”inScience．Themassiveparallelism，hi曲-densitystorageandenergyefficiencyofDNAcomputingmayoffsetthedisadvantagesofelectroniccomputers．Inthispaper,theprincipleandbiologicalfoundationofDNAcomputingisintroduced，andtheapplicationofDNAcomputingincombinationandoptimizationisan
5、alyzed．Then，wepresenttheDNAcomputingmodelsofmulti—dimensionalknapsackproblemsandcollapsingknapsackproblems．Forthemulti—dimensionalknapsackproblem，weproposetwokindsofcomputingmodels，thefirstkindisatwo—phasemodel，andthesecondkindisasurface—basedmodel．Inthetwo-phasemodel，thealgorithmi
6、sperformedintwophases—thetubephaseandthesurfacephase．Inthesurface—basedmodel，thesolutionsaregainedbyutilizingthetechniquesoffluorescencelabelingafterdisassemblingtheconstraintequationgroup．Forthecollapsingknapsackproblem，weproposeakindofcomputingmodel．Inthismodel，wefirstlypartition
7、theconstraintofthecollapsingknapsackproblemintoseveraldifferentconstraints，andthenweperformaseriesofbiochemicaltechnologies(1igature，gelelectrophoresis，DNAprobeandautomdiography)toobtainthesolutions．Weillustratetheconcreteimplementingprocessesofeachmodelbysomecaseanalyses．Furthermo
8、re，weanalyzeofbiochemicalt
