题目：活体生物计算模型在NP-完全问题中的应用

自上世纪九十年代Adleman在实验室用分子生物实验操作成功地求解一7个顶点图的Hamilton路问题以来，生物计算这个全新的研究领域就随之产生。因为生物计算具有巨大的并行性、海量的存储能力以及较低能耗等优势，该领域的研究愈来愈引起众多研究者的关注。本文结合分子生物学的实验技术及研究方法，对生物计算及其计算模型的生物实现做了初步的分析及讨论，并主要从活体生物计算模型出发，对图与组合优化中的哈密尔顿路（HPP）和可满足性（SAT）两个基本问题进行了讨论与研究，具体内容如下：
目前生物计算中存在三个难点问题：1、编码，把求解的问题映射为生物分子，这也是生物计算中首要解决的问题，目前的编码方法还不能很好地满足生物计算模型的实际需求；2、生物实现，如何设计实验和操作，使得代表问题解的分子顺利生成，而不出现“伪解”或“错解”；3、解的检测，如何正确检测问题的解是当前生物计算研究中的困难问题之一，本文对现有检测技术进行了详细的论述和分析。
活体生物计算模型是基于各种生化分子在生物活体内以特定形式进行的相互协作处理信息而出现的一种新的生物计算模型。由于它的计算组成部件具有一定的计算能力，并且直接镶嵌在生物活体里面，这就使得人们可以深入研究生物体处理信息的能力以及对获得这种能力进行有效的控制。本文主要对基于质粒载体的活体生物计算模型进行论述，并首次对哈密尔顿路（HPP）和可满足性（SAT）问题进行了活体生物模型分子算法的探讨。
HPP是一NP-完全问题，它在工程优化、现场管理等很多实际问题中有着广泛的应用，本文首先对问题进行单双链混合编码，然后利用质粒载体对相关路径进行了筛选，最后通过电场分离装置提出最优解，并给出实例以说明此算法的具体实现步骤。
SAT问题是众多NP-完全问题的“种子”，在人工智能、硬件测试等方面有着广泛应用，本章基于活体生物计算模型给出了SAT问题的分子算法，首先对各个变量给予编码，值得提出的是，所有的编码都在一条双链DNA分子上，这样使得编码操作即合成DNA的工作量相应减少；计算过程中通过每个约束条件对质粒重组体进行酶切操作，在对各个子句都进行相应的酶切操作判断后，剩余的试管中所含有的代表变量的DNA串即是我们要输出的解空间，最后检测即获得问题的解，并给予实例说明了此算法的实现。在本章后，还给出了此算法的推广，即解决数学中的全错位排列问题，其基本思想是首先把全错位排列问题转化为可满足性（SAT）问题，然后再基于活体生物计算模型给出此问题的分子算法。
本文的最后，分析讨论了活体生物计算模型的优势和不足之处，即虽然活体生物计算模型有着一定的优势，但是就现在的生化实验操作和技术来讲还存在着一定的难题，①对于活体的操作过于难以控制；②随着求解问题规模的增大，限制性内切酶种类的需求增多；③酶切的错误可能造成数据丢失和“伪解”或“错解”的出现。总之目前对于活体的控制操作还存在着很大的困难，如何避免或解决这些困难就成为我们今后研究的方向，需要我们更进一步的努力。