近几年DNA计算作为一门新的交叉学科正逐渐发展起来,DNA计算是一种以模拟生物分子DNA的结构为手法,通过相应的生物技术来进行运算的一种新方法,利用DNA计算模型为背景和DNA的大量存储能力和高度并行性设计新一代计算机。所以DNA计算机也是一种利用DNA建立的一种完整信息技术形式,以编码后的DNA序列为运算对象,运用生物分子学的操作,获得最后目标DNA链,解决所求问题的生物计算机。DNA计算的基本思想是:用分子生物技术解决计算机难题,使运算过程可控操作。DNA计算模型包括粘贴模型、质粒模型、双链DNA模型等。目前作为研究热点之一的DNA信息处理领域的DNA计算技术具有并行性好,能耗低,可保存性高等优点,因此,它已被应用于各种复杂的计算问题。DNA纳米技术的新兴领域也发展迅速,其中DNA链置换的方法因自诱导,灵敏,准确,操作简单而备受关注。本文介绍了一种基于DNA链置换的生物计算方法,它是一种无需人工干预的计算方法。该模型能够使用逻辑公式在连接范式中执行迭代解析步骤。该方法的实现基于DNA链置换技术,每个子句编码在一个单独的DNA分子命题中,被编码为每个命题和它的互补链对应命题子句被编码在同一条链中的不同命题。该模型允许通过级联解析步骤运行由霍恩子句组成的逻辑程序。该模型的潜力也体现在其求解SAT的理论能力上,结果的SAT算法在求解步骤的数量上具有线性时间复杂度,而其空间复杂度在公式的变量数上是呈指数级增加的。本文总结了DNA计算中DNA链置换的最新发展的五个方面:(1)级联电路;(2)催化反应;(3)逻辑计算;(4)表面上的DNA计算;(5)基于由链置换引导的纳米颗粒的逻辑计算。本次研究首先介绍了几种目前计算领域所涉及的新兴生物技术,重点介绍了本研究涉及的技术,然后利用链置换技术解决最大匹配问题、小顶点覆盖问题及邮递员问题。第一,以DNA计算为研究背景,讨论DNA计算的研究意义和发展前景。第二,对于已给图形中所有的边集,找出图中任意两条边没有共同顶点的最大边集,这是一个是NP完全问题,求解这种问题的算法模拟把数学问题转换到DNA链上,对所给图中的每一条边采用DNA的特点进行编码,而在相应的生物操作中,利用链置换技术把目标链分离出来,这条链表示解。通过实验操作,给出基于链置换的最大匹配问题的解决方式,验证此算法有效可行。第三,本文针对DNA计算解决最小顶点覆盖覆盖问题,采用对表示空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。第四,组合优化中典型的背包问题是非常重要的NP问题,针对0-1背包问题,本文采用把数学问题转换到DNA链上的算法,对给定物品的体积和价值分别进行编码,不加入连接酶的情况下,根据DNA链的W-C原理,将所需的DNA链分别用一条短链连接,并在反应过程中,加入外源链,得到满足约束条件的物品组合,利用链置换技术及相应的生物操作删除外源DNA链,以及最终链的分离,给出基于链置换的0-1背包问题的计算方式,提出的算法有效可行。第五,将邮递员的行走路线用图论的语言来描述,本文采用把数学问题转换到DNA链上的算法,对给定图G中的每条边进行编码,并编码出连接的DNA链,生成问题的解的DNA链,及相应的生物操作把最终链分离,得出问题的解。第六,本文对DNA编码方法进行设计,并设计一种用6个顶点求解的中国邮递员问题的算法,证明提出的DNA计算方式的算法有效可行。