（计算机软件与理论专业论文）基于pc机群系统的序列比对并行fastlsa算法研究.pdf

摘要 序列比对是生物信息学中一个基本的问题。在序列比对中广泛使用的三种算 法有n e e d l e m a n w u n s c h 算法、h i r s c h b e r g 算法和f a s t l s a 算法，而f a s t l s a 算 法是这三种算法中效率最高的算法。 为了进一步改进f a s t l s a 算法性能，本论文利用一个简单而有效的”波阵线 机制”对f a s t l s a 算法进行了并行化处理，本文称这种经过并行处理的f a s t l s a 算法为并行f a s t l s a 算法。相对于f a s t l s a 算法，本文的并行f a s t l s a 算法进 一步改进了时间性能，同时保持使用线性空间。 本论文也详细的描述了并行f a s t l s a 算法的实验环境：p c 并行机群系统， l i n u x 操作系统及其软件分布式共享内存系统( d s m ) 。本论文同时也分析了并行 f a s t l s a 算法的效率以及理论上和实际上的算法的性能。而且，从实验的结果上 也展示了并行f a s t l s a 算法在p c 机群系统中具有好的加速比，并且随着被比对 的序列的长度的增加，算法的效率会变得更好。 关键词：并行算法序列比对时间和空间复杂度p c 机群系统 a b s t r a c t s e q u e n c ea l i g n m e n ti sa f u n d a m e n t a lp r o b l e mi nb i o i n f o r m a t i c s t h e r ea r et h r e e e x i s t i n ga l g o r i t h m s ：n e e d l e m a n w u n s c ha l g o r i t h m ，h i r s c h b e r ga l g o r i t h m a n d f a s t l s a a l g o r i t h m ( a b b r e v i a t i o n f o rf a s tl i n e a r s p a c ea l i g n m e n t ) ，w h i c h a r e w i d e l yu s e df o rb i o l o g ys e q u e n c ea l i g n m e n t n e v e t h e l e s s ，i ti sp r o v e nt h a tf a s t l s a a l g o r i t h mi st h em o s t f f e c t i v eo n e i nt h i s p a p e r ，w eu s eas i m p l eb u te f f e c t i v ef o r mo fw a v e f r o n tp a r a l l e l i s mt o p a r a l l e l i z e d f a s t l s aa l g o r i t h m ，w h i c hw ec a l l e dp a r a l l e l f a s t l s a c o m p a r e dw i t h f a s t l s aa l g o r i t h m ，i tf u r t h e r i m p r o v e st h et i m ep e r f o r m a n c e ，w h i l e s t i l lu s eo n l y l i n e a rs p a c e t h et h e s i sd e s c r i b e si n d e t a i lt h e e x p e r i m e n t a l s o f t w a r ea n dh a r d w a r e e n v i r o n m e n to ft h ep a r a l l e lf a s t l s aa l g o r i t h m ：b u i l d i n go fp e r s o n a l c o m p u t e r p a r a l l e lc l u s t e r i n gs y s t e mb a s e do i ll i n u x o p e r a t i o ns y s t e ma n ds o f t w a r ed i s t r i b u t e d s h a r e dm e m o r ys y s t e m w ea l s oa n a l y z et h ee f f i c i e n c yo fp a r a l l e lf a s t l s aa n dg i v e d e t a i l e da c c o u n t so fi t st h e o r e t i c a la n dp r a c t i c a l p e r f o r m a n c e o u re x p e r i m e n t a l r e s u l t ss h o wt h a tp a r a l l e lf a s t l s ae x h i b i t s g o o ds p e e d u p s ，a n d a l s ot h a tt h e e f f i c i e n c yo fp a r a l l e l f a s t l s ai n c r e a s e sw i t ht h el e n g t ho ft h es e q u e n c e st h a ta r e a l i g n e d k e y w o r d s ： p a r a l l e l a l g o r i t h m t i m ea n d s p a c ec o m p l e x i t y s e q u e n c ea l i g n m e n t p c c l u s t e r i n gs y s t e m 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注的和致谢中所罗列的内容以外，论文 中不包括其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 本人签名： 牢雠弘 日期：m 多； 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名： 导师签名： 刨塑塾 班望 日期：垄翌垒。i ：当 日期：竺丝乏 第一章绪论 第一章绪论 1 1 引言 进入2 l 世纪，随着人类基因组计划( h g p ) 在全世界范围内启动，产生了一门 生物学与计算机科学、信息学及应用数学交叉融合而成的新兴科学一生物信息学， 它逐渐成为人们研究的一个重要的前沿课题。广义地说，生物信息学是用数学和 信息学的观点、理论和方法去研究生命现象、组织和分析呈指数级增长的生物信 息数据的一门学科。首先是研究遗传物质的载体d n a 及其编码的大分子量物质， 以计算机为其主要工具，研究各种学科交叉的生物信息学的研究方法，找出其规 律性。进而发展出适合它的各种软件，对逐步增长的浩如烟海的d n a 和蛋白质的 序列和结构进行收集、整理、发布、提出、加工、分析和发现。生物信息学的研 究的目的在于通过这样的分析逐步认识生命起源、进化、遗传和发育的本质，破 译隐藏在d n a 序列中的遗传语言，揭示人体生理和病理过程的分子原理，为人类 疾病的诊断、预防和治疗提供最合理的和最有效的方法或途径。其中研究的热点 有：序列的比对、基因识别和d n a 序列分析、蛋白质结构预测、分子进化等等。 1 2 课题的研究背景 本节简要介绍与本文算法相关的分子生物信息学的基本概念，对分子生物学 的详细介绍可参考有关遗传学机制和有关研究基因的技术文章剐。 1 2 1 分子生物信息学的概念 现代研究表明所有的生物体具有相似的分予化学结构。在分子化学结构中最 重要的分子是蛋白质和核苷酸，蛋白质通过调节新蔽代谢来作为有机体生命的载 体，而核苷酸则通过编码必要的遗传信息从而产生蛋白质，也就承担着向下一代 传递遗传信息的任务。 分子生物学的主要研究是蛋白质和核营酸的结构和功能。下面简要的描述一 下在生命化学方面的重要参与者一蛋白质和核苷酸。 1 蛋白质 蛋白质是由许多被称为氨基酸的小分子通过链接的方式构成的大分子。表1 1 列举了在蛋白质中常见的2 0 种氨基酸。 在目前的有机生命体中，蛋白质是主要的组成成分，例如结构化的蛋白质是 生物组织的建筑块，而蛋白酶则在生物化学反应中起着催化剂的作用，其它的蛋 2 基于p c 机群系统的序列比对并行f a s t l s a 算法研究 白质被用作氧气的运输或者充当免疫系统中的抗体。准确的说，原始氨基酸的残 基才是分子生物链的主体，由于这个原因，一个蛋白质的长度是由残基决定而不 是由氨基酸来决定的，但是，实际使用时常常使用后者。典型的蛋白质的长度是 3 0 0 个残基“，但是也有些蛋白质长度不到1 0 0 ，而有些则长达5 0 0 0 个残基。 表1 ，1 构成蛋白质的常见的2 0 种氮基酸 代表字母缩写全名 1am aa l a n i n e 2c c y sc y s t e i n e 3d a s pa s p a r t i ea c i d 4j eg l ug l u t a m i ca c i d 5fp h e p h e n y l a l a n i n e 6g g i yg l y c i n e 7hh i sh i s t i d i n e 8il i ei s o l e u e i n e 9k l y sl y s i n e 1 0ll e ul e u c i n e 1 1hm e tm e t h i o n i n e 1 2na s n a s p a r a g i n e 1 3pp r op r o l i n e 1 4qg i ng l u t a m i n e 1 5r a r g a r g i n i n e 1 6ss e rs e r i n e 1 7tt h rt h r e o n i n e 1 8vv a lv a l i n e 1 9w trpt r y p t o p h a n 2 0y t y rt y r o s i n e 2 核苷酸 在分子生物学里面，存在着两种类型的核营酸，一种是脱氧核糖核酸( d n a ) ， 另一种是核糖核酸( r n a ) 。跟蛋白质分子相似，d n a 分子也是由简单的小分予链接 而成的，它包括两条被称作带的链。j 组成每一条带的小分子叫做核苷。一个d n a 核苷由一个脱氧核糖，一个磷酸残基，一个氮基组成。d n a 分子由四种不同的碱基 或者核苷构成，这四种碱基分别是腺嘌呤( a ) ，鸟嘌呤( g ) ，胞嘧啶( c ) 和胸腺嘧 啶( t ) ，其中a 和g 是属于嘌呤组，而c 和t 是属于嘧啶组。单条d n a 带具有规 范的方向，它的长度是由碱基或者核苷来度量的。 d n a 分子比蛋白质分子长得多。例如，有的d n a 分子有上百万个核苷长，相反 蛋白质充其量是几千个残基长。而且氨基酸就是由d n a 的三个核苷一组核营编码 而成，这样的一组核苷叫密码子。 一个d n a 分子的两条带紧紧缠绕成空间螺旋结构。这个著名的双螺旋结构是 j a m e sw a t s o n 和f r a n c i sc r i c k 在1 9 5 3 年发现的。这样的一条带非常稳定，是因为 一条基带上的一个残基必须与另一条基带上的一个残基绑定。规则是这样的：碱 第一章绪论 3 基a 必须与碱基t 配对，而碱基g 必须跟碱基c 配对。这些比对就叫做w a t s o n c r i c k 碱基对，一般来说，碱基对( b p ) 被用来计算d n a 分子的长度。 r n a 分子与d n a 分子相似。它们之间的组成和结构差别很少。在r n a 中，核糖 代替了脱氧核糖，尿嘧啶( u ) 代替了胸腺嘧啶( t ) ，所以尿嘧啶( u ) 跟腺嘌呤 ( a ) 配对。最重要的差别是r n a 不会形成一个双螺旋结构，从功能上来说，d n a 分子在遗传过程中的作用是编码信息，而在细胞核中的多种类型的r n a 则起到不 同的表达作用。 两种类型的核苷酸，d n a 和r n a ，在分子生物信息学中使用的d n a 序列是 用字母集( a ，c 。g ，t ( u ) ) 的四个字母组成的字符串来表示的。 1 2 2 生物信息学的序列比对 在生物信息学中，生物信息最基本的表达形式就是一维分子的排列顺序一序 列，包括上面介绍的核营酸序列和蛋白质序列，最基本的仍是d n a 序列。 自从1 9 5 3 年d n a 的螺旋结构被发现和新的d n a 测序技术出现以来，情况有了 重大的突破，生物信息量呈指数式的增长，呈现出“大爆炸”的局面。截至到1 9 9 8 年1 0 月份，已发表了约2 0 亿个碱基对的d n a 序列，丽每天增长的量达到1 0 8 一1 0 7 碱基对。在面对这些海量的数据，怎样获知这些数据之间的复杂关系以及从这些 数据中获得有用的生物信息和知识，这些都是科学家目前所面临的一项挑战性工 作。例如人和老鼠的基因组大小相似，都含有约三十亿碱基对，基因的数目也类 似。可是人类和老鼠差异却如此之大，这是为什么? 以及各种物种之间差异或者 相似性有多大，测量这些差异或者相似性的方法是什么? 在生物信息学中，解决上面提到的诸多闯藏的基本方法就是序列之间的比对。 序列比对就是对两个或者多个d n a 或者蛋白质序列避行比较，从而找出其相似性 或不相似性。序列比对在生物信息学中是非常重要的，是进行其它生物信息学研 究的基础，例如基因识别和d n a 序列分析、蛋白质结构预测等，进一步可以进行 生物同源性比较等等。 1 2 3 计算机科学技术在序列比对中的应用 在对d n a 序列和蛋白质序列进行比对的过程中，计算机科学技术是一种主要 比对工具。由于d n a 或者蛋白质的序列一般都比较长，这些比对过程所需的计算 量都比较大。因此它对高性能计算环境提出了很高的要求。 高性能的计算环境包括计算机硬件系统、操作系统软件和网络三大主要部分。 目前从计算机体系结构上提高计算能力的主要途径为大规模并行处理。而大规模 4 基于p c 机群系统的序列比对并行f t l s a 算法研究 并行处理( m p p ) “”早已是超级计算机应用中的一项前沿课题。美国在1 9 9 2 年提出 的高性能计算与通信( h p p c ) 计划当中，就已将超级计算机用于人类基因的研究作 为重大挑战性应用课题来公布，并将提供3 t ( 即1 t e r a f l o p s 计算能力、1 t e r a f l o p s 主存储器、l t e r a f l o p s 的i o 带宽) 性能的计算机作为h p c c 计划的研究目标。目 前，依据y o nn e u m a n n 结构设计的用于并行处理的超级计算机按物理结构分为共 享公用存储器、分布式共享存储器和分布式存储器。按数据和指令关系分为s i m d 和m i m d 两大类。”1 。多线程和数据流计算机则是在开发大规模并行计算时提出的全 新的体系结构思想。显然，开发研制具有m p p 能力的超级计算机需要巨大的人力、 物力与财力的投入。以我国的国情，近期内开发与推广应用超级计算机的能力非 常有限。但是，随着p c 机群系统的发展以及它的独特的优势( 具有成本低、开发 周期短、易维护性、伸缩性好、高可靠性、开发工具通用且丰富等优势) ，在现有 的条件下，加强p c 机群系统在序列比对并行高性能计算方面的应用是一种很好的 策略。 1 3 目前国内外研究的现状 如前所述，关于序列比对算法已经经历了几十年的发展，并且每个时期都有 相应的算法。这些算法基本上是建立在动态规划算法之上的。如图1 1 所示。 图1 1 部分相关序列比对算法 局部比对算法主要着眼于序列中的某些特殊片断，比较这些片断之间的相 似性。而全局比对算法主要考察序列之间的整体相似性。在目前全局比对算法中， 比较常用的三种算法是：n e e d l e m a nw u n s c h 算法、h i r s c h b e r g 算法和f a s t l s a 算 法。其中，n e e d l e m a nw u n s c h 算法的时间复杂度和空间复杂度都是平方级的； h i r s c h b e r g 算法的时间复杂度也为平方级的，而空间复杂度却为线性的，虽然 h i r s c h b e r g 算法的空间复杂度降到了线性空间，但是它是以牺牲时间复杂度来换 第一章绪论 取空间复杂度的降低；f a s t l s a 是这三种算法中效率最好的算法，它在保持线性空 间复杂度的同时，使得算法时间复杂度有较大的改善。虽然f a s t l s a 算法在串行 上可以获得好的效率，但由于它的计算量十分巨大和在计算时所需主存容量也很 大，所以将其在高性能计算机上做并行处理可以解决这些问题。同时也可获得更 好的效率。本文的并行算法就是建立在这种效率较高的算法之上。 1 4 课题研究内容与意义 本课题的研究内容是：通过对效率较高的f a s t l s h 算法的分析，找出影响算 法效率的关键之处，利用目前的高性能并行计算机平台，将该算法做并行优化处 理。本文将这种并行优化处理的f a s t l s a 算法称为并行f a s t l s a 算法。而本文的 主要工作就是如何将f a s t l s a 算法的关键部分在高性能平台上做并行优化改进并 从理论上分析了该算法的时间和空间复杂度，并用实验结果来对理论上分析的结 果进行评估。在改进这种算法时，本文使用了“并行波前机制”和网格缓冲区以 及四方格缓冲区。由于并行f a s t l s a 算法处理的数据是海量级的。而p c 并行机群 系统处理海量数据方面有其独特的优势： 1 运行平台搭建的简易性； 2 平台具有高性能的计算能力； 3 平台具有高可用性、开发工具通用且丰富； 4 平台具有可扩展性、易维护性、高可靠性： 5 。运行平台搭建的低成本； 所以本文的并行f a s t l s a 算法的实验平台采用这种p c 并行机群系统。 本课题的意义是：通过将并行f o s t l s a 算法在p c 并行机群系统运行并分析算 法产生的结果，从中得出此并行f a s t l s a 算法的时间和空间复杂度降到更低，使 算法的运行效率、加速比及执行时间性能更好。 1 5 后续章节的安排 下面对本文后续章节做一个简要介绍： 第二章主要介绍跟序列比对相关的算法，也就是跟本文有关的 n e e d l e m a n w u n s e h 算法、h i r s c h b e r g 算法和f a s t l s a 算法。在获得优化比对路径 的序列比对中，它们是曾经被广泛使用过的三个序列比对算法。f a s t l s a 算法是建 立在h i r s c h b e r g 算法的基础之上的。而f a s t l s a 算法又是本文的并行f a s t l s a 算 法的基础。在对这三个串行算法进行详细介绍的基础上，对每一个算法进行了详 细的算法分析，包括时间复杂度、空间复杂度以及效率等方面的分析。 6 基于p c 机群系统的序列比对并行f a s t l s a 算法研究 第三章主要介绍并行f a s t l s a 算法。首先详细地介绍如何实现并行f a s t l s a 算法，然后对该算法进行分析，最后从理论上给出了并行f a s t l s a 算法的时间和 空问复杂度的计算和说明。 第四章主要介绍并行f a s t l s a 算法的实验环境，即搭建基于l i n u x 和软件分 布式共享内存( d s m ) 的p c 并行机群系统，并探索可扩展的p c 并行机群系统的构建 和实现方法。同时说明了并行f a s t l s a 算法在p c 机群系统运行的软硬件环境。最 后讨论了并行f a s t l s a 算法在软件分布式共享内存j i a j i a 系统中的简便实现。 第五章主要介绍并行f a s t l s a 算法在p c 机群系统的运行情况以及对运行结果 进行分析。首先解释了影响并行算法性能的因素。在实验的过程中，本文使用两 对真正的基因序列来验证这个算法，并画出性能比较图，并对性能比较图进行分 析。最后从分析的结果得出，并行f a s t l s a 算法的时间、空间复杂度与算法本身 理论计算结果的时间、空间复杂度是相一致的。 最后一章对全文所作的工作做了概括性的总结，同时提出了将来对并行 f a s t l s a 算法应该改进的地方。 第二章相关算法 第二章相关算法 7 对于如何找到两个生物序列比对的最优比对值，一个比较自然的方法是将这 两个序列所产生的所有可能的比对都穷举出来，然后从这些比对中选出分值最大 的也就是最优的比对。然而，随着比对序列的长度增加，比对结果将呈指数级增 加。这种穷举算法运算起来效率非常低，有时在算法上根本无法实现。当然，目 前有很多的算法比穷举算法效率高很多。下面几节将对序列比对算法基础以及这 些典型算法做一描述。 2 1 序列比对算法基础 在生物信息学里面，利用序列比对算法来进行生物序列之间的相似性比较， 在计算机科学领域里面主要体现为字符串的匹配和查找。为了定量的分析序列之 间的相似性，计算机科学家将序列之间的相似性用字符串比较所获得的分值来度 量。具体见下面的定义： 定义一：两个任意的字符x 和y ，q 。表示x 与y 比较时的分值： f 2 如果x = y ( 也就是x 与y 匹配) 盯( 。) = - 2x = i _ t 或者y = - 也就是g a p _ p e n a l t y - 2 式( 2 一1 ) l 一1如果x y ( 也就是x 与y 不匹配) 式( 2 一1 ) 中x = o 或者y = o 在生物信息学上表示：在生物进化过程中出现了变异 ( 插入和删除) 现象。在算法中用空位来表示这种现象，这就是空位罚分的由来。 引入空位罚分的目的是补偿那些在序列中出现的插入或者删除，从而获得更好的 序列之间的相似性。空位罚分的模型主要有权值恒定模型和仿射罚分模型“”，权 值恒定模型就如式( 2 一1 ) 所示取一个常量负值，而仿射罚分模型就是用一个附加的 罚分去乘空位的长度“。 事实上，在生物信息学中，序列之间的相似计分值不像式( 2 - 1 ) 定义的那么简 单，而是与在生物基因中按一定数目的进化步骤把一个序列中的某一个位置上的 字母转化成另一个序列相应位置的字母所产生的统计概率有关。至于蛋白质，把 氨基酸进行比较就可以获得它的比对分值了。例如，具有相似大小尺寸的氨基酸 之间的替换概率比起那些大小尺寸相差很大的氨基酸之间的替换概率要大。氨基 酸容易跟水分子结合，这也影响相互变异替换的概率。由于蛋白质之间的比较经 常用来建立序列之间的进化关系，因此在算法中尽量使用那些精确反映统计概率 的计分函数。在算法中，一般利用已经由别人创建且经过验证的计分矩阵。比 如，众所周知的p a m 和b l o s u m 矩阵。关于p a m 和b l o s u m 的介绍以及在生物序列 比对中的如何选择可以参考相关文献“1 。 基于p c 机群系统的序列比对并行f a s t l s a 算法研究 2 2 1 算法思想 2 2n e e d l e m a n w u n s c h 算法 n e e d l e m a n w u n s c h 算法是1 9 7 0 年被提出来的，它是针对寻求最优序列比对这 一问题所设计的动态规划寻优策略。动态规划寻优策略是由b e l l m a n 在5 0 年代提 出的，它的理论基础是最优化原理。假定两个序列a 和b ，这个算法从两个序列较 短的前缀开始找到一个局部优化的比对分值，然后利用前面的结果来解决较长的 前缀序列的优化比对分值。在a 和b 之间的优化比对分值找到以后，一个或者多 个的优化比对序列就在后处理回溯阶段能被求出来了。算法的详细求解过程见下 面的例子： 假设序列a 具有m 个字符长，而序列b 具有n 个字符长。那么字符串a 用数 组d 1 f 0 i m 表示，当i = 0 时表示字符串a 是空串。同样的，字符串b 用数组 6 1 力，0 ，s m 表示，当j = o 时表示字符串b 是空串。n e e d l e m a n w u n s c h 算法逐 步计算数组a 和b 的f j i f 缀的优化比对分值，而数组a 的前i 个与b 的前j 个优化 比对分值存放在具有( m + 1 ) 行m + 1 ) 列的n e e d l e m a n - w u n s c h 算法矩阵s 的第( i ， j ) 位置上。并且矩阵的第( i ，j ) 位置的值被称作s 【f ，刀，此算法的第一阶段的目的 就是计算出s m ，n 】。如果要计算s m ，疗】，矩阵中所有的单元都必须要参与计算。 由此看来，n e e d l e m a nw u n s c h 算法是基于一个二维矩阵。 为了简单起见，对于本节的例子。采用的空位罚分系统是权值恒定模型而不是 仿射空位罚分模型，也就是说空位罚分取式( 2 一1 ) 中常量负值。 对于式( 2 - 1 ) 的计分系统来说，n e e d l e m a n w u n s c h 算法对带有空位罚分的矩阵 s 的第一行及第一列的初始值如下； s i ，0 】= i x g a p p e n a l t y ，v f ，0 f 州 斗、 s o ， = ，g a p p e n a l t y ，o j s 雅 实际上式( 2 2 ) 是根据式( 2 - 1 ) 得来的，因为对于s i ，o 】和s o ，刀这种情况来说比对 的结果只有一种，那就是一个序列跟另一个空序列之间的比对，即一个序列中的 一个空位跟另一个序列里面的一个字符比较。当然，如果两个序列都为空，那样 的比较是没有意义的。 为了计算出n e e d l e m a n - w u n s c h 算法矩阵s 中单元( i ，j ) 的值，根据算法的设 计思想，必须依据如下的三种情况： 己知s i - 1 ，j - 1 和a i 与b j 比对的结果； 已知s i ，j 1 和一个空位与b j 比对的结果； 已知s i 一1 ，j 和a i 与一个空位比对的结果； l 面三种情况用图形表示如下： 第二章相关算法 s i 一1 ，j 一1 s i 一1 ，j s h j - 1 h 面夏耐s l - 1 ，j 图2 1n e e d l e m a n w u n s c h 算法矩阵中的数据依赖关系 9 上面图2 1 表示了矩阵中的数据依赖关系。从生物信息学上来说，在两个比对序 列中的同一个位置出现两个空位是没有任何意义的。因此，n e e d l e m a n w u n s c h 算 法矩阵单元s i ，j 的值是通过由下面的公式得到的； 球，j 】：m a x s i 一1 ，一l 】+ 吼， s i 一1 ，j + g a p p e n a l 妒 s 【i ，_ ，一1 】+ 劬一p e n a l t y 式( 2 - 3 ) 从式( 2 3 ) 中可以看出s i ，j 的值仅依赖于矩阵单元 i 一1 ，j - 1 或者 i ，j - 1 或 者 i _ 1 ，j 的值。因此最近于单元( i ，j ) 的这三个值在计算s i ，j 之前必须有效。 由于存在初始条件，计算n e e d l e m a n w u n s e h 算法矩阵可以一行按一行来计算，并 且对于每一行的计算必须从左到右计算出每一个单元的值。 图2 2 描述了利用n e e d l e m a n w u n s c h 算法计算矩阵s 的过程以及图2 3 利用 这个矩阵通过回溯的方法求出n e e d l e m a n w u n s e h 算法的最优比对路径。序列 a = a t a g t c ( 垂直放置) ，b = a t t a g g c ( 水平放置) ，计分系统使用式( 2 - i ) ，初始条件 见式( 2 - 2 ) 以及式( 2 3 ) 。 attaggc 02- 46- 8- 1 0 - 1 2- 1 4 a一220_ 2- 468- i 0 t- 4o4202- 46 a一62234202 g一84ol2642 t- i 06220453 c- 1 28_ 4o1237 图2 2n e e d l e m a n - w u n s c h 算法矩阵 l o 基于p c 机群系统的序列比对并行f a s t l s a 算法研究 这个优化比对的分值从矩阵的单元( m ，n ) = ( 6 ，7 ) 可以得到，它的值是7 。 出于n e e d l e m a n w u n s c h 算法是建立在动态规划寻优策略基础之上，所以 n e e d l e m a n w u n s c h 算法不仅要计算出序列a 和b 之间优化比对的分值，而且还要 找到两个序列之间的一条或者多条优化比对路径。也就是说要利用 n e e d l e m a n w u n s c h 算法矩阵s 来从矩阵s 中的( m ，n ) 单元开始到( 0 ，o ) 单元结束 之间寻找一条或者多条优化比对路径，这些路径具有下面的属性： 如果( i ，j ) 单元所代表的点属于这条最优路径，那么单元( i ，j ) 一( i 一1 ，j 1 ) 的值在式( 2 - 3 ) 中是最大值： 如果( i ，j 一1 ) 单元所代表的点属于这条最优路径，那么单元( i ，j ) 一( i ，j - 1 ) 的值在式( 2 - 3 ) 中是最大值； 如果( i l ，j ) 单元所代表的点属于这条最优路径，那么单元( i ，j ) 一( i 一1 ，j ) 的值在式( 2 - 3 ) 中是最大值； 一条优化比对路径的建立就是通过对n e e d l e m a n w 吼s e h 算法矩阵s 使用这种 回溯方法求得的。在求矩阵s 的最优比对路径时，算法的回溯方法从单元( m ，n ) 开始，不停地使用公式( 2 - 3 ) 中的最大值，一直达到( 0 ，0 ) 单元为止，从而求得最 优比对路径。同时也要注意：在回溯的过程中可能会产生不止一条最优比对路径， 这种情况下导致了在n e e d l e m a n w u n s c h 算法下产生了多条最优比对路径，当然通 过回溯得到的最优比对路径在计算机中可以用堆栈的方法获得。 幽2 3n e e d l e m a n w u n s c h 算法回溯过程求出序列a 和b 的优化比对路径 a t a g t c 第二章相关算法 从图2 3 中可以看出n e e d l e m a n ，w u n s c h 算法通过回溯获得了两条最优比对路 径，第一条最优比对路径是： 口：a t a g t c b ：a t t a g g c 另一条最优比对路径： 口：a t a g t c b ：a 7 r t a g g c 2 , 2 2 算法伪代码描述 算法：n e e d l e m a n w u i l s c h ； 输入：序列a 和b ； 输出：在数组a l i g n _ a 和a l i g n _ b 中存放着优化比对路径，优化比对分值存 放在矩阵的单元( m ，n ) 中； m = h n = s 0 0 = 0 f o ri = lt omd o s i ，0 = i g a p _ p e n a l t y l i ，0 = ( i 一1 ，0 ) f o rj = lt ond o s 0 ，j = j x g a p _ p e n a l t y l 0 ，j = ( o ，j - 1 ) f o ri = lt omd o f o rj = lt ond o s i ，j = m s x ( s 卜1 ，j - 1 + a l i g n ( a i ，b 【j j ) ， s i ，j - 1 + g a p _ p e n a l t y ，s 卜i ，j ， s i - 1 ，j + g a p _ p e n a l t y ) “i ，j = m a x s u p p l y ( ( i - i ，j - i ) ，( i ，j - i ) ，( i 一1 ，j ) ) i = m j = n l e n = o w h i l ei 0o rj 0 i fl i ，j = = ( i _ 1 ，j - 1 ) t h e n a l i g n _ a 1 e n = a i a l i g n _ b 1 e n - b j e l s ei fl i ，j = = ( i 。j - 1 ) t h e n a t i g n _ a 1 e n = l a l i g n _ b 1 e n = b j e l s e a l i g n _ a l l e n = a i a l i g n _ b 1 e n - i 一 l e n = l e n + 1 ( i ，j ) = l i ，j r e v e r s e ( a li g n _ a ) 1 2 基于p c 机群系统的序列比对u 弗行f a s t l s a 算法研究 r e v e r s e ( a li g nb ) r e t u r ns m ，n 闰2 4n e e d l e m a n w u n s c h 算法的伪代码 算法中数组l i ，j 被用来产生优化比对路径。伪代码中的( i ，j ) 表示矩阵s 中位置( i ，j ) 的值。函数m a x s u p p y ( ) 返回的是与单元( i ，j ) 相邻的有数据依赖关 系的单元值的位置。而且这个算法仅返回一条最优路径而不管算法中存在多少条 最优路径。例如如果从式( 2 3 ) 中求得的值都是一样的话，那么返回的比对结果是 序列a 中一字母和序列b 中一字母；而序列b 中为一空位跟序列a 中一字母比对 为其次。最终结果的优化比对序列存放在数组a l i g n _ a 和a l i g n _ b 中，优化比对 的分值就是s m ，n 。 2 2 3 算法分析 对n e e d l e m a n - w u n s c h 算法来说，分析它的时间和空间复杂度非常容易。前 面的两个循环用于初始化数组，所以花费的时间为0 ( m ) 和d ( 疗) 。下面的两层嵌套 循环所花费的时间跟矩阵的行数与列数呈正比，故时间复杂度为o ( m x n ) 。比对的 获得在最后一个循环中，时间复杂度为o ( 1 e n ) ，由于m 硎口l ，1 6 i ) s l e n m + 九，最 后一个循环在最坏的情况下的时间复杂度为0 ( m + n ) 。因此，整个算法的时间复杂 度为o ( m h ) 。 n e e d l e m a n w u n s c h 算法的空间复杂度主要就是n e e d l e m a n - w u n s e h 算法矩阵s 和临时矩阵l 所占用的空间，所以，此算法的空间复杂度为d ( 2 x m 疗) 。并且数 组a l i g n a 和a l i g nb 所需的空闻为：o ( 1 e 吣= o ( m + n ) 。故此算法的空间复杂度 为o ( m n ) 。n e e d l e m a n - w u n s c h 算法的时间和空间复杂度都是o ( m 珂) ，特别是当 输入的两个序列相等且等于n 时，算法的时间和空间复杂度变成了o ( n 2 ) 。 从历史的角度来看，n e e d l e m a n 和w u n s c h 提出这个关于生物信息学序列比 对的算法对当时的生物学家来说是非常重要的，并且此算法也被人们广泛的接受。 本论文对于n e e d l e m a n w u n s e h 算法不进行过于复杂的分析。在本论文后面的章节 中对该算法的实验显示，这个算法的时间复杂度实际达到了立方【1 6 】。目前，就有 很多时间复杂度只有平方的算法可以使用，其中就包括仿射空位罚分的 n e e d l e m a n w u n s c h 算法【1 6 1 。n e e d l e m a n - w u n s e h 算法中使用的空位罚分是常量， 该常量只不过是仿射空位罚分函数的一个特例。尽管n e e d l e m a n w u n s c h 算法不是 很完善，但是n e e d l e m a n w u n s c h 算法经常被用来设计基于动态规划的全局比对 算法f 1 6 】。 第二章相关算法 2 3 1 算法背景 2 3h i r s c h b e r g 算法 由于n e e d l e m a n w u n s c h 算法需要平方级的空间复杂度，这对于非常长的序列 来说是非常的不适合。例如，如果要比对具有1 0 0 ，0 0 0 个碱基的d n a 序列( 这在 生物信息学中很常见) ，假设n e e d l e m a n w t m s c h 算法矩阵中每个单元仅分配四个 字节的整形数空间单元用来存放值的话，那么光存储这些单元的值就需要4 0 g 的 存储空间，更不用说运算。即使这个比对的n e e d l e m a n w u n s c h 算法矩阵的值能全 部存放到计算机的主存中去，那么比对操作的时间性能将不次于0 ( 1 0 ”) 。通过分 析n e e d l e m a n w u n s c h 算法，可以将空间复杂度降到线性空间。 根据图2 1 所表示的数据依赖关系，也就是n e e d l e m a n - w u n s c h 算法矩阵中的 行i 仅仅需要行i - 1 的值，和式( 2 2 ) 的初始条件。可以对n e e d l e m a n w u n s c h 算 法进行改进，具体见下图2 5 中的算法伪代码描述，该算法使得空间复杂度降到 了线性空间。 算法l a s t r o w ： 输入：序列a 和b 输出：数组l l m = hn - = h f o rj = 0t oad o l l j = j g a p p e n a l t y f o ri = lt omd o o l d = l l o l l o = i g a p _ p e n a l t y f o r j = lt ond o t e m p = l l j + l l j = m a x ( o l d + a l i g n ( a i 。b j ) ，l l j 1 + g a p _ p e n a l t y ， l l j + g a pp e n a l t y ) 0 1 d = t e m p 图2 5l a s t r o w 算法的伪代码 在l a s t r o w 算法中输入的是字符串a 1 m 和b 1 ，n ，输出结果是矢量数 组l l 。该矩阵存放的值与n e e d l e m a n w u n s c h 算法所计算出来的n e e d l e m a n w u n s c h 算法矩阵最后一行的值是一样的，并且数组l l 中最后一个元素值就是最优比对分 值。然而，从算法中可以看出l a s t r o w 算法仅使用了n + 1 个内存单元来计算矢量 数组l l 。因此该算法的空间复杂度与序列的长度相一致，从而使空间复杂度降到 了线性空间。 l a s t r o w 算法的正确性需要下面的三条规则来得以证实： 1 4 基于p c 机群系统的序列比对并行f a s t l s a 算法研究 - 在第i 步的最外一层循环的开始处，矢量数组l l 必须存放的是行卜1 单 元的值； - 在最内一层循环中，在第j 步的开始处，矢量l l o j - 1 必须存放第i 行 的值，相反矢量l l j n 必须保存有行i - 1 的值； 在第j 步，o l d = s i l ，j 1 ； l a s t r o w 算法步骤跟n e e d l e m a n w u n s c h 算法极其相似，但是该算法仅使用了一个 一维矢量数组l l 和两个临时变量。由于l a s t r o w 算法也是两层循环，所以它的时 间复杂度仍为o ( m 玎) 。 l a s t r o w 算法计算的序列之间的相似性( 优化的比对分值) 存放在矢量数组 l l 中最后一个元素。想要像n e e d l e m a n - w u n s c h 算法那样，利用对 n e e d l e m a n w u n s c h 算法矩阵的回溯过程来获得两个序列最优比对路径在l a s t r o w 算法中是不可行的，该算法是被h i r s c h