DNA计算机原理_进展及难点_生物计算系统及其在图论中的.pdf

第26卷 第1期 2003年1月 计 算 机 学 报 CHINESE JOURNAL OF COMPUTERS Vol 26No 1 Jan 2003 DNA计算机原理 进展及难点 生物计算系统及其在图论中的应用 许 进 1 张 雷 2 1 华中科技大学分子生物计算机研究所 武汉430074 2 中国建设银行信息技术部 北京100077 收稿日期 2002201208 修改稿收到日期 2002210216 本课题得到国家自然科学基金 60174047 60103021 60274026 教育部博士点基 金 湖北省自然科学基金资助 E2mail jxu mail 许 进 男 1959年生 教授 博士生导师 主要研究方向为DNA计算机 图论 神经网络 遗传算法等 张 雷 男 1958年生 博士 研究方向为系统优化算法和生物计算 摘 要 基于生化反应机理的DNA计算机模型受到科学领域内许多不同学科学者们的关注与兴趣 DNA计算已 经形成国际科学前沿领域内研究的一个新的热点 DNA计算机的研制需要诸如生物工程 计算机科学 数学 物理 化学 信息科学 微电子技术 激光技术以及控制科学等许多学科的共同协作攻关 该系列文章拟对DNA计算机的 基本原理 研究进展 DNA计算的模型以及当前研究中的难点给予研讨 该文属首篇 重点讨论了DNA计算机的 基本原理 引入了生物计算系统的概念 并较系统地讨论了DNA计算模型在图与组合优化中的研究进展 关键词 DNA计算 基本原理 生物计算系统 图与组合优化 中图法分类号TP301 DNA Computer Principle Advances and Difficulties I Biological Computing System and Its Applications to Graph Theory XU Jin 1 ZHANGLei 2 1 Institute of Biomolecular Computer Huazhong University of Science and Technology Wuhan 430074 2 Department of Technology China Construction Bank Beijing 100077 Abstract Biomolecular computing is computation at the molecular scale using biotechnology engi2 neering techniques Recently Many scientists in different fields are interest in DNA computer model based on reaction of biochemistry Because DNA computer has been formed a new science field The studying and making DNA computer needs many science subjects such as biological engineering com2 puter science mathematics physics chemistry information science micro2electronics laser technol2 ogy and control science etc Based on this the advances of DNA computer are considered in detail in this four2part paper such as fundamental principle several models of DNA computing and difficulties In this paper authors discuss the fundamental principle introduce the notion of biological computing system and summarize in detail the applications of DNA computing to some NP2complete problems in Graph Theory and Optimizations such as directed Hamiltonian Path problem satisfaction problem maximal clique and maximal independent problem 021 programming problem etc Keywords DNA computing fundamental principle biological computing system graphs and opti2 mization 1 引 言 电子计算机对人类社会的发展起到了巨大的促 进作用 然而 随着社会和科学技术的发展 许多新 工程领域中的复杂巨系统不断出现 在这些复杂巨 系统的研究过程中 各种各样的非线性问题 形形色 色棘手的NP2完全问题处处可见 使得电子计算机 解决这些NP2完全问题 复杂的非线性等问题难度 很大 甚至无能为力 其原因主要有两点 1 与要 解决的实际问题相比 电子计算机的运算速度太慢 2 目前的电子计算机存储信息的容量太小 另外 电子计算机在制造工艺上将很快达到0 08 m这个 极限值 基于这些原因 迫使科学家们寻求其它技术 来提高运算速度与信息存储等问题 于是 人工神经 网络计算机模型 量子计算机模型以及DNA计算 机模型相继产生 其中DNA计算机模型在近几年 内倍受科学界的关注 发展神速 DNA计算是一种以DNA分子与相关的某些生 物酶等作为最基本的材料 以某些生化反应为基础 的一种新的计算模式 DNA计算模型首先是由 Adleman博士于1994年提出来的 1 它的最大优点 是充分利用了DNA分子具有海量存储遗传密码以 及生化反应的海量并行性 因而 以DNA计算模型 为背景而产生的DNA计算机必有海量的存储以及 惊人的运行速度 DNA计算机模型克服了电子计算 机存储量小与运算速度慢这两个严重的不足 它具 有如下4个优点 1 具有高度的并行性 运算速度快 在一周的运 算量相当于所有电子计算机从问世以来的总运算量 2 DNA作为信息的载体其贮存的容量非常 之大 1m3的DNA溶液可存储1万亿亿的二进制数 据 远远超过当前全球所有电子计算机的总存储量 3 DNA计算机所消耗的能量只占一台电子 计算机完成同样计算所消耗的能量的十亿分之一 4 DNA分子的资源丰富 由此可见 DNA计算的每一个突破性的进展必 将给人类社会的发展作出不可估量的贡献 下面 我 们将简要地讨论一下DNA计算与DNA计算机的 几个方面的意义 1 DNA计算与DNA计算机的研究具有极为 重要的意义 2 3 由于DNA计算机的速度惊人 使得 目前的密码系统对于DNA计算机而言已经失去意义 2 DNA计算机的研制对理论科学的研究具 有无法估量的意义 特别是数学 运筹学与计算机科 学 这是因为 在理论研究中许许多多的困难问题在 DNA计算机的面前可能显得非常简单 如大数学家 Erdos认为人类要解决Ramsey数 R 5 5 R 6 6 是非常困难的 然而 若用DNA计算机来解决可能 在几个小时 甚至有望在几分钟内得到解决 3 P N P 这个著名的数学难题有望得到彻 底的解决 进而使人类在计算问题上有一个大的飞 跃 NP2完全问题不再像现在这样困扰科学家们 许 多工程技术问题的研究会大踏步的向前飞跃 4 DNA计算机必将极大地促使非线性科学 信息科学 生命科学等的飞速发展 事实上 在DNA 计算系统中 非线性问题与线性问题几乎是一样的 这些问题的解决与发展必将导致诸如图像处理 雷 达信号处理等巨大的发展 蛋白质优化结构的更深 层认识乃至第二遗传密码的解决 天气预报更准确 乃至整个气象科学的巨大发展等 也必将促使诸如 量子科学 纳米科学等得到巨大的发展 5 DNA计算机的研制成功 对考古学 生态 科学与地球科学等意义更为重大 特别是DNA计 算机时代的天气预报几乎准确无误 正是由于DNA计算与DNA计算机的上述重 要意义 使得目前国际上关于DNA计算与DNA计 算机的研究形成了一个新的热点 正在极大地吸引 着不同学科 不同领域的众多的科学家 特别是生物 工程 计算机科学 数学 物理 化学 激光技术以及 信息等领域内的科学家 2 DNA计算的概念与原理 DNA计算模型可简要地通过图1所示的框图 来描述 输入的是DNA片断和一些生物酶 然后通 过可控的生化反应 输出DNA片断 这些DNA片 断 就是我们所需要的问题的解 DNA计算的基本 原理可视为是将现实实际问题创造性地映射到 DNA计算这种模式上去 图2给出了将诸如图与组 合优化问题 各种数学模型 非线性问题等映射到 DNA计算模式的示意 2 计 算 机 学 报2003年 DNA计算是利用巨量的不同的核酸分子杂交 产生类似某些数学运算的一种组合结果并对其进行 筛选来完成的 4 DNA是由单核苷酸通过磷酸二酯 键共价连接形成的线性多核苷酸聚合物 DNA分子 中一个核苷的5 2OH和另一个核苷的3 2OH通过 磷酸二酯键相连接 核酸分子杂交应用核酸分子的 变性和复性的性质 使来源不同的DNA片段按碱 基互补关系形成双链分子 首先 由于维持双螺旋的 力是由氢键和疏水键提供的 因而凡是破坏氢键和 疏水键的因素都能导致双螺旋的破坏 即导致DNA 分子的变性 这些因素包括加热 极端的pH值 有 机溶剂 尿素 甲酰胺等 其次 DNA分子的变性又 是可逆的 在适宜的条件下 分开的两条单链可以按 碱基互补原则重新恢复双螺旋结构 如通过加热变 性会破坏双螺旋 但当逐渐降温后 双螺旋结构又重 新构成 当参与复性的核酸来源不同时 我们就称为 杂交 5 6 由于DNA分子本身含有5 2OH和3 2OH末 端 故DNA分子是有方向性的 当大量随机的DNA 链相互杂交后 每个DNA链原来所携带的信息就 会产生一种新的组合结果 对于一个给定的运算 此 结果的获得则是通过对DNA分子进行一系列连续 的操作来实现的 这些操作包括 合并 分离 加热与 退火 扩增 切割 连接 聚合 检测等生物工程技术 DNA计算的基本思想是 利用DNA特殊的双 螺旋结构和碱基互补配对规律进行信息编码 把要 运算的对象映射成DNA分子链 在生物酶的作用 下 生成各种数据池 data pool 然后按照一定的规 则将原始问题的数据运算高度并行地映射成DNA 分子链的可控的生化过程 最后 利用分子生物技术 如聚合链反应PCR 超声波降解 亲和层析 克隆 诱变 分子纯化 电泳 磁珠分离等 检测所需要的运 算结果 DNA计算的核心问题是将经过编码后的 DNA链作为输入 在试管内或其它载体上经过一定 时间完成控制的生物化学反应 以此来完成运算 使 得从反应后的产物中能得到全部的解空间 在DNA计算系统中 DNA分子中的密码作为 存储的数据 当DNA分子间在某种酶的作用下瞬 间完成某种生物化学反应时 可以从一种基因代码 变为另一种基因代码 如果将反应前的基因代码作 为输入数据 那么反应后的基因代码就可以作为运 算结果 这样 通过对DNA双螺旋进行丰富的精确 可控的化学反应 包括标记 扩增或者破坏原有链来 完成各种不同的运算过程 就可能研制成一种以 DNA作为芯片的DNA计算机 随着人们对DNA计 算机研究的不断深入 用DNA计算所对应的可控 生化反应以及PCR扩增技术 特别是关于检测技术 的不断提高 生物芯片技术的不断成熟 必将改进诸 如以Adleman为首的试管实验的方法与步骤 或者 改进近期关于表面研究技术等 但有一个基本点是 不变的 那就是DNA计算是充分利用生物酶 蛋白 质 特别是DNA分子的特性以及DNA分子中海量 的密码信息来进行可控的生化反应实现计算这个最 基本的原理 3 生物计算系统 在DNA计算模型的基础上 我们在本节引入 了 生物计算系统 的概念 这个概念是对DNA计 算模型的扩充与抽象 我们可以认为DNA计算过程由4个子系统构 成 它们是资源子系统 运算子系统 生化反应子系 统以及解的检测子系统 由这4个有机相互关联的 子系统构成的系统称为DNA分子计算系统 从更 广泛地的意义上说 我们称之为生物计算系统 如图 3所示 3 1 资源子系统 从目前的分子生物计算研究情况来看 主要以 DNA分子进行 1 3 7 23 另外 也有一些学者应用 RNA 24 以及蛋白质 25 等为材料来进行分子计算 在DNA分子中 有用诸如质粒DNA分子 单链 DNA分子 双链DNA分子 发卡型DNA分子等各 3 1期许 进等 DNA计算机原理 进展及难点 生物计算系统及其在图论中的应用 种类型的DNA分子为材料来进行计算 限于篇幅 有关这方面较为详细的内容 我们将另文讨论 3 2 运算子系统 任何计算机 无论是以碳为基础的 还是以硅为 基础的 都假设具备一种常规数学计算的能力 其中 最为基础的问题就是要考虑如何进行四则运算问 题 由于分子生物计算模型的特性 未来的分子计算 机运算系统不可能仅以四则运算为主要运算算子 而应除了四则运算外 还应以诸如连接酶 核酸内切 限制酶 DNA聚合酶 DNA与RNA修饰酶 核酸外 切酶与核酸内切酶等构成的所谓新型的运算算子 在这一小节里 我们将重点介绍四则运算中的有关 研究进展 3 2 1 加法运算 在DNA计算机运算系统的研究中 首先取得 突破性工作的是Frank等人 7 Frank等运用位置 算子 位置转移算子和位节符等概念 用类似于电子 计算机中的位数交换 bit 2flipping 方法 完成了二 进制数的存取与进位 创造性地完成了对DNA分 子生物运算过程的构造与控制 他们给出了DNA 计算系统中的正有理数的加法运算 他们工作中最 为关键的贡献是解决了加法的进位问题 他们的算 法是很灵活的 无论是被编码的DNA链条作为反 应的起因者还是调查者 这种算法都适用 甚至还允 许 附带一个 和增一个新的固定的数字 但是 该算 法并不允许加法出现在同一个平行的式子当中 主 要原因是人们选择生物技术为基础的计算体系要多 于基于硅的计算体系 Frank等人的工作仅仅是一 种关于实验可行性的一种证实 还未能进入实用性 阶段 下面 我们将简要给出Frank等人在文献 7 中的基本思想 Frank等人的开创性的工作是首先给出了二进 制数0 1的DNA表示方法 如图5所示 在关于 DNA表示方法上已经引入了诸如位置转移算子 位 置算子以及位节符等概念 然后在此基础上建立 DNA计算的加法运算模型 20位置 第1个位数 0 5 DEF 0 1 0 0 DEF 0 3 5 DEF 0 1 1 0 OPP 0 3 0 5 DEF 0 1 1 0 DEF 0 3 5 OPP 0 1 0 0 OPP 0 3 第2个位数 0 3 DEF 0 5 0 3 OPP 0 5 21位置 第1个位数 0 5 DEF 1 2 0 1 DEF 1 J 3 5 DEF 1 2 1 1 OPP 1 J 3 5 OPP 1 2 0 1 CA R 1 J 3 1 5 DEF 1 2 1 1 DEF 1 J 3 5 OPP 1 2 0 1 OPP 1 J 3 5 OPP 1 2 1 1 CA R 1 J 3 第2个位数 0 5 DEF 1 DEF 0 1 J 3 5 OPP 1 OPP 0 1 J 3 1 5 OPP 1 DEF 0 1 J 3 5 CA R 1 OPP 0 1 J 3 22位置 5 1 2 OPP 1 2 J 3 图5 所有可能的非负的两位二进制整数相加对的DNA表示 在给定的2 n位置第 1个和第2个数字分别叫 作要相加的第1个数和第2个数在该位置的值 0 或1 除了上划线暗示了互补的DNA序列之外 所 有DNA序列是单链的 唯一的而且没有补序列 例 如 DEF 0 1 是DEF 0 1 的补序列 括号内的数 字称为位置 不在括号内的数字叫做该位置上的数 字的值 20位置上第一个数由两条DNA链表示 每一条 链含有从5 端开始的 位置转移算子 例如 DEF 0 1 将20位置的信息转移到 21位置 20位置 该数字表示值的元素和 位置算子 如DEF 0 表 示仅用于20位置的算子 20位置上第2个数分别由 单条DNA链DEF 对应数字0 和OPP 对应数字 1 表示 这种单链DNA表示一种算子 它将在引物 扩展反应中充当引物 4 在21位置的第2个数字由 两条DNA链表示 每一条链含有上述所说的位置 转移算子 DEF 0 1 或OPP 0 1 或第3种算子 取名为CA R 携带之意 一个位置算子和一个阻止 粘贴延伸的元素J表示数字的DNA链中只有一条 充当模板进一步延长前一步表示结果的DNA链 4 计 算 机 学 报2003年 如果从20位置载入了0或1 这个引物扩展模板将 分别是表示这个数字的第1或第2链 因此在20位 置和21位置上的位置转移算子的作用分别是发送 和接收信息 在21位置上的第1个数字由3条DNA 链表示 每一条含有如上定义的已有表示的4种元 素 只有其中之一将充当表示结果的DNA链继续 扩展的引物 如果在20位置上的反应带给21位置的 是一个0 而在20位置上的第2个数字是0或1 则 粘巾模板分别对应于0和1的第一个数的DNA表 示中的第1或第2条 然而如果20位置带给21位置 的是一个1 而且第2个数字在20位置上也是1 则 模板必然是表示值1的第3条链 而且1必定被携 带到22位置 为了进行这最后的信息传递 构造了 22位置上的进位器 它将充当在适当条件下才可用 于表达结果的DNA链进一步扩展的模板 后面的这 个操作类似于电子计算机中使用的 位数交换法 Frank等人在上述工作的基础上 在文献 8 中 将文献 7 中的结果扩展到一般的3进制乃至k进制 的加法运算 有关这方面的详细论述参见文献 8 1999年 Bernard等人提出了一种新的DNA加 法模型 这种加法运算与Frank 7 8 的工作相比 其 优点是DNA计算中的Boole逻辑的DNA分子中 输入串与运算串是分离的 该加法通过对几例实验 操作成功显示了具有复杂度为30个逻辑门的数字 分子计算的可行性 有关详细介绍参见文献 9 3 2 2 乘法运算 一种DNA计算的矩阵乘法运算模型在文献 10 中给出 在文献 10 中 作者给出了基于DNA 计算模型的布尔矩阵和正实数矩阵乘法的计算方 法 并将此方法进一步扩展 应用于给出矩阵的幂的 计算 该方法的基本原理简述如下 1 将一个给定的布尔矩阵转化成一个有向图 其转化 的方法可通过图6中的 a 和 b 得到说明 2 应用已有的求解一个有向图的有向Hamilton路径 问题和SAT问题等方法进行运算 详见下一节 或者文献 1 与文献 11 在文献 10 中 作者提出了解决此问题的 两个新的特点 1 提出与以往不同的分析方法 即所谓的 路径综合分析方法 2 应用某种策略进行定量计算 而不 是简单地确定一个成功的路径模式 这种新技术及分析问题的方法能够促进基于 DNA技术来解决更多具有挑战性的组合问题 有关 这方面较为详细的内容参见文献 10 目前关于负数的DNA计算系统中的表示问题 减法运算 除法运算等尚未解决 这些都是DNA计 算机研制过程中必须要解决的问题 3 3 生化反应子系统 在生化反应子系统中 目前主要以诸如连接反 应 PCR 聚合链反应 分子克隆 POA等反应构成 限于篇幅 我们不在此展开讨论 将重点放在PCR 反应 基本原理 PCR是Polymerase Chain Reaction 的缩写 即聚合酶链式反应 此技术是Mullis及其同 事在1985年设计并研制成功 并在1993年Mullis 由于发明PCR仪而与第一个设计基因定点突变的 Smith共享诺贝尔化学奖 PCR的原理类似于DNA 的天然复制过程 待扩增的DNA片段和与其两侧互 补的两端寡聚核苷酸引物 经变性 退火和延伸若干 个循环后 DNA扩增倍数可达到2 n倍 可用如下公 式表示 y 1 x n 其中 y为DNA扩增倍数 x为扩增效率 n为循环 数 PCR法需要的基本条件 5 1期许 进等 DNA计算机原理 进展及难点 生物计算系统及其在图论中的应用 1 靶 目标双链 DNA 2 两个可与目标双链上的相对链的侧翼序列 杂交的引物 3 4种脱氧单核苷酸 dNTP 4 DNA耐热聚合酶 Taq聚合酶 5 适量的Mg2 存在 PCR的3个步骤 1 高温变性 将材料加热到95 以解开DNA 分子的双链 每条链各为一个模板 2 低温退火 将温度降到55 使引物与模板 结合 3 中温延伸 将温度升至72 在DNA聚合 酶的引导下 将核苷酸加到与模板结合的引物上 这 样 被复制的DNA数就增加了一倍 这一过程大约 持续5min 在这个过程结束时 温度重新被升高 下 一循环开始 PCR法是一种可以快速并准确地大量复制 DNA片断的技术 它有3个特点 1 可以不经分离 而制造特别的DNA片断 2 可以制造大量的DNA 片断 3 只需极少量的DNA片断就可以很好地完 成基因测定 这种方法非常方便 它不仅使以前的技 术变得更快 更准确 还为进行以前无法想像的实验 带来了新思路 在PCR法发明之前 复制重组体DNA的各种 方法都要花费大量的时间和人力 而使用一台PCR 法的机器就可以在几个小时内完成多轮复制 生成 几十亿个DNA片断 PCR的主要应用 1 快速并准确地大量复制DNA片断 2 PCR用于产物的检测 3 PCR法测定基因表达的相对差异 4 PCR用于测序 5 PCR用于克隆 3 4 解的检测子系统 解的检测子系统是以诸如电泳技术 层析分析 技术 分子纯化技术 同位素技术 荧光技术以及激 光技术等构成 有关系统深入的结果参见文献 6 26 27 这里略去 由于生物计算系统概念的引入 我们对DNA计 算概念与原理应有一个重新的认识 所谓DNA计 算 就是在对资源子系统中的DNA分子 通过相应 的生物运算酶以及某些可控的生化反应得到相应的 数据池 然后通过解的检测子系统将所需的解检测 出来 相应的 DNA计算的基本原理可理解为 如何 将实际中的某一个具体的数学问题 或者非线性问 题 或者图与组合优化问题等映射到DNA分子生物 计算系统上去 见图7所示 4 DNA计算在图与组合优化中的应用 众所周知 电子计算机在解决图与组合优化中 的NP2完全问题上是非常困难的 特别是规模很大 时几乎是不可能的 但是 基于生化机理的DNA计 算在解决图与组合优化有些问题上却有一种 天然 的优势 也可能是这个原因 目前在关于DNA计算 模型的实验实例中 几乎绝大多数是图与组合优化 中的一些NP2完全问题模型 所以 我们将在这一节 里重点论述这方面的成果 4 1 有向H amilton路问题的DNA计算模型 设G是一个有向图 v1 v2是G的两个顶点 如果存在一条从v1出发到达v2 且经过G中其它 每个顶点一次且只有一次的有向路P 则称P是G 中从v1到v2的一条有向Hamilton路 寻找一个给定 有向图的有向Hamilton路问题是所谓的有向 Hamilton路问题 简记为HPP问题 类似地可定义 无向的情况 1994年Adleman开拓性地提出了应用DNA计 算方法求一个给定有向图的有向Hamilton路问题 的算法 1 这种算法的基本思想是首先让有向图的 每一个顶点随机地对应一条长度为20的寡聚核苷 酸 在此基础上 让图中的每一条弧对应确定的长度 为20的寡聚核苷酸 加入适量的连接酶 并通过 PCR扩增技术获得从起点到终点的全部有向路 再 通过电泳技术检测出所需要的Hamilton有向路 Adleman对图4所示有向图进行了实验证明 实验 时间长达1星期 求出了从指定起点 A 到终点 G 的Hamilton路 这一开拓性的成果 开辟了用 DNA分子通过生化反应进行计算的新时代 下面 6 计 算 机 学 报2003年 我们将简要给出Adleman的算法步骤与相应的生化 实验 求解HPP问题的算法步骤 1 随机生成通过该图的路径 2 仅保留起点为A 终点为G的路径 3 仅保留有p个顶点的路径 4 仅保留进入该图所有顶点至少一次的图 5 如果存在满足上述条件的路径 输出为YES 否则为 NO 对于上述算法的每一步 Adleman通过生化反 应来完成 算法第1步的生化实验操作 1 令图中每个顶点i对应一条随机长度为20的寡聚 核苷酸S i 例如我们取 S 2 TATCGGATCGGTATATCCGA S 3 GCTATTCGAGCTTAAAGCTA S 4 GGCTAGGTACCAGCATGCTT 这些寡聚核苷酸的片断的方向是5 3 2 对于图中的每一条弧i j 构造一条寡聚核苷酸 S i j 方法如下 将S i 中的序列分为两个部分S1 i 和S2 i 其中 S1 i 为前10个碱基 S2 i 为后10个碱基 序列 基于上述准备 Adleman对于图8中每一条i j弧 定 义它所对应的寡聚核苷酸序列为S2 i S1 j 例如 S 2 3 GTATATCCGA GCTATTCGAG S 3 2 CTTAAAGCTA TATCGGATCG S 3 4 CTTAAAGCTA GGCTAGGTAC 3 构造连接反应 对于图中每个顶点和每一条弧 在 单个的连接反应中 取出50pmolS i 表示S i 的补链 和 50pmol的S i j 分别混合在一起 S i 核苷酸充当夹板 将相容的弧连接在一起 从而连接反应的最终结果导致了以 编码形式对应图的随机路径的DNA分子形成 S 2 3 S 3 4 GTATATCCGA GCTATTCGAG CTTAAAGCTA GGCTAGGTAC 3 CGATAAGCTCGAATTTCGAT 5 S 3 4 连接反应分析 连接反应的规模大大超过了所考 虑的图的必需程度 对于图中的每一条弧 大约有3 1013个 拷贝被加入到连接反应中 因此 几乎没有理由怀疑编码 Hamilton有向路的许多DNA分子是否生成 理论上 产生出 一个这样的DNA分子集合就足够了 事实上 对于此图而 言 核苷酸的数量少于1 mol级可能足矣 换言之 一个更大 的图用于此处的核苷酸应以p mol数量级进行 算法第2步的生化实验操作 对于第1步的产物 通过以 S 0 和 S 6 为引物来进 行PCR扩增 算法第3步的生化实验操作 对于第2步的产物进行凝胶过滤层析 分离出140个 碱基对所对应的恰好有7个顶点的路径的双螺旋DNA 并 将其浸泡在重蒸馏水 即双氧水ddH2 O 中以便提取 所得产 物经过PCR扩增 琼脂凝胶过滤层析 纯化数次 进一步增 加纯度 算法第4步的生化实验操作 对于第3步的产物用磁珠分离系统进行亲和层析 为 此 首先将双螺旋DNA融化 解链成各种单链DNA 然后用 与磁珠结合的 S 1 孵化试管中的单链DNA 只有那些含有 序列 S 1 而编码了顶点1至少1次的单链DNA分子得以 保留 对于 S 2 S 3 S 4 S 5 等的施行与 S 1 的过程 相同 算法第5步的生化实验操作 对于第4步的产物进行PCR扩增并进行珠凝胶电泳 以上我们比较详细地介绍了Adleman创造的 DNA计算方法求解有向图的有向Hamilton路问题 的模型 最近 我们在此模型的基础上 进一步对赋 权型的Hamilton路问题 其中包括有向与无向的两 种类型 建立了DNA计算模型 我们不在此详述 有兴趣的读者参见文献 25 4 2 可满足性问题的DNA计算模型 SAT问题的定义 设A a1 a2 是一组 Boole变量的集合 一个子句是一个公式 C b1 b2 bk 其中符号 表示逻辑 或 每个bi是A中的一个变 量或者A中变量的补 A中的元素a的补用符号a 来表示 一个逻辑式是指由若干个子句的 与 构成 的式子 C1 C2 Cr 其中每个Ci是一个子句 而符号 表示逻辑 与 可满足性问题是要求出满足逻辑式 中满足 1的解的集合 这个问题显然是一个NP2完全问 7 1期许 进等 DNA计算机原理 进展及难点 生物计算系统及其在图论中的应用 题 目前基于DNA计算的SAT问题有不少模型 我 们在此将重点介绍Lipton在1995年的工作 11 有 关其它模型参见文献 22 1995年 Lipton仿效Adleman的方法 对于可 满足性问题 SAT问题 给出了一种DNA计算模 型 11 此模型的基本思想是 让SAT问题的每一个 可行解对应成一个n位二进制数 通过构造简单接 触网络Gn 将n位二进制数据池对应成网络Gn的 从起点a1到终点an 1的有向路 如图9所示 然后 用 Watson2Crick 方法 构造DNA数据池 通过4 种基本的分子生物技术 聚合重叠放大POA 综合 SYNTHESZE 聚合链反应探测PCR2DETECT 解 螺提取EXTRACT 得到SAT问题的全部解 Lipton的基本思想如下 1 如果一个公式 C1 C2 Cr包含k 个变量 则构成所有的k2位DNA分子串 并将其放 入在一个试管t0之中 2 对每个子句Ci b1 b2 bm m k i 1 2 r 以及j 1 2 k 从试管ti 1中提 取bj2位是1的k个位 即 如果bj a 则第bj2位 的值是1 如果bj a 则第j位的值是0 在试管ti 中结合所有的子句 3 如果在最后的试管tr中存在DNA 则答案 是 Yes 否则为 No 下面 我们将较为详细地给出Lipton的具体计 算步骤 1 对图9中的顶点及有向边采用和Adleman相同的方 法进行编码 即顶点和边的长度均为20bp 对任一顶点i用 piqi表示 pi和qi分别为顶点i的前10bp和后10bp序列 对 任一有向边i j用qipj表示 将编码顶点和边的DNA分子 放入初始试管t0 经过充分反应后就会形成代表图G中各 种有向路的DNA分子 2 以pa1和qa3为引物搜索出试管t0中以a1开始以a3 结尾的有向路 于是t0中就剩下代表上面4条路的DNA分 子 3 从试管t0中搜索出第1位为1 x 1 的DNA分子 并放入试管t1中 剩下的放入试管t 1中 然后再从试管t 1 中搜索出第2位为1 y 1 的DNA分子放入试管t2中 将 试管t1和t2合并为t3 得到满足第1个子句的DNA分子 4 从试管t3中搜索出第1位为0 x 0 的DNA分子 并放入试管t4中 剩下