【作者】 潘果；

【导师】 李肯立；

【作者基本信息】 湖南大学 ， 计算机应用， 2007， 硕士

【摘要】 1994年,Adleman用操纵DNA分子的办法解决了一个经典的NP完全问题—哈密顿路径问题(一个包含7个顶点实例)。自此以后,生物计算作为生物与计算机科学的交叉学科迅速的发展起来。随着DNA计算研究的逐渐深入,现有基于穷举方法的DNA计算机算法中存在的解空间指数爆炸问题日益突出,已成为限制DNA超级计算应用的瓶颈因素,如何减少DNA计算机求解NP完全问题中以问题输入纯指数增长的DNA链数,已成为DNA计算研究的重要内容之一。现有DNA计算模型的并发操作难以达到电子计算机并行处理操作的自如程度,因此,不管基于DNA计算的何种模型,目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式,而DNA计算模型上的不可扩展是求解NP问题算法上难于扩展的原因。因此考虑将传统电子计算机并行处理的策略、方法和技术引入DNA超级计算是降低DNA链数的重要途径之一。这一问题源于现有DNA计算模型的不可扩展性。本文考虑将传统电子计算机中的并行策略应用于DNA计算中,采用理论分析和生物实践相结合的方法,解决DNA计算中限制DNA计算的瓶颈的DNA链数问题。具体将分治策略应用于DNA计算领域中,提出了基于分治策略的求解子集积问题的DNA计算机算法,并通过对现有算法中存在的时间复杂度过高的问题,提出一种具有较好可扩展性的改进质粒模型,并将分治策略应用于子集积问题的DNA分子算法设计中,提出一种求解子集积问题的新的DNA计算机算法。本文提出的算法的DNA链数均可达到亚指数的O(1.414n),其中n为子集积问题的维数。将提出的算法与已有文献结论进行的对比分析表明:本算法在不改变算法操作复杂性的条件下,将穷举算法中的DNA链数从O(2n)减少至O(1.414n),因此利用本算法在试管级水平上能将可破解的背包公钥的维数从60提高到120。更多还原

【Abstract】 Since Adleman successfullu solved an instance of hamiltonian path problem with 7 vertexes, which is a NP-complete problem, biomolecular computation has become a new a research field which sets up a bridge over computer science and biology.With the researching goes deeply, the problem of exploding of solution space existing in DNA computing algorithms based on the exhaust method, this has been the bottleneck in the application of DNA computing. How to decrease the volume in DNA computers has become a basic problem in the research of DNA computing. And the poor scalability in the DNA-based algorithms roots in the poor scalability of the DNA models. This leads to almost all the current DNA computing algorithms taking the brute-force mehod regardless of the different models, and the exponential increase in DNA volume. Therefore, taking the strategy, method and technology of parallel processing of the traditional computers into DNA computing is an important way to reduce the DNA strands volume.This paper proposed an improved plasmid model for DNA computing. For the objective to decrease the DNA volume which increases in a pure exponentially with the scale of the subset sum problem, an improved plasmid model is proposed in this paper. Based on it, a new DNA algorithm for subset sum problem is also proposed where the strategy of divide and conquer is introduced. In this algorithm, we develop an improved plasmid-based algorithm to finish the function of decimal subtraction. The proposed algorithm can solve the n-dimension subset sum problem by using the O(1.414n) shorter DNA strands on the condition of not varying the time complexity, as compared by far the best molecular algorithm for it in which O(2n) DNA strands is used. Therefore, the scale of the public key cryptosystem can be theoretically broken using biological operations may be enlarged from 60 to 120 variables.更多还原