（系统工程专业论文）DNA计算和遗传算法的编码与几个优化模型的研究.pdf

华 中 科 技 大 学 博 、 士 学 位 论 文 摘要 计算机技术被认为是2 0 世纪三大科学革命之一， 电子计算机为社会的发展起到 了巨大的促进作用，但是量子物理学己经成功地预测出芯片微处理能力的增长不能 长期地保持下去。基于这一原因，科学家们正在寻找其他全新的计算机结构，如人 工神经网络计算机、量子计算机、光学计算机以及d n a计算机模型等，其中d n a 计算机倍受科学界的关注。本文对d n a计算的d n a编码和遗传算法进行了研究。 全文由“ 导论” 、 d n a序列编码和优化模型” 、 “ 遗传算法编码与优化模型” 、 “ 总结 和展望”四个部分组成。本文的研究主要包括二方面的内容: d n a计算中的编码问 题和模型研究。 由于在d n a计算中，信息总是通过特定长度的d n a序列来表示的，因此，选 择高质量的方式来表示 d n a序列就成为一个重要的问题。本文给出了一个改进的 d n a序列的图表示:在2维直角坐标系内用四个特定的向量分别表示d n a序列中 的四 个碱基， 从而使d n a序列可以用一个平面内的有向路表示。 文中给出了一个例 子说明该方法的有效性， 可以证明该种改进的d n a序列图表示方法具有较低的退化 度甚至没有退化。 我们给出了d n a计算中序列设计的支持系统: 计算由多个评价指标的线性和组 成的适应值函数的最小值。我们的系统不仅可以搜索好的序列，而且可以得出每个 评价指标对于适应值函数的贡献度。通过简化适应值函数，可以减少各评价指标的 数目 .这有助于为d n a计算的序列设计找到好的评判标准。 本文提出了一个适合生物学特征的实数的编码方案， 该方案的编码有固定长度。 根据问题的特征， 提出了一个求解最小支撑树问题的d n a算法。 仿真验证了所提出 的方法的有效性，同时也讨论了该方法的优点和缺点。 在模型研究中，本文主要就如下几个问题给出了有效的算法模型。首先给出了 图的关联着色和文件传输问题的遗传算法。文中对一个关联色数是 6的图进行了仿 华 中 科 技 大 学 博 士 学 位 论 文 真， 得到了该图的关联色数。同时给出了文件传输问题的边着色模型。给出了一个 例子来说明算法的收敛性和收敛效率。 其次给出了基于e l m o r e 模型的s t e i n e r 树问题 的遗传算法。给出了一个表示解的染色体新构造方法。分析了算法的时间复杂性和 空间复杂性。 关键词:d n a 计算 关联着色 d n a 编码最小支撑树问题遗传算法图 着色 文件传输问题s t e i n e r 树问题 . ， . 巨 喇 ， ， ， ， 叫 ， 曲 ， . 目 目 . ， 巨 呻 . . 巨 n 华 中 科 技 大 学 博 士 学 位 论 文 abs tract t h e c o m p u t e r t e c h n i q u e i s c o n s i d e r e d a s o n e o f t h e t h r e e b i g r e v o l u t io n s o f s c i e n c e i n 2 0 c e n t u r i e s , a n d t h e c o m p u t e r i s p l a y gr e a t r o l e f o r t h e d e v e l o p m e n t o f s o c i e t y . b u t q u a n t u m p h y s i c s s u c c e s s f u l l y f o r e c a s t t h e i n c r e a s e o f m i c r o - p r o c e s s i n g a b i li t y o f c h i p c a n n o t k e e p d o w n f o r a l o n g p e r io d . s o , s c i e n t i s t s a r e s e e k i n g o t h e r c o m p l e t e l y n e w c o m p u t e r s t r u c t u r e . s u c h a s a rt i f i c i a l n e u r a l n e t w o r k c o m p u t e r , q u a n t u m c o m p u t e r , o p t i c a l c o m p u t e r a s w e l l a s d n a c o m p u t e r m o d e l . a m o n g t h e m , t h e d n a c o m p u t e r i s p a i d m u c h a t t e n t i o n b y s c i e n t i s t s . s t u d y o n t h e d n a c o d i n g f o r d n a c o m p u t in g a n d g e n e t i c a l g o r i t h m s i s i m p l e m e n t e d i n t h i s d i s s e rt a t i o n . t h e w h o l e d i s s e rt a t i o n i s d i v i d e d i n t o f o u r p a r t s : i n t r o d u c t i o n , s e q u e n c e c o d i n g a n d o p t i m i z a t i o n m o d e l o f d n a c o m p u t i n g , c o d i n g a n d o p t i m i z a t io n m o d e l o f g e n e t i c a l g o r i t h m s , a n d s u m m a r y a n d r e s e a r c h i n s i g h t s . t h i s d o c t o r a l t h e s i s m a i n l y f o c u s e s o n t h e f o l l o w i n g t w o s u b j e c t s : t h e e n c o d i n g p r o b l e m a n d t h e v o l u m e e f f i c i e n t a l g o r i t h m f o r c o m b i n a t o r i a l o p t i m a l p r o b l e m s . i n d n a c o m p u t i n g , t h e i n f o r m a t i o n i s a l w a y s r e p r e s e n t e d b y u n i q u e d n a s e q u e n c e s t h e r e f o r e , i t i s v e r y im p o rt a n t t o s e l e c t h i g h q u a l i t y w a y s t o e n c o d e d n a s e q u e n c e s . i n t h i s t h e s i s , w e g i v e s a n o v e l gra p h i c a l r e p r e s e n t a t i o n o f d n a s e q u e n c e s b y t a k i n g f o u r s p e c i a l v e c t o r s i n 2 - d c a rt e s i a n c o o r d i n a t e s y s t e m t o r e p r e s e n t t h e f o u r n u c l e i c a c i d b a s e s i n d n a s e q u e n c e s , s o t h a t a d n a s e q u e n c e i s d e n o t e d o n a p l a n e b y a d i r e c t e d w a l k . a e x a m p l e t o i l l u s t r a t e t h e e f f i c i e n c y o f t h e m e t h o d i s g i v e n . i t i s s h o w n t h a t t h e n e w g r a p h i c a l r e p r e s e n t a t i o n o f d n a s e q u e n c e s h a s l o w e r o r n o n d e g e n e r a c y . w e d e v e l o p s u p p o rt s y s t e m f o r s e q u e n c e d e s i g n i n d n a c o m p u t i n g , w h i c h m i n i m i z e s t h e e v a l u a t io n f u n c t i o n c a l c u l a t e d a s t h e l i n e a r s u m o f t h e p l u r a l e v a l u a t i o n t e r m s . o u r s y s t e m n o t o n l y s e a r c h e s f o r g o o d s e q u e n c e s b u t a l s o p r e s e n t s c o n t r i b u t i o n r a t i o o f e a c h e v a l u a t i o n t e r m t o t h e e v a l u a t i o n f u n c t i o n a n d c a n r e d u c e t h e n u mb e r o f c o mb i n a t i o n o f e v a l u a t i o n t e r m s b y r e d u c t i o n o f t h e e v a l u a t i o n f u n c t i o n . i t h e l p s u s t o f i n d a g o o d c r i t e r i o n f o r s e q u e n c e d e s i gn i n d n a c o m p u t i n g . a n e w e n c o d i n g s c h e m e f o r r e a l v a l u e s t h a t i s b i o l o g i c a l l y p l a u s ib l e a n d h a s a f i x e d i i i 华 中 科 技 大 学 博 士 学 位 论 文 c o d e . l e n g t h i s p r o p o s e d . a c c o r d i n g t o t h e c h a r a c t e r o f t h e p r o b l e m , a d n a a lg o r i t h m s o l v in g t h e m i n i m u m s p a n n in g t r e e p r o b l e m i s g i v e n . t h e e ff e c ti v e n e s s o f t h e p r o p o s e d m e t h o d i s v e r i fi e d b y d i s c u s s e d . s i m u l a t i o n . t h e a d v a n t a g e s a n d d i s a d v a n t a g e s o f t h i s a l g o r i t h m a r e r e g a r d i n g t h e a l g o r i t h m d e s i g n , w e m a i n l y p r e s e n t e f f i c i e n t a l g o r i t h m s f o r t h e f o l l o w i n g p r o b l e m s . f i r s t l y , w e p r e s e n t a g e n e t i c a l g o r i t h m f o r t h e i n c i d e n c e c o l o r i n g o n g r a p h s a n d s t e i n e r t r e e p r o b l e m . t h e p a p e r g i v e s a s i m u l a t i n g a b o u t a g r a p h w i t h i n c i d e n c e c o l o r i n g n u m b e r 6 , a n d o b t a i n s t h e i n c i d e n c e c o l o r i n g n u m b e r o f t h e g r a p h . a e d g e c o l o r i n g m o d e l f o r f i l e t r a n s m i s s i o n p r o b l e m s i s g i v e n . a n e x a m p l e t o i ll u s t r a t e t h e c o n v e r g e n c e p r o p e rt y a n d t h e c o n v e r g e n c e e f f i c i e n c y o f t h e a l g o r i t h m i s g i v e n . t h e n , a n e w g e n e t i c a lg o r it h m f o r s t e i n e r t r e e p r o b l e m b a s e d o n e l m o r e m o d e l i s d e v e l o p e d i n t h i s t h e s i s . a n e w m e t h o d c o n s t r u c t i n g c h r o m o s o m e f o r s o l u t i o n s i s p r e s e n t e d . t h e c o m p l e x i t y b a s e d o n t i m e a n d s p a c e i s a n a l y z e d d n a c o m p u t i n g g e n e t i c a l g o r i t h m s d n a c o d i n g min i m u m s p a n n i n g t r e e p r o b l e m g r a p h c o l o r i n g i n c i d e n c e c o l o r i n g f i l e t r a n s mi s s i o n s t e i n e r t r e e p r o b l e m. 份-户 种 种 种 种 . 种 种 . . . . . 口 . . . . 种 . 种 种 种 . . 口 . . i v 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的 研究成果。 尽我所知，除文中己经标明引用的内 容外， 本论文不包含任何其他 个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体， 均己 在文中以明确方式标明。 本人完全意识到本声明的 法律结果由本人承担。 学 位 论 文 作 者 签 名 : 扣 、 孙 食 口 ， 日 . n n n ， 年 ，、 月 汀 日 学位论文版权使用授权书 本学位论文作者完全了 解学校有关保留、使用学位论文的规定，即:学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在_年解密后适用本授权书。 本 论 文 属 于/ 不保密.e ( 请在以上方框内打 “v v ) 学 t g 文 作 者 签 名 : 列扬鸯 日 期 : -) .0 9 年! za 肠 日 指导教师签名 日 m : ;,id if :_ 夺 ( 7 ,q 1 叫 华 中 科 技 大 学 博 士 学 位 论 文 1 绪论 【 摘要】 : 本章简 要概述了d n a 计算的 研究现状、 d n a计算的 墓本思想与 计算方法、 d n a 计算 的应用与进 展、以 及目 前d n a计算研究中 存在的问 越等. 在本章的 后边 部分给出了 论文的主 要 思路和创新之处，以及本文所获得的主要结果. 【 关钮词】 :d n a计算，编码， 研究进展， 研究内容与方法 1 . 1选题依据和资助项目 n p 完全问 题是国内 外算法研究领域的热点和难点。 该类问 题的解决不仅具有重 要的理论意义，而且在国民 经济各行各业有非常重要的应用前景。目 前对这类问题 的研究已 转向模拟生物智能的智能化方向发展。在探索智能形成机制方面所取得的 成就给人们的启示是:研究智能的最好方式是向人类自 身学习。目 前对智能的模拟 和研究主要有三个不同的方法和技术: ( 1 ) 人工神经网 络方法: 它以 生物大脑神经元受外界刺激后相互作用为原型， 在 神经元层次上模拟大脑神经系统进而模拟生物大脑的自 主学习和自 适应的能力。基 于神经网络的神经计算是一种能 够模拟人脑局部功能的超大规模并行计算。 1 9 8 5 年 h o p f ie ld和t a n k 两 人开 拓 性 地 采 用h o p f ie ld神 经网 络 模型 对 有3 0个 城市的 下 s 尸 仃 r a v e l in g s a le m a n p r o b le m ) 这个n p 一 完全问 题进行了 研究， 在0 .0 2 秒内 搜索 到问 题的 解， 取得了 传统 方法 无法 取得的 可喜结果。 在h o p f ie ld 网 络中 ， 系 统能 够 从初始状态，经过一系列的状态转移而逐渐收敛于平衡状态，此平衡状态是局部极 小点。 (2 ) 进 化 计 算 方 法 2) : 它 以 达 尔 文 进 化 论 为 支 持 ， 借 鉴 生 物 界自 然 选 择 和自 然 遗 传 机 制 的 生 物 群 体 优 胜 劣 汰 的 竞 争 机 制， 主 要 包 括 遗 传 算 法( g e n e r ic a lg o r it h m s , 简记为g a s ) 、 进化规划(e v o lu t io n a ry p r o g r a m m in g ，简记为 e p ) 和进化策略 ( e v o lu t io n a ry s t r a t e g ie s , 简 记为e s ) 。 进 化计 算的 研 究 试图 揭 示 学习 过 程 在 基因 层 次 上的 实 现， 其中 以h o lla n d 3 提出 的 遗 传 算 法 最具 代表 性。 遗 传 算 法 通过 在 求解 1 华 中 科 技 大 学 博 士 学 位 论 文 过程中使群体不断优化，进而找到最优解或准最优解。在算法实现方面，它具备了 结构上的隐含并行性、计算原理上的随机性和自 适应性，对非线性复杂问题的全局 搜索能力及简单通用、鲁棒性强的显著特点，迅速成为国际学术界和工程界关注的 热点。 ( 3 ) d n a 计算方 法: 这是一 个 最新发 展 起来的以 模拟分 子生 物d n a的 双螺旋结 构和碱基互补配对规律进行信息编码的方法和技术。从遗传进化、人工神经网络和 d n a分子生物技术对智能的模拟过程看，它们分别对应生物群体、生物神经网络和 生物分子三个不同的层次。由此可以看到， 基于对分子生物d n a的模拟和研究将有 可能更深刻地揭示智能形成的本质。d n a计算与 d n a计算机的研究发展神速，在 诸如d n a计算应用于一些n p 一 完全问题解法、d n a计算的运算问题、d n a计算在 生物实验方面的研究、 d n a计算机的语言系统、 联想记忆问 题、 d n a计算在密码学 上的 应用等都取得了 不少巨大的 进展5 -9 ,1 1 -2 2 ,4 5 .5 5 d n a计算是一种以d n a与相关的某些生物酶等作为最基本材料的、 基于某些 生化反应原理的一种新型的分子生物计算方法。在杂交过程中的错误杂交，容易产 生丢失解 ( 对于有些问题来说，会产生伪解) 。 这一问题是生物技术上目 前很难控制 的， 也是d n a计算研究的主要难点之一。同时， 单链寡聚核昔酸片断之间可能会形 成不需要的发夹结构。因此需要设计适合d n a计算的编码。关于d n a编码的研究 也是d n a计算研究中的一个热点。 目 前， 已 经有 许多关于d n a 编码的理 论和 应用研究ij r- 1 。 多 数的 研究 都是围 绕 如何防止或降低计算过程中错误而展开的。 d e a t o n 和g a rz o n 首先对a d le m a n 的试 验中 可能 发生的 各种错误进行了 分 类ia s i 。 同 时 他们还给出了 一 个关于可以 有可信的 解 的 问 题 规 模的 上 界 im。 在h a m m in g距 离 的 基 础 上， 他 们 引 入 了 一 种 对 于 杂 交 可 能 性的 新 评 价 方 法， 提出 了 关 于d n a 计 算 避免出 错的 理 论 19 0 1 . m a ra t h e 等 提出 了 基 于h a m m in g 距离的d n a 序列 动 态 规 划设 计 方法 9 1 . f r u t o s 等 给出 了 一 个 利 用 尽量 少 的 模 式 和映 射 选 择 大 规 模的 不 相 类 似的d n a 序 列的 模 式 方 法 19 2 1 . h a rt e m in k 等人 利 用s c a n 程 序 产 生了 可 程 序 化 突 变 的d n a 序 列 【93 1 . f e ld k a m p 等 人同 样 提出 一 个 d n a 序 列生 成 程 序 9 4 1 . 该 程 序 利 用了 有向 图 ， 图 的 顶 点 是 碱 基串 ， 一 个 顶点 的 后 继 是四个串， 这些串可以 在一个长的序列里作为后继串出现。g a rz o r x 等提出了h一 测 度函 数 概念 9 5 1 。 该函 数 对一 个d n a 序列 和 它的 互 补串 间 的h a m m in g 距离 进 行了 度 华 中 科 技 大 学 博 士 学 位 论 文 量，能够反映这两条串是否能够进行杂交。也有关于在计算中使用有相同的退火温 度的d n a分子的研究。 若还需要应用限制性切割酶， 则还要避免产生冗余的带有识 别位点的双链d n a分子。 本文研究的第一部分对d n a计算编码进行研究; 第二部分对遗传算法优化模型 进行研究，在这一部分我们的研究重点是编码。 本课题的研究得到了国家自 然科学基金资助，资助课题为: ( 1 ) d n a计算在图论与组合优化中的应用” ，项目 批准号:6 0 1 0 3 0 2 1 ; ( 2 )“ 基于d n a计算的系统优化方法探索” ，项目 批准号:6 0 1 7 4 0 4 7 . 1 . 2 d n a计算的过程、基本思想、研究领域和研究简况 1 9 9 4 年， a d le m a n 的划时代的一篇论文在 s c ie n c e 上发表，第一次实现了 用生物材料作计 算物质解决数学问 题: 七个顶点的有向图的h a m ilt o n 路径问 题吹 该思想基于如下事实: ( ， ) 生物体异常复杂的结构是对由d n a序列表示的初始信息执行一系列简单操 作的结果; ( 2 )可计算函数可以 通过一系列基本的简单函数的计算而得到。 洞察两者之间的相似性，正是 d n a计算诞生的基础。d n a全序列的信息破译 与d n a计算有两个共同的 特征: 都以d n a为物质基础，又都以 计算 数学 ) 为基本 原理。 这显然不是巧合，因为它们都揭示着同一个新的自 然观: 生物是计算的产物， 计 算是 生物的 本能。 关于d n a 计算的 综 述文章参见 56 -8 8 1 1 .2 . 1 d n a计算的一般过程 d n a计算的过程一般是先产生代表问题所有可能解的 d n a表示，然后通过生 化反应及电泳等分离技术逐步排除错误答案，最后得到正确答案。 d n a计算一般可 概括为3 个基本步骤，即: ( ， ) 分析要解决的问题， 采用特定的编码方式， 将该问题反映到d n a链上，并 根据需要合成d n a链: ( 2 ) 根据碱基互补配对的原则进行d n a链的杂交， 由杂交或连接反应执行核心 3 华 中 科 技 大 学 博 士 学 位 论 文 处理过程; ( 3 ) 得到的产物即为含有答案的d n a分子混合物， 用提取法或破坏法得到产物 d n a 。 在提取前通常采用p c r 技术或克隆技术扩增d n a的量， 提取分析后得到结 果，常用的提取方法有凝胶电泳。 破坏法的目 的是排除非答案d n a分子，如使用限 制性核酸酶切断干扰d n a链。 如果待计算的问 题比较复杂， 经一轮的核心处理和提取分析只能得到中间结果， 那么可重复步骤( 2 ) , ( 3 ) 直到得到满意结果为止。 在d n a计算中，d n a串 用由四个基本的碱基组成的序列表示，由字母a 工qc 表示，5 和3 ， 表示 d n a 串的方向。 一个串可以表示为一个序列:5 tta 0 0 0 a 3 ,: 表示由零个字母组成的空串。由于相应的操作可以在d n a串上进行，因此 d n a计 算模型是如下基本的生物操作的多种组合: 一 合成所需要长度的d n a串; 一 混合:将两个测试试管的内容物倒入第三个; 一 退火 ( 杂交):通过降低溶液温度连接两个互补的单串 形成双链; 一 熔解 ( 变 性):通过加热溶液温 度将双链d n a 解开形成单串 ; 一 扩增 ( 复制) : 通过聚合链式反应 ( p c r) 得到d n a辛的多个复制; 一 分离:通过电泳分离不同 长度的d n a链; 一 提取:通过亲 合纯化得到包 含特定模式作为子串 的d n a链; 一 切割:利用工业 化的限制性切割酶在特定的位点将d n a双链切封; 一 连接:利用d n a连接酶将具有相容粘贴端的两个d n a链连接 一 替代: 通过p c r指定位寡聚核等酸突变剂替代、 插入或者删除d n a序列; 一 检测或读出:从溶液中检测或读出一个d n a序列 1 . 2 . 2 d n a计算的基本思想 d n a计算是一种以d n a与相关的某些生物酶等作为最基本材料的、基于某些 生化反应原理的 一种新型的分子生物计算方法。 利用d n a特殊的双螺旋结构和碱基 互补配对规律进行信息编码， 把要运算的对象映 射成d n a分子链， 在生物酶的作用 下，生成各种数据池( d a t a p o o l) ，然后按照一定的 规则将原始问 题的数据运算高度 并行地映射成d n a分子链的可控的生化过程。 最后， 利用分子生 物技术如聚合链反 华 中 科 技 大 学 博 士 学 位 论 文 应p c r 、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等， 检 测所需要的运算结果。d n a计算的核心问题是将经过编码后的d n a链作为输入， 在试管内或其它载体上经过一定时间完成控制的生物化学反应，以此来完成运算， 使得从反应后的产物中能得到全部的解空间。 d n a 计算的最大优点是充分利用海量的d n a 分子中的遗传密码，以及巨量的并 行性。因而，以d n a 计算模型为背景而产生的所谓的新一代计算机，称为d n a 计算 机， 必有海量的存储以及极快的运行速度。在d n a 计算系统中，以d n a 分子中的密 码作为存储的数据， 当d n a 分子间在某种酶的作用下瞬间完成某种生物化学反应时， 可以 从一种基因代码变为另一种基因 代码。 如果将反应前的基因代码作为输入数据， 那么反应后的基因代码就可以作为运算结果。这样，通过对d n a 双螺旋进行丰富的 精确可控的化学反应，包括标记、 扩增或者破坏原有链来完成各种不同的运算过程， 就可能研制成一种基于d n a 芯片的d n a 计算机。 1 .2 3 d n a计算的 研究领域 目 前，关于d n a计算及d n a计算机的研究，主要集中在以下几个方面: 1 ) 研究可用于d n a计算的不同分子结构。 如单链的d n a分子( 主要以 此为平 台) ， 双链的d n a分子( 大部分d n a计算模型的建立都离不开 双链d n a分子卜单 双链混合d n a分子 ( 如粘贴模型) 、 环状的d n a分子 ( 如质粒分子)以及半环状的 d n a 分子 ( 如发夹结构分 子) 、 k - 臂d n a 分子结构等11 2 2 -1 3 4 1 2 ) 建 立不同问 题的d n a计 算模型。 如 组合优化中的n p 一 完全问 题 及困 难的 计 算问题、 密码破译、矩阵乘法、加法运算等问题。 3 ) 研究d n a计 算有关的形 式语言 及d n a计算的 复杂 度。 4 ) 在d n a计算实验中， 研究如何选择实际操作的参数数目、 个体操作的速度、 个体操作和序列操作的可靠性、信息载体的稳定性及一个实验中连续操作的次数。 5 ) 研究适合d n a计算的d n a编码。 较多的单链寡聚核昔酸片断中可能有些会 形成发夹结构，这就需要在编码时，尽可能的使所选择的寡聚核昔酸片断有比较明 显的差异。关于d n a编码的研究也是d n a计算研究中的一个热点。 6 ) 在杂交过程中的错误杂交。当杂交过程中产生错误杂交时， 容易产生丢失解 ( 对于有些问 题来说， 会产生伪解) 。 这一问题是生物技术上目 前很难控制的， 也是 s 华 中 科 技 大 学 博 士 学 位 论 文 d n a 计算研究的主要难点之一。 1 .2 . 4 d n a计算的研究简况 d n a计算并不是一个固定的模式，由于问题的多样性导致所采用的分子生物技 术的 多 样 性， 具体问 题需要具体设计。 a d l e m a n 4 ) 于1 9 9 4 年首次 使用d n a分子 计 算方法解决了一个7 顶点的h a m ilt o n ia n 路径问题。自a l d e m a n 成功应用d n a计 算给出了h p p问题d n a计算模型之后，化学家、生物学家、计算机科学家共同努 力， 尝试用d n a计算方法解决更多的问 题，希望充分发掘d n a计算的潜力。h p p 问题属于组合优化类的一类 n p完全问 题， 用d n a计算方法计算该类问题有很多成 功的实例。 在a d le m a n 思 路 的 启 发 下 ， q .o u y a n g 11 3 1给出 t 解 决 最 大团 问 题的d n 解 。 普 林 斯 顿 大 学l ip t o n 1 2 1作 了 类 似 的 探 索， 以 求 解 决 数 学 中 另 一 个n p问 题 可 满 足性问 题s a t (s a t is f ia b ilit y o f a b o o le a n f o r m u la ) . c n f ( c o n j u n c t iv e n o r m a l f o r m) 是合取范式。 c n f - s a t问 题是s a t问 题一 个子类。 s a k a m o t o 等人在无任何外加控制情况下采用发夹形式的d n a分子计算方 法 解 决了6 变 量1 。 子 句的c n f - s a t问 题p 3 -7 4 1 。 普 林 斯 顿 大 学的l a n d w e b e r 等 人 应用了基于r n a的分子计算方法解决了一个 国际象棋问题， 这个关于国际象棋中马 如 何 移动的问 题也 属于s a t问 题的 一 个实 例p o -7 2 1 h e a d 提出了 用 质粒d n a 分 子 来 解 决可 满足 性问 题 1 4 熟高 琳， 马 润 年， 许 进 利 用质粒d n a分子结构给出了图的 最大匹配问 题的d n a计算模型 1 46 1 ; 张连珍， 许 进给出了一种基于环状质粒d n a计算的新方法， 这种计算质粒包含一个特殊的插入 d n a序列片断，每个片断定位在匹配的限制性内切位点，通过剪切和粘贴实现计算 过 程， 并 讨论了0 - 1 背 包问 题 ( z k p ) 的 质 粒d n a 计 算 模型 算 法 i 3 l a c u k r a s 等人 用r n a代替d n a给出了 可满足性问 题的一种实验性的计算模型，并讨论国际象棋 问 题 的r n a计 算 模 型 1 a 2 0 0 。 年， l iu 等 人对的 可 满足 性问 题 进行了 基于 表 面实 验的d n a计 算 0 2 0 0 1 年， w u 对 表 面 计算 进行了 改 进， 使 得表 面 计算 的 操 作 更具 有 可 行 性 0 2 0 0 0 年，日d n a 计 算 机 研究具 有 突破 性的 进 展 应 是2 0 0 1 年以 色 列w e iz m a n n科学院 的 b e n e n s o n关于 基于分 子生 物的 可 编程 半自 动 化 试管 型 d n a 计 算 机 的 研 究 1 s 。 这 种 有 限自 动 机由d n a和 操 作d n a的 生 物 酶 构 成。 该自 一 . . . . . ， ， 一 . . . . 一 . ， 一 . . . . 一 - . . . . . 一 . . . . . . . . . 口 . . . . 目 . ， ， . ， . . 6 华 中 科 技 大 学 博 士 学 位 论 文 动操作的硬件由限制核酸酶和连接酶构成，软件和输出由 双螺旋输出编码， 且编程 相当于选择适当的软件分子。 同年， 日 r a ic h 等给出了半自 动化自 组装d n a计算模型， 并 利 用该 模型 解 决了 含 有2 。 个 变元的3 一 可 满 足性问 题1 5 0 1 。 他们 利 用 所 有 解的 组 合 构 造s t ic k e r 模 板， 通过 杂 交 对 解 进 行 检 测。 他 们的 思 想与l ip t o n 的 思 想 基本 相同 ， 但是他们将解的捕获和电泳这两步生物操作进行了合成，从而使得他们所采用的生 物方 法 具 有自 动 化的 特点。 另 外， 这 个 模型 解 决了 具 有2 。 个 变元z 2 0 种 解的 组合 的 可满足问题， 是到现在为止最好结果， 也为d n a计算的高度并行性提供了更有力的 证据。 在d n a 计 算 模 型 的 研 究 中 ， 粘 贴 模 型1 4 9 -1 5 0 1 和 剪 接 系 统 模 型 ( s p lic in g s y s te m m o d e l ) s ， 一， 5 2 1 是 最 近 几 年内 主 要 的 两 个 模 型。 k a r l 等 对 粘 贴 系 统 进 行了 研 究 4 8 -5 0 1 9 9 8 年 ， p a u n 与g rz e g o r z 在 文 献 1 5 2 1 的 基 础 上 将 粘 贴系 统 的 概 念 推 广 到 一 个 更为 普 遍的 形式上。 文献 5 3 1 给出了 基于粘贴 模型的图的 顶点覆盖问 题; 文献1 5 4 1 中 提出 了 粘贴 模型的 一 种扩展型的 新 模型，即 所谓的k 一 进制 粘贴模型。 文献 1 56 1 用粘贴模 型给出了诸如图的子图求解、 图的所有k 一 团、 k 一 独立集、 h a m ilt o n 路与圈 等问题、 以 及 关 于 给 定 边 或 者 顶 点 集 的s t e in e r 树 等 问 题的d n a 计 算 模 型。 这 些 算 法 不 仅 确 定了 解的存在而且产生了所有的解， 且对具有” 个顶点， 条边的无向图g， 这些算法 的 运 行时间 在。 十 ， 线 性时间内 。 在文献 i 1 m中 对粘贴d n a计算机 模型给予 较为 详细 地讨论，诸如基本模型、 在粘贴模型的基础上建立起来的粘贴系统、k 一 进制粘贴模 型理论及其应用、粘贴模型在图与组合优化上的应用等，并建立了图的顶点着色问 题k 一 进制粘贴模型。 除 d n a片断外，此外还有许多的分子结构或生物材料可以用来实现计算。 h a g iy a 等 人 v 3 1首 次 将 单 链。 n a 形 成 的 发 夹 结 构 用 于b o o le a n p - f o r m u la 的 学 习 问 题， a d le m a n 将 该 方 法 命 名 为wh ip la s h p c r 。 利 用 这 种二 级结 构 ，可使d n a 分 子计 算实 现自 动 控 制。 s a k a m o t 。 描 述了 有限 状 态 变换 n 4 1 . l a n d w e b e r 等 人 7 1 ,7 2 1首次 将 r n a用于分子计算的工作， 他们用该方法解决了一个象棋难题。 对于r n a参与的 分 子计 算， 因 为r n a的2 轻 基 对 水 解 敏 感， 故 能 提 高 选择 性从 而降 低 错 误 率 1 3 。 一 般d n a计算需要用分子生物学的 技术由 反应混合物中提取表示问 题的 解的d n a分 子， ， 这个过程通常要用p c r扩增产物， 并用凝胶电泳分离， 这两个操作都耗时而且 易产生错误。g a rz o n等人提出了 一种完全酶控制的方法来获得代表答案的d n a分 华 中 科 技 大 学 博 士 学 位 论 文 子， 并 应用该方法解决了h a m i lt o n io n g r a p h 问 题。 该方法中对代表地图中 各顶点的 d n a链采用了 特殊的 编码方案使它们退火后生成的 路径是一个封闭 单链分子， 路径 分子的扩增利用了d n a修复系统中起重要作用的r e c - a蛋白、聚合酶;路径的筛 选中使用了单链核酸内切酶、核酸外切酶、连接酶，整个扩增和筛选辅以热循环。 实验证明， 用该方法既 排除了不需要的d n a分子，又会使代表可能路径的d n a分 子以 指数倍扩增。 win f r e e 等人精心设计和选择了带有3 个或4 个粘性末端的三分支 和交叉结构的 碎片(t ile ) d n a分 子实现了 抽象的 拼图 ( t i li n g ) ， 并用 于分子计算的自 控 制。 g a r z o n 等人利用生物分子体系内在的容错机制提出了自 控制和容错的有限状态 机( f s m ) 的分子实现方法。s h a p i r o提出了一个类似的用来实现图灵机 (t u r in g m a c h in e ) 的 方 法。 逻辑电 路( b o o le a n c ir c u it ) 的 应 用 将把电 子 计算 机中 信息 处 理技术成功地引入分子世界，是分子计算中的一个重要进步。l ip t o n较早提出 将逻 辑电路的评价方法用作s a t和经典 n p问题的解决方案。a m o s等人改进了这种方 法的 应 用。 a r it a 将 该 方 法 应 用于h p p 问 题。 n a t a s a j o n o s k a 等 人， 61 提出 了 利 用3 维图 结 构 进行计 算的 方法。国 外其他的 一些关于d n a 计 算的 文章见r7 + - 7 气 国内 关于d n a 计算的 研究见t a m -1 2 1 1 ， 其中 文1 0 7 系统地讨论了d n a计算模型 在图与组合优化中的研究进展，提出了生物计算系统的理论体系。然而，利用d n a 计 算解决实际问 题 方 面的 研究不多 1 3 s - 1 4 4 目 前， d n a计算研究极大地吸引了不同学科、不同领域的众多的科学家。 特别 是计算机、分子生物、数学、物理、化学以及信息等领域内的科学家们。d n a计算 机有望成为人类科学史上的一个新的里程碑， 因为d n a计算机有望解决当今在电子 计算机上许多无法解决的问题，如密码破译、困难的 n 户 一 完全问题以 及当