（计算机应用技术专业论文）若干问题的dna计算算法研究.pdf

太原理工大学硕士研究生学位论文 若干问题的d n a 计算算法研究 摘要 近年来，随着生物技术的飞速发展，一个新的研究领域- d n a 计算 随之产生。d n a 计算是一种新的计算模式，它以d n a ( d e o x y r i b o n u c l e i c a c i d ，脱氧核糖核酸) 为“原料 ，以生化实验为工具进行计算。由于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 h p p ) 以来，有 关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 算法也被相继提出。由于粘贴模型仅采 用原有的四种基本操作，实验操作步骤较多，耗费了大量时间，本文求解 问题时采用了多级分离装置，可以实现d n a 计算中的多种基本操作，并能 实现“多级分离”操作，大大减少实验步骤，成倍提高解题效率。 本文介绍了基于表面的d n a 计算求解o 1 整数规划问题的算法，并且 在此算法的基础上把未知数的取值范围扩充到从一2 到+ 2 的范围，从而扩 展了此表面算法的适用范围。定义了两种约束补链，给出了求解此类整数 规划问题的d n a 表面计算求解算法。本文给出了一个实例的求解步骤，证 明此算法的思想和可行性。本算法中采用荧光猝灭的有关技术，通过观察 太原理工大学硕士研究生学位论文 荧光来排除非解，具有读解、编码简单和错误率低的特点。运用此种增加 变量的方法来代替未知数的取值思维方法同样可以适用未知数取+ 3 ，一3 ， + 4 ，一4 等的规划问题中。 本文应用多级分离技术解决了以下两个问题： ( 1 ) o 1 整数规划问题。文中给出了利用多级分离装置基于溶液求解0 1 整数规划问题的d n a 算法。此种解法克服了表面求解方法的编码和荧光数 受限的缺点，且使用了多级分离操作，大大减少实验步骤，成倍提高解题效 率。 ( 2 ) 背包问题。本文给出了背包问题的一种新解法，即将其转化为0 - 1 整数规划问题进行求解，在求解中利用了多级分离装置，使实验步骤减少， 解题效率提高。 在解决以上两个问题时，文中都给出了具体的实例，并通过模拟试验 得到了具体的解决方案，说明了算法的可行性和有效性。 关键词：d n a 计算，多级分离，粘贴模型，o 1 整数规划，背包问题 i i 太原理工大学硕士研究生学位论文 r e s e a r c ho nd n aa l g o i u t h m so fs e v e r a l p r o b l e m s a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fb i o l o g i c a lt e c h n i q u e s ，an e wd i s c i p l i n e - - - d n a c o m p u t i n g h a sc o m e i n t ob e i n g d n ac o m p u t i n gi san e wc o m p u t i n g p a r a d i g m i tc o m p u t e s w i t hd n as t r a n d sa s m a t e r i a l s ，a n db i o c h e m i s t r y e x p e r i m e n t sa st o o l s t h em a s s i v ep a r a l l e l i s m ，h i g h d e n s i t ys t o r a g ea n de n e r g y e f f i c i e n c y o fd n ac o m p u t i n gm a yo f f s e tt h e d i s a d v a n t a g e so fe l e c t r o n i c c o m p u t e r s d n ar e s e a r c h e so nd n ac o m p u t i n gh a db e e ns p r e a do u t ，s i n c e19 9 4 ， 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 fg 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 t h e r e s e a r c h e r sh a dm a d eb i gp r o g r e s s ，b u tt h e r ea r es t i l ln od n a a l g o r i t h m so f s e v e r a lc l a s s i c a lp r o b l e m so ng r a p ha n dm 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 e p r o b l e m sh a d b e e ne x i s t e d ，b u ts t i l lt ob ei m p r o v e d t h es t i c k e rs y s t e mi sal a n g u a g eg e n e r a t i v em e c h a n i s mb a s e do ns t i c k i n g o p e r a t i o n sa n dad n ac o m p u t a t i o na b s t r a c tm o d e lt h a tf o l l o w sw a t s o n c r i c k c o m p l e m e n t a r i t yr e l a t i o nt oa n n e a l u s eo ff i x e d l e n g t hd n as 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 fm a t e r i a l sc a u s e dr e s e a r c h e so n s t i c k e rm o d e lm a k i n gar a p i dd e v e l o p m e n t ，a n dd n a a l g o r i t h m so fm a n y p r o b l e m sw e r ep r o p o s e d ，t o o b u t o p e r a t i o n s 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 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 s i nd n a c o m p u t i n gc o u l db ec a r r i e do u ti nt h i se q u i p m e n t s o ，t h eo p e r a t i o n s s t e p sw e r er e d u c e d ，a n dt h ee f f i c i e n c yi ns o l v i n gp r o b l e m sw a si m p r o v e d i i i 太原理工大学硕士研究生学位论文 t h e p a p e r i n t r o d u c e t h ed n ac o m p u t i n g a l g o r i t h m o nt h e t h e s u r f a c e d b a s e dm o d e la n dt h exo ft h es p e c i a lt i g e rp l a n n i n gi sf r o m - 2t o + 2a n dad n a a l g o r i t h mi ss h o w ni nt h ep a p e r t h eo p e r a t i n gs t e p sa r eg i v e n t h r o u g ha ni n s t a n c e b yu t i l i z i n gt h et e c h n i q u e so ff l u o r e s c e n c ed i s t i n g u i s h i n g ， t h en e w a l g o r i t h mc a ne l i m i n a t ea l lo ft h o s ef a l s es o l u t i o n st h r o u g ho b s e r v i n g t h ef l u o r e s c e n c eo nt h es u r f a c eo fd n am o l e c u l e sa n dt h en e wp r o p o s e d a l g o r i t h mh a ss u c hg o o dc h a r a c t e r i s t i c sa ss i m p l ee n c o d i n ga n dl o wf a u l tr a t e e t c t h ef o l l o w i n gt w op 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 s i nt h i st h e s i s ： ( 1 ) o - 1i n t e g e rp l a n n 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 ns o l u t i o n w a sp r o p o s e dt os o l v et h eo 一1 i n t e g e rp l a n n i n gp r o l e mp r o b l e m t h en e w a l g o r i t h mc a no v e r c o m et h es h o r t c o m i n go fe n c o d i n ga n dt h ef l u o r e s c e n c e i n t h ep a p e rm u l t i - s e p a r a t i o ni su s e d s o ，t h eo p e r a t i o n ss t e p sw e r er e d u c e d ，a n d t h ee f f i c i e n c yi ns o l v i n gp r o b l e m sw a si m p r o v e d - ( 2 ) k n a p s a c kp r o b l e m t h ek n a p s a c k w a ss o l v e di nt h ew a yo f t r a n s f o r m i n g i ti n t ot h e o 一1 i n t e g e rp l a n n i n gp r o b l e m i nt h ep a p e r m u l t i s e p a r a t i o n i su s e d s o ，t h e o p e r a t i o n ss t e p s w e r er e d u c e d ，a n dt h e e f f i c i e n c yi ns o l v i n gp r o b l e m sw a si m p r o v e d t h es p e c i f i ci n s t a n c e sw e r eg i v e nt os o l v et h et w op r o b l e m sa b o v e a n dt h e s o l u t i o n sw e r eg o tb ys i m u l a t i n ge x p e r i m e n t s s o ，t h ef e a s i b i l i t ya n dv a l i d i t y w 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 e ，s t i c k e rm o d e l ，o - 1i n t e g e r p l a n n i n g ，k n a p s a c kp r o b l e m i v 芦明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 鹰乏 、- ，日期：垄堕：查 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：座兰!日期： 导师签名： 砌、f 步 日期：弛参：二金 太原理工大学硕士研究生学位论文 1 1d n a 计算的产生背景 第一章绪论弟一早三百t 匕 计算机技术被认为是2 0 世纪三大科学革命之一，电子计算机为社会的发展起到了 巨大的促进作用，但是量子物理学已经成功地预测出芯片微处理能力的增长不能长期地 保持下去。在传统计算机计算速度增长空间有限的情况下，如何进一步的提高计算机的 计算能力? 人们把目光投向新的计算模式或介质，如量子计算和生物计算。 1 9 9 4 年a d l e m a n 首次用实验显示了d n a 用于计算的可能性。他在s c i e n c e 杂志上 发表的突破性的文章中【lj ，介绍了用d n a 计算解决图论中n p 完全问题有向图七节点六 条边h a m i l t o n 路径问题的实验。他的方法的主要思想是：首先随机生成所有的有向路， 然后找出所有开始于起点，结束于终点的有向路，最后寻找经过图的每个顶点且每个顶 点只经过一次的有向h a m i l t o n 路。对应于生物实现步骤是首先用寡核苷酸片断编码图的 顶点和边，然后将这些寡聚核苷酸片段放入溶液中，利用连接酶将它们连接起来，从而 产生对应于所有有向路的不同的d n a 链，最后利用p c r 扩增、探针、电泳等生物手段 寻找对应于只经过图的顶点一次的有向h a m i l t o n 路的d n a 链，如果有这样的路，则说 明该图存在有向h a m i l t o n 路，否则说明该图不存在有向h a m i l t o n 路。这个奇迹表明了 采用d n a 进行特定目的计算的可行性。它的新颖性不在于算法，也不在于速度，而在 于采用迄今为止还没有作为计算机硬件的生物工业技术来实现，并且开发了这种媒体潜 在的并行性。这一研究成果引起了数学、物理、化学以及生物界科学家们的广泛关注， 也开辟了d n a 计算这一崭新的研究领域。随后来自各国的2 0 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 计算机是生命科学与计算机科学相结合的产物，它将具有以下几个方面的突 出优点 2 1 ： ( 1 ) 具有高度的并行性，运算速度快。在一周的运算量相当于所有电子计算机从问世 以来的总运算量。在a d l e m a n 的实验中，通过适当估计，d n a 串的并行操作数目可达 1 0 1 4 ，许多研究者认为，用当前技术1 0 1 5 到1 0 2 0 个串的并行操作是可以达到的，而目前 太原理工大学硕士研究生学位论文 最快的巨型机每秒能执行1 0 1 2 个操作，虽然d n a 计算每个操作本身与电子实现相比非 常缓慢，但对于当前要求的巨型机或更强的计算挑战，d n a 反应的巨大并行性足以补 偿； ( 2 ) d n a 作为信息的载体其贮存的容量非常之大。1 立方米的d n a 溶液可存储l 万 亿亿的二进制数据，远远超过当前全球所有电子计算机的总存储量。 ( 3 ) d n a 计算机所消耗的能量只占一台电子计算机完成同样计算所消耗的能量的十 亿分之一。 ( 4 ) 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 计算机成为世界各国科学家们致力追求的目标，掀起了计算机革命的新篇章，一个新兴 的学科_ d n a 计算也随之诞生。总之，我们有理由相信d n a 计算机的出现将会给人 类文明带来一个质的飞跃，给整个世界带来巨大的变化。 1 2d n a 计算的发展及研究现状 自1 9 9 4 年a d l e m a n 在s c i e n c e 发表第一篇d n a 计算的文章以来已经过去了1 4 年。 这1 4 年内国际上的d n a 计算研究经历了不同的阶段，包括开始的兴奋，广泛被关注和 支持，研究的困难等。到了现在，可以说进入了稳步发展的阶段。早期有过d n a c o m p u t i n g 和d n ac o m p u t e r 等名词概念上的争论，随着人们认识的加深，这些争论亦不复存在。 最近也有学者开始将d n a 计算与遗传算法、神经网络、模糊系统和混沌系统等智能计 算方法相结合。目前，关于d n a 计算与d n a 计算机的研究发展速度非常惊人，无论 在理论研究上，还是实验方式的研究上都取得了很大的进展。下面对国内外研究的现状 作一个简要的介绍。 1 9 9 4 年，美国南加州大学的l e o n a r dm a d l e m a n 在美国著名杂志s c i e n c e 上发表了 一篇划时代的论文，这篇题为 m o l e c u l a rc o m p u t a t i o no fs o l u t i o n st oc o m b i n a t o r i a l p r o b l e m s ) ) 的论文，提出了d n a 计算的概念，用人眼看不到的d n a 分子来做计算解决 了一个n p 难题一有向哈密顿路径问题，借助生物实验向冯诺依曼的理想迈出了开创性 2 太原理工大学硕士研究生学位论文 的一步，指出了d n a 计算潜在的巨大并行性及待研究的问题，开创了d n a 计算机的 新纪元。 1 9 9 5 年，美国普林斯顿大学的r j l i p t o n 教授也在 s c i e n c e ) ) 上发表文章，利用 d n a 计算的巨大并行性来求解n p 完备问题可满足性问题( s a t 问题) 【3 】，从而开 创了一个非标准计算研究的新领域。它使人们对计算的本质产生了新的理解和认识。 1 9 9 7 年，o uy a n g 等利用d n a 计算解决了另一个n p 完全问题，图的最大团问题 4 1 。 从这三位学者的工作之后，陆续的很多研究人员给出了不同类型的n p 完全问题的 d n a 计算方法与结果，如l i p t o n 连接网络、二进制加法、电路及最大电路以及正规电 路等的可满足性问题【3 】【5 】 6 】【7 】；质粒d n a 分子是一种环状的超螺旋结构8 】_ ，h e a d 提出了 用质粒d n a 分子来解决可满足性问题网；c u k r a s 等人用r n a 代替d n a 给出了可满足 性问题的一种实验性的计算模型并讨论国际象棋问题的r n a 计算模型【l 川；l i u 等人对 可满足性问题进行了基于表面实验的d n a 计算【1 2 】；w h 对表面计算进行了改进，使 得表面计算的操作更具有可行性【l 引。虽然d n a 计算模型产生十多年时间，但关于基于 d n a 计算乃至一般的分子生物计算的图论与组合优化模型的研究已经有不少的结果。 日本的s a k a m o t o 等人用d n a 分子二级结构进行计算i l4 。，他们用生物技术求解了个由6 个变量1 0 个子旬组成的逻辑公式。w i s c o n s i n - m a d i s o n 大学的l i u 等人所做的表面计算 ( s u r f a c ec o m p u t i n g ) t 1 5 】，他们的实验使得d n a 计算可在固体表面进行，而不在溶液中进 行0 这项成果大大降低了d n a 计算的出错率。d n a 计算机的研制是d n a 计算研究中 最具有挑战性的问题，目前这方面研究也己经有几个非常好的结果，d n a 计算机研究 具有突破性的进展应是2 0 0 1 年以色列w e i z m a n n 科学院的b e n e n s o n 关于基于分子生物 的可编程与自治计算机器的研究1 1 6 】。我们称它为是一种“半自动化试管型d n a 计算机 。 2 0 0 2 年，a d l e m a n 的另一次实验给出了半自动化自组装d n a 计算模型【1 7 1 ，并利用该模 型解决了含有2 0 个变量2 4 个子句的3 可满足性问题。这要涉及2 2 0 即大约1 0 0 万种可 能性。为d n a 计算的高度并行性提供了有力的证据。特别值得一提的是2 0 0 4 年g p a u n 所提出的膜计算( m e m b 啪e c o m p u t i n g ) 概念【1 8 】。它是近年来d n a 计算领域的一个重大的 突破。膜系统其实不是直接的d n a 计算研究，它利用目前的计算手段来描述给予生物 细胞这一种多重膜结构的计算系统，并期望从中发现全新或高性能的生物计算概念和方 式。 国内关于d n a 计算的研究也己逐步开展起来。上海交通大学成立了世界上第二个 b i o x 生命科学研究中心，通过多学科交叉的优势，已完成了中国第一台“d n a 计算 机”雏形的研究。华中科技大学分子生物计算机研究所成立于2 0 0 1 年，是我国最早从事 太原理工大学硕士研究生学位论文 分子生物计算的研究团队之一。北京大学理论生物学中心在李政道先生提议下于2 0 0 1 年9 月正式成立，开展了生物分子进化、d n a 计算等方面的研究。许进等于2 0 0 4 年发 表了p a u n 等关于d n a 计算专著的中译本。2 0 0 6 年，山东大学申请到了d n a 数据挖掘 方向的国家自然科学基金，开始了在这一方向的研究。同年，首届生物计算理论及应用 国际会议在武汉召开。此外，在这方面展开研究的还有复旦大学、浙江大学、南京大学、 吉林大学、北京工业大学等。 国际上，d n a 计算机的研究已经很热。美国、加拿大、英国、波兰、德国、以色 列等国家的著名研究机构和大学都相继开展了这一领域的工作。许多研究小组及机构进 行跨国界的相互协作，并定期进行各种技术交流和讨论。在美国，该项研究得到美国国 家科学基金会和五角大楼国防高级项目局的支持。近几年，亚洲的日本和韩国对d n a 计算的研究也非常重视。 d n a 计算国际会议( i n t e r n 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 ) 自19 9 5 年在普林斯 顿举办第一届以来，已经举办了1 2 届，2 0 0 6 年第十二届会议在韩国汉城大学举行；2 0 0 7 年在美国孟菲斯举行第1 3 届d n a 计算国际会议。 当前d n a 计算的研究正在向下列方面扩展： ( 1 ) 继续探索其他新的d n a 计算及模型【1 9 1 ，以及编码方式1 2 0 2 1 1 ，d n a 加密技术 2 2 1 2 3 6 盘 守口 ( 2 ) 探索各种类型可由d n a 计算解决的n p 问题1 2 4 1 3 】【2 5 2 g i ，这类问题应该：实践 上可由分子计算求解。从误差检测和误差校正的角度来看，要有鲁棒的d n a 算法。 有可证明的、具有本质上优点的d n a 解答。 ( 3 ) 定义和研究d n a 计算的复杂性、生物复杂性和可实现性的衡量尺度。 ( 4 ) 探索一种分子高级语言所必须的基本生物操作。操作必须易于实现，易于自动化， 易于消除或减少差错，优化完成操作的分子过程。 ( 5 ) 研究d n a 计算与各种软件科学的结合和集成【2 7 】【2 8 】。d n a 计算与遗传算法、神 经网络等智能计算方法的结合，d n a 数据挖掘技术四 3 0 1 ，探索d n a 计算在工程和智 能控制中的应用。 ( 6 ) 开发适合于分子生物计算新的问题求解工具和程序。构建基于d n a 求解问题的 装置并使之自动化。研究未来d n a 计算机的可行性。 ( 7 ) 开发可利用的各种d n a 芯片。以用于计算机、半导体和光化学合成等微加工技 术。 4 太原理工大学硕士研究生学位论文 1 3 目前存在的问题 尽管d n a 计算的研究已取得了一些进展，但是在d n a 计算的研究中还有许多实 际问题和理论问题有待解决，可以简单的归纳为以下几点： ( 1 ) d n a 分子的局限性。d n a 分子有其非常稳定的一面，如果存在的方式合适，它 可以永久性保存；但是在溶液状态下高温加热5 分钟就可能使其发生部分断裂。d n a 分子稳定性的双面性正是它作为遗传物质所需要的：既要有保守性，也要有进化的余地。 这些性质如何有效地应用在d n a 计算中还没有得以系统的实现，因此我们还需要时间 确定到底主要使用哪些方式进行d n a 计算。 ( 2 ) 在d n a 计算实验中，如何选择实际操作的参数数目、个体操作的速度、个体操 作和序列操作的可靠性、信息载体的稳定性及一个实验中连续操作的次数，以提高反应 的自动化程度也是待解决的问题。 ( 3 ) 编码的复杂性。较多的单链寡核苷酸片断中可能有些会形成发夹结等结构，这就 需要在编码时，尽可能的使所选择的寡核苷酸片段有比较明显的差异。d n a 编码的研 究也是d n a 计算研究中的一个热点。 ( 4 ) 在杂交过程中的错误杂交。当杂交过程中产生错误杂交时，容易产生丢失解( 对 于有些问题来说，会产生伪解) 。这一问题是生物技术上目前很难控的，也是d n a 计算 的主要难点之一。 随着生物技术的不断发展，d n a 计算将会被用来解决更多的实际问题，特别对一。 些复杂巨系统中的问题。它将会给数学、计算机科学、生物学、化学和工程等学科带来 飞速的发展。 1 4 本文的内容 本文研究了d n a 计算在图论及组合优化中若干问题上的应用，研究中利用了多级 分离技术，使用多级分离装置模型解决了所选问题。 第一章绪论，简要概述了d n a 计算的产生的背景，简述了d n a 计算的基本原理、 优缺点、发展及研究现状；介绍了本文的主要内容、创新之处。 第二章d n a 计算的生物基础，简要介绍了d n a 的分子结构，建立在d n a 分子上 的基本生物化学操作等等。 。 第三章基于粘贴模型的多级分离技术，第一节介绍了粘贴模型的发展状况、编码 太原理工大学硕士研究生学位论文 方式、粘贴模型的四种基本操作及其物理实现、生物实现；第二节介绍了多级分离的概 念、多级分离装置模型的各个组成部分、以及利用多级分离装置所能执行的操作。 第四章基于多级分离技术求解整数规划问题，首先简述了0 1 整数规划问题，对 现有的该问题求解算法作了介绍，其中对基于表面的求解算法进行了扩展，使得算法求 解的问题的范围得到扩展；且以一个实例对算法的思想和可行性予以证明。再者，本文 基于多级分离技术求解了o 1 整数规划问题，与传统的分离技术求解此类问题的方法相 比，多级分离技术的的采用，提高了解题的效率；并且对一个实例进行了模拟，得出了 求解的结果，说明了本解法的思想及可行性。 第五章基于多级分离技术求解背包问题，首先简述了背包问题，介绍了已有的背 包问题求解算法，本文将背包问题转化为0 1 整数规划问题，然后基于多级分离技术给 出了求解背包问题的d n a 算法。并用实例说明了该算法的思想和可行性， 第六章总结 6 太原理工大学硕士研究生学位论文 第二章d n a 计算的生物基础 2 id 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 是活细胞中的关键分 子，它自身的分子结构支持d n a 的两个最重要的功能：对蛋白质的产生进行编码以及 自我复制，将精确副本传递到子代细胞中。 d n a 的单分子脱氧核苷酸( 简称为核苷酸( n u c l e o t i d e ) ) 由三个单元组成：戊糖、 磷酸和含氮碱基，这里的戊糖称为脱氧核糖，它有5 个碳原子，为便于区分，它们都有 一个固定的编号。由于碱基中也含有碳原子，为避免混淆，糖中碳原子用1 一5 来编 号，碱基中碳原子用1 5 编号( 如图2 1 ) 。磷酸基与碳5 相连，碱基与1 相连， 在糖内部，有一个羟基( 0 m 与3 相连。 n h c 0 l o p 0 1 0 n h2 i 图2 - 1 脱氧核糖核苷酸结构示意图 f i g u r e2 - 1t h em o l e c u l es t r u c t u r eo f n u c l e o t i d e 不同核苷酸的区别仅在于它们的碱基，有两类碱基：腺嘌呤( a d e n i n e ) 和鸟嘌呤 ( g u a n i n e ) ，简记为a ，g ；胞嘧啶( c y t o s i n e ) 并1 胸腺嘧啶( t h y m i n e ) ，简记为c ，t 。这四种 碱基的分子结构如图2 2 所示嗍 7 太原理工大学硕士研究生学位论文 o c y t o s i n e t h y m i n e 图2 - 2 碱基的分子结构 f i g u r e2 - 2t h em o l e c u l es t r u c t u r eo fb a s e s 简言之，d n a 是一种高分子化合物，组成它的基本单位是脱氧核苷酸。每个脱氧 核苷酸是由一分子磷酸、一分子脱氧核糖和一分子含氮碱基组成的。含氮碱基有4 种， 腺嘌呤( a ) 、鸟嘌呤( g ) 、胞嘧啶( c ) 和胸腺嘧啶( 1 ) 。既然核苷酸的区别仅是它们的 碱基，我们就可以依据其拥有的碱基类型分别将它们称为a 核苷酸，g 核苷酸，c 核 苷酸，t 核苷酸。 一个核苷酸的5 磷酸基和另一个核苷酸的3 羟基相连接形成磷酸二酯 ( p h o s p h o d i e s t e r ) 键，它是强键( 共价键，c o v a l e n t b o n d ) ，这就使得形成的分子具有方 向性，我们可以称5 - - 3 向或3 一5 向。方向性是了解d n a 的功能和操作的关键， 同时也是建立d n a 计算模型的关键。 一个核苷酸的羟基可与另一个核苷酸的羟基相互作用形成一种较弱的氢键，它的形 成遵循如下配对原则：a 和t 配对，c 和g 配对。碱基上的配对关系称为w a t s o n c r i c k 互补性原则【8 1 。d n a 一般为双链线性分子，有些为环形，也有些为单链环形。w a t s o n - c r i c k 碱基互补原则使得两条互补的d n a 单链分子螺旋缠绕在一起，形成了著名的双螺旋结 构嗍。( 如图2 3 所示) 图2 - 3d n a 的双螺旋结构 f i g u r e2 - 3 t 1 1 es t r u c t u r eo fd n ad o u b l eh e l i x 8 太原理工大学硕士研究生学位论文 2 2d n a 计算常用的酶 酶是一种蛋白质结构，某些操作必须在酶的作用下才能完成。在d n a 的计算中， 常用到以下几种酶。 限制性内切酶( r e s t r i c t i o ne n d o n u c l e a s e s ) ：一般简称限制性酶。它能够识别链中特定 的碱基序列，并且在相应的位置切断d n a 序列。这个相应的位置可能是识别的碱基序 列所在的位置，也可能是与识别的碱基序列有一定距离的位置。 核酸外切酶( e x o n u c l e a s e s ) ：它能够从d n a 序列的端( 3 端或5 端) 开始，切除 碱基。 聚合酶( j ) o l y m e r a s e ) ：在一个d n a 序列的一端上添加核苷酸，使序列增长。 连接酶( 1 i g a s e ) ：使两条具有互补粘性末端的d n a 链连接为一条。粘性末端是指双 链的d n a 分子末端有部分是单链结构，因此能与互补的单链结构粘和在一起。有互补 粘性末端的两条链形成稳定的双链，要用到连接酶。 ，a d l e m a n 认识到可以利用分子生物学的工具来解决数学问题。精确地说，d n a 序 列可用来编码信息，而酶可用来模拟简单的运算 2 3d n a 计算的基本思想 d n a 计算是一种以d n a 相关的某些生物酶等作为最基本材料的，基于某些生化反 应原理的一种新型的分子生物计算方法。d n a 计算的基本思想是【3 l j ：利用d n a 特殊的 双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成d n a 分子链， 在生物酶的作用下，生成各种数据池( d a t ap 0 0 1 ) ，然后按照一定的规则将原始问题的数 据运算高度并行地映射成d n a 分子链的可控的生化过程。最后，利用分子生物技术如 聚合链反应p c r 、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等， 检测所需要的运算结果。d n a 计算的核心问题是将经过编码后的d n a 链作为输入，在 试管内或其它载体上经过一定时间完成控制的生物化学反应，以此来完成运算，使得从 反应后的产物中能得到全部的解空间。 d n a 计算一般可概括为几个基本步骤，即 1 ) 分析要解决的问题，采用特定的编码方式，将该问题反映到链上，并根据需要合 成链。 2 ) 根据碱基互补配对的原则进行链的杂交，由杂交或连接反应执行核心处理过程。 9 太原理工大学硕士研究生学位论文 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 分子中的遗传密码，以及巨量的并行 性。因而d n a 计算模型为背景而产生的所谓的新一代计算机，称为d n a 计算机，必 有海量的存储以及极快的运行速度。在d n a 计算系统中，d n a 分子中的密码作为存储 的数据，当d n a 分子间在某种酶的作用下瞬间完成某种生物化学反应时，可以从一种基 因代码变为另一种基因代码。如果将反应前的基因代码作为输入数据，那么反应后的基 因代码就可以作为运算结果。这样，通过对d n a 双螺旋进行丰富的精确可控的化学反 应，包括标记、扩增或者破坏原有链来完成各种不同的运算过程，就可能研制成以d n a 。 作为芯片的计算机。 2 4d n a 分子的生物操作 d n a 计算是通过各种生物操作来实现的。目前，与d n a 计算模型有关的生物操作 主要有以下几种【3 2 1 3 3 1 。 2 4 1d n a 链的变性和复性 由于同链内的磷酸二酯键大大强于两个互补碱基之间的氢键，这就使得在不破坏单 链的前提下分离两条链成为可能。一种方法是通过加热溶液到某一特定温度，将双链 d n a 分解成两条互补的单链d n a ，即d n a 双链的分离，也称为变性( d e n a t u r a t i o n ) 。 变性温度一般为8 5 - - 9 5 。如果将加热的溶液再冷却，分开的两条单链又通过氢键重 新结合在一起( 冷却过程必须慢慢进行，使得相应的互补碱基有足够的时间进行配对) ， 形成双链d n a ，这一过程称为复性( r e n a t u r a t i o n ) 。将两个互补的d n a 单链结合在一 起的过程也称为退火( a n n e a l i n g ) 。 1 0 太原理工大学硕士研究生学位论文 2 4 2 合并 合并( u n i o n m e r g e ) ，对于盛有d n a 溶液的以个试管t l 、t 2 、t n ，将所有试 管中的溶液倒入一个试管t 中，那么t 中包含原来刀个试管中的所有d n a 链。 2 4 3 特定d n a 分子的提取 提取，又叫做抽取( e x t r a c t i o n ) ，按子串分离( s e p a r a t i o nb yh y b r i d i z a t i o n ) 可分两种情况：1 、提取出已知d n a 分子( 称为目标分子) ，事先将合成好的探针 分子( 即与该子序列互补的d n a 序列) 固定在固体表面，如玻片或磁珠上；然后将附 着有探针分子的固体支持物放入当前溶液中；这样，包含该子序列的d n a 分子就会与 探针分子杂交，清洗掉其它溶液后就得到了包含该子序列的所有d n a 分子。如果目标 分子不是单链，首先要将双链分子分解成单链分子。例如，假设要从一个溶液s 中提取 出单链分子链u 。将c l ( q 是o 【的互补分子，称为引物) 粘在一个过滤器上，用该过滤 器对s 进行过滤，a 同a 结合留在过滤器上，其它分子被过滤掉。通过这种方式，可以 得到附着在过滤器上的双链分子( a 和) 以及s 中去掉a 后的溶液s 。然后将过滤 器放到一个容器中，分解双链分子，移走过滤器，容器中仅剩下目标分子。也可以将引 物附着在细小的磁珠上，将其放入含有目标分子的溶液s 中，摇动混合液，目标分子 就附着在磁珠。 2 、得到已知长度的未知d n a 序列的分子，可以从凝胶电泳的结果中获得。例如， 从凝胶中切下含有所要d n a 分子的薄片，将其放在液氮中冷冻破坏凝胶的结构，然后 将其解冻，用特殊的过滤器( 仅d n a 分子才能通过) 过滤，就可以重新获得所需d n a 分子。 相关技术将在本文第三章详细介绍。 2 4 4p c r 扩增 聚合酶链式反应( p o l y m e r a s ec h a i nr e a c t i o n ，简称p c r ) 是诺贝尔化学奖获得者 m u l l i s 于1 9 8 5 年发明的具有划时代意义的技术。利用d n a 聚合酶，将给定溶液中特定 的d n a 序列快速地复制。p c r 扩增( a m p l i f y i n g ) 过程包含了一系列温度循环，每一 循环由下述三步组成( 如图2 4 ) ： 太原理工大学硕士研究生学位论文 ( 1 ) 变性，通