论文部分内容阅读
1994年,Adleman博士采用DNA分子和生物酶作为计算材料,成功地求解了含有七个顶点的有向图Hamilton路问题,开创了DNA计算的新纪元。近年来,国内外众多学者已开始从事这一领域的研究工作,并取得了丰硕的研究成果。关于DNA计算和DNA计算机的探索,在理论研究、实验方法以及实现技术手段上都得到了很大的发展。
在DNA计算中,序列编码问题占据核心地位,它直接影响到DNA计算的有效性和可靠性,并决定了最终DNA计算的成败。本文以DNA序列的编码问题为出发点,对其进行了分析研究。在此基础上,讨论了DNA计算在多值逻辑门运算中的应用,最后将DNA计算用于求解最大流量问题。本文的主要工作包括以下几个方面:
本文研究了DNA序列的编码问题,将剪枝算法用于DNA序列编码设计,设定了相关组合和热力学约束条件,有效提高了编码序列的设计速度。计算机仿真结果表明,同现有的结果相比,采用剪枝算法设计的编码序列满足一定约束条件,具有较高的编码质量和热力学稳定性,能够提高DNA计算的可靠性和有效性。可见,在设计小规模DNA编码序列时,采用剪枝算法进行DNA编码具有很好的设计效果。
构造了用于DNA序列编码的过滤函数,将DNA编码序列映射为实空间中的向量并对其进行了分析研究。在此基础上设计了用于DNA序列编码的算法,并对所生成编码序列进行分析比较。计算机仿真结果表明,基于过函数的DNA编码算法是有效的。将其用于DNA编码序列设计时,能够得到质量较高,热力学稳定性较好的DNA编码序列。
在纠错码编码理论的基础上,设计了用于DNA序列编码的算法,采用该算法能够构造出满足一定约束条件的DNA编码序列。算法仿真结果表明,设计核酸序列时,算法是有效的。
设计了基于发卡结构的多值逻辑运算DNA计算机模型。将基于化学诱导结构的DNA发夹结构用于构造多值输入逻辑门,并设计了3模代数逻辑系统中模3加法运算的发卡模型。计算后的逻辑门可以重新被利用,而且逻辑门的输出信号与输入信号具有相同的线性DNA编码形式,使得上一级逻辑门的输出信号可以直接作为下一级逻辑门的输入。这种构造逻辑门的方法也可应用于其它多值逻辑运算。本文构造的多值逻辑运算DNA计算机模型具有可重复利用以及可靠性较高等特点。
最后,本文将DNA计算用于求解最大流量问题。求解该类问题时,算法一般分两阶段进行,在第一阶段采用DNA算法,利用了DNA计算的巨大并行计算能力,求解出相应扩充流网络中所有的增广链。与现有的算法相比,在第一阶段采用DNA算法求解最大流量问题时,计算复杂性最低。算法分析表明,将DNA计算机和电子计算有机两者有机地结合起来,能够大大提高计算效率。