1994年,Adleman用操纵DNA分子的办法解决了一个经典的NP完全问题—哈密顿路径问题(一个包含7个顶点实例)。自此以后,生物计算作为生物与计算机科学的交叉学科迅速的发展起来。 本文探讨了生物计算中最受关注的DNA计算中的一些算法及编码问题。 在第一章中,首先介绍了一些相关的预备知识;其次,对生物计算,特别是DNA计算的不同研究方面及状况进行了简要的总结分析,例如DNA计算的模型,解决NP完全问题的算法等。 在第二章中,提出了把参数算法应用于生物计算,以减少生物计算的空间复杂度的思想。这一章首先给出了顶点覆盖问题的参数算法,和这个参数算法用DNA计算模型实现的方法,并且得出这个算法以非常接近于1的概率的输出正确结果。 本章还利用独立集和顶点覆盖问题的关系,得到了在输入参数很大的情况下,降低解决顶点覆盖问题的所需分子数目的方法。相应的,也得到了独立集问题的生物参数算法。 在第三章中,首先给出了在粘结模型下解决带有数值参数的NP完全问题—划分问题的生物算法,并分析了其正确性。在此基础上,给出了背包问题相应的算法。本章的最后,还给出了一个可以进行连续加法运算的,主要使用剪切和连接操作的方法。 DNA计算的另外一个重要的问题是什么样的编码能够减少操作所需生化反应的错误。这个问题和DNA序列的组成有密切的关系,要减少错