（计算机软件与理论专业论文）多级分离技术及若干问题的dna算法研究.pdf

太原理工大学硕士研究生学位论文 多级分离技术及若干问题的d n a 算法研究 摘要 d n a 计算是一种新的计算模式，它以d n a ( d e o x y r i b o n u c l e i ca c i d ，脱氧核 糖核酸) 为“原料”，以生化实验为工具进行计算。d n a 分子具有庞大的存 储容量，d n a 计算具有其它计算方法无法比拟的巨大的并行性。 自1 9 9 4 年美国南加州大学的a d l e m a n 教授用生化实验解决了七个顶点 的有向哈密尔顿路径问题( d i r e c t e dh a m i l t o np a t hp r o b l e m , d i - i p p ) 以来，有关 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 ) 马步遍历问题。文中给出了基于a d l e m a n 模型解决扩展棋盘上马步 遍历问题的d n a 算法。使用基本的“分离”操作即可解决该问题，本文使 i 太原理工人学硕上研究生学位论文 用了多级分离，旨在说明多级分离装置也可以完成基本的分离操作。 ( 2 ) 图顶点着色问题。该问题是一个典型的n p 完全问题，目前，已有 人提出了解决该问题的d n a 算法，但存在着编码方式复杂、将问题复杂化、 效率不高等问题。本文利用l i p t o n 解决可满足性( s a t i s f i a b i l i t y , s a t ) 问题 的思想，给出了解决该问题的一种粘贴d n a 算法；并引入多级分离技术加 以改进，减少了操作步骤，提高了解题效率。 ( 3 ) 地图肛着色问题。四色定理告诉我们，任意地图都可以用四种颜色 正常着色。但有些地图或许需要更少的颜色。本文将地图肛着色问题转化 为顶点着色问题进行解决。 在解决以上三个问题时，文中都给出了具体的实例，并通过模拟实验 得到了具体的解决方案，说明了算法的可行性和有效性。 关键字：d n a 计算，多级分离，粘贴模型，马步遍历，图顶点着色， 地图着色 i i 太原理工大学硕士研究生学位论文 r e s e a r c h s ；：o nm u l t i s e p a r a t i o nt e c h n i q u e s a n dd n a a l g o r i t i 皿讧so fs e v e r a i ，p r o b l e m s a b s t r a c t d n a c o m p u t i n gi s an e wc o m p u t i n gp a r a d i g m i tc o m p u t e sw i t hd n a s t r a n d s 鹊m a t e r i a l s ，a n db i o c h e m i s t r ye x p e r i m e n t sa st o o l s d n as t r a n d sh a v e h u g es t o r a g ea b i l i t y o fm e s s a g e ；a n dd n ac o m p u t i n gh a st r e m e n d o u s p a r a l l e l i s mt h a to t h e rc o m p u t i n gp a r a d i g m sc 缸n o tc a t c hu pw i t h r e s e a r c h e so nd n a c o m p u t i n gh a db e e ns p r e a do u ts i n c e1 9 9 4w h e n p r o f e s s o ra d l e m a ni ns o u t hc a l i f o r n i au n i v e r s i t ys o l v e dd i r e c t e dh a m i l t o n p a t hp r o b l e mo fag r a p hw i t hs e v e nv e r t e x e sb yb i o c h e m i s t r ye x p e r i m e n t s r e s e a r c h e r sh a dm a d eab i gp r o g r e s s ，b u tt h e o r yr e s e a r c hw a sab i gb u l l r e s e a r c h e so no p e r a t i o n sa n de x p e r i m e n te q u i p m e n t sw e r es c a r c 宅t h e r ea r e s t i l ln od n aa l g o r i t h m so fs e v e r a lc l a s s i c a l p r o b l e m s a b o u tg r a p ha n d m a t h e m a t i c s d n aa l g o r i t h m so fs o m ep r o b l e m sh a db e e ne x i s t e d ，b u ts t i l lt ob e i m p r o v e d s t i c k e rm o d e la n ds p l i c i n gm o d e la r et w oo f t h ei m p o r t a n td n a c o m p u t i n g m o d e l s p e e rc o m p u t i n gc a p a c i t yt os p l i c i n gm o d e l ，u s eo ff i x e d - l e n g t hd n a s t r a n d s ，f r e eo f e n z y m e sa n ds t r a n d se x p a n d i n g ，r e p e a t e du s eo f m a t e r i a l sc a u s e d r e s e a r c h e so ns t i c k e rm o d e lm a k i n gar a p i dp r o g r e s s ，a n dd n a a l g o r i t h m so f m a n yp r o b l e m sw e r ep r o p o s e d ，t o o b u to p e r a t i o ns t e p sw e r ee x c e s s i v e ，a n d p r e c i o u st i m ew a se x h a u s t e ds i n c eo n l yf o u rb a s i co p e r a t i o n so fs t i c k e rm o d e l w e r ea d o p t e di ne x p e r i m e n t s f o rt h er e a s o n sa b o v e ，n o to n l yt h ec o n c e p t m u l t i s e p a r a t i o n b u ta l s oam u l t i s e p a r a t i o ne q u i p m e n tm o d e lw a sp r o p o s e d m u l t i s e p a r a t i o na sw e l la sm a n yb a s i co p e r a t i o n si nd n ac o m p u t i n gc o u l db e c a r r i e do u tw i t ht h i se q u i p m e n t s o ，t h eo p e r a t i o ns t e p sw e r er e d u c e d ，a n dt h e e f f i c i e n c yw a si m p r o v e d i i i 太原理工大学硕士研究生学位论文 t h ef o l l o w i n gp r o b l e m sw e r es o l v e dw i t hm u l t i - s e p a r a t i o nt e c h n i q u e si n t h i st h e s i s ( 1 ) t h ek n i g h tt r a v e r s i n gp r o b l e m ad n a a l g o r i t h mb a s e do na d l e m a n m o d e lw a sp r o p o s e dt os o l v et h ek n i g h tt r a v e r s i n gp r o b l e mo ne x p a n d e dc h e s s b o a r d t h ep r o b l e mc o u l db es o l v e dw i t hb a s i cs e p a r a t i n go p e r a t i o n , b u t , m u l t i s e p a r a t i o nw a si n 拓o d u c e di no r d e rt oi l l u m i n a t et h a tt h em u l t i - s e p a r a t i o n c o u l dd ot h es a m ew o r k ( 2 ) t h ev e r t e xc o l o r i n gp r o b l e mo fg r a p h t h i si sac l a s s i c a ln p c o m p l e t e p r o b l e m t h o u g ht h e m w e r es e v e r a ld n a a l g o r i t h m so f t h i sp r o b l e m ，t h ec o d i n g m e t h o d si nt h e s ea l g o r i t h m sw e r ec o m p l i c a t e d ，a n dt h e s ea l g o r i t h m st h e m s e l v e s w e r ei n e f f i c i e n t u s i n gt h ei d e a lw h i c hl i p t o ns o l v e dt h es a tp r o b l e m , w e p r o p o s e dad n aa l g o r i t h mb a s e do ns t i c k e rm o d e l a ni m p r o v e da l g o r i t h mw i t h s e p a r a t i o nt e c h n i q u e sw a sg i v e nt or e d u c et h eo p e r a t i o ng e p s f i n a l l y , t h e e f f i c i e n c yw a si m p r o v e d ( 3 ) t h ek - c o l o r i n gp r o b l e mo fm a p t h ef o u r - c o l o rt h e o r yt o l du st h a ta n y m a pc o u l db ec o l o r e dn o r m a l l yw i 吐lf o u rk i n d so fc o l o r s b u tt w oo rt h r e ek i n d s o fc o l o r sw o u l dd ot os o m es p e c i f i cm a p s t h em a pc o l o r i n gp r o b l e mw a s s o l v e di nt h ew a yo f t r a n s f o r m i n gi ti n t ot h ev e r t e xc o l o r i n gp r o b l e mo f g r a p h i n s t a n c e sw e r eg i v e nt os o l v et h et h r e ep r o b l e m sa b o v e a n dt h es o l u t i o n s w e r eg o tb ys i m u l a t i n ge x p e r i m e n m s o ，t h ef e a s i b i l i t ya n dv a l i d i t yo ft h e s e a l g o r i t h m sw e r ep r o v e d k e yw o r d s ：d n ac o m p u t i n g ，m u l t i - s e p a r a t i o n ，s t i c k e rm o d e l ，k n i g h t t r a v e r s i n g ，v e r t e xc o l o r i n g ，m a pc o l o r i n g i v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外。本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 4 d 壹 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管，使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的。 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 签名： 导师签名： 日期：丝兰z ：三兰蒸 太原理工大学硕士研究生学位论文 1 1d n a 计算概述 第一章绪论 自从第一台电子计算机问世，传统计算机的发展始终遵从着摩尔定律，即单位平方 英寸的晶体管数目每经过一年半到两年就增加一倍。但是晶体管尺寸很快就会达到由其 制造工艺所决定的o 0 8 m 这一极限值。而且，诸多n p 完全问题、n p 难问题在传统计 算机上没有一个多项式时间复杂度的算法，人们只能靠牺牲精度的办法近似计算。基于 上述原因，人们努力探索新的计算模型【1 】使其在计算速度上与晶体管计算机相比能有 质的飞跃，d n a 计算就是其中的代表。 传统的计算机是用0 和l 进行编码的，而d n a 计算可以用组成d n a 分子的4 个 字母的集合z = a ，g ，c ，t 来编码各类信息。酶可看作在d n a 序列上简单的计算， 不同的酶相当于作用在d n a 串上的不同的算子，如限制性内核酸内切酶( r e s l r i c t i o n e n d o n u e l e a s e ) 口- 作为分离算子；链接酶( 1 i g a s e ) 口- i 作为链接算子，聚合酶( p o l y m e r a s e s ) 可 作为复制算子，外核酸酶( e x o n u c l e a ) 可作为删除算子等即1 。 d n a 计算的基本思想是【2 】【4 】：利用d n a 分子的双螺旋结构和碱基互补配对的性质， 将所要处理的问题编码成特定的d n a 分子，在生物酶的作用下，生成初始数据池( d a t a p 0 0 1 ) ，即：问题的可能解；然后利用现代分子生物技术如聚合酶链反应( p o l y m e r i z ec h a i n r e a c t i o n , p c r ) 、聚合重叠放大技术( p a r a l l e lo v e r l a pa s s e m b l y ，p o a ) 、超声波降解、亲和 层析、分子纯化、电泳、磁珠分离等手段破获运算结果；最后通过测序或其他方法解读 计算结果。 与传统的晶体管计算机相比，d n a 计算有着如下优点f 2 】【4 j ： ( 1 ) 高度并行性：由于用d n a 计算有着高度的并行性，使得其一周内的运算总 量相当于所有电子计算机闯世以来的计算总量。 ( 2 ) 巨大的信息存储容量：d n a 作为信息载体，其存储容量非常之大，每立方 米的d n a 溶液可以存储1 0 2 0 个二进制数据，远远超过目前所有电子计算机 的总存储量。 太原珏工人学硕士研究生学位论文 ( 3 ) 低能耗：d n a 计算所耗的能量只有一台传统计算机完成同样的计算量所耗 能量的十亿分之一。 ( 4 ) 丰富的d n a 分子资源：现在从动植物的体内( 活体和死体) 提取d n a 的 技术已相当成熟，而自然界的物种具有多样性，不同物种之间、以及同种物 种的不同个体其d n a 都是不同的。 上述优点使得有望用d n a 计算的方法解决目前许多传统计算机无法解决的问题， 譬如：密码破解问题、n p 完全问题、n p 一难问题等等；同时，也使得在世界范围内掀起 了研究d n a 计算的热潮。自1 9 9 4 年美国南加利福尼亚大学的a d l e m a n 教授用d n a 解 决了一个七节点的有向哈密尔顿路径问尉习以来，世界各国的很多学者致力于这方面的 研究，虽然已经取得了可喜的成就，但依然存在着诸如编码问题、“指数”爆炸问题、 生化操作误差等问题。因此，提出一个新的高效的算法或是对已有的编码方式或算法进 行改进，减小编码与运算的复杂度、提高运算效率都将对这一学科的发展有着重要的意 义。 1 2 d n a 计算的研究现状 1 9 9 4 年，l m a d l e m a n 在s c i e n c a 上发表了首篇关于d n a 计算的文章，介绍了用 生物化学实验的方法解决图论中h a m i l t o n 路径问题的方法，开创了d n a 计算的先河。 时隔一年的时间，普林斯顿大学的l i p t o n 发明了一种新的d n a 编码方案，可以将d n a 编码翻译成0 、l 串，他提出了用于求解s a t 问题的计算模型嘲。2 0 0 1 年，以色列科学 家e s h a p i r o 领导的研究小组在n a t u r e 杂志上发表了他们的研究成果【7 l 利用d n a 分子和d n a 限制性内切酶实现了一种具有简化图灵机功能的可编程自动d n a 分子计 算机模型，在生物计算机的研究上取得了重大突破。 2 0 0 2 年生物计算机方面最突出的进展是美国的a d l e m a n 研究小组用d n a 计算机求 解了一个包含2 0 个逻辑变量、2 4 个子句且只有一组解的s a t 问题1 8 i 。同年，奥林巴斯 光学公司与东京大学联合研制成功一台有商业化可能的d n a 计算机。 d n a 计算国际会议( h t e m a t i o n a lm e e t i n go nd n a c o m p u t i n g ) 自1 9 9 5 年在普林斯 顿举办第一届以来，已经举办了1 2 届，2 0 0 6 年第十二届会议在韩国汉城大学举行：2 0 0 7 年将在美国孟菲斯举行第1 3 届d n a 计算国际会议。 2 太原理工大学硕士研究生学位论文 目前，国外在d n a 计算方面研究比较活跃的有美国、加拿大、英国、日本、德国、 以色列等国家的一些高校和大公司。计算模型与算法的实现仍然是研究的热点。 国内在这方面的研究自1 9 9 9 年开始，主要研究基地是华中科技大学许进教授领导 的d n a 计算和分子计算机系统工程研究所和东华大学信息科学与技术学院丁永生教授 领导的研究小组。许进教授主要进行了图论与组合优化的d n a 计算模型方面的研究； 丁永生教授就d n a 计算与软计算的结合进行了深入的研究。此外在这方面展开研究的 还有西安交通大学、上海交通大学、复旦大学、浙江大学、南京大学、吉林大学、北京 工业大学等，2 0 0 6 年，山东大学申请到了d n a 数据挖掘方向的国家自然科学基金，开 始了在这一方向的研究。 特别值得一提的是，上海交通大学生命科学研究中心与中科院上海生命科学院营养 科学研究所最近研究出了d n a 计算机的试管雏形，这在国内乃属首次。 会议方面，由北京大学、郑州轻工业学院、华中科技大学承办的第二届“生物计算 理论及应用国际会议”将于2 0 0 7 年9 月1 4 日1 7 日在郑州举行。 近几年，国内的研究成果主要有：2 0 0 4 年，华中科技大学的王淑栋等提出了图的最 小顶点覆盖问题的质粒d n a 计算模型 9 1 ；2 0 0 5 年，董亚非等对r o w e i s 的s a t 问题的 试管解决方案及高琳等基于表面粘贴模型而设计的解决图的最小顶点覆盖问题的算法 【1 0 1 进行了改进【1 ”，并解决t s p 问题【1 2 】；2 0 0 5 年，许进领导的研究小组将分子信标方法 应用于解决n p 完全问题 1 3 - 1 4 】；北京工业大学进行了用d n a 计算的方法进行解密的探 索；2 0 0 5 年，复旦大学的曲惠琴博士提出将参数算法应用于d n a 计算【1 5 】等等。 总的说来，目前d n a 计算研究所涉及的主要方向有：d n a 计算的模型峋，编码方 式f 1 7 。”1 ，d n a 加密技术“9 - 2 0 ，用d n a 计算方法解决图论及数学难题的算法【2 1 粕l ，d n a 计算与遗传算法、神经网络等智能计算方法的结合【2 5 - 2 6 ，d n a 数据挖掘技术 2 7 。2 8 1 等等。 有关d n a 计算与d n a 计算机的研究偏向于理论，对于实验操作以及实验装置的研究 很少。 1 3 本文的内容 本文研究了d n a 计算在图论及组合优化中若干问题上的应用，引入了多级分离技 术，设计了一个多级分离装置的模型，并使用该装置模型解决某些问题。 3 太原理工人学硕士研究生学位论文 第一章绪论，简要概述了d n a 计算的产生、基本原理，d n a 计算的优势，国内 外的研究现状；介绍了本文的主要内容、创新之处。 第二章d n a 计算的生物工具，简要介绍了d n a 的分子结构，建立在d n a 分子上 的基本生物化学操作等等。 第三章基于粘贴模型的多级分离技术，第一节介绍了粘贴模型的发展状况、编码 方式、粘贴模型的四种基本操作及其物理实现；第二节介绍了多级分离的概念、多级分 离装置模型的各个组成部分、以及利用多级分离装雹所能执行的操作。 第四章基于a d l e m a n 模型求解马步遍历问题，首先简述了马步遍历问题，对该问 题进行了扩展；简要介绍了a d l e m a n 模型，依据该模型给出了扩展棋盘上的马步遍历问 题的d n a 算法；对一个简单的实例进行了模拟，得出了遍历路径。 第五章基于粘贴模型的图顶点着色问题的d n a 算法，首先给出了图顶点着色问题 的一般描述；第二节综述了图顶点着色问题d n a 计算方法的研究现状；第三节将图的 顶点着色问题转化为可满足性闯题；第四节给出了解决该问题的一种算法一 c _ w a p h c o l o r i n g 算法，给出了实验步骤，并用实例模拟了该算法：第四节引入多级分离 技术对g r a p h c o l o r i n g 算法加以改进，并将其与改进前的算法进行了比较。 第六章地图七_ 着色问题的d n a 算法，第一节简单介绍了地图矗着色问题；第二节 将该问题转化为图的顶点着色问题；第三节给出了该问题的一般解决方案：第四节以山 西地图的地区着色问题为例，给出了实验操作方案，并进行了模拟，得出了具体的着色 方案。 第七章总结和展望，对全文加以总结，并简述了下一步要做的工作。 1 4 本文创新之处 1 本文提出了多级分离技术，并设计出了一个多级分离装置的模型。 2 给出了扩展棋盘上的马步遍历问题的一种d n a 计算方法。 ，3 给出了解决图顶点着色问题的一种d n a 粘贴算法，并引入多级分离技术改进了 算法，减少了操作步骤，提高了解题效率。 4 将地图缸着色问题最终转化为s a = r 问题进行解决。 4 太原理工大学硕士研究生学位论文 2 1 d n a 的结构 第二章d n a 计算的生物工具 生物的性状之所以能够得以遗传和延续，是因为生物体内含有一种高分子化合物一 d n a 。d n a 分子内含有控制物种遗传的所有性状信息。脱氧核糖核苷酸是构造d n a 单体的基本单位，一个分子的脱氧核苷酸由一分子脱氧核糖、一分子磷酸和一分子的含 氮碱基组成。 组成脱氧核苷酸的脱氧核糖是一个戊糖，它含有五个碳原子。为了区别于碱基的碳 原子，脱氧核糖的五个碳原子分另用1 、2 、37 、4 、5 编号，羟基与3 碳原 予相连。其中，磷酸基与57 碳原子相连，碱基与l 碳原子相连。d n a 分子含有四种 不同的碱基，即腺嘌呤( a d e n i n e ，a ) 、鸟嘌呤( g u a n i n e ，g ) 、胞嘧啶( c y t o s i n e ，c ) 、胸 腺嘧啶( t h y m i n e ，t ) ，这四种碱基的分子结构如图2 1 所示 2 9 1 。根据所含碱基类型的不 同，核苷酸可分为a 核苷酸、g - 核苷酸、c 核苷酸和r - 核苷酸。 期o a d e n i n ec m l l i n c 砖o c y t o s i n e t h y m i n e 图2 - 1 碱基的分子结构 f i g u r e2 - 1t h em o l e c u l es l x u c t u l - eo f b a s e s 一个核苷酸的5 磷酸基和另一个核苷酸的3 羟基相连，形成磷酸二脂键，该键 是一个强共价键，从而使形成的分子具有方向性，通常称之为5 3 方向或3 5 ， 方向，这种方向性是理解d n a 功能和建立模型的关键。 5 太原理工大学硕士研究生学位沈文 1 9 5 3 年，j a m e sw a g o n 和f r a n c i sc r i c k 推断出了d n a 分子的双螺旋结构。这种双 螺旋结构的形成是由于四种碱基遵循着w a t s o n c r i c k 碱基互补原则口9 】：a 和t 互补，c 和g 互补( 如图2 - 2 所示) 。 a ：t g ：c 图2 - 2 d n a 碱基对 f i g u r e2 - 2t h ed n ab a s ep a i r s w a t s o n - c r i c k 碱基互补原则使得互补的两条d n a 单链分子螺旋缠绕在一起，形成 了著名的双螺旋结构。例如d n a 单链5 - a g c t c a g g 3 和3 t c g a g t c c 5 的 各个碱基互相配对，形成图2 3 所示的双螺旋结构1 2 9 1 。 图2 - 3 d n a 的双螺旋结构 f i g u r e2 - 3t h es l x u c t u r eo f d n a d o u b l eh e l i x 2 2d n a 分子的生物操作叫2 】 2 2 1 合成( s y n t h e s i s ) 特定d n a 分子的合成可以在合成器( s y n t l l e s i z e r ) 里进行。以a 、c 、g 、t 四种碱基 为原料，在合成时从d n a 分子的3 端开始，以输入的d n a 单链为母链逐步合成所需 要的d n a 链。 6 太原理工人学硕士研究生学位论文 这种合成方法比较简单，适用于合成长度比较短( 一般为2 0 个碱基以内) 的d n a 链； 由于用合成器直接合成较长的d n a 分子链容易发生断链现象，所以经常采用分段合成 的办法。 2 2 2 变性( d e n a t u r a t i o n ) 与复i 生( r e n a t u r a t i o n ) 变性，又叫熔解( m e l t i n g ) ，d n a 双链加热到一定的湿度可以熔解为两条互补的 d n a 单链，解链的温度由构成d n a 分子的碱基对决定。由于双链中的氢键远比共价键 弱得多，所以加热将首先破坏d n a 双链中的氢键，从而可以得到d n a 单链。由图2 - 2 得知，a t 碱基对含有两个氢键，c g 碱基对含有三个氢键，所以破坏c g 碱基对需要 的温度比破坏a 刀碱基对的温度较高，这就导致了d n a 双链的解链温度随d n a 双链 分子的结构不同而不同。 复性，又叫杂交( h y b r i d i z a t i o n ) 、退火或熔合( a n n e a l i n g ) ，是变性的逆过程。通 过加热解链的d n a 双链溶液逐渐冷却，熔解得到的两条互补的d n a 单链将根据 w a t s o n - c r i c k 互补原则，重新熔合为一条具有双螺旋结构d n a 双链。 2 2 3 抽取( e x t r a c t i o n ) 与合并( u n i o n m e r g e ) 抽取，又叫按子串分离( s e p a r a t i o n b y h y b r i d i z a t i o n ) ，根据是否含有子串x ，将d n a 溶液分别装入两个试管t i 和t 2 ，其中试管t 1 中的d n a 链都含有子串x ，而试管t 1 中 的d n a 链都不包含子串x 。这一操作可以使用磁珠技术完成，相关技术将在本文第三 章详细介绍。 合并，对于盛有d n a 溶液的r 1 个试管t 卜t 2 、l ，将所有试管中的溶液倒 入一个试管中t 中，那么t 中包含原来n 个试管中的所有d n a 链。 2 2 4 连接( l i g a t i o n ) 连接，是指d n a 分子通过连接反应结合在一起，连接反应是在连接酶的催化作用 下进行的。 具有粘性末端的不完全双链分子在连接酶的作用下，根据w a t s o n - c r i c k 碱基互补配 对原则可以粘贴在一起。如图2 4 所示，不完全双链分子h l 、h 2 在d n a 连接酶的作用 下连接在一起，形成具有螺旋结构的d n a 双链。 7 太原理工大学硕士研究生学位论文 h i 坞 o 一酶 5 c a c c t g a g t g 3 3 g t g g a c r c a c 5 图2 - 4 d n a 粘性端的连接 f i g u r e2 - 4l i g a t i n go f d n as t i c k ye n d s 在本文中，最常用的是d n a 单链的连接，两条并不互补的d n a 单链分子s l 、s 2 在连接酶的作用下，通过粘贴链( g l u es t r a n d ) s 3 连接在一起。d n a 单链分子s l 的尾部 的碱基与粘贴链s 3 的前半段的碱基满足w a t s o n c r i c k 碱基互补原则，而s 2 的首部的碱 基与s 3 的后半段的碱基互补。设s 1 、s 2 分别表示d n a 单链分子3 7 - g a c c t b u 屺g c c c 气a - 5 和3 - g c c a c t f a a c c g c a t - 5 ，s 3 表示3 7 一g g g t t c g g t g - 5 。首先，s 3 将与s l 尾部的五个碱基以及s 2 首部的五个碱基通过碱 基互补原则结合在一起；然后在连接酶的作用下，s l 和s 2 连接成一条d n a 链。( 如图 2 5 所示) 3 - g a c c t g a a c g c c c a a - 5 s i 3 g g g 兀g ( 玎b5 s ， 3 g c c a i ：1 r a a c c g c a t - 5 s 2 3 t - g a c c r g a a c g c c c g c c a c t t a a c c g c k e 3 - g g g t c g g t g - 5 d 1 帆连接酶 3 - g a c c t g a a c g c c c a a g c c a c t r a a c c g c a t - 5 3 - g g g 订c g g t g - 5 7 图2 - 5 d n a 单链的连接 f i g u r e2 - 5l i g a t i n go f s i n g l ed n am a n d s 8 太原理工大学硕士研究生学位论文 2 2 5 凝胶电泳( g e l e l e c t r o p h o r e s i s ) 凝胶电泳，又叫按长度分离( s e p a r a t i o nb yl e n g t h ) ，是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 分子在凝胶中运动速度较快。经过一段时 间焐，在凝胶中将按照d n a 分子的长度形成一条条d n a 凝胶带，距离正极较近的凝 胶带为比较短的d n a 分子，越靠近负极的d n a 分子就越长。凝胶电泳的过程如图2 - 6 所示。 卜 d n a 分子由大到小 图2 - 6 凝胶电泳过程 f i g u r e2 - 6g e l - e l e c n , o p h o m s i sp r o c e s s 9 太原理工人中顶士研究生学位论文 最后，可以通过荧光染色技术来标识各条d n a 凝胶带，通过紫外线观察。 2 2 6 聚合酶链接反应( p o l y m e r a s ec h a i nr e a c t i o n ，p c r ) p c r 是诺贝尔化学奖获得者m u l l i s 于1 9 8 5 年发明的具有划时代意义的技术，它能 使d n a 扩增量呈指数级增加。p c r 由变性、复性和延伸三个基本步骤循环构成。( 如 图2 7 所示) 模板：3 5 3 5 3 兰兰 ii x y z 0 变性解链 u x y z i i 引物：5 = 一3 5 3 5 3 5 引铷3 商 x y z 图2 - 6 p c r 的三个步骤 f i g u r e2 - 6t h et h r e es t e p so f p c r 1 0 5 3 5 3 5 7 5 3 太原理工大学硕士研究生学位论文 1 模板d n a 的变性：模板d n a 经加热至9 3 c 左右一定时间后，使模板d n a 双 链或经p c r 扩增形成的双链d n a 熔解为单链，使之与引物结合，为下一轮的反应做准 备。 2 模板d n a 与引物的复性：模板d n a 经加热交性熔解为单链后，温度降至5 5 ( 2 左右，引物与模板d n a 单链的互补序列按照w a t s o n - c r i c k 碱基互补原则配对结合，熔 合为d n a 不完全双链。 3 引物的延伸：d n a 模板和引物的结合物在t a q d n a 聚合酶的作用下，按碱基配 对原则，合成一条新的与模板d n a 链互补的复制链。 重复循环以上三个基本过程，就可获得更多的复制链，这种复制链可作为下次循环 的模扳。每完成一个循环需2 4 分钟，2 3 小时就能将待扩增的d n a 分子扩增几百 万倍。 2 2 7 切割( c u t ) 切割，分为内切和外切，是利用特定的核酸内切酶( e n d o n u c l e a s e s ) 和核酸外切酶 ( e x o n u e l e a s e s ) 将d n a 链切割缩短的技术。 利用特定的内切酶可以在d n a 单链或双链的任意位置进行切割，而外切酶是通过 每次从d n a 分子的末端去掉一个核苷酸进行切割。 2 2 8 检测( d e t c c i i o n ) 检测是指测定在给定的试管中是否含有d n a 分子链，若试管中至少包含一条d n a 链，结果为“是”，否则为“否”。 除上述常用的基本操作之外，针对d n a 分子的操作还有修复、提纯、标识、破坏、 插入、替换等等，有关这些操作的实现方式，本文将不再赘述。 ” 2 3 本章小结 本章介绍了组成d n a 分子的四种碱基的分子结构，以及它们之间的互补配对原则 m t s o n c r i c k 碱基互补配对原则，即a 矗配对、c g 配对；a 玎碱基对之间有两个 氢键，c g 之间有三个氢键。由于碱基互补原则的存在，导致了d n a 双链分子是两条 互相盘绕的双螺旋结构。 1 1 太原理工人学硕士研究生学位论文 基于d n a 分子的一系列的基本生化操作是用d n a 进行计算的基本工具，其中最 重要的是凝胶电泳技术和聚合酶链接反应，本章对这些基本操作逐一加以介绍，这对理 解以下各章节是不无裨益的。 1 2 太原理工大学硕士研究生学位论文 3 1 粘贴模型 第三章基于粘贴模型的多级分离技术 计算模型的研究一直是d n a 计算领域的研究热点之一，至今已有不少的计算模型 被提出，其中，近几年的研究热门是剪接模型( s p l i c i n g m o d e l ) 和粘贴模型( s t i c k e r m o d e l ) 3 3 - 3 6 。剪接系统模型主要基于剪接操作，剪接系统模型具有完备性d o 】，2 0 0 1 年底，一 个基于剪接系统的可编程有穷自动机已经得以实现。 粘贴模型是r o w e i s 等人于1 9 9 6 年首次提出的d n a 计算模型，是近几年的研究中 备受关注的计算模型，它是一种基于分子操作和随机访问内存的一种d n a 计算模型， 是一种通用的计算机系统【3 3 1 。该模型有着与剪接模型同样的计算能力，而且具有不需要 延伸d n a 分子链、不需要酶的参与以及材料可以重复利用等优点【3 5 1 。目前，研究者们 基于粘贴模型已经解决了不少n p 类问题。例如：3 可满足性( 3 s a f i s f i a b i l i t y ，3 - s a t ) 问尉8 】口4 1 、旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 【1 2 】l ，k - 团与k - 独立集f 咂i 3 e 等。 基于粘贴模型的计算模式就是将问题的所有可能解用位串来编码，得到一个“初始 数据池”，对该数据池中的位串通过粘贴模型的四种基本操作中的某一种或者几种操作， 筛选出结果串。如果结果串为空，则表明问题无解。 3 1 1 粘贴模型的编码方式 在粘贴模型中，用单、双链d n a 分子编码，分别对应于传统计算机的0 和1 。粘贴 模型的存储区存放着由存储链和粘贴链组成的存储合成物( m e m o r yc o m p l e x ) 。存储链是 一个由刀个不重叠子链组成的单链d n a 分子，每个子链包含朋个碱基，所以每个存储 链的长度l = m * n 个碱基。粘贴链也由r a 个碱基构成，而且每个粘贴链均与存储链中的 某一个子链满足w a t s o n - c r i c k 互补关系阅。当一个存储合成物中的某一位元为单链时表 示0 ，为双链时表示1 。例如：子链数为4 ，子链长度为5 个碱基的位串： a t t a cc g t a ac g g t ta g g c t g c a t tg c c a a 对应的二进制串是：0 1 1 0 。 1 3 太原理工人产硕一 ：研究生学位论文 3 1 2 粘贴模型的基本操作 粘贴模型在位串上定义了四种基本操作：合并，分离、设置和清除f 3 5 】。 合并( m e r g