（计算机应用技术专业论文）dna计算及其算法优化.pdf

太原理工大学硕士研究生学位论文 d n a 计算及其算法优化 摘要 在计算机中，利用有机分子的信息处理能力来代替数字开关部件， 这就是d n a 计算的基本思想。以当前的计算机技术要实现微型化存在明 显的局限性，所以要进行大的革新，很早以前就有人提出现代计算机的 基本部件应逐步过渡到分子水平，这样一来，它将会比我们利用当前技 术制造出的任何东西都要小得多，量子计算和d n a 计算是当前这种思想 的两种不同表现，本论文主要介绍d n a 计算。d n a 计算主要基于以下两点： ( 1 ) d n a 链的巨大并行性；( 2 ) w a t s o n c r i c k 的互补结构。传统理论上 的计算机科学植根于重复写操作，这对于大部分自动机械装置和语言理 论模型是正确的，然而，在计算行为中，自然界操作d n a 分子利用的是 完全不同的操作类型：剪切、粘贴、连接、插入、删除等。可以证明， 利用这些操作可以建立计算模型，并且在功能上等价于图灵机。 以前d n a 计算的研究主要集中在一些组合问题上，像h a m i l t o n i a n 路径问题、旅行商问题、3 - s a t 问题，甚至破解d e s 密码等等，但提出的 上述所有问题的d n a 算法基本上都是蛮力搜索，初始化时生成问题的所 有可能的解决方案，然后根据条件消除掉不正确的答案，最后剩下的方 案即是问题的正确答案。 但值得注意的是，实际问题的正确答案也许会在计算过程中被破坏 掉，最后得到的答案也许是一个错误的答案。为了避免这种错误，我们 提出了将启发式优化算法和d n a 计算结合，采用新的手段来设计算法。 在这篇论文中，我们将蚁群优化算法和d n a 计算结合，来解决旅行商问 题。即使正确的答案在处理的过程中被破坏掉，该正确答案在以后的处 理过程总还会被构造，在过滤掉不合适的答案以后，我们利用控制变性 i 太原理工大学硕士研究生学位论文 温度的方法按比例放大经过过滤剩下的序列，并把放大的结果作为下次 迭代的输入，相应的代表正确答案的d n a 序列的浓度就会增加。在经过 多次迭代之后，若结果趋于稳定，则认为剩下的序列即为问题的答案。 论文的前两部分主要介绍生物学的基础知识、d n a 计算的基本概念、 基本模型和相关的著名实验，接下来介绍了启发式优化算法：蚁群优化 算法；然后提出蚁群优化算法和d n a 计算结合的构想与具体实现，同时 详细介绍了算法处理过程；在文章的最后对提出的算法进行了总结，并对 d n a 计算的前景进行了展望。 关键词：d n a 计算，启发式优化方法，n p 完全问题，序列抽取 i i 太原理工大学硕士研究生学位论文 d n ac o m 口u t i n ga n do p t i z a t i o no ft h e a l g o r i t h m a b s t r a c t i n f o r m a t i o n - p r o c e s s i n gc a p a b i l i t i e so fo r g a n i cm o l e c u l e sc a l lb eu s e di n c o m p u t e r st or e p l a c ed i g i t a ls w i t c h e s ；t h i si st h eb a s i ci d e ai nd n ac o m p u t i n g t h e r ea r eo b v i o u sl i m i t st om i n i a t u r i z a t i o nw i t hc u r r e n t c o m p u t e r t e c h n o l o g i e s f o rad r a s t i ci n n o v a t i o n ，i tw a ss u g g e s t e da l r e a d yal o n gt i m e a g ot h a tt h eb a s i cc o m p o n e n t ss h o u l dg ot ot h em o l e c u l a rl e v e l t h er e s u l t w o u l db em u c hs m a l l e rt h a na n y t h i n gw ec a nm a k ew i t hp r e s e n tt e c h n o l o g y q u a n t u mc o m p u t i n ga n dd n ac o m p u t i n ga r et w or e c e n tm a n i f e s t a t i o n so f t h i ss u g g e s t i o n t h i sw o r ki s * b o u tt h el a t t e r d n ac o m p u t i n ga r eb a s e do nt w o f u n d a m e n t a lf e a t u r e s ：( 1 ) t h em a s s i v ep a r a l l e l i s mo fd n as t r a n d s ；( 2 ) w a t s o n - c r i c kc o m p l e m e n t a r i t y c l a s s i ct h e o r e t i c a l c o m p u t e rs c i e n c e i s g r o u n d e do nr e w r i t i n go p e r a t i o n s ；t h i si st m e f o rm o s ta u t o m a t aa n dl a n g u a g e t h e o r ym o d e l s a sw es h a l ls e e ，n a t u r em a n i p u l a t e st h ed n a m o l e c u l e si na c o m p u t i n gm a n n e rb yu s i n go p e r a t i o n so faq u i t ed i f f e r e n tt y p e ：c u ta n dp a s t e ， a d j o i n i n g ，i n s e r t i o n ，d e l e t i o n ，e t c i th a sb e e np r o v e dt h a tb yu s i n gs u c h o p e r a t i o n sw ec a nb u i l dc o m p u t i n gm o d e l st h a ta r ee q u i v a l e n ti np o w e rw i t h t u r i n gm a c h i n e s p r e v i o u sr e s e a r c ho nd n a c o m p u t i n gh a ss h o w nt h a td n aa l g o r i t h m s a r eu s e f u lt os o l v es o m ec o m b i n a t o r i a lp r o b l e m s ，s u c ha st h eh a m i l t o n i a n p a t hp r o b l e m ，t r a v e l i n gs a l e s m a np r o b l e m ，3 - s a tp r o b l e m ，b r e a k i n gt h ed e s i l l 太原理工大学硕士研究生学位论文 c o d ea n ds oo n t h eb a s i cc o n c e p ti m p l i c i ti np r e v i o u sd n a a l g o r i t h m si st h e b r u t ef o r c em e t h o d t h a ti s a l lp o s s i b l es o l u t i o n sa r ec r e a t e di n i t i a l l y , t h e n i n a p p r o p r i a t es o l u t i o n sa r ee l i m i n a t e d ，a n df i n a l l yt h er e m a i n i n gs o l u t i o n sa r e c o r r e c to rt h eb e s to n e s h o w e v e r ，c o r r e c ts o l u t i o n sm a yb ed e s t r o y e dw h i l et h ep r o c e d u r ei s e x e c u t e d i no r d e rt oa v o i ds u c ha ne r r o r w er e c o m m e n dc o m b i n i n gt h e c o n v e n t i o n a lc o n c e p t so fd n ac o m p u t i n gw i t hah e u r i s t i c o p t i m i z a t i o n m e t h o da n da p p l yt h en e wa p p r o a c ht od e s i g ns t r a t e g i e s i nt h i st h e s i s ，w e p r e s e n tad n aa l g o r i t h mb a s e do na n tc o l o n yo p t i m i z a t i o n ( a c o ) f o rs o l v i n g t h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) o u rm e t h o dm a n i p u l a t e sd n a s t r a n d s o fc a n d i d a t es o l u t i o n si n i t i a l l y e v e ni ft h ec o r r e c ts o l u t i o n sa r ed e s t r o y e d d u r i n g t h ep r o c e s so ff i l t e r i n g o u t ，t h er e m a i n i n gs o l u t i o n sc a nb e r e c o n s t r u c t e da n dc o r r e c ts o l u t i o n sc a l lb er e f o r m e d a f t e r f i l t e r i n g o u t i n a p p r o p r i a t es o l u t i o n s ，w ee m p l o yc o n t r o lo fm e l t i n gt e m p e r a t u r et oa m p l i f y t h es u r v i v i n gd n a s t r i n g sp r o p o r t i o n a l l y t h ep r o d u c ti su s e da st h ei n p u ta n d t h ei t e r a t i o ni s p e r f o r m e dr e p e a t e d l y a c c o r d i n g l y , t h ec o n c e n t r a t i o no f c o r r e c ts o l u t i o n sw i l lb ei n c r e a s e d i f t h er e s u l t st e n dt ob es t a b l ea f t e rs e v e r a l i t e r a t i o n s ，t h a tw ed e c i d et h a tt h es o l u t i o n sr e m a i n e di st h ea n s w e r st h a tw e w a n t i nt h i st h e s i s ，f i r s to fa l l ，ii n t r o d u c et h eb a s i cc o n c e p t i o no fb i o l o g ya n d d n ac o m p u t i n g ，a n db a s i cm o d e l sa n df a m o u s e x p e r i m e n t s ，a n dt h e n i n t r o d u c et h eh e u r i s t i c o p t i m i z a t i o nm e t h o d ：a n tc o l o n yo p t i m i z a t i o n a l g o r i t h m s ；ig i v et h ed e t a i l so f t h ed n aa l g o r i t h mb a s e do na c oi nt h en e x t c h a p t e r t h el a s tp a r ti st h ec o n c l u s i o n k e yw o r d s ：d n a c o m p u t i n g ，h e u r i s t i co p t i m i z a t i o nm e t h o d ，n pc o m p l e t e p r o b l e m s ，s e q u e n c ee x t r a c t i n g i v 声明尸 h 月 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：王邋国日期： 2 g ，上 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容【保密学位论文在解密后遵守此规定) o 签名：三越因日期：2 鲤堑：篁。兰垒 导师签名：金堡函 日期：窒塑乡苎：垫 太原理工大学硕士研究生学位论文 第一章介绍 1 9 9 4 年，a d l e m a n 在( s c i e n c e 发表文章，首次提出了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 ) 分子和分子生物试验技术 成功地解决了含有7 个节点的h a m i l t o n 路径问题：同时他还指出了d n a 计算潜在的 并行性及有待解决的问题。1 9 9 5 年，l i p t o n 也在 s c i e n c e ) 上发表文章。”，进一步 论证d n a 计算可解决n p 完全问题。自此以后的l o 多年时间里，很多不同学术背景的 专家学者进入这一领域并做了大量的研究工作，国际上从1 9 9 5 年开始，每年举行一 次关于d n a 计算的会议，分享该领域的研究成果。 1 1 生物基础知识及d n a 计算的过程 在由聚合物与单体等大分子和小分子组成的生物世界里，d n a 是一种由许多单体 牢固地连接在一起的聚合物，是在活性细胞中起决定作用的分子。d n a 具有令人惊奇 的结构，这种结构决定了d n a 的两种最重要的功能：蛋白质的编码和自复制。d n a 携 带遗传信息，能转录成r n a ，r n a 再转译成蛋白质；d n a 还能以自身作为模板，复制 出另一个相同的d n a 。 1 9 5 3 年，j a m e sw a t s o n 和f r a n c i sc r i c k 发现了d n a 分子的双螺旋结构。1 ，其结 构如图卜1 所示。 图卜1d n a 分子的双螺旋结构 f i g 1 - 1 d o u b l eh e l i xs t r u c t u r eo f d n a 由于构造d n a 的单体是脱氧核糖核苷酸，每个核苷酸由三部分组成：戊糖、磷酸 基和含氮的碱基。这里的戊糖是指脱氧戊糖，每个戊糖上有五个碳原子，如图卜3 ， 而每个碱基上也有碳原子，为了避免混淆，戊糖上的碳原子用l 5 进行编号，磷酸 基与5 碳原子链接，碱基与1 碳原子链接，羟基连接在3 碳原子上。 d n a 分子含有2 条多核苷酸长链，多核苷酸长链是通过一个核苷酸的5 。磷酸基 与另一个核苷酸3 ，- 羟基相连，形成的磷酸二酯键，磷酸二脂键是强键；两条多核苷 酸长链之间通过碱基上的羟基相连，两羟基形成较弱的氢键，如图卜2 所示。利用磷 酸二酯键可以合成单链d n a ，利用氢键可以形成双链d n a 分子。 太原理工大学硕士研究生学位论文 截车章 贸母_ 图卜2d n 分子的构成 f i g 1 2c o m p o n e n t so f d n a m o l e c u l e d n a 分子中的碱基有两种类型：嘌呤和嘧啶。嘌呤分为腺嘌呤( a ) 、鸟嘌呤( g ) ： 嘧啶分为胞嘧啶( c ) 、胸腺嘧啶( t ) 。氢键的形成遵从a 与t ，g 与c 配对原则( 即 w a t s o n - c r i c k 配对) ，其中a 、t 之间通过2 个氢键相连，g 、c 之间通过3 个氢键相 连。因此，g 、c 配对比a 、t 配对的连接更牢固，需要更多的能量才能分解g 、c 碱 基配对。两条单链d n a 通过上述配对原则形成双螺旋结构，其中一条从3 端到5 端， 另一条则方向相反。d n a 链的方向性如图卜3 所示。 图卜3 单链d n a 分子的方向性 f i g l - 3 t h ed i r e c t i o no f s i n g l es t r a n dd n a d n a 作为遗传信息的载体，在转录、复制、信息的存储与处理等诸多方面与图灵 机模型有相似之处。图灵机模型处理和存储信息是以序列或者符号列表的形式，这与 生物学的工作机制非常相似。1 ，单链d n a 可以看作由a 、c 、g 、t 四种不同的符号组 成的串，d n a 的转录、复制、信息的存储和处理其实就是对这4 种不同符号的处理， 这就像电子计算机内部对“0 ”和“1 ”的处理一样。在d n a 序列上可以执行一些简单 2 太原理工大学硕士研究生学位论文 的操作，这些操作是通过大量能处理一些基本任务的酶来完成“1 ，如：h a e i i i 限制内 切酶可以将双螺旋d n a 片断“c c g g ”从中间切断；d n a 聚合酶可以延长d n a 。 d n a 链在生化反应中的巨大并行性和d n a 链的碱基互补配对原则是d n a 计算的两 大基石“1 。目前d n a 计算解决的几类n p 完全问题”1 及破解d e s ”“”( d a t ae n c r y p t i o n s t a n d a r d ) 尝试采用的方法均是利用d n a 巨大的并行性和高存储密度的特性来生成问 题的解空间，然后利用生化方法从中筛选出正确的答案：而互补配对原则使得我们从 已知的单链d n a 可以明确地知道它的补链。d n a 解决问题的基本思想如图卜3 所示。 图卜3d n a 计算的示意图”1 f i gi - 3i l l u s t r a t i o no f d n a c o m p u t i n g 首先使用合理次序的由a 、c 、g 、t 组成的寡核苷酸序列( 简短的化学合成的单 链d n a 分子) 对计算问题进行编码，然后通过大量不同序列的杂交( 充分利用了d n a 的并行性和信息的高存储密度) ，并根据解决问题的本身算法，对杂交后的序列进行 处理，通过放大和分离技术，得到想要的序列，最后分析该序列，就会得到相应的答 案。在一般的实验处理过程中，杂交、放大、分离等还要经过多次的迭代处理。 1 2d n a 计算的完备性和通用性 d n a 计算的完备性是指：d n a 计算可以解决任何问题吗? 而d n a 计算的通用性是 指：是否能够实现可编程的d n a 计算机? 基于目前d n a 计算的数学模型，上边两个问 题都有了肯定的答案。在d n a 计算提出以后，用d n a 计算可以解决的问题越来越多： 可满足性问题、旅行商问题、图染色问题、0 - i 规划问题、最大团问题、最小覆盖问 题等等。如今，已经提出了多种d n a 计算模型：粘贴系统、w a t s o n c r i c k 自动机、 插入一删除系统、剪接系统、有穷h 系统的通用性、分布式h 系统等，这些模型各有 千秋，公认的d n a 计算机的“图灵机”还没有诞生。在资料 5 中有以上提到个各个 数学模型的介绍及通用性完备性证明，相对而言，“剪接系统”的d n a 计算模型较为 3 太原理工大学硕士研究生学位论文 成功，所以在以下讨论d n a 计算的通用性和完备性中，都将以“剪接系统”为例进行 介绍。 1 2 1 剪接系统的通用性 剪接模型是在限制酶和连接酶作用下d n a 分子重组行为的一种形式模型，并不严 格的讲，剪接两条链是指：首先通过给定子链的特定位点把它们切开，然后把获得的 这些片段交叉地连接在一起。h e a d 最早给出剪接操作的形式语言定义，后又由许 多作者修正。一个剪接操作可以用以下例子说明：在给定字符集及其上两个串x ，y 。 利用一个剪接规n r 剪接x ，y ：在由剪接规则r 决定的位置上切割x 、y ；分别将结 果中x 前段与y 后段，y 的前段与x 后段连接一起。用p a u n 给出的形式化方法。“，上剪 接规则r 是形如：口抖屈$ p 2 口，的串，其中o f ，口，屈，废是上的串，# 、$ 是外的标 记符号。若：x - - x o f l 届x 2 ，y = y - 口2 屈y z ( x - ，x z ，y - ，y 2 + ，为上由连接操作生成的 所有字符串的集合，中的元素称为词或串) ，剪接规n r = o f 。样届$ 以群口：剪接x 、y 的结果是z = x - 口l 岛y ：、w = y t 口2 届x z ，并记作( x ，y ) o r ( z ，w ) ，口l 属、盯2 成称为剪接 位点，x 、y 称为剪接项。 将剪接作为基本操作建立的生成机制称为剪接系统。给定一个公理系，在其上反 复使用剪接规则就生成了剪接系统的语言。由于在实际d n a 计算中，一种串只能使用有 限多次剪接规则，从而在数学用语上不用集合来表示剪接项，而用多重集，即在每个时 刻都应当记录每种串可用的次数。+ 上的多重集爿是指+ 到自然数集的一个映射 中一种串的个数是爿中一个自然数。有了这些概念，可以给出剪接系统的数学定义。 剪接系统定义：剪接系统是一个四元组y = ( ，7 ，月，励，其中是一个字 符集，t a 是终结字符集，爿是上的多重集，斤+ # z + $ # 间接规则集。直 观地讲，给定一个串的“集合”，剪接这些串就可生成下一个串的“集合”。剪接之 后，剪接项被消耗而剪接后的结果加入到这“集合”中。在字母表上由剪接规则曰按 重复量集爿生成的字符串集及其无限重复生成规则就构成剪接系统。将剪接系统 y 生成的语言记为( y ) ，定义以厅，丘) = l ( y ) iy = ( ，z 爿，励，月尼 ，即 是从公理集开始根据厉所给出的剪接规则无限重写而生成的字符串的集合。如果 ，厉 是两个0 型语言族，则( 一，e ) 就是一个通用的剪接系统，于是有以下结论。 剪接系统通用性定理1 ：对每个给定的字符集，都存在一个剪接系统，其公理 集和规则集都是有限的，而且对于以，为终结字符集的一类系统是通用的。 4 太原理工大学硕士研究生学位论文 1 2 2 剪接系统的完备性 证明剪接系统是计算完备的，等于要证明任何可计算函数可以用剪接系统来实 现，这里的可计算函数可以简单地理解为所有。而与t u r i n g 机可计算的函数等价的语 言是0 型语言，即由不在其生成规则上施加任何限制的语法生成的语言。若0 型语言记 为l o , 则剪接系统完备性结论可以表述如下。 剪接系统完备性定理：l o = 1 1 ( f i n ，f i n ) 即每个0 型语言都可由带有限条公理 和有限条规则的剪接系统生成。2 。”( f i n 为有限语言的集合) 。 完备性定理证明了任何可计算函数都可以由剪接系统实现，也就是断言了任何图 灵机可计算的事情全可以由d n a 计算模型来计算，这就是d n a 计算模型完备性的含义。 特别值得注意的是，这里并没有说明相反的结论，也就是说d n a 的计算能力并不一定 受到丘奇一图灵论断的限制，因为关于它的能力的讨论并不一定要在t u r i n g 机的理论 框架中讨论。 1 3d n a 计算的特点 1 3 1d n a 计算的优点 d n a 计算的特点主要表现在以下几个方面。 j ( 1 ) 并行计算能力。d n a 计算与电子计算机相比，最大的优势在于它的并行计 算能力。目前最快的巨型机每秒能执行1 0 ”次操作，在a d l e m a n 试验中，通过适当的 估计，d n a 计算的并行操作数目可以达到1 0 “，而运用适当的技术，1 0 “1 0 ”个d n a 链的并行操作是可以达到的。 ( 2 ) 低能耗。d n a 计算是通过生化反应工作的，所以消耗的能量很少。巨型机 执行1 0 9 次方操作需要1 j 的能量，而用于实现d n a 计算操作的酶是在进化中产生的， 具有很高的能量效率，1 j 的能量足以执行2 1 0 9 次操作。 ( 3 ) 存储容量高。由于d n a 计算是建立在分子计算和分子存储的基础上的，因 而在d n a 分子中，存储信息的存储密度可以达到每立方纳米存储1 个位，而目前录像 带的信息存储密度仅为1 0 ”立方纳米存储1 个位。 ( 4 ) 资源丰富。从植物或动物中提取d n a 的成熟技术为d n a 计算的提供了丰富 的核心材料。 1 3 2d n a 计算目前存在的问题 d n a 计算目前还处在初步的发展阶段，d n a 计算的核心思想在于经过编码后的d n a 链作为输入，在反应介质内经过一定时间控制的生化反应，以此完成运算，反应的产 物及溶液给出了全部的解空间。但最优解怎样与其分离出来，这是一个技术性极强的 问题。d n a 计算目前存在的问题主要集中在以下几个方面： 5 太原理工大学硕士研究生学位论文 ( 1 ) 计算中误差的消除。计算误差主要存在于两类操作中，提取( e x t r a c t i n g ) 和退火( a n n e a l i n g ) 。 ( 2 ) d n a 制作成本高。大量寡核苷酸片断的合成、处理、标记和单链变性所需 要的d n a 数量随着变量数的增加而增加，搜索空间的数量呈指数级增加。 ( 3 ) 最优解或真实结果的分离输出问题。 ( 4 ) 序列设计的困难。随着问题的复杂程度的增加，如何设计每条序列将随着 序列指数级增加而变得极其复杂。 本论文的最后就是基于最优解或真实结果的有效分离和输出做初步的探讨和研 究。 6 太原理工大学硕士研究生学位论文 第二章预备知识及经典试验 d n a 计算并不是把特定的序列放到试管溶液就能自动完成，而是借助许多的生化 操作来实现；在2 1 节将介绍实现d n a 计算的主要的生物工具，在随后的小节里将介 绍利用这些生物工具实现的经典试验。 2 1 生物工具n 0 1 合成：将核苷酸按照一定的次序生成所需长度的d n a 链。我们可以把它想象成一 台机器，它的生产原料是a 、c 、g 、t 四种碱基，生产的产品是一条我们想要的特定 碱基排列和特定长度的d n a 链。 熔解( m e l t i n g ) 和退火( a n n e a l i n g ) ：通过加热溶液，使双链d n a 分解成两条互补 的单链d n a ，这是熔解，熔解破坏了碱基之间的氢键；退火是熔解的逆过程，通过冷 却溶液，使单链d n a 重新组装形成双链d n a ，其过程如图2 1 所示。在双链d n a 中， g 、c 之间有三个氢键，a 、c 之间有两个氢键，因此当g 、c 的含量相对较高时，其熔 解的温度也相对的要高。 更占喜黾 磊磊幕写i 一蕊磊享= 妒 熔解退火 图2 - id n a 双螺旋分子的熔解和退火 f i g 2 1i l l u s t r a t i o no f m e l t i n ga n da n n e a l i n g 聚合( 引物延伸) ：d n a 的聚合可以实现d n a 的复制，给定一串单链d n a 作为模 版，利用一段短的寡核苷酸序列作为引物，该引物序列是该模板d n a 中部分片段的补 链，在溶液中d n a 聚合酶的作用下，将溶液中的脱氧核苷酸沿着引物的3 端依次添加， 使引物序列利用碱基配对原则沿着模板从57 端到3 端延伸，如图2 2 所示。 引柳：3 - g g c a t 一5 o 一3 r - g g c a t 一5 - o 3 一t c g a t g g a g g c a t 一5 模板t ：5r - a g c t a g c t c c g t a 一3 r 。5r a g c t a g c i c ( 3 g t a 一3 r 75 - a g 6 x a c , c t c c g t a 一3 图2 - 2 引物延伸 f i g 2 - 2 i l l u s t r a t i o no f p r i m e re x t e n s i o n 7 太原理工大学硕士研究生学位论文 聚合酶链式反应( p o l y m e r a s ec h a i nr e a c t i o n ，p c r ) ：利用d n a 聚合酶，可以将 特定的d n a 串复制，进行数量的放大。图2 3 显示了p c r 的工作原理，首先，选择双 螺旋d n a 的某一片断，按片段中某一已知序列，合成一对寡核苷酸链，此一对寡核苷 酸链称为引物，每一个引物各与d n a 片段中的一股链的一定核苷酸序列互补，将引物 加入含有双螺旋d n a 的溶液并加热使双螺旋d n a 熔解，然后迅速降低温度使引物与模 板链的互补序列结合，然后采用引物延伸，形成双螺旋d n a ，如此反复，便可以按指 数级扩增特定的d n a 序列。 笮竺辈、 = = ： 呻m ，一，f 一 二之f 嚣嚣暑篙搿翻。稍h 一l 器嚣：盘淼 ；主二! 睾愉， l 舳”州蚺砸脚”蚶 f 1 ：；罱= - l t ：兰盘盐皇f ，o = p “ f f _ ，u 跏z l - 一- 。一- - 一- ” “鼍0 瓮：箔9 h ，、，、，、，一 f - ，v v ， l 葛：喾：= ：高 t - o ， 、，n ，、r 、，- j i - _ 岫_ _ _ h d w ，弭”狮r _ t ” 口 i ”_ * 撕_ p m - v ，v 、，- l _ w l l n 图2 - 3p c r 实现了特定d n a 片段的复制放大 f i g 2 3 i l l u s t r a t i o no f p c r , i t a m p l i f yt h ed s d n a a taf i x c dr e g i o n 凝胶电泳( g e le l e c t r o p h o r e s i s ) ：是一种测量d n a 分子长度的技术，它是分子 生物学中使用最为广泛的技术。单链d n a 分子的长度是指构成该分子的核苷酸的数 量，双链d n a 分子的长度是指碱基对的数目。如图2 5 所示， i i - l + l _ l d h a 魏着电源的正极移动 一 摊一鼢的 图2 - 5 凝胶电泳分焉不同大小的d n a 链 f i g 2 5 g e le l e c t m p h o r e s i ss e p a r a t e sd n a s t r a n d sa c c o r d i n gt h es i z e 将d n a 链放到凝胶的一端，然后对其施加一个电场，因为d n a 分子带负电，所以 它会在电场的作用下从凝胶的一端移动到带正电的一端；当一个d n a 分子的负电荷与 它的长度成比例时，移动该d n a 分子所需要的力也与它的长度成一定比例。故这两种 相互抵消，且在理想溶液里，所有的分子都以同一速度移动。为了使不同长度的分子 以不同的速度移动，我们需要凝胶。当d n a 分子穿越凝胶向正电荷移动，需要穿越凝 胶的网孔，网孔起到分子筛的作用，小分子通过凝胶比大分子容易，所以速度快，显 然，同样长度的分子移动具有相同的速度，在给定时间范围内，小分子将比大分子移 动更长的距离。d n a 分子是无色的，在电泳后的凝胶中是看不到的，故在d n a 分子注 8 太原理工大学硕士研究生学位论文 入凝胶之前，要进行做标记处理，标记d n a 有两种方法，一种是用紫外光照射下发出 荧光的溴化物溴化乙锭进行着色，该方法适用于双链d n a 分子；另一种是在d n a 分子 的末端附加放射性的标记，最后对胶片曝光，察看不同长度的d n a 分子的显示。目前， 可以根据d n a 分子的迁移距离计算出它的长度。用于凝胶电泳的的凝胶主要有两种： 琼脂糖浆和聚丙烯酰胺凝胶，琼脂糖凝胶电泳是测量大分子( 大于5 0 0 b p ) 片断的标 准技术，而聚丙烯酰胺凝胶电泳可以测出长度方面仅相差一个碱基的d n a 片断，在测 量d n a 分子小片断时，聚丙烯酰胺凝胶是首选。 杂交( h y b r i d i z a t i o n ) ：利用碱基互补配对原则，利用一段寡核苷酸序列将两条 单链分子首尾相接形成双螺旋d n a 分子，图2 4 显示了从杂交到连接、脱杂交的一系 列过程。 连接( 1 i g a t i o n ) ：在杂交后的两条单链d n a 分子接合处形成磷酸二脂键，使两条 单链d n a 首尾相连形成一条单链d n a ，如图2 4 。当氢键把互补的d n a 分子连接到一 起的时候，在这些链的每一条上经常有一个缝隙，称为“缺口”。缺口是相邻的核苷 酸之间由于缺少磷酸二脂键而形成的，这样的键可以通过连接酶来建立。连接酶所具 备的条件是：被连接的3 - 端具有羟基且被连接的5 - 端具有磷酸基，幸运的是，当一 种限制酶切割相邻的核苷酸之间的磷酸二脂健时，它在3 端产生羟基，在5 端产生磷 酸基。 - - - - - - - - - - - - - - - - - - - - - - + a 吼干1 ：a - g - g - a - t - g - g - c a _ t _ g - g a - a - t - c c g a - t - g 。c a - t - g - - g - c 一 + a 喝c - t _ t - a g g a _ t - g g - c a - t - g - ga - a 干c c 吒一a 干6 - c a - t - g g 一甜 a 吒- c t - 卜a g g a - 1 - g g - c a - t - g - g - a - a - t c _ c - g - a - t - g c - a 千g - g - c a - g c _ t _ t - a g g a 十g g - c a 千g g a a - t - c - c - g a 千g c 。a - 丁_ g 。g 。c + + 。 c - g - t - a - c - c - t - t - a - g - g - c - t 。 图2 - 4 杂交、连接、脱杂交示意图 f i g 2 - 4 h y b r i d i z a t i o n 1 i g a t i o na n dd e h y b f i d i z a f i o n 磁珠分离：使用附着寡核苷酸片段的磁性珠子，将含有特定寡核苷酸片断的单链 d n a 从溶液中分离出来；该单链d n a 中含有与珠子上的寡核苷酸片断互补的d n a 片断。 其工作原理如图2 - 6 所示。需要注意的是，磁珠分离不仅可以分离含特殊的d n a 片断 9 太原理工大学硕士研究生学位论文 在d n a 链的端点位置处的d n a 链，也可以分离在其他的位置处的d n a 链。 图2 - 6 磁珠分离得到包含特定d n 片段的d n a 链 f i g 2 - 6 m a g n e t i cb e a ds e p a r a t i o n 切割d n a 分子：利用限制酶( r e s t r i c t i o ne n z y m e ) 可以在双链d n a 分子的某一 特定的位置处切断d n a 分子，表2 1 列出了一些常用的限制酶和相应的剪切位点。有 些内切核酸酶( 如：s 1 ) 能切断单链d n a 分子，而有些内切核酸酶( 如：d n a s ei ) 可以切断单链和双链两种d n a 分子。 表2 - i 一些限制酶和相应的剪切住点 t a b l e2 - ls o m er e s t r i c t i o nc 1 1 z y m c sa n dt h e i rc o r r e s p o n d i n gr e s t r i c t i o ns i t e s 限制酶剪切位点一 a e 5 一g g c c 一3 p 3 c c g ( 5 一 飘麒 5 c c g g 3 一 3 一g ( 屺c 一5 e c o l l t5 一g a6 眦一3 p 3 一c t l & a g 一5 b a m 5 - g g a t c c 一3 一 3 一c 锨g g 一5 p h i n 5 一a a g c t r _ 3 3 一t r c g a a 一5 p n o t i5 一g c g g c c g c 一3 p 3 - c g c c g g c g 一5 p p s t5 一c t g c a g 3 o 3 一g a c g t c 一5 u 限制酶破坏了磷酸二脂键和碱基之间的氢键，将双螺旋d n a 在剪切位点处切成两 1 0 太原理工大学硕士研究生学位论文 段。图2 7 演示了h a e i i i 和b a r h i 在相应的剪切位点处切断d n a 的情况。 ( a ) 5 ，g g c c 3 5 - c , - - gc - c - 3 3 ，c c g g 5 ，。- 3 - c - c g - g - 5 t 酬1 1 ( b ) 5 - ( 封g - a - t * c - c 3 5 g g - a t - c - c - 3 ，二一一一7i一，_-_卜3，cct-a-g3cc 卟( 卜5 ， - t - a - c g - 5 。u 。 1 ”o t 芝娆。a s ， b m , t , f | j 图2 - 7 限制酶h a e i i i 和b a m h i 在相应的剪切位点处切断d n a f i g 2 - 7 ( a ) i l l u s t r a t i o no f d n a s t r a n d sa f t e rc u tb yh a c h i ( b ) l l l u s t r a f i o no f d n as t r a n d sa r m c u tb y b a m h i 变性梯度凝胶电泳( d e n a t u r e dg r a d i e n tg e le l e c t r o p h o r e s i s ，d g g e ) 及温度梯 度凝胶电泳( t e m p e r a t u r eg r a d i e n tg e le l e c t r o p h o r e s i s ，t g g e ) ：传统的凝胶电泳 方法只能分离长度不同的d n a 分子，而长度相同的d n a 链却不能分离。d g g e t g g e 技 术在一般的凝胶基础上，加入了变性剂梯度或是温度梯度，能够把同样长度但序列组 成不同的d n a 片断区分开来。 如果d n a 双链分子全长不断增加温度或使用化学变性剂处理，两条链就会分开 ( 解链) 。不同的双链d n a 片断因为其序列组成不一样，其解链区域也不一样。当进 行d g g e t g g e 时，开始温度( 或变性剂浓度) 比较小，不能使双链d n a 片断在低解链 区解链，随着d n a 片断的迁移，若该区域的温度刚好达到双链d n a 片断最低的解