（计算机应用技术专业论文）基于并行计算的线性空间算法在双序列比对中的应用.pdf

摘要 序列比对是生物信息学中一种基本的信息处理方法，对于发现核酸和蛋白质序列上 的功能、结构和进化的信息具有非常重要的意义。随着生物序列数据库中序列数据的激 增，开发出能够进行大规模运算的并行算法就显得非常迫切。本文研究了生物信息学中 的双序列比对算法以及其并行算法，主要研究内容和取得的成果如下： 1 根据目前双序列比对的研究现状，对于经典的双序列比对算法：动态规划算法和 线性空间算法进行了研究，给出了这两个算法的数学模型，并通过c + + 语言编程实现了 这些算法。为本文研究的基于并行计算的线性空间算法创造了对比的实验条件。 2 介绍并分析了并行计算的定义以及它的分类，尤其是对工作站机群技术进行了研 究。 3 分析了并行算法的设计以及常用的算法分解技术，选择了适当的通信机制，并根 据原有算法的研究，提出了基于并行计算的线性空间算法。 4 通过对s a r s 病毒的r n a 的不同测序结果的比对，将本文提出的基于并行计算 的线性空间算法与传统的双序列比对算法进行了比较。证明了基于并行计算的线性空间 算法的在进行长序列比对时，时间复杂性优于经典的线性空间算法。并论述了并行计算 技术在这一研究领域中的发展前景。 本文的研究内容是生物信息学中双序列比对的创新算法，经过实际测试其运算效率 较之两种传统串行算法均有所提高，为生物信息学的研究及实践提供进一步的支持。 关键词：双序列比对；动态规划算法；线性空间算法 a b s t r a c t s e q u e n c ea l i g n m e n ti s ab a s i ci n f o r m a t i o nd i s p o s a lm e t h o di nb i o i n f o r m a t i c s i ti s u s e f u lf o rd i s c o v e r i n gf u n c t i o n a l ，s t r u c t u r a l ，a n de v o l u t i o n a r yi n f o r m a t i o ni nd n aa n d p r o t e i ns e q u e n c e s b e c a u s es e q u e n c ed a t ai n c r e a s er a p i d l yi nb i o l o g ys e q u e n c ed a t a b a s e ，i ti s v e r ye x i g e n tt od e v e l o pa l g o r i t h m st h a th a v eh i g he f f i c i e n c y p a i r w i s es e q u e n c ea l i g n m e n t a l g o r i t h m so fb i o i n f o r m a t i c sa r es t u d i e di nt h i sp a p e r t h em a i nc o n t e n t sa n dp r o d u c t i o nc a n b eb r i e f l ys u m m a r i z e da sf o l l o w s ： 1 o nt h er e s e a r c ha c t u a l i t yo fp a i r w i s es e q u e n c ea l i g n m e n t ，c l a s s i c a lp a i r w i s 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 ga l g o r i t h ma n dl i n e a rs p a c ea l g o r i t h mw e r e 。a n a l y s e d 。a n dm a t h sm o d e l so ft h e ma r ct h e s ea l g o r i t h m sw l 目r ep r o g r a m m e d w i t hc + + p r o g r a m m e o f f e r e de x p e r i m e n tc o n d i t i o nf o r t h el i n e a rs p a c ea l g o r i t h mf o rp a i r w i s es e q u e n c ea l i g n m e n tb a s e do np a r a l l e lc o m p u t i n gp r e s e n t e di n t h i sp a p e r 2 t h ed e f i n i t i o na n dc l a s s i f i c a t i o no fp a r a l l e lc o m p u t i n gw e r ei n t r o d u c e da n da r i a l y s e d 。c l u s t e ro fw o r k s t a t i o n sw a ss t u d i e de s p e c i a l l y 3 t h ed e s i g no fp a r a l l e lc o m p u t i n ga n dt e c h n o l o g i e so fa l g o r i t h md e c o m p o u n d i n gw h i c hw e r ei nc 0 n 1 1 3 1 0 nu s ew e r ea n a l y s e d a p p r o p r i a t ec o m m u n i c a t i o nm e c h a n i s m w a ss e l e c t e d o nt h er e s e a r c ho ff o r m e ra l g o r i t h m ，l i n e a rs p a c ea l g o r i t h mb a s e do np a f a l l e lc o m p u t i n gw a sp r e s e n t e d 4 b yt h ea l i g n m e n to fd i f f e r e n ts e q u e n c i n gr e s u l t sf o rr n a o fs a i l s ，l i n e a rs p a c ea l g o r i t h mb a s e do np a r a l l e lc o m p u t i n gp r e s e n t e di nt h i st h e s i sw a sc o m p a r e d 谢t l l c l a s s i c a lp a i r w i s es e q u e n c ea l i g n m e n t i tt e s t i f e dt h a tl i n e a rs p a c ea l g o r i t h mb a s e do n p a r a l l e lc o m p u t i n gi ss u p e r i o rt oc l a s s i c a l l i n e a rs p a c ea l g o r i t h mi n t i m ec o m p l e x i t y g i v e nt h ed i s c u s s i o no ft h ef o r e g r o u n df o rt e c h n o l o g yo fp a r a l l e lc o m p u t i n gi nt h i sr c s e a r c hf i e l d t h er e s e a r c hc o n t e n t sa r ei n n o v a t e da l g o r i t h m so fp a i r w i s es e q u e n c ea l i g n m e n ti n b i o i n f o r m a t i c s t h e s ea l g o r i t h m sa r ea d v a n c e dm o r ee v i d e n t l yt h a nt h et w ot r a d i t i o n a 1 a l g o r i t h m si nb i o l o g yc o m p u t i n ge f f i c i e n c y i tc a no f f e rs u s t a i n m e n tf o rb i o i n f o r m a t i c sr e s e a r c ha n dp r a c t i c e k e y w o r d s ：p a i r w i s 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 ga l g o r i t h m ；l i n e a r - s p a c e a l g o r i t h m 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：爱垒垄盈 日期： ；一，； 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即； 东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学 位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：量j 兰塑 日期：色! 卫上函 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名：拉车 日期：j 他 电话： 邮编： 引言 2 0 世纪9 0 年代以来，随着各种基因组计划的不断发展，核酸和蛋白质数据迅速增 加。但是，与这些以指数方式增长的生物学数据相比，这些数据中所蕴藏的知识却非常 匮乏，而这些知识帮是医学、药物学、农学和环保学所急需的，这就造成了数据与知识 之间的一个极大的矛盾，这个矛盾催生了一门新兴的交叉科学一一生物信息学 ( b i o i n f o r m a t i c s ) i 】捌。目前，生物信息学已成为生命科学和自然科学研究的重大前沿 领域之一。 生物信息学的研究重点主要体现在基因组学和蛋白质组学两方面，具体地说就是从 核酸和蛋白质序列出发，分析序列中表达的结构和功能的生物信息【2 】。生物信息学的基 本任务是对各种生物大分子序列进行分析，也就是研究新的计算机方法，从大量的序列 信息中获取基因结构、功能和进化等知识。在从事分子生物学研究的几乎所有实验室中， 对所获得的生物信息学分析已经成为下一步实验之前的一个标准操作f 3 1 。而在序列分析 中，将未知序列同已知序列进行相似性比较是一种强有力的研究手段，从序列的片断测 定，拼接，基因的表达分析，到r n a 和蛋白质的结构功能预测，物种亲缘树的构建都需 要进行生物分子序列的相似性比较。这种相似性比较分析方法就称为序列比对 ( s e q u e n c ea l i g n m e n t ) 。 目前，国际互联网上提供了众多的序列比对分析软件。然而，不同的分析软件会得 到不屈的结果，网异寸所使用的参数在很大程度上影响到分析的结果1 4 】。有时常常会由于 采用了不合适的参数而丢失了重要信息，导致后续的实验研究走弯路。因此，本文研究 的生物信息学中的序列比对算法具有非常重要的理论与实践意义。 第一章生物信息学简介 生物信息学是一门新兴的交叉学科，它以核酸、蛋白质等生物大分子为主要研究对 象，以数学、物理、化学等自然科学和信息科学、计算机科学等工程科学为主要手段， 以计算机硬件、软件和计算机网络为主要工具，对生物大分子数据进行存储、管理、注 释、加工，以达到阐明和理解大量数据所蕴含的生物学意义的目的，并通过对序列和结 构数据及其相关文献的查询、搜索、比较、分析，从中获取基因编码、基因调控、代谢 途径、核酸和蛋白质结构功能及其相互关系等理性知识，在大量信息和知识的基础上， 探索生命起源、生物进化以及细胞、器官和个体的发生、发育、病变、衰亡等生命科学 中重大问题，发现它们的基本规律和时空联系【5 洲。 1 1 生物信息学简介 1 9 5 6 年，在美国田纳西州盖特林堡召开了首次“生物学中的信息理论研讨会”， 会议产生了生物信息学的概念。1 9 8 7 年，林华安博士正式为这一领域定下生物信息学 ( b i o i n f o r m a t i c s ) 这一称谓【6 】。生物信息学是伴随着基因组研究而发展的。它以人类基 因组计划完成为标志，经历了两个历史时代，即测序基因组时代和功能基因组时代。其 研究重点主要体现在基因组学( g e n o m i c s ) 和蛋白组学( p r o t e o m i c s ) 两方面。具体说， 是从核酸和蛋白质序列出发，分析序列中表达的结构与功能的生物信息。其研究内容主 要包括： ( 1 ) 新基因的发现与鉴定； ( 2 ) 完整基因组的比较研究； ( 3 ) 大规模基因功能表达谱的分析； ( 4 ) 生物大分子的结构模拟与药物设计； ( 5 ) 非编码区信息结构分析； ( 6 ) 遗传密码起源和生物进化的研究。 生物信息学对揭示人类及重要动植物种类的基因的信息，继而开展生物大分子结构 模拟和药物设计十分有益，是当今国际上正在迅速发展的自然科学领域的重大课题之 一，不仅对认识生物体和生物信息的起源、遗传、发育与进化的本质有重要意义，而且 将为人类疾患的诊治开辟全新的途径，还可为动植物的物种改良提供坚实的理论基础。 生物信息学研究是从理论上认识生物本质的必要途径，通过生物信息学研究和探 索，可以更为全砸和深刻地认识生物科学中的本质问题，了解生物分子信息的组织和结 构，破译基因组信息，阐明生物信息之间的关系。生物信息学的出现将改变生物学的研 究方式。传统的生物学是一门实验科学，传统的分子生物学实验往往是集中精力研究一 个基因、一条代谢路径，手工分析完全能够胜任。然而，随着分子生物学技术的发展， 2 生物学已经从一次只分析一个生物分子的时代跳跃到同时分析成千上万个生物分子的 时代。此时，必须利用计算机进行自动分析。另外，现在全世界每天都会产生大量的核 酸和蛋白质序列，不可能用实验的方法去详细研究每一条序列，必须是首先进行信息处 理和分析，去粗取精，去伪存真。通过预处理，发现现有的线索，在此基础上进行有针 对性、有明确目的的分子生物学实验。因而，生物信息学在指导实验、精心设计实验方 面都会发挥重要的作用。 生物信息学研究在医学上也有重要的意义。通过生物信息学分析，可以了解基因与 疾病的关系，了解疾病产生的机理，为疾病的诊断和治疗提供依据。这方面的研究不仅 对认识生物的起源及对认识生物遗传、发育与进化的本质有重要意义，而且将为人类疾 病的科学诊断和合理治疗开辟全新的路径，还可为动植物的物种改良提供坚实的理论基 础m 。 1 2 序列比较背景及意义 在生物信息学中序列比较是最重要的原始操作，是许多其他更复杂操作的基础。在 生物信息学中，对序列数据进行相似性比较，即序列比对，是一种基本的信息处理方法， 它对于发现生物序列中的功能、结构和进化的信息具有非常重要的意义 s 】。而序列比对 就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基 数，比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物 学特征t g 。常常会遇到下面这样的问题： ( 1 ) 有两个字母表相同、长度相同的串( 几万字符) 。已知序列几乎是相同的， 仅有少数差异，如字符的插入、删除、替换等。这些差异的平均频率很低，几百个字符 出现一个。因此，需要发现差异出现的位置。 ( 2 ) 有两个字母表相同的序列，各自长数百字符。因此，需知道一个序列的前缀 是否与一个序列的后缀相似。 ( 3 ) 问题同( 2 ) ，但有几百个序列，每一个需与所有其他序列进行对比。而且， 绝大部分序列之间是无关的，即它们缺乏应有的相似度。 ( 4 ) 有两个字母表相同的序列，各自长数百字符。因此，需知道它们之间是否存 在相似的子串。 ( 5 ) 问题同( 4 ) ，但不是两个序列，而是一个序列与数千个序列比较。 当一个基因被两个不同的实验室测序时，他们需要比较测序的结果，这时将出现类 似问题( 1 ) 的问题。甚至当一个长序列被输入计算机两次时，会有键入错误，类似情 形同样出现。问题2 与问题3 出现于大规模d n a 测序的片断组装过程中。问题( 4 ) 与问题( 5 ) 出现于大型生物数据库的局部相似性搜索【。 基于上面的各种问题，把比对定义为在序列中任意位置插入空格使得序列长度相 同。等长后，扩展的序列能够完全相互重叠，产生两序列字符间或字符与空格间的对应， 但不得有两空格的对应。空格甚至可以插入在序列的头部和尾部。 在分子生物学中，d n a 或蛋白质的相似性是多方面的，可能是核算或氨基酸序列 的相似，可能是结构的相似，也可能是功能的相似。一个普遍的规律是序列决定结构， 结构决定功能。研究序列相似性的目的之一是，通过相似的序列得到相似的结构或相似 的功能。这种方法在大多数情况下是成功的。研究序列的相似性的另一个目的是通过序 列的相似性，判别序列之间的同源性，推测序列之间的进化关系。 1 2 1 序列的相似性 序列的相似性可以是定量的数值，也可以是定性的描述。相似度是一个数值，反映 两条序列的相似程度。一般来说，相似性很高的两条序列往往具有同源关系。序列比较 的基本操作是比对( a l i g n ) 。两条序列的比对是指这两条序列的各个字符的一种一一对 应关系，或字符比对排列。序列的比对是一种关于序列相似性的定性描述，它反应在什 么不为两条序列相似，在什么部位两条序列存在差别。最优比对揭示两条序列的最大相 似程度，指出序列之间的根本差异。 1 2 2 双序列比对 双序列比对也叫两两比对。进行双序列比对最直接的方法就是生成两条序列所有可 能的比对，分别计算得分( 或代价) 函数，然后挑选一个得分最高( 或代价最小) 的比 对作为最终结果。但是，两条序列可能的比对数非常多，是序列长度的指数函数，随着 序列长度的增长，计算量呈指数增长。从算法的时间复杂性的角度来看，这种比对方法 不合适。因此，必须设计高效的算法以找出最优的比对。 1 2 3 序列多重比对 与双序列比对不一样，序列多重比对( m u l t i p l ea l i g n m e n t ) 的目标是多条序列比对 的共性。如果说双序列比对主要用于建立两条序列的同源关系和推测它们的结构、功能， 那么，同时比对一组序列对于研究分子结构及进化关系更为有用。对于多序列比对，现 有的大多数算法都基于渐进比对的思想，在双序列比对的基础上逐步优化多序列比对的 结果。进行多序列比对后，可以对结果进一步处理，例如构建序列的特征模式、将序列 聚类及构建分子进化树等。 4 面： 第二章双序列全局比对算法 上一章中简单的介绍了生物信息和序列比对算法。这一章中主要内容为以下几个方 定义全局比对模型； 给出两个序列的最优全局比对动态规划算法： 给出线性空间的最优全局比对算法。 2 1 定义全局比对模型 存在相似关系的两个序列彳、b 可以重新被排列成两个有序的字母序列。比对中包 括：匹配( 包括字符相同和字符不同) 、删除空格、和插入空格。一个匹配是由一个彳 中的字母和一个8 中的字母组成的；一个删除空隙是由4 中的一个字母和b 中的一个空 隙组成的；一个插入空隙是由4 中的一个空隙和曰中的一个字母组成的。 比对的相似性由一个数值来衡量。a ( a ，6 ) 表示两序列中由a ，b 两个字母组成的匹 配的得分。通常用q 表示一个空隙罚分。 例：m a t c h ：1 ；m i s m a t c h ：- 1 ；q ：- 2 ： a g c t a c g t a c a c t a c c 一序列 a g c t a t c g t a c - t a g c 口序列 上面两个序列比对过程中q 分值为一2 。比对相似分就是每个匹配和每一个空隙罚分 的和。例：1 1 3 1 1 2 * 3 = 6 两个序列彳和占的最优全局比对就是比对分值最高的比对。 2 2 动态规划算法 在生物信息学中，动态规划算法是序列比对的最经典的算法之一。为了从理论上能 够有效地分析动态规划算法，下面先将计算机科学中动态规划算法介绍如下： 动态规划算法的思想来自于分治法。分治法的基本思想是将一个规模为胛的问题分 解为k 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解决这些子 问题，然后将各子闯题的解合并得到原问题的解。 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题， 先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用 动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法解这类 问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而， 不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了 许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可 5 以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以用一个表来 记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就 将其结果填入表中。这就是动态规划法的基本思想。具体的动态规划算法是多种多样的， 但它们具有相同的填表格式。动态规划算法适用于解最优化问题。通常可以按以下步骤 设计动态规划算法： ( 1 ) 找出最优解的性质，并刻画其结构特征； ( 2 ) 递归地定义最优值； ( 3 ) 以自底向上的方式计算出最优值； ( 4 ) 根据计算最优值时得到的信息，构造最优解。 步骤( 1 ) 一( 3 ) 是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤 ( 4 ) 可以省去。若需要求问题的最优解，则必须执行步骤( 4 ) 。此时，在步骤( 3 ) 中计算最优值时，通常需记录更多的信息，以便在步骤( 4 ) 中，根据所记录的信息， 快速构造出最优解【l ”。 2 2 1 动态规划算法的基本要素 晟优予结构性质和子问题重叠性质。从一般的意义上讲，问题所具有的这两个重要 性质是该问题可用动态规划算法求解的基本要素。这对于在设计求解具体问题的算法 时，是否选择动态规划算法具有指导意义。下面着重研究动态规划算法的这两个基本要 素 1 最优子结构 设计动态规划算法的第一步通常是刻画最优解的结构。当问题的最优解包含了其子 问题的最优解时，称该问题具有最优子结构性质。闯题的最优子结构性质提供了问题可 用动态规划算法求解的重要线索。在动态规划算法中，利用问题的最优子结构性质，以 自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。算法考察的子 问题空间的规模较小。 2 重叠子问题 可用动态规划算法求解的问题应该具备的另一个基本要素是子问题的重叠性质。也 就是说，在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些 子问题被反复计算多次。动态规划算法正是利用了这种子阅题的重叠性质，对每一个子 问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地 用常数时间查看一下结果。通常，不同的子问题个数随着问题的大小呈多项式增长。因 此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。 2 2 2 最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给 定序列x = x 1x 2 c x 。 ，则另一序列z = 编，z 2 ，气) ，石的子序列是指存在一个严格 递增下标序列 ，之，) ，使得对于所有歹= 1 , 2 , - - - , k ，有z ，= x g 。例如，序列 z = b ，c ，d ，b ) 是序列x = a ，b ，c ，b ，d ，a ，b ) 的子序列，相应的递增下标序列为 6 2 ，3 ，5 ，7 ) 。 给定两个序列工和y ，当另一序列z 既是x 的子序列又是y 的子序列时，称z 是x 和y 的公共子序列。 例如，若x = a ，b ，c ，b ，d ，a ，b ，y = f 晟d ，c 爿，b ，a ) ，序列 b ，c 栅是x 和y 的一 个公共子序列，但它不是工和】，的最长公共子序列。序列 占，c ，占，彳) 也是x 和y 的一个 公共子序列，它的长度为4 ，而且它是z 和y 的最长公共子序列，因为x 和r 没有长度 大于4 的公共子序列。 最长公共子序列问题：给定两个序列x = “，工：，工。) 和y = ，y ：，y 。) ，找出 x 和y 的最长公共子序列。 动态规划算法可有效地解此问题。下面按照动态规划算法设计的各个步骤设计解此 问题的有效算法。 1 最长公共子序列的结构 穷举搜索法是最容易想到的算法。对x 的所有子序列，检查它是否也是】r 的子序列， 从而确定它是否为x 和y 的公共子序列。并且在检查过程中记录最长的公共子序列。x 的所有子序列都检查过后即可求出x 和y 的最长公共予序列。x 的每个子序列相应于 下标集 1 ，2 ，m ) 的一个子集。因此，共有2 ”个不同子序列，从而穷举搜索法需要指数 时间。 事实上，最长公共子序列问题具有最优子结构性质。 设序列x = “，x ：，x 。 和y = ，y ：，y 。的最长公共予序列为 z = z i ，z , 2 ，z i ) ，则 ( 1 ) 若岛= 只，则乙= 而= y 。，且z l 。是x 。和l 。的最长公共子序列。 ( 2 ) 着x 。y 。，且以x 。，则z 是x “和l ，的最长公共子序列。 ( 3 ) 若工，y 。，且以y 。，贝z 是石和的最长公共子序列。 其中 戈。- 1 = 而，z 2 ，工。- 1 ) k l = y l ，y 2 ，儿一i ) 乙- 1 = 瓴，z 2 ，二i i ) 证明： ( 1 ) 用反证法。若k = y 。，且乙靠，则，2 2 c - r 以，k ) 是x 和y 的长度为k + l 的公共子序列。这与z r ：x 和y 的最长公共子序列矛盾。因此，必有= x m = y 。由 此可知乙一，是x 。和e 一。的长度为k - 1 的公共子序列。若。r 和e 一。有长度大于七一l 的 公共子序列矽，则将x 。加在其尾部产生x 和】，的长度大于k 的公共子序列。此为矛盾。 故z 。是x 册- 。和o 。的最长公共子序列。 ( 2 ) 由于z i ，z 是x 卅_ ，和y 的公共子序列。若x “和j ，有长度大于k 的公共 子序列矿，则矿也是x 和l ，的长度大于k 的公共子序列。这与z 是x 和y 的最长公共 7 子序列矛盾。由此即知，z 是x 。和y 的公共子序列。 ( 3 ) 证明与( 2 ) 类似。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序 列。因此，最长公共子序列问题具有最优子结构性质。 2 子问题的递归结构 由最长公共子序列问题的最优子结构性质可知，要找出x = 瓴，屯，k ) 和 y = ，y ：，以 的最长公共子序列，可按以下方式递归计算： ( 1 ) 当工。= y 。时，找出x 。和l 一，的最长公共子序列，然后在其尾部加_ k x 。( = y 。) 即可得x 和y 的最长公共子序列。 ( 2 ) x m y 。时，必须解两个子问题，即找出工。和】，的一个最长公共子序列及 x 和】，：i 。的一个最长公共子序列。这两个公共子序列中较长者即为x 和】，的最长公共子 序列。 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算x 和y 的最长公共子序列时，可能要计算石和艺一，x m _ ，和y 的最长公共子序列。而这两 个子问题都包含一个公共子问题，即计算x ，。和l 的最长公共子序列。 首先建立子问题最优值的递归关系。用d 小刀记录序列x i 和r ，的最长公共子序列 的长度。其中，x i = 扛；，恐，薯) 和l = 饥，y 2 ，y j 。当i = 0 或j = o 时，空序列是x ， 和f 的最长公共子序列，故此时c 【f 】【月= 0 。在其他情况下，由最优子结构性质可建立 递归关系如下： f o 江o ，j = o c f 】【刀= e l i - 1 埘- 1 】+ 1 f ，j o ；x j = y ， ( 公式2 1 ) l m a x c i j - 1 ，c 【f 一1 】l ，】 i , j o ；t y j 3 计算最优值 直接利用递归公式容易写出计算c o j 】的递归算法，但其计算时间是随输入长度指 数增长的。由于在所考虑的子问题空间中，总共有o ( m n ) 个不同的予问题，因此，用动 态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法l c s l c n g t h 以x = ，屯，) 和 y = 饥，y ：，y 。 两序列作为输入。输出两个数组c 和6 。其中c m 刀存储x ，和t 的最 长公共子序列的长度，6 【f 】【刀记录e i l j 】的值是由哪一个子问题的解得到的，这在构造 最长公共予序列时要用到。问题的最优值，即x 和】，的最长公共子序列的长度记录于 c m 】【，| 】中- p u b l i cs t a t i ci ml c s l e n g t h ( e u a r x ，c h a r y ，i n q 】” n t1 1 1 x 1 e n g t h - 1 ： i n t n 2 y 1 e n p h - i ； s i n t 1 】c 2n e w i n t m + 1 n + l 】； f o r ( i n ti _ l ；i 0 ，j o 用以4 ，b ) 代表能得到最大分值& f ，) 的最优比对。p ( 4 ，b j ) 中最后一 个比对必是下列情况中的一种： l n 一个匹配( 啦，b j ) ； 一个删除空格( a i _ ) ； 一个插入空格卜，6 ；) ； 如果是1 ，那么尸( 4 ，b ) 在最后一对碱基之前的部分就是4 _ 1 和能得到最高分 & f - l , j - i ) 的比对，因为p ( 4 ，b j ) 是4 和b j 得到最高分的比对。此种情况下，p ( 4 ，b j ) 变 成由p ( a “，乃- 1 ) 和碱基对 ，屯) ；因此p ( 4 ，乃) 的得分等于以彳“，) 加上碱基对 ( 口，6 ，) 的得分，也就是： & j ) = s v - 1 ，川) 十以口i ，b j ) 如果是2 ，p ( 4 ，b j ) 是一个由删除空格结束的比对由d ( 的定义，有 s = d 同样，如果是似- 6 ，) ，有： s t i 。拜2i t l 抒 由s ，d ，j 的定义，下面的不等式总是成立的： & ，) s ( i - 1 ，j - - 1 ) + 似口f ，b j ) s d s ( i ，) j ( f ，) 由此得到结论，当i 0 ，j 0 时： & j ，j = m a x 奴f 1 ，- 1 ) + 以嘶，乃) ，d ( f ，) ，f ，) ) 下一步计算d ( j ) 。当f 0 ，j o 时，用x ( x b j ) 表示由删除空格( q 广) 结束的a i 和占序列的最高得分比对。用y ( 4 一l ，b j - i ) 表示此比对方法x ( 4 ，b j ) 中最后一对比对之 前的所有比对如果r ( x f - l ，召。) 是以一个删除空格结尾，因为x ( x f ，易) 是以一个删除 空格结束的最高分比对，那么r ( a i 一| ，b j - 1 ) 是一个以d ( h ，) 为最高比分，以彳f 1 和占j 为 比较序列的比对。换句话说，x ( 4 ，b j ) 是由x ( x ，一l ，b ) 和一个删除空格( 口f ，_ ) 组成： d ( i ，j ) = d ( i - 1 ，) 一g 如果】，( 4 1 ，b j ) 不是由删除空格结束的，而是由有最高分文爿。一1 ，b j ) 的一“和占， 序列的比对。( 因为x ( 4 ，b j ) 是以一个删除空格结束的最高分比对) 换句话说，x ( a f f b ，) 是由p ( a f - 1 ，曰，) 和一个删除对( 口，一) 构成的： j d ( 1 ，) 2 & h ，) 一g 表达式中一日是空隙( 口，- ) 的罚分，s ( i - 1 ，j ) 是以碱基对或插入对结尾的最优比对 p ( 4 - 1 ，b j ) 的得分。 因为再附加删除对( 口f ，_ ) 到石( 4 1 ，b 。) ，4 和b 的比分为d ( i l ，) 一日；同样， 再附加删除对( q ，一) 到p ( a f - l ，b j ) ，4 和b j 的比分为s ( f 一1 ，j ) - q ；因为这两种比对都 是以一个删除对作为结尾，根据d ( t ) 定义有： d ( i ，) d ( i 一1 ，- ，) 一g d ( i ，_ ，) s ( i 一1 ，歹) 一g 注意，如果f = 1 ，则d ( n ，d 没有定义假设d ( o ，) 的值为s ( o ，歹) 一g ，而当i = 1 时不 再可能出现d ( h j ) 这种状况了。综上，可以得出： 当i 0 且， 0 时： 皿材) = m a x d ( f 吐，- 1 ) 窜，s o - 1 , 1 ) 一g ) 矩阵j 最优比对得分j ( l ，) 证明方法类似： f ，) 2m a x i ( i - 1 , 1 4 ) 一9 ，s ( i - l , j ) 一日) 当i = 0 或j = 0 时，s 、d 、，的计算也容易给出，则s 、d 、j r 的计算可简写如 下： s ( o o ) = 0 & l ，o ) = d ( o ) 当i 0 s ( o d ) = i ( o ，) 当j 0 文f ，) = m a x s ( h 一i ) + 烈q ，乃) ，q f j ) ，7 i 当f 0 且， 0 d ( o d = s t o , ，) 一日当j 0 d ( f ，o ) = d ( i - l , o ) 一目当f 0 d ( i , i ，= m a x d ( - l ，j - i ) 一譬，& f - 1 ) 一g ) 当f o 且， 0 f ，o ) = & f ，o ) = s ( f ，o ) 一目当i 0 f ，) = m a x 7 ( i - 1 ，产d ) 一q ，s ( i - i 。j ) 一q 动态规划方法的另一种表现形式是由坍+ 1 行、疗十l 列组成的图表如图1 1 。每一 个元素由代表3 个矩阵的3 种节点构成： 当i 0 时，每一条垂直边从f l 到砰表一个删除对( q 广) ； 当j 0 时，每一条水平边从，l 到，代表一个插入对( 一，6 ，) ； 当i 0 ，j 0 时，从( i l ，j 一1 ) 到( f ，) 的对角线代表碱基对( 口f ，6 ，) 。 每一条从元素( 0 , 0 ) 到元素( f ，j ) 的路径都称为4 和曰，的一种比对。 假设对于任一元素，从d 到s 和从j 到s 的得分都为0 ； 从元素( 0 , 0 ) 到元素( f ，_ ，) 这条路径的得分是这条路径上的所有边之和。 对于任意一个元素( 1 ，力定义& ，) 为元素( o o ) 到元素g 歹) 的所有路径的最大值。同 样对于元素( 1 ，) 的d 、，结点。因此，给出类似d ( “) 和j ，) 的定义。 如果没有从属于s 集合的元素( o ，0 ) 结点到属于d 或，集合的元素( f ，_ ，) 结点的比对 路径，则d f ) 或i 棚可以被设置为s 一q 或更小的值。这样可以简化重新计算d 或， 的方法，并且不会改变d ( 。1 ，) 或7 i 川) 。 图2 1 动态规划算法的不意图 下面考虑当f 0 且 o 时。如何计算& “l ，将从( o ，o ) 到g - ，) 的路径分成3 组： 组包含所有以对角线结尾的路径，此组的最大分值为s ( f 一，- 1 ) + 驴( 口，0 ) ； 包含所有以垂直边结尾的路径，此组最大值为d ( “) ； 包含所有以水平边结尾的路径，此组最大值为f ，) - 因此& f ，) 应是三种表达式中最大值，与前面给出当f 0 ，_ ， o 时& ，。，) 相同。接下 来考虑计算边界元素( i = 0 或j = 0 ) 时的情况： s f o ，o )