（计算机应用技术专业论文）dna计算在两类特殊应用问题上的研究.pdf

d n a 计并在两类特殊应用问题e 的研究 摘要 d n a - t - 算的海量存储和巨大并行运算能力，使其成为n p 完全问题和其它难解 问题的潜在解决方案之一，在理论上己成功的在多项式时间下解决了许多著名的 n p 完全问题。d n a 计算的特点使其在复杂的调度问题上有了新的解决方案，许多 复杂的调度问题均基于难解的n 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 计算研究的逐渐深入，现有的基于穷举方法 的d n a 计算算法中存在的解空间指数爆炸问题日益突出，已成为限制d n a 超级计 算应用的瓶颈。因此考虑将传统电子计算机并行处理的策略、方法和技术引入 d n a 超级计算是降低d n a 链数的重要途径之一。 本文采用c h a n g 等提出的d n a 计算模型对于多处理机独立任务调度问题， 采用粘贴模型解空间及a d l e m a n 的生物操作集合，给出了一种新的该类问题的 d n a 计算模型及相应的独立任务调度算法。 同时本文对如何减少d n a 解空间问题做了一些尝试。从电子计算机中传统 并行计算和并行处理的模型出发，将传统并行处理的策略和d n a 计算的特点相 结合，将电子计算机并行计算中的具有普适性的分治算法设计技术应用于求解子 集和问题的d n a 计算中，提出一种求解子集和问题的质粒d n a 算法，理论分析 表明：新算法在不提高算法的时间复杂度的前提下，可将求解子集和问题所需的 d n a 链数从穷举算法的0 ( 2 疗) 减少至0 ( 2 州2 ) 。 关键词：d n a 计算；任务调度问题；并行计算? 分治法；n p 完全问题；背包问 题 i i a b s t r a c t t h ea b i l i t yo fd n ac o m p u t e r sa f f o r d san u m b e ro fu s e f u lp r o p e r t i e ss u c ha s m a s s i 、，ep a r a l l e l i s ma n dah u g em e m o r yc a p a c i t y ，w h i c hm a k e sd n ac o m p u t i n g b , e c o m e s o ，n e o ft h ep o s s i b l ew a y st os o l v en pc o m p l e t ea n do t h e r h a r d ，p r o b l e m sforone h a n dm o s tt a s ks c h e d u l i n gp r o b l e m sa r en ph a r dp r o b l e m s a n dw i t h o u t c o r e s p o n d i n gd n ap a r a l l e la l g o r i t h m s f o r a n o t h e rh a n d ，d i f f e r e n tf r o mt h e t r a d i t i o n a lc o m p u t e r s d n ac o m p u t e r sa r el e s su n i v e r s a lt h a nt r a d i t i o n a lo n e s ，s ot h e a l g o r i t h mo rad n ac o m p u t e rj u s tf o ro n ep r o b l e m c a nn o tb eu s e df o ro t h e rp r o b l e m s w i t h o u ta n ym o d i f i c a t i o n t h i sl e a d st oa l m o s ta l lt h ec u r r e n td n ac o m p u t i n g a l g o r i t h m st a k i n gt h eb r u t e f o r c em e h o dr e g a r d l e s so f t h ed i f f e r e n tm o d e l s ，a n dt h e e x p o n e n t i a li n c r e a s e i nd n av o l u m e t h e r e f o r e ，t a k i n gt h em e t h o do fp a r a l l e l p r o c e s s i n gi nc o m p u t e r si n t od n ac o m p u t i n gi s a ni m p o r t a n tw a yt or e d u c et h ed n a s t r a n d sv o l u m e i nt h i sp a p e r ，w et a k et h ec h a n g sm o d e lw h i c hu s e st h es t i c k e r ss o l u t i o ns p a c e a n da d l e m a n sd n ao p e r a t i o ns e ti n t ot h ei n d e p e n d e n tm u l t i p l yp r o c e s s o r st a s k s c h e d u l i n gp r o b l e m sa n dd e s i g na nd n ap a r a l l e la l g o r i t h m m e a n w h i l e ，w ea l s ou s e t h ep l a m i s tm o d e li n t os o l v i n gt h ek n a p s a c kp r o b l e m s ，a n dt a k eo n eo ft h ei r n p r o t a n t p a r a l l e lc o m p u t i n gt e c h n o l o g y - - - d i v i d ea n dc o n q u e ri nt r a d i t i o n a lc o m p u t e r si n t ot h e n e wm o d e lt od e s i g nn e wa l g o r i t h m sf o rk n a p s c a kp r o b l e m t h ea l g o r i t h m sd e s i g n e d c a nd e c r e a s et h ed n as t r a n d ss h a r p l yf r o m0 ( 2 州2 ) v o l u m ei n t o0 ( 2 玎) d n as t r a n d s k e yw o r d s ：d n ac o m p u t i n g ；t a s ks c h e d u l i n gp r o b l e m ；p a r a l l e lc o m p u t i n g ；d i v i d e a n dc o n q u e r ；n pc o m p l e t ep r o b l e m ；k n a p s c kp r o b l e m 1 1 1 d n a 计算在两类特殊戍用问题一卜的石j f 究 插图索引 图1 。1d n a 分子双链结构图一3 图2 1d a g 任务图一9 图3 1独立：任务的不同的调度策略18 图4 1质粒d n a 的剪切计算模型1 2 7 图4 2质粒结构图2 8 图4 3d n a 编码链3 0 v 1 硕二 ：学位论文 附表索引 表3 1死中2 7 个变量的d n a 序列2 2 表3 23 个任务和2 个处理器独立任务调度问题的8 种可能分配策略2 3 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了支巾特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：物1 竣 日期：御严岁月胗日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囤。 ( 请在以上相应方框内打“”) 作者签名：2 局1 诞殳 导师签名： 日期： 日期： 泖笤 翮 年7 年 月儿日 月91 7 1 ， 硕 学位论文 1 1 研究目的与意义 第1 章绪论 电子计算机对人类社会的发展起到了巨大的促进作用，随着社会和科学技术 的发展，许多n p 一完全问题广泛应用于不断出现的新工程领域的复杂系统中。这 些问题不仅应用广泛，而且在计算机理论科学的研究中具有十分重要的地位。 随着分子生物学的发展，一个测试试管已可产生1 0 1 8 个d n a 链【1 1 。1 0 ”个分子 链可用于表示10 1 8 位数据，基本生物学操作能同时处理1 0 1 8 位信息，即能使1 0 ”位 数据并行执行。因此，生物计算在处理大型难解问题可提供巨大的并行性【l 】。19 9 4 年，a d l e m a n 开创性的使用基于d n a 分子的生化反应解决了7 个顶点的有向 h a m i l t o n 路径问题【2 】，之后，关于d n a 计算机及其计算模型与实验方法等方面的 研究日益引起重视。l i p t o n 仿效a d l e m a n 的方法成功求解了另一个经典的n p 完全 问题一可满足性( s a t ) i h 题【3 j 。随后l i p t o n 的思想在实验里用生物技术得以实现【4 1 。 此后，有诸多学者给出了不同类型的图与组合优化问题的d n a 计算机算法和实验 结果 5 - 9 】。 近年来，借鉴生物学原理进行科学计算研究已成为科学计算领域的典型特征 之一【l 们。比较著名的有模拟人的大脑学习机制而建立的人工神经网络，受达尔文 进化论启发而建立的遗传算法，以及模拟人体的免疫机制而提出的免疫算法【1 1 1 。 生物分子计算的思想产生可追溯到电子计算机刚产生的年代。科学家希望利用生 物分子来改进计算机硬件的效率，因为生物分子在化学反应中具有高度的并行性， 而且它们在自然界中大量存在，体积小而可编码的信息量却非常大。 早期生物分子计算的工作只是尝试利用生物材料模仿传统的电子模式，直到 19 9 4 年，a d l e m a n 矛0 早期生物分子计算的工作只是尝试利用生物材料模仿传统的 电子模式，直到1 9 9 4 年，a d l e m a n 矛l j 用d n a 分子计算方法解决了哈密顿路径问题 ( h a m i l t o n i a np a t hp r o b l e m ，h p p ) 忆j ，从而在生物分子计算领域开辟了一个新纪 元。在过去的几年中，不断有新的分子计算方法产生，让我们看到生物分子计算 是一个崭新和充满潜力的研究领域。 d n a 计算以其具有的海量存储和并行运算能力从理论上可克服电子计算机 存储量小与运算速度慢的不足【l3 1 。而且，只要未来关于d n a 计算的生物技术走 向成熟( 无错码、链长适中、操作自动化等) ，其超级计算的成本将远低于现有基 于v l s i 结构的超级计算机的成本1 1 4 。1 5 1 ：目前为止，一个测试试管已可产生1 0 1 8 个d n a 链，它可使l0 1 8 位数据以数据并行的方式并行运行。因此，d n a 计算可 提供相当于1 0 1 8 个处理单元的并行性和0 ( 10 1 8 ) 的存储空间1 1 4 - 1 5 。到2 0 0 1 年最快 d n a 计算在两类特殊应用问题上的研究 的超级计算机在10 0 0 s 内大约能并发处理l2 8 1 0 1 5 位的信息，而d n a 计算中耗 时最长的“抽取”操作在1 0 0 0 s 内可在试管中同时处理1 0 1 3 位的数据单元；d n a 计 算的存储密度大约为磁带的1 0 1 2 倍【5 1 。尽管目前科学界还没有给出d n a 计算将 来的确切前景，所进行的运算实验也仅是n p 问题的极简单情况，d n a 计算还有 许多实际问题和理论挑战有待解决。在当前所有d n a 计算框架中，d n a 串表达 的计算状态类似于并行机的芯片状态。并行计算中用的算法通常依赖于并行计算 元件之间的通信。目前在d n a 计算的研究中，几乎还没有对如何获得d n a 串 之问通信的建议，因此许多在常规并行计算中的技术目前还不能用于d n a 计算。 但由于它在科学计算、制药和医疗等方面所展现的巨大潜力，其未来研究仍然相 当可期【5 1 。 1 2 生物分子计算的基本思想和基本方法 随着现代分子生物学的发展，人们逐渐认识到脱氧核糖核酸d n a ( 除少数病毒 为r n a 外) 是所有生物的主要的遗传物质。d n a 是一种由脱氧核苷酸组成的高 分子化合物，每个脱氧核苷酸由一分子磷酸、一分子脱氧核糖和一分子含氮碱基 组成。含氮碱基有4 种：腺嘌呤( a ) 、鸟嘌呤( g ) 、胞嘧啶( c ) 和胸腺嘧啶( t ) 。 传统的计算机是用“0 ”和“l ”进行各种编码的。而在d n a 计算中，可以 用组成d n a 分子的4 个字母的集合= a ，g c ，t ) 来编码信息。酶可看作在d n a 序列上简单的计算，不同的酶相当于作用在d n a 串上的不同的算子，如限制内 核酸酶( e n d o n u c l e a s e s ) 可作为分离算子；链接酶( 1 i g a s e ) 可作为链接算子，聚合 酶( p o l y m e r a s e s ) 可作为复制算子，外核酸酶( e x o n u c l e a s e ) 可作为删除算子等。 d n a 计算的基本思想是：利用d n a 分子的双螺旋结构和碱基互补配对的性 质，将所要处理的问题编码成特定的d n a 分子，在生物酶的作用下，生成各种 数据池( d a t ap 0 0 1 ) ，即问题的可能解；然后利用现代分子生物技术如聚合酶链反 应( p o l y m e r i z ec h a i nr e a c t i o n ，p c r ) 、聚合重叠放大技术( p a r a l 2 1 e lo v e r l a p a s s e m b l y ，p o a ) 、超声波降解、亲和层析、分子纯化、电泳、磁珠分离等手段 破获运算结果；最后通过测序或其它方法解读计算结果。 d n a 计算的核心问题是将经过编码后的d n a 串作为输入，在试管内经过一 定时间完成控制的生物化学反应，以此来完成运算，使得从反应后的产物及溶液 中能得到全部的解空间。d n a 分子生物算法具有如下三方面的显著特点： ( 1 ) d n a 分子生物算法具有高度的并行性，运算速度快。在a d l e m a n 的实验中， 通过适当估计，d n a 串的并行操作数目可达1 0 1 4 ，许多研究者认为，用当前技术 10 1 5 到10 2 0 个串的并行操作是可以达到的，而目前最快的巨型机每秒能执行10 1 2 个操作，虽然d n a 计算每个操作本身与电子实现相比非常缓慢，但对于当前要 求的巨型机或更强的计算挑战，d n a 反应的巨大并行性足以补偿。 2 硕士学位论文 ( 2 ) d n a 作为信息的载体其贮存的容量非常之大，1 立方米的d n a 溶液可存储 1 万亿亿的二进制数据，远远超过目前所有电子计算机的总储存量； ( 3 ) d n a 分子生物计算所消耗的能量只有一台电子计算机完成同样计算所消耗 的能量的十亿分之一。 d n a 计算的上述特性，即运算的高度并行性、大容量、低消耗是目前计算 机和并行计算机所无法比拟和替代的，从这个意义上说，19 9 4 年由a d l e m a n 所开 创的分子生物计算技术具有划时代的意义，正因为如此，d n a 计算机成为人们 所追求的目标。 1 3d n a 计算机理 3 糖一磷酸骨架链 图1 1d n a 分子双链结构图 传统的计算机是用“0 和“1 进行各种编码的。而在d n a 计算中，可以 用组成d n a 分子的4 个字母的集合= a ，g ，c ，t 来编码信息。酶可看作在d n a 序列上简单的计算，不同的酶相当于作用在d n a 串上的不同的算子，如限制内 核酸酶( e n d o n u c l e a s e s ) 可作为分离算子；链接酶( 1 i g a s e ) 可作为链接算子，聚合 酶( p o l y m e r a s e s ) 可作为复制算子，外核酸酶( e x o n u c l e a s e ) 可作为删除算子等。 d n a 计算的基本思想是：t 0 用d n a 分子的双螺旋结构和碱基互补配对的性质，将 所要处理的问题编码成特定的d n a 分子，在生物酶的作用下，生成各种数据池 ( d a t ap 0 0 1 ) ，即问题的可能解；然后利用现代分子生物技术如聚合酶链反应 d n a 计算在两类特殊应用问题 ：的研究 ( p o l y m e r i z ec h a i nr 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 算法解决计算问题的基本思想是：以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 a t ap 0 0 1 ) ，然后按照一定的规则将 原始问题的数据运算高度并行地映射成d n a 分子链的可控的生化过程。最后，利 用分子生物技术如聚合酶链反应p c r 、聚合重叠放大技术p o a 、超声波降解、亲 和层析、克隆、诱变、分子纯化、电泳、磁珠分离等，破获运算结果。这种思想 突破了传统计算机体系结构的束缚，开创了一个新的计算空间。 从d n a 的原理来看，它与数学操作非常类似。d n a 的单链可看作由4 4 不同 符号a 、g 、c 和t 组成的串。它在数学上就像计算机中的编码“0 ”和“1 ”一样，可 表示成4 个字母的集合= a ，g ，c ，t ) 来译码信息。d n a 串可作为译码信息。酶可看 作模拟在d n a 序列上简单的计算。不同的酶相当于作用在d n a 串上的不同的算 子，如限制内核酸酶可作为分离算子；链接酶可作为链接算子，聚合酶可作为复 制算子，外核酸酶可作为删除算子等。 1 4d n a 计算研究的国内外现状、水平与发展趋势 d n a 计算的实现方式可以分为3 种：试管、表面、芯片。试管方式( t e s tt u b e b a s e d ) 就是d n a 计算所基于的生化反应是在一个或多个试管的溶液里进行，反 应时可以同时或分阶段加入所需的反应物，如各种d n a 分子、引物、缓冲液、 酶、碱基d n t p 等；表面方式( s u r f a c e b a s e d ) 就是将对应于问题解空间的d n a 分 予固定于一块经过特殊化学处理的固体表面，如胶片、塑料、玻璃、硅半导体等， 然后对表面上的d n a 分子重复进行标记、破坏、去标记等操作，最后获得运算结 果。目前，w i s c o n s i n 大学已成为d n a 计算表面方式研究的中心；芯片方式( c h i p b a s e d ) 是d n a 计算研究的最终目标。目前，d n a 计算主要是在试管和表面两 种方式下进行，试管方式主要是验证d n a 计算的可行性，而表面方式则是为d n a 计算芯片的研制作准备。 d n a 分子生物计算【15 】的研究包括：d n a 计算模型【1 6 17 1 、使用具体模型求解 问题时的d n a 计算算法【1 8 2 0 】和包括编码、分子合成、输入输出技术等在内的d n a 计算实现技术等三个方面。d n a 计算模型和d n a 计算算法设计两种密切相关【2 1 1 ， 4 硕，l 二学位论文 从d n a 计算首次求解n p 问题1 2 2 1 开始【，就备受人们关注，近十年来已涌现有许 多重要的成果 2 3 - 2 5 。以下是近年d n a 计算模型发展： 自h e a d 首先提出s p l i c i n g 模型后，已有多种d n a 计算模型提出，而且仍在不断 发展，目前d n a 计算常用的模型有：剪接系统( s y s t e m s ) 【2 6 1 、粘贴模型( s t i c k e r ) t 2 7 2 8 1 、 表面计算模型( s u r f a c e b a s e d ) t 2 9 1 、基于质粒( p l a s m i d s ) 的d n a 计算模型【3 0 】、禁止一 允许模型( f o r b i d d i n g e n f o r c i n g ) l 圳等。 剪接系统基于剪接运算，它切割双链d n a 分子并在切割处连接不同d n a 分 子的切割部分形成个新的d n a 分子。19 8 7 年，t h e a d 首先引入剪接的概念，并 利用形式语言理论分析了d n a 分子重组模型的生成能力。后来他又利用形式语言 技术给出了分子计算的抽象模型一剪接系统p 。2 0 0 1 年，y b e n e n s o n 等通过剪 接系统构造了一台可编程的有穷自动机，说明了剪接系统是计算完备的，即每个 p a s c a l 程序都可以通过合适的剪接系统来模拟，反之亦然，并证明了通用剪接 系统的存在性，即剪接运算基础上的通用可编程的d n a 计算模型的存在性【3 2 1 。现 在有关剪接系统的研究主要集中于它所产生的形式语言的性质( 如封闭性) 及其与 乔姆斯基体系中其它形式语言的关系。k a t r i ne r k t 3 3 j 利用剪接系统的高度并行性， 将布尔电路作为剪接系统的词进行模拟，在有穷时间内得到了布尔电路的值。 粘贴模型【2 7 五8 】由r o w e i s 等于第2 届d i m a c s 会上所提出，是一种计算完备、 与有限自动机理论密切相关的基于分子操作和随机访问内存的一种d n a 计算模 型。基于此模型，已成功设计出可满足性问题、集合覆盖问题、图的顶点覆盖问 题等图论问题算法【2 7 _ 2 引。上述各种基于粘贴模型的d n a 算法的基本思想为：利 用d n a 单双链特对问题的所有可能进行编码，然后对问题进行并行操作以求得 问题的解，最后通过逐步剔除那些不符合要求的解得到问题的最终解。因此，基 于该模型所设计的算法几乎均为穷举算法【2 7 也引，算法中的d n a 链数都为纯指数 阶的2 n 0 为团问题的顶点数等) 。另外，尽管基于d n a 粘贴模型可实现二进制的 各种算术运算，理论上可解决众多图论及数学上的n p 完全问题，而且在运算过 程中也不需要d n a 链的延伸和酶的作用，但其算法必须通过反复的合并、设置、 清除、分离等操作来完成。这些操作中又须通过杂交、退火和探针的设计来完成。 而由于杂交及退火的不完整性，会因此导致大量伪解出现；此外，复杂的生物操 作过程还使得最终的d n a 链长过长，以致超出现有生物技术的能力。 表面计算【2 9 】由w i s c o n s i n 大学的研究人员所提出，它通过把d n a 计算的所有 可能的结果附着在固体表面，然后通过系列杂交和酶切来得到最终结果。与试管 计算相比，表面计算有不少优点，其中最突出的特点是它与硅技术有很好的匹配 性【2 9 1 。基于表面计算模型的d n a 计算也已设计出解决一些n p 完全问题的算法， 如：最佳匹配问题【3 4 1 、最大匹配问题【3 5 l 等。l i u l 2 9 1 等一直致力于表面上的d n a 计 算，成功地解决了s a t 问题，对生物实验的手段和方法进行了完善，减少了早期 d n a 计钎在两类特殊应用问题上的研究 试管实验的差错率。随着生物芯片( b i o c h i p ) 技术的不断发展，基于此模型的d n a 计算应会变得简单和方便。但基于此模型的d n a 算法中仍然存在杂交和酶切等生 物操作，其不完整性同样会导致较多伪解的产生。更重要的是：基于表面模型的 算法与粘贴模型在求解问题时所用的方法一致，还是通过简单枚举求解问题，因 而依然无法避免算法的可扩展性过低带来的问题，即使是对中等规模s a t 或最佳 匹配问题，现有生物技术还不能为算法实现提供支持。 2 0 0 0 年，h e a d l 3 0 】提出基于质粒的d n a 计算，该模型的质粒d n a 在每一步进 行限制性内切酶剪切后，又迅速连接呈环状分子，可确保计算过程免受其它酶的 干扰，计算准确性高且稳定，它没有复杂的自身退火单链d n a 或p c r 扩增步骤造 成的麻烦，该模型在处理图论问题中，不需要直接穷举问题的所有可能，降低了 以往算法中呈指数增长的d n a 分子数。如当它用于求解最大权团问题p 6 j 时，算法 通过酶切操作，仅需逐步生成具有，z 个节点的图中所有的团而非所有2 一中可能，降 低了d n a 分子数。但算法同样不具有可扩展性，因为当问题参数过大时，过长的 d n a 分子链将会影响算法的执行。而且受该模型自身特性和种类有限的酶影响， 算术减法、乘法和除法操作难于实现。禁止一允许模型( f o r b i d d i n g e n f o r c i n g j e ) p l j 是最近出现的一种新模型，尽管该模型可实现可满足性、哈密尔顿等计算问题【j 列。 但实现该模型的计算需要一定的拓扑代数背景知识，其前景尚待进一步观察。 就d n a 计算而言，用d n a 计算求解n p 完全的图和组合优化问题的一个关 键问题是d n a 计算模型的选择。虽然d n a 计算模型一直在不断的发展，从最初 的剪接系统模型【2 6 1 发展到目前常用的剪接系统模型【26 1 、粘贴模型【2 7 2 8 】、表面计算 模型1 2 9 】、基于质粒的d n a 计算模型【3 0 】和基于图的自组模型以及最近的禁止一强 迫模型( f o r b i d d i n g e n f o r c i n g ，w e ) l 3 1 】等，这些模型在生物操作1 3 8 】所出现的伪解等方 面较最初的模型均有较大改进。但现有的这些模型均存在一定不足：基于粘贴的 d n a 计算模型能实现二进制的算术运算，理论上可解决许多n p 完全问题【2 7 , 2 8 1 ， 而且在运算过程中不需要d n a 链的延伸和酶的作用，但算法必须通过杂交、退 火和探针的设计来完成。由于杂交及退火的不完整性，会导致大量的伪解出现。 表面计算可解决一些如最佳匹配问题等n p 完全问题，但基于该模型的算法中仍 然存在杂交和酶切等生物操作，因而依然无法避免大量伪解的产生1 34 。基于质粒 的d n a 计算模型成功解决了最大权团等n p 完全问题，该模型虽没有复杂的自身 退火单链d n a 或p c r 扩增步骤造成的麻烦，可确保计算过程免受其它酶的干扰， 从而保证计算的准确性和稳定性【3 6 】，但受其自身特性的影响，该模型实现算术减 法、乘法和除法操作目前均有难度。基于图的自组模型和屈模型尽管可成功求解 小规模s a t 问题，但满足条件的图的建造有时却相当困难【3 。 为了提高d n a 计算机算法的可扩展性，扩大使用d n a 计算机算法解决难解问 题的规模，e r i cb a c h 等【2 9 】首次提出了一种将a d l e m a n 和l i p t o m 的d n a 计算模型相 结合的改进d n a 计算模型，并将传统计算机算法的基本思想应用于该模型，设计 6 硕士学位论文 了求解3 色问题和独立集问题的d n a 算法，在理论上实现了d n a 链数分别为 d ( 1 8 9 ”) 和o ( 1 6 7 ”) 的求解3 色问题和独立集问题的d n a 计算机算法。但由于使用 经典a d l e m a n 和ll i p t o m 计算模型，该模型中杂交、退火和探针的设计使得求解过 程中错解和伪解率过高，理论上，生物操作数也明显复杂得多，因而难于走向实 践。19 9 7 年，f u 等po j 应用传统串行算法设计技术，将所求问题先通过计算机做一 定变化，以改变问题的初始解空问，达到降低d n a 分子数的目的，并相应提出了 几种d n a 计算机算法：链数d ( 1 4 9 7 打) 求解可3 s a t 问题算法、链数p ( 1 3 4 5 疗) - - 着 色问题算法、d ( 1 2 2 9 竹) 的独立集问题算法，而且，这些算法的时间或操作复杂性 也均为多项式量级。但是，考虑到d n a 分予计算的特性，缩小的初始空间在用d n a 分子初始化时很难构造，使其可行性大大降低，而且，使用计算机来作d n a 计算 的部分计算工作的方式也与d n a 计算机向全自动化、无外界干预的发展趋势不符 1 3 。2 0 0 4 年，李源等1 9 j 首次将进化算法引入最大团问题的d n a 计算中，提出一种 求解最大团问题的d n a 计算机概率算法，该算法可在不显著增力 i d n a 计算时间前 提下，大大减少直接穷举方法试管中的d n a 分子数目，对于具有顶点数为3 0 左右 的团的问题，该算法相当成功，因为它可以高概率找到问题的解，而且所需迭代 的代数也不大，但对顶点数更多和连同度较大的最大团问题，该算法则很难以高 概率求得问题的解p j 。 总之，从引入d n a 计算概念以来，d n a 计算模型一直在不断发展和完善， 理论上，现有计算模型可解决多数计算上的难解问题，而且已设计出相应的d n a 计算机算法，但这些基于穷举方法的算法中普遍存在算法可扩展性过低的问题， 尽管在提高d n a 计算机算法的可扩展性研究方面，已取得一定的进展，但这些 研究仅是初步的，尚存在诸如普适性、需要人工和计算机干预、很难得到理论精 确解等种种不足，必须进行更加系统和深入的研究。由于d n a 计算机算法的不 可扩展性源于d n a 计算模型的不可扩展性。因此，尽管现在对d n a 计算具有很 好前景的预言为时尚早，但注意到近年来国内外在d n a 计算机的实际实现上的 多种进展【3 , 3 2 j ，旨在显著减少d n a 算法中d n a 链数和链长的具有良好可扩展性 的d n a 计算机模型的研究不仅具有重要的理论意义，而且是必要和迫切的。 1 5 论文主要工作 本文的主要工作为： 1 对于多处理机独立任务调度问题，采用粘贴模型的解空间和a d l e m a n 的 生物操作集，给出了一种新的该类问题的d n a 计算模型。本文首先对任务分配 的恰当的编码，以便于使用常规的生物操作及生物酶来完成解的产生及最终解的 分离，并依据分子生物学的实验方法提出了基于分子生物技术的多处理机独立任 务调度问题的d n a 算法。 2 将分治策略应用于背包问题的d n a 分子计算中，本文提出一种求解背包 问题的新的基于质粒d n a 计算机算法。本算法的d n a 链数可达到亚指数的 7 d n a 计算在两类特殊应用问题卜的研究 = = = 詈鲁皇= 皇! = = = 皇= 曼= 詈鼍= 詈詈= 昌詈= 暑詈= = = = = = = = 詈= = = ：= = = = = = = = = 皇= = = 。! ：巴皇= 詈竺! = 皇= = = = 皇= = = = = = = 詈= 暑= = = 詈皇= 暑! 詈毫= 暑皇= 皇詈皇毫= 暑皇詈鼍! = 昌皇= ! 詈詈= 皇皇! 皇 o ( 1 4 1 4 几) ，其中n 为背包问题的维数。将提出的算法与已有文献结论进行的对比 分析表明：本算法将穷举算法中所需的d n a 链数从0 ( 2 ”) 减少至o ( 1 4 1 4 ”) ，因此利 用本d n a 计算机算法在试管级水平上能将可破解的背包公钥的维数从6 0 提高到 12 0 。 1 6 论文组织结构 本学位论文共有4 章，其内容具体安排如下： 第1 帝为绪论，简要的介绍了本文的选题日的、研究意义、同内外研究进展、 主要工作和组织安排；第2 章为预备知识，简要的介绍包括以下必要的理论背景： 任务调度问题、n p 完全问题、d n a 计算模型、计算复杂性概念；第3 章采用粘 贴模型的解空间和a d l e m a n 的生物操作集，提出了多处理机独立任务调度问题的 d n a 计算机算法；第4 章设计了分治策略应用于背包问题的d n a 分子计算中， 本文提出一种求解背包问题的新的基于质粒d n a 计算机算法。 1 7 小结 本章为整个论文的绪论部分，着重介绍了本文的目的、意义、研究背景、主 要工作以及全文结构的组织安排。 第l 节简要介绍了本文的目的，本文的目的是利用生物计算机解决多处理机 独立任务调度问题；在质粒模型下，利用分治策略，对缩小背包问题d n a 解空 间所做的尝试。第2 节简单介绍包括以下必要的理论背景。第3 节提出了多处理 机独立任务调度问题的d n a 计算机算法。第4 节一种求解背包问题的新的基于 质粒d n a 计算机算法。 8 硕士学位论文 2 1 任务调度问题 第2 章相关理论背景 网格环境中的应用程序可以由多个子任务构成的集合来描述，一个网格应用 程序可以表示为一个d a g ，g = ( t ，e ) ，其中t 是节点集，e 是有向边集。一个节 点t 在d a g 中表示一个任务，一个有向边用一个节点对( t i ，t j ) 表示，前一个节点 称为父节点，后一个节点称为子节点。无父节点的节点称为入口，即应用程序的 开始：无子节点的节点称为出口，即应用程序的结束。图l 给出了一个d a g 任 务图示例，其中， i x 是任务的序号，括号内的数字为计算量参数。 图2 1d a g 任务图 一个在有m 个处理单元和任务图g = ( t ，e ) 之上的调度是一个函数f ，f 将每 个任务以某个特定的开始时间映射到某个处理单元。从形式上，一个调度可描述 为：f it 一 l ，2 ，m ) 【0 ，1 ，如果存在v t ，f ( v ) = ( i ，t ) ，则表示任务v 被调 度到处理单元p i 上，且从时间t 开始执行。函数f 可以表示成如下定义的g a n t t 图：g a n t t 图用于直观地表示所有任务的开始时间和完成时间。在一个g a n t t 图中， 有一个分布系统的处理单元表，对于表中每个处理单元都有一个任务分配表，即 将分配到这个处理单元的所有任务按执行时间排列成表，其中包括开始时间和结 束时间，分别用s t ( t i ，p ) 和f t ( t i ，p ) 表示。实际上，g a n t t 图是一个四元表：g a n t t ( p i ，t j ，s t ( t j ，p i ) ，f t ( t j ，p i ) ) 其中，p i ( i = l ，2 ，m ) 为处理单元；t j ( j = l ，2 ，一，n ) 为分配至l j p i 上的任务；s t ( t j ，p i ) 为t j 在p i 上的开始时间；f t ( t j ，p i ) 为t j 在p i 上的结束时间。 一个任务调度系统的最大调度长度s l ( s c h e d u l e l e n g t h ) 定义为所有处理机p i 中的，调度的目标就是要将任务适当分配到处理机并协调任务之间的执行顺序， 使得并行执行时满足并行任务之间的优先约束关系，而且s l 最小。 9 d n a 计算神：两类特殊应用问题e 的研究 任务调度问题属于n p 完全问题，没有最优解。任务调度问题的最常见的目 标函数就是完成时i t j ( m a k e s p a n ) 。用c p 来表示调度算法的综合性能指标，该指 标主要通过三个参数( m a k e s p a n ，i d l et i m e ，o v e rd e a d l i n e ) 来表示。计算公式如下： 其中，f ，6 0 和0 分别表示m a k e s p a n ，i d l et i m e ，o v e rd e a d l i n e ，而w i ，w m 和 w o 分别表示它们的权值。对于一族给定的权值，c p 值越小，算法的综合性能 越好。 调度器取得新下达任务的描述，按相关说明将其划分为一组子任务，并计算 得出各个子任务的最早最迟完成时间，生成子任务对象。导入当前所管辖的计算 资源的信息数据，包括计算资源本身的参数、当前正在运行的任务、任务队列情 况等。根据经过划分和计算的子任务的需求，以及计算资源的现有条件，按一定 规则将各个子任务调度到适当的计算资源。在调度的过程中，如果发生某个或某 些计算资源无法完成任务而导致整个任务无法在指定时间内完成的情况，则需要 进行调整。在执行任务的过程，由计算资源及时记录日志信息，并反馈给调度系 统。 一般从调度策略本身考虑，可将任务调度分为静态调度和动态调度两类。静 态调度的主要特点是实现简单，但调度质量不佳。动态调度的主要特点是能充分 发挥各资源的处理能力，但实现起来比较复杂，可能由于任务的动态调整影响个 别任务的执行效率。目前出现了将静态调度与动态调度相结合的混合调度方法， 可以兼顾二者的优越性。 调度器的组织分为集中式、分层结构和分布式的三种。集中式调度器易于实 施和管理，易于实现资源的协同分配，缺点是维护代价高，难于实现容错。分层 调度器易于实现扩展和容错，易于资源的协同分配，但不支持资源地域自治和多 种调度策略。分布式调度器易于扩展和容错，支持资源自治和多种调度策略结合 使用，但不易于管理和资源协同分配。 网格任务调度与负载平衡是提高网格计算环境可用性和效率的关键问题， n i m r o d g 、a p p l e s 和c o n d o r g 等网格任务调度器都基于特定的调度策略，适 用于特定情况的任务调度。g l o b u s 任务调度方法基本是轮循方式的；n i m r o d g 采用应用程序级的基于微观经济模型的调度方法，适用于各个资源的定价机制都 很完整的情况；a p p l e s 采用应用程序级的调度方法，用网络气象服务监测资源性 能的动态改变情况作为任务调度的依据，信息维护代价较高，且要求各节点间的 连接都具有监测机制：c o n d o r g 要求每个资源代理周期性广播其可提供的服务， 客户代理广播其需求，匹配器执行集中式的任务到资源之间的匹配调度。 调度策略可分为固定的和可扩展的，固定式调度又可以分为面向系统的和面 向应用程序的，前者的调度目标是最大化系统吞吐量，后者的调度目标是最优化 应用程序完成时间。可扩展调度策略又分为a d h o c 类型和结构化类型，前者执行 l o 硕十学位论文 固定调度策略，但允许系统外部实体修改调度结果，而后者允许外部代理修改系 统任务调度策略。从系统状态估计的支持上，可将网格任务调度分成有状态预测 和无状态预测两类，预测方法包括启发式方法、基于经济模型的方法和机器学习 方法。无预测的方法包括启发式方法和概率分布方法。各种调度策略各有优缺点， 在各种网格系统中都有不同的组合使用。为了尽可能提高网格计算资源的利用率， 应该尝试设计面向某个具体应用或者某类应用的任务调度模式。 2 2n p 完全问题 n p 完全性是计算复杂性理论中的一个重要概念，它表征某些问题的固有复 杂度。一旦确定一类问题具有n p 完全性时，就可知道这类问题实际上是具有相 当复杂程度的困难问题。 探讨各种各样问题是否具有n p 完全性，研究n p 完全问题的处理方法，这 对许多实际问题的算法设计和分析很有帮助，并与n p # = p 等理论问题密切相关。 人们在这方面开展了大量研究工作，己逐渐形成一个专门性的理论n p 完全性 理论。 对于一个问题，如果存在一个图灵机，对这个问题的任何实例，都能给出回 答，那么这个问题就称作可解的；如果存在一个图灵机，又存在一多项式p ，在 给定问题的实例后( 设1 1 是给定实例在0 、1 编码下的长度) ，这个图灵机能在p ( n ) 步内给出回答，那么该问题称作多项式时问可解的。 图灵机可分为确定型和非确定型。确定型图灵机在多项式时间内可解决的全 部问题类记作p 。非