DNA计算中的核酸序列设计及应用研究

摘要

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计算机和电子计算有机两者有机地结合起来，能够大大提高计算效率。

目录

文摘

英文文摘

声明

1绪论

2基于剪枝算法的DNA编码设计

3基于过滤函数的DNA编码设计

4基于纠错码理论的DNA序列设计

5多值输入DNA逻辑门构造

6网络最大流的DNA算法

7总结与展望

致谢

参考文献

附录