DNA计算中的3-SAT问题的自装配算法

论文摘要

在过去的10 年中,DNA 计算取得突飞猛进的成果,尤其是在SAT 问题上,以Lipton , Adleman , Qinghua liu 等人为代表的科学家们纷纷在SAT 问题上,取得了可喜的成果。本文则在前人的基础上继续探索3-SAT 问题的有效算法,并给出了4 种方法的8 个算法第一种算法为自装配算法,根据自装配的原理,设计了链接方式,设计的思想非常简单明了,那就是首先在m 个试管中分别找到可以使m 个子句各自为1的链,然后再将找到的这些链全都倒入同一个试管中,利用自装配方法一步找到公共链,也就是公式的解。第二种方法为荧光标记法,它是自装配算法的一种,只不过他采用了荧光标记的方式,它的设计思路与第一种方法基本相同,所不同的是,在第二步将m个试管中的链到入同一个试管中之后,用的是探针模板来找公共解, 这也是一步完成的,与算法一的效果是一样的,只是它的空间复杂度要比算法一要小一些。第三种算法为三联接法,其实质上是算法一的一种改进算法,不过所采用的方式比起算法一要巧妙的多,它同过三联接的设计,较好的解决了时间复杂度的问题。它主要通过三联管的设计,以三个试管为一个单位,进行自装配,也就是分步自装配法,实现方法与第一种算法相同。第四种方法为三分法,,这是一种分支策略,首先对所有的变量通过其在子句中出现的数目进行变量重排,然后利用对斜率的算法,求出第一个分支点k,再根据不同的情况确定第二个分支点,从而将所有的变量分成三部分,根据这个划分,相应得创建三个子库,对于三个子库相应的将所有的子句划分成四个部分,从而将原来的公式划分成四个子公式。这样就将求原来的公式解得问题划分成求四个子公式的公共解得问题。这4 种方法的8 种算法,。前三种算法是本文的基本算法,它们的共同之处在于,通过自装配模型来实现了算法的高度并行,从而将算法的时间复杂度降低到了常量时间,而空间复杂度与其他算法相比却没有改进,而三分法则克服了上述缺点,在将算法的时间复杂度降低到了常量的同时,也将空间复杂度降低到了较小的水平。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 DNA 计算的显著特点
• 1.3 DNA 计算的自装配
• 1.4 DNA 计算的发展现状
• 1.5 研究内容、意义及前景展望
• 1.6 本章小结
• 第2章 SAT问题
• 2.1 可满足性（SAT）问题的概念
• 2.1.1 定义
• 2.1.2 布尔表达式
• 2.1.3 SAT 问题的一般表述
• 2.2 NP 完全问题
• 2.3 约束可满足性问题
• 2.4 3-SAT 问题
• 2.5 其它可满足性问题
• 2.6 DNA 计算中的操作原理
• 2.6.1 DNA计算的基本步骤
• 2.6.2 DNA链的互补原则
• 2.6.3 DNA计算的简单试管操作
• 2.7 DNA计算的常用操作
• 2.8 本章小结
• 第3章 SAT 问题的综述
• 3.1 试管溶液法
• 3.1.1 Lipton 的有向图法
• 3.1.2 Adleman 凝胶电泳法
• 3.1.3 Adleman20 个变量的SAT 问题
• 3.1.4 RNR 解决国际象棋问题
• 3.2 表面基法:
• 3.2.1 Qinghua liu 等人的表面基算法
• 3.3 两种特殊的算法
• 3.3.1 发夹算法
• 3.3.2 DNA 的抑制性算法
• 3.4 自装配算法
• 3.4.1 可满足性问题的2D DNA 自装配
• 3.5 搜索算法
• 3.5.1 SAT 问题的一个子句链的DNA 算法
• 3.5.2 在环状分子上解决3-sat 问题的随机搜索算法
• 3.5.3 以DNA 为基础的并行算法
• 3.5.4 k-SAT问题的一个空间有效算法
• 3.6 本章小结
• 第4章 自装配并行算法的设计
• 4.1 自装配算法
• 4.1.1 库S 的设计
• 4.1.2 算法及操作
• 4.1.3 算法分析
• 4.2 三联法
• 4.2.1 库S 的设计
• 4.2.2 算法及操作
• 4.2.3 算法分析
• 4.3 三分法
• 4.3.1 分支策略
• 4.3.2 自装配模型
• 4.3.3 三联接模型
• 4.4 本章小结
• 第5章 荧光标记法设计
• 5.1 荧光标记法
• 5.1.1 设计A:
• 5.1.2 设计B:
• 5.2 三分法的荧光标记模型
• 5.2.1 调用4.3.1 分支策略
• 5.2.2 库链的设计
• 5.2.3 算法及操作
• 5.2.4 算法分析
• 5.3 探针及芯片的制备
• 5.3.1 探针的制备
• 5.3.2 芯片的制备
• 5.3.3. DNA芯片上的杂交反应
• 5.4 本章小结
• 第六章 算法举例
• 6.1 自装配算法
• 6.2 三联接法
• 6.3 荧光标记法
• 6.4 本章小结
• 结论
• 参考文献
• 致谢