试论dna计算及其算法优化

《试论dna计算及其算法优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、太原理工大学硕士学位论文DNA计算及其算法优化姓名：王斌田申请学位级别：硕士专业：计算机应用技术指导教师：余雪丽;欧阳钟灿20060501太原理工大学硕士研究生学位论文DNA计算及其算法优化摘要在计算机中，利用有机分子的信息处理能力来代替数字开关部件，这就是DNA计算的基本思想。以当前的计算机技术要实现微型化存在明显的局限性，所以要进行大的革新，很早以前就有人提出现代计算机的基本部件应逐步过渡到分子水平，这样一来，它将会比我们利用当前技术制造出的任何东西都要小得多，量子计算和DNA计算是当前这种思想的两种不同表现，本论文主要介

2、绍DNA计算。DNA计算主要基于以下两点：(1)DNA链的巨大并行性；(2)Watson—Crick的互补结构。传统理论上的计算机科学植根于重复写操作，这对于大部分自动机械装置和语言理论模型是正确的，然而，在计算行为中，自然界操作DNA分子利用的是完全不同的操作类型：剪切、粘贴、连接、插入、删除等。可以证明，利用这些操作可以建立计算模型，并且在功能上等价于图灵机。以前DNA计算的研究主要集中在一些组合问题上，像Hamiltonian路径问题、旅行商问题、3-SAT问题，甚至破解DES密码等等，但提出的上述所有问题的DNA算法基

3、本上都是蛮力搜索，初始化时生成问题的所有可能的解决方案，然后根据条件消除掉不正确的答案，最后剩下的方案即是问题的正确答案。但值得注意的是，实际问题的正确答案也许会在计算过程中被破坏掉，最后得到的答案也许是一个错误的答案。为了避免这种错误，我们提出了将启发式优化算法和DNA计算结合，采用新的手段来设计算法。在这篇论文中，我们将蚁群优化算法和DNA计算结合，来解决旅行商问题。即使正确的答案在处理的过程中被破坏掉，该正确答案在以后的处理过程总还会被构造，在过滤掉不合适的答案以后，我们利用控制变性I太原理工大学硕士研究生学位论文温度的

4、方法按比例放大经过过滤剩下的序列，并把放大的结果作为下次迭代的输入，相应的代表正确答案的DNA序列的浓度就会增加。在经过多次迭代之后，若结果趋于稳定，则认为剩下的序列即为问题的答案。论文的前两部分主要介绍生物学的基础知识、DNA计算的基本概念、基本模型和相关的著名实验，接下来介绍了启发式优化算法：蚁群优化算法；然后提出蚁群优化算法和DNA计算结合的构想与具体实现，同时详细介绍了算法处理过程；在文章的最后对提出的算法进行了总结，并对DNA计算的前景进行了展望。关键词：DNA计算，启发式优化方法，NP完全问题，序列抽取II太原理工

5、大学硕士研究生学位论文DNACOM口UTINGANDOPTI~ⅡZATIONOFTHEALGORITHMABSTRACTInformation-processingcapabilitiesoforganicmoleculescallbeusedincomputerstoreplacedigitalswitches；thisisthebasicideainDNAcomputing．Thereareobviouslimitstominiaturizationwithcurrentcomputertechnologies．Forad

6、rasticinnovation，itwassuggestedalreadyalongtimeagothatthebasiccomponentsshouldgotothemolecularlevel．Theresultwouldbemuchsmallerthananythingwecanmakewithpresenttechnology．QuantumcomputingandDNAcomputingaretworecentmanifestationsofthissuggestion．Thisworkis*boutthelatt

7、er．DNAcomputingarebasedontwofundamentalfeatures：(1)ThemassiveparallelismofDNAstrands；(2)Watson-Crickcomplementarity．Classictheoreticalcomputerscienceisgroundedonrewritingoperations；thisistmeformostautomataandlanguagetheorymodels．Asweshallsee，naturemanipulatestheDNAm

8、oleculesinacomputingmannerbyusingoperationsofaquitedifferenttype：cutandpaste，adjoining，insertion，deletion，etc．Ithasbeenprovedthatbyusingsu