（计算机软件与理论专业论文）多序列同步比对算法研究.pdf

华中科技大学硕士学位论文 摘要 多序列比对问题是根据已知的给定的字符问的相似程度标准，对一组字符序列进 行比较；并通过插入空格，尽量使处在不同序列中的相同或相似度较高的字符串排 列仡同位置的问题。多序列比对问题的算法在d n a 和虽白质的序列比对、蛋白质 的级结构和功能预测、系统发生树的建立等许多领域中都有着十分重要的应用 多序列同步比对法是属于一类精确序列比对算法。它的完备算法对求解二维( 两 条序列的比对) 或三维的问题非常有效，但是对于维数稍高的问题却很难应用。 通过对序列比对的完备算法：动态规划算法和a 算法特点的分析，提出了两种改 进方法：双向动态规划算法和a 完备算法的改进算法。通过理论分析，证明了它们 在求序列比对的完备解时，降低了计算的复杂度。 针对多序列比对问题的快速求解，提出了一种基于a 算法的启发式算法。该算 法采用的多个优化搜索机制使求解多序列进行同步比对所需的计算时间有着显著地 缩短。同时，它能够得到精度比较高的比对结果。另外，通过实验可以看出，此方 法的求解效率不依赖于序列之间的相似程度。这在很多算法中是不容易做到的。 仿射g a p 模型能够不打断比对序列中的相似字符串。通过解决应用仿射g a p 模 型后多序列比对问题在计算过程中遇到的一些困难，使序列比对算法在应用过程中 更具实用价值。 关键词：多序列t 潞；动态窥翻；a 。算启发式羹妥；仿射6 i 生物信k 息学 华中科技大学硕士学位论文 a b s t r a c t s o l v i n gm u l t i p l es e q u e n c ea l i g n m e n tp r o b l e m i st om a k e c o m p a r i s o n w i t hs e q u e n c e s b ys p e c i f i e dc r i t e r i o no fc o m p a r a b i l i t y b e t w e e nc h a r a c t e r s ，a n dt oa l i g ns i m i l a rs e q u e n c e s t o g e t h e rb yi n s e r t i n gg a p s t ot h e s es e q u e n c e s t h em e t h o d st os o l v et h i sp r o b l e mh a v e b e e nw i d e l yu s e di nt h ea r e a so fd n aa n d p r o t e i ns e q u e n c e sa l i g n m e n t s ，t e r t i a r ys t r u c t u r e a n df u n c t i o n p r e d i c t i o no fp r o t e i n ，c o n s t r u c t i o no fp h y l o g e n e t i ct r e e ，e r e a l g o r i t h m f o rm u l t i p l es e q u e n c es i m u l t a n e o u s a l i g n m e n t i sc o n s i d e r e da sam o r e e x a c ta p p r o a c ht ot h i sp r o b l e m i ti sap r a c t i c a lm e t h o df o rt w oo rt h r e ed i m e n t i o n a l i g n m e n tp r o b l e m s b u tn o tf o r h i g e rd i m e n t i o n o n e s b ya n a l y z i n g t w oe x a c ta l g o r i t h m sf o rm u l t i p l es e q u e n c e p r o b l e m ：d y n a m i c p r o g r a m m i n g a n d a + a l g o r i t h m ，t w o a m e l i o r a t i v ea l g o r i t h m sw a s g i v e n t h e ya r e b i d i r e c t i o n a ld y n a m i c p r o g r a m m i n g a n d i m p r o v e da a l g o r i t h m b yc o m p r e h e n s i v e a n a l y s i so ft h e s et w oa l g o r i t h m s ，t h e ya r ep r o v e d t ob em o r et i m ea n d s p a c e e f f i c i e n ti n s o l v i n gm u l t i p l es e q u e n c ea l i g n m e n tp r o b l e m w i t he x a c t a p p r o a c h a na + - b a s e dh e u r i s t i ca l g o r i t h mw a ss h o w nt og e t a p p r o x i m a t e r e s u l t sw i t hm u c h l e s st i m es p e n d i n g s e v e r a ls t r a t e g i e sa r eu s e di nt h i sa l g o r i t h mt og e tf a i rw e l lr e s u l t s w i t h i ns h o r tt i m e a n di tc a nb es e e nf r o mt h et e s tr e s u l t st h a tt h ec o m p l e x i t yo ft h i s a l g o r i t h md o e sn o td e p e n do n t h es i m i l i t u d eo f s e q u e n c e s ，w h i c h i sa g o o d c h a r a c t e r i s t i c t h a tm a n yo t h e r a l g o r i t h m sd o n o th a v e a f f i n e dg a pp e n a l t ym o d e la v o i d sb r e a k si ns i m i l a rs t r i n g s w i t ht h ea p p l i c a t i o no f a f f i n e dg a p p e n a l t ym o d e l ，m o r ep r a c t i c a la l i g n m e n t o f s e q u e n c e s c a nb e g o t t e n k e yw o r d s ：m u l t i p l es e q u e n c ea l i g n m e n t ；d y n a m i cp r o g r a m m i n g ；a a l g o r i t h m ； h e u r i s t i ca l g o r i t h m ；a f f i n e d g a pp e n a l t y ；b i o i n f o r m a l t c s l i 华中科技大学硕士学位论文 1绪论 1 1序列比对问题的生物学背景 1 1 1 序列的由来 生物学家在研究生物的d n a ，蛋白质等在分子数量级上的物质时，往往需要对 这些物质进行比较。例如比较两条d n a 之间的相似程度。如果仅仅通过肉眼来判断， 很难得出比较精确的结果。而且如果需要比对序列的数量很大，往往是人力所不能 及的。这时就要借助计算机的高速运算能力和其巨大的存储容量。然而要让计算机 帮助人们对生物物质进行比较的实验，首先就要解决让计算机认识这些物质，也就 是要让计算机能用它能识别的语言表达这些物质的特征。 我们已经知道d n a 是由四种脱氧核糖核酸组成的双螺旋结构。核苷酸的碱基有 四种：胸嘧啶( t ) 、腺嘌呤( a ) 、鸟瞟呤( g ) 和胞嘧啶( c ) 。如果把这种双螺 旋结构拉直，就形成两条平行的由这四种脱氧核糖核酸组成的链。因为是链状结构， 所以它可以由代表这四种核酸的字符所排列的字符串表示。另外，如果一条链中有 核酸a ，那么另一条链上的相同位置必有核酸t ；如果一条链中有核酸c ，那么另一 条链上的相同位置必有核酸g 。反之亦然。因此，如果我们只要知道其中一条链中 核糖的组成，就能推算出另一条链上核糖的组成。这样，只要一条字符序列就能够 表示整条d n a 序列的核酸组成。这时d n a 序列就被表示成形如：a c c t a g g t a 的能够用计算机语言表示的字符串了。 1 1 2 世界上著名的序列数据库 近年来大量生物学实验的数据积累，形成了当前数以百计的生物信息数据库。它 们各自按一定的目标收集和整理生物学实验数据，并提供相关的数据查询、数据处 理的服务。随着因特网的普及，这些数据库大多可以通过网络来访问，或者通过网 络下载。 一般而苦，这些生物信息数据库可以分为一级数据库和二级数据库。一级数据库 的数据都直接来源于实验获得的原始数据，只经过简单的归类整理和注释；二级数 一一 华中科技大学硕士学位论文 据库是在一级数据库、实验数据和理论分析的基础上针对特定目标衍生而来，是对 生物学知识和信息的进一步整理。国际上著名的一级核酸数据库有g c n b a n k i l j 数据 库、e m b l l 2 l 核酸库和d d b j 库【3 l 等；蛋白质序列数据库有s w i s s p r o t l 4 1 、p i r 例 等；蛋白质结构库有p d b l 6 l 等。国际上二级生物学数据库非常多，它们因针对不同 的研究内容和需要而各具特色，如人类基因组图谱库g d b 、转录因子和结合位点库 t r a n s f a c 、蛋白质结构家族分类库s c o p 等等。 1 2 序列比对和数据库搜索 比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备 的特性。在生物信息学研究中，比对是最常用和最经典的研究手段。 最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列 之间的相似区域和保守性位点，寻找二者可能的分子进化关系。 比对还是数据库搜索算法的基础，将查询序列与整个数据库的所有序列进行比 对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有关查询序列 的大量有价值的参考信息，对于进一步分析其结构和功能都会有很大的帮助。近年 来随着生物信息学数据大量积累和生物学知识的整理，通过比对方法可以有效地分 析和预测一些新发现基因的功能。b a l i b a s e 数据库【7 l 提供了大量已由人工比对比对好 的序列。它们能够作为序列比对程序的参考标准。 1 2 1 序列两两比对 序列比对的理论基础是进化学说，如果两个序列之问具有足够的相似性，就 推测二者可能有共同的进化祖先，经过序列内残基的替换、残基或序列片段的缺 失、以及序列重组等遗传变异过程分别演化而来。序列相似和序列同源是不同的 概念，序列之问的相似程度是可以量化的参数，而序列是否同源需要有进化事实 的验证。 全局的序列比较通常用罚分矩阵描述序列两两比对，两条序列分别作为矩阵的两 维，矩阵点是两维上对应两个残基的相似性的罚分，罚分越低则说明两个残基越相 似。因此，序列比对问题变成在矩阵里寻找最佳比对路径，目前最有效的方法是 华中科技大学硕士学位论文 n e e d l e m a n w u n s c h i8 l 动态规划算法，在此基础上又改良产生了s m i t h w a t e r m a n l 9 1 算法 和s i m 算法。 在进行序列两两比对时，有两方面问题直接影响相似性分值：罚分矩阵和空格罚 分。针对不同的研究目标和对象应该构建适宜的罚分矩阵，但国际上常用的罚分矩 阵有p a m 和b l o s u m 等，它们来源于不同的构建方法和不同的参数选择，包括 p a m 2 5 0 、b l o s u m 6 2 、b l o s u m 9 0 、b l o s u m 3 0 等。对于不同的对象可以采用不 | 刊的墩代矩阵以获得更多信息，例如对同源性较高的序列可以采用b l o s u m 9 0 矩 阵，而对同源性较低的序列可采用b l o s u m 3 0 矩阵。 g e n b a n k 、s w i s s p r o t 等序列数据库提供的序列搜索服务都是以序列两两比对 为基础的。不同之处在于为了提高搜索的速度和效率，通常的序列搜索算法都进行 了定程度的优化，如最常见的f a s t a l l o l i 具和b l a s d n l 7 - 具。f a s t a 是第一个 被广泛应用的序列比对和搜索工具包，包含若干个独立的程序。f a s t a 为了提供序 列搜索的速度，会先建立序列片段的“字典”，查询序列先会在字典里搜索可能的 匹配序列b l a s t 是现在应用最广泛的序列相似性搜索工具，相比f a s t a 有更多改 进，速度更快，并建立在严格的统计学基础之上。n c b i 提供了基于w c b 的b l a s t 服务，用户可以把序列填入网页上的表单里，选择相应的参数后提交到数据服务器 上进行搜索，从电子邮件中获得序列搜索的结果。b l a s t 包含五个程序和若干个相 应的数据库，分别针对不同的查询序列和要搜索的数据库类型。 1 1 2 多序列比对 顾名思义，多序列比对就是把两条以上可能有系统进化关系的序列进行比对的方 法。目前对多序列比对的研究还在不断前进中，现有的大多数算法都基于渐进的比 对的思想，在序列两两比对的基础上逐步优化多序列比对的结果。进行多序列比对 后可以对比对结果进行进一步处理。 目前使用最广泛的多序列比对程序是c l u s t a l w ( 它的p c 版本是 c l u s t a l x l l 2 1 ) 。c l u s t a l w l l 3 j 是一种渐进的比对方法，先将多个序列两两比对构 建距离矩阵，反应序列之间两两关系；然后根据距离矩阵计算产生系统进化指导树， 对关系密切的序列进行加权；然后从最紧密的两条序列开始，逐步引入l 晒近的序列 并不断重新构建比对，直到所有序列都被加入为止。 华中科技大学硕士学位论文 c l u s t a l w 的程序可以自由使用，在n c b i 的f t p 服务器上可以找到下载的软 件包。c l u s t a l w 程序用选项单逐步指导用户进行操作，用户可根据需要选择打分 矩阵、设置空位罚分等。e b l 的主页还提供了基于w e b 的c l u s t a l w 服务，用户 可以把序列和各种要求通过表单提交到服务器上，服务器把计算的结果用e m a i l 返 回用户。 华中科技大学硕士学位论文 2 序列比对问题及算法介绍 2 1比对算法及数据结构 我们这里介绍多序列比对问题的一些定义，以及它和最短路径问题的关系。 多序列比对问题中包含确定的字符集c ，一个用来表示空格的字符“”，和罚 分函数w ：c x c - * r ( 用来表示字符问的相似度) 序列( c l c 2 。) 是由有序排列的一些字符组成，其中对于所有1 i sm 都有c f c 。 构成一条序列的字符的个数m 表示这条序列的长度。 d 条序列： 0 1 。c 1 1 c 1 2 c l m o d 。c d l c d 2 c “- 的比对是由d 条长度相等的序列构成的一个d 柳l 型的字符矩阵： d l 垃c 1 1 c 1 2 c 1 o d 。c d j c d 2 c d m 它要满足以下条件：( i ) 对任一f ，1 s 括d 存在一系列递增整数：吩。 2 ，峨。， 满足q ；c i n 。，c i n 。，c n ，。对任一，1 ，s m ，若，不属于上述递增整数序列，那么 字符c “必为空格符“一”。( i i ) 对任一，1 s js m 必存在一个f 使得石。的字符乙不 为空格符。换个说法是：序列的比对就是在原序列中插入空格符。使所有序列的长 度相等。同时应保证不让所有序列在同一个位置出现空格符。 上述比对的罚分定义为： 。w 正，i ) ； “维”表示待比对的序列的条数。二维序列比对的罚分是所有比对字符之间的罚 分的和。当维数大于二时，我们称这种序列比对问题为多序列比对。定义多序列比 对的罚分为所有两两比对的罚分和。两个空格符之间的罚分被定义为零。这种罚分 模型被称作s p ( s u m o f p a i r s ) 。它被广泛应用于蛋白质和d n a 的比对。 一一 华中科技大学硕士学位论文 序列比对问题是找出给定序列的具有最小罚分的比对的问题。而求解罚分最小比 对问题又等同于在一特定网络图中找两点之间的最短路径。令d 表示序列的条数。 i ( 1s is d ) 条序列q c n c f 2 c h 。有图g 。- 7 4e 4 ) ，其中： v “； o i ，工d ) i 石。一0 , 1 ，m e 4 = ( “，v ) i “暑o l ，一，z d ) y ap i 1 + e l ，z d - i - e d ) y 。，“一v , e i - 0 , 1 ，喜# 中1 s fs d ， 一条从点s - ( 0 ，0 ) 到点f 一( m ，卅d ) 的路径对应着对给定序列的一种比对。 边( h ，v ) 表示比对中的“列”，令h x l , - - , x d ) ，v 一瓴+ 8 l ”，硝- t - e 。) 。如果e j 一0 ， 表示把空格符“一”加入比对的第珀女序列；如果巳一1 ，表示把序列q 的第而+ 1 个 字符加入比对的第i 条序列。 r d a s 幽2 - 1 两条序列比对示意图 例如：对字符串t l w y 和加r 进行比对。可以构造g 。如图一。图中粗线表示的 一条从j 到t 的路径即表示一个比对； 一tlwy a 一一d r 图中的横线和垂线都表示插入空格符。当图中每条边根据相应两个字符之间的 罚分被给定后。求解这两条序列的最佳比对等同于在图中找到一条s 到t 的最短路 径。 华中科技大学硕士学位论文 2 2 罚分矩阵 罚分矩阵( s u b s t i t u t i o nm a t r i x ) 1 1 4 1 是在做序列比对的关键，它定义了所有比对在 一起的字符的分数。罚分矩阵会决定序列比对的准确性，因此，如何选择一个适当 的罚分矩阵是十分重要的。目前几种比较常用的罚分矩阵分别是p a m ，b l o s u m ， g o n n e t 等。而根据比对字串的长短不同各有一些较合适的罚分方式： p a m 矩阵是由d a y h o f f l l 5 , 1 6 在1 9 7 8 年所提出，其中以p a m 2 5 0 最常被使用，p a m 矩阵是利用不同的胺基酸在演化的过程中被其它氨基酸取代的频率推导而来。他观 察7 1 群较接近的蛋白质序列中的1 ，5 7 2 个突变推导出p a m 矩阵。下表为p a m 2 5 0 的罚分矩阵。 图2 - 2p a m 2 5 0 罚分矩阵 除此之外，还有一些动态的罚分方法，例如c o f f e e 模型【1 8 j 及隐马可夫模型 h m m 1 9 , 2 0 1 。由于篇幅的原因这里不再一一介绍。 2 3 比对算法的复杂性 多序列比对的计算量相当可观，因此有必要分析一下计算的复杂性。双序列比对 所需要的计算时间和内存空间与这两个序列的长度有关，或者说正比于这两个序列 1 一一 y q o吨q7咕。吒qq吨吃ti，qqi，吨吨o w吒咱吖呵。吖喝吨咕吨qq吨吨2吨巧吒 vo吨屹吨d0屹吨：o吒q屹屹屯o。 y e1吨oo吨oto o吨doo咀t13 w s 1 o oo1吐qo；吒11吐02 v r吨qtdl-吨2吨3咭ooal6 t qo咕22咕t3吨1屹咀10 4 8 p1嵋qq咕吐。屹t吨吨以6 r noq21q o 2 c ；| 1 吨屹2 q md咕屹。吨吨20 4 6 p l吨吨qq2q吨2喝5 n kq咕ooi吨。吒5 m 工一心屹c；11f；吨5 l hq喝11吨吨6 k 日1 1 o 5 工 pqq咕9 h e 0 5 3 4 g d 0 5 4 f c 屹挖 e a 2 d a c 华中科技大学硕士学位论文 长度的乘积，用d ，n ：) 表示。其中_ r l ，、n ：是指两条序列的长度。三序列比对则可以 理解为将双序列比对的两维空间扩展到三维，即在原有二维平面上增加一条坐标轴。 这样算法复杂性就变成了o ，n ：n ，) ，其中n ，表示第三条序列的长度。 随着序列数量的增加，算法复杂性也不断增加。我们用o ( n 。n ：h ，j l d ) 表示对d 个 序列进行比对时的算法复杂性，其中n 。是最后一条序列的长度。若序列长度相差不 大，则可简化成o ( n 。) ，其中d 表示序列的数目，n 表示序列的长度。显然，随着序 列数量的增加，序列比对的算法复杂性按指数规律增长【2 1 j 。已经证明多序列比对问 题是一个n p 完全问题f 2 2 】。因此| 2 3 , 2 4 1 ，要对多序列比对问题进行精确求解十分困难。 降低算法复杂性，是研究多序列比对的一个重要方面。为此，产生了不少很有实 片j 意义的多序列比对算法。这些方法的特点是利用启发式( h e u r i s t i c s ) 算法降低算法 复杂性，以获得一个较为满意但并不一定是最优的比对结果，用来找出子序列、构 建进化树、查找保守序列或序列模板。以及进行聚类( c l u s t e r i n g ) 分析等。有的算 法将动态规划和启发性算法结合起来。例如，对所有的序列进行两两比对，将所有 的序列与某个特定的序列进行比对，根据某种给定的系统发生树进行分组比对，等 等。必须指出，上述方法求得的结果通常不是最优解，至少需要经过d 一1 次双序列 比对，其中d 为参与比对的序列个数。 2 4 比对算法的的分类 2 4 1j 司步法( s i m u l t a n e o u sa l i g n m e n t ) 同步法实质是把给定的所有序列同时进行比对，而不是两两比对或分组进行比 对。其基本思想是将一个二维的动态规划矩阵扩展到三维或多维。矩阵的维数反映 了参与比对的序列数。这类方法对于计算机的系统资源要求较高，通常是进行少量 的较短的序列的比对。 基于动态规划d p ( d y n a m i cp r o g r a m ) 的算法是求解多序列比对的完备算法。这 种方法搜索图中的每个节点。它的时间和空间的复杂度是d o 。) 。它对求解二维( 两 条序列的比对) 或三维的问题非常有效。但是对于维数稍高的问题却很难应用。因 为，即使d 不是很大的情况下n 4 的大小是惊人的。为了能够求解维数较高的问题， 华中科技大学硕士学位论文 必须找到能够以较快的速度求出近似解的方法。因为想要在不损失解的精度的同时 把搜索区域限制到足够小是很困难的。 a 和a + 算法是非常著名的启发式算法，它被广泛应用于人工智能问题的求解。 它们利用每一点到终点的最短路径估计长度，减小了搜索空间的大小，并能得到最 优解。然而这些方法往往对序列之间的相似程度有很强的依赖性。并且它们的时间 和空阳j 复杂度仍然是o ( n o ) 。 现在著名的基于s p 的多序列比对算法有通过构造进化树的进化算法 ( p r o g r e s s i v e ) ，例如c i u s t a i w ；有使用叠代方法的算法1 2 5 9 1 ，如i t c r a l i g n 等。这些 算法的求解速度非常快。但是精度不高。m s a ( m u l t i p l es e q u e n c ea l i g n m e n t ) 印j 是著 名的对多序列进行全局同时比对的程序。它能给出较为精确的比对，但是它的求解 速度比较慢。m s a 的基本思想是基于动态规划的，利用投影的最短路径和通过计算 最短路径长的上下界缩小搜索区域。d c a ( d i v i d e a n d c o n q u e ra l i g n m c n o 1 3 1 1 是目前多 序列全局同时比对速度最快的程序之一，它把长序列之间的比对分解成若干个短序 列之间的比对，然后进行拼接。但是短序列间的比对是用m s a 来完成，所以说m s a 是它的基础。在用m s a 求解比对时，如果参数选择得好，能在较短的时间内得到十 分精确的比对。但是，用来限制搜索区域的参数选择非常不容易选择。如果把搜索 区域限制得过小就得不到比对；如果减小对搜索区域的限制又往往需要花费过长的 运算时问。本文介绍的基于a 的启发式算法却能在缩小搜索区域的同时得到精度较 商的解。启发式算法能够在很大程度上减小搜索的空间和时间0 ( 2 。) 。而且，此方法 对于序列之间的相似程度没有依赖，这在现在流行的许多算法是做不到的。 2 4 2 步进法和迭代法( p r o g r e s s i v ea n di t e r 汀i v ea l l g n m e n t ) 这类方法通常是根据序列间的距离矩阵构造系统发生树1 3 2 - 3 5 1 ，然后按照系统发生 树表示的次序对序列族进行比对。在这些算法中最常用的就是c l u s t a l 。它是由f e n g 和d o o l i t t l e 于1 9 8 7 年提出的( f e n g 和d o o l i t t l c ，1 9 8 7 ) 3 6 1 。由于对于实际的数据利 用多维的动态规划矩阵来进行序列的比对不太现实因此大多数实用的多序列比对 程序采用启发式算法，以降低运算复杂度。c l u s t a i 的基本思想是基于相似序列通常 姒仃进化相关性这一假设。比对过程中，先对所有的序列进行两两比对并计算它们 的相似性分数值，然后根据相似性分数值将它们分成若干组，并在每组之间进行比 华中科技大学硕士学位论文 对，计算相似性分数值。根据相似性分数值继续分组比对，直到得到最终比对结果。 比对过程中，相似性程度较高的序列先进行比对，而距离较远的序列添加在后面。 作为程序的一部分，c l u s t a l 可以输出用于构建进化树的数据。步进算法最大的优点 就是速度快，但缺点是。我们无从得知最后的结果( a l i g n m e n t ) ：是否符合我们的要求， 也就是我们无法得知a l i g n m e n t 出来的品质是好是坏。 迭代算法的基本思想是把问题分解成若干已知的优化问题。在已得到的解的基础 上对其不断优化，以期得到更好的解。应用这种思想的算法有模拟退火算法及遗传 算法1 3 7 , 3 8 ；i 。 国外对序列比对问题已经经历了一个长期的研究过程，有不少文纠3 9 4 2 】介绍了 并总结了这些成果。近年来，国内也开展了相关的研究。例如，清华大学对真核基 因的选择性剪接形式进行了研究提出了一种启发式多序列比对算法【4 3 , 4 4 l 。中国地质 大学通过s m i t h 和w a t e r m a n 法用p v m 系统在工作站机群上完成了分布式序列比对 法1 4 5 l 。 华中科技大学硕士学位论文 3 双向动态规划算法 3 1双向动态规划算法需要解决的问题及意义 在序列比对的诸多问题中，两条序列的比对是基础。多序列比队、系统发生树的 构成都是以两序列比对为基础的。而两序列比对的时间和空间复杂度相对不是很高， 因此往往需要对它进行精确求解。因为两序列比对的应用非常广泛，所以求解此问 题算法的效率也成为影响其它以这种算法作为基础的问题的解决的一个重要因素。 因此在保证两序列比对精度的同时，提高两序列比对算法的速度有着非常重要的意 义。 3 2 动态规划算法及动态规划算法的特点 动态规划算法1 4 6 j 7 1 是用来求解最短路径问题常用算法。它是一个完备算法，通过 它可以得到任何一个具有非负边有向图的最短路径。d i j k s t r a 是应用动态规划求解最 短路径问题的经典算法。它依照图中的每个点到起点的最短路径长度的由小到大的 顺序依次求出图中每个点到起点的最短路径。这里所列的算法对原始的d i j k s t r a 作了 适当修改：当找到了起点s 到终点t 的最短路径后就终止搜索。 d i j k s t r a 是应用动态规划求解最短路径问题的经典算法。它依照图中的每个点到 起点的最短路径长度的由小到大的顺序依次求出图中每个点到起点的最短路径。 这里所列的算法对原始的d i j k s t r a 作了适当修改：当找到了起点s 到终点t 的最短 路径后就终止搜索。 d i j k s t r a 算法 输入：网络图n 一( g - ，) ，) ，对于任一边o ，p ) e ，啦，v ) 0 ；起点：s ； 终点：t 输出：j 到t 的最短路径 b e g i n 1 s 一庐；s 。一如) ；p ( s ) 一0 ；耶) - 妒； 华中科技大学硕士学位论文 2 r e p e a t 2 1 令u 为s 中具有p 值最小的点； 2 2 s s u 扣) ；s 一s 、恤) ； 2 3 i f u = tt h e nr e t u r n 尸( f ) ； 2 4 f o r 任一0 ，v ) e d o i fv 圣s o r p ( u ) + i ( u ，v ) p o ) t h e n p 0 ) - p ( u ) + t ( n ，v ) ； p ( v ) 一尸 ) u 0 ，v ) ) ； s 一s 。u p ) ； e n d i f u n t i lf a i s e ； e n d 集合s 中存放的点到起点s 的路径( 不一定是最短路径) 已被找到，在以后的运 算中有可能被转移到s 中。而集合s 中存放的点到5 的最短路径都已被找到，并且会 一直被保留在集合中。p 0 ) 表示一条从sn u 的路径；p 0 ) 表示这条路径的长度。 d i j k s t r a 算法不断更新s ，中点的p 和p 值。当s 中的点“到s 的最短路径被找到后， 就把“放入集合s 中并对“的后继点进行访问，我们称之为“扩展”点h ，即把u 的 所有尚未放入s 中的后继点放入s 。，或修改“的已在s 中的那些后继点的p 似) 和 p ( “) 值。如此循环，越来越多的点被放入s - 或s ，直到点t 被放入s 。此时程序停止。 p “) 即为sn t 最短路径。在最坏的情况下，图中的每个节点都被“扩展”一次。这 种算法在求解两条或三条序列的比对时能够得到较为满意的结果。但是当序列的条 数稍稍增加这种方法就不能应付了，因为当序列的条数d 稍稍增加图中节点总数 ll m 【川。+ 1 j 会迅速增长。 定理3 - l ：对于在d i j k s t r a 算法中任一属于集合s 的点“，有； p ( u ) - l + o ，“) ，其中工o ，“) 表示图中起点j 到点h 的最短路径长。 证明：s 集合中具有p o ) 值最小的点y 被放入s 集合以后，s t 中具有p 值最小的 点的p 值大于v 的p 值，因为： 华中科技大学硕士学位论文 首先，s 。集合中其它任一点的p 值都大于点v 的p 值 另外，由点v 产生或修改的点的p 值有： p ) = p o ) + f p ，m ) ，p p ) 因此，s 中具有p 值最小的点虽然不断地更替，但它们的p 值在不断地增大。 因为，点的p 只有可能被s 中具有p 值最小的点修改，但又由上面的结论我们知 道p m ) p ( v ) 。p 0 ) + l ( u ，p 卜p ( v ) ，所以v 不会在以后的计算中被任何s 中的点修 改。 证毕。 定理3 2 ：当d i j k s t r a 算法把任一点“放入集合s 中时( 第2 2 步) ，对于任一 v ( y s ) ：+ o ，“) s l + o ，v ) 证明；当y e s 时：已知即是5 中p 值最小的点，即：p 0 ) - p ( v ) 。又由定理 3 - 1 易知，当h 被放入集合s 中时，工o ，“) - p 0 ) 且由它修改的后继点的p 值都 比它大，因次此后已在或即将进入s 集合中的点的p 值都会大于 的p 值即 + ( j ，u ) 。直至v 进k s 时它的p 值都大于l + o ，“) ，即工+ o ，“) 工。o ，p ) 证毕。 这个定理说明：从起点s 到s 集合中任一点的最短路径都不可能经过除s 以外的 任何个点。 这个定理说明了这个算法的正确性。这个定理是建立在网络中的边长都是非负数 这个条件之上的。这个条件对于d i j k s t r a 算法是非常重要的，我们在以后的说明中常 常要用到这个条件。 定理3 - 2 告诉我们d i j k s t r a 算法在每一次循环过程中，不断的把除s 中点以外的 最接近起始点s 的点加入集合5 中。这就意味着，这个算法会按照图中点到起始点最 短路径长度的次序，依次把图中点放入集合s ( 也就是求出这些点到起始点的最短 路径及其长度) ，直到终点t 也被放入。但是注意到我们是求两点之间的最短路径一 一起点s ；终点f ，这个算法有它的不足之处：它只考虑了图中点与起始点s 之间的 华中科技大学硕士学位论文 关系，而没有顾及具有与点s 相同地位的点t 。此算法对于与t 之间最短路径长或的 点都是同等对待的。 3 3 双向动态规划 3 3 1 目标：利用动态规划基本算法，缩小搜索空间 我们把被“扩展”的点作为衡量动态规划算法的搜索空间的一个单位。由定理 3 - 2 ，我们很容易知道：d i j k s t r a 算法在结束时会“扩展”所有离起始点最短路径长度 0 i 长于起点、终点之间最短路径长度的所有图中的点。在最坏的情况下，d i j k s t r a 算 法在运行结束i j i 会“扩展”图中的每一个点。所以这个算法的空间复杂度为：o ( n 2 ) 。 如果我们简单的把两条序列比对问题的网络图画成如下图中的正方形区域。我们用 下图表示o i j k s t r a 算法的运算过程中“扩展”点在整个网络图中的分布状况。图中， 扇形区域所覆盖的区域表示进入s 集合中的点，这些点已被d i j k s t r a 算法“扩展”。 d i j k s t r a 算法的搜索过程就是不断的扩大这个扇形区域的过程。直到这个扇形区域的 边缘触及到终点t ，算法结束。假设图中起点j 到其它各点的集合距离就表示在网络 图中的点到起始点s 的最短路径长度。由定理3 2 知，接个搜索过程会是一个规则扇 形区域不断扩增的过程。扇形所覆盖的面积就表示了“扩展”点的个数 图3 - 1 d i j k s t r a 算法搜索最短路径示意图 华中科技大学硕士学位论文 由于扇形所覆盖的面积表示了d i j k s t r a 算法搜索空间的大小，如何缩小这个区域 的面积就成为降低此算法空间复杂度的关键。 3 3 2 引入另一个特殊点的信息 由于动态规划算法利用了已知点到起始点的最短路径信息，所以它能够避免搜索 那些到起始点的最短路径长大于终点到起始点。我们可以看到，在这个问题中其实 还存在一个在拓扑结构上与起始点具有同等地位的点终点t 。动态规划算法没有 利用图中点到终点t 的最短路径信息。由此，我们设想能否利用动态规划算法的特点， 使用双向动态规划的方法对原动态规划算法进行改进。双向动态规划把起始点s 和终 点f 都作为动态规划的起始点，对这两个点同时进行动态规划。当两个动态规划的过 程搜索到的区域相交时停止搜索。以下是双向动态规划算法的描述： 3 3 3 算法描述 双向动态规划算法 输入：网络图n 1 ( g 一，e ) ，f ) ，对于任一边0 ，y ) e ，l ( u ，v ) 0 ；起点：s ； 终点：t 输出：s 到f 的最短路径 b e g i n 1 s l 一庐；s l - p ，；p ( s ) - 0 ；耶) - 庐； 2 s 2 一；s 2 - p ；p 0 ) - 0 ；p ( o - 妒； 3 r e p e a t 3 1 令n 为s 。中具有p 值最小的点；b 为s ：中具有p 值最小的点 3 2 口e s 2 r e t u r n p 1 如) ，p 2 ( a ) ； 3 3 i fb s 1 r e t u r n p l ( b ) ，p 2 ( b ) ； 3 4 i f p ( 口) sp ( b ) t h e n 3 4 1 s 1 - s lu 4 ；墨一s l 、如 ； 3 4 2 f o r 任一0 ，v ) e d o 华中科技大学硕士学位论文 i f v 甓s l o rp l ( a ) + l ( a ，y ) p l ( v ) t h e n p l ( v ) 一p l ( a ) + l ( a ，v ) ； 几p ) 一e l ( a ) u ( 口，v ) ； 墨一s i u 似； e n d i f 3 4 e l s e 3 4 1 s 2 - s 2u p ) ；$ 2 t - s 2 、伪) ； 3 4 2 f o r 任一，v ) e d o i f 6 譬s 2 。o rp 2 p ) + ，p ，y ) p ( y ) t h e n p 2 ( v ) 一p 2 ( b ) + t ( b ，y ) ； p 2 ( v ) 一p 2 ( b ) u ( 6 ，y ) ； s 2 - s u v ； e n d i f u n t i lf a l s e ； e n d 3 1 步和3 2 步判断集合s 。和集合s ：是否有公共的点。如果有，停止程序运行。 这个公共点到点s 及点t 的最短路径p 1 及p 2 所组成的路径即为s 导t 的最短路径。3 4 步的判断语句可以控制两个动态规划过程的交替进行。它使两个动态规划扩展的区 域中最远的点离起点的距离基本相同。 3 4 双向动态规划的性能分析 3 4 1 精度上 性质：d i j k s t r a 算法中，集合s 中已经被“扩展”过的点在以后的运算过程中不 会再次被“扩展”。 这在算法的描述中就有体现。在d i j k s t r a 的第2 4 步：s 中具有p o ) 最小的点被 “扩展”时，对其后继点进行搜索。如果后继点属于s 则不对其进行操作。所以当 华中科技大学硕士学位论文 一个点一旦进入了集合s 就不会重新放回集合f 。而“扩展”点的操作只会对s 中 的点进行。 定理3 - 3 双向动态规划算法得到的路径长度不超过网络图中起点j 到终点，的 最短路径长度与最大边长之和。即双向动态规划算法所得到的结果的误差不超过图 中的最大的单边长。 证明： 如图3 2 ， s 图3 - 2双向动态规划算法搜索过程示意图 因为集合s 和集合s ：只有一个公共点，所以从点j 到点，的最短路径只有以下两 种情况： 1 点“即为最短路径上的点。 容易证明，p l ( u ) 和p 2 ( u ) 组成图中点j 到点，的最短路径。满足命题的要求 2 点“不在最短路径上a 可以证明最短路径上所有的点要么属于集合墨，要么 属于集合& 华中科技大学硕士学位论文 反证法：假设最短路径上存在如图点v ，它既不属于墨也不属于集合s ：a 由定理3 - 2 知工+ o ，“) s l + o ，y ) ；l + ( f ，“) s l + ( f ，v ) 有工( s ，h ) + l + ( f ，“) l + ( s ，v ) + 工+ o ，v ) 即通过“点的从点s 到点t 的最短路径的长度小于通过y 点的从点s 到点t 的最短 路径的长度。与前面的假设矛盾。 因此这种情况下点s 到点f 的最短路径上不存在点y ，既不属于集合s 。也不属于集合 s 2 。 所以图中点j 到点t 的最短路径上必存在一条边a b ( n - u ；b 一“) 。a ，b 分别属于 集合s 。和集合s ：。 因为，b 硭s 1 ，由定理3 2 有： j 已+ ( s ，“) l + o ，6 ) 同理，l + ( f ，“) s l + o ，a ) 所以，工+ ( s ，“) + 工+ o ，u ) s l + ( 5 ，6 ) + 上+ o ，口) 因为a ，b 为最短路径上的点，有l ( s ，6 ) + ( f ，a ) - l + o ，d + ，( 口，b ) 即l 4 ( s ，“) + 工( f ，u ) 上o ，f ) + ，( 口，b ) ，满足命题的要求 证毕。 3 4 2 速度上 从两头开始搜索，到程序结束时，搜索到的点一般比基本动态规划搜索到的少 现在我们来看看双向动态规划算法在搜索空间上与原动态规划算法之间的比较。 我们假设待搜索区域是如图3 3 一边长为b 的方形区域。图中起点s 到其它各点 的集合距离就表示在网络图中的点到起始点s 的最短路径长度。由定理3 - 2 知，整个 搜索过程会是一个规则