（计算机应用技术专业论文）并行遗传算法在生物序列比对中的应用研究.pdf

中文摘要 序列比对是生物信息研究的基础和前提，它为蛋白质结构和功能预测、系统 发育树的建立、新药物设计等许多生物研究提供了有用的信息。但此问题至今仍 是计算分子生物学中尚未解决的一个难题，已经证明多序列比对问题是一个 n p c o m p l e t e 问题。这是一个极富有挑战性的工作。 国内外现有的算法大致可以分为三大类：同步法、步进法和迭代法。它们都 存在一些问题，例如：同步法只能比对8 条之内的序列，步进法有时会陷入局部 最优解，迭代法运算速度很慢等等。 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 算法 和遗传算法有机结合应用于多序列比对，来提高多序列比对的运算精度和计算速 度。新算法采用新的编码方法，使其能适应各种长度各种大小的序列比对；随机 产生初始种群以确保在整个解空间内搜索求解；在交叉算予中选择父代中适应值 高的子片段组成予代，保证产生更优的子代；在变异算子中引进了 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 s t r a c t 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 ( m s a ) i so fg r e a tv a l u et ot h er e s e a r c hi n b i o i n f o r m a t i c s s i n c ei t s u p p o r t s t h e d e v e l o p m e n t o fg e n e t i cs c i e n c e ss u c ha s e x p e c t i n gt h ef u n c t i o n s & s t r u c t u r e so fp r o t e i n ，t h ed i s c o v e r i n gt h ee v o l u t i o n a r y r e l a t i o n s h i p s ，a n dd e v e l o p i n gn e wm e d i c i n e h o w e v e r , m s ap r o b l e m i sk n o w nt o b en p h a r d ，m o r es t i l ll e f t u n d e t e r m i n e d o b v i o u s l y , m s a i s a m o n gt h e m o s t i m p o r t a n ta n dc h a l l e n g i n g t a s ki nc o m p u t a t i o n a l b i o l o g y a l g o r i t h m s a r ec l a s s i f i e dt h r e e s p e c i e s ：d y n a m i cp r o g r a m m i n g m e t h o d ， p r o g r e s s i v e m e t h o da n di t e r a t i v em e t h o d i ns o n l e s e n s e ，t h e y a l lh a v es o m e d e f i c i e n c i e s f o re x a m p l e d y n a m i cp r o g r a m m i n gm e t h o dc a na l i g nw i t ho n l y8 s e q u e n c e s ；t h em a i nd i s a d v a n t a g eo fp r o g r e s s i v ea l g o r i t h m i st h el o c a lm i n i m u m p r o b l e m a n di t e r a t i v ea l g o r i t h mi st i m ec o n s u m i n g n e e d l e m a n w u n s c h ( n w ) a l g o r i t h m i sac l a s s i c a la l g o r i t h ma m o n gt h eo p t i m u m p a i r w i s ea l i g n m e n t s g e n e t i ca l g o r i t h m ( g a ) i sa na p p r o a c ho f i t e r a t i v ea l g o r i t h m s ， w h i c ha p p e a r sc a p a b l eo ff i n d i n gg l o b a l l yo p t i m a lm u l t i p l ea l i g n m e n t s t h i sp a p e r c o m b i n e sn w a l g o r i t h mw i t hg a f o rm u l t i p l es e q u e n c e sa l i g n m e n tt oe n h a n c ei t s s p e e d a n d p r e c i s i o n t h i sa l g o r i t h ma d o p t sa i l e wc o d em e t h o dt om a k ei ta d a p t a b l et o d i f f e r e n tl e n g t h sa n ds i z e so fs e q u e n c e s w ep r o d u c er a n d o mi n i t i a l p o p u l a t i o nt o e n s u r es e a r c hf o rs o l u t i o n si nt h ew h o l es o l u t i o ns p a c e ，s e l e c tb e t t e rs e c t i o n si nt h e p a r e n t c h r o m o s o m e si nc r o s s o v e r o p e r a t o r t o p r o d u c e b e t t e r c h r o m o s o m e ，a n d i n t r o d u c en w a l g o r i t h mi n t om u t a t i o no p e r a t o rt os p e e d u pl o c a ls e a r c h t oe n h a n c e t h es p e e d ，t h i sp a p e rc a n d y n a m i c a l l yc r o s s o v e ra n dm u t a t i o no p e r a t ew i t hm u l t i p o i n t a c c o r d i n gt os e q u e n c el e n g t h t h i sp a p e ra d o p t sa s y n c h r o n o u sc o m m u n i c a t i o nt o d e c r e a s et h e w a i t i n gt i m eb e t w e e np r o c e s s e s ，t oc o n q u e rb o t t l e n e c kp r o b l e m sb y s y n c h r o n o u sc o m m u n i c a t i o na n dt oh e i g h t e nf u r t h e ro p e r a t i o ns p e e d i nc o n c l u s i o n as e r i e so fe x p e r i m e n t a ld a t aa n dt h e a n a l y s i s o fr e s u l t s d e m o n s t r a t et h a tt h i sn e w a p p r o a c hc a nf i n ds o l u t i o n sm o r ee f f i c i e n t l yt h a nt r a d i t i o n a l i t e r a t i v e a l g o r i t h m s m o r e o v e r , i t s s o l u t i o n sa r ea s g o o da s ，e v e n b e t t e rt h a n p r o g r e s s i v ea l g o r i t h m si np r e c i s i o ne x c e p ti ns e v e r a ls p e c i a lc a s e s k e yw o r d s ：s e q u e n c ea l i g n m e n t ，g e n e t i ca l g o r i t h m ，p a r a l l e la l g o r i t h m ， n e e d l e m a n - w t m s c ha l g o r i t h m ，b i o i n f o r m a t i c s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨壅盘茔或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 秘前 签字日期：如啦年，月 f 日 学位论文版权使用授权书 本学位论文作者完全了解盘注盘堂有关保留、使用学位论文的规定。 特授权苤洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 旃芍 导师签名：孑长考吁莓 签字日期：动v 年d 月i f t 签字日期：即口妒年五月( f t i 第一章绪论 1 1 生物信息学 第一章绪论 人类基因组计划( h g p ，h u m a ng e n o m ep r o j e c t ) 正式启动于1 9 9 0 年，这 是一个跨世纪、跨国界的最伟大的生命科学工程，经美、英、法、德、日、中6 国的合作和努力，于2 0 0 0 年完成全部序列测序工作，标志着二十一世纪是生命 科学的世纪。随着分子生物科学的长足进展，把生命活动的物质基础追溯到核酸 和蛋白质两大类生物大分子的序列上，它们构成了生物数据的主要部分。关于这 些生物大分子的结构、相互作用和生物功能的研究，产生了大量的生物数据。为 了更好地组织、发掘、再利用这海量的原始生物数据，以加速生命科学的进步和 发展，计算机技术被越来越多地应用到生物研究中，并发挥着至关重要的作用。 从而一个崭新的领域一一生物信息学( b i o i n f o r m a t i c s ) i g 速发展起来，它是应用计 算机和信息技术搜集、储存、分析、整理各种生物信息，并予以管理和利用的一 门交叉学科【1 。生物信息学充分发挥计算机技术和网络技术在生物学科各个领 域的数据处理分析能力，将基因的结构、蛋白质功能以及物种的进化在基因信息 的基础上统一起来。 生物信息学是一门生物学与信息学交叉而成的年轻学科，旨在研究生物系统 与生物过程的信息量与信息流，以便支持人口健康、农业生产、创新材料和资源 环境等领域的研发计划。广义地说，生物信息除了基因组信息之外，还包括基因 产物( 蛋白质或核酸) 的结构和功能，以及生物之间的进化关系等其他信息资源。 生物信息学最终是一门研究生物系统中信息现象的学科，它的主要研究内容包括 2 ，3 】： 1 ) 大规模基因组测序中的信息分析，新基因的发现和鉴定。 2 ) 基因组相关信息的收集、储存、管理与提供。 3 ) 遗传密码的起源与生物进化分析。 4 1 完整基因组的比较研究。 5 ) 大规模基因功能表达谱的分析。 6 ) 蛋白质分子空间结构预测、模拟与药物分子设计。 1 2 序列比对意义 序列比对( s e q u e n c ea l i g n m e n t ) 是生物信息研究的基础和前提。序列比对 不仅是数据库搜索、基因比较和新基因发现的最常用和最经典的序列分析手段， 第一章绪论 而且序列比对的结果作为二级生物数据，为蛋白质结构和功能预测、系统进化树 的建立、基因病的治疗、新药物设计 4 等许多生物研究提供了宝贵的信息。 序列比对是指通过一定算法对两个或多个核酸或氨基酸序列( 即：字符序列) 对齐进行比较，逐列比较其字符的异同，判断它们之间的相似程度和同源性，从 而推测它们的结构、功能以及进化上的联系。序列比对包括同一个序列内不同片 段的比较，以及两个或多个序列的对比。最基本的比对是蛋白质序列之间或核酸 序列之间的两两比对，通过比较两个序列之间的相似区域和保守性位点，寻找二 者可能的分子进化关系。进一步的比对是将多个蛋白质或核酸序列同时进行比 较，寻找这些有进化关系的序列之问共同的保守区域和位点，从而探索导致它们 产生菸同功能的序列模式。比对的主要目的在于阐明序列之间的同源关系，并且 将其中相似性的结构区域突出显示，以及从已知序列预测新序列的结构和功能 5 。 序列比对是生物信息学计算的核心。尤其对新测定的序列，必须应用计算机 工具和程序，在序列数据库中进行查询检索，通过将未知序列与整个数据库中的 已知序列进行比较分析，来推测这个序列的性质、结构、功能、同源性、变异性， 从而进一步了解其生物进化关系。 d n a 测序自动化引起生物信息爆炸，使得生物大分子序列数据激增，而蛋 白质结构测定的速度远不能与之相比。从生物数据库的中序列信息直接推断其可 能的生物学功能，显然比从实验室测定其功能要快得多，序列分析成为生物信息 学研究的有用工具。 将查询序列与整个数据库的所有序列进行比对，从数据库中获得与其最相似 序列的已有的数据，能最快速的获得有关查询序列的大量有价值的参考信息，对 于进一步分析其结构和功能都会有很大的帮助。此外，还可以把蛋白质序列与核 酸序列相比来探索核酸序列可能的表达框架；把蛋白质序列与具有三维结构信息 的蛋白质相比，从而获得蛋白质折叠类型的信息。近年来随着生物信息学数据大 量积累和生物学知识的整理，通过比对方法可以有效地分析和预测一些新发现基 因的功能。 此外，序列比对，尤其是多序列比对在生物信息工程实践中起了至关重要的 作用。例女f i - 遗传疾病的诊断和基因治疗。众所周知遗传病是由于染色体上的某 些核苷酸被取代、丢失或变异造成，通过对正常人与患病者的基因进行序列比对， 可确定病变基因位置，进一步进行有针对性的基因治疗。序列比对还可以帮助我 们建立系统的染色体进化树，通过同已知功能和结构的序列相比较，能预测未知 序列的某些机构特征和功能。例如在对s a r s 冠状病毒的研究中，就是根据病毒 分类学，运用比对软件对目前已知的所有1 1 个s a r s 冠状病毒的基因组序列进行 第一章绪论 多序列比对分析，根据比对的结果，构建冠状病毒的系统进化树( 如图1 - 1 ) ，对 s a r s 冠状病毒做出初步的分析，了解它和其它已知冠状病毒的关系，从而进一 步进行流行病学分析和治疗上的研究。 图1 1s a r s 冠状病毒的进化树 1 3 本课题研究意义及主要内容 由于多序列比对( m u l t i p l es e q u e n c ea l i g n m e n t ，简称m s a ) 能够揭示两个 序列比对所不能发现的序列微弱相似性、序列模式和功能位点，因而对蛋白质和 核酸序列的结构、功能和进化研究更加有用。所以一种速度快、精确度高的多序 列比对算法，对于生物学研究领域具有非常重大的意义。已经证明多序列比对问 题从根本上说是一个n p c o m p l e t e 问题【6 ，因此多序列比对问题的求解至今仍 是计算分子生物学中尚未解决的一个难题。这是一个极富有挑战性的工作。 国内外现有的算法，都存在一些问题，例如：同步法只能比对8 条之内的序 列；c l u s t a l 软件有时会陷入局部最优解，比对结果精度不好；s a g a 算法( 迭 代法) 运算速度很慢等等。所以研究新的计算方法，已经成了当务之急，并使得 序列比对成为计算机在生物学中应用的热点。 多序列比对计算量大，由于存储空间和计算时间的限制，用现有的训算机求 出精确解是不切实际的，一般只寻求优化的近似算法。本文将同步法和迭代法有 机地结合起来，把动态规划应用到遗传算法中，来提高运算精度和加快计算速度。 主要的改进如下： 1 采用新的编码方法，在内存允许的条件下，比对序列的数目不再受到限制。 2 完全随机地产生初始种群，增加了染色体的多样性，确保在整个解空间内 搜索求解。 3 提出了新的交叉算子和变异算子，根据比对序列的长度，动态地进行多点 交叉和变异。在新算子中引进了n e e d l e m a n w u n s c h 算法和类似聚类的思想， 使得生成子代的过程变为一个优生过程，即每次产生一个更优的子代，从 第一章绪论 而缩短了进化过程，提高了运算速度。 4 根据遗传算法本身的特性，对新算法进行并行化。传统的同步通信必然造 成主进程的瓶颈问题，另外同步通信还会引起各个从进程之间的同步等待， 所以，本文采用异步通信主从式并行算法来实现新的遗传算法，消除了从 进程之间的等待时间，并且减缓了主进程的瓶颈现象，从而进一步提高了 运算速度。 第二章生物信息学的一些基本概念 第二章生物信息学的一些基本概念 我们处在一个激动人心的时代基因组时代。科学的进步已使人类可以窥 探生命的秘密，甚至包括人类自身。在世纪之交，人类基因组被人类自己破译了。 这部由3 0 亿个字符组成的人类遗传密码本己活生生地摆在了我们面前。与此同 时，来自其它生物的基因组信息源源不断从自动测序仪中涌出，堆积如山，浩如 烟海。这些海量的生物信息是用特殊的“遗传语言”染色体的四个碱基字符 ( a 、t 、g 和c ) 和蛋白质的2 0 个氨基酸字符( a 、r 、n 、d 、c 、q 、e 、g 、h 、i 、l 、 k 、m 、f 、p 、s 、t 、w 、y 和v ) 写成。生物信息学是一门年青的学科，它使 我们能在急速上涨的数据海洋中邀游。生物信息学科虽然年青，但它充满挑战和 机遇且引人入胜。 2 1 核酸和蛋白质 虽然自然界中的生物种类有成万上亿，但决定它们形态、特性和生命运动的 基本生物分子都是核酸和蛋白质。核酸是遗传信息的携带者，不仅在细胞之间， 同时也在生物个体之间世代相传，而蛋白质是遗传信息转化成生物结构和功能的 表达者。 核酸是由四种单体聚合成的一维高分子链，其中每个单体又称为核苷酸。核 酸是携带遗传信息的有机大分子，遗传信息就编码在这些单体的不同排列次序 上。核酸根据单体类型的不同，可以分为脱氧核糖核酸( d e o x y r i b o n u c l e i xa c i d ， d n a ) 和核糖核酸( r i b o n u c l e i xa c i d ，r n a ) 。脱氧核糖核酸是由腺嘌呤、胞嘧 啶、鸟嘌呤、胸腺嘧啶4 种脱氧核苷酸组成的多聚核苷酸链；核糖核酸是由腺嘌 呤、胞嘧啶、鸟嘌呤、尿嘧啶4 种核苷酸组成的多聚核苷酸链。其中，d n a 上核酸 的特定序列决定了生物体结构和功能( 包括蛋白质的种类、结构和功能) ，并以 其半保留复制机制，保证世世代代准确地传递下去。 蛋白质是一种由2 0 种氨基酸通过肽键连接而成的生物大分子。蛋白质结构和 功能都是由核酸根据三联体密码决定的，并在细胞内合成，它参与生物的一切生 命活动。 因此，将一切物种核酸或蛋白质序列看作由4 个或2 0 个元素组成的字母表中 选出的字母序列( 表2 1 ，表2 2 ) ，如： a t g g c c a a c t ) ， g s s k y p r e t t ) 分别表示 一条核酸序列或蛋白质序列。生物信息就是成千上万条以字符序列形式存储核酸 或蛋白质序列，并以某些特定格式存放在各类生物数据库中。 篁三曩生塑堡星堂塑二些堇查塑垒 _ _ - _ 一一一 表2 一l 核苷酸代码 表2 2 氨基酸代码 2 2 分子生物学的中心法则 1 9 5 8 年，f r a n c i sc r i c k 首先提出了分子生物学的中心法则 7 】，它很好地说明 了核苷酸和蛋白质这两大类生物大分子之间的信息传递关系。简单地说，d n a 作为遗传信息的携带者，它在一定条件下可以准确地自我复制。遗传信息只能通 过最终产物的蛋白质体现或“表达”出来。为此要先把信息“转录”到单股的 r n a 链上( 把此类传递遗传信息的r n a 称为信使r n a ，简称m i l n a ) 。细胞液中 有大量核糖体，它们把r n r n a 上的信息翻译成蛋白质。新生的蛋白质要折叠形成 特定的三维形状，才能有生物活性，在生命过程中发挥功能。因此，从d n a 到 r n a 然后再到蛋白质的信息表达过程是一个单向信息流，这个单向信息流同 d n a 之间的信息传递一起构成了分子生物学的中心法则。但是后来人们发现有 一些病毒里面存在反向信息流一一r n a 也可以转录成d n a 。这类病毒的遗传信 息存储在r n a 中，遗传信息的传递需要首先从r n a 反转录为d n a ，然后才能进 行d n a 复制。中心法则如图2 1 所示。 其中，将4 种核苷酸的编码信息转化为2 0 种氨基酸编码的蛋白质序列的分子 机理就是翻译。在翻译过程中，每3 个核苷酸编码( 称为一个密码子) 被翻译成 蛋白质中一个特定的氨基酸。 第二章生物信息学的一些基本概念 、 复制l d n a 2 3 序列比对分类 转录 4 - - m r n a 一 逆转录 翻译 _ + 蛋白质 图2 1 分子生物学的中心法则 根据比对序列数目的多少可以分为双序列比对和多序列比对。双序列比对实 质是寻找最佳匹配路径；多序列比对的实质是寻找多个序列之间的关联性。双序 列比对是序列分析常用方法之一，是多序列比对和数据库搜索的基础。多序列比 对在识别一组相关序列中重要生物学意义的序列模型方面具有相当重要的作用。 对双序列比对算法的研究比较成熟，基本上可以分成两类，一类是基于序列 的全局相似性的全局比对( g l o b a la l i g n m e n t ) 算法，考察两个序列之间的整体相 似性，最佳比对中包括了全部的最短匹配序列：而另一类是基于序列的局部相似 性，着眼于寻找某些特殊片段，比较这些片段之间的相似性，称为局部比对( 1 0 c a l a l i g n m e n t ) 算法。在下一章将介绍这两种算法的具体机制。 但对多序列比对算法的研究还在进行中，比较流行的方法有动态规划法、聚 类法、基于退火算法的方法和基于遗传算法的方法等 8 1 2 。 2 4 序列比对的基本原理 为了更好地介绍序列比对的基本原理，首先扼要地讨论序列比对算法中所涉 及的一些主要概念，然后以双序列比对为例来说明序列比对的基本原理。 2 4 1 空位罚分 基因在进化过程中往往会产生残基+ 的插入或缺失等。有时是1 个或者2 个 残基的插入或缺失，有时则是大片段( 如一个结构域) 的插入或缺失。这样，在 进行序列比对时，为了更好地反映序列的相似性，也就必须考虑在序列比对时插 入空位，并进行罚分( p e n a l t y ) 。也就是说，序列比对过程中引入空位时设霹的 负分，罚分大小可由用户在运行程序时设定，以控制空位插入的合理性以及达到 总体上更好的比对效果 1 3 1 。 把构成核酸或蚩白质的饺苷酸或氪基酸统称为残基。 第二：章生物信息学的一些基本概念 空位罚分时涉及到两个参数，一个是空位开放罚分( g a po p e n i n gp e n a l t y ) ， 一个是空位延伸罚分( g a pe x t e n s i o np e n a l t y ) 。顾名思义，前者为新空位产生时 进行的罚分，而后者则为空位延伸时进行的罚分。也就是说，每当第一次插入空 位时，要进行一定的空位开放罚分，而连续插入空位时，通常按比例给以稍小的 空位延伸罚分。因此，计算一组连续空位罚分( w k ) 公式如下： w k = a + b k 公式( 2 - 1 ) 其中，a 和b 分别表示空位开放罚分和空位延伸罚分，k 是连续空位的总个数。 具体使用时，常数a 和b 的值与所比较的是核酸序列还是蛋白质序列有关，而且 还要与下面讲到的替换矩阵的选择相适应。 2 4 2 替换矩阵( s u b s t i t u t i o nm a t r i x ) 由于序列比对不仅需要考虑子序列之间的匹配，而且需要对整个序列进行比 较。因此，实际操作中，获得序列之间理想的序列比对并不是一件容易的事。所 以，通常用替换矩阵( 又叫计分矩阵) 赋予序列比对结果以分值，用最高的分数 来解释具有显著性生物学意义的比对结果。替换矩阵可以分为单一矩阵和相似性 替换矩阵。 单一替换矩阵就是只考虑两个序列之间完全相同的匹配残基数目，可以把它 理解为1 和0 的矩阵，即：相同残基的分数值为l ，不同残基的分数值为0 。表 2 3a 中显示的是d n a 序列的单一替换矩阵。显然，这种单一替换矩阵具有很大 的局限性。 表2 - 3 d n a 的单一替换矩阵和相似性替换矩阵 acgt a1000 c0l00 g0o10 t000 l ( a ) 单一替换矩阵 ( b ) 相似性替换矩阵 相似性替换矩阵是基于远距离进化过程中观察到的残基替换率，用不同的计 分值表征不同残基之问相似性程度。相似性替换矩阵改进了单一替换矩阵的表征 第二：章生物信息学的一些基本概念 性能，能揭示那些潜在的具有生物学意义的最佳匹配。恰当选择相似性替换矩阵， 可以提高序列比对的敏感度，特别是两个序列之间相同残基较少的情况下。表 2 3b 中显示的是d n a 序列的相似性替换矩阵。常用的蛋白质替换矩阵有突变数 据矩阵( p o i n ta c c e p t e dm u t a t i o n ，简称p a m ，d a y h o f f 等，1 9 7 8 ) 、b l o s u m 矩 阵( b l o c k ss u b s t i t u t i o nm a t r i x ，h e n i k o f f 和h e n i k o i f , 1 9 9 2 ) f 1 4 - 1 5 。p a m 2 5 0 矩阵和b l o s u m 6 2 矩阵参见附录1 2 。 经过多年的试验，大多数比对程序均对特定的替换矩阵设定了空位罚分的缺 省值，如果用户希望使用不同的替换矩阵，则原来的空位罚值设定不一定合适。 如何设定罚分并无明确的理论可遁，但大的空位开放罚分配以很小的空位延伸罚 值被普遍证实是最佳的设定思路 1 6 1 。 2 4 3 双序列比对基本原理 下面以一个双序列比对为例简单说明序列比对的原理。图2 2 所示是对两个 蛋白质序列片段进行比对的一般方法，其基本思想是将两个序列上下排列，若上 下对应的残基相同，用+ 表示。可以通过插入空位使它们具有最好的匹配，b u 两 个序列所对应的相同残基最多。下一步则可以计算相同残基个数，并用计分给出 定量指标 1 7 1 8 1 。 图2 2 显示了两个蛋白质序列片段 a g d v l i y c g v f f q ) 和 a g d l i yf f q1 用单一的置换矩阵计分，这两个序列在未经比对之前总分为3 。通过比对运算， 在适当的位置插入若干个空位之后，使得比对后序列的总分变为9 ，从而得到最 佳比对。 插入空位前序列1 a g d v l i y c g v f f q 序列2 a g d l i y f f q 插入空位后序列1 a g d v l i y c g v f f q 序列2 a g d j i yf f q 女女女 图2 - 2 利用插入空位的方法获得最佳序列比对 显然，从这个例子中可以看出，匹配对准的相同残基数越多，两个序列之间 相似性比对得分就越高。当然，这只是一个用来说明比对原理的简单例予，与实 际应用还有一些差别： 第二章生物信息学的一些基本概念 1 例子中的序列很短，只有十几个残基，而大多数蛋白质序列为2 0 0 5 0 0 个残基，甚至更长。 2 这两个序列的长度几乎相等，而实际情况下，待检序列和目标序列长度 往往差别很大。 3 这两个序列的大部分残基相同，只有一种比对结果，实际序列比对会有 多种比对结果。 4 在此例子中仅仅用单一置换矩阵，但为了使比对结果更有生物学意义， 需根据具体序列选用某种相似性替换矩阵，同时还要涉及到空位罚分的选择。 第三章多序列比对算法的研究现状 第三章多序列比对算法的研究现状 多序列比对就是将一组序列同时进行比对，主要用于描述一组序列之间相似 性关系，以便对基因家族的特征有一个基本了解，揭示这个基因家族的保守性。 它是生物信息学的重要分析工具之一，在分子序列分析中起到至关重要的作用。 国内外对多序列比对的研究一直在不断前进中，根据算法的机制大致可以分为三 大类：同步法、步进法和迭代法。 3 1 同步法 同步法( 又称动态规划法) 就是把双序列比对的动态规划算法简单地推广到 多序列比对的问题上，例如：m s a 、o m a 、a 。算法 1 9 2 1 等。下面以双序列比 对为例来具体说明序列比对的动态规划方法。 3 1 1 动态规划算法 动态规划( d y n a m i cp r o g r a m m i n g ) 的求解方法是先把问题分成多个子问题 ( 每个子问题是互相关联和影响的) ，再依次研究逐个子问题的决策。决策就是 某个阶段的状态确定后，从该状态演变到下一阶段状态的选择。当全体子问题都 解决时，整体问题也随之解决。 kpdn k n 缸 图3 1 利用动态规划算法进行双序列比对 n 3 - l 中的加黑线显示的是 k p d n ) 和 k d m ) 比对结果的最佳路径。利用 动态规划算法解决两条差异程度小的双序列比对时，有时会出现比对结果不唯一 的问题，这是需要采用回溯技术，并根据空位罚分等参数比较达到高分比对的不 同路径。动态规划的核心是要将各个最佳子路径连接起来，最终构成具有最优结 果的路径，而得到比对结果。动态规划算法能有系统地寻找同源的序列，缺点是 速度太慢。 笙三童墨壁型! ! 堕蔓鎏塑竺塞塾鲨一 计算双序列间的最佳比对的经典方法有n e e d l e m a n w u n s c h 算法和 s m i t h w a t e m a r l 算法，它们都属于动态规划算法的范畴。 3 1 2n e e d ie m a n w u n s c h 算法 全局比对算法从整体上分析两个序列的关系，即考虑序列总长的整体比较， 用类似于使整体相似( g l o b a ls i m i l a r i t y ) 最大化的方式，对序列进行比对。两个不 等长度序列的比对分析必需考虑在一个序列中去掉一些残基或者在另一序列作 插入空位处理。生物序列分析中已经有了比较成熟的算法，最著名的就是 n e e d l e m a n w u n s c h 算法 2 2 1 ，简称n w 算法。这一算法是为氨基酸序列发展的， 但也可以用于核苷酸序列。算法最初寻求的是使两条序列间的距离最小。尽管这 类距离的元素是以一种特定的方式定义的，但该算法的良好特性在于它确定了最 短距离。 n w 算法基于一个二维矩阵f ( n ，m ) ，并通过某种算法找出最佳匹配路径。 矩阵的最基本形式是：将两条长度分别为1 2 ，m 的序列x ，y 中匹配残基所对应 单元的分值设置为1 ，不匹配的分值设置为0 。如果考虑更多的生物特性则可以 采用替换矩阵，然后对矩阵中每个单元进行连续求和。下面详细介绍各个具体步 骤，并用两条短序列 g a a t t c a g t t a 和 g g a t c g a l 的比对为例子解释算法每 一步骤。在此例子中我们用单一替换矩阵，即若x = y j ，则s ( x i ，y j ) = 2 ；否则， s ( x ，y i ) = o ：并且设d = 0 。 1 首先建立一个二维矩阵f ( n ，m ) ，并对其初始化( 图3 3 ) 。 为了使算法能够具体实现，我们需要处理一些边界情况，对于最上的一行和 最左一例进行特殊处理，即：f ( i ，o ) = 一id ，f ( o j ) = 一jd ，其中d 为空位罚分。 2 从左上到右下逐步根据公式3 1 填充矩阵f ( i ，i ) 。 若令当前单元为f ( i ，j ) ，那么能够到达它的单元为f ( i 一1 ，i 一1 ) 、f ( i i j ) 、 f ( i ，j 1 ) 。如图3 2 所示。而且这三个单元都是已知的，因此就可以根据公式3 一l 计算当前单元f ( i ，j ) 的值。其中s ( x i ，y j ) 表示序列x 第i 个残基和序列y 第j 个残 基的对应替换矩阵的权重。重复应用这个等式，递归地生成矩阵f ( i ，i ) 各项值。 最后得到的f ( n ，m ) 就是我们所想要的序列x 和y 的最佳全局比对的打分值。该 算法有效的原因是分值是各个独立片段的和得到的，所以在比对中到达某个位点 的最佳分值是前一步那个位点上的最佳分值加上新的一步的增量分数。当我们得 到f ( i ，j ) 值的时候，还需要记录此f ( i ，j ) 值是从哪个方向得到的，用来标明回溯 的方向( 在图3 - 4 中用箭头表示) 。 兰三至至壁型些堕蔓鲨塑塑星婴鲨 f c i ，= m a x ff ( i - 一l , j - 1 ) + s ( x i ，y j ) 图3 2n e e d l e m a n - w u n s c h 算法中计算最优得分方法 t j o a t c g a jaat tca0tta 0 、q 000000o000 0 ：i o o o 0 0 o 图3 - 3n e e d l e w u n s c h 算法的初始矩阵 公式( 3 - 1 ) 3 用回溯的方法从右下角开始回推得到最佳路径 为了找到比对本身，我们必须找到导致得到这个最终值的最佳路径，这个过 程称之为回溯。它是通过从右下角出发，按照我们建立矩阵时存储的指针反方向 到达左上角，建立比对来实现的( 图3 5 和图3 - 6 ) 。在回溯过程的每一步中，当 前的位点( i ，j ) 移回方向只有三种可能，即( i l j - 1 ) 、( i j - 1 ) 和( i 1 j ) 位点中 的一个。其生物含义为：1 ) 从单元( i 一1 ：j ) 向( i ，j ) 的垂直移动，相当于在x 序列中 插入一个空位使相似序列延伸。换而言之，y 序列由x 序列中x ，的缺失所产生。 2 ) 从单元( i 1 j 1 ) 向( i ，j ) 的对角线移动，相当于增加残基x ，和y j 使相似序列延伸。 换而言之，y 序列由x 序列中的x i 被y j 取代所产生。3 ) 从单元伽1 ) 向( i ，j ) 的水平 第三章多序列比对算法的研究现状 移动，相当于在序列y 中插入一个空位使相似序列延伸。换言之，y 序列由x j 插 入x 序列所产生。最终比对结果如图3 7 所示。 0aat t ca0tt 0 、 0 0 、o 、o 、0 、0 、 0 、 0 0 、0 、 0 q、互吨0、- (、- l、- l、罨吨 二z、- l 0：置 、】= 1 - 2。誓 - 2 ：l、c 、- 2 q 。0 ：t、c 乙rq 、g气、嘎 、0、1 q 二1：乏 ：3：j j r乙i二1：l l：芝0 q 二1 。吨：1：l：t：3 c1 艺lv o：1 0：2 = 7 q 二1 。i ： ：毛。：3 =l二l 0。0、4 f0 01 1、r3 、r2、3 图3 - 4n e e d l e w u n s c h 算法的最终矩阵 oaatt ca0tta gattcg tta 图3 5n w 算法回溯过程 图3 - 6n w 算法回溯过程结果 gaattcgtta i il li ggatcg 且 图3 - 7n e e d l e w u n s c h 算法序列比对结果 3 1 3 s m i t h w a t e r m a n 算法 n w 算法适用于整体水平上相似性程度较高的两个序列。如果两个序列的亲 缘关系较远，它们在整体上可能不具有相似性，但在一些较小的区域上却可能存 在局部相似性。1 9 8 1 年，s m i t h 和w a t e r m a n 提出了一种用来寻找并比较这些具 第三章多序列比对算法的研究现状 有局部相似性区域的方法，即常用的s m i t h w a t e r m a n 算法【2 3 ( 简称s w 算法) 。 与n w 算法类似，它也是一种基于矩阵的方法，而且同样利用递推和回溯的方 法来确定允许空位插入的比对。s w 算法在寻找序列中一些小的、具有局部相似 性的片段时，确实具有很高的灵敏度。 s w 算法一个重要特性是矩阵中每个单元均可以是比对结果序列片段的终 点，该片段的相似性程度由该单元中的分值表示，即从起点开始，向后追踪矩阵， 直到到达某一负值。对于具有最大相似性片段以外部分的差异性不会影响到该片 段。s w 比对算法与上一节中介绍的n w 比对算法有很紧密的联系，具体步骤如 下： 1 s w 比对算法初始化矩阵时，最上一行和最左一列都赋予0 ，即f ( i ，o ) = e o j ) = 0 。 2 在递归产生f ( i ，j ) 时，对公式3 1 略微做了调整，变成公式3 2 。从公式 3 2 可以看出，s w 算法在矩阵的每一个位点上，增加了一个新的可能性，即当 所有其他选项的值为负时，允许f ( i ，j ) 取值0 。选择0 是为了开始一个新的比对 片段。 f ( j ) 嚼“y j ) 公式( 3 - 2 ) 3 s w 算法的矩阵中每个单元均可以是比对结果序列片段的终点，该片段的 相似性程度由该单元中的分数值表示。这样，我们就需要在整个矩阵范围内寻找 f ( n ，m ) 最大值的位点，这是两个序列间高分比对的终点，从那里开始回溯，根据 回溯路径得到一个片段的比对。回溯过程终止于分值为o 的位点，这里就是这个 比对的起点。如果需要，还可以找出在上述回溯范围以外其他具有较高分值的矩 阵单元，再进行回溯，即找出多个具有较高分值的相似性片段。 3 1 4 多序列的动态规划法 多序列的动态规划法是把给定的所有序列同时进行比对，而不是两两比对或 分组进行比对。其基本思想是将一个二维的动态规划矩阵扩展到三维或多维。以 三个短序列 v s n s ) 、 s n a ) 、 a s ) 为例，通过动态规划算法找出了比对的 最佳路径。结果如图3 8 所示。 第三章多序列比对算法的研究现状 v |， ，7 l 矗， 。p i， 。l l| l ，1 1 ，p ? 图3 8 同步法多序列比对 矩阵的维数反映了参与比对的序列数。这类方法所得到的解精确度很高，但 其空间复杂度和时间复杂度正比于序列长度的乘积，即o ( m 1m2 ) ( 其中 m 卜- m 。分别指n 条序列的长度) 。 3 2 渐进法 渐进法则是在序列两两比对的基础上逐步优化多序列比对的结果。现今较为 成熟的渐进法软件有c l u s t a lw $ 1 1 m u l t a l 2 4 2 7 1 。 目前使用最广泛的多序列比对程序是c l u s t a l 软件包，下面简单介绍其比 对机理。c l u s t a l 先将多个序列两两比对构建距离矩阵，该矩阵反映两序列之 间的关系；然后根据距离矩阵计算产生系统进化指导树，对关系密切的序列进行 加权；然后从最紧密的两条序列开始，逐步引入临近的序列并不断重新构建比对， 直到所有序列都被加入为止。比对过程中，相似性程度较高的序列先进行比对， 而距离较远的序列添加在后面。该算法采用聚类分析方法来达到去除无用信息的 目的，主要包括四个阶段 2 3 ： 1 对所有n 个序列分别对进行两两比对，以便计算一个给出每对序列发散 性的距离矩阵。 2 由距离矩阵创建向导树。 3 根据向导树中的分支次序对所有序列进行渐进式比对： 1 ) 使用标准的双序列比对算法对叶子序列进行比对。 2 ) 在分支结点上进行序列谱多序列比对( p r o f i l e sm s a ) 。 3 ) 使用