基于三链DNA结构的0-1整数规划

论文摘要

DNA计算是一种以DNA与相关的某些生物酶等作为最基本材料的、基于某些生化反应原理的一种新型的分子生物计算方法。DNA计算的最大优点是充分利用海量的DNA分子中的遗传密码以及巨量的并行性。因而,以DNA计算模型为背景而产生的所谓的新一代计算机,称为DNA计算机,必有海量的存储以及极快的运行速度。在DNA计算系统中,DNA分子中的密码作为存储的数据,当DNA分子在某种酶的作用下瞬间完成某种生物化学反应时,可以从一种基因代码变为另一种基因代码。如果将反应前的基因代码作为输入数据,那么反应后的基因代码就可以作为运算结果（输出数据）。这样,通过对DNA双螺旋进行丰富的精确可控的化学反应,包括标记、扩增或者破坏原有链来完成各种不同的运算过程,就可能研制成一种以DNA作为芯片的DNA计算机。本文从DNA计算所使用的DNA分子构形角度,对目前主流的计算模型:表面计算模型、粘贴计算模型、质粒计算模型以及三链计算模型进行了介绍。文中尝试利用三链DNA计算模型解决DNA计算领域内的时间复杂度转化为空间复杂度问题,给出了0-1整数线性规划的模型。对于一般整数规划可以转化为0-1整数线性规划,同时给出了可满足性问题也能转化为整数线性规划从而转化为0-1整数线性规划。文中还给出了利用表面载体计算模型、DNA芯片模型等解决0-1整数规划。

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 DNA简介
• 1.2 DNA计算的研究现状
• 1.3 目前 DNA计算待解决的问题
• 2 DNA计算的生物学基础
• 2.1 DNA的结构
• 2.2 DNA计算中主要的生物操作
• 2.2.1 DNA链的分离与结合
• 2.2.2 DNA链的延伸
• 2.2.3 DNA链的链接
• 2.2.4 DNA链的内切
• 2.2.5 DNA链的外切
• 2.2.6 DNA链的复制
• 2.2.7 DNA链长度测量
• 3 目前常用的DNA计算模型
• 3.1 表面计算模型
• 3.2 粘贴计算模型
• 3.3 质粒计算模型
• 3.4 分子信标模型
• 3.5 三链 DNA模型
• 4 基于抗原中介三链DNA结构的0-1整数线性规划
• 4.1 0-1整数规划
• 4.1.1 基本算法
• 4.1.2 生物算法
• 4.1.3 生物编码与生物操作步骤
• 4.2 简单0-1规划模型实例
• 4.3 一般0-1整数规划
• 4.4 可满足性问题
• 4.5 结论
• 5 0-1规划问题的其他DNA计算模型
• 5.1 简单0-1规划问题的DNA计算模型
• 5.2 0-1规划问题的表面DNA计算模型
• 5.3 0-1规划问题的DNA计算模型
• 5.4 0-1规划问题的DNA芯片模型
• 结论
• 参考文献
• 后记或致谢
• 作者简介及读研期间主要科研成果