【作者】 王宾；

【导师】 张强； 魏小鹏；

【作者基本信息】 大连大学 ， 计算机应用技术， 2009， 硕士

【摘要】 近年来,DNA计算是计算机研究领域的一个研究热点,在分子生物计算机的研究中倍受学者们的关注。1994年Adleman博士在Science上发表了一篇名为“Molecular Computation of Solution to Combinatorial Problems”的论文标志着DNA计算的诞生。DNA分子具有高度的并行性,并且作为信息的载体其储存的容量也非常大,同时DNA分子的资源也非常的丰富,这些也就是DNA计算所具备的优点。随着生物技术的不断发展,DNA计算将会被用来解决越来越多、越来越复杂的实际问题,特别是一些NP问题,最终将会产生一种全新的DNA计算机,它将会给数学、计算机科学等学科带来飞速地发展。DNA计算中最主要的是DNA分子间的杂交反应,其效率和精度直接影响到DNA计算的结果,因此好的序列编码方法对于提高DNA计算的可靠性和有效性具有十分重要的意义。目前DNA编码研究主要分为两个主要方向:一个是DNA序列编码的质量优化;另一个是DNA序列编码的集合设计。本文针对这两个方向做了较深入地研究,并着重对DNA序列编码的集合进行研究。DNA序列编码的质量优化研究的主要内容是依据问题的规模来找出满足确定约束条件的一定数量的DNA序列。所采用的约束条件通常是汉明距离约束和热力学约束,主要研究方法包括理论上的构造和计算机搜索两种主要方法。目前DNA编码的质量方面的研究已比较成熟,并已开发出比较好的软件成品。本文中将利用改进的遗传算法对DNA序列进行质量优化,该优化方法得到的DNA序列不仅满足DNA序列的约束条件,而且与前人研究成果相比有了显著地提高。DNA序列集合设计研究的主要内容是已知序列的长度及其约束条件,找到满足条件的所有的DNA序列的集合的最大值。目前最常用的约束条件是汉明距离约束下的约束条件,热力学约束条件以及他们的组合约束。主要研究方法分为理论研究和算法研究。结合上述约束条件,本文基于DNA序列集合研究的特点,对遗传算法进行更进一步地改进,将其运用于对DNA序列集合进行研究,不仅算法性能上有了显著地提高,而且得到的结果也比前人的成果有了很大地提高。更多还原

【Abstract】 DNA computing is a new method that uses biological molecule DNA as computing medium and biochemical reaction as computing tools. In 1994, Dr Adleman released“Molecular Computation of Solutions to Combinatorial Problems”in Science, which indicates DNA computing comes into being. The DNA molecule has a high parallelism, and a great of storage capacity as a carrier of information. There are the merits of DNA computing. At the same time, the resource of DNA molecule is very rich. Along with the development of biologic technology, the DNA computing will solve more and more complex problems, especially NP problems. Finally, it will product a new DNA computer which could bring the flying development of Mathematics, Computer Science and other subjects.In DNA computing, the core reaction is the specific hybridization between DNA sequences or the Watson-Crick complement, and which directly influences the reliability of DNA computation with its efficiency and accuracy. The efficiency and accuracy is influenced by DNA sequences, so how to product good DNA sequences is very important for improving the efficiency and reliability of DNA computing. At present, these are two researchful aspects about DNA sequences coding: on the one hand, it is the quality optimization of DNA sequences coding; on the other hand, it is the designing of DNA sequences coding sets. This paper counters these two aspects to do penetrating research, and puts emphasis on the research about the designing of DNA sequences sets.The main researchful content of the quality optimization of DNA sequences is that: according to the scale of problem, it is to search a certain amount of DNA sequences which satisfy the combinatorial constraints. The common constraints include the Hamming distance constrain, thermodynamics constrain and combinatorial constraints. The two main researchful methods are the theoretical contract and the searching by computer. At present, the research about the DNA sequences is relatively mature, and has developed software which has better ability. This paper which uses the improved genetic algorithm optimizes the quality of DNA sequences. These DNA sequences which are obtained by the improved genetic algorithm not only satisfy the DNA constraints, but also comparing with the previous works, have a significantly improvement.The main researchful content of the designing of DNA sequence sets is that: according to the known the length and the constraints, it is to search all the maximum of DNA sequences sets which satisfy the constraints. The common constraints include the Hamming distance constrain, thermodynamics constrain and combinatorial constraints. It includes two main methods one of which is theoretical research, other is research of algorithm. According to the constrains and the characteristic of the designing of DNA sequences sets, this paper ulteriorly improves the genetic algorithm and uses it to research the designing of DNA sequences sets. It not only makes the algorithm improved, but also obtains the results which are better than previous works.更多还原