基于DNA计算的NP问题研究

《基于DNA计算的NP问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要捅要DNA计算是一种模拟生物分子DNA的结构并借助分子生物技术进行计算的新方法，DNA计算主要分为两步：第一步是生成问题的所有可能解，第二步是解的检测。它作为一门新兴的交叉学科正逐渐发展起来，在解决大规模并行计算问题上，特别是在解决NP一完全问题上有其不可估量的优势。1994年，Adleman利用DNA计算解决了图论中的哈密顿路径问题，并成功地进行了实验。其目标是产生以DNA计算模型为背景、具有海量的存储遗传密码以及极快运行速度的新一代计算机。DNA计算的基本思想是：利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下

2、，生成各种数据池(datap001)，然后按照特定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后，利用分子生物技术如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等，检测所需要的运算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入，在试管内或其它载体上经过一定时间完成可以控制的生物化学反应，并以此来完成运算，使得从反应后的产物中能得到全部的解空间。在DNA计算系统中，DNA分子中的密码作为存储的数据，当DNA分子间在某种酶的作用下瞬间完成某种生物化学反应时，可以从一种基因代码变为另一种基因代码。DNA计算实际

3、也就是通过对DNA双螺旋进行丰富的精确可控的化学反应，包括标记、扩增或者破坏原有链来完成各种不同的运算过程。本文从DNA计算所使用的DNA分子结构角度，对目前DNA编码问题及其在解决NP一完全问题方面的应用进行了介绍。对于TSP问题，利用DNA序列表示权值大小、熔点温度控制编码、粘帖系统等三种方式实现算法：提出了一种基于可满足解空间的最小顶点覆盖问题的DNA计算模型：在对骑士问题处理中利用粘贴模型，它是应用DNA链作为信息表示的物理基础，它的计算是基于Watson-Crick的补码变化规律。图【34】表【4】参【79】关键词：DNA计算，NP．完全问题，DNA编码，粘贴模型分类

4、号：TPl3摘要AbstractTheDNAcomputingisanewmethodthatsimulatesthestructureDNAofbiologymoleculeanddoesthecomputingbymoleculebiologicaltechnology．TheDNAcomputingmainlydividesintotwosteps：FirststepproducesallpossiblesolutionsofthequestionandnextstepdoesSolutionexamination．Itisanmerginginterdisciplina

5、rystudiesthatdevelopsgradually．Ithasinestimablesuperiorityinsolvinginthemassivelyparallelestimationproblem，speciallyinsolvinginaNPcompleteproblem．In1994，AdlemanhassolvedHmiltonwayprobleminthegraphtheoryusingtheDNAcomputation,andhasdonetheexperimentssuccessfully．Ttsgoalistoproduceanewgenerati

6、oncomputerwhichtakestheDNAcomputingmodelasthebackgroundandhasthemagnanimousmemorygeneticcodeandtheextremelyquickrunningrate．ThebasictheoryofDNAcomputingis：EncodeinformationusingthespecialstructureofDNAdoublehelixandnucleotidesmatchrule，andmappingtheobjecttooperatingtoDNAmoleculesstrands，andu

7、nderthecontrolofenzymebuildadatapool，thenusetherulesappointedmappingtheDNAmoleculesstrandstoahighspeedparalleldatacomputingbio-ehemistryprocedure．Atlast,usingmoleculebiologytechnologysuchaspolymerizationchainreaction(PCR)，ultrasonicdegradation,hybr