文档介绍：华中科技大学
博士学位论文
剩余数与PCR在DNA计算中的应用
姓名:郑学东
申请学位级别:博士
专业:系统分析与集成
指导教师:许进
2009-12-02
华中科技大学博士学位论文
摘要
电子计算机技术在科学研究与工程实践中获得了巨大的成功,但芯片的承载
能力与处理能力限制了电子计算机计算速度的长久增长。作为一种新的计算模
式,DNA计算获得了广泛关注。DNA计算主要面临以下困难:编码的质量与数量
之间难以协调,编码问题难以求解;实验中繁琐的操作及生化反应的不完全,会
对DNA计算结果产生不良影响;另外,对NP-完全问题,计算所需DNA分子数量与问
题规模呈指数关系,限制了DNA计算的求解问题规模。针对上述问题,本文尝试从
以下几个方面对DNA计算进行一些研究与讨论。
针对DNA编码问题,给出一种基于小种群遗传算法的求解方法。介绍了DNA编
码问题的定义、约束条件及相关参数的计算方法。通过将H-类约束映射到DNA码字
个体上,并引入码字之间的共享函数,构造了DNA编码问题的多目标优化模型,使
得应用小种群遗传算法求解DNA编码问题成为可能。在具体求解过程中,引入逆补
密码子算子,分段交叉算子,频变算子与倒位算子,对DNA编码问题进行了求解。与
已有的结果相比,小种群遗传算法可以避免码字质量分布不均匀的问题,且种群规
模约为DNA码字数量的2倍,计算量较少。
为降低DNA编码难度,在DNA算术运算中引入剩余数制。基于Adleman-Lipton模
型,给出了DNA剩余算术运算的编码方案,以及二进制算术运算的DNA算法,并
分别基于4-模数集P = {2n+1 + 2n − 1, 2n, 2n − 1, 2n + 2n−1 − 1}与n−模数集P =
{2mn−1 , 2mn−2 − 1, · · · , 2m0 − 1},给出了剩余算术运算的DNA算法。在n−模数集中,
1
计算的并行度为n,计算对DNA码字的需要量约为相应二进制情况下的。由于剩余
n
位之间无进位影响,可以发挥DNA计算的并行性,减少DNA分子操作步骤,有助于
误差控制。
为避免DNA计算中生化反应不完全对计算结果的不良影响,这里用PCR作为
主要的操作手段实现了DNA计算过程,构造了基于PCR操作的计算操作模型,且计
算过程中不需要限制性酶。基于该模型,给出了逻辑与算术运算的DNA编码方案
以及DNA算法,并针对一个典型的NP-完全问题–最小顶点覆盖问题,给出了求解
的DNA编码方案与DNA算法。PCR的应用使得计算操作简单可靠,DNA分子的分离
仅与其长度有关,分离操作更为精确。
I
华中科技大学博士学位论文
对DNA计算中NP-完全问题求解的指数爆炸问题,给出遗传算法的PCR构造。利
用PCR操作来构造基本遗传算法中的变异算子、交叉算子以及选择算子,将遗传
算法中的适应度函数映射为DNA双链分子的长度,并将用PCR构造的遗传算法应
用于最小顶点覆盖问题的求解,给出了二进制位串的DNA编码方案,及问题求解
的DNA算法与结果比较。与其它操作手段相比,用PCR构造遗传算法更为可行,且
计算不需要预先生成解空间,可以避免指数爆炸问题。
关键词:DNA计算,DNA编码,遗传算法,剩余数制,逻辑与算术运算,聚合酶链式
反应,NP-完全问题,顶点覆盖问题
II
华中科技大学博士学位论文
Abstract
Although the puter has achieved a great ess in the scientific re-
search and the engineering practice,the carrying capacity and the processing power of
the chip restrict the puter to maintain long-term growth of putation
speed. As a puting paradigm, puting has attracted a considerable at-
tention. The main difficulties in puting are as follows. The problem of DNA
coding is difficult to be solved and it is hard to coordinate the relationship between the cod-
ing quantity and the coding quality. The tedious operat