（系统工程专业论文）质粒DNA计算模型的研究与应用.pdf

华中科技大学硕士学位论文 摘要 从1 9 9 4 年至今，关于d n a 计算的研究已经取得了不少令人振奋的结果。作为 d n a 计算研究的一个重要分支，质粒d n a 计算兼容了d n a 计算的所有优点，同时 由于其环状结构的特异性，质粒d n a 计算载体还可以作为d n a 计算机的有效计算单 元，本文我们主要给出质粒d n a 计算模型研究及其在图的组合优化问题的应用。 本文首先介绍了质粒d n a 独特的分子结构和生化性质，在t h e a d 等人的工作 基础之上我们进一步推导出其计算模型的数学描述，质粒d n a 内含的限制性内切计 算酶可以保证实现精确的计算。我们提出根据一种自装配的g ，。语法规则来编排质粒 d n a 的信息位点的结构，同时介绍了一种主要依赖g c 含量变化改变解链温度的一种 编码方法，这种方法可以弥补由于d n a 序列太长带来的真值表达的不准确。 本文以解决动态规划问题为主要目标，提出了图的可达性问题和背包问题的d n a 计算分析，并在此基础上给出0 1 规划问题的质粒d n a 计算常规算法分析，引入了 h o f m e i s t e r 的对初始解构造进行优化的策略和改变g c 含量的t g g e 编码方法，最后 我们给出编码序列的评价函数：序列设计支持系统，通过s a 算法最大限度消除编码 的“相似性”问题。 本文同时给出构建基于质粒d n a 计算o 一1 规划问题的生物实验分析过程，t g g e ( 温度梯度凝胶电泳) 是基于d n a 片断解链温度的相关性，是敏感度极高的一种方 法，甚至片断序列中仅仅改变一个核苷酸都可以t g g e 分离。整个实验中p c r 扩增 是关键，采用温度梯度编码方法，理论上可以解决1 0 0 0 个不同变量的动态规划问题。 最后总结了全文，提出了系统进一步工作的构想，并总结了项目中的一些开发经 验和体会。 关键词：质粒d n a n p - - 完全问题g ，刊规则 g c 含量编码0 1 规划 序列设计支持系统d n a 重组t g g e 华中科技大学硕士学位论文 a b s t r a c t f r o m19 9 4t ot h ep r e s e n t ，t h er e s e a r c ho fd n a c o m p u t i n gh a sa l r e a d yg o r e nm a n y e x c i t i n gr e s u l t s a sa l li m p o r t a n tb r a n c ho fd n a c o m p u t i n g ，p t a s m i dd n ac o m p u t i n gh a s a l lc o m p a t i b l em e r i t so fd n a c o m p u t i n g a tt h es a n l et i m e ，f o rt h ep e c u l i a rq u a l i t i e so fi t s c y c l i cs t r u c t u r e ，p l a s m i dd n a c a r r i e rc o u l db eu s e da st h eu n i te f f e c t i v e l yo f d n a c o m p u t e r t h ep l a s m i dd n a c o m p u t i n gm o d e l a n dt h ea p p l i c a t i o ni nc o m b i n a t o r i a la n d o p t i m i z a t i o n p r o b l e m so f t h eg r a p h a r e m a i n l yp u b l i s h e di nt h i sp a p e r p l a s m i dd n a u n i q u e m o l e c u l a rs t r u c t u r ea n db i o c h e m i c a lc h a r a c t e r i s t i ca r ei n 拄o d u c e d i nt h i sp a p e ra tf i r s t t h em a t h e m a t i c sm o d e l d e s c r i p t i o nb a s e do n t h ew o r ko f t h e a d ，e t ci s d e r i v e df u r t h e r a n dt h er e s t r i c t i o ne n z y m e o f p l a s m i dd n a c a n g u a r a n t e e t or e a l i z ea c c u l m - t ec o m p u t i n g ak i n do fs e l f - a s s e m b l e g 瑚dg r a l n n 2 a r r u l et os e ti n f o r m a t i o ns i t e ss t r u c t u r e o f p t a s m i d d n ai sp r o p o s e d a n dac o d em e t h o dr e l i e do ng cc o n t e n tt oc h a n g et h e m e l t i n gt e m p e r a t u r e i sp u b l i s h e da tt h em e a n t i m e t h i sk i n do f m e t h o dc a i la v o i dt r u t h e x p r e s s i o n i n a c c u r a t ec a u s e db yt o ol o n gd n a a r r a y i ti st h em a i ng o a lt os o l v et h ed y n a m i c p r o g r a m m i n gp r o b l e mi nt h i sp a p e r t h ed n a c o m p u t a t i o n a la n a l y s i so f t h ez k pa n d0 - 1p r o g r a m m i n gp r o b l e mh a sb e e np r o p o s e d w e i n t r o d u c e dt h e s t r a t e g y o fh o f m e i s t e rt o o p t i m i z e i n i t i a ls o l u t i o na n dt h et g g ec o d e m e t h o do f c h a n g i n gg c c o n t e n t a tl a s tw e g i v eo u tt h ee v a l u a t i o nf u n c t i o no fc o d ea r r a y s ： s u p p o r ts y s t e mf o rs e q u e n c ed e s i g n t h e ”s i m i l a rq u a l i t y ”p r o b l e mo f t h ec o d ec o u l db e e r a s e dm a x i m u m t h r o u g hs aa l g o r i t h m t h eb i o c h e m i c a le x p e r i m e n t a la n a l y s i sc o u r s eo f o - 1i n t e g e rp r o g r a m m i n go nt h eb a s i s o f p l a s m i dd n ac o m p u t i n g i sp u b l i s h e di nt h i sp a p e ra tt h es a l n et i m e t 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 a t r o p h o r e s i s ) r e l y o nc o r r e l a t i o no f m e l t i n gt e m p e r a t u r eo f d n a s e q u e n c e ，a n d i t ss u s c e p t i b i l i t yi se x t r e m e l y h i g h ，e v e nc h a n g i n g o n en u c l e o t i d ei nt h e s e q u e n c e c o u i dl e a dt ot g g e s e p a r a t e ，p c r i sa k e y i nt h ew h o l e c o u r s e a d o p t i n g t h e t e m p e r a t u r eg r a d i e n tc o d em e t h o d ，i nt h e o r y w ec o u l ds o l v et h ed y n a m i c p r o g r a m m i n g p r o b l e m sw i t h1 0 0 0d i f f e r e n tv a r i a b l e s a tt h ee n do ft h ep a p e rw es u m m a r i z ef u l lp a p e r , a n d g i v eaf o r w a r d t ot h es y s t e ma n d w o r k sf u r t h e r , a n ds u m m a r i z es o m e d e v e l o p m e n te x p e r i e n c e a tl a s t k e y w o r d s ：p l a s m i dd n an p c o m p l e t ep r o b l e m t h eg r u l eg cc o n t e n t 0 - 1i n t e g e rp r o g r a m m i n g s u p p o r ts y s t e m f o rs e q u e n c e d e s i g n d n ar e c o m b i n a t i o nt g g e i l 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：客羔今 日期：础p 年毕月r 目 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密吐 ( 请在以上方框内打“”) 学位论文作者签名：弓k 蛊介 日期：娜毕年年月i r 日 指导教师签名：饷迫一 日期：1 郫悔中月f j 日 华中科技大学硕士学位论文 1绪论 本章首先介绍了主要介绍了d n a 计算产生的历史背景、研究质粒d n a 计算的意 义。接着介绍了国内外与本文研究有关的编码方法、计算模型等方面的研究现状以及 一些在实现技术上存在的问题，主要包括生物信息技术、检测技术等等。最后，简要 介绍了本文的主要研究内容和章节安排。 11 d n a 计算的研究背景 计算机技术被认为是2 0 世纪三大科学革命之一，电子计算机为社会的发展起到了 巨大的促进作用。计算机科学家们也将计算的问题划分为：容易、困难和不可计算三 类。处理容易类的计算，目前的电子计算机胜任愉快，但处理困难类的问题，通常称 之为 垆一完全问题时，电子计算机会随着问题规模的增大，计算所需的时间以指数级 增长，而量子物理学已经成功地预测出芯片微处理能力的增长不能长期地保持下去， 因此，科学家们正在寻找其他全新的计算机结构，试图有效地解决这些困难问题。一 些有效的计划已被提出，比如人工神经网络计算机、量子计算机、光学计算机以及d n a 计算机模型等，其中d n a 计算机在近几年倍受科学界的关注【”。 利用d n a 特殊的双螺旋结构和碱基互补配对原则对问题进行编码，把要运算的 对象映射成d n a 分子链，在d na 溶液的试管旱，在生物酶的作用下，生成各种数据 池( d a t ap 0 0 1 ) ，然后按照一定的规则将原始问题的数据运算高度并行地映射成d n a 分子链的可控的生化过程。最后，利用分子生物技术如聚合酶链式反应p c r 、聚合重 叠放大技术p o a 、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离 等，破获运算结果。这种思想突破了传统计算机体系结构的束缚，开创了一个新的计 算空间。 从d n a 的原理来看，它与数学操作非常类似。d n a 的单链可看作由4 个不同符 华中科技大学硕士学位论文 号a 、g 、t 和c 组成的串。它在数学上就像计算机中的编码“o ”和“1 一样，可 表示成4 个字母的集合= a ，g ，t ，c ) 来译码信息。d n a 串可作为译码信息。酶可看 作模拟在d n a 序列上简单的计算。不同的酶相当于作用在d n a 串上的不同的算子， 如限制内核酸酶可作为分离算子；链接酶可作为链接算子，聚合酶可作为复制算子， 外核酸酶可作为删除算子等口t 3 1 。 和传统的电子计算机相比，d n a 计算机有如下突出优点【1 ： ( 1 ) 高度并行性，参加生化反应的每一个d n a 分子都相当于一个纳米级处理器， 在目前技术条件下，常规生化试验所能处理的d n a 分子的数目大约为1 0 ”，即使考虑 到单个生化反应操作的时间延迟，其计算速度也将比现有的超级计算机快至少1 0 5 倍。 ( 2 ) 存储容量大，组成d n a 分子的4 个碱基的平均长度仅为0 3 5 n m ，按每条 d n a 链为1 0 0 0 b p 计算，其长度也仅有3 5 0 n m 。大约几十克d n a 分子就可以存储目 前全世界所有的信息。 ( 3 ) 耗能低，据估计，电子计算机每焦耳耗能可执行2 1 0 ”个操作，而相同的能 量可以完成1 0 9 个d n a 连接反应。 基于生化反应的计算方式主要是由d n a 分子闻的特异性杂交来完成的，而杂交反 应的结果受d n a 序列的编码以及影响生化反应的各种因素( 如反应物的浓度、温度以 及溶液的p h 值等的影响。因此，编码问题的研究很早就引起人们的注意。d n a 线性 序列的编码受外界环境的影响更为明显，长d n a 序列在温度、浓度异常的条件下极易 发生断裂，同时具有黏性末端的d n a 链非常容易与其相匹配的单链连接，从而大大影 响计算结果的准确性。因此如果能够找到一种相对独立、稳定的计算载体非常重要。 1 2 研究质粒d n a 计算的意义 尽管d n a 计算的研究己取得一些进展，但是d n a 计算机毕竟只是一种理论设想， 所进行的运算实验也仅是p 一问题的极简单情况，d n a 计算还有许多实际问题和理论 挑战有待解决。在当前所有d n a 计算框架中，d n a 串表达的计算状态类似于并行机 的芯片状态。并行计算中用的算法通常依赖于并行计算元件之间的通信。目前在d n a 华中科技大学硕士学位论文 计算的研究中，几乎还没有对如何获得d n a 串之间通信的建议，因此许多在常规并行 计算中的技术目前还不能用于d n a 计算。实际设计一个d n a 计算机的障碍主要有以 下几个方面： 1 构造的现实性及计算潜力 d n a 计算机的核心思想在于将经过编码后的d n a 链作为输入，在试管内经过一 定时间控制的生化反应，以此完成运算。反应的产物及溶液给出了全部的解空间。但 是最优解怎样与其它解分离，怎样输出，这是一个技术性极强的问题。尽管现代分子 生物学提供了像p c r 、高效电泳、亲和层析等选择以及放大纯化技术，但所消耗的时 间和空间复杂性远比在此前所进行的反应过程复杂得多。特别是随着求解问题规模的 增大，“输出技术”瓶颈可能成为d n a 计算机实现的主要障碍。 2 运算过程中错误的发生与传播 p c r 扩增是一种循环过程。耐热聚合酶有较高的碱基错配率。理论上讲，每次p c r 循环中不仅前一循环后已带有错误碱基的拷贝数量会增加，而且还会产生新的错误拷 贝。随着循环次数的增加，d n a 双链中不含任何错误碱基的拷贝比例在产物中会越来 越少，另外，由于热力学和动力学的原因，把大量的d n a 链放在一起通过几百个过程 步骤，偶尔会有一些非酶的不受控制的支路反应发生，甚至包括d n a 链的动力分解。 这样的错误会导致一些“伪解”出现，并在整个解空间中传播，那么系统结构及程式 中就必须有相应的程序来纠错，这样就增大了最优解输出的难度。 3 有效的通用算法 虽然已经证明d n a 计算机可以解决图灵机所能解决的所有问题，但有效而通用 的算法尚未面世。对于不同的问题【8 】，d n a 计算的解决方案也各不相同。尽管剪切模 型和粘贴模型从理论上是通用的，也给出了解决问题的例子【7 8 刚，但尚未得到实验上 的验证。 4 人机界面 对于各种计算问题，怎样寻找一种直接的翻译方式，变换成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 进行定点 插入和删除操作。 质粒d n a 计算概念的三个明显特征： 1 、用户购买并可能完善他( 她) 对计算中所用的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 的经验是不断积累的。对于由新序列分子引发的奇特性，用户可以间断地来调 整。 3 、整个计算中，质粒d n a 都保持双链形式。没有复杂的自身退火单链d n a 或 p c r 扩增步骤造成的麻烦。使用的d n a 保持本性。在复制和转录过程中，d n a 不被 分裂成长的单个链。相反，d n a 的少部分被打开并被相关的蛋白质周密地控制，这可 以阻止无法预料到的退火在d n a 计算中以某些现存形式出现。( 然而，我们对接近计 算结束时用p c r 技术从质粒体中读取线形片段却是满意的。) 4 华中科技大学硕士学位论文 = = = ；日= = = = ；= = = 一 1 3 国内外的研究进展 从1 9 9 4 年至今，关于d n a 计算的研究已经取得了不少令人振奋的结果。在国际 上掀起了场d n a 计算的“热潮”，美国、加拿大、英国、波兰、德国、以色列等国 家的著名研究机构和大学都相继开展了这一领域的研究工作，其中包括s o u t h e r n c a l i f o r n i au n i v e r s i t y ，c a l i f o r n i ai n s t i t u t eo ft e c h n o l o g y ，w i s c o n s i nu n i v e r s i t y ，d u k e u n i v e r s i t y p r i n c e t o nu n i v e r s i t y ，m i t ，l i v e r p o o lu n i v e r s i t y , w a r s a wu n i v e r s i t y ， t o k y ou n i v e r s i t y m e m p h i su n i v e r s i t y 等。2 0 0 1 年1 1 月，以色列w e i z m a n n 科学研 究所研制成功第一台全自动运行的d n a 计算机【1 ，使d n a 计算机的研制向着实用化 的阶段迈进了一大步。2 0 0 2 年2 月，s u y a m a 等研制出一台用于基因表达分析的d n a 计算机，主要由二部分组成：分子计算组件和检测部分。这一系列研究成果为我们进 一步研究d n a 计算问题打开了一片广阔的空间。 1 9 9 9 年t h e a d 和他的研究小组运用质粒d n a 计算解决六个顶点的最大独立集 问题，并且提出了一种环状计算的概念。根据t h e a d 等人的设计思想，我们对一个 质粒d n a 环状分子进行编码，以相应的限制性内切酶位点作为计算位点( 如图) ： v e r t i c e s ：af 0哇 be l ! ! 塑h ! 塑h 型卜竺l 件竺+ _ 竺 图11 计算质粒体p m p 6 0 7 9 的草图 华中科技大学硕士学位论文 在此基础上，他们通过对一个无向图g = ( v ，e ) ( 其中矿是顶点集，e 是边集) 的 顶点进行编码，用一定的核苷酸序列长度表示特定的一个顶点，从而给出具有顶点集 v = h 6 ，c ，d ，p ，) 和由四个无序对 d ，6 ) ， 6 ，c ， c ，田， d ，g 组成边集的图g = ( v ，e ) 对应的m l s 问题质粒体计算的实验解决方法。 根据t h e a d 等人的研究成果，华中科技大学许进教授领导的d n a 计算和分子 计算机研究所王淑栎提出了包含十个顶点图的顶点最小覆盖问题的求解算法，刘文斌 利用质粒d n a 分子的环形结构，将选择变量和执行随机行走分开的策略，大大简化了 随机行走的d n a 实现方法，显示出质粒d n a 计算模型在解决某些图的组合优化问题 中还是具有独特的优势。 2 0 0 2 年日本的k e n i c h iw a k a b a y a s h i 和m a s a y u k iy a m a m u r a 还提出了采用大肠 杆菌细胞中质粒d n a 的结构实现一些逻辑运算。f e m a l e 不包含转移质粒，她们发 送信息( p h e r o m o n e ) 给m a l e 细胞使之结合形成共扼结构，并让m a l e 细胞中的质粒 d n a 传送到f e m a l e 细胞。 r e c i p i e n t ( f e m a l e d o n o r ( m a l e c o n j u g a t m n a n d p l a s m i dt r 册s f 缸 图1 2 大肠杆菌的共扼质粒转移 然后将p h e r o m o n e 作为输入，质粒( p l a s m i d ) 作为输出，在信息池( p h e r o m o n e p 0 0 1 ) 中通过一个信息门( i n f o r m a t i o ng a t e ) 开关，我们可以实现4 + b 十c 的操作。 华中科技大学硕士学位论文 ab 0 ，l0 ，1 x ( i n ) 1 n f o r m a t i o ng a t e ( o r e ) 图1 3 给出了所用的计算质粒体的草图 1 4 质粒d n a 计算研究面临的困难 我们知道，d n a 计算的研究已经涉及到许多领域，也取得了许多成果： 1 基于d n a 的大规模分子数据库 d n a 分子作为遗传信息的存储介质具有独特优势一高密度和易于实现联想搜索。 p r i n c e t o n 大学的b a u m 在1 9 9 5 年就提出了构建基于d n a 大规模联想存储器( al a r g e a s s o c i a t i v eo rc o n t e n ta d d r e s s a b l em e m o r y ) 的设想【1 2 】。由于当时的技术条件的限 制而没有引起人们的重视。随着d n a 表面计算方法和生物技术的飞速发展，建立基于 表面方式的d n a 大规模数据库的研究已经具备基本的技术条件，d u k e 学的r e i f 等正 在从事这方面的研究。他们已经通过实验构建了一个1 2 7 规模的数据库，下一个目标是 构建1 2 4 规模的数据斟1 3 1 4 1 。 表1 1三个主要d n a 序列数据库网址 华中科技大学硕士学位论文 目前国际上有3 个主要的d n a 序列数据库( 表1 1 ) 1 4 】：欧洲分子生物学实验室 ( e u r o p e a nm o l e c u l a rb i o l o g yl a b o r a t o r y ，e m b l ) ( 位于英国剑桥) ，g e n b a n k 美国国家 生物技术信息中一5 , ( n a t i o n a lc e n t e rf o rb i o t e c h n o l o g yi n f o r m a t i o n ，n c b i ) ，该中心隶 储于美国家医学图书馆，位于美国家卫生研究院( n i h ) 内】和日本d n a 数据库( d n a d a t a b a n k o f j a p a n ，d d b j ) 。这3 个大型数据库于1 9 8 2 年达成协议，组成合作联合体。 它们每天交换信息，并对数据库d n a 序列记录的统一标准达成一致。每个机构负责收 集来自不同地理分布的数据( e m b l 负责欧洲，g e n b a n k 负责美洲，d d b j 负责皿洲 等) ，然后来自各地的所有信息汇总在一起，3 个数据库共同享有并向世界开放，故这 3 个数据库又被称为公共序列数据库( p u b l i c s e q u e n c ed a t a b a s e ) 。所以从理论上说， 这3 个数据库所拥有的d n a 序列数据是完全相同的。 2 编码逻辑和实现方式 最早研究编码问题的是b a u m ，为了减小d n a 分子间的非特异性杂交，他提出编 码每个信息元的d n a 分子间的最小相同子序列应该大于某一常数f 1 5 1 。d e a t o n 等将 d n a 序列的编码同影响生化反应的条件结合起来，并首次从信息论的角度对编码问题 的可靠性进行了研究【1 冬1 7 1 。此外，他还提出了一种基于d n a 遗传算法的编码方法，当 然，这种方法只是理论上的，目前还滩以通过试验进行验证1 18 】。为了更为准确的度量 d n a 编码问的相似性，g a r z o n 等提出了移位距离的概念【1 9 l 。c o n d o n 等结合编码理论 对d n a 编码的性质以及编码数量的上下限等方面进行了研列2 0 1 。但是影响编码的因素 众多，而且这些因素的关系复杂，难以确定编码能够客观评价编码质量的适应度函数。 早期的d n a 计算主要是在实验室环境下在一个或多个试管溶液里进行，而随着计 算微型化、整体化的进一步要求，采用微流控技术的表面方式将d n a 计算的研究向前 大大迈进了一步曙他2 1 。表面方式将对应于问题解空间的d n a 分子固定在一块经过特殊 化学处理的固体表面如胶片、塑料、玻璃、硅半导体等，然后对表面上的d n a 分子重 复进行标记、破坏、去标记等操作，最后获得运算结果；或是在其表面上逐步生成解 空间，最后获得运算结果。这种通过化学方法固定在载体表面上的d n a 分子，能够承 受在表面上进行的各种加热、清洗及其它生化反应的作用。表面计算的发源地和研究 华中科技大学硕士学位论文 中心是美国w i s c o n s i n 大学的c o r n 领导的研究小组。 3 d n a 基因表达方式 2 0 0 1 年日本的s u y a m a 和n i s h i d a 等将d n a 芯片、d n a 编码数( d n ac o d e n u m b e r ) 及d n a 计算技术结合起来，设计了一种智能化的基因表达分析方法。所谓 基因表达分析是指在特定时序和空间上，待测样品中基因表达的种类和丰度。首先， 将样品中转录的m r n a 反转录为对应的c d n a ，然后不同的c d n a 序列对应唯一的 d n a 编码数( 用正交化技术得到的特定长度的d n a 序列) ，最后用布尔逻辑公式表示 各种可能的基因表达组合，如图1 4 所示。图中的a ，b ，f 即表示不同的编码数， 有荧光的地方代表该编码数所表示的基因被表达。这是首次将d n a 计算方法应用于生 物信息技术领域的尝试，该方法成功地完成了一个有7 个小鼠表达基因的分析实例。 此外，他们结合目前在生物芯片中日趋发展成熟的微流控制技术( 将微泵、微阀门、 检测装置、加热器及微型毛细管通等集成在一块不大的半导体芯片上) ，提出了一种 h p p 问题计算芯片的原理图f 2 2 1 。 n o i o r 图14 基于d n a 计算的基因表达分析示意图 9 华中科技大学硕士学位论文 4 基于d n a 的生物检测技术f 2 3 i 基于微流控技术的表面方式是许多生物检测技术的有机融和，具体包括酶谱技术、 d n a 杂交技术、d n a 芯片技术( 全自动d n a 测序仪) 、复序到分析( v a r i a b l en u m b e r o f t a n d e mr e p e a t s ，v n t p ) 、探针标汪、r f l p 分型技术、斑点杂交分型技术等等。 同时，微型阎的控制，细小管壁的微观动力学影响( 如雷诺效应) 等等也是一个重要 的研究热点。作为d n a 计算研究的一个分支，质粒d n a 的计算模型也同样需要以上 这些技术的支撑。 1 5 本文的主要内容 本文的研究内容主要包括三个方面：提出质被d n a 计算模型，编码问题以及组合 优化问题的实现。其中，编码问题主要在t h e a d 等提出的模型基础上进行了进一步 的研究：关于组合优化问题的d n a 计算模型，我们给出具体的实验过程。此外，我们 还提出了一个基于d n a 的逻辑结构的描述。主要安排如下： 第一章：绪论，主要介绍了d n a 计算产生的历史背景、研究质粒d n a 计算的意 义、国内外发展状况以及质粒d n a 计算面临的困难。 第二章：质粒d n a 用于计算的研究：第一节引言；第二节介绍质粒d n a 的生物 学基础：第三节在前人研究基础上得到质粒d n a 计算模型的数学描述i 第四节给出质 粒计算编码的基本思想；最后小结。 第三章：运行质粒d n a 计算机的应用：第一节我们给出质粒d n a 主要解决的几 类组合优化问题，第二节我们将对具体地运行动态规划算法进行描述，第三节我们会 给出编码的评价函数：第四节本章小结。 第四章：实验分析：在这一章我们将就实验的可行性给出具体的过程和实验分析。 1 0 华中科技大学硕士学位论文 2 质粒d n a 计算模型的研究及编码规则 这一章我们给出了一种基于环状质粒d n a 计算的新方法，这种计算质粒包含一个 特殊的插入d n a 序列片断，每个片断定位在匹配的限制性内切位点，通过剪切和粘贴 实现汁算过程。论文同时给出了生物计算模型和相关的数学描述，并且就相关的q 。编 码规则进行了详细讨论，最后介绍了由g c 对含量改变解链温度的方法来编码的策略。 2 1 引言 1 9 9 4 年美国计算机科学家l a d l e m a n 成功地运用线性d n a 分子的退火和连接 方法解决了一个有向h a m i l t o n 路径问题，通过一系列的生物化学分离步骤，从适当长 度的分子中得到解。此后研究者们对将d n a 和其它生物分子应用到计算过程这一领域 进行了不懈的探索，本文主要研究非线性的环状d n a 结构，这就是质粒d n a 。 质粒是一种特别引人注目的亚细胞有机体，它的结构比病毒还要简单，既没有蛋 白质外壳，也没有细胞外的生命周期，只能在寄主细胞内独立地增殖，并随着寄主细 胞的分裂而被遗传下去。由于质粒自身独立，稳定等优点，它将进一步成为一种优良 的生物计算载体。 1 9 9 9 年t h e a d 等人率先提出了基于环状d n a 计算的思想，并且成功地通过生 物实验验证了质粒可以取代线性d n a 计算解决六个顶点的最大独立集问题。本文将在 t h e a d 等人的研究基础上，进一步给出环状d n a 计算的数学描述和编码算法。 2 2 质粒d n a 分子结构和性质。4 已知的绝大多数质粒都是由环形双链的d n a 组成的复制子，称为质粒d n a 。质 粒d n a 分子可以持续稳定地处于染色体外的游离状态，但在一定的条件下又会可逆地 整合到寄主染色体上，随着染色体的复制而被复制，并通过细胞分裂传递到后代。 环形双链的质粒d n a 分子具有三种不同的构型：当两条多核苷酸链均保持着完整 1 1 华中科技大学硕士学位论文 的环形结构时，称之为共价闭合环形d n a ( c c c d n a ) ，这样的d n a 通常呈现超螺旋 的s c 构型；如果两条多核苷酸链中只有一条保持着完整的环形结构，另一条链出现 有一至数个缺i = 1 时，称之为开环d n a ( o c d n a ) ，也就是o c 构型；若质粒d n a 经过 适当的核酸内切限制酶切割之后，发生双链断裂丽形成线性分子( i d n a ) ，通称l 构 型。在琼脂糖凝胶电泳中，不同构型的同一种质粒d n a 具有不同的电泳迁移率，其中 走在最前面的是s cd n a ，其后依次是ld n a 和0 cd n a 。 质粒d n a 的编码中，适用于作为基因克隆载体的所有质粒d n a 分子，都必定包 含下面三种共同的组成部分，即复制基因( r e p l i c a t o r ) 、选择性记号和克隆位点。其中， 复制子结构包括一个复制起始位点( o r i g i n ，简称o r i ) ，控制复制频率的调控基因，以 及一些复制子编码基因。这里的克隆位点我们主要强调m c s ( 多克隆位点) ，包含若 干单一限制性酶切位点，可供外源d n a 定点插入。 结构如图2 1 所示： 图2 1 质粒d n a 的结构图 2 华中科技大学硕士学位论文 2 2 1 用于d n a 计算的质粒d n a 载体的般类型 通常，我们采用正选择的质粒载体和表达型的质粒载体进行计算的编码，这里我 们详细介绍一下这两种质粒载体。 ( 1 ) 正选择的质粒载体 根据遗传学上的正选择( d i r e c ts e l e c t i o n ) 原理，即应用只有突变体或重组体分子 才能正常生长的培养条件进行选择，发展了一系列正选择质粒载体( d i r e c ts e l e c t i o n v e c t o r s ) ，这种质粒载体具有直接选择记号并可赋予寄主细胞相应的表型。 我们知道，一般质粒载体包含两个选择记号，在与外源d n a 的重组过程中，其中 一个记号保持完整，用作选择转化予，并根据另记号的插入失活效应迸一步筛选出 转化子，用来表明它带有具外源d n a 插入序列的重组质粒。正选择质粒载体的优点在 于它将一般质粒载体所需要的两个选择记号合成在一起，使得我们能够在转化之后直 接选择出重组质粒，从而大大降低了需要筛选的转化子的数量，提高了选择的敏感性。 ( 2 ) 表达型的质粒载体 由于在生物计算中，我们更关注的是基因的编码蛋白质产物，所以表达型的质粒 d n a 是一种更为广泛应用的质粒载体。那么什么叫表达型质粒载体呢? 为了将克隆的 基因置于原质粒的转录一转译信号控制之下，我们可以设计一种结构，能使克隆在其 中特定位点的外源基因的编码序列，在原细胞中正常转录并转译成相应蛋白质的克隆 载体特称为表达载体( e x p r e s s i o nv e n o m ) ，表达型质粒载体就是它的一个分支。 以典型的大肠杆菌表达型质粒载体为例，包括细菌启动子及操纵位点序列、多克 隆位点、转录及转译信号、质粒载体的复制起点及抗菌素抗性基因。待表达的真核基 因编码序列被克隆在紧挨着启动子下游的多克隆位点上，并以编码蛋白质氨基末端这 一头靠近启动予的方向插入。转录终止子能够增进m r n a 的数量及稳定性，而操纵位 点则通过与阻抑蛋白质的结合作用来调节转录的反应。核糖体结合位点为克隆基因 m o n a 的有效转译提供了必要的序列信号，抗菌素抗性基因则为含有重组体o n a 的转 化子提供了有效的选择记号。 1 3 华中科技大学硕士学位论文 2 2 _ 2 质粒d n a 易位结构的深入研究 除了t h e a d 等人提到的计算模型中质粒d n a 具有环状结构，限制性内切酶剪 切之后产生黏性末端从而自环连接之外，构建质粒载体的过程中还可以通过易位子的 作用插入其它的抗药性基因，例如氨苄青霉素抗性( a m p ) 、四环素抗性( l e t 。) 和卡 那霉索抗。胜( k a n ) 等。在这种抗药性记号结构内部包含核酸内切限制酶，在某些单切割 位点上插入外源核苷酸序列会使此抗性基因失活。我们以p b r 3 2 2 质粒载体为例具体 说明它的结构特点。 八 ir 7 2 6 8 ) 砂 图2 2p b r 3 2 2 质粒载体的构建过程 1 4 华中科技大学硕士学位论文 p b r 3 2 2 质粒的亲本之一是p m b l 质粒，它的氨苄青霉素抗性基因( a m p ) 足驳 自于r 1 质粒。( 1 ) r 1 质粒形成一种变异体r 1 d r d l 9 带有5 种抗药性基因：a m p 、 c m l 、s t r 、s u l 、k a n 。位于r l d r d l 9 质粒上的易位子t n 3 ，编码有对氨苄青霉素抗性 的0 一内酰胺酶基因，即氨苄青霉素抗性基因( a m p ) 。( 2 ) 在一次独立进行的实验中， 将r 1 d 删1 9 质粒同c o l e l 质粒共培养在同样的细菌细胞中，致使在这两个质粒之间发 生体内易位作用，易位子t n 3 便从r l d r d l 9 质粒易位到c o l e l ，产生新质粒p s f 2 1 2 4 作为p b r 3 2 2 质粒的另一个亲本。( 3 ) 同样，将r 1 d r d l 9 质粒和p m b l 共同培养易位 得到含a m p 的p m b 3 质粒，通过e c o r i 活性消化p m b 3 质粒得到重组体p m b 8 质粒。 这时p m b 8 质粒不含有任何抗药性基因，分子大小仅为2 6 k b 。( 4 ) 我们在e c o ri 活性条件下切割p s c l0 1d n a ，然后同加入e c o r i 的p m b 8d n a 连接，可以将来自 p s c l 0 1 质粒的含四环素抗性基因( t e t 7 ) 的d n a 片断导入p m b 8 质粒形成一个5 3 k b 的重组质粒p m b 9 。( 6 ) 接下来将p m b 9 和p s f 2 1 2 4 共同培养在同一种细菌细胞中， 使t n 3 易位子从p s f 2 1 2 4 质粒易位到p m b 9 质粒形成具有双重抗性的重组质粒 p b r 3 1 2 。( 7 ) 再将p b r 3 1 2 质粒作e c o r i 消化连接形成质粒p b r 3 1 3 ，从而除去多 余的b a r n h i 识别位点。( 8 ) 最后去掉两个p s t l 位点和e c o r n 片断，去掉非必要的区 段以降低分子量形成p b r 3 2 2 质粒。 新构成的p b r 3 2 2 质粒载体含有两个抗药性基因片断a m p 和t e t 且不重叠，对于 t e l 基因而言，外源的d n a 插入这个b a m h i 位点或h i n d 及s a i l 位点，都会造成此 基因失活，而a m p 基因则仍然保留着功能活性。同样，a m p 7 基因中的某些位点插入 外源d n a 序列也会造成基因失活，而不影响t e t 基因活性。最后的结果可以通过菌落 实验检测。根据这一结果，我们可以解决实际的多约束问题。 2