（计算机科学与技术专业论文）跨物种全基因组剪接比对快速算法设计与实现.pdf

垦堕型兰垫垄盔堂堑壅生堕兰堡丝苎 摘要 生物信息学是利用计算机技术处理和研究生物数据的一门新兴交叉学科。序 列比对是生物信息学领域一种重要的研究方法，进行比对可以根据已知序列对未 知序列的结构和功能进行快速的预测。剪接比对指的是在比对过程中考虑不同选 择性剪接方式的序列比对方法。随着生物序列数据的激增以及选择性剪接对真核 基因调控机制研究的进一步发展，如何获得比对质量更好、时空效率更高适合于 基因组级别序列比对的剪接比对算法成为生物信息学研究的一个具有重要意义 的课题。 本文首先对f a s t a 、b l a s t 、b l a t 、s i m 4 等现有比对工具进行了分析与比较， 阐述了其所存在的问题。结合自身的应用问题需求对目前国际上流行的剪接比对 工具s i m 4 进行了深入剖析，提出了跨物种全基因组剪接比对快速算法，通过对 参与比对序列建立索引以及选定合适的命中( h i t ) 选取策略等方法对s i m 4 进行了 串行优化，目的在于不改变原工具敏感度前提下提高比对速度并使其适合跨物种 之间的序列比对。在此基础上，基于任务划分策略对该算法进行了并行化研究。 并对并行程序进行了测试，与当前流行的比对工具( b l a s t 、b l a t 、原始s i m 4 等) 进行比较，结果表明新方法可以获得较好的的运行性能。 随着人类基因组草图以及其他生物基因组草图的制备成功，人类已迈入后基 因时代，使用高通量生物技术来研究基因的功能已是当前研究的热点。优化后 s i m 4 适合于跨物种的转录本序列与基因组序列的比对，可为基因组范围内的基 因识别、图谱制作等应用问题提供支持。 主题词：生物信息学，序列比对，剪接比对，任务划分，并行化 第1 页 国防科学技术大学研究生院学位论文 a b s t f 认c t b i o i n f o r m a t i c si san e wc r o s s i n gd i s c i p l i n ew h i c hu t i l i z e sm o d e r nc o m p u t a t i o n a l t e c h n o l o g yt oh a n d l ea n dr e s e a r c ht h ed a t ao fb i o l o g y s e q u e n c ea l i g n m e n ti sa n i m p o r t a n tr e s e a r c hm e t h o di nb i o i n f o r m a t i c s i tc a np r e d i c tt h es t r u c t u r e sa n d f u n c t i o n so fu n k n o w ns e q u e n c e sb ya l i g n i n gt h e mt ot h ek n o w ns i m i l a rs e q u e n c e s s p l i c e da l i g n m e n ti s as e q u e n c ea l i g n m e n tm e t h o dw h i c hc o n s i d e r st h ed i f f e r e n t a l t e r n a t i v es p l i c i n gf o r m sd u r i n ga l i g n m e n t w i t ht h er a p i dg r o w t ho fb i o l o g i c a l s e q u e n c ea n dt h ed e v e l o p m e n to fr e s e a r c ho nt h er e g u l a t o r ym e c h a n i s mo f a l t e r n a t i v es p l i c i n g , i t sv e r ye s s e n t i a lt od e v e l o pas p l i c e da l i g n m e n ta l g o r i t h mw i t h h i g ha l i g n m e n tq u a l i t ya n dh i g ht i m e s p a c ee f f i c i e n c y t h ep a p e rf i r s ta n a l y z e sa n dc o m p a r e st h ee x i s t i n ga l i g n m e n tt o o l sc a r e f u l l y t h e nw ef o c u so nt h ep o p u l a rs p l i c e da l i g n m e n tt o o ls i m 4 c o n s i d e r i n go u rs p e c i f i c a p p l i c a t i o n s , w eb r i n gf o r w a r daf a s ts p l i c ea l i g n m e n ta l g o r i t h mo nc r o s s s p e c i e s w h o l e g e n o m e ，i nw h i c hw eb u i l di n d e xo ft h es e q u e n c e sa n dc h o o s et h ep r o p e rh i t s e l e c t i o nc r i t e r i a t h ep u r p o s ei st oi n c r e a s et h ep r o c e s s i n gr a t ew i t h o u ts i g n i f i c a n t l o s so fs e n s i t i v i t ya n dm a k ei ts u i tf o rc r o s s - s p e c i e sa l i g n m e n t a f t e r w a r d sw ep a r a l l e l t h ea l g o r i t h mb a s e do nt a s kp a r t i t i o ns t r a t e g y t h e nt h et e s t sa r ep e r f o r m e dt o c o m p a r et h en e wa l g o r i t h mw i t ht h ep o p u l a ra l i g n m e n tt o o l s ( b l a s t , b l a t ，s i m 4 e t c ) a n dt h er e s u l t ss h o wt h a tt h eo p t i m i z e ds i m 4 h a v eb e t t e re x e c u t i o np e r f o r m a n c e a sm o r eo ft h eh u m a ng e n o m ed r a f ts e q u e n c ei sf i n i s h e d a n dg e n o m e sf r o m o t h e ro r g a n i s m sb e g i nt ob es e q u e n c e d ，h u m a n b e i n g sh a v es t e p p e di n t o p o s t g e n o m i ct i m e i t sb e i n gh o t s p o tr i g h tn o w t os t u d yt h ef u n c t i o n so fg e n e sb y h i g ht h r o u g h p u tb i o t e c h n o l o g i e s t h eo p t i m i z e ds i m 4i s s u r a b l ef o ra l i g n i n g t r a n s c r i p t st og e n o m ea c r o s ss p e c i e s i tc o u l db eu s ea ss u p p o r tt og e n er e c o g n i t i o n a n dg e n em a pm a k i n gi ng e n o m es c a l e k e yw o r d s ；b i o i n f o r m a t i c s s e q u e n c ea l i g n m e n t ，s p l i c e da l i g n m e n t ，t a s k p a r t i t i o n ，p a r a l l e l i z a t i o n 第f i 页 国防科学技术大学研究生院学位论文 表目录 表2 1 一种核酸的替换矩阵。 表2 2 空位设置罚分和空位扩展罚分的序列比对的影响1 3 表3 1b l a s t 家族2 2 表3 2 人类小鼠替换矩阵2 6 表3 3 跨物种比对时s i r e 4 的性能甜2 8 表3 4 测试结果 表4 1 测试数据4 8 表4 2 运行结果、加速比及效率4 8 表5 1m g c 数据5 2 表5 2m g c 提供下载数据5 2 第页 垦堕型堂垫查盔堂婴塞生堕兰垡堡塞 图目录 图1 1g e n b a n k 核算序列数据库增长情况( 数据来源：2 0 0 6 年3 月发布的g e n b a n k 第1 5 6 版说明) 2 图2 1 动态规划算法矩阵示意图1 0 图2 2 一个典型的序列比对计分公式1 2 图2 3 选择b l o s i j l 5 0 矩阵，使用恒等空位罚分d ：8 时全局比对情况1 4 图2 4 选择b l o s u m 5 0 矩阵，使用恒等空位罚分d = - 8 时局部比对情况1 4 图2 5 可变剪接的基本形式1 6 图2 6 剪接比对示意图。1 7 图2 7 剪接比对算法流程18 图3 1f a s l a 比对示意图2 1 图3 2f a s t a 算法示意图2 1 图3 3 建立索引示意图3 0 图3 4 完全匹配3 1 图3 5 近似完全匹配3 2 图3 6 多完全匹配3 4 图3 7 确定内含子外显子边界3 6 图3 8 核苷酸级别比对评测方法4 0 图4 1s i r e 4 并行策略4 7 图4 2 并行程序的加速比c a ) 和并行效率( b ) 4 9 图5 1m g c ：b c 0 6 3 2 5 0 与小鼠1 存染色体进行比对示意图5 4 图5 2 比对结果的比较( ( a ) ：s i r e 4 的结果；( b ) ：改进后程序的结果) 5 5 图5 3s i r e 4 对h m r l 9 5 中记录a b 0 1 0 2 8 1 的分析结果5 5 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 ， 学位论文题目：堕塑整全基固缉夔捷出盟迭选簋选遮让皇塞丑 学位论文作者签名：i 盘翌 日期：扣，年，月牛同 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：堕塑挫全基因组翦接堂墅迭造篡洼遮让皇塞理 学位论文作者签名：i 壑 作者指导教师签名 日期：幽。年1 1 月牌日 日期：c ；口6 年ff 月f 午同 国防科学技术大学研究生院学位论文 第一章绪论 人类基因组计划饵u r n 柚g e n o m ep r o j e 鸭h g p ) 的完成是是人类生命科学史 上最具里程碑意义的事件。人类基因组计划旨在通过测定人类基因组d n a 约 3 0 亿个碱基对的序列，搜寻所有人类基因并确定它们在染色体上的位置，明确 所有基因的结构和功能，解读人类的全部遗传信息，使得人类第一次在分子水 平上全面认识自我。该计划的完成为揭示生命奥秘的浩瀚工程提供了丰富的生 物分子数据，生物数据以惊人的速度增长，每天都有成千上万的新数据加入到 生物数据库中，这些数据资源中必定蕴含着大量重要的生物学意义，这正是解 决生命奥秘的关键所在，在信息不断膨胀的压力之下，门崭新的交叉学科一 一生物信息学应运而生。 1 1 课题背景 生物信息学是一门通过综合运用数学、计算机科学与工程和生物学等学科 的工具与技术对大量复杂的生物数据进行分析、加工和再处理，从而揭示出这 些数据所蕴含的生物学奥秘的学科。它通过对生物学实验数据的获取、加工、 存储、检索与分析，进而揭示数据所蕴含的生物学意义。生物信息学当前研究 内容主要包括：自动化获取实验数据进而进行加工和整理；d n a 序列拼接；基 因编码区域的预测：基因功能预测及蛋白组分析；蛋白质结构、功能预测等。 随着高通量生物技术的发展以及各种模式生物基因组研究的广泛开展，生物信 息学家所面临的任务，不仅仅是寻找高效的数据储存手段，还需要开发有效的 数据分析工具。只有利用新的、有效的数据分析工具，才能将序列信息转换成 生物学知识，并弄清它们所蕴含的结构和功能信息，进而彻底了解它们所表达 的生物学意义。 在生物学的研究过程中，生物学家的主要任务是解释实验所产生数据的生 物学意义。随着现代分子生物学的发展以及实验技术的不断改进，分子生物学 数据不断产生，这些数据数量庞大，关系复杂，以至于人们很难再凭借传统研 究方法完成如此海量数据的分析。特别是自1 9 9 0 年人类基因组计划启动以来， 人类与各种模式生物基因组的测序工作相继展开。根据国际数据库的统计，1 9 9 9 年1 2 月d n a 碱基数目为3 0 亿，2 0 0 0 年4 月d n a 碱基数目是6 0 亿。截止2 0 0 5 第1 页 国防科学技术大学研究生院学位论文 年为止，仅美国g e n b a n k 数据库中的d n a 序列总量己超过5 6 0 亿碱基对( 图 i 1 ) 。基于d n a 序列测序所建立起来的表达序列标签( e x p r e s s i o ns e q u e n c et a g ， e s t ) 数据库，其记录也已达1 0 0 0 多万条。在这些数据基础上派生、整理出来 的数据库已达7 0 0 余个。不但如此，数据仍以每1 4 个月翻一番的速度增长。 1 1 9 8 2 2 s l 枣 凋 摹 霞 i 百 万 鬃 鬣 纂 ( 肇 位 j + 亿 ) 1 9 8 2 髑嘻6 佃9 0 构9 t 锎瞎2 2 图1 1g e n b a n k 核算序列数据库增长情况( 数据来源：2 0 0 6 年3 月发布的g e n b a n k 第1 5 6 版说明) 生物信息学数据的激增极大丰富了生命科学的数据资源，同时也对数据处 理提出了更高的要求序列比对是生物信息学的核心研究内容之一，也是进行 各种序列分析任务的基本方法。在生物学研究过程中，为了确定新测序列的生 物属性，经常需要进行序列同源性分析，就是将新序列加入到一组与之同源， 但来自不同物种的序列中进行多序列同时比较，以确定该序列与其他序列间的 同源性大小。这是理论分析方法中最关键的一步。完成这一工作通常使用序列 比对的方法。不仅如此，在蛋白质结构预测等其他研究领域，序列比对也是最 为重要的一种方法。如何在庞大且繁冗复杂的数据中快速找到我们感兴趣的数 据，如何高效的利用已知基因组信息对数据进行整理，也是确定序列数据所包 第2 页 孵簿辩貔转聃熊“艟辨鹅拓料兹德髂籀甜篮嚣傅傅”佗侉8 6 2 0 秘畦轴嚣罅“撼罅鹈撼辩旅特蕾撼辩丝储憾似住健i2 o 国防科学技术大学研究生院学位论文 含生物学意义的关键。快速增长的生物数据要求有与之相适应的快速比对工具， 通过对现有比对软件进行分析，并没有满足我们工作需求的合适的比对工具， 因此开发多条转录本序列与基因组数量级序列的跨物种比对工具非常必要。 1 2 研究现状 序列比对的基础是基本的双序列比对，即只比较两条序列。进行比对的目 的是找出这些参与比对序列中结构或功能的相似性区域，从而判断序列是否具 有同源性。 双序列比对又分为全局比对( g l o b a la l i g n m e n t ) 和局部比对( l o c a l a l i g n m e n t ) ，典型的全局比对算法是n e e d l e m a n - - w u n s c h 算法【3 9 l ，该算法适用 于全局水平上相似性程度较高的两个序列的比对研究，n e e d l e m a n - - w u n s c h 算 法是最早提出的使用动态规划方法进行d n a 序列相似性比较的比对算法，随后 涌现的相关序列相似性比较算法都是基于动态规划思想的；典型的局部比对算 法是s m i t h - - w a t e r m a n 算法【4 0 】，这种算法适用于亲源关系较远、整体上不具有 相似性而在一些较小的区域上存在局部相似性的两个序列。这两个算法均为序 列比对的基本算法，都是基于动态规划方法的算法。1 9 7 5 年h i r s c h b e r g 4 2 】提出 一种空间复杂度为0 ( i n + n ) 的算法，但是该算法的时间需求是基本动态规划算法 的2 倍，是典型的时间换空间的算法。在国内，中国科学院计算技术研究所开 发了f a ( f a s t 舢i g n m e m ) 算法【4 3 l ，该算法时间和空间复杂度都介于基本动态规划 算法和h i r s c h b e r g 之间，另外可以通过对参数k 的调节获得在不同存储条件下 序列比对问题的最小解决时间。然而，随着生物序列信息量的激增，这些算法 的效率已不适合于生物信息学的需求。因此研究人员开发出许多基于基础比对 算法的启发式比对工具，如f a s t a 、b l a s t 、e s t g e n o m e 等目前应用最广泛 的工具。 在实际的序列相似性比较中，很少直接使用给予基础动态规划方法的算法， 因为对于长序列( 特别是d n a 序列) ，使用动态规划方法过于消耗时间。通常 使用的序列比对算法都在基础动态规划算法基础上进行了一定程度的优化。详 细算法会在第三章中描述。 转录本序列与基因组序列进行比对同基因组序列之间的比对不同，因为在 比对过程中转录本序列会在剪接位点处发生剪接，之后同基因组序列的不同位 第3 页 国防科学技术大学研究生院学位论文 置进行比对。这种比对方式称为剪接比对，目前比较流行的剪接比对工具有 b l a t 、s i r e 4 等。这里提到的比对工具同样会在第三章中详细介绍。 在序列比对算法领域，国外起步较早，因此有较多成熟的软件产品，丽国 内主要是提供国外的信息服务镜像，如北京大学的e m b l 镜像；或是对现有序 列比对算法进行优化，如中科院计算技术研究所与华大测序中心合作，基于曙 光3 0 0 0 超级计算机系统，开发了b l a s t ，s m i t h - - w a t e r m a n 的并行算法，并应 用于华大测序中心的数据处理流程中。剪接比对工具方面，军事医学科学院开 发的剪接比对程序e l p a r s e r 4 1 】可以给出详细的比对情况，可给出内含子，外显子 间接位点处的匹配情况，尽量满足g t a g 等规则剪接方式，但并不为了强制比 对满足边界类型而破坏最优匹配。e i p a r s e r 也可以动态调整字( w o r d ) 长，不允许 长度 5 b p 的匹配并且严格要求短外显子的剪接边界符合规则剪接，尽可能避免 不符合生物学意义的短外显予以及可能影响调控的变异。 由于不同物种之间进化距离不同，因此各物种间的碱基变异倾向性有所不 同。为了提高在进行不同物种的跨物种序列比对时的准确性，通用的方法是考 虑不同物种的碱基替换矩阵，例如跨物种比对工具b l a s t z 即考虑了人类- 小鼠 替换矩阵。 在基因组学中对基因和其他生物特征的标注称为基因组注释( g e n o m e a n n o t a t i o 小。全基因组和基因组片段不仅在序列大小、获取方式等方面存在差异， 而且在生物学注释等方面存在很大的不同。而目前正在使用的序列分析和预测、 注释软件都是基于基因组片段开发设计的，因此，它们在分析处理基因组片段 数据时非常成功，而在分析处理全基因组数据时却先天不足。研究表明，不同 物种基因组序列之间的保守区域很有可能是具有生物学功能的区域，随着人类、 大鼠、小鼠等生物基因组测序的完成，利用跨物种序列比对进行基因组注释已 经逐渐成为一种趋势。 综上所述，序列比对仍1 日是生物信息学领域关键而具有挑战性的研究内容， 研究和设计同时具有高敏感性和高速度的跨物种剪接比对算法是目前急需解决 的问题。 1 3 本文主要工作及其贡献 本课题源自国家自然科学基金项目( 6 0 6 7 4 0 1 5 ) “大规模r n a 二级结构预 国防科学技术大学研究生院学位论文 测算法及其并行化研究”。 本文在深入探讨序列比对以及现有比对工具的优劣后，针对我们课题处理 数据的特点，首先对剪接比对软件s i r e 4 进行了串行优化，在不损失敏感度前提 下加快其运行速度，引入替换矩阵使其适合于跨物种比对，并改进了原s i m 4 的 边界识别策略。在串行优化基础之上，我们基于任务划分策略对s i m 4 进行了并 行优化，取得了较好的并行效果，并且该并行方法具有一定的通用性，可以用 于实现其他生物序列比对软件的并行化。之后介绍剪接比对的一个应用问题： 将转录本数据与人类、大鼠、小鼠的基因组数据进行交叉比对，利用已经完成 测序的基因组信息，对实验得出的转录本进行整理，制作跨物种的转录图谱， 以研究新的基因的结构与功能。 本文主要有以下四个方面的工作和贡献： 第一，学习了解比对的有关工艺流程和数据处理过程，建立序列比对问题 的背景知识。 第二，在详细分析现有剪接比对工具基础之上，对在对串行s i m 4 进行优化 的基础上，提出了跨物种全基因组剪接比对快速算法。主要方法为在搜索阶段 改变建立索引策略和h i t 确定策略以求在保证敏感度前提下提高程序处理序列 的速度：在比对阶段使用人类，j 、鼠替换矩阵以便于程序适合于跨人类- 啮齿类的 序列比对，同时放松内含子# v 显子边界的要求，避免原s i m 4 因过分强调边界条 件而导致比对不准确的情形发生。经测试，优化后算法可应用于解决跨物种的 全基因组范围内的序列比对问题。 第三，基于问题空间分解的策略，提出并实现了跨物种全基因组剪接比对 快速算法并行化方法，并对并行化后的程序进行了测试。 攻读硕士学位期间，共发表论文3 篇，其中以第一作者在核心期刊发表论 文l 篇。 1 4 论文结构 第二章重点介绍了序列比对以及可变剪接和剪接比对的基本概念、基本算 法。 第三章对现有的比对软件进行详细的分析说明，针对比对的不同阶段提出 跨物种全基因组剪接比对快速算法的计算方案，并程序进行了测试，探讨了探 第5 页 国防科学技术大学研究生院学位论文 讨了新算法的性能。 第四章对跨物种全基因组剪接比对快速算法进行了基于任务划分的并行 化，并对并行化后的进行了性能测试。 第五章介绍剪接比对软件的一个应用，跨物种的转录图谱制作。 第六章对全文进行总结，并展望今后的工作。 第6 页 国防科学技术大学研究生院学位论文 第二章序列比对以及序列剪接比对机理研究 2 1 序列比对 序列比对( s e q u e n c ea l i g n m e n t ) ，又称为序列连配、序列对齐、序列对准， 是生物信息学中最经典的研究方法之一。序列比对的意义在于从核酸、氨基酸 层次上分析序列的相似性，推测其结构、功能及进化上的联系，是基因识别、 分子进化、生命起源研究的常规技术，也是数据库搜索算法的基础。本课题主 要涉及双序列的比对，因此如无特殊说明，下文中的比对均指双序列比对。序 列比对可以在核酸和氨基酸两种水平上进行，因为本课题解决的主要是在核酸 水平上的进行转录本与d n a 序列的比对问题，所以以下序列比对均指在核酸水 平上进行序列比对。 2 1 1 序列比对的意义 序列比对是揭示两个序列之间是否具有足够的相似性的一个重要途径，从 这种计算出的相似性可以迸一步推断两者是否具有共同的进化祖先，即同源性 9 1 。所谓序列相似性只是经过一定的算法所得出的可以量化的结果( 例如两两 序列之间的相同d n a 碱基残基数量的多少，通常采用一定的比对分数来表示) ； 而同源性则是一个进化意义上的概念，即两个序列是否同源需要有进化事实的 验证。由于无法得知这个祖先的序列( 除非能够从化石中获得它的d n a ) ，所 以我们所能做的就是从现存的序列中进行探求。当发现两个基因或蛋白质具有 惊人的相似性时，可以认为他们具有一段共同的进化历程，从而推断它们可能 会具有相似的生物学功能，不过在该推断成为结论之前必须要经过实验验证。 序列比对的另一个重要结果是可以通过序列之间的相同氨基酸残基来说明 序列中这些相同的氨基酸残基比其他位置上的残基更保守，从而提示这些保守 点上的残基对蛋白质的结构和功能是至关重要的，如它们可能是酶的活性位点 残基、形成特定功能结构域( d o m a i n ) 或基序( m o t i f ) 的残基等等。 序列比对还是数据库搜索算法的基础，将查询序列与整个数据库中序列进 行比对，继而获得该序列与数据库中已有数据的相似性，这样可以快速的获得 与查询序列有关的信息，为进一步获得该序列的功能、结构提供参考。近年来 第7 页 国防科学技术大学研究生院学位论文 随着生物信息学数据的大量积累以及对数据的注释日益增多，比对方法已经成 为分析、预测新基因的有效方法。 2 1 2 序列比对的数学模型 设x - - - x lx 2 x 。和尸y ly 2 y n 是一个固定字符集合e 上的两条序列，在生物 序列中，若x 是d n a 序列，则= a ，g ，c ，t ，若x 是蛋白质序列，则 = a ，r ，v ，蛋白质由2 0 种氨基酸组成，因此集合中的字符数为2 0 。 定义2 1 ：如果x 和y 是两个任意的字符，那么o ( x ，y ) 表示字符x 和y 在进行比较时所得的分值，称为一个记分函数。记分函数包括了当x 为空字符 或y 为空字符的情况，在序列中一个所谓的空字符表示序列在此位置可能缺失 了一个字符，我们用“一”来表示这种缺失。在不同的算法当中，记分函数可 以有不同的记分方法。例如，可以这样定义记分函数。o ( x ，x ) = + 2 ，o ( x ，y ) = o ( x ，- - ) = o ( 一，y ) = - 1 。 定义2 2 ：给定两条序列s = s 18 2 s n 和t - - t it 2 t n ，那么用i s i 表示s 的长度， s i l l 表示序列s 的第i 个字符。若序列s 和t 相同，则必须满足： ( 1 ) i s l = l t b ( 2 ) s 【i 】_ t t i ，( 1 i i s l ) t 定义2 3 ：如果s 和t 是两个序列，那么s 和t 的全局序列可以用序列s 7 和t 7 来表示，其中： ( 1 ) f s7 i = i t 1 ( 2 ) 将s 和t 中的空字符除去后所得到的序列分别为s 和t ，( 例，若s = “a o - 一bc d ”，t 7 = “一ca d b d 一”，那么s = “ac bc d b ”，t = “ca d b d ”) ； 比对就是把序列s 和t 上下罗列起来，相应的位置进行一一的比较。比对 a 的分值s c o r e 可以用如下的公式来表示： ， s c o r e = 盯伊，【f 】) j - 1 【1 ) 其中，= l s i = i t 7 i ； 定义2 4 ：对于两个序列s 和t ，它们的全局最优比对a 是指在s 和t 的 所有相似性比较中值最大的s c o r e 所对应的排列。 在序列比对的过程中引入空位是为了补偿插入或删除，使序列的比对能更 紧密地符合某种期望的模型，但是在序列的比对中引入空位必须加以限制，否 第8 页 国防科学技术大学研究生院学位论文 则可能会出现为了使比对得分高而插入大量空格导致无效比对的情况发生。常 用的限制方法就是空位罚分，即每插入一个空位，就在总分值中减去一定分值 ( 罚分值) 。因此，序列比对最终结果的得分值是两个序列之间匹配碱基的总分值 与空位罚分的总和。关于空位罚分方面内容在后续章节将详细解释。 从序列比对的数学描述中得知，序列比对的目标就是寻找能够使得两条参 与比对的序列问具有最大相似度的比对方式。比对算法是寻找两个序列s 和t 的全局最优比对，是一个寻优问题。目前进行序列比对的算法很多，但大多数 算法都基于动态规划思想，时间和算法复杂度都是o ( m n ) ，其中m 、n 是算法矩 阵的行数和列数( 即参加比对的两条序列长度) 。下面对基于动态规划思想的 序列比对算法进行分析介绍。 2 1 3 序列比对算法 如前所述，序列比对问题可以转化为数学上的寻优问题，因此用来解决寻 优问题的算法都可以用来解决序列比对问题。目前最基本最普遍采用的方法是 动态规划算法。 动态规划算法解决序列比对问题的基本思想可描述为：使用迭代方法计算 出两个序列的相似分值，存于一个得分矩阵中：根据这个得分矩阵，回溯寻找 最优的比对序列。见图2 1 。其中箭头所指即为一个最佳比对，比对结果为： 第9 页 国防科学技术大学研究生院学位论文 acc g tcact g c a a c c 、 g 卜 c a c t g 、 图2 1 动态规划算法矩阵示意图 2 1 3 1 计分矩阵替换矩阵和空位罚分 从计算的角度出发，衡量两个序列之间相似性的方法是为每个与查询序列 比对的序列分配一个分值。一般这个分值越高表示两个序列之间比对得越好， 相似性越高。最简单的描述这种相似性的方法就是仅仅区分两条序列每个碱基 是相同还是不同，即将比对分值定义为相同的碱基数量。这种分析通常可以采 用点矩阵 1 0 】( d o t m a t r i x ) 的方法来进行，即以二维平面将两组序列之间相同的 碱基标记出来，从而以目视的方式观察两条序列相似的位置。 彳rgc gr gca 丁gcuiu al 彳r gcat gt ：一：1 ， ( 1 ) ( 2 ) g一111 s c d j ：4s c d r ：二3 一l 上面是两个d n a 序列之间的比对点矩阵，对于相同的碱基赋予分值1 ，对 第l o 页 ac gi口o t i t c l c a i a c l c t - g i o e c l c c l ca l a a b 国防科学技术大学研究生院学位论文 于不同的碱基赋予分值1 ，这样最后可以得到一个总分来衡量不同序列比对的 相似性。根据上图的得分情况，容易得出第( 1 ) 组序列相似性高于第( 2 ) 组 序列。 这种矩阵并没有考虑残基相互取代的倾向性，对所有的取代情况一视同仁， 在应用于同物种比对时还比较合适，因为同物种变异相对很少，比对的序列相 似性比较大而在不同物种情况下，例如人类和小鼠，这种矩阵就不是很合适 了在进行不同物种比对时必须要考虑变异的情况，即，使用一种考虑残基取 代倾向性的矩阵，否则比对结果必然要大打折扣。 表2 1 是考虑了残基之间取代倾向性的一个打分矩阵，不同残基取代被赋予 不同的分值。这种矩阵具有物种相关性，即不同两个物种之间残基取代倾向性 不同，替换矩阵也不相同，从表2 1 可以看出a 更倾向于转化为g 而不是c ，c 则更倾向于转化为t 而不是g 等。 表2 1 种核酸的替换矩阵 a1 3 6 g- 3 7 1 3 6 c1 6 01 6 01 3 6 t 1 6 0- 1 6 03 7 1 3 6 agct 拥有2 0 种氨基酸的蛋白质就复杂多了。目前最常用的两类蛋白质替换矩阵 是p a m 和b l o s u m 。p a m 在全局比对时效果较好，可用于寻找蛋白质的进化 起源，而b l o s u m 在局部比对时作用更明显，更易于用于发现蛋白质的保守域。 p a m 矩阵( p o i n ta c c e p t e dm u t a t i o np e r1 0 0r e s i d u e s ) 基于进化突变模型，一 个p a m 就是个一进化变异单位，进化距离对应残基突变的概率依照每1 0 0 个碱 基中有一个可接受的单点突变，但这并不意味1 0 0 次p a m 之后每个氨基酸都发 生了变化，因为其中一些位置可能会发生多次突变，甚至可能会变回到原来的 氨基酸。将1 个p a m 进化距离的矩阵多次自乘，可得到进化距离较远的p a m 矩阵，如p a m l 0 0 ，p a m 2 5 0 ( 数字越大，进化距离越远) 。 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 c e s ) 是从蛋白质模块数据库找出的 一组替换矩阵，用于解决序列远距离相关比对，如b l o s u m 5 0 ，b l o s u m 6 2 ， 数字越大表示序列相似度越高。 前面有所介绍，两条比对序列并不总是等长的，为了得到最优的全局比对 第l l 页 里堕登堂垫查盔堂堑塞生堕兰垡堡奎 结果，在比对时要加入一定的空位。如图2 2 所示，两个碱基之间的破折号即代 表了一个空位。从生物学角度来理解空位比较容易，最常见的就是单个碱基的 插入或缺失突变，还有在染色体交换过程中发生大片段的插入或丢失、d n a 复 制过程中的插入错配等都会产生大量的空位。很明显，这些空位的数量对最后 的比对分数也有很大的影响。因此，比对所得分值应该包括以上两个部分的内 容。如图2 2 所示为两条d n a 序列两两比对的最后得分公式： 嬲激锱撼磷黼裟黼c 圣泓t g 黜t ”n 羹誉蕊徽挑a a g c , - g t a t c g 静，w ”，。?_ “一。、：氨：i勰 一一 瓤，j 一 ， s = ( i 妇以f f f 协+ 错配) 一日空位罚分， s c o r e = m a x ( s ) 图2 2 一个典型的序列比对计分公式 空位的引入反映了序列在突变过程中碱基插入删除的情况。插入删除可能 只涉及一个碱基，也可能涉及多个连续碱基。因此空位的引入不仅要考虑位置、 数目，还要考虑连续空位长度。在一些罚分模型中，连续的插入删除操作总罚 分并不等于单个插入删除操作的罚分总和。 用# s p a c e 表示空格数，# g a p 表示空位数。下面是两种常用的空位罚分方法： ( 1 ) 、恒定空位罚分( c o n s t a n tg a pp e n a l t i e s ) ： 对于每个空位罚分w g ，比对得分为： s c o r e ( a ) = m a 】【 a ( s n t j 】) + w g x # g a p 。 j ( 2 ) 、 仿射空位罚分( a f f i n eg a pp e n a l t i e s ) ： 对于长度大于l 的空位，给空位的第一个空格分配空位罚分w g ，称为“空 位设置罚分”，表示新增一个空位的成本，给后面的每个空格分配罚分w s ，称 为“空位扩展罚分”，表示空位延伸一个的成本；对于长度等于l 的空位，就 给这个空位分配“空位设置罚分”。则比对得分为： s c o r e ( a ) = m a x c r ( s t ，【，】) + x # g a p + w , x # s p a c e l 仿射空位罚分模型更容易反映序列比对的生物学意义。表2 2 说明了空位设 国防科学技术大学研究生院学位论文 置( g a po p e n i n g ) 和空位扩展( g a pe x t e n s i o n ) 对序列比对结果的影响。 表2 2 空位设置罚分和空位扩展罚分的序列比对的影响 空位设置罚空位扩展罚 作用 分分 极少插入或删除，适用于亲缘关系接近的序 大大 列比对 少量较长空位插入，适用于可能在整个功能 大小 域插入空位的情况 大量短空位插入，用于亲缘关系较远的序列 小小 比对 2 1 3 2 全局比对和局部比对 根据比较目的不同，可以将序列比对分为两种，即全局比对( g l o b a l a l i g m n e n t ) 和局部比对( l o c a la l i g n m e n t ) 9 1 。简单的讲，全局比对就是将序列 的全部信息进行比较。而局部比对则只考虑某些序列区域的相似性。选择哪种 方法取决于是要推定两个序列在整个长度上都相关，还是只有序列局部的同源 性。 相应的，动态规划算法按照解决问题的不同可以分为全局动态规划算法和 局部动态规划算法 全局比对：n e e d l e m a n - w u n s e h 算法 算法的基本思想是：使用较短的予序列的最佳比对逐步递归的构建整条序 列的最佳比对，即在算法矩阵的右下角和左上角单元之间寻找一条最优路径。 图2 3 是对两条短蛋白质序列h e a g a w g h e e 和p a w h e a e 进行比对的情况， 选择b l o s u m 5 0 矩阵，使用等值空位罚分模型( d = - 8 ) 。 第1 3 页 国防科学技术大学研究生院学位论文 tp 4 - - 啦- 强i t - - 啦h 锄p 璀- 伪十“- 以p 寥量、4 气母、渤 墙、毵。越_ 埘国辑书 ，弋、 矗_ 碡- m毒+4pm嚣。氆- 、雏k - 承h 澎- 勘 广广、弋 w- 3 爆4 1 - 6刁1 ，5 - 口- o l + - - 2 9 卜舅 f l 、 h3 2- k埔f s 毫 辱船 - 7- 3 _ - l l _ - 1 9 产尹气，、 尹气。、 量- 4 0 秘 i 卜_ 岱- 1 6 母 * 1 2- i s 7 3 t1t 、 、 、tl 、 走嘏渤韶毋扣- l lm趣1 21 5s2 f芦f 。广气s 、 e- 5 6 - 箍3 “正1 2。，- 1 5投毒l 丑蕊g a w g 珏2 一致 一一p - ；啜一h e a e 图2 3 选择b l o s l r m 5 0 矩阵，使用恒等空位罚分d _ 8 时全局比对情况 局部比对：s m i t h w a t e r m a n 算法 同全局比对不同，局部比对解决的问题是在算法矩阵中寻找一条活n 条最 优路径，这些路径的起点和重点不必要是左上角或右下角的两个单元，可以是 人意的，即这些路径在矩阵中是局部最优的。使用s m r h w a t e r m a n 算法对相同 的两条蛋白质序列进行局部比对，使用相同的打分矩阵和空位罚分策略，所得 结果如图2 4 所示。 000o 0o口0b0 1 p00oo0番oo 奇 口 i 气、 0o0s05 ono o 1 飞 w静 o 0覆 蕾 o筠扣1 2 卜4o 、，气、 h0i o - 哩0 oo瞎l 毒 墨一1 4 - 1 ， 、 e021 6 _ ， oo4l o倦嚣j t 、 f ao口t2 1 - l 毒，04 1 02 0j 、尹气 、 毫嚣疆：6珏 l 毒1 2t , - 4碡41 6： a 鞫写飘嚣 摹翁哺 图2 4 选择b l o s u m s o 矩阵，使用恒等空位罚分d = - 8 时局部比对情况 国防科学技术大学研究生院学位论文 2 2 可交剪接与剪接比对 将转录本序列( 例如e s t 序列、c d n a 序列以及m r n a 序列) 比对至基因 组序列与基因组序列之间进行比对不同。因为转录本与基因组序列