欢迎来到天天文库
浏览记录
ID:35129520
大小:3.34 MB
页数:70页
时间:2019-03-19
《试论基于dna计算的np问题研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、安徽理工大学硕士学位论文基于DNA计算的NP问题研究姓名:鲍士军申请学位级别:硕士专业:控制理论与控制工程指导教师:殷志祥20090601摘要捅要DNA计算是一种模拟生物分子DNA的结构并借助分子生物技术进行计算的新方法,DNA计算主要分为两步:第一步是生成问题的所有可能解,第二步是解的检测。它作为一门新兴的交叉学科正逐渐发展起来,在解决大规模并行计算问题上,特别是在解决NP一完全问题上有其不可估量的优势。1994年,Adleman利用DNA计算解决了图论中的哈密顿路径问题,并成功地进行了实验。其目标是产生以DNA计算模型为
2、背景、具有海量的存储遗传密码以及极快运行速度的新一代计算机。DNA计算的基本思想是:利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码,把要运算的对象映射成DNA分子链,在生物酶的作用下,生成各种数据池(datap001),然后按照特定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后,利用分子生物技术如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等,检测所需要的运算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其它载体上经过一定时间完成
3、可以控制的生物化学反应,并以此来完成运算,使得从反应后的产物中能得到全部的解空间。在DNA计算系统中,DNA分子中的密码作为存储的数据,当DNA分子间在某种酶的作用下瞬间完成某种生物化学反应时,可以从一种基因代码变为另一种基因代码。DNA计算实际也就是通过对DNA双螺旋进行丰富的精确可控的化学反应,包括标记、扩增或者破坏原有链来完成各种不同的运算过程。本文从DNA计算所使用的DNA分子结构角度,对目前DNA编码问题及其在解决NP一完全问题方面的应用进行了介绍。对于TSP问题,利用DNA序列表示权值大小、熔点温度控制编码、粘帖
4、系统等三种方式实现算法:提出了一种基于可满足解空间的最小顶点覆盖问题的DNA计算模型:在对骑士问题处理中利用粘贴模型,它是应用DNA链作为信息表示的物理基础,它的计算是基于Watson-Crick的补码变化规律。图【34】表【4】参【79】关键词: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
此文档下载收益归作者所有