（计算机软件与理论专业论文）基于astar和dialign算法的多序列比对.pdf

摘要 序列比对是现代生物信息学中一个最基本的研究课题。通过多序列比对，可 以预测新序列的结构和功能，分析序列之间的同源关系，以及进行系统发育分析。 本文首先介绍了序列比对涉及的基本问题：空位罚分，替换矩阵和比对结果评价 标准。接着，主要介绍了两种序列比对算法：a 算法和斜线比对算法求多序列比 对。 理论上n e e d l e m a n - w u n s c h 算法可以很容易地应用于多条序列中产生分值最优 的比对，但是随着序列条数的增长，算法的复杂性成指数增长，而且算法不能扩 展到多于三条序列。而a 算法利用合理的启发式函数限制多序列比对的搜索空间。 用这种方法，即使是八条序列，每条序列含有几百氨基酸残基也可以同时比对。 首先，该算法将多序列比对问题转化为求最短路径问题，利用a 算法可以在找到 最短路径的同时有效地降低时间复杂度。本文将a + 算法应用于多序列比对，选择 有效的预测函数和边界值，最大限度的缩小搜索空间。并且从程序性能和算法性 能上努力做出改进：找更接近的边赛值；利用哈希链表代替简单链表提高程序的 节点查找时问。最后，讨论了算法在测试例子中的应用，并且与经常使用的比对 方法产生的结果比较。实验结果表明：设置边界值( b o u n d ) 和利用哈稀链表代 替简单链表后，程序的执行速度比未改进之前提高了好几倍。理论上讲，只要选 择合适的目标函数和打分矩阵，计算出的结果应该是非常理想的；然而，实际情 况与理想值之间还有较大的差距，还有待于预测函数以及目标函数进一步的改进。 但是该算法的潜能是非常大的，一旦打分矩阵和目标函数的设定方面获得突破， 其前景将不可限量。 在本文中，接着介绍了另一个不同的序列比对的方法，即斜线比对算法。不 同于比较单个的残基，它使用免空格段段比对算法比较随机长度的序列片段。特 别地，该算法不使用任何空格罚分。通过定义关于斜线位置的集合，它把比对看 成一个一致的等价关系。在寻找斜线段阶段，尝试使用新的方法。即先将两条序 列比对，然后只在两两最优比对部分查找。在对算法的总体性能影响不太大的情 况下，有效地提高了程序的执行速度。实验表明：该算法是一种有效的局部多序 列比对算法，非常适合产生生物信息学上的有某种特定意义的比对。 关键词：生物信息学多序列比对a t 算法预测函数斜线比对 a b s t r a c t s e q u e n c ea l i g n m e n t i st h em o s t9 0 1 3 1 i n o r tf u n d a m e n t a ls u b j e c ti nm o d e m b i o i n f o r m a t i c s t h r o u g hs e q u e n c ea l i g n m e n t , w ec a np r e d i c tt h es t r u c t u r ea n df u n c t i o n o fn e ws e q u e n c e s ，a n a l y s i st h ee v o l u t i o n a r yl i n k a g eo fs e q u e n c e s ，a n dd op h y l o g e n e t i c a n a l y s i s f i r s t l y , w ed e s c r i b et h eb a s i cp r o b l e ma b o u ts e q u e n c ea l i g n m e n t ，s u c ha sg a p p e n a l t y , s u b s t i t u t i o nm a t r i xa n dt h es t a n d a r do fa s s e s s i n ga l i g n m e n tr e s u l t s e c o n d l y , t w om e t h o d s ，a + a l g o r i t h ma n dd i a g o n a la l i g n m e n ta l g o r i t h m , a r ei n t r o d u c e di nt h i s p a p e r i nt h e o r y , t h en e e d l e m a n - w a n s c ha l g o r i t h mc a nb ee x t e n d e dq u i t ee a s i l yt o p r o d u c es c o r eo p t i m a la l i g n m e n t so fm o r et h a nt w os e q u e n c e s t h ec o m p l e x i t yo f t h e a l g o r i t h mg r o w se x p o n e n t i a l l yw i t h t h en u m b e ro fs e q u e n c e s ，t h ea l g o r i t h mi s p r o h i b i t e dt oe x t e n dt om o r et h a nt h r e es e q u e n c e s a + a l g o r i t h mr e s t r i c t st h es e a r c h s p a c eo f t h em u l t i p l ea l i g n m e n tp r o b l e mb yu s i n gr e a s o n a b l eh e u r i s t i c s i nt h i sw a y , 嬲 m a n ya se i g h tp r o t e i ns e q u e n c e s ，e a c hc o n t a i n i n gs e v e r a lh u n d r e da m i n oa c i dr e s i d u e s ， h a v eb e e na l i g n e ds i m u l t a n e o u s l y f i r s t , m s ap r o b l e mi st r a n s f o r m e dt ot h es h o r t e s t p a t hp r o b l e m ，t h e nw eu s e sa + a l g o r i t h m , w h i c hc a r lf i n de f f i c i e n t l yt h es h o r t e s tp a t h a n dd e c r e a s et h et i m ec o m p l e x i t y t h i sp a p e ra p p l i e st h ea 。a l g o r i t h mt om u l t i p l e s e q u e n c ea l i g n m e n tp r o b l e mw i t hm o r ep o w e r f u le s t i m a t o ra n du p p e rb o u n d ，m o s t l y d e c r e a s et h es e a r c hs p a c e t r ym yb e s tt oi m p r o v et h ep e r f o r m a n c eo fp r o g r a ma n d a l g o r i t h m ：f i n d i n gc l o s e rb o u n dv a l u ea n du s i n gh a s hl i s ti n s t e a do fs i m p l el i n kl i s t a t t h el a s t w ec o m p a r eo u ra l g o r i t h mw i t l ls e v e r a lo t h e rm e t h o d si nt e s t i n ge x a m p l e s t h e r e s u l ts h o w st h a tp r o g r a ma f t e rs e t t i n gb o u n dv a l u ea n du s i n gh a s hl i s ti ss e v e r a lt i m e s m o r ee f f i c i e n tt h a nb e f o r e s p e a k i n gi nt h e o r y ，t h er e s u l ts h o u l db ev e r yp e r f e c ti fw e s e l e c ta p p r o p r i a t eo b j e c t i v ef u n c t i o na n ds u b s t i t u t i o nm a t r i x h o w e v e r , t h er e a lr e s u l t i sd i f f e r e n tf r o mt h ei d e a ls i t u a t i o n , h e u r i s t i cf u n c t i o na n do b j e c t i v ef u n c t i o ne x p e c tt o b ei m p r o v e d b u tt h ep o t e n t i a lo ft h ea l g o r i t h mi sg r e a t o n c eo b j e c t i v ef u n c t i o na n d s u b s t i t u t i o nm a t r i xa c q u i r eb r e a k t h r o u g h ，t h ef u t u r ei sb r i # u i nt h i sp a p e r ，w ei n t r o d u c ea n o t h e ra l g o r i t h mf o rs e q u e n c ea l i g n m e n tn a m e d d i a g o n a la l i g n m e n tw h i c hd i f f e r sf r o mo t h e ra l g o r i t h m s i n s t e a do fc o m p a r i n g i n d i v i d u a lr e s i d u e s ，w eu s eg a p - f r e es e g m e n t - t o s e g m e n ta l i g n m e n t sw i t hv a r i a b l e s e g m e n tl e n g t h i np a r t i c u l a r , o u ra l g o r i t h md o e sn o te m p l o ya n yg a pp e n a l t i e s w e p r o p o s et oc o n s i d e ra l i g n m e n t sa sc o n s i s t e n te q u i v a l e n c er e l a t i o n sd e f i n e do nt h es e to f a l lp o s i t i o n so c c u r r i n gi na l ls e q u e n c e su n d e rc o n s i d e r a t i o n i nt h es t a g eo ff i n d i n g d i a g o n a l s ，w et r yt ou s en e wm e t h o d n a m e l yt h ef a c tt h a tw es h o u l da l i g nt w o s e q u e n c e sf i r s t l y ，t h e nf i n dt h ed i a g o n a l si nt h ea l i g n m e n t i nt h ec a s eo fi n s u r i n g p e r f o r r n a n c eo fa l g o r i t h m , t h er a t eo fp r o g r a mr u n n i n gi si m p r o v e d t e s t i n gr e s u l t i n d i c a t e st h a tt h i s i sat y p eo fe f f i c i e n tl o c a lm u l t i p l ea l i g n m e n ta l g o r i t h ma n dw e l l s u i t e dt op r o d u c e b i o l c l g i c a l l yp l a u s i b l ea l i g n m e n t s k e y w o r d ：b i o i n f o r m a t i c sm u l t i p l es e q u e n c ea l i g n m e n t a - s t a ra l g o r i t h m h e u r i s t i cf u n c t i o n d i a g o n a la l i g n m e n t “。 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：当鲎 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：f 导师签名： 率蛆一 日期驾! f ：垒 醐上牛丛 第一章绪论 第一章绪论 1 1 序列比对的研究背景 1 1 1 序列比对的生物学背景 序列比对是生物信息学中最基本、最重要的操作，通过序列比对可以发现生 物序列中的功能、结构和进化的信息。序列比对的根本任务是：通过比较生物分 子序列，发现它们的相似性，找出序列之间共同的区域，同时辨别序列之间的差 异。在分子生物学中，d n a 或蛋白质的相似性是多方面的，可能是核酸或氨基酸 序列的相似，可能是结构的相似，也可能是功能的相似。一个普遍的规律是序列 决定结构，结构决定功能。研究序列相似性的目的之一是，通过相似的序列锝到 相似的结构或相似的功能；另一个目的是通过序列的相似性，判别序列之间的同 源性，推测序列之间的进化关系。 在进行序列比较时经常使用“同源”( h o m o l o g y ) 和“相似”( s i m i l a r i t y ) 这两个概 念。两条序列同源是指它们具有共同的祖先。在这个意义上，无所谓同源的程度， 两条序列要么同源，要么不同源。而相似则是有程度的差别，如两条序列的相似 程度达到3 0 或6 0 。一般来说，相似性很高的两条序列往往具有同源关系。但 也有例外，即两条序列的相似性很高，但它们可能并不是同源序列，这两条序列 的相似性可能是由随机因素所产生的，这在进化上称为“趋同”( c o n v e r g e n c e ) ，这样 一对序列可称为同功序列。同源又分为直向同源和共生同源，直向同源( o r t h o l o g o u s ) 序列是来自于不同的种属同源序列，而共生同源( p a r a l o g o u s ) 序列则是来自于同一 种属的序列，它是由进化过程中的序列复制而产生的。 序列比较的基本操作是比对( a l i g n ) 。序列的比对是一种关于序列相似性的定性 描述，它反映在什么部位两条序列相似，在什么部位两条序列存在差别。它是一 种基本的信息处理方法，对于发现生物序列中的功能、结构和进化的信息具有非 常重要的意义【2 】。序列比对就是运用某种特定的数学模型或算法，找出两个或多个 序列之间的最大匹配碱基或残基数，比对结果体现了算法在多大程度上反映了序 列之间的相似性关系以及它们的生物学特征【耵。这个过程往往需要通过数据库搜 索，找出具有相似性的同源序列，对于d n a 序列，可推测该未知序列可能属于哪 个基因家族，具有哪些生物学功能。而对蛋白质序列来说，有可能找到已知三维 结构的同源蛋白质，而推测其可能的空间结构与功能。 生物信息学中，对各种大分子序列进行分析是一件非常基本的工作。序列分 2 基于a - s t a r 和d i a l i g n 算法的多序列比对 析的主要任务就是从大量的序列信息中获取基因结构、功能和进化等信息。例如， 在发现一个基因或蛋白质序列后，为了推测这个序列的性质、结构、功能、同源 性、变异性等等，首先必须应用序列数据库进行相似形检索，得到与未知序列相 似的目的序列，从而为后续实验确定初步的研究方向。很多有价值的发现，都有 赖于利用计算机所进行的序列同源性比较与分析。在生物学的研究中，将未知序 列与已知序列进行比较分析已经成为一种强有力的研究手段。这种寻找相似性的 过程就是序列比对。双序列比对是序列分析的基础。而对于构成基因家族的成组 序列来说，只有建立多个序列之间的关系，才能揭示整个基因家族的特征。多序 列比对在阐明一组相关序列的重要生物学模式方面起着相当重要的作用。序列比 对的研究在生物学中的意义主要表现为以下几个方面：1 、是序列分析的基础；2 、 为实验提供新思路，并指导进一步实验设计；3 、是寻找和鉴定新基因的重要手段； 4 、是蛋白质结构预测和分子设计的基础；5 、是研究生物进化和种属分类的基本 方法。 1 1 2 序列比对在生物信息学中的兴起 计算机性能和速度的提高大大促进了生物科学技术的迅速发展，无论是从数 量上还是从质量上都极大地丰富了生物科学的数据资源。数据资源的急剧膨胀迫 使人们寻求一种强有力的工具去组织这些数据，以利于储存、加工和进一步利用。 而海量的生物学数据中必然蕴含着重要的生物学规律，这些规律将是解释生命之 谜的关键，人们同样需要一种强有力的工具来协助人脑完成对这些数据的分析工 作。另方面，以数据分析、处理为本质的计算机科学技术和网络技术迅猛发展 并日益渗透到生物科学的各个领域。于是，一门崭新的、拥有巨大发展潜力的新 学科一生物信息学悄然出现，这也直接导致了序列比对台句兴起。 生物信息学的主要研究内容是：l 、序列比对( a l i g n m e n t ) 。基本问题是比较两 个或两个以上符号序列的相似性或不相似性，序列比对是生物信息学的基础。2 、 结构比对。基本问题是比较两个或两个以上蛋白质分子空间结构的相似性或不相 似性。3 、蛋白质结构预测，包括2 级和3 级结构预测。4 、计算机辅助基因识别( 仅 指蛋白质编码基因) 。基本问题是给定基因组序列后，正确识别基因的范围和在基 因组序列中的精确位置。5 、非编码区分析和d n a 语言研究。6 分子迸化和比较基 因组学。7 序列重叠群( c o n t i g s ) 装配。8 遗传密码的起源。9 基于结构的药物设 计。l o 其他与生物信息学密切相关的计算机科学技术。 本文的主要内容是研究序列比对，通过序列比对可以发现生物序列中的功能、 结构和进化的信息。 第一章绪论 1 2 序列比对的研究现状 根据同时进行比对的序列的条数，序列比对算法分为双序列比对( p a i r w i s e s e q u e n c ea 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 ) 算法。 双序列比对又分为全局比对和局部比对算法，典型的全局比对算法是 n e e d l e m a n w u n s c h 算法；局部比对算法的基础是s m i t h w a t e r m a n 算法。双序列比 对的算法中，广泛使用的算法有f a s t a 和b l a s t 。 多序列比对是现代生物信息学中一个最有挑战性的问题，也是本文研究的主 要问题。现有的多序列比对方法大体可以分为4 类：精确比对方法，渐进比对方 法，迭代比对方法和基于图论的比对方法。 精确比对方法完全基于动态规划算法，最为经典的是多维n e e d l m a n w u n s c h 算法【4 1 ，但其可行的计算维数为3 ，c a r r i l l o l i p m a n 算法1 5 】通过减小计算空间，将计 算维数提高到1 0 。s t o y e 通过描述一种新的分治算法d c a 6 】将序列在不影响其特 征表现的前提下，切割成充分满足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 算法进行序列比对。2 0 0 0 年又提出了一种减少了存储空间的 对d c a 算法的递归调用算法o m a 算法【7 】。a 算法利用启发式搜索的思想，减小 搜索空间加快搜索效率，将在第三章详细介绍。 ： 渐进比对方法首先由h o g e w e g 和h e s p e r t 8 】提出，f e n g 9 署i t a y l o r 1 0 1 又加以完善。 真基本思想是迭代地利用两条序列动态规划算法，先由两条序列的比对开始，逐 渐添加新序列，直到所有序列都加入为止。但是不同的添加顺序会产生不同的比 对结果，所以确定合适的比对顺序是渐进比对方法的一个关键问题。而两个序列 越相似人们对它们的比对就越有信心，因此，整个序列的比对应该从最相似的两 个序列开始，由近至远逐步完成。基于这种方法的软件很多，主要c l u s t a l w 和 t - c o f f e e 等。 迭代比对方法是使用比对计分函数反复添加一条附加的序列到已比对的序列 中，首先在所有的两条序列比对中找出距离最小的一组，组成最优比对，然后反 复地找出与最优比对距离值最小的序列。与最优比对的表头文件进行匹配，并且 根据所得的结果相应的修改最优比对和表头文件。这类算法根据改善比对的策略 可以分为确定型和随机型迭代比对方法。最简单的迭代比对类型是确定型 ( b r o c c h i e f i & k a r l i n , 1 9 9 8 ；r e i n e r te ta 1 ，2 0 0 0 ；w a n g & l i ，2 0 0 4 ) 。随机迭代方法包括 p r r p ( g o t o h ，1 9 9 6 ) ，隐马尔可夫( h m m ) 模型( k r o g h , 1 9 9 4 ；b a l d i ，1 9 9 4 ) ，遗传算法 ( n o t r e d a m a & h i g g i n s ，1 9 9 6 ) 以及其他方法( b e r g e r , 1 9 9 1 ；l a w r e n c e ，1 9 9 3 ) 。这类方法的 主要优点在于将优化过程和目标函数在概念上进行了分离。但是这类算法不能提 供获得优化比对结果的保证，但却具有对比对序列个数不敏感等特性。有很多方 4 基于a - s t a r 和d i a l i g n 算法豹多序列比对 法都是渐进方法和迭代方法的混合。m u l t a l i n ( c o r p e t , 1 9 8 8 ) 方法就是一个基于渐进 与迭代混合的多序列比对方法； 1 3 本文主要工作及安排 本文主要对生物信息学的多序列比对算法进行了研究。根据a - s t a r 算法的理 论基础，实现了将a - s t a r 算法应用到多序列比对问题中；并介绍了利用斜线算法 进行多序列比对，并尝试在算法中的寻找斜线段的阶段改进。然后具体实现了这 两种算法，通过实验结果对算法进行评估，并对结果进行了具体的分析。 论文内容具体安排如下： 第一章主要介绍了该课题的背景及其意义，提出了作者的工作安排和各章 节的内容分配，简要说明了作者所做的主要工作。 第二章首先讨论了序列比对所涉及到的一些问题、概念等，如空位罚分、 相似性替换矩阵、目标函数和调和序列。然后介绍了目前序列比对算法的发展， 包括两条序列比对和多序列比对的经典算法以及一些新方法，并对多序列比对的 相关问题做了简要的分析。 第三章主要介绍了a s t a r 算法的原理、特点，并分析了该算法的难点：a 、 找到准确的目标函数：b 、建立有效的预测函数而o 。；c 、设置适当的边界值 ( b o u n d ) 。算法首先将求序列比对的最优问题转化为最短路径问题，将打分距阵 上的值映射为两点之间的距离。根据快速而且结果相对较好的序列比对算法( 如 c l u s t a l ) 的思想，程序实现类似c l u s t a l 的快速算法( 打分函数不同) 计算 边界值，利用哈稀链表代替简单链表提高程序的节点查找时间，实现了将a - s t a r 算法应用于多序列比对算法的应用，并从程序性能和算法性能上努力做出改进， 且进行了大量的实验。并根据结果评价标准s p s 和c s 的思想，实现了该程序，通 过实验对a s t a r 算法计算的结果进行了性能分析。 第四章介绍了斜线比对算法及其特点，并详细举例分析了斜线比对的各个 关键步骤和算法。主要分为以下五步：a 计算概率；b 找出所有的斜线对 ( d i a g o n a l s ) ；c 根据出现的概率计算斜线对的权值；d 权值的优化；e 在保证 一致性的前提下进行比对。在寻找斜线段阶段，尝试使用新的方法，即先将两条 序列比对，然后只在两两最优比对部分查找。保证对算法的总体性能影响不太大 的情况下，有效地提高了程序的执行速度。并通过实验对该算法进行了详细的分 析和性能评估。 第五章对全文进行了总结并提出了不足之处和本文的难点，可改进的地方， 以及今后的改进方向。 第二章生物序列比对 第二章生物序列比对 序列比对是生物信息学的焦点问题之一，也是一个比较陌生的问题，本章从 序列比对的基本概念讲起，然后介绍影响序列比对的基本要素：空位罚分、相似 性替换矩阵和目标函数，最后简单介绍了一些序列比对算法。 2 1 序列比对的基础知识 2 1 1 序列比对的相关概念 d n a 或蛋白质序列可以表示为有限字符集中的字母组成的字符串，对于 d n a ，艺包含a 、t 、g 、c ，分别代表四种不同的核苷酸，将其统称为碱基；对于 蛋白质，包含2 0 个字母，分别代表2 0 种不同的氨基酸，将其统称为残基。序列 分析的基本操作是比对( a l i g n ) 。两条序列的比对是指这两条序列中各个字符的一种 一一对应关系，或字符对比排列。序列的比对是一种关于序列相似性的定性描述， 它反映在什么部位两条序列相似，在什么部位两条序列存在差别。最优比对揭示 两条序列的最大相似程度，指出序列之间的根本差异。以下是序列比对中常用的 一些概念： 如果从两个不同的生物体中提取出来两条相似的d n a 序列，在生物学中可以 理解为它们来自于同一个祖先的d n a 。根据这一原理，并且考虑到在进化过程中 发生变异的可能性，同一家族在同一时代的种类之间会出现差异。这些差异可以 分为以下三种情况： 1 插x , ( i n s e r t i o n ) 在序列中插入一个或多个字符，通常用“”、或、或“”来表 示。 2 删除( d e l e t i o n ) 从序列中删除一个或多个字符。 3 替换( s u b s t i t u t i o n ) 用个字符替换另一个字符。 插入和删除两者是相反的，例如给定两条序列，如果在一条序列中插入一个 或多个字符后，得到另一条序列。那么前者就相当于从后者删除一个或多个字符 而得到。由于插入和删除之间的相互关系，两者通常可简化为i n d e l ( i n s e r t i o n d e l e t i o n 的缩写) 。 距离( d i s t a n c e ) 其定义来自于对上述每一种变异分配一个加权值，给定两条序 列，其中一条序列经过一系列的变异可以变换为另一条序列，那么这两条序列之 间的距离为这些变异的权值之和的最小值。 6 基于a - s t a r 和d i a l i g n 算法的多序列比对 相似度( s i m i l a r l y ) ：给定两条序列，对应位置的相似之处赋予一定的分值( 或 权值) ，那么这两条序列的相似度为这些权值之和的最大值。 编辑距离( e d i td i s t a n c e ) ：两条序列之间的编辑距离是一条序列经过一系列的 编辑操作( 插入、删除、替换诤 交为另一条序列所需要的操作的最小次数。相对应 于每一个操作赋予一个分值( 或权值) ，通常插入和删除( i n d c l ) 的分值是相同的，利 用比对的算法，求出最小分值( 或最大的负分值) ，即为这两条序列之间的编辑距离。 2 1 2 替换矩阵与空位罚分 在进行序列两两比对时，有两方面的问题赢接影响相似性分值：替换矩阵和 空位罚分。粗糙的比对方法仅仅用相同或不同来描述两个残基的关系，显然这种 方法无法描述残基取代对结构和功能的不同影响效果，缬氨酸取代异亮氨酸与谷 氨酸取代异亮氨酸的应该给予不同的打分。因此如果用一个替换矩阵来描述氨基 酸残基两两取代的分值会大大提高比对的敏感性和生物学意义。在进行序列比对 时，算法需要通过插入空位( g a p ) 使其具有最佳匹配，即序列之间所对应的相同残 基最多。但是，空位的引入意味着两条序列之间残基的插入或删除，如果引入空 位不加限制，所得的比对结果即使分值很高，也缺乏生物学意义。因此，必须有 一种机制来对空位的引入加以限制，常用的方法就是空位罚分。 1 相似性替换矩阵 序列比对时的计分方法除了用计分函数表示外，最常见的是用替换矩阵来表 示。用于d n a 序列的替换矩阵相对比较简单，如常用的有单位矩阵。而2 0 种氨 基酸之间的替换，远比核苷酸复杂，因为没有一个矩阵可以适合各种情况。 相似性替换矩阵的构建，是基于远距离进化过程中观察到的残基替换率，并 用不同的分值表征不同残基之间相似性程度。恰当选择相似性替换矩阵，可以提 高序列比对的敏感度，特别是两条序列之间完全相同的残基数比较少的情况下。 虽然针对不同的研究目标和对象应该构建适宜的替换矩阵，但国际上常用的 替换矩阵是突变数据矩阵和残基片段替换矩阵( b l o c k ss 蛐t i o nm a t r i x 矩阵， b l o s u m 矩阵) 等，它们来源于不同的构建方法和不同的参数选择，包括p a m 2 5 0 、 b l o s u m 6 2 、b l o s u m 9 0 、b l o s u m 3 0 等。 突变数据( m u t a t i o nd a 协，m d ) 计分方法是基于蛋白质序列中单点可接受突变 ( p o i n ta c c e p t e dm u t a t i o n ，p a m ) 的概念，通过对蛋白质进化模式的研究而建立的【1 4 1 。 1 个p a m 进化距离对应于残基发生突变的概率依据每1 0 0 个残基中有1 个可接受 单点突变而取。将1 个p a m 进化距离的概率矩阵多次自乘，可以得到进化距离较 远的p a m 矩阵。有p a m 2 0 ，p a m 6 0 ，p a m l 2 0 。p a m 2 5 0 等，p _ 枷2 5 0 相似性分 值相当于序列问仍有2 0 相同残基，数字表示进化距离，数字越小。距离越近， 第二章生物序列比对 7 反之距离越远。 残基片段替换矩阵( b l o s u m 矩阵) 是由h e n i k o f f 夫妇于1 9 9 2 年提出的，为了 克服突变数据矩阵在进化距离较远的情况下的不足，用于解决序列的远距离相关。 在构建矩阵过程中，通过设置最小相同残基数百分比将序列片段整合在一起，以 避免由于同一个残基对被重复计数而引入潜在的偏差。在每一片段中，计算出每 个残基位置的平均贡献，使得整个片段可以有效地被看成是单一序列。通过设置 不同的百分比，产生了不同的矩阵。如高于或等于8 0 相同残基的序列组成序列 模块可用于产生b l 0 s u m 8 0 矩阵等。 大量实验表明，b l o s u m 矩阵总体比p a m 矩阵更适合于生物学关系的分析 和局部相似性搜索。对于不同的对象可以采用不同的替换矩阵以获得更多信息， 例如对同源性较高的序列可以采用b l o s u m 9 0 矩阵，而对同源性较低的序列可采 用b l o s l n 订3 0 矩阵。 2 空位罚分 空位罚分是为了补偿插入和缺失对序列相似性的影响，由于没有什么合适的 理论模型能很好地描述空位问题，因此空位罚分缺乏理论依据而更多的带有主观 特色。常用的空位罚分规则有三种： ( 1 ) 常量空位罚分 常量空位罚分是对插入比对序列中的每个空格都赋予一个常数量的罚分吸，整 个比对的空位罚分就是插入的全部空格数k 的罚分之和，即x k 。如下面的比对： s ：ctt e-f edttacc t：c一-edfct f-d tt一c 则娜丁序列中的空格个数分别为3 和5 ，所以s 与7 序列比对的空位罚分就为伟名 x ( 3 + 5 ) 。 这种罚分策略的优点是简单，不会增加额外的时间复杂度。但是其缺点也是 显而易见的。因为在实际的生物分子进化中，基因中不同位点的突变概率是不同 的，对每个空位使用相同的常量罚分显然是不能准确刻画序列比对的生物意义。 ( 2 ) 恒定空位罚分 这种罚分策略从整体上处理插入的空格，即序列中插入的相连空格被看作一 个整体的空位进行罚分。这样每个空位的罚分吸都是与其长度无关的。如上面的s 和z 序列的比对，在孵列中有2 个整体空位，在r 中有3 个整体空位，这样这一比对 的罚分值就为畋( 2 + 3 ) 。恒定空位罚分虽然可以避免常量空位罚分将罚分单纯依赖 于空位长度的缺点，但是却忽略了空位长度对比对结果的影响，可能造成插入过 多空格导致割裂整个比对片段。因此更合适的罚分策略应当同时考虑引入空位长 度的影响，但又要避免单纯的长度依赖。 ( 3 ) 仿射空位罚分 ， 8 基于a - s t a r 和d i a l i g n 算法的多序列比对 仿射型的空位罚分把整个罚分分成两个罚分值，起始空位罚分和延伸空位罚 分。所谓起始空位，是指序列比对时，在一条序列中插入一个空位，使两条序列 之间有更好的匹配：所谓延伸空位，是指在引入一个或几个空位后，继续引入下 一个连续的空位，使两条序列之间有更好的匹配。任一空位的出现均需给以起始 空位罚分，而任一空位的扩大必须给以延伸空位罚分。对于一个空位长度为七的罚 分w k 可以用如下式( 2 1 ) 表示： w 产- a + b k 式( 2 1 ) 其中口表示起始空位罚分，6 表示延伸空位罚分，七为空位长度。口和b 两个参数 设置的不同将产生不同的比对结果，其影响如表2 1 所示。 表2 i 起始空位罚分和延伸空位罚分对匹配的影响 通过对上面公式的改进得到了一种更为理想的空位罚分，改进的公式如式( 2 2 ) 所示： w 卢口】o g 辑+ 1 )式( 2 2 ) 大多数比对算法针对特定的替换矩阵设定了空位罚分的默认值( d e f a u l t ) ，如果 使用者希望使用不同的替换矩阵，则原来的空位罚分设置不一定适合。如何设置 罚分并无明确的理论可循，但大的起始空位罚分配以很小的延伸空位罚分，这样 的设置被普遍证实是最佳的设置思路。 2 1 3 目标函数 目标函数( o b j e c t i v ef u n c t i o n ，o f ) 是用来衡量多序列比对结果好坏的一种度量 标准。因为所有多序列比对方法都依赖于一个目标函数来说明所得的多序列比对 结果的好坏从而反映此方法的精确度和有效性。理想的情况是希望目标函数所得 的分值有更多的生物学意义。目标函数除了是评价一个结果好坏的标准外，还能 反映这个比对的生物信息并且预示着序列的结构或比对序列之间存在的进化关 系。理论上，如果被比对的每一列碱基有相同的进化或在r n a 和蛋白质的三维折 叠结构中起到相似的作用，这样的多序列比对结果就是正确的。 对于多序列比对，如何选择计分函数即目标函数是困难的，目前。还没有一 个公认的目标函数用来评价多序列比对的结果【1 5 】。比较广泛使用的两个目标函数 是：基于s p ( s u m o f - p a i r ) 计分的目标函数和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 e f u n c t i o nf o ra l i g n m e n te v a l u a t i o n l 目标函数。 1 s p 目标函数 第二章生物序列比对 9 多序列比对把认为是相似的碱基排列在同一列中，类似于双序歹h 比对，当一 个位置的碱基缺失的时候，本文使用“”表示，同样也像双序列比对一样，用一 种计分方式表示多序列比对。一个简单的方法，也是实用很广泛的一种方法，多 序列比对中包含所有双序列得出的计分，即：多序列比对中的所有双序列比对的 计分总和，本文把它称为s p 目标函数l “，定义如式( 2 3 ) 和式( 2 - 4 ) 所示： c o s t ( a ) = c o s t ( a t ，a ) 式( 2 3 ) t - ij - i + 1 ， c o s t ( a = d ( a ，m 4 + 钗m “ 式( 2 4 ) k - i 其中c o s t 臼。4 为有条序列的序列集彳中第i 和第，条序列的双序列比对的 计分值；d 为两条序列的相似性函数，实际应用中，本文使用相似性计分矩阵来 得出d ，故五叫正明，4 陶) 一般表示序列爿- 和4 对应残基的替换分值；g 为空位罚 分；力吼为序列以和以中的自然空位数。如果彳的一个比对a 满足： c o s t ( 彳) = m s x ( 铡栅) ，则称一是一个最优比对。 基于s p 的目标函数是一种基于一个相似性替换矩阵的计分策硌；它的应用最 广泛，对于每一个可能的氨基酸替代需要一个替换矩阵，对于删除插入的情况使 用空位罚分给出其代价和给序列加权【1 7 1 。在这种情况下，一个最优多序列比对被 定义为：对于替换和插入或删除有最小的代价。这个计分方法的主要限制是依赖 于通用的相似性替换矩阵。通常基于大量比对的统计分析来建立，因此这不可能 适合于每一个序列。 2 c o f f e e 目标函数 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 te v a l u a t i o n ) 目标函 数是1 9 9 8 年由c e d r i cn o t r e d a m e 等人提出的一种新的计分函数。这个目标函数反 映了一个多序列比对和这个统一序列的双序列比对的数据库的一致性的程度。使 用c o f f e e 能提高多序列比对的精确性，当序列之间的相似度较低的时候c o f f e e 优于其他的目标函数。 c o f f e e 目标函数由两部分组成：( 1 ) 组相关的双序列比对库；( 2 ) 计算多序 列比对和库中双序列的一致性的目标函数c o f f e e 函数。 ( 1 ) 创建双序列比对数据库。这个数据库由双序列比对产生，但至少要包括定 义这个多序列足够的信息。例如一个多序列比对包括个序列，这个双序列比对 数据库中要包括所有可能的( h 声- n ) 2 个双序列比对结果，双序列比对的方法，我们 可以任意选择。 ( 2 ) c o f f e e 函数 “ 假设一个满意的双序列比对数据库已经建好了。c o f f e e 目标函数定义如式 ( 2 - 5 ) 所示： i o 基于a - s t a r 和d i a l i g n 算法的多序列比对 c o f f e e s c o r e = i 彬，s c o r e ( 彳, a ) i i 形。x l e n ( a j 。) j 式( 2 5 ) l i = l p i * 1jl “j - i + l j 一个多序列比对包括条序列s l 曲；a o 为多序列中的双序列的投影，l e n ( a 。0 为双序列比对的长度，8 c o r e ( a , j ) 是多序列比对中如和数据库中z “双序列比对结 果的一致性分数。即：s c o g 圆( a o ) 为多序列比对中a 。和数据库中a i j 双序列比对结 果的匹配残基的数目。阡0 为双序列比对相关的权值，最简单的矾，等于两个比对 序列的相似度的百分比。从上面的公式我们可以看出c o f f e es c o r e 是在0 - 1 之 间的数。 c o f f e e 目标函数和s p 目标函数的主要的不同是：在c o f f e e 中没有额外的 空位罚分，因为这些信息都已经包含在双序列比对库中。c o f f e e 目标函数的计 算过程如图2 1 所示： 我们可以计算出来c o l u m ns c o r e 一8 0 + 5 0 + 2 5 + 6 0 8 0 + 3 0 + 2 5 + 5 0 + 6 0 + 6 0 = 0 7 图2 1c o