資源描述：
《試論基于dna計算的求解背包問題的方法研究》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、武漢科技大學碩士學位論文基于DNA計算的求解背包問題的方法研究姓名：劉毅申請學位級別：碩士專業(yè)：控制理論與控制工程指導教師：宋玉階20070520武漢科技大學碩士學位論文第1頁摘要近年來，隨著生物技術的飛速發(fā)展，一個新的研究領域一DNA計算隨之產生。其標志為Adleman于1994年在Science上發(fā)表的文章“MolecularComputationofSolutionstoCombinatorialProblems”。由于DNA計算機所具有的巨大并行性、海量存儲以及低能耗等優(yōu)點，因此將有望在某些領域彌補現(xiàn)有電子計算機的不足。本文介紹了DNA計算的原理和生
2、物基礎，分析了DNA計算在組合優(yōu)化中的典型應用，在此基礎上重點研究了基于DNA計算的求解背包問題的方法，提出了多維背包問題(MDKP)并11收縮背包問題(CKV)ff勺DNA計算模型。首先，針對多維背包問題提出了兩種計算模型，第一種是兩階段計算模型，依據(jù)該模型建立的算法分為試管階段和表面階段兩個階段；第二種是表面計算模型，在分解處理約束方程組后利用表面方式結合熒光標記的有關技術求解。然后，針對收縮背包問題提出了一種計算模型，在該模型中，先將問題的約束條件進行分解，再通過鏈接反應、凝膠電泳、探針檢測和放射自顯影技術來求解。本文對提出的每個求解背包問題的DNA計
3、算模型的具體實現(xiàn)過程都用實例進行了詳細說明，并分析了每個計算模型中采用的生物技術，指出了其在算法執(zhí)行過程中的優(yōu)勢與局限。關鍵詞：DNA計算，組合優(yōu)化，多維背包問題，收縮背包問題第1I頁武漢科技大學碩士學位論文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
