（计算机软件与理论专业论文）dna序列比对最大似然度进化模型.pdf

摘要 摘要 序列比对是生物信息学中重要的研究课题，是发现序列的功能，结构和进化 信息的重要手段。现有的很多比对算法都是基于目标函数，目标函数利用替换矩 阵和空位罚分对比对过程和结果进行记分，用记分值来判断序列比对结果的好坏。 基于目标函数的比对算法的缺点是记分系统的些许变动就可能导致局部或全局比 对剧烈变化。由此，本文提出了d n a 序列最大似然度比对算法来对d n a 序列进 行序列比对。 本文首先介绍序列比对的基本概念，详细叙述了替换矩阵、空位罚分和目标 函数以及它们对序列比对的影响，然后深入研究了双序列各种常用的比对算法： 点阵分析、动态规划算法和词或缸串方法，并给出了它们的算法思想或伪代码。 接着，根据基于目标函数算法的缺点，提出最大似然度比对算法，该算法分为两 个部分：参数估值算法和比对算法。最大似然度比对算法首先使用进化参数估值 算法对一对d n a 序列相关的进化参数进行估值，然后比对算法利用估算出来的参 数值对d n a 序列进行比对。它是一个独立的方法，完全避开了基于替换矩阵和空 位罚分的序列比对算法由于d n a 序列相似度的不同而要选择与之相适应的替换矩 阵的问题。最后，通过对进化模型最大似然度d n a 比对算法的序列比对结果和 f a s t a 比对程序结果进行比较，验证了进化模型最大似然度d 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 sa ni m p o r t a n tf u n d a m e n t a ls u b j e c t i nb i o i n f o r m a t i c sr e s e a r c h ， ，h i c hi sa ni m p o r t a n tm e a s u r ct od i s c o v e rt h ef u n c t i o n ，s t r u c t u r ea n de v o l u t i o n a r y i n f - 0 m a t i o ni 1 1b i o l o g i c a ls e q u e n c e s t h e r ea r em a n ya l g o r i t h m si nt h i sa r e a , w h i c h a r e b a s e do no b j e c t i v ef u n c t i o n s t h eo b j c c t i v c p e n a l t y t os c o r et h ep r o c e s s e sa n dr e s u l t so f t ot h es c o r e so fa l i g n m e n t t h es h o r t a g e f u n c t i o n su s es u b s t i t u t i o nm a t r i xa n dg a p a l i g n m e n t , a n dj u d g et h er e s u l t sa c c o r d i n g o fa l i g n m e n ta l g o r i t h m sw h i c hr e l yo n o b j e c t i v ef u n c t i o n si st h a ts m a l lc h a n g e si nt h es c o r i n gs y s t e mc a na b r u p t l yc h a n g e 趾 a l i g n m e n tf r o mal o c a lt oa # o b a la l i g n m e n t f o rt h i sr e a s o n ，t h i sp a p e rp r o l o s e s a m a x i m u ml 墩e l i h o o dm e t h o dw h i c hi sb a s e du p o na s t a t i s t i c a lm o d e lo fd n as e q u e n c e e v o l u t i o nf o ra l i g n m e n to ft w od n as e q u e n c e s a tf i r s t b a s i cc o n c c p t i o n so fs e q u e n c e sa l i g n m e n ta r ei n t r o d u c e di nt h i sp a p e r , w h i l es u b s t i t u t i o nm 砌c e s ，g a pp e n a l t i e sa n do b j e c t i v ef u n c t i o n sa r ea l ld e s c r i b e dm d e t a i lw i 也m e i ri n f l u e n c e so nt h es e q u e n c e sa l i g n m e n t ，a n dt h e n t h ea l l g n m e n t a 1 9 0 r i 也m so fp a i r s o fs e q u e n c e sa r ea n a l y z e di n d e p t h ，w h i c hu s u a l l yi n c l u d et h e f o i l o w i n gm e m o d s ：d o tm 捌xa n a l y s i s ，t h ed y n a m i cp r o g r a m m i n g ( d p ) a l g o r i t h ma n d w o r d0 r 缸t u p l em c t h o d s ，# v i n gt h ea l g o r i t h mi d e a so rt h ep s e u d o e o d e s o ft h e m t h e n , a c c o r d i n gt ot h es h o r t a g eo fa l g o r i t h mr e l y i n go no b j e c t i v ef u n c t i o n s ，am 踟m u m l i k e l t h o o dm e t h o di sp r e s e n t e d ，w h i c hi sc o m p o s e do fp a r a m e t e re s t i m a t i o na l g 鲫协m a n da l i g n m e n ta l g o r i t h m t h em a x i m u m p a r a m e t e re s t i m a t i o na l g o r i t h mt oe s t i m a t e l i k d i h o o dm e t h o du s e st h ee v o l u t i o n a r y t h ee v o l u t i o n a r yp a r a m e t e r sr e l e v a n tt oa p a i ro fu n a l i g n e dd n as e q u e n c e sa tf i r s t , a n dt h e n a l i g n m e n tp r o c e d u r eu s e st h e p a r 锄锨st oa l i g n m e n tt h ed n as e q u e n c e s t h i si s a ni n d e p e n d e n tm e t h o d ，w h l c h c o m p l e t e l ya v o i d st h ep r o b l e m so fc h o o s i n ga p p r o p r i a t es c o r i n gm a t r i c e sb a s e du p o n s 嘶n gm 砌c e s ，s e q u e n c ea l i g n m e n t sf o rt h e i rd i f f e r e n ts i m i l a r i t i e so f d n as e q u e n c e s f i n a l l y ，t h ev a l i d i t ya n da c c u r a c yo ft h em a x i m u ml i k e l i h o o d m e t h o di st e s t i f i e d t h r o u 西c o m p a r i n gt h er e s u l t so ft h em a x i m u m l i k e l i h o o dm e t h o dw i t ht h er e s u l t so f f a s t a k e y w o r d ：b i o i n f o r m a t i c s s e q u e n c e sa l i g n m e n t e v o l u t i o n a r ym o d e l m a x i m u mi n 【e i i l i o o de v o l u t i o n a r yp a r a m e t e r p a r a m e t e re s t i m a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：丛亟釜 日期 夕卯扩，才 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：型亟垒 导师签名： 日期) 矽汐2 船 日期2 0 0 8 2 8 第一章绪论 第一章绪论 1 1 引言 生物信息学的最主要的研究领域之一就是生物序列分析，其主要工作就是从 原始生物序列数据中发掘和提取信息，探索和揭示生命的奥秘。序列分析包括很 多方面，但大致可归纳为序列同源性搜索( h o m o l o g ys e a r c h ) 、多序列比对和系统 发育树的建立( m u l 卸l ea l i g n m e n ta n dp h y l o g e n e t i ct r e ec o n s t r u c t i o n ) 、蛋白质结构的 预狈l j ( p r o t e i n s t r u c t u r ep r e d i c t i o n ) 、基因组序列分析和基因发现( g e n o m i cs e q u e n c e a n a l y s i sa n dg e n e f i n d i n g ) 以及快速搜索序列数据库技术( d a t a b a s es e a r c h i n g ) 等主 要方面。序列比对是序列分析的基本工具和主要手段。在生物信息学中，对序列 数据进行相似性比较，即序列比对，是一种基本的信息处理方法，它对于发现生 物序列中的功能，结构和进化信息具有非常重要的意义，而序列比对就是运用某 种特定的数学模型和算法，找出两个或多个序列之间最大匹配的碱基或残基数， 比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生 物学特征。 生物信息学发展到今天，已经有了很多的比较成熟的算法，其中很多比对算 法都是基于目标函数( o b j e c t i v ef u n c t i o n ，o f ) 的。目标函数利用替换矩阵 ( s u b s t i t u t i o nm a t r i x ) 和空位罚分( g a pp e n a l t y ) ，对比对过程和比对结果进行记分，根 据分值来判断比对的好坏。 虽然科学家们对替换矩阵和空位罚分进行了很多的研究，提出了一些通用性 和适用性都很好的替换矩阵，但是替换矩阵是建立在某个特定的模型之上，总会 受到模型的限制和影响。例如，氨基酸替换矩阵p a m 是基于d a y h o f f 进化模型， 在该模型中，一个蛋白质中的每个氨基酸位点在任何时刻能够变成另外2 0 个氨基 酸的概率由p a m 表给出，且蛋白质在每个位点的变化是独立于其它的位点，这 个假设是建立d a y h o f f 记分矩阵的基础，但事实上并非如此【l 捌。首先，d a y h o f f 进化模型假设每个氨基酸位置是同等可变的，然而，事实上突变能力在各个位点 是可变的，并且蛋白质中不同的氨基酸的突变能力也是不一样的。而且，替换矩 阵都是根据一组相似性确定的序列，根据特定的模型总结出来的，因而它只能正 确的反映相似性与之相近的序列的生物学特征。对于相似度不同的序列比对，必 须选择与该相似度相对应的替换矩阵，才能正确的反映待比对序列之间的关系。 例如：p a m l 2 0 、p a m 8 0 和p a m 6 0 矩阵可用于相似性分别为4 0 、5 0 和6 0 的序列比对，对于其它相似性的序列比对，存在较大的误差。对于待比对序列， 2 一 d n a 序列比对最大似然度进化模型 在比对之前，要知道它们的相似性不是一件简单的事情。因为相似性的确定，必 须依赖序列比对的结果。所以对于序列比对，选择合适的替换矩阵和设置合理的 空位罚分值是一个非常困难的问题。 为了克服这个难题，本文提出了最大似然度比对算法。最大似然度比对算法 基于进化模型，符合普遍接受的进化论观点。进化模型的最大特定就是假设待比 对的序列是从同一个共同祖先进化而来，序列间的差异是由于经过了不同的进化 事件( e v o l u t i o n a r ye v e n t s ) 的结果。最大似然度算法的基础是对序列中置换 ( s u b s t i t u t i o n ) 、插) , ( i n s e r t i o n ) 和删除( d e l e t i o n ) 提供一个框架，同时对特定进化时间 内出现的每一个碱基的变化给出一个概率。最大似然度比对算法将检测从一个序 列突变到另外一个序列的所有可能的组合，选定其中似然度最高的( 即概率值最大 的) ，就可以获得一条序列到另外一条序列之间的距离。最大似然度比对算法与利 用打分矩阵的比对算法最大的不同是，最大似然度比对算法中对空位的引入均来 自于插入删除模型，而非特定的空位罚分系统。它利用进化参数( e v o l u t i o n a r y p a r a m e t e r s ) 作为权值，而不是传统比对算法中的替换矩阵和空位罚分。最大似然 度算法分为两部分：参数估值算法和序列比对算法。首先对待比对的序列利用参 数估值算法进行参数估计，这些参数是比对算法的基础。接着，比对算法利用估 计出来的进化参数进行序列比对，从而避免了针对相似性不同的序列要选择相适 用的替换矩阵和设置适当空位罚分值的难题。 1 2 序列比对的现状 根据比对序列的数目，可以将序列比对分为双序列比对( p a i r w i s es e q u e n c e a l i g n m e n t ) 和多序列比对( m u l t i p l es e q u e n c ea l i g n m e n t ) 。 双序列比对是通过特定的算法对两个d n a 序列或者蛋白质序列进行比对， 找出两者之间最大相似性匹配。双序列比对是序列分析常用的方法之一，也是多 序列比对和数据库搜索的基础，也是本文要研究的问题。 已有的常用双序列比对算法有：1 9 7 0 年g i b b s 和m c i n t y r e 提出的点阵分析( d o t m a t r i xa n a l y s i s ) t 3 1 。点阵分析是种图像显示方法，之后m a i z e l 和l e n k 利用带颜 色的点阵来增强相似区域的检测能力【4 】。点阵分析可用于寻找蛋白质和d n a 序列 中的正向或反向重复，并预测r n a 中的自补区域，因而具有构建二级结构的能 力。虽然现在已经拥有很多更复杂更精确的算法来求取序列的相似性，但是点阵 方法仍然是一个很流行很有效的描叙方法。它是双序列比对中最基本的方法，属 于局部比对算法。动态规划算法( d y n a m i cp r o g r a m m i n g ，d p ) ，它是一种最优算法， 典型的有1 9 7 0 年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 算法【5 】，适应 于全局水平上和相似性程度较高的序列比对，本质上和点阵图类似。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 算法【6 】，它是一种用来寻找并比较具有局部 相似性的动态规划算法，在识别局部相似性时，具有很高的灵敏度，一直是局部 比对算法的基础。由于动态规划算法时间复杂度太高，不适应与数据库搜索，因 此出现了各种启发式算法( h e u r i s t i ca l g o r i t h m s ) ，它们的优点是速度快，能满足数 据库查询的需要，其中应用最广的有f a s t a 算法【_ 7 】和b l a s t 算法【8 】。f a s t a 算 法是由p e a r s o n 和l i p p m a n 于1 9 8 5 年提出来的，f a s t a 的基本思想是：一个能 揭示出真实序列关系的比对至少包含一个两条待比对序列都拥有的词( 称为肛 串) ，把查询序列中所有肛串编成h a s h 表，然后在序列库搜索时查询这个h a s h 表，以检索出可能的匹配，这样那些命中的珏串就能很快被鉴定出来。b l a s t 算法，由a l t s e h u l 等人在1 9 9 0 年提出，采用一种片断匹配算法和一种有效的统计 模型来找出目的序列和数据库序列之间的最佳局部比对结果。其基本思想是：通 过产生数量更少的但质量更好的增强点来加快速度。之后，d e l c h e r 于1 9 9 9 年提 出了全基因组比对的m u i v l i n e r 算法【9 】，它是一种基于后缀树结构的方法，在速度 上比b l a s t 算法要快，缺点是仅能处理具有较高相似性的全基因序列比对。 已有的多序列比对算法大致分为三类：精确比对算法、渐进比对算法和迭代 比对算法。 ， 精确比对算法最为经典的是多维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 算法可以用于任意多条序列比对的计算，但是由于算法时间、 空间复杂度的限制，可行的计算维度为3 。c a r r i l l o l i p m a n 算法【l o j 通过减小计算 空间，将计算维度提高到1 0 。s t o y e 提出了一种新的分治算法d c a i l ，将序列在 不影响其特征表现的前提下，切割成完全满足c a r r i l l o l i p m a n 算法长度要求的子 序列集，利用c a r r i l l o l i p m a n 算法进行序列比对。精确比对算法的缺点是时间和 空间复杂度大，不能很好的对多维序列进行快速比对。 渐进比对算法由h o g e w e g 和h e s p e r 首先提出【1 2 】，f e n g t l 3 】和t a y l o r 1 4 】又加以 完善。m u l t a l i n 方法【1 5 】( h t t p ：p r o d e s t o u l o u s e i n r a f r m u l t a l i n m u l t a l i n h t m l ) 的原理 是：从一系列两两比对开始，计算出相似性记分值，再根据这些记分值进行分层 聚类。当序列都分类后，开始进行多序列比对，计算出多序列中的序列两两比对 的新记分值，基于这些新记分值，再重新分类。这个过程不断循环，直到分值不 再上升，此时多序列比对也就结束。最具代表性的、广泛使用的多序列比对软件 包c l u s t a l w 【1 6 】( f t p ：f t p e b i a c u k p u b s o f t w a r e ) 正是基于渐进比对来构建，其基本 思想是相似性序列通常具有进化相关性这一假设。其具体计算过程是：在比对过 程中，首先对所有输入的序列进行两两比对，并计算它们的相似性记分，再根据 相似性记分值将这些序列分成若干组，并在每组之间进行比对，计算出相似性记 分值。根据相似性记分值继续分组比对，直到得到最终比对结果。在比对过程中， 相似性程度较高的序列优先进行比对，而距离较远的序列添加在后面。 4 一 d n a 序列比对最大似然度进化模型 渐进比对算法的主要问题是最终的多重比对结果必须依赖于起始时两两比 对，如果起始的两两比对中出现的错误会扩展到多序列比对中，尤其是起始比对 的序列存在较远的亲缘关系，即相似性较小时，这一问题更加明显。迭代比对方 法通过不断的重排来纠正这种错误，同时对这些亚类群进行比对以获得所有序列 的全局比对。基于模拟退火( s i m u l a t e da n n e a l i n g ) ，遗传算法( g e n e t i ca l g o r i t h m ) 、隐 马尔科夫模型( h i d d e nm a r k o vm o d e l ，h m m ) 、g i b b s 取样等都是基于迭代比对方 法。 般来说，评价生物序列比对算法的标准有两个：1 ) 算法的运算速度；2 ) 序 列比对结果的敏感性( s e n s i t i v e ) 或准确性( a c c u r a c y ) ，简称精度。虽然科学家已经提 出了做多的序列比对算法，但是由于序列比对问题的复杂性，目前还没有一个最 佳的比对算法能同时满足这两个方面。 1 3 本文所做的工作 现行的大量序列比对算法大多是利用记分矩阵( s c o r i n gm a t r i x ) 来获得序列的 比对结果，因而记分矩阵对比对结果产生重要的影响。记分矩阵是科学家根据特 定的模型，对大量序列比对数据进行分析后得出的统计结果，是基于远距离进化 过程中观测到的残基替换率，使用不同的记分值表征不同残基的相似性程度。根 据待比对序列的相似性选择与之相适应的记分矩阵，能大幅度的提高序列比对的 精确度。反之，不恰当的选择记分矩阵将会影响序列比对结果。例如：p a m 2 5 0 适用于残基相似性为2 0 的序列，如果将其用于残基相似性为6 0 的序列比对， 比对的结果会相当的不准确。对于待比对的序列，准确的知道它们之间的残基的 相似性程度是比较困难的，故而要正确地选择适用的记分矩阵还有相当的难度。 本文通过分析进化模型的特点，提出参数估值算法和最大似然度比对算法。 首先，运用参数估值算法，对输入的d n a 序列进行参数估值，然后根据进化参 数利用最大似然度比对算法对序列进行序列比对。最大似然度比对算法采用动态 规划的思想，利用进化参数和发散时间作为权重，对d n a 序列进行比对，完全 避开了比对算法对记分矩阵的依赖，难于选择合适的记分矩阵的问题。 论文内容具体安排如下： 第一章：主要介绍序列比对问题的背景知识，序列比对研究意义和现状。 第二章：主要介绍序列比对中涉及的一些基本概念和问题，包括：序列比对 的定义，序列比对中使用的替换矩阵、空位罚分、目标函数以及它们对序列比对 的影响。然后详细介绍了双序列比对中经常用到的算法：点阵分析、动态规划、 词或缸串方法( k - m p l c ) 。 第三章：针对常用的比对算法严重依赖于记分函数( 目标函数) 这一特点，提 第一章绪论 出了最大似然度比对算法。首先，介绍了进化模型，根据进化事件对空位的影响， 将进化过程分为替换过程和插入删除过程。然后提出了最大似然度比对算法，它 分为参数估值算法和比对算法。参数估值算法首先对待比对的序列进行参数估计， 这些参数是比对算法的基础。接着最大似然度比对算法利用估计出来的进化参数 进行序列比对。为了说明似然度算法的正确性和精确性，将它的结果和f a s t a 序 列比对程序的结果进行了比较。 第四章：对整篇文章进行了总结，并指出了该方法的不足。 5 一 第二章双序列比对基础 第二章双序列比对基础 比较是科学研究中最常见的方法，通过将研究对象互相比较来寻找对象可能 具备的特征。在生物信息学中，比对是最常用和经典的研究手段，最常见的比对 是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列之间的相似性 区域和保守位点，寻找两者可能的分子进化关系，探索导致它们产生共同功能的 序列模式，从而可以有效地预测和分析一些新发现序列的新功能。本章主要阐述 双序列比对的概念以及相关的概念，介绍一些双序列比对算法。 2 1 序列比对的基本概念 2 1 1 序列比对的定义 核酸和蛋白质序列可以看成是从字母表中选出的字母组成的字符串，一个字 母表的复杂度定义为它所包含的不同字母的数目。用表示残基类型的集合。对 于d n a 序列s = a ，t ，c ，g ) ，对于蛋白质序列s 包含了2 0 个字符，每一字符代表一 种氨基酸。在进化过程中，少数的残基会发生缺失( 删除) 或插入的现象。因此， 在比较两个或几个相关序列会出现中断( b r e a k ) 现象，为了消除这种现象对序列比 对的影响，导入了空位( g a p ) 。空位用“一 表示，用s 表示s u 一) 。 假设有条序列s j = s j ，s ，2 s j f ，s n = s m s ：j = 2 跏，s 刀表示第n 条序列，s 以，表示 第n 条序列中第，个位点的残基，厶表示序列s 一的长度。一个序列比对a 是一个 二维字符矩阵，即a = s n i ) ( n 1 。加，i 1 上f ) ，其中s i n e s ，并且序列比对a 满 足下面四个条件：( 1 ) 矩阵的行数等于序列的数目：( 2 ) 如果移去每一行中的空位 “一”字符，将得到原来的序列；( 3 ) 将不同的序列中相同或相似的残基放入同 - - n ，即尽可能将序列间相同或相似的残基上下对齐。( 4 ) 一行中不能所有的字 符均为“一”。当_ 2 时，a 为双序列比对；当n = 3 时，a 为多序列比对，如图 2 1 所示： a t cg a g t g c t a t cg a c t g c t ( a ) d n a 双序列比对 a t c g a g t g c t a t c g a c t g c t t c g g c t g c t a t c g a g c g c 一 ( b ) d n a 多序列比对 图2 1d n a 序列比对 7 一 d n a 序列比对最大似然度进化模型 2 1 2 替换矩阵 由于比对代表了序列经过替换、插入、删除以后的优化结果，所以必须对每 一对d n a 或氨基酸序列的替换、插入和删除操作预置数值，由这些预置的数值 构成的矩阵就叫替换矩阵。替换矩阵对相同、相似和不同的残基匹配设置不同的 记分值，因而替换矩阵又叫记分矩阵。序列比对算法中经常用到的四种基本的替 换矩阵如下： ( 1 ) 单位矩阵( u n i t sm a t r i x ) 1 7 】这是一种简单的替换矩阵，适用于核苷酸序 列。它只考虑了残基的同一性，所以又叫同一性矩阵。所谓同一性，是指 序列之间完全相同的残基匹配。当比对的序列在同一个位点上残基的类型 相同时，设定其记分值为1 ，否则取0 。对于d n a 序列，其单位矩阵如 图2 2 所示： at cg a10 0 0 t o 100 c 0o 10 g00o1 图2 2 d n a 的单位矩阵 ( 2 ) 遗传密码矩阵( g e n e t i cc o d em a t r i x ，g c m ) g c m 记分矩阵采用氨基酸侧 链的结构相似性信息【l 引，根据一种氨基酸改变为另一种氨基酸所需要的 密码子碱基的改变个数来确定，如果变化一个碱基使某些氨基酸的密码子 改变为另一些氨基酸的密码子，则其匹配记分为1 ；如果需要改变2 个碱 基，则记分为2 ，依次类推。g c m 所依据的假设是：遗传密码是影响氨 基酸置换的唯一因素【l9 】。它可用于进化距离的计算，其优点就是计算结 果可以直接用于绘制进化树( e v o l u t i o n a r y t r e e s ) ，但是它在蛋白质序列比对 尤其是相似程度低的序列比对中很少被使用。 ( 3 ) d a y h o 行突变数据矩阵( m u t a t i o nd a t am a t r i x ，m d m ) 瞄u jm d m 记分方法是 基于蛋白质序列中单点可接受突变( 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 等选择7 1 组密切相关的蛋白质( 至少8 5 相似) 进行比对，绘制出这些蛋白质家族的进化树，并据此推导出它们的 祖先序列。根据推导出的祖先序列，计算在进化过程中，一种氨基酸被另 一种氨基酸取代的实际数目，即p a m s 。根据这些改变，确定了2 0 种氨 基酸中每种氨基酸的相对突变率。根据p a m s 和相对突变率就可以计算出 第二章双序列比对基础 m d m 中的元素值。p a m 矩阵是基于进化的突变模型，并假定氨基酸变 化是一个马尔可夫过程，即每个位点的氨基酸的变化独立于该位点以前的 变化。由于在d a y h o f f 蛋白质进化模型中用到的蛋白质序列是从一个共同 的祖先分化而来，所以p a m 适用于高相似性的蛋白质序列比对。 与d a y h o f f p a m 记分矩阵所用的模型相类似，1 9 9 1 年，s t a t e s 等利用 马尔科夫模型建立了一系列的核酸p a m 矩阵【2 1 1 ，如图2 3 所示。尽管这 些矩阵最初的目的是用来提高对序列数据库中相似性搜索的敏感度，但是 它们也可以用于核苷酸序列的记分。 atcg a2666 t6266 c6626 g6662 9 一 图2 3 进化距离为1 p a m 的核苷酸置换矩阵 ( 4 ) 模块替换矩阵( b l o c k ss u b s t i t u t i o nm a t r i x ，b l o s u m ) e 2 2 】b l o s u m 是以序 列片断为基础，基于蛋白质模块数据库b l o c k s ，找出的一组替换矩阵， 用于解决序列的远距离相关。在构建矩阵的过程中，通过设置最小相同残 基数百分比将序列片断整合在一起，以避免由于同一残基对被重复计数而 引入的任何潜在的偏差。通过设置不同的百分比，可以得到不同的矩阵。 例如，相似性高于或等于8 0 的序列比对可以产生b l o s 切8 0 矩阵。那 些相似性有6 2 或以上的序列产生b l o s u m 6 2 矩阵，依次类推。与p a m 不同，p a m 矩阵对相关序列中所有的氨基酸位置进行记分，而b l o s u m 矩阵则是基于区域中置换和保守的位置，这些位置代表了相关序列中最相 似的共同区域，因而，p a m 模型可用于寻找蛋白质的进化起源，而 b l o s u m 模型则用于发现蛋白质的保守区域。 除了上面介绍的替换矩阵外，还有一些基于其他模型的替换矩阵。比如，在 序列比对程序f a s t a 和b l a s t 中，常用到的d n a 序列比对记分矩阵如图2 ，4 所示： atcg a5- 444 t- 45- 4- 4 c_ 4- 45- 4 g- 44- 45 图2 4f a s t a 和b l a s t 中常用替换矩阵 1 0 d n a 序列比对最大似然度进化模型 2 1 3 空位罚分 为了使得两个序列获得最佳匹配，常常需要在序列中插入空位。空位的引入 是为了补偿那些残基的插入或者缺失，使序列的比对取得更好的结果。但是引入 的空位并不代表真正的进化事件，如果对引入的空位数量不加限制，即使比对结 果所得的记分值较高，也缺乏生物学依据，因而必须引进一种机制来对空位的引入 进行控制，常用的方法就是空位罚分，即每插入一个空位，就在比对结果的总记 分值中减去一定的分值( 也叫罚分值) 。因此，最终的序列比对结果记分值是两个 序列之间匹配残基的记分值与空位罚分的总和。 常用的空位罚分规则有如下两种： 1 )常量空位罚分 常量空位罚分是对比对序列中的每个空位都赋予一个常量的罚分值峨，整个 序列比对的空位罚分就是插入的全部空位数k 的罚分之和，即殴k 。有如下两 条序列s 1 ：a a t g g a c 和序列s 2 ：a a g g t t a c ，其比对结果如下： aatgg ac aaggttac 序列s 1 中插入的空位数为2 ，序列s 2 中插入的空位数为1 ，因而上面序列比 对的空位罚分为哌x ( 2 + 1 ) 。 这种罚分策略的优点是简单，但是其缺点也是显而易见的。因为在实际的生 物进化过程中，不同位点的残基的突变概率是不一样的，对每个插入的空位使用 同样的罚分值不能正确地反映这一过程。 2 ) 仿射空位罚分( a f f m eg a pp e n a l t y ) 对于序列比对结果中引入的空位，既要考虑到罚分值与插入空位的长度的关 系，又要避免单纯的依赖插入空位的长度。仿射空位罚分的引入就可以解决这一 问题。仿射空位罚分是将空位罚分分为两部分：起始空位罚分( g a po p e n i n gp e n a l t y , g o p ) 和延伸空位罚分( g a pe x t e n s i o np e n a l t y , g e p ) 。所谓起始空位，是指在序列比 对时，在一个序列中插入一个空位，使两个序列之间有更好的匹配结果。延伸空 位是指在引入一个或者多个空位后，继续引入下一个连续的空位，使两个或多个 序列之间取得更好的匹配。在序列中，引入的第一个非连续的空位均是起始空位， 起始空位后的空位或者扩展空位后引入的空位均是延伸空位。延伸空位罚分值可 以随意设定，它可以与起始空位罚分值相同，也可以比起始空位罚分值小，甚至 可以比起始空位罚分值大。在仿射空位罚分规则中，若用a 表示起始空位罚分值， b 表示延伸空位罚分值，对于空位长度为k 的序列，根据p a s c a r e u a 和a r g o s 的假 定【2 3 】，如果插入和删除呈几何分布，并且几个连续的插入或删除由一个单独的进 第二章双序列比对基础 化事件产生，那么可以得到如下的仿射罚分值： 彤p 口+ 6 晦1 ) 2 1 4 目标函数 式( 2 1 ) 有了替换矩阵和空位罚分的概念之后，可以利用它们定义一个函数来衡量比 对结果的优劣，该函数称为目标函数，又叫记分函数或打分函数。在比对算法中， 目标函数不仅是用来考察序列比对结果好坏的标准，而且其值还反映了这个比对 的生物学信息，并且预示序列的结构或者序列之间存在的进化关系。因而，目标 函数的选择直接影响着序列比对的结果。 双序列比对和多序列比对有着完全不同的目标函数。对于双序列比对的目标 函数，可以简单的根据替换矩阵和空位罚分来获得，并且能很好的反映生物学意 义。具体的方法是把所得的双序列比对的每一列根据所选的替换矩阵记分求和， 然后根据空位罚分减去由于插入空位而带来的代价。而对于多序列比对，还没有 公认的目标函数来评价多序列比对的结果，不过有一些常用的目标函数：s p ( s u m o fp a i r ) 目标函数( 2 4 】和c o f f e e ( c o n s i s t e n c yb a s e do b j e c t i v ef u n c t i o nf o ra l i g n m e n t e v a l u a t i o n ) 目标函数2 5 1 ，由于本文只涉及双序列比对，因而具体方法不再论述。 对于下面的双序列比对： atagagt ttgtacg tagcggt t cgt t cg 假设相匹配的残基记分值为1 ，残基与残基不匹配的记分值为1 ，残基与空 位匹配的记分值为2 ，则上面序列比对的目标函数记分值为：1 0 4 3 = 3 。实际上 在双序列比对中，难点在于替换矩阵的选取和空位罚分的设置，来取得合理的目 标函数值。 2 2 双序列比对算法 双序列比对实际上是根据特定的数学模型找出两个序列之间的最大匹配残基 数。双序列比对算法是指通过一定的算法对两个d n a 或蛋白质序列进行比较， 找出两者之间最大相似性匹配。双序列比对是序列分析常用的方法之一，也是多 序列比对的基础。 双序列比对算法很多，常用的算法有：1 ) 点阵分析；2 ) 动态规划；3 ) 词或 缸串方法。 1 2 d n a 序列比对最大似然度进化模型 2 2 1 点阵分析 点阵分析是比较两个序列，以寻找序列间可能的性状对位比对的一种方法。 其主要优点在于可以找到两个序列间的所有可能的残基匹配。 在序列比对的点阵方法中，一个序列a 排列在页面的顶部，而另一个序列b 则排列到页面的左边，如图2 5 所示，该图采用的是d n a s t r i d e r ( v e r s i o n1 3 ) 的点 阵模块t 2 6 j ( h t t p ：l l w w w e g r k i s e l e g r g r o u p s l s o m a h a m m e r d o t t e r h t m l ，) 。 ( 1 )用a m ，b n 分别表示序列a ，b 中第m 和1 1 个残基。从b 的第一个残基b 1 开始，沿着序列a 移动，与序列a 中每一个残基进行比较，如果b l 和 a i ( 1 - - - i - - - m ) 类型相同，那么在其对应位置标一个点。 ( 2 )接着对b 中第二个残基b 2 与序列a 中每一个残基进行比较，类型相同则 用点在相应位置做出标记。 ( 3 )重复此过程，直至序列b 中每一个残基和序列a 中所有的残基完成比较。 标记的点表明了序列a 中与序列b 中的残基所有可能的匹配，相似序列的任 何区域都能通过一个点的对角线表示出来。对角线之外的孤立点表示随即匹配， 即那些可能与任何重要比对都不相关的匹配。 在点阵图方法中，可以利用滑动窗口过滤掉随机匹配，提高匹配区域的检测。 利用滑动窗口比较序列时，不是比较序列的单个残基，而是同时对两个序列相邻 位置的一个窗口进行比较。只有当残基的匹配数目达到窗口定义的最小匹配数目 ( 串) 时，才在相应的位置上用点标记。例如：若将窗口大小定义为1 5 ，窗口中所 需匹配的残基数目为1 0 ，那么a 中连续的1 5 个残基和b 中连续1 5 个残基比较， 只有这些残基匹配的数目大于或者等于1 0 时，才在相应位置用点标记。一般来说， d n a 序列比蛋白质序列所用的窗口规模要大，这是因为d n a 只有a 、t 、c 、g 四种类型的碱基，而氨基酸残基有2 0 种类型，d n a 的随机匹配的数目要比蛋白 质的大。d n a 序列一般采用长的窗口和串，一个典型的窗口大小是1 5 ，对应于 的串的长度为1 0 。蛋白质序列般采用短窗口和短串，典型的窗口和串值均1 。 点阵方法可以快捷地找到序列间存在的插入或者删除，因为插入和删除的存 在，使得水平或者垂直方向上发生了位移。对角线点阵图中两条完全相同的序列 被表示成一条连续的对角线，两个不完全相同却具有一定相似性的序列表示为一 些间断的对角线，其中不相连的区域表示那些不匹配的区域。相似性程度较低的 序列所构成的点阵图，具有较大的噪声( 即随机匹配) 。一定长度的相似性序列片 断则在点阵图上，以成组的较短的对角线形式出现，它们平行于主对角线，其与 主对角线的距离反映了插入空位的多少，如图2 6 所示。 第二章双序列比对基础 l 轴0 雏s 酶咖 1 3 图2 5 大肠杆菌编码噬菌体九故垂直轴) 和噬菌体蛋白p 2 2c 2 ( 水平轴) d n a 序列间的点阵分 析。该分析图采用的是m a c i n t o s hd n a 序列分析程序d n a s t r i d e r ( 1 3 版) 的点阵显示完成。 窗口大小为1 1 ，串为7 ，这意味着只有在序列中，窗口位置当且仅当1 1 个位置中有7 个残基 匹配时才打印一个点。 a s 七q l b 暑q l c s t q l 图2 6 具有不同相似程度序列的点阵图。 ( a ) 相同序列( b ) 高度相似性序列( c ) 具有一定相似性的序列。 尽管点阵分析方法可以用来