DNA计算在两类困难问题上的研究

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

1、中图分类号：Q2窆学科分类号：一jlQ：墨2论文编号：密级：公珏安徽理工大学硕士学位论文DNA计算在两类困难问题上的研究作者姓名：奎废夔专业名称：座题数堂。研究方向：垡丝理途墨廑旦导师姓名：迕查荭教援魃蠢登熬援导师单位：塞徽堡王太堂理堂睦答辩委员会主席：塞±信熬握论文答辩日期：2013年6月1日安徽理工大学研究生处2013年6月7日ADissertationinAppliedMathematicsDNAcomputingresearchontwokindsofdifficultproblemsCandidate：

2、LiQingyanSupervisor：XuZhicaiYinZhixiangSch001ofSicienceAnHuiUniversityofScienceandTechnologyNo．168，ShungengRoad，Huainan，232001，P．R．CHINA独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得塞徽理王盍堂或其他教育机构的学位或证书而使用过的材料。

3、与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：二奎立敛日期：2盟年』月早日学位论文版权使用授权书本学位论文作者完全了解塞徼堡王太堂有保留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于塞徵理王太堂。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权安徽理工大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书

4、)学位论文作者签名：专庆板签字日期：加，；年6月了日锄张歹倒鳓舭噼∞日摘要摘要DNA计算是以编码携带遗传信息的DNA序列和与之有关的+些生物酶等为最基本物质，运用生物操作来实现并行信息处理的一种新型的分子水平上的生物计算方式。1994年，Adleman首先提出DNA计算的方法来解决NP一完全问题，对NP一完全问题的计算提供了一种新方法。此后学者们不断地研究利用DNA分子或者是其它生物分子来进行计算过程，并取得了令人瞩目的成果。DNA计算的主要思想是：利用DNA分子特有的双螺旋结构及碱基互补配对性质，把需要解决的问

5、题编码并映射成相应的DNA链，通过生物酶的参与形成数据池，然后按照一系列的实验步骤把待解决问题的原始数据经过运算高度并行地映射成DNA分子链的可控制的生化过程，再利用现代分子生物技术检测所需要的运算结果。本文从DNA计算的基础理论问题出发，研究了DNA计算模型及其在解决两类困难问题上的应用。详细研究内容的安排如下：本文讨论了文中用到的质粒DNA计算模型和闭环DNA计算模型。质粒DNA计算模型是一种以闭环状质粒作为基础的DNA计算模型，在该模型中被用到的质粒具有一段特殊的DNA插入序列，全部的片断确定在对应的限制性

6、内切位点，运用剪切及粘贴的生物操作执行计算过程。闭环DNA计算模型与质粒DNA计算模型有许多异同点，闭环DNA计算模型具有更大的研究价值和更广的应用范围。基于质粒DNA计算模型，给出了求解图的最小顶点覆盖问题的DNA算法。该算法通过合适的编码以及基本的生物操作完成解的生成及最终解的分离。基于闭环DNA计算模型和其主要的生物化学实验，介绍了求解最大加权独立集问题的闭环DNA算法。该算法首先通过适当的编码以及多次删除实验获得所有独立集，再用其它实验手段得到图的最大加权独立集。图[16]表[O】参[55】关键词：DNA

7、计算；质粒模型；闭环模型；最小顶点覆盖问题；最大加权独立集分类号：110．87AbstractDNAcomputingisanewkindofbiologicalcomputingmethodatthemolecularlevel，whichisDNAsequencecarriedthegeneticinformationandsomeenzymesforthemostbasicmaterial，usesthebiologicalactionstoimplementinformationprocessing．In

8、1994，AdlemanfirstproposedDNAcomputingmethodtosolvetheNPcompleteproblems，whichhadprovidedSanewmethodtosolvetheNP。completeproblem．Eversincethen，thescholarshaveconstantlystudiedusingDNAmolec