（计算机软件与理论专业论文）基于竞争策略的多序列比对算法.pdf

华中科技大学项士学位论文 摘要 在分子生物学和基因缮分析中，鬣白质序列和d n a 序列的e 对是一种重瑟的 势轿 鬟。多侉列 鼹蔺藤楚n p 完全润蘧，这藏蹩说，任餐磷究抉褥完全箨法瓣金 凰郄攘霆l | 鑫极大爨难。求鳞多痔剃毙对阏题瓤墩番成是在一令骞囱茏巧图中寻找两 点蒯的最短路径，求解此类问题众所周知的方法是动态规划方法，但是使用动态规 划方法得到最优比对霈要消耗大擞的时间和空问，对于规模较大的情形，原封不动 地照搬动态规划方法求解从现实角度悬不可能的。 首先，提出了一种称之为基于竟绎策略的侠速多序硝t e 对近儆舞法，多序鳓沈 瓣箨法势为丽辩院对算法稻菲同霹魄对算法，本算法为一弱辩滋对算法。使瘸零算 法砖基毽瘴b a l i b a s e 2 0 1 孛0 0 , 亭n 簇进行了测试，势犍实验缝鬃与著名熬嗣黠比对算 法m s a 避行了比较，实验结果表明本算法题一种十分黯效的同时比对算法。 其次，在基于竞争策略的多序列比对算法的纂础上采用分治策略对比对结果进 行_ 迸一步的处理，也就怒进行优化。采用了一定的方法将原问题转化成了几个子 问题，然后对每个予问题采用原算法谶行求解，最后将备个予问题的结栗缝合越来 佟为琢同麓静解。闻徉采蠲诧傥纯方法对b a l i b a s e 2 0 1 中鹣序列簇遴行7 测试，并将 往他矮豹结栗与原缝聚进褥了对垅，实验结慕表骥这季申德纯是骞效豹。 、一 、一 关键词：多序列比对：竞争策略；优先级比；对罚分；罚分函数 华中科技大学硕士学位论文 a b s t r a o t t h ea l i g n m e n to fp r o t e i na n dd n a s c q u e n c c si s a l l i m p o r t a n tt o o l i nm o l e c u l a r b i o l o g ya n dg c n o m ea n a l y s i s t h em u l t i p l es e q u e n c ea l i g n m e n t i san p c o m p l e t ep m b l c m i na n o t h e rw o r d ，a n ya t t e m p tt oi n v e s t i g a t eaf a s ta n dc o m p l e t ea l g o r i t h mw i l lf a c eg r e a t d i f f i c u l t i e s t h ep r o b l e mc o 珊：s p o n d st ot h es h o r t e s tp a t hp r o b l e m t h ea p p r o a c hb a s e do n d y n a m i cp m 倒n m i n gi s w e l l - k n o w nf o rt h i s p r o b l e m b u td y n a m i cp r o g r a m m i n g r e q u i r e se n o r m o u s t i m ea n d s p a c e t oo b t a i nt h e o p t i m a la l i g n m e n t f i r s t ，p r e s e n taf a s ta n da p p r o x i m a t ea l g o r i t h m ，w h i c hi s s i m u l t a n e o u s t e s tt h e d a t a s e t si nb a l i b a s e 2 0 1 u s i n go u ra l g o r i t h m ，a n dc o m p a r e i tw i t ht h ew e l l k n o w nm s a a l g o r i t h m t h er e s u l t ss h o w o u ra l g o r i t h mi sa ne f f i c i e n ts i m u l t a n e o u s a l g o r i t h m s e c o n d ，o p t i m i z et h er e s u l tw h i c hi s o b t a i n e di ns t a g e0 1 1 eu n d e rt h ed i v i d i n ga n d c o n q u e r i n gs t r a t e g y a tf i r s t ，d i o d e st h eo r i g i n a lp r o b l e mi n t os o m es u b p m b l e m s ，t h e n s o l v ee a c hp r o b l e mb yo u rp r o b l e m ，a n dt h e nc o m b i n et h ea l i g n m e n tt o g e t h e r t e s tt h e d a t a s e t si nb a l i b a s e 2 0 1 a n dc o m p 卸et h eo p t i m i z e da l i g n m e n tw i t ht h eo r i # n a lr e s u l t w h i c hi so b t a i n e di n s t a g eo n e t h e r e s u l t ss h o wt h eo p t i m i z i n gm e t h o di se f f i c i e n t 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 ；c o m p e t i t i v es t r a t e g y ；p r i o r i i y ； a l i g n m e n ts c o r e s ；c o s tf u n c t i o n 华中科技大学硕士学位论文 1 1 序列比对的应用背景 1绪言 蛋f 匀质序列的比对【1 9 j 是分子生物学研究的重要课题之一。在分子生物学和基因 组分析中，蛋白质序列的比对是一种重要的分析工具。近年来，生物实验室以核酸 和蛋白质序列的形式输出了大量的数据。大量数据的产生迫切需要快而高效的比对 算法。 生物学并不是字符串比较技术的第一个应用，更不是唯一的应用。字符串比较 技术可应用在计算机科学中的字符校对和文件的比较等等。错误检查和错误校正在 编码理论和数据转换中是十分重要的。语言处理和手写体分析是连续数据流比较的 例子。 字符串比对技术有着广泛的应用，但目前主要还是应用在分子生物学研究中。 1 2 多序列比对研究的现状 多序列比对问题是n p 完全问题，文献【1 0 】给出了其详细证明。 求解多序列比对问题可以归结为在一个有向无环图中寻找两点间的最短路径。 我们知道，求解最短路径众所周知的方法是动态规划方法【1 1 】，但是使用动态规划方 法得到最优比对需要消耗大量的时间和空间，对于规模较大的情形，原封不动地照 搬动态规划方法求解从现实角度是不可能的1 1 2 1 。 多序列比对问题在国外有许多比较成功的算法【1 4 矧。文献 2 4 - 2 v 对这些算法的优 缺点作了对比。全局比对算法有a m u l t ( 】b a n o n 和s t e i n b e r g ) 、d f a l i g n ( f e n g 和 d o o l i t t l c ) 、m u l t a l ( t a y l o r ) 、m s a ( l i p m a n ) 、t u l l a ( s u b b i a h 和h a r r i s o n ) 、c l u s t a l v ( h i g g i n s ) 、c l u s t a lw ( t h o m p s o n 和n i g g i a s ) 、m w t ( 1 ( e c e c i o g l u ) 和a + f s 删和 华中科技大学硕士学位论文 m g o s h h n a ) ，局部比对算法有m a c a w ( s c h u l e r ) 、p i m a ( s m i t h ) 和 p r a l i g n ( w a t e r m a n ) 。 幽内近几年也有相关的研究成果，文献【2 9 】提出了一种启发式多序列比对算法， 浚算法借助引导树启发序列之间的两两段对段比对，通过建立序列相似性估计模型，给 h 了一种由序列间相同词数估计序列相似程度的方法；文献1 3 0 论述了一种分布式算 法的实现和性能指标；文献1 3 1 提出了一种基于动态规划的跨膜蛋白疏水图比对方 法；文献1 3 2 1 提出了一种基于生物进化思想的序列比对算法。 这艰简要介绍两个有代表性的例子，也就是m s a j l 2 1 和c l u s t a l w 。m s a 是一 个i 二j 时比对算法，其主要思想是应用c a r r i u o 1 i p m a n 界f l j ，将最优解确定在比较小的 范幽内，然后使用动态规划d i j k s t r a 算法i l l l 求解。m s a 对于序列数较少的序列簇可 以得出比较好的比对结果，但m s a 需要较多的内存，对于规模稍大的情形，如多于 1 0 条序列的序列簇，m s a 无法计算出比对结果。c l u s t a l w 是一个比较成功的首 先构造系统发生树d 3 - 3 6 1 然后进行比对的算法之。它的主要步骤分为三步。首先计算 出一个距离矩阵1 3 ”，矩阵中的第i 行第，列的值为序列簇中的第i 条序列与第j 条 序列的最优比对的罚分。然后，根据上一步计算出的距离矩阵，采用 n e i g h b o u r i n g - j o i n i n g 算法1 4 1 l 计算出一个系统发生树。最后根据第二步计算出的系统 发l ! 树中的顺序，一步一步的比对，其中每次比对都是两序列比对，每次比对的结 果均作为以后比对的一条序列。c l u s t a l w 是一种启发式算法，它可以比对几十条 序列的序列簇，而且时间空间消耗不多，但它得到的比对结果没有m s a 优。 1 3 课题的主要研究工作 本文提出了一种称之为基于竞争策略的多序列比对算法，该算法为同时比对算 法a 基因库【删j b a l i b a s e l 4 4 l 是一个专门用于评价比对质量的基准库( b e n c l 姗a r k ) ，它可 以用来发现比对程序的强项以及弱势。本文对基因库b a l i b a 2 0 1 刚中的序列簇进行 了比对，试验结果表明本算法是一种十分成功的同时比对算法。此外，本文在基于 2 华中科技大学硕士学位论文 竞争策略的多序列比对算法的基础上采用分治策略对比对结果进行了进一步的处 理，也就是进行优化。本文采用了一定的策略将原问题转化成了几个子问题，然后 对每个子问题采用原算法进行求解，最后将各个子问题的结果组合起来作为原问题 的解。本文同样采用此优化方法对b a l i b a s e 2 0 1 中的序列簇进行了测试，并将优化后 的结果与原结果进行了对比，实验结果表明这种优化是有效的。 3 华中科技大学硕士学位论文 2 1 有关术语 2 多序列比对问题 为了论文叙述方便，这里给出几个术语。 设占为任何有限个字母组成的集合，这里称三为字母表。若s 为三中的字母组 成的字符串，那么我们称s 为三上的一个序列，有时也称为字符串。序列s 的长度 用吲表示，也就是s 所包含的字符的个数。字母& 代表s 的第f 个字母。长度为零的 串称为空串，空串用f 表示。如对于如 c j 印一斟，则字符串s = c s s p a p 、t = p p t s 均 为三上的序列，陶= 6 ，s 4 甲。 序列拼接用符号+ + 表示，如“+ ls 与r 拼接也可以简单的表示为s t 。 例2 1 ：对于s = c s s p a p 、t = p p t s ，s + + t = c s s p a p p p t s 。序列s = s l s z s 的逆表示为 s 。驾品j 岛岛。若序列s = u f w , 其中队k 均为字符串，则u 称为s 的前缀， v 称为s 的子串，缈称为s 的后缀。 2 2 序列比对 定义2 2 1 ( 两序列比对) 设s 、r 为字母表趾的两条序列，三中不包含空格字符“”，这样空格字符“” 可以用来表示输出串中的空格。则s 和r 的一个比对是字母表三= 三u 上的一个 字符矩阵，且满足如下三个条件： 矩阵共有2 行： 矩阵中的第1 行去掉其中的空格字符“”后，即得到字符串& 第二行去掉 其中的空格字符“”后，即得到字符串r 。 矩阵中不存在全是空格字符“”的列。 华中科技大学硕士学位论文 例2 2 d ： 设字符串s 、r 分别为s = d k s ，t = - m i l v f ，则下面的四个字符矩阵爿、b 、c 、 a = c = 厂、 b ；i - - d k - s - i i m i - l v - fl l r 一、 | _ d - s k i il i h i l v fl l 字符矩阵a 为两行，第- - v r “一d - k s - ”去掉其中的空格字符“”后得到“d k s ”， 也就是序列第二行“m i l v f ”去掉其中的空格字符后得到“m i l v f ”，也就是序 列兀另一方面，爿中不存在全是空格字符“”的列，满足定义2 2 1 的三个条件， 是s 与丁的一个比对。字符矩阵b 也是s 与r 的比对。字符矩阵c 中第三列均为空 格，不满足定义2 2 1 的第三个条件，所以c 不是序列s 与r 的比对。字符矩阵d 也 不是序列s 与7 t 的比对，因为矩阵d 的第- v r 为“一d - s k - ”，去掉其中的空格后得到 的字符串为“d s k ”，不等于序列不满足定义2 2 1 的第二个条件。 字符矩阵a 的列数为6 ，而字符矩阵占的列数为7 ，爿和b 都是序列s 与序列r 的比对，由此我们可以看出比对的列数是不定的。 从定义2 2 1 的第三个条件我们可以看出，两个有限长度序列簇之间的比对的个 数是有限的。记乃”川) 为长度分别为m 、月的两条序列所构成的比对的个数，则肋力 可以通过下面的递归式得到： a m ，n ) = f l m - 1 , n ) + f l m l ，”- 1 ) + f l m , n - 1 )( 2 1 ) 其中初始值苁o ，h ) 嗽m ，o ) = l ，对任意的n , m o 。 这里给出递归式( 2 1 ) 正确性的简要证明。设阎= = m 、1 7 1 邗，如果s 的最后一个字 母蜀。与空格构成配对，那么共有a m - l ) 种比对；如果s 的最后一个字母品与丁的 最后一个字母品构成配对，那么共有a m l ，r l 1 ) 种比对；如果空格与丁的最后一个字 母霸构成配对，那么共有a m , n 1 ) 种比对。将这3 个值加起来，即得至t j 3 m , n ) 。 、ii、li-、 盼 嘶 子 岬 ，m帆、 华中科技大学硕士学位论文 由递归式( 2 1 ) 可以得出 砌，疗户 n i ( ( n 一肌) ! ( 一打) ! ( 脚+ h 一) ! ) n f f i m m j i 文献【1 3 】给出了证明，这里不再赘述。 定义2 2 2 ( 多序列比对) 设占为字母表，岛岛，韪为三上的字符串，且t 2 ，设翮i 包含空格字符“- ”， 这样空格字符“”可以用来表示输出串中的空格。一个多序列比对是字母表三= 占 u - ) 上的一个字符矩阵，且满足如下三个条件： 矩阵共有k 行； 矩阵中的i 行去掉其中的空格字符“”后，即得到字符串& ： 矩阵中不存在全是空格字符“”的列。 例2 3 ：对于序列簇研= c s t , 岛= 删、岛= k ，下面的四个字符矩阵爿、曰、c 、 d ： c = eii s t - i：s：=t- 厂、 盼僻- c - s t 。- i li l 卜十一j 字符矩阵a 满足定义2 2 2 的三个条件，是序列簇西、岛、岛的一个比对，a 的列数 为5 ；b 也是研、岛、岛的一个比对，口的列数为6 。字符矩阵c 的第五列均为空格 字符，存在全是空格字符的列，不满足定义2 2 2 的第三个条件，所以不是序列簇岛、 岛、岛的比对。d 也不是序列簇岛、岛、岛的一个比对，尽管j d 中不存在全是空格字 6 、illii、lilii 华中科技大学硕士学位论文 符“的列，但是d 的第二行“s n k - d ”去掉其中的空格字符“一”后，得到的字符 串为s n k d ，而s 2 = s n d k ，不满足定义2 2 2 的第二个条件。 2 3 比对的罚分 一个序列簇存在多个比对，使用什么来衡量一个比对的好与坏呢? 目前存在多种 衡量比对质量的方法，也就是罚分函数1 , 1 5 1 。对于生物序列分析中常见的氨基酸序列 的比对，目前使用较为广泛的罚分函数有l 叫m a 2 5 0 、b l o s u m 等。本节将介绍使用最广 泛的罚分函数之一，也就是p a m 2 5 0 罚分函数。 定义2 3 1 ( 罚分函数) 罚分函数定义为：s u b ：三三呻，其中，三= 三u 一 ，为自然数。如s u b ( a ， 6 ) 表示第一个序列的字母口与第二个序列的字母b 构成比对的罚分。同样的，s u b ( - ，b ) 表示第一个序列的一个空格与第二个序列的字母b 构成比对的罚分。函数s u b 是对 称的，也就是说，对任意的口，6 ，s u b ( a ，b ) = s u b ( b ，玎) 。 p a r e 2 5 0 是目前使用最广泛的罚分函数之一。p a m 2 5 0 所使用的字母表三由2 0 个 标准氨基酸的简记符号组成，即三= 以s , t , p , a ，g ，j = d ，e q h 冠k 必z 厶v , e y , 叨。 p m n 2 5 0 可用一个如下表所示的罚分矩阵表示： 由上表可以看出s u b ( c ，0 = 4 ，s u b ( c , s ) = 1 6 ，s u b ( t , a ) = 15 ，s u b ( a ，) = 2 4 ，s u b ( ，) = o 。 华中科技大学硕士学位论文 有了罚分函数的定义，我们可以给出两序列比对罚分的定义。 定义2 3 2 ( 两序列比对的罚分) 设a 为字符串s f 是的一个两序列比对构成的矩阵，记该比对的罚分为c 研) ，则 c 似) 定义为： c 翻) = l 自；岱u b ( a 1 1 m 4 【2 】m ) 其中彳【l 】加】、彳【2 】m 分别表示矩阵爿的第一行第丹列、第二行第刀列元素，w 是比 对矩阵a 的列数。 例2 4 ：对于序列s = c c s q 、序列t = a k t g ，下面的字符矩阵 厂、 i c c s qi i l a k l 6 j 为序列s 与序列丁的一个比对，根据定义2 3 2 ，该比对的罚分为： c ) = 泓6 ( 一a ) + s u b ( c , k ) + s u b ( c , 一) 蝴 d 十鼢m q ，g ) 根据p a m 2 5 0 ，该比对的罚分为： c ( 爿) = 2 4 + 2 l + 2 4 + 1 5 + 1 7 = 9 9 定义2 3 3 ( 多序列比对矩阵中的任意两行之间的罚分) 设a 为字符串岛岛，蕊的一个多序列比对构成的矩阵，根据罚分函数的定义， 我们记矩阵中的第i 行。第，行( 其中o 乜且f ，) 之间的罚分为c ( a u ) ，则 c ( a , j ) 定义为： 刚= m 渤m 【f 】m 一们m ) 其中，爿【f 】m 表示矩阵a 的第i 行第行列的元素，w 为矩阵彳的列数。 例2 5 ：对于例2 3 的序列簇西= c s t , 岛= s n d k 、s 3 = k i , 比对矩阵4 为： 华中科技大学硕士学位论文 妊阵 9 、fl|j 卜 溅 卜 s 一 卜卜卜 华中科技大学项士学位论文 的罚分为： c ( a k 堪l 南+ c 堪l 如+ c ( a 2 玉 = 9 3 + 6 1 + 1 1 4 = 2 6 8 2 4 仿射g a p 模型 a ； 。a w v l 。- 按照定义2 2 3 所介绍的罚分模型，其罚分为 s u b ( a ，k ) + s u b ( 彬- ) + 锄6 ( k - ) + s u b ( l ，- ) + s u b ( - ，聊 = 3 + s u b ( 1 4 , ) + s u b ( a 固恤6 ( 一，聊 对于矩阵的第二行k - 一i v , 其中连续的空格意味着这可能是由一次基因转变所 引起的，所以按照前面介绍的罚分模型来计算罚分也许是不科学的”2 1 。在这种情形 f ，计算罚分时应该考虑一处空格中的空格字符的个数，而不是仅仅将各空格“一” 与字母的罚分加起来。这也就是本节即将介绍的仿射g a p 模型。为了跟本节所介绍 的仿射g a p 模型相区别，本文称2 3 节所介绍的模型为简单g a p 模型。 定义2 4 1 ( 仿射g a p 模型下两序列比对的罚分) 设a 为字符串岛岛的一个两序列比对构成的矩阵，记该比对的罚分为q 印) ： c 鼬) = s u b ( a 1 l n ，一【2 】【甩】) + g ( ，) l ( , n s w 州j i n 卜一州2 i i n l , , 一 g ( ，) = 口+ 其中“、卢 o ，一【l 】m 、彳【2 】i n 分别表示矩阵a 的第l 行第月列的元素和第2 行第疗列的元素。g ( ，) 表示所有空格与其他字母构成配对的罚分的和，为一处空 i o 华中科技大学项士学位论文 墨i i i ii _ _ 糯 格巾空格字键“”的个数，w 为比对矩阵4 的列数。 倒2 7 ：妇对予如下豹 越么； a = 比对a 夜两处存在空格字符“- - ”j 丽且每处均含有多个空格字符，第一处空格 会鸯3 令空襁字铸“- ”，第二处含寿s 个空格字符“- ”，赦第一处空摄的弱分为：塞( 3 ) ， 第二处空格其罚分必蠢5 ) 。掇据定义2 4 。l ，该魄对矩阵其总罚分为：c g a ) = s u b ( c , s ) + s u b “，6 3 + s u b 4 pg ( 3 ) + 甙5 ) 。 再给出个例子： 倒2 8 ：对于下面的比对曰； 厂、 | g n d e q i t r - 一疑| 肛 ll l g - d m - - g i 黼e m 、 、 比对矩阵嚣中有3 处含有空格，第一处只有1 个空格字符“”，第二处有2 个空 格字符“”，第三处有4 个空格字符“”，根据仿射g a p 模型下两序列比对罚分的 定义，蓼狮 可以得到比对嚣的罚分为：s u b ( g g ) 十s u b ( d , d ) + s u b ( e , m ) + s u b ( r ，6 3 + s u b ( m , a 毋+ g o p g c 2 弦塞姆) 。 由意义2 4 t ，我嬲可以番出，对节 # 连续豹空给譬符“* ”，其与其镶字母磊对黪 鞠分为譬( 1 产a + 筘；两个不连续豹窆格字符“- ”与其镶字蹲构成配对，其罚分豹和 为g ( 1 ) 吲1 ) - - ( 洲一卢) 十( d 十口弘- 2 ( 口+ 芦) ；两个连续的空格字符“- ”与冀他字母的酉己 对，其罚分为占( 2 ) = a + 2 。 对于仿射g a p 模型，貔l l 】可以这样来理蠹攀：连续空撂中的第一个空摄字符“” 与其他字母豁对的弱分走a + 参，褥连续空格中瓣第二令空格字铸“”与其键字母静 镄分为筘，连续空格中豹第三个空格字符“- ”与其他字母豹罚分也为参，依诧类推， 连续空格中的第拊( h 2 ) 个空格字符，其罚分为芦。有时我们记s u b ( v , “一”声鼻( 任 华中科技太学硕士学位论文 意的 ，三) ，r 澎a = g a p 。冀意思熄连续窆格巾的第一个空格字襁“一”与其他字姆 的铷分较非酋空格字符与其他字母的罚分而言。其罚分多出一个g a p 。 定义2 4 2 ( 仿射g a p 模型下多序列比对矩阵中的任意两彳亍之间的罚分) 设a 为字符串岛国，蕊的一个多序列比对构成的矩阵，根据仿射g a p 模型下 两序列眈辩豹罚分定义，我们记债射g a p 模燮下矩阵中静第i 行，第，行( 其中0 搿是蠢f ，) 之潮豹罚分必诞毋，剐舔搿定义为： c 基崖茹一 s u b ( x i l n ，蠢f 歹l 【辫】+ g 秽) 月“l m i - i s n j s l w 】l 州- 一 g d ) = d + 其中口、芦 o ，a q 【棚、一们m 分剐表示矩阵a 的第一行第n 列、第二行第打列元 素。g ( ? ) 表示掰有奎格的弱分鹃和，f 为连续空稽中空格字符“一”的个数，w 为 对矩薛a 豹列数。 定义2 4 3 仿慰g a p 模型f e 对矩蓐的援分) 设a 为序列簇瓯舷成的一个多序列e 对构成的矩阵，根据矩黪筵i 行第，符 之问的罚分的定义，我们记多序列比对爿的罚分为c l a ) ，则q “) 定义为： c m i = xt , 彬k c g ( a u ) 其中c 譬0 为 e 对矩阵a 的第f 行尚第_ ，行之间的罚分。 多序列 黠瀑要瓣决垂冬蠲题裁是：辩一个蠢毒条痔列豹痔剜簇西，翰& ，要求 这k 个序列的一令多序列比对a ，使褥在序列簇韪岛是鼹骞霹戆熬多序列 对孛， 该比对的罚分c 研) ( 或q a ) ) 煅小。 华中科技大学硕士学位论文 3 多序翱比对洞怒的阏格黼模型 3 1 简单g a p 模型下的刚格图模型 求解简单g a p 模型下多序列比对问题可以归结为在一个有向玉环图中寻找给定 掰点阿酶最短路径。翔，对于痔捌簇两甄蕊，设s d 代表第d 个痔列( 1 矗妨，它 的长度为n o ，；己为蚓= 瑚，k 表示序列的个数，也猕为维数。于是农毒向无环图联虬 毋，睁 o ，地柏盼电l ，哪，e = u 。l o 1 i ( v , v + e ) l v , v + e e 踟o 中，一条从起始点 s o o 。，至终点l - - ( n l 2 , 黝豹憝径瓣应羞序捌簇戆一令魄对。 为描述方便。我们先考虑两序列 _ 2 ) 的情形。设s i = a w v l ，s 2 - = k w g ，这两条 窿确对瘴静有囱冤环圈g 如謦3 1 。 ，= ，r，f ，f，rr ， r |r 。rr ，l 幽3 - 1 序列岛= a t w l 与序列& = k w g 对应的有向无环图 在蹋3 1 中，行代表第一个字符串，列代表第二个字符串。每祭边表示一个配对， 边的长度即戈该配对的捌分。每条斜边表零孤个j # 空接字德“”鹣一个醚慰，在凝 3 - 1 中，边0 ，也) 表示第一个序列的第一个字母a 与第二个序列的第一个字母k 构成配 对，这条透豹长度惫s u b ( a d o 。透l ，砖) 表示第一个序列懿第二个字每矽与第二个序 华中科技大学硕士学位论文 ；= ；罱出i i 1 1 i i 瑚= 目；2 自目g 目目目日# 目# 置 列的第一个字母k 构成配对，相应的，这条边的长度为s u b ( w , l o 。横边和竖边都表 示撼入空揍。横边表示在第二个廖到中捶入空辏字德“一”，也就是袭示第一今序歹驰 聪应位赞豹一个字符与第二今序裂静空格字符“”构成配对，边鹣长度为瓣瘦的菲 空格字符与空格字符“- ”之间的罚分。在图3 - l 中斌边 v 1 ) 表示第一个序捌的第一 个字母与第二个序列的空格字符构成配对，即相当于在第二个序列中的相应位置插 入4 个空格，这条边的长度为s u b ( , 4 ，) 。横边( v 2 , v j ) n 表示第一个序列的第二个字母 与第二个序列的窆接构成配对，这条边的长度必s u b ( 数- ) 。露竖边则表承第二个廖 列静一个非窆格字符与第个序列鑫冬一个空格字符构成配对，郯榴当予在第一个序 列稠应韵位鬣插入一个空格字符。在阉3 - l 中，竖边( ，) 表示第一条序剐的空格字符 “”与第二条序列的第一个字符构成配对，也就是相当于在第条序列中插入空格 字符“”，相应的这条边的长度为s u b ( - ，1 0 。 在嬲3 1 中，有三条边以毪为终点，我艘? 懿v - z 鸵入度菇3 ，嬲中蠢三条边以砖 为越点，我 j 称毪靛港凄必3 。对于二维豹情形，除逮器煮磐，每个点的出度入度都 为3 。 由豳3 1 我们可以得出如下结论，一个多序列比对对应着图中从起始点到终点的 一条路径，反之也成立。 在图3 - 1 中褥在一系粗线构成的从起点s 要4 终点f 的路径。这条鼹经对癍蛇对 矩黔为： 反过来。上面的比对对应的路径就是图中粗线构成的路径。 同样的邀理，对予维数k 2 的情形，序歹q 簇的一令比慰与握应鲍墅g ( 虬d 中毂 一条铁起点s ( 0 ，锈碧) 裂终熹t ( n i 渤，蝣存在一一黠反关系。 椤 | 3 1 ：辩予如下浮列簇两意潞函： 两= g n d e q h r k 、，i，j阳卜 华中科技大学项士学位论文 舻匿 华中科技大学硕士学位论文 i i 、i l 劬懒) 喾o 则称y 为x 的恁继点，为y 的翦驱点。 显然，对于毒维情形，每令 # 边器轰搀寄一1 令# 驱亵藤继。 定义3 2 2 ( 维空闯孛边韵长废) 对于k 个序列岛囝，& ，闻嘲，我们可以构造一个七维空间中的有向无环图， 图中点的坐标舳柏满足：0 一 对应着下甏豹露个字母静院对梦l j ；r g - n 其长度为； s u b ( r ，g ) + s u b ( r ) + s u b ( r , n ) + s u b ( g ，) + s u b ( g , n ) + s u b ( - , n ) 3 2 仿射g a p 模型下多序列比对问题的网格图模型 求解仿射g a p 模撄下多序列比对问题仍然可以归结为在一个有向无环图中求给 定鼹点间的最短鼹径长阚题，与传魅g a p 模型所不网的是圈巾边长教定义。 1 6 华中科技大学硕士学位论文 ；# j _ 自目= l # 目= _ _ - 自# ；目_ _ i i _ _ _ _ _ 目# 目# 目e ；目_ = _ _ 目_ _ - j _ _ _ _ _ _ - _ _ _ 目# 目_ 2 对于序列簇s t , s 2 ，砖。设曲代袭第d 个序列，它的长度为n d ，记为酬= ：惭七 袭示序列的个数，也称为维数。于是可以构造存向无环图g ( v ，妨， ， 0 ，黝，黝转产o 1 一，臻 ，e = u 能豫i 产 ( 牧删k 蚪霉、矗g o t 倒3 3 ：为叙述方便我 f 】稻然戳两维为铡。设两= d e q h , s z = r k m , 这两条序列对应 的有向光环圈g 如图3 2 曲”f p 一。rf r? ， ，f，r，气， ， t 隧3 - 2 序列s t = d f 潺i 与謦剜& = 脯对应韵有商无环阉 在这个圈中，行代表第一个字符串，列代表第二个字符串。边代表一个配对， 斜边代表两个非空格字符串的蹲己对。横边表示第一个字符串的个字母与第二个字 符串的空格构成配对，竖边表示第一个字符串的空格与第二个字符串的一个字姆橡 成配慰。圈中从越点至终点粒路径乓这嚣条字德串瓣魄对存在对应关系。叛上 与篱荦g a p 模型下韵阏格模蝥是样的。不同之鲶在予：鞠3 - 2 中酌边长的定义与 翻3 - 1 中边长的定义不同，边的长度不仅与构成该边的配对裔关，而且与该边的前驱 边有关。这是因为在仿射g a p 模型下，一个配对的罚分不仅与构成该配对的两个字 母有关，而且与该配对的前一个配对有关。如，在阉3 - 2 中，对于边皿瓿均来说， 如果该边麴蘸条边菇毯，均，鄹么选尽该蟛对黩的长度为口+ 芦；如聚该边静蔫 一条边为壤w ，窃，那么该边的长液为g ：如祭该边的前一条边为e ( v l ，囝，那么 该边韵长度为肆+ 声。 率中稀技大学硕士擎位论文 在謦3 - 2 中，我们碍疆羲鞠，籍逑豹长发燕定德。滋为籀逮表承嚣令 空稔字霉 捡贼的配对，艇以不管翦甄囊没有空格字箍“* ”，它的长度仍然是构成这个酝对的鼹 个字母之阕嚣鬟分。鲤器3 2 孛，籍逑点铷，妨懿长瘦为鳆魏硒，不错该斜边熬蘸 一条逑燕嚣么。瑟鸷一条逾熬长覆与遮条逾熟薷驱透露关系，瞧我 j 爨然记边觞长 度为上苫，如边e ( v 2 ，的的长度记为l s ( e ( v 2 , v s ) ) ，与简单g a p 模型不同的烧，l s ( e ( v e ，功) ) 瀚德与浚边豹蠡一条这舂美。 定义3 2 1 ( 自驱边与矮继边) 若黠予点跏协砖，熬袋毪舞艟熬嚣糕点，如淹托豹嚣继点，则称逸e ( v 2 3 ) 为遮￥ ，蜴粒鑫继迓；穗盛熬+ 旅域p f 瑚舞鬏强蝣戆驱选。 与简单g a p 模趟下的网格图一样，从起点s 到终点，的路径跟两和岛之间驹比 霹存在一一对痤豹关系。在鬻3 - 2 孛，翔穰豹途梭戏了象嘉起点到终患的魏经，这 条路径对应的比对为下葱豹比对矩黪a ： a = 两一1 l| l 鼢一睬； 该 e 霹瞧露藤着瀚3 - 2 巾糨线构成豹藏强。这蓊路径蠡孽长璇、也裁燕该魄怼豹器 分为： s u b ( d , r ) + g ( 2 ) + s u b ( h , k ) + g ( 1 ) 。 这群求释多謦剥魄对麴翊蘧裁羟绻舞了奁一令霄怒茏臻鬻孛寻我获起煮s 赞| 蟪 点t 的最短路径的问题。 3 3 求解最短路的d i j k s t r a 算法 d i j k s t r a 算法是求解最短路闽蹶最常用的弹法之一，该算法是由d i j k s t r a 于1 9 5 9 霉罐豳来麓。为了穗述该葵法，蕾惫给密魏下豹示铡，如甏3 0 华中科技大学硕士学位论文 2 讥 图3 - 3 单行线交通网 对于图3 3 所示的单行线交通网，图中每条边旁边的数字表示这条单行线的长 度。现在有人要从v ，出发，通过这个交通网到v 7 去，求使总路程最小的旅行路线。 幽图3 3 可见，从到v 7 的路线是很多的，例如可以从出发，依次经过 v 5 、v 6 然后到达v 7 ；也可以从v ，出发，依次经过v 3 、v z 、v 5 、v 。，然后到达v 7 。不 同的路线，其总路程是不同的。 从这个例子可以引出一般的最短路问题，给定一个赋权有向图g ( k 日，对每一 个边e ( v 。劫，相应的有边长球一( w f ；o ) ，又给定g 中的两个顶点v ，设p 是 g 中从k 到h 的一条路，定义路的长度为p 中所有边的长度之和，记为w ( 尸) 。最短 路问题就是要在所有从b 到v t 的路中，求一条长度最小的路疡，使 w ( p 护m i n p w ( p ) 式中对g 中所有从到n 的路尸取最小，称凡是从b 到的最短路。 如下事实是经常要利用的，如果路径户是g 中从b 到h 的最短路，v i 是p 中的 一一个点，那么从v s 沿p 到的路是从h 到的最短路。事实上，如果这个结论不成 立，设q 是从h 到n 的最短路，令p7 是从b 沿q 到达v l ，再从沿p 到达 的 路，那么，p 7 的长度就比p 的长度小，这与，是从b 到v ，的最短路矛盾【i l 】。 9 华中科技大学项士学位论文 当聊乏0 时，目前公认的求解最短路的最好方法是由d i j k s t r a 于1 9 5 9 年提出来 的。 d o k s t m 方法的基本思想是从k 出发，逐步向外搜寻最短路。执行过程中，与每 个点对应，记录下一个数( 称为这个点的标号) ，它或者表示从h 到该点的最短路的路 径长( 称为尸标号) 、或者表示从略到该点的最短路的路径长的上届( 称为丁标号) ，方 法的每一步是去修改7 1 标号，并且把某一个具有7 1 标号的点改变为具有p 标号的点， 从而使g 中具有p 标号的顶点数多一个，这样，至多经过p 一1 步，就可以求出从 h 到各点的最短路。 在下述d i j k s t r a 方法具体步骤中，用p 、r 分别表示某个点的p 标号、7 1 标号， 研表示第i 步时，具有p 标号点的集合。为了在求出从到各点的距离的同时，也求 出从h 到各点的最短路，给每个点v 以一个 值，算法终止时，如果 ( 咖硼，表示 在从h 到v 的最短路上，y 的前一个点是v m ；如果 = m 则表示d 中不存在从 v , 至j jv 的路； ( v ) = o 表示v = 。 d i j k s t r a 方法的具体步骤如下： j 1 ：始( 卢0 ) ，令s 乒 ，h 曲= o ， ( 蝣= o ，对每一个v 如令殁沙讣一， ( v ) 叫， 令k = s ， 如果s r v , 算法终止，这时，对每个y s ，碳，v 户以v ) ；否则转入； 考察每个使( ，v j ) e e 且吁叠的点吁： 如果h 够中( 帕+ w 可，则把h 功修改为h 帕十峋，把 ( 啪修改为颤否则转入； ( 9 令丁( k ) = m i n - 峨 7 1 ( 0 ) ) 如果r ( v ) 十。，则把v 的r 标号变为p 标号p ( 匕) = t ( y i j ) ，令品i - 昌u 匕) ， 慨，把f 换成f + l ，转入；否则终止，这时对每一个v s 娟k ，炉p ( v ) ，而对每一 个v q t s ，坝b ，v ) = 删。 现在用d i j k s t r a 方法求图3 - 3 中v i 到1 ，7 的最短路，这时s = l ： 卢o ：s 0 2 v ，p ( v 1 ) = o ， ( ) = o ，t ( v t ) = m ( i = 2 ，3 ，7 ) ，t = l 。因( ，叻e ，心仨s o ， 华中科技大学硕士学位论文 p ( v ，) + w ? 一o 的情形，当赋权有向图中存在负权时，算法失 效。这是因为若赋权有向图中存在负权时，如果路径p 是g 中从峙到v j 的最短路， v l 是p 中的一个点，那么从h 沿p 到v j 的路不一定是从b 到v l 的最短路。 d i j k s t m 算法的空间复杂度为有向无环图中点的个数，时间复杂度比空问复杂度 还要商，多序列比对问题所构造的有向无环图的点的个数随序列条数的增长成指数 增长，照搬d i j k s t r a 算法求解多序列比对问题从现实的角度是不可能的。 3 4 求解多序列比对的m s a 算法 在介绍m s a 之前首先介绍著名的c a m l l o - l i p m a n。设硒岛，, s k ) = m i n a c ( a ) ， l = e 列 琦) ，u 为姆岛，渤的上界，假设a 为这k 条序列的一个比对，那么我们 可以得到： - 华中科技大学硕士学位论文 弘乏蚵f c 卅渊黝】 乏c ，捌晦岛) 其中p q 。将上式整理后即得到： c ( a 曲勰驴眦( + ) 这就是著名的c a r r i l l o l i p m a a 界。 现存的算法中，m s a 是比较成功的例子。m s a 采用的是动态规划策略。它首 先采用c a r r i l l o l i p m a n 界和i 嘲，将最优解确定在比较小的范围内，然后按照 d u k s t r a 算法搜索从起点赋o 0 o ) 到终点户- ( n h n 2 ，蚴的最短路径。 m s a 得到( ) 式中上界u 的方法有三种，一种是用户指定一个，然后将+ 作为u 的值：第二种方法是首先计算5 即痧一嘏黝，然后取= 吲8 扩进而得 到u 乩+ ；最后一种方法是由用户提供5 护之后得到u 的方法与第二种方法相同。 对于序列簇岛，鼢& ，m s a 算法的步骤可以分为如下两步： 第一步： f o r ，一lt o 七1d o f o r j 一件lt o k d o 设s t = a a 2 a n 、s j = b b z 6 埘， f o r ，一lt o 疗d o f b 吖一1i o m d o 锄“切：刮 6 吐蚴 g z 切：气嵌 + n ，) ，( 岛0 ) o d o d f o r f 一1t o ”d o 凡f 】一卅i 劬【明+ g z “明劬巾l m 】+ 。f ) o d 2 2 华中科技大学硕士学位论文 # ；= = j = 目, i i i i 鼻 l 一胁q m 堋 o d o d “- 一三+ 第二步； 按照d i j k s t r a 方法在界和c a r r i l l o l i p m a n 界的前提下搜索从起点到终点的路 径。其体的说，对于点v ( v l ，也，v k ) ，弛莱致咖e 阿g d h 啊爱日称v 满足 界；对于点，k ，哟。如果