（计算机应用技术专业论文）dna计算机中数据结构的研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庭 邮电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：季咯国嘶 签字日期： 如7 年 月日 学位论文版权使用授权书 本学位论文作者完全了解重迭整鱼太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重麽邮电太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：魄国嘶 签字日期：1 年月日 翩辑：和斧信 签字醐：1 年皇日 磊；夏舡知n j 话西4 萌；+ 二每话蔷渺赢描。礞矗珏；强蠡珏舔；赫蕊秽i 秭赫 j 蝣磊，磁瓣螽驻瓣西焉播瓣；赫砂，赫“ 。o 麒。话嚣疆蕊# ，i # 届谲j 州，。 石t ，z 精 并行计算，而且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 计算 机中实现图元素的遍历。 最后，我们依据h e a d 的实验程序和我们上面提出的遍历算法，设计了 遍历算法的实验步骤实现，并对我们设计的实验进行了分析。 关键词：d n a 计算，序列编码，数据结构，图，遍历算法 重庆邮电大学硕士论文a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，d n ac o m p u t i n gh a sb e c o m eah o td i r e c t i o ni nt h en e l d o fc o m p u t e rs t u d i e sa n dt h er e s e a r c ho fm o l e c u l a rc o n l p u t e rh a sb e e nt a k e n m u c hc o n c e r n b a s e do nt h em o l e c u l a r b i o l o g y ， d n ac o m p u t i n gi sa u l t r a - l a r g e - s c a l ep a r a l l e lc o m p u t i n gw h i c hs i m u l a t st h es t r u c t u r eo fd n aa n d t a k e sb i o c h e m i c a lr e a c t i o n sa saw o r k i n gt 0 0 1 t h ed o u b l eh e l i xs t r u c t u r eo f 亡n ah a se n o r m o u ss t o r a g ec a p a c i t ya n ds o p e o p l eh a v eg e n e r a t e dg r e a t i n t e r e s t i nt h ed n ac o m p u t e r p l a s m i dd n a c o m p u t i n gh a sa 1 1c o m p a t i b l e m e r i t so fd n a c o m p u t i n g a tt h es a m 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 ac a r r i e rc o u l db eu s e da st h eu n i te f 诧c t i v e l y0 f d n a c o m p u t e r t h er e s e a r c ho fd a t as t r u c t u r ei sam o s ti m p o i r t a n tp a no ft h e i n ac o m p u t e rs t u d y i n g t h es t a c ka n dq u e u qh a v eb e e ns t u d i e dd e e p l y ，a n d t h eo p e r a t i o na l g o r i t h m sh a v eb e e ni m p l e m e n t e di nt h ed n a c o m p u t e r f i r s t l y ，w et a l k ea b o u tt h ec o d i n gp r o b l e mo ft h es e q u e n c ei nd n a c o m p u t e r t h ed n ac o d i n gh a sb e e ns t u d i e d ，i t sl i m i t i n gf a c t o r sa r ef o u n d ， a n dt h ec a n o n i c a ls t r u c t u r ei ss u m m a r i z e d t h ec o m p u t i n gm o d e lo ft h e o p t i m i z i n gc o d i n gi sf 0 u n d e d ，a n dq u a n t i t a t i v ea n a l y s i si sg a v e n ，t h ec o d i n g s o ft h es e q u e n c ew h i c hi sn e e di nt h ed a t as t r u c t u r ed e s i g n i n gi si n s t a n t i a t e d s e c o n d l y ，o nt h eb a s i so ft h ea d j a c e n c yl i s to ft h eg r a p h sd a t as t r u c t u r e i ne l e c t r o n i cc o m p u t e r ，w ed e s i g nt h es i m i l a r - a d j a c e n c yl i s to ft h eg r a p h s d a t as t r u c t u r ei nd n a c o m p u t e r r e c u rt ot h ec o m p u t i n gm o d e lo ft h ep l a s m i d d n aa n dt h es t o r a g es t r u c t u r e ，t h eb a s i co p e r a t i o na l g o r i t h m sa r ep r o p o s e d w el u c u b r a t et h et r a v e r s i n gg r a p ho ft h ed n ac o m p u t e ri n - d e p t hb a s e do nt h e s t o r a g es t r u c t u r e t h ed e p t hf i r s ts e a r c ha l g o r i t h ma n dt h eb r e a d t hn r s ts e a r c h a l g o r i t h ma r eg a v e dt oi m p l e m e n tt h eg r a p h st r a v e r s i n gi nd n ac o m p u t e r a tl a s t ，t h eb i o c h e m i c a le x p e r i m e n t a lp r o c e s s e sa r ed e s i g n e d ，a c c o r d i n g t ot h eh e a d se x p e r i m e n t a lp r o c e s s e sa n dt h et r a v e r s i n ga l g o r i t h m t h e n ，t h e e x p e r i m e n tt h a tw ed e s i g n e di sa n a l y z e d k e y w o r d s ：d n ac o m p u t i n g ，s e q u e n c ec o d i n g ，d a t as t r u c t u r e ，g r a p h ， t r a v e r s i n ga l g o r i t h 重庆邮电大学硕士论文目录 目录 摘要i a b s t r a c t i i 等一章绪论、 1 1 选题背景1 1 2 研究现状2 1 3d n a 计算研究取得的成果4 1 4 主要研究工作5 1 5 本文的主要内容6 第二章质粒d n a 计算模型的分析7 2 1 引言7 2 2d n a 计算的原理7 2 3 质粒d n a 分子结构和性质9 2 3 1 质粒d n a 载体介绍1 0 2 3 2 质粒d n a 结构的研究1 l 2 3 3 质粒d n a 的计算酶1 3 2 4 质粒d n a 的计算模型研究1 4 2 4 1 质粒d n a 的计算模型研究1 4 2 4 2 质粒d n a 的计算模型以及数学描述2 9 1 1 6 2 5 质粒d n a 的计算的编码问题1 7 2 6 本章小结1 8 第三章d n a 计算中的编码问题1 9 3 1 引言1 9 3 2d n a 编码的规范模型2 0 3 3 编码问题及其影响因素2 l 3 3 1 编码问题2 2 3 3 2 影响编码的因素【3 5 1 2 3 3 4 编码优化计算模型2 5 3 4 1 编码优化计算模型的建立2 5 3 4 2 编码约束条件2 5 3 5 应用分析2 6 3 6 本章小结2 7 第四章d n a 计算机中图数据结构的设计以及遍历算法2 8 h i 4 3 1 深度优先搜索遍历算法3 3 4 3 2 广度优先搜索遍历算法3 4 4 4 本章小结3 5 第五章实验程序设计与分析3 6 5 1 生物学实验常用生物技术3 6 5 1 1 基本操作3 6 5 1 2d n a 重组( d n ar e c o m b i n a t i o n ) 3 9 5 2 实验程序设计一4 l 5 3 程序设计分析。4 2 5 4 本章小结4 3 第六章结论及未来的工作4 4 6 1 结论4 4 6 2 进一步的工作4 4 致谢4 6 攻读硕士学位期间发表及录用的论文4 7 参考文献4 8 i v 要研究内容和章节安排。 1 1 选题背景 计算机技术被认为是2 0 世纪三大科学革命之一，电子计算机为社会 的发展起到了巨大的促进作用。计算机科学家们也将计算的问题划分为： 容易、困难和不可计算三类。处理容易类的计算，目前的电子计算机胜任 愉快，但处理困难类的问题，通常称之为n p 完全问题时，电子计算机会 随着问题规模的增大，计算所需的时间以指数级增长，而量子物理学已经 成功地预测出芯片微处理能力的增长不能长期地保持下去，因此，科学家 们正在寻找其他全新的计算机结构，试图有效地解决这些困难问题。一些 有效的计划已被提出，比如人工神经网络计算机、量子计算机、光学计算 机以及d n a 计算机模型等，其中d n a 计算机在近几年倍受科学界的关注 【l 】 o 利用d n a 特殊的双螺旋结构和碱基互补配对原则对问题进行编码， 把要运算的对象映射成d n a 分子链，在d n a 溶液的试管里，在生物酶的 作用下，生成各种数据池( 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 组成的串。它在数学上就像计算机中的编码“0 和“1 一样，可表示成4 个字母的集合= 4 ，r ，g ，c ) 来译码信息。d n a i 重庆邮电大学硕士论文第一章绪论 相当于作用在d n a 串上的不同的算子，如限制内核酸酶可作为分离算子， 链接酶可作为链接算子，聚合酶可作为复制算子，外核酸酶可作为删除算 子等【2 1 。 和传统的电子计算机相比，d n a 计算机有如下突出优点【3 - 6 】： 高度并行性，参加生化反应的每一个d n a 分子都相当于一个纳米 级处理器，在目前技术条件下，常规生化试验所能处理的d n a 分子的数 目大约为1 0 1 8 ，即使考虑到单个生化反应操作的时间延迟，其计算速度也 将比现有的超级计算机快至少1 0 5 倍。 存储容量大，组成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 分子就可以存储目前全世界所有的信息。 耗能低，据估计，电子计算机每焦耳耗能可执行2x1 0 1 9 个操作， 而相同的能量可以完成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 研究现状 自1 9 9 4 年a d l e m a n 博士利用现代分子生物技术，首次提出了有向哈密 顿路问题的d n a 计算方法【2 】，并在d n a 溶液中得以成功验证以来，d n a 计算理论一直是科学界的一个研究热点关于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 l o r n i ai n s t i t u t eo ft l 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 o u 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 计算机【_ 7 1 ，使d n a 计算机的研 2 重庆邮电大学硕士论文第一章绪论 究所研制成功第一台全自动运行的d n a 计算机【7 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 年，h e a dt 和他的研究小组运用质粒d n a 计算解决六个顶点的最 大独立集问题【引，并且提出了一种环状计算的概念。根据h e a dt 等人的设 计思想，我们对一个质粒d n a 环状分子进行编码，以相应的限制性内切酶 位点作为计算位点( 如图) ： 蜘w 峨麓鬈f 霉db 卜苎塑ll 塑塑ll 兰塑h! ! 塑卜l 兰竺h 二! ! 图1 1 质粒体p m p 6 0 7 9 在此基础上，他们通过对一个无向图g = ( l e ) ( 其中y 是顶点集，e 是 边集) 的顶点进行编码，用一定的核苷酸序列长度表示特定的一个顶点， 从而给出具有顶点集矿= 口，6 ，c ，d ，p ，) 和由四个无序对 口，6 ) ， 6 ，c ) ， c ，d ， d ，p ) 组成边集的图g = ( 矿，e ) 对应的m i s 问题质粒体计算的实验解决方法。 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 的结构实现一些逻辑运算【9 1 。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 细胞。然后将p h e r o m o n e 作为输 入，质粒( p i 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 的操作。 根据h e a dt 等人的研究成果，华中科技大学许进教授领导的d n a 计算 _ 盔鲨甾盔童盆盔i 盆盆盆菡溢近盏。盆逝盏i ：出：盏：耋：鲨= = 湓笾= ：! 盛巴至= 绂= = 羔量j ! 量蛭芽毒世一。呼，。弓叶，赫，葫、脚鬻。竺嘲。垂：! = 乎t 。鼍：辱二誊。一州j 茹絮 重庆邮电大学硕士论文第一章绪论 和分子计算机研究所【l0 】王淑栋提出了包含十个顶点图的顶点最小覆盖问 题的求解算法，刘文斌利用质粒d n a 分子的环形结构，将选择变量和执行 随机行走分开的策略，大大简化了随机行走的d n a 实现方法，显示出质粒 d n a 计算模型在解决某些图的组合优化问题中还是具有独特的优势。 国内东华大学丁永生教授n 、李汪根博士n 2 对堆栈以及队列等线性数 据结构进行了深入的研究，在d n a 计算机中设计了数据结构中堆栈以及队 列的存储结构，并使用限制性内切酶实现了基本的入队、出队、入栈、出 栈操作算法。 1 3d n a 计算研究取得的成果 我们知道，d n a 计算的研究已经涉及到许多领域，也取得了许多成果： 编码逻辑和实现方式 最早研究编码问题的是b a u m ，为了减小d n a 分子间的非特异性杂交， 他提出编码每个信息元的d n a 分子间的最小相同子序列应该大于某一常 数。d e a t o n 等将d n a 序列的编码同影响生化反应的条件结合起来，并首次 从信息论的角度对编码问题的可靠性进行了研究【1 3 ，1 4 1 。此外，他还提出了 一种基于d n a 遗传算法的编码方法，当然，这种方法只是理论上的，目前 还难以通过试验进行验证【l5 1 。为了更为准确的度量d n a 编码间的相似性， g a r z o n 等提出了移位距离的概念【1 6 】。c o n d o n 等结合编码理论对d n a 编码 的性质以及编码数量的上下限等方面进行了研究【l 7 l 引。但是影响编码的因 素众多，而且这些因素的关系复杂，难以确定编码能够客观评价编码质量 的适应度函数。 早期的d n a 计算主要是在实验室环境下在一个或多个试管溶液里进 行，而随着计算微型化、整体化的进一步要求，采用微流控技术的表面方 式将d n a 计算的研究向前大大迈进了一步【l9 1 。表面方式将对应于问题解空 间的d n a 分子固定在一块经过特殊化学处理的固体表面如胶片、塑料、玻 璃、硅半导体等，然后对表面上的d n a 分子重复进行标记、破坏、去标记 等操作，最后获得运算结果；或是在其表面上逐步生成解空间，最后获得 运算结果。这种通过化学方法固定在载体表面上的d n a 分子，能够承受在 表面上进行的各种加热、清洗及其它生化反应的作用。表面计算的发源地 和研究中心是美国w i s c o n s i n 大学的c o r n 领导的研究小组。 d n a 基因表达方式 4 _ ，善i ：夏焉：篡：二三二：= ：篓：篓羔：兰竺妻赫黟霉嚣鼍i 霉鬻裁稀篙纛誓：攀筝霉霉蔫露霹鬻纛戆嚣燕蠹麓震熏霹嚣雾鬟嚣焉骥蒌篱i l 燕 i 蓄蔷蓄蔷警湓鲨盆盆蔷二譬二三鲨= 二盐2 盘2 = = 盘兰童兰茎主薹蒌；薹薹篓三篓乏篡要篡篓雯 重庆邮电大学硕士论文 第一章绪论 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 a c 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 序列) ，最后用布尔逻辑公式表示各种可能的基因表达组合。 这是首次将d n a 计算方法应用于生物信息技术领域的尝试，该方法成功地 完成了一个有7 个小鼠表达基因的分析实例。此外，他们结合目前在生物 芯片中日趋发展成熟的微流控制技术( 将微泵、微阀门、检测装置、加热 器及微型毛细管通等集成在一块不大的半导体芯片上) ，提出了一种h p p 问题计算芯片的原理图【2 们。 基于d n a 的生物检测技术【2 1 】 基于微流控技术的表面方式是许多生物检测技术的有机融和，具体包 括酶谱技术d n a 杂交技术、d n a 芯片技术( 全自动d n a 测序仪) 、复序 列分析( v a r i a b l en u m b e ro ft 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 4 主要研究工作 目前在d n a 计算研究领域，数据结构的研究正处于起步阶段，但是研 究人员已经进行了大量的探索，做出了许多卓有成效的创造，取得了一些 重要进展，可是至今仍不能说这方面的研究可以打上句号。因此有必要作 进一步研究。本文将针对以下问题展开深入讨论： d n a 计算机中序列的编码问题。对d n a 编码进行研究，找出序列 编码的限制条件，总结其规范几何结构。建立编码优化计算模型，并进行 定量化，依据我们即将进行的数据结构设计，进行编码的实例分析。 设计非线性数据结构图的存储结构，借助于质粒d n a 计算模型， 提出图的基本操作算法，并根据其存储结构给出了图的深度优先搜索与广 度优先搜索遍历算法。 算法实验步骤描述，实验设计分析。我们根据上面提出的遍历算 重庆邮电大学硕士论文第一章绪论 法，设计了相应的算法实验步骤实现，并对我们设计的实验进行了分析。 1 5 本文的主要内容 本文的研究内容主要包括三个方面：讨论了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 计算机中的非线性数据结构图进行研究，并根 据h e a dt 等人的研究成果，特别是关于质粒体计算的实验解决方法来实 现我们提出的相关算法。 重庆邮电大学硕士论文第二章质粒d n a 计算模型的分析 第二章质粒d n a 计算模型的分析 这一章我们给出了一种基于环状质粒d n a 计算的新方法，这种计算 质粒包含一个特殊的插入d n a 序列片断，每个片断定位在匹配的限制性 内切位点，通过剪切和粘贴实现计算过程。论文同时给出了生物计算模型 和相关的数学描述，最后就相关的编码规则进行了讨论。我们在后面进行 数据结构研究设计算法时就是使用的质粒d n a 计算模型。 2 1 引言 1 9 9 4 年美国计算机科学家a d l e m a nl 成功地运用线性d n a 分子的退 火和连接方法解决了一个有向h a m i l t o n 路径问题，通过一系列的生物化学 分离步骤，从适当长度的分子中得到解。此后研究者们对将d n a 和其它 生物分子应用到计算过程这一领域进行了不懈的探索，本文主要研究非线 性的环状d n a 结构，这就是质粒d n a 。 质粒是一种特别引人注目的亚细胞有机体，它的结构比病毒还要简 单，既没有蛋白质外壳，也没有细胞外的生命周期，只能在寄主细胞内独 立地增殖，并随着寄主细胞的分裂而被遗传下去。由于质粒自身独立，稳 定等优点，它将进一步成为一种优良的生物计算载体。 1 9 9 9 年，h e a dt 等人率先提出了基于环状d n a 计算的思想，并且成 功地通过生物实验验证了质粒可以取代线性d n a 计算解决六个顶点的最 大独立集问题。本文将在h e a dt 等人的研究基础上，设计图数据结构的 基本操作算法，以及遍历算法的实验实现。 2 2d n a 计算的原理 d n a 计算不仅是一种全新的计算模式，同时也是关于生物化学领域和 数学领域相结合的一种全新的思维方式。尽管生物与数学的过程有各自的 复杂性，但它们具有一个重要的共性，即生物体异常复杂的结构是对由 d n a 序列所表示的初始信息执行一系列简单操作的结果，而可计算函数又 7 。， ? 1 。；。j 1 j ”+ ”1 1 “q 、一；日 - 蓄i ；誓盆二；蔷蓄；叠i 蔷；叠誓誓i 蔷二- 0 二蔷：二j ；雀盗i i ：盍蓄：盔蔷盆：。蓝菡盆；盆孟五盘：；主：盆；：溘：i ：i ：童羔：釜：i i 芏：! 羔耋：兰一一苎竺篓蔓蔓曼? 耋茄| 二二曾i 。毒品一一螽：i ；争二。一； 重庆邮电大学硕士论文第二章质粒d n a 计算模型的分析 可以通过一系列基本的简单函数的计算而得到。洞察两者之间的相似性， 正是d n a 计算诞生的基础【2 2 1 。 d n a 单链可看作由四个不同符号a ，g c ，t 所组成的链，即可通过四个 字母的集合y = 彳，g ，c ，乃来编码信息。d n a 链可认为是含有编码信息的 载体，通过在d n a 链上执行一些简单的生化操作，来实现信息的传递和转 换，从而完成计算目的。这一点与计算机科学中的编码技术非常类似。 经典的计算科学理论是建立在一系列重要的操作的基础上的，大部分 自动机的语言理论模型均是如此。类似地，d n a 计算也是建立在一系列连 续的操作的基础上的，不同仅在于操作对象是分子。这些用于计算目的的 分子生物操作在形式上具有多样性，例如，切割、粘贴、分离、连接、插 入和删除等。从理论上来讲，通过合理有效地使用这些基本的分子生物操 作，可以建立与图灵机一样强大的新的计算模型【2 3 1 。 d n a 计算的本质就是利用大量不同的核酸分子杂交，产生类似于数学 计算过程的某种组合的结果，并根据限定条件对其进行筛选，最后得出结 果。也就是说，不同的d n a 分子由于其具有不同的末端，所以具有不同的方 向性。根据d n a 分子间的w a t s o n c r i c k 互补原理，当大量随机的d n a 分子 相互杂交后，每个d n a 分子链所携带的原始信息就会与其它d n a 分子链所 携带的信息重新组合，形成类似于数学组合的某种结果。对于某种特定的运 算而言，这种结果的获得可通过对d n a 进行一系列的连续的生物化学操作 来实现【2 4 2 6 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 芯片的d n a 计算。其中a l d e m a n 的d n a 计算实 验是在试管中进行的，即计算过程中d n a 分子始终处于溶液体系，是基于溶 液反应的生物分子计算的典型。继a l d e m a n 之后，l i p t o n 【2 7 】提出了一个通用 的并行计算模型，该模型在试管中应用了提取、合并、删除和放大等分子操 作。表面计算方法被广泛的用于n p 问题求解，d n a 计算只有采用固相方法 才能被实际地应用。但基于表面的计算是在二维空间中进行的，表面可容纳 重庆邮电大学硕士论文 第二章质粒d n a 计算模型的分析 的信息量小。最常用的是“d n a 芯片( d n ac h i p ) ，g e n ec h i p 是a f f y m e t r i x 公司作为基因分析研究用的专利微阵，它能够在芯片上摆放多至4 0 0 0 0 0 个 不同的寡核营酸片段或1 0 0 0 0 个基因的每个基因的4 0 个片段，d n a 芯片 技术仍然广受青睐。 所以，d n a 计算的基本思想可以归纳如下：d n a 计算就是利用d n a 特殊的双螺旋结构和w a t s o n c “c k 互补配对( 也称碱基互补配对) 规律进行 信息编码，即对于某个具体数学问题的所有可能解，按照一定的规则将原 始问题的数据对象映射成d n a 分子链，用不同的d n a 序列进行编码，然 后在相关生物酶的作用下，生成各种数据池( d a t ap 0 0 1 ) ，并对经过高度并 行映射后的d n a 分子链在合适的条件下进行可控的生物化学操作( 瞬间完 成) ，生成新的d n a 片断，即生成原始问题的所有可能的解空间，最后利用 分子生物检测技术萃取出所需要的新的d n a 片断( 即待求问题的解) 。 综上所述，一般的，d n a 计算主要包括三个步骤：编码。即将所要 解决的原始问题映射为一个d n a 分子的集合；计算过程。在相关酶的 参与下，进行各种生化反应生成可能解空间；解的分离和读取。 2 3 质粒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 8 1 ：当两条多核苷酸链 均保持着完整的环形结构时，称之为共价闭合环形d n a ( c c c d n a ) ，这样 的d n a 通常呈现超螺旋的s c 构型；如果两条多核苷酸链中只有一条保持着 重庆邮电大学硕士论文第二章质粒d n a 计算模型的分析 完整的环形结构，另一条链出现有一至数个缺口时，称之为开环d n a ( o c d n a ) ，也就是o c 构型；若质粒d n a 经过适当的核酸内切限制酶切割 之后，发生双链断裂而形成线性分子( 1 d n a ) ，通称l 构型。在琼脂糖凝 胶电泳中，不同构型的同一种质粒d n a 具有不同的电泳迁移率，其中走在 最前面的是s cd n a ，其后依次是ld n a 和o 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 所示： 蔓翻b 眭缝经波渊 图2 1 质粒d n a 的结构图 2 3 1 质粒d n a 载体介绍 i 通常，我们采用正选择的质粒载体和表达型的质粒载体进行计算的编 码，这里我们详细介绍一下这两种质粒载体。 正选择的质粒载体 重庆邮电大学硕士论文第二章质粒d n a 计算模型的分析 根据遗传学上的正选择( 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 插入序列 的重组质粒。正选择质粒载体的优点在于它将一般质粒载体所需要的两个 选择记号合成在一起，使得我们能够在转化之后直接选择出重组质粒，从 而大大降低了需要筛选的转化子的数量，提高了选择的敏感性。 表达型的质粒载体 由于在生物计算中，我们更关注的是基因的编码蛋白质产物，所以表 达型的质粒d n a 是一种更为广泛应用的质粒载体。那么什么叫表达型质 粒载体呢? 为了将克隆的基因置于原质粒的转录一转译信号控制之下，我 们可以设计一种结构，能使克隆在其中特定位点的外源基因的编码序列， 在原细胞中正常转录并转译成相应蛋白质的克隆载体特称为表达载体 ( e x p r e s s i o nv e c t o r s ) ，表达型质粒载体就是它的一个分支。 以典型的大肠杆菌表达型质粒载体为例，包括细菌启动子及操纵位点 序列、多克隆位点、转录及转译信号、质粒载体的复制起点及抗菌素抗性 基因。待表达的真核基因编码序列被克隆在紧挨着启动子下游的多克隆位 点上，并以编码蛋白质氨基末端这一头靠近启动子的方向插入。转录终止 子能够增进m i a 的数量及稳定性，而操纵位点则通过与阻抑蛋白质的结 合作用来调节转录的反应。核糖体结合位点为克隆基因m d n a 的有效转译 提供了必要的序列信号，抗菌素抗性基因则为含有重组体d n a 的转化子 提供了有效的选择记号。 2 3 2 质粒d n a 结构的研究 除了h e a dt 等人提到的计算模型中质粒d n a 具有环状结构，限制性 内切酶剪切之后产生黏性末端从而自环连接之外，构建质粒载体的过程中 还可以通过易位子的作用插入其它的抗药性基因，例如氨苄青霉素抗性 ( a m p r ) 、四环素抗性( t e t 。) 和卡那霉素抗性( k a n ) 等。在这种抗药性记号结 构内部包含核酸内切限制酶，在某些单切割位点上插入外源核苷酸序列会 使此抗性基因失活。我们以碓浪3 2 2 质粒载体为例具体说明它的结构特点。 重庆邮皇奎兰堡主笙窒笙三皇星垫型垒盐竺堡型塑坌堑 - _ _ _ i - - _ _ - - _ _ - _ - - - _ - _ i _ - i - - i _ _ _ _ - _ - _ _ _ - _ _ - _ - _ _ l - - _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ i _ - _ _ _ _ _ _ _ _ 一一一 图2 2 加尺3 2 2 质粒载体的构建过程 1 2 ：蒜翼篡= 兰篓：篓竺i 霉警霉菇徽端游露零零焉嚣辫鞣瓣飘巍瑟瑟鬻黼瓣雾蒸熏 盏蓄蔷蓄蔷蔷蔷蓄；蓄