基于IC的DNA计算算法的仿真与实现

《基于IC的DNA计算算法的仿真与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京邮电大学硕士学位论文基于IC的DNA计算算法的仿真与实现姓名：汤立伟申请学位级别：硕士专业：计算机科学与技术指导教师：余文20070301摘要1994年，Adleman用操纵DNA分子的办法解决了一个经典的NP完全问题～哈密顿路径问题(一个包含7个顶点实例)。自此以后，生物计算作为生物与计算机科学的交叉学科迅速地发展起来。虽然DNA计算(分子计算)具有运算高度并行，DNA作为载体信息贮存量大，能量消耗低，DNA分"子资源丰富等优点，但是从目前分子计算发展来看，分子计算实现主要是溶液方式和表面方式，这两种实现

2、方式目前显示出很多缺点：计算错误率高，单步执行慢，编码复杂，很难实现自动化。为了克服上述缺点，我们设计一种利用现有的IC技术解决DNA计算的新的实现方式。本文主要研究内容如下：1．系统地对DNAi,J-算方法、原理、主要实现方式和优缺点等方面进行了探讨和总结，学习了FPGA和单片机的原理和软硬件开发环境，提出了一种基于大规模集成电路设计的DNA计算实现方式。2．结合传统计算机和DNA计算的并行性，本文设计了一种基于DNA计算的计算机结构模型。传统的计算机在解决串行工作任务的时候，其能力是无懈可击的，DNA计算相

3、对于传统的计算机也有自己独特的优势，它能够同时搜索获得所有的结论。3．根据分子计算原理设计了一种具有可扩展性的解决SAT问题的算法，并用4个变量和6个变量的问题对算法的正确性进行了验证。并使用单片机作为控制器，FPGA]：设计实现电路解决了上述问题。受限于目前实验条件，虽然理论上可以解决任意多个变量的问题，但是目前仅能解决11个变量也就是2048个分子处理单元的问题。4．研究分析了0—1规划问题的模型，并根据该问题的原理，提出了一种基于DNA计算的算法，并在所设计的机器模型上对该算法的正确性进行了验证，结果表明

4、算法是正确的。5．分析了均分问题的计算模型原理，在原有模型基础上对7个变量的均分问题进行了仿真，验证了算法的正确性。6．最大集团问题是图论中一个重要问题，本文尝试了一个五个变量的最大集团问题，算法实现上目前只适合变量个数较少的问题，实现起来步骤虽然有所减少但是实现复杂度仍旧较大，本问题旨在探求一种用Ic电路实现的满足进化算法和分子计算问题的实现电路。关键词：DNA计算SAT问题FPGA均分问题最大集团问题线性非线性规划问题ABSTRACT1994．AdlemanresolveaclassicNP．complet

5、eproblemcalledHamiltoniaupathproblem(include7vertex)．Sincethen，theDNAcomputingtermsasthejunctionofbiotechnologyandcomputersciencegetrapiddevelopment．AlthoughtherearesomeadvantagesofDNAcomputing，suchashiglllyparallelismcompute，highcomputationalspeed，bigstorag

6、ecapacity,low-energyconsumptionandabundantinnaturalresourcesetc．，therealizationofDNAcomputingiSmainlybaseonthechemicalmethodwhichhavehigherrorrate．WiththedevelopmentofcurrentVLSItechnology,thespeedofICincreasingandthepricesofstorageequipmentbecomelowerandlow

7、er．Takingtheaboveintoaccount，wedecidetouseICtorealizeDNAcomputing．Thispapermainlydiscussesfollows：1．Discussandsummarizethemethod，theprinciple，themainrealizemethod，theadvantagesanddisadvantagesofDNAcomputing．LearnetheprinciplesoftheMCUandFPGA'ssoftwaredevelop

8、mentenvironmentandproposeamethodofusingICtorealizeDNAcomputing．2．Traditionalcomputerisgoodatsolveserialtask．DNAcomputingisbetterthantraditionalcomputerinsomepoints，itCallsearchandgetalltheanswer