学海网

博士学位论文 DNA计算若干问题研究，共51页
摘要：1994年,Adleman用操纵DNA分子的办法解决了一个经典的NP完全问题—哈密顿路径问题(一个包含7个顶点实例)。自此以后,生物计算作为生物与计算机科学的交叉学科迅速的发展起来。 本文探讨了生物计算中最受关注的DNA计算中的一些算法及编码问题。 在第一章中,首先介绍了一些相关的预备知识;其次,对生物计算,特别是DNA计算的不同研究方面及状况进行了简要的总结分析,例如DNA计算的模型,解决NP完全问题的算法等。 在第二章中,提出了把参数算法应用于生物计算,以减少生物计算的空间复杂度的思想。这一章首先给出了顶点覆盖问题的参数算法,和这个参数算法用DNA计算模型实现的方法,并且得出这个算法以非常接近于1的概率的输出正确结果。 本章还利用独立集和顶点覆盖问题的关系,得到了在输入参数很大的情况下,降低解决顶点覆盖问题的所需分子数目的方法。相应的,也得到了独立集问题的生物参数算法。 在第三章中,首先给出了在粘结模型下解决带有数值参数的NP完全问题—划分问题的生物算法,并分析了其正确性。在此...
关键词：DNA计算; 空间复杂度; 数值参数; θ自由码子集; 层次结构;