（计算机科学与技术专业论文）带约束路由问题的dna计算研究与应用.pdf

r e s e a r c ha n da p p l i c a t i o no nd n a c o m p u t i n gf o r r o u t i n gp r o b l e m sw i t hc o n s t r a i n t b y h u a n gq i x i n b e ( h u n a nu n i v e r s i t y ) 2 0 0 5 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g 1 n c o m p u t e rs c i e n c ea n dt e c h n o l o g y i nt h e g r a d u a t es c h o o i o f h u n a n u n i v e r s i t y s u p e r v i s o r a s s o c i a t ey a n gl e i p r o f e s s o rl ik e n l i m a y ，2 0 1 1 帅5 6唧6m 8 0 9椰胛y 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者虢孝施 训，嗍：伽年尹眇日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 作者签名： 导师签名： l 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 期：今秒f | 年f 月? 伊日 期： z 矿f1 年罗月) 9 日 j 带约束路由问题的d n a 计算研究i 应用 摘要 带约束路由算法问题一直是通信领域的热点问题。然而，多数特殊约束路由 问题为n p 完全问题，除非n p = p ，否则无法给出多项式时间算法。对于这些问题， 已经出现各种伪多项式算法，但这些算法必须在一定的限制条件内才能保证算法 时间效率。1 9 9 4 年a d l e m a n 博士首次提出了d n a 计算的概念，并设计了d n a 算法成 功解决了7 个顶点的哈密尔顿路径问题，显示了d n a 计算解决复杂问题的巨大潜 力。由于路由问题的特点，可以利用d n a 计算高度的并行性将问题的时间复杂度 转化为d n a 分子链的空间复杂度，从而在多项式时间内得出问题的精确解。本文 提出一套通用的路由问题的d n a 编码方案，并对两种特殊的带约束路由问题进行 d n a 计算算法设计。 指定结点路由问题可一般性地定义为带指定结点约束的最短路径问题，是一 个n p 难问题。本文提出一种将电子计算机算法与d n a 计算算法相结合的方法求解 指定结点路由问题。算法由转化算法，源宿结点搜索切割算法，转化图结果搜索 算法和结果读取算法共四个子算法组成。分析结果表明：执行算法的电子计算机 部分可显著减少参与生化反应的d n a 链的数量，在试管内d n a 链数恒定的情况 下，增加了可解决问题的结点和链路的规模。算法的d n a 计算部分对最短路径进 行并行搜索，可以在多项式时间内得出问题的解。 链路分离路径对可用于保障网络传输稳定性，增加传输带宽和实现负载均衡。 本文对计算链路分离路径对的电子计算机算法l i d o m p a 算法进行算法优化改进， 提出基于d n a 计算的高效并行算法。该算法主要由最短路径搜索算法，路径分类 算法，链路分离路径构造算法组成。在d n a 计算中，可以将l i d o m p a 算法中多个 需要指数时间复杂度的操作改进为多项式时间。 本文主要探讨了d n a 计算针对两种特定约束路由问题的算法，并为其它路 由问题的d n a 计算编码和基本操作提供了通用方案。只要未来关于d n a 计算的 生物技术走向成熟，d n a 计算完全可以在路由问题中发挥更大的作用。 关键词：d n a 计算；指定结点路由；链路分离路径；n p 完全问题 u r o u t i n ga l g o r i t h m sw i t hc o n s t r a i n t si sa l w a y sah o ti s s u ei nt e l e c o m m u n i c a t i o n f i e l d m o s tr o u t i n gp r o b l e m sw i t hs p e c i a lc o n s t r a i n t sa r en p - c o m p l e t ep r o b l e m s ， h o w e v e r t h e y c a nb es o l v e di np o l y n o m i n a lt i m eo n l yi fn p = p t h e r ea r es e v e r a l p s e u d o p o l y n o m i n a lt i m ea l g o r i t h m sf o rt h e s eq u e s t i o n s ，b u tt h e s ea l g o r i t h m sm u s tb e c o n f i n e di nr e s t r i c e t e dc o n d i t i o n sa st oe n s u r et h et i m e e f f i c i e n c y d r a d l e m a n p r o p o s e dt h ec o n c e p to fd n ac o m p u t i n gf i r s t l yi n19 9 4 ，a n dh ea l s os o l v e da7n o d e h a m i l t o np a t hp r o b l e mb yad n a a l g o r i t h m ，w h i c hs h o w sh u g ep o t e n t i a lc a p a c i t yo f s o l v i n gc o m p l i c a t e dq u e s t i o n sb yd n ac o m p u t i n g b e c a u s e o ft h e s p e c i a l i t y o f r o u t i n gp r o b l e m s ，t h et i m ec o m p l e x i t yo ft h e s ep r o b l e m sc a nb ec o n v e r tt os p a c e c o m p l e x i t y o fd n as t r a n d st a k e a d v a n t a g e o fh i g h l y p a r a l l e l i s m o fd n a c o m p u t i n g s ow ec a nw o r ko u te x a c ts o l u t i o n sf o rt h e s eq u e s t i o n si np o l y n o m i n a l t i m e t h i sp a p e rp r o p o s e dac o m m o n l yu s e dd n a c o d i n gs c h e m ef o rs o l v i n gr o u t i n g p r o b l e m s ，a n dw ea l s ow o r k e do u ta l g o r i t h m sf o rt w or o u t i n gp r o b l e m sw i t hs p e c i a l c o n s t r a i n t sb yd n a c o m p u t i n g r o u t i n gp r o b l e m w i t he x p l i c i tn o d ec o n s t r a i n tc a nb e g e n e r a l l yd e f i n e da s s h o r t e s tp a t hp r o b l e mw i t he x p l i c i tn o d ec o n s t r a i n t a na l g o r i t h mt h a tc o m b i n e dt h e e l e c t r o n i cc o m p u t e rw i t hd n a c o m p u t i n gi sp r o p o s e dt os o l v et h er o u t i n ga l g o r i t h m s s a t i s f y i n ge x p l i c i tn o d ec o n s t r a i n ti nt h i sp a p e r t h ea l g o r i t h mc o n s i s t so ff o u r s u b a l g o r i t h m s ：g r a p h t r a n s f o r m a l g o r i t h m s ，s t a r t - e n dp o i n t s e a r c ha n dc u t a l g o r i t h m s ，r e s u l ts e a r c ha l g o r i t h m sf o rt r a n s f o r m e dg r a p h ，r e s u l tr e a d i n ga l g o r i t h m s t h et h e o r e t i ca n a l y s i ss h o w st h a tt h eu s a g eo fe l e c t r o n i cc o m p u t e rp a r to ft h e a l g o r i t h mc o u l d c u td o w nt h en u m b e ro fn o d e sa n dl i n k s s h a r p l y s ot h a tt h e c o r r e s p o n d i n gd n av o l u m es t r a n d sc o u l db er e d u c e d a n dt h es c a l eo fn o d e sa n d l i n k sw h i c hc a nb ys o l v e db yd n a c o m p u t i n gi sa m p l i f i e da sl o n ga st h ed n a s t r a n d s n u m b e ri sc o n s t a n ti no n et e s tt u b e t h ed n ac o m p u t i n gp a r to ft h ea l g o r i t h m sc a n p a r a l l e ls e a r c hf o rt h es h o r t e s tp a t ha n dw o r ko u tr e s u l ti np o l y n o m i n a lt i m e l i n k - d i s j o i n tp a t h s c a nb eu s e dt oe n s u r et h e s t a b i l i t y o fb u s i n e s s t r a n s m i s s i o n ，i n c r e a s et r a n s m i s s i o nb a n d w i d t ha n da c h i e v en e t w o r kl o a db a l a n c i n g a h i g he f f i c i e n c yp a r a l l e la l g o r i t h mi sp r o p o s e d i nt h i s p a p e rb yi m p r o v i n g t h e e l e c t r o n i cc o m p u t e ra l g o r i t h ml i d o m p ai n t od n ac o m p u t i n ga l g o r i t h mf o rs o l v i n g i i i a l g o r i t m sp r o p o s e di nt h i sp a p e rw i l lo p r i m i z et h et i m ec o m p l e x i t yo ft h eo p e r a t i o n s f r o me x p o n e n t i a lt i m et op o l y n o m i n a lt i m eo nd n a c o m p u t i n g w ed i s c u s s e dd n a c o m p u t i n ga l g o r i t h m sf o rt w or o u t i n gp r o b l e m sw i t hs p e c i a l c o n s t r a i n t sa n dp r o p o s e da nu n i v e r s i a ld n ac o d i n gs c h e m ef o r s o l v i n gr o u t i n g p r o b l e m s a sl o n ga sb i o t e c h n o l o g yo fd n a c o m p u t i n gb e c o m em a t u r ee n o u g h ，t h e d n a c o m p u t i n gw i l lp l a yab i g g e rr o l ei ns o l v i n gr o u t i n gp r o b l e m s k e yw o r d s ：d n ac o m p u t i n g ；e x p l i c i tn o d e c o n s t r a i n t ；l i n k d i s j o i n tp a t h s ； n p - c o m p l e t e ri_i 硕l 学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引v i i 附表索引v i i i 第1 章绪论1 1 1 研究目的与意义一l 1 2 约束路由技术的研究背景2 1 3d n a 计算研究背景4 1 4 论文主要工作4 1 5 论文组织结构5 第2 章路由问题的通用d n a 计算模型一6 2 1d n a 计算模型基本概念6 2 1 1d n a 计算复杂性概念一6 2 1 2d n a 计算模型6 2 2 路由问题的d n a 计算通用方案8 2 2 1 路由问题的通用d n a 编码方案和生物操作8 2 3 小结1 2 第3 章指定结点路由问题的d n a 计算算法：1 3 3 1 指定结点路由问题描述1 3 3 2 指定结点路由问题算法1 4 3 2 1 算法电子计算机部分1 5 3 2 2 算法d n a 计算部分18 3 3 指定结点路由问题算法性能分析2 1 3 3 1 电子计算机算法复杂度分析2 l 3 3 2d n a 计算算法复杂度分析一2 2 3 4d n a 编码实现2 3 3 4 1d n a 编码方案2 3 3 4 2d n a 编码长度分析2 4 3 4 3 计算实例2 4 3 5 小结2 5 v 4 4 链路分离路径对问题算法一3 3 4 4 1p 2 路径筛选算法3 3 4 4 2l i d o m p a 构造c o s 方法简介3 8 4 4 3d n a l i d o p a 算法构造c o s 3 9 4 5 算法复杂度比较4 5 4 5 1l i d o m p a 算法复杂度分析4 5 4 5 2d n a l i d o p a 算法复杂度分析4 6 4 6 计算实例4 7 4 6 1d n a l i d o p a 算法实例d n a 编码方案4 7 4 6 2d n a l i d o p a 算法实例算法实现4 8 4 7 小结5 5 结论5 6 参考文献5 8 致 射6 2 附录a ( 攻读硕士期间发表论文目录) 6 3 附录b ( 攻读硕士期间参加的科研项目) 6 4 v i 硕十学位论文 插图索引 图1 1 无结点分离路径对的拓扑3 图2 1 结点编码方案一9 图2 2 链路编码方案1 0 图2 3 路径长度比较1 0 图2 4s u p p l e m e n t o r o 操作1 1 图3 1 指定结点路由问题组网图1 4 图3 2 指定结点转化图1 6 图3 3 删除冗余链路转化图1 7 图3 4 转化图解路径2 5 图3 5 原图最终解路径2 5 图4 1 链路分离路径对2 8 图4 2 结点填塞d n a 2 9 图4 3 链路填塞d n a 一3 0 图4 4d n a 链中结点和链路荧光染色3 0 图4 5g 向g 转化3 5 图4 6 荧光筛选两条相连路径d n a 模拟一4 1 图4 7 计算实例拓扑4 7 图4 8g 生成操作4 9 图4 9p 2 路径分类5l 图4 1 0p 1 和最构成的最优c o s 5 2 图4 1 1 尸l 和& 构成的最优c o s 5 3 图4 1 2 尸l 和最构成的最优c o s 5 4 图4 1 3 最优链路分离路径对：5 4 v h 带约束路由问题的d n a 计算研究与应用 附表索引 表3 1 原图与转化图映射关系表1 8 表3 2 转化图中结点d n a 编码表2 3 表3 3 转化图中权值d n a 编码表2 4 表3 4 链路d n a 双链编码实例：2 4 表4 1d n a l i d o p a 算法实例结点编码4 7 表4 2d n a l i d o p a 算法实例链路编码4 8 v i i i 硕l ：学位论文 1 1 研究目的与意义 第1 章绪论 路由算法问题是网络技术中的重要问题。尽管路由器、交换机在处理速度、 带宽容量等方面不断提升，但随着网络规模的不断增长，网络特性的多样化以及 网络用户的爆发性增长，对路由算法性能的要求也越来越高。传统的路由转发采 用“尽力而为”的策略，然而，随着网络结构的复杂化，“尽力而为”的策略会造成 网络资源的不合理分配，而且，这种算路策略无法满足各种约束条件，无法提供 高质量的网络传输。随着用户对传输质量，网络安全性等方面的要求进一步提高， 一些例如跳数限制，延迟限制，主备路径传输，指定必经路由结点等约束条件被 加入到路由算路策略当中。 尽管带约束路由能够满足用户对网络服务质量的特殊要求，但是已有研究表 明：在路由问题中加入一些约束条件后算路问题即成为n p 完全问题【l 3 】。众所周 知，除非n p = p ，否则这些问题在电子计算机上不存在多项式时间的解。于是求解 带约束路由问题的算法被转化为求解特定情况下的伪多项式时间算法【4 5 】。这些 算法往往限制条件比较苛刻，不能被普遍采用。 在m p l s 或a s o n 网络中，由于网络运营商对于业务路径控制的需要以及各 个网络结点交换能力的差别等原因，在路由计算中指定一个或多个必经结点有着 现实的需求。而且，该问题的算法在交通运输，电力输送等领域都有着很高的应 用价值。然而，指定结点路由问题是个n p 难问题，虽然已有相关文献给出了该 问题的伪多项式时间算法，但除某些特定情况外，算法时间效率仍无法保证【p 7 1 。 链路分离路径是实现业务传输可靠性的重要方法，所谓可靠性包括路由的鲁 棒性和负载均衡两个方面【8 l 。鲁棒性是指当传输业务的路径因故障而中断时，网 络能在不影响用户使用甚至用户察觉不到的情况下将业务恢复。例如，为不影响 通话质量，网络语音传输的中断应该不超过2 0 0 m s ，因此语音业务中断后必须在 2 0 0 m s 内完成新路径的建立。负载均衡是指在网络传输中实现带宽，交换节点， 链路等资源的均匀分配，从而避免拥塞，提高网络吞吐量。链路分离路径的方法 既可用于提高路由的鲁棒性，又可用于负载均衡。在通信的源和宿结点之间除用 于通信的主路径外，另外计算一条或多条备用路径，当主路径失效后，可将业务 倒换到备用路径传输，从而减少重新算路所造成的时间损耗，实现了鲁棒性。对 同一业务通过两条或两条以上的分离路径进行传输，通过业务数据在多条路径上 的复用，即可实现带宽的均匀分布，实现了网络负载均衡。并且，通过这种方法 带约束路由问题的d n a 计算研究与应用 传输，网络窃取者在一条链路上仅能获取部分传输数据，难以恢复出所有通信信 息，还可用于提高网络的安全性。然而，由于计算最优链路分离路径的算法复杂 度很高，难以用于大规模的网络拓扑。 针对以上两种特殊的约束路由问题，本文设计出d n a 计算的算法实现。由 于d n a 计算的高度并行性，为约束路由问题多项式时间内求解提供了可行性。 1 9 9 4 年美国南加州大学a d l e m a n 博士首次提出了d n a 计算的概念，他利用d n a 分子双螺旋结构，通过生物分子生化反应完成d n a 计算，成功求解了7 个顶点 的h a m i l t o n 路径问题【9 】。巨大的存储能力和海量的并行运算能力是d n a 计算的 最大优势，从理论上讲，这种结构可以克服电子计算机存储量小与并行度不高的 不足【l 们。而且，随着d n a 计算相关的生化操作走向成熟( 如操作自动化、误码率 低、链长适中等) ，d n a 计算的实际应用将逐步成为现实，并且d n a 计算的造价 将可能远低于现有的基于v l s i 的超级计算机【1 1 , 1 2 】。现有的生物技术可以在一个 测试试管中容纳1 0 1 8 条d n a 链，也即它可以使10 1 8 位数据以并行的方式进行运 算，因此，d n a 计算模型可以提供相当于1 0 1 8 个处理单元的并行性和o ( 10 1s ) 规 模的存储空间。截止到2 0 11 年，世界上最快的超级计算机，我国国家超级计算天 津中心安装的“天河1 a ”在1 0 0 0 s 内能并行处理大约2 5 7 l0 1 6 位的信息，相比之 下，d n a 计算中耗时最长的“抽取”操作在1 0 0 0 s 内可在一根试管中并行处理1 0 1 8 位的数据，和造价昂贵的超级计算机处理速度为相同数量级。并且d n a 计算存 储密度非常巨大，大约为磁带的1 0 1 2 倍【l3 1 。尽管对于d n a 计算将来的前景，目 前科学界还没有明确地给出，但由于它在科学计算、生物分子学以及医疗等方面 所展现的巨大潜力，其未来的研究前景仍然相当可期。 在本文中，首先对指定结点路由问题进行分析，采用电子计算机将问题转化 为更适合d n a 计算实现的模型，即删除网络中不必要的链路和结点，从而提高 了d n a 计算可应用的网络拓扑规模。在d n a 计算部分，根据指定结点路由问题 的特点，将a d l e m a n l i p t o n 模型生物操作进行扩展，并且设计出适合路由问题的 通用高可靠性编码方案，最终给出指定结点路由问题的d n a 计算算法。对于最 短链路分离路径对问题，本文首先对已有的电子计算机算法进行了分析，已有算 法虽然能在多种复杂网络拓扑中找到最短链路分离路径对，但由于算法存在多个 指数级时间复杂度的步骤，难以实际应用。针对该问题，本文提出了相应的d n a 计算算法，分析表明，通过本文的算法，该问题的多个步骤的时间复杂度均已降 为多项式级。 1 2 约束路由技术的研究背景 在通信网络发展的初期，存在着网络规模小，带宽容量低，服务单一等问题。 随着网络通信技术的发展，网络已逐步向传输高速化，服务多样化，网络一体化， 2 硕1 二学位论文 管理智能化方向发展。为适应网络发展中的新需求，针对各种约束的路由算法应 运而生【1 4 , 1 5 。 约束路由技术是在各种约束条件的限制下的路由计算，它从q o s 路由演化而 来。为提高业务传输服务的质量，q o s 路由往往从延迟、跳数、丢包率等方面出 发，对路由进行约束。除q o s 路由外，实际应用中仍存在其它约束条件，其它约 束路由对q o s 路由进行了扩展，其主要目标是： ( 1 ) 选择能够满足一定服务质量要求的路由； ( 2 ) 避免拥塞，改善网络的效用； ( 3 ) 提高网络的利用率。 通过约束路由算法算路时，不仅仅考虑网络的拓扑结构，还要考虑特定的约 束条件。因此，约束路由算法得出的并不一定是一条传统意义上的最短路径，而 是综合了所考虑的约束条件后的一条或多条最优路径。例如，本文中指定结点约 束的路由问题的结果路径必须包括所有指定必经结点，而最短链路分离路径对问 题则要求两条成对的路径链路相互分离。 指定结点路由问题不同于一般的q o s 约束，是一种松散指定路由约束【7 , 1 6 , 1 7 l 。 未 为保证算法的时间效率，目前实际应用中的系统要么必须指定整条路径，要么至 少指定路径经过所有指定结点的顺序。实际应用中，指定必经结点可以满足业务 监测、负载均衡等需要，而人为指定结点顺序并无意义。而且，按照人为指定的 结点顺序并不能保证得到经过所有指定结点的最短路径。 分离路径主要有两种情况：结点分离和链路分离。结点分离路径是指相同源 ， 和宿的多条路径除源宿结点外，不存在其它共用结点。显然，结点分离路径一定 是链路分离路径，而且各条路径独立性高，可靠性好。然而，受网络拓扑的影响， 往往很难找到两条或两条以上的结点分离路径，例如图1 1 中，源结点为v l j 宿结 点为1 ，7 。尽管源和宿结点间存在多条可用路径，但仍无法找到两条结点分离路径。 7 图1 1 无结点分离路径对的拓扑 链路分离路径是指相同源和宿之间的多条路径互相不存在共用链路。尽管相 对于结点分离路径，链路分离路径可靠性略低，但由于其受网络拓扑影响较小， 实用性更强。例如，在上图1 1 中虽然没有结点分离路径，却存在多条链路互相分 带约束路由问题的d n a 计算研究与成用 离的路径。本文主要针对链路分离路径进行研究，由于在实际应用中使用两条分 离路径的情况最为普遍，本文仅考虑寻找两条最优链路分离路径的情况，将这两条 链路分离路径的组合称为最优链路分离路径对。 1 3d n a 计算研究背景 从1 9 4 6 年第一台电子计算机诞生到现在，主要应用的计算机都是基于电子结 构的。但d n a 计算却是一种基于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 链作为运 算的结果。利用d n a 计算解决问题的步骤一般如下：对所要求解的问题进行编 码，把问题映射成d n a 分子链，然后在d n a 溶液的试管里，利用一些生物酶与 d n a 分子的生化反应作用，生成各种数据池( d a t a p 0 0 1 ) ，然后按照一定的规则将 所求问题的数据运算高度并行地映射成d n a 分子链的可控的生化过程，并生成 最终的试管，最后检测最终试管，提取问题的解。 引入d n a 计算概念以来，d n a 计算模型一直在不断发展和完善，理论上， 现有计算模型可解决多数计算上的难解问题，而且已设计出相应的d n a 计算算 法。但到目前为止许多算法还存在诸如可扩展性过低、需要人工和电子计算机干 预、很难得到理论精确解等种种不足，因此必须进行其进行更加系统和深入的研 究。目前国内外在d n a 计算的研究上已做了大量相关的工作，并取得了一定的 进展，这些工作的研究对象包括：d n a 计算模型1 1 $ , 1 9 】、使用具体模型求解问题时 的d n a 计算算法【2 0 , 2 1 】、可扩展性研究【2 2 】等等。 1 4 论文主要工作 本文是在杨磊老师和李肯立老师的指导下完成的，本文的主要工作为： 1 提出了针对路由问题的通用通用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 计算分子链含量恒定的情况下，可显著增加d n a 计算可处理的网络拓扑规模。 4 的操作降为多项式级。 1 5 论文组织结构 本学位论文共有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 计算在多项式时间复杂度下解决了该问题。 5 带约束路由问题的d n a 计算研究与应用 第2 章路由问题的通用d n a 计算模型 2 1d n a 计算模型基本概念 2 1 1d n a 计算复杂性概念 计算复杂性理论是用来研究算法有效性和待解决问题难度的一种工具，是分 析问题和算法以及提高问题计算效率的理论基础1 2 引。空间复杂度和时间复杂度是 衡量一个算法优劣的主要标准。算法的复杂度是决定算法成本的主要方面，算法 复杂度越高，则该算法的计算成本越高；相反，算法复杂度越低，该算法的计算 成本越低。为衡量算法的复杂度，一般通过计算解决问题所使用的时间或空间资 源来决定，亦即时间或空间资源的耗费情况反映了算法的时间复杂度和空间复杂 度。而且需要指出的是，所需要求解问题的规模也对算法复杂度起到至关重要的 作用，因此，可以定义一个以需解决问题的规模作为输入数据量，时间或空间消 耗量作为输出数据的函数，用来度量该算法的时间或空间复杂度，使用图灵机给 出其定义【2 4 j ： 存在确定型图灵机可以在多项式时间内解决的问题，该类问题属于 p ( p o l y n o m i a l ) 问题。所有其解可以在确定型图灵机的多项式时间内验证的问 题，或者等效的说，那些可以在非确定图灵机上在多项式时间内找出解的问 题，称为n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 问题。如果问题q 满足以下两个条件： 第一，它是n p 问题。第二，对于任意的n p 问题，都可以在多项式时间规约到q ， 则称此类问题为n p 完全( n p c o m p l e t e ) 问题。如果有一类问题，它满足n p 完全问 题定义的第二个条件，但不一定满足第一个条件，则称这类问题为n p 难( n p h a r d ) 问题【2 3 1 。 d n a 计算的本质是将传统电子计算机求解n p 完全问题或n p 难问题的时间代 价转换为d n a 计算的空间代价即生物分子数目代价。因此，在基于穷举的d n a 计 算算法中，图灵机算法中指数阶的时间转化成了d n a 计算算法中的指数量级的 d n a 链数，相应地，在d n a 计算可处理的问题规模内，d n a 计算可以在多项式时 间内得到n p 完全问题或n p 难问题的解，以下将介绍相关d n a 计算模型。 2 1 2d n a 计算模型 、d n a 算法解决计算问题的主要思路是：使用d n a 特有的双螺旋结构和固定的 碱基配对规则，使用碱基或碱基对组成编码，把要计算的问题映射为d n a 编码序 列，然后使用试管或其他器具作为载体，利用生物化学新技术，使用各种生物酶 6 输入输出技术等在内的d n a 计算实现技术等三个方面。其中，d n a 计算模型的发 展尤为迅速。 剪接系统模型( s p l i c i n gs y s t e m s ) 是由h e a d 在1 9 9 2 年首先提出来的【2 9 1 。该模型 基本思想是，首先从d n a 分子的某个位置将其断链，然后将断链后的d n a 分子运 用生化反应重新连接。h e a d 还给出了一种形式语言，并从理论上分析了d n a 计算 剪接系统模型的可行性，并且使用该形式语言给出对于剪接系统模型的形式化定 义。 粘贴模型是r o w e i s 等人在1 9 9 6 年所提出一种使用有限自动机部分理论、计算 可行性完备、拥有随机内存访问能力d n a 计算模型 3 0 , 3 1 】。d n a 分子单链和双链 混合编码是粘贴模型的特点，双链表示二进制中的l ，而单链则表示0 。从而使得 单双链的d n a 分子编码与二进制数一一对应起来。 ： 表面计算模型是w i s c o n s i n 大学的研究人员所提出来的，与其它计算模型使用 试管不同，该模型将可能的d n a 链附着在固体表面，然后使用各种生物酶和变温 变压等技术最终得到结果d n a 链【3 2 1 。与使用试管的d n a 计算模型相比表面计算模 型可以与硅技术具有良好的交叉性。 禁止一允许模型( f o r b i d d i n g e n f o r c i n g ) 3 3 1 是最新提出的一种d n a 计算模型，可 满足性问题，汉密尔顿问题等问题的算法均可通过该模型进行算法设计【3 引。但。 实现该模型的计算需要拓扑代数的知识，而且其实际应用仍然存在很多困难。 1 9 9 5 年，l i p t o n 提出了a d l e m a n l i p t o n 模型【3 4 1 。此后，该模型受到广泛关 注，并被用来解决了团，顶点覆盖和集合覆盖等n p 完全问题【36 1 。由于该模型已 被实践检验，并且适合路由问题计算，因此本文主要采取扩展的a d l e m a n l i p t o n 模型作为d n a 计算模型。在该模型中，四种碱基被表示为字母表 彳，c ，r ，g ， 一个含d n a 链的试管可以看作一个编码集，给定一个试管，a d l e m a n l i p t o n 模 型中的d n a 操作可描述如下【3 5 】： ( 1 ) 抽取( e x t r a c t ) ：给定试管聊一个短的d n a 单链z 。抽取操作有：+ ( 冗刁和 - ( 瓦z ) 。+ ( 瓦z ) 表示丁中所有包含i s 作为子链的d n a 分子链。( 丁，z ) 表示r 中所有不包 含z 作为子链的d n a 分子链。 ( 2 ) 合并( m e r g e ) ：给定试管r l 和乃，操作u ( 丁l ，死) = r iu 孔表示将试管r l 和疋合 并到一根试管中而不改变r l 和死中的任何链。 ( 3 ) 检狈l j ( d e t e c t ) ：给定试管丁，如果丁中至少包含一个d n a 链，贝j j d e t e c t ( 乃返回 ”y e s ”，否则，返回”n o ”。 7 带约束路由问题的d n a 计算研究与应用 ( 4 ) 复制似m p l i f y ) 给定试管丁，操作a m p l i f y ( l 丁1 ) 将r 中的所有d n a 链复制到 r l 。 ( 5 ) 添加( a p p e n d ) ：给定试管r 和一个短的d n a 链z ，该操作a p p e n d ( 瓦z ) 将z 添加到丁中每个链的末尾。 ( 6 ) 5 限制性粘性切割( 5 c u t ) ：给定试管r 和一个短的d n a 单链z ，该操作 5 7 c u t ( t , z ) 使用限制性内切核酸酶对丁中含z 的d n a 双链从z 的5 端进行粘性切割， 使其断链成具有两条悬挂的5 端的d n a 链。 ( 7 ) 3 限制性粘性切割( 3 - c u t ) ：给定试管丁和一个短的d n a 链z ，该操作 3 c u t ( t , z ) 使用限制性内切核酸酶对丁中含z 的d n a 双链从z 的3 端进行粘性切割， 使其断链成具有两条悬挂的3 端的d n a 链。 ( 8 ) 丢弃( d i s c a r d ) ：给定试管丁，这一操作d i s c a r d ( 乃将把试管丁中溶液丢弃。 ( 9 ) 读取( r e a d ) ：给定试管丁，该操作r