试论基于dna计算的求解背包问题的方法研究

《试论基于dna计算的求解背包问题的方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉科技大学硕士学位论文基于DNA计算的求解背包问题的方法研究姓名：刘毅申请学位级别：硕士专业：控制理论与控制工程指导教师：宋玉阶20070520武汉科技大学硕士学位论文第1页摘要近年来，随着生物技术的飞速发展，一个新的研究领域一DNA计算随之产生。其标志为Adleman于1994年在Science上发表的文章“MolecularComputationofSolutionstoCombinatorialProblems”。由于DNA计算机所具有的巨大并行性、海量存储以及低能耗等优点，因此将有望在某些领域弥补现有电子计算机的不足。本文介绍了DNA计算的原理和生

2、物基础，分析了DNA计算在组合优化中的典型应用，在此基础上重点研究了基于DNA计算的求解背包问题的方法，提出了多维背包问题(MDKP)并11收缩背包问题(CKV)ff勺DNA计算模型。首先，针对多维背包问题提出了两种计算模型，第一种是两阶段计算模型，依据该模型建立的算法分为试管阶段和表面阶段两个阶段；第二种是表面计算模型，在分解处理约束方程组后利用表面方式结合荧光标记的有关技术求解。然后，针对收缩背包问题提出了一种计算模型，在该模型中，先将问题的约束条件进行分解，再通过链接反应、凝胶电泳、探针检测和放射自显影技术来求解。本文对提出的每个求解背包问题的DNA计

3、算模型的具体实现过程都用实例进行了详细说明，并分析了每个计算模型中采用的生物技术，指出了其在算法执行过程中的优势与局限。关键词：DNA计算，组合优化，多维背包问题，收缩背包问题第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