生物信息学序列比对ppt课件

1 第二章 序列比对 生物信息学 2 第一节 引 言 Section 1 Introduction 3 （一） 同源 两个序列享有一个共同的进化上的祖先，则这两 个序列是同源的。 对于两个序列，他们或者同源或者不同源，不能 说他们 70% 或 80% 同源。 一 、同源、相似与距离 4 同源可分为垂直同源（ ortholog）和水平同源（ paralog） 垂直同源与水平同源 5 （二） 相似 性 与距离 相似性、距离：是两个定量描述多个序列相似度 的度量。 相似性：被比对序列之间的相似程度。 距离：被比对序列间的差异程度。 相似性既可用于全局比对也可用于局部比对，而 距离一般仅用于全局比对，因为它反映了把一个 序列转换成另一个序列所需字符替换的耗费。 6 二、 相似与距离的定量描述 相似性可定量地定义为两个序列的函数，即它可有 多个值，值的大小取决于两个序列对应位置上相同 字符的个数，值越大则表示两个序列越相似 。 编辑距离 （ edit distance） 也可定量地定义为两个序 列的函数，其值取决于两个序列对应位置上差异字 符的个数，值越小则表示两个序列越相似 。 7 对于一个比对，不论使用什么计分函数进行计分 ，相似性被定义为总等值于最大的计分： 对于 k个序列，如果用一个函数 cost（） 对每一列 的所有替换操作进行计分，则多个序列之间的距 离等值于最小的计分： 8 对相似性的计分 9 编辑距离（ edit distance）：一般用海明距离表示。 10 三、算法实现的比对 用计算机科学的术语来说，比对两个序列就是找出 两个序列的最长公共子序列 （ longest common subsequence， LCS） ，它反映了两个序列的最高 相似度。 11 动态规划法示意 （ A） 使用动态规划法寻找两个序列的最长公共部分； （ B） 动态规划表的填写。 12 四、序列比对的作用 获得共性序列 序列测序 突变分析 种系分析 保守区段分析 基因和蛋白质功能分析 13 第二节 比对算法概要 Section 2 Alignment Algorithms 14 （ 一 ） 通过点矩阵对序列比较进行计分 A.两条序列完全相同 一、替换计分矩阵 15 B.两条序列有一个共同的子序列 16 C.两条序列反向匹配 17 D.两条序列存在不连续的两条子序列 18 （ 二 ） DNA序列比对的替换计分矩阵 等价矩阵 （ unitary matrix） 转换 -颠换矩阵 （ transition-transversion matrix） BLAST矩阵 19 核苷酸转换 矩阵 20 （ 三 ） 蛋白质序列比对的替换计分矩阵 等价矩阵 遗传密码矩阵（ GCM） 疏水性矩阵（ hydrophobic matrix ） PAM矩阵 BLOSUM矩阵 21 PAM矩阵是从蛋白质序列的全局比对结果推导出来 的，而 BLOSUM 矩阵则是从蛋白质序列块 （ 短序 列 ） 比对推导出来的。 PAM/BLOSUM矩阵编号与序列亲缘关系的比较 22 二、双序列全局比对 动态规划算法 的思想 a, b是使用某一字符集 的序列（ DNA 或蛋白 质 序列）； m = a的 长 度； n = b的 长 度； S（ i,j） 是按照某替 换计 分矩 阵 得到的前 缀 a1.i 与 b1.j最大相似性得分； 23 w（ c,d） 是字符 c和 d按照替 换计 分矩 阵计 算的得分。 可按照 规则 建立得分矩 阵 ： S（ i,0） = 0, 0 i m S（ 0,j） = 0, 0 j n S（ i-1,j-1） + w（ ai,bj） 匹配或错配 S（ i,j） =max S（ i-1,j） + w（ ai,-） 插入 S（ i,j-1） 缺失不罚分 24 例如，对于序列 a=ACACACTA，序列 b=AGCACACA，计分规则 w（ 匹配 ） =+2； w（ a,-） =w（ -,b） =w（ 失配 ） =-1 25 得分矩 阵 26 三、双序列局部比对 处理子序列与完整序列 （ 或短序列与长序列 ） 比对 的一般过程是：设短序列 a和长序列 b，它们的长度 分别为 La和 Lb，比对是在 b序列中寻找 La长度的 a序 列的过程。 27 四、多序列全局比对 多序列比对主要涉及四个要素： 选择一组能进行比对的序列 （ 要求是同源序列 ）； 选择一个实现比对与计分的算法与软件 ； 确定软件的参数 ； 合理地解释比对的结果 ； 与双序列比对一样，多序列比对也有全局比对 和局部比对 。 28 （ 一 ） 动态规划法进行多序列比对 （ A） 计算三个序列间的一个比对单元 （ i,j,k） 依赖于其 7个前导项； （ B） 计算 u=ATGTTAT， v=ATCGTAC， w=ATGC三序列 比对的 三维 得分矩阵 。 计算三序列比对 29 （ 二 ） 渐进多序列比对 三 个 序列 的配对比对未必能组合成一个多序列比对 30 对于接近或超过 100个序列的多序列比对，渐进多序 列比对具有较高效率。最流行的渐进多序列比对软件 是 Clustal家族 。 31 ClustalW 有以下特点 ： 首先，在比对中对每个序列赋予一个特殊的权值以 降低高度近似序列的影响和提高相距遥远的序列的 影响 （如下图）。 ClustalW 中对序列赋 权的方法 32 其次，根据序列间进化距离的离异度 （ divergence） 在比对的不同阶段使用不同的氨基酸替换矩阵； 第三，采用了与特定氨基酸相关的空缺 （ gap） 罚分 函数，对亲水性氨基酸区域中的空缺予以较低的罚分 ； 第四，对在早期配对比对中产生空缺的位置进行较少 的罚分，对引入空缺和扩展空缺进行不同的罚分。 33 迭代法 基于一致性的方法 遗传算法 其他多序列全局比对方法 34 五、多序列局部比对 全局比对，其共同特征是序列中所有对应字符均假 定可以匹配，所有字符具有同等的重要性，空格的 插入是为了使整个序列得到比对，包括使两端对齐 。 局部比对不假定整个序列可以匹配，重在考虑序列 中能够高度匹配的一个区段，可赋予该区段更大的 计分权值，空格的插入是为了使高度匹配的区段得 到更好的比对。 35 对 2个序列进行全局和局部比对可得到完全不同的结果 36 基于 隐马尔可夫 模型的多序列比对方法 隐马尔可夫 模型和 3个蛋白质序列 PHSFTYVMT、 PGSFTYW 、 RFTGFW 的最小公共超图 37 六、比对的统计显著性 确定比对得分 score是否偶然 ： 1.将 球蛋白或肌球蛋白与大量非同源的蛋白质做比 对，然后将 score与这些比对的得分进行比较。 2.把一个序列与一组随机产生的序列进行比对，然后 同样将 score与这些比对的得分进行比较。 3.随机将两个序列中的一个打乱重组，比如说重组 100次，并与另一个序列比对，同样得到一组比对 的得分。 38 第三节 数据库搜索 Section 3 Database Search 39 一、经典 BLAST 基本的 BLAST算法本身很简单，它的要点是片段 对 （ segment pair） 的概念，它是指两个给定序列 中的一对子序列，它们的长度相等，且可以形成 无空格的完全匹配。 40 程序 名 查询 序列 数据库 类型 方法 blast p 蛋白 质 蛋白 质 用蛋白 质查询 序列搜索蛋白 质 序列数据 库 blast n 核酸 核酸 用核酸 查询 序列搜索核酸序列 数据 库 blast x 核酸 蛋白 质 将核酸序列按 6条 链 翻 译 成蛋 白 质 序列后搜索蛋白 质 序列数 据 库 tblas tn 蛋白 质 核酸 用蛋白 质查询 序列搜索核酸序 列数据 库 ，核酸序列按 6条 链 翻 译 成蛋白 质 tblas tx 核酸 核酸 将核酸序列按 6条 链 翻 译 成蛋 白 质 序列后搜索由核酸序列数 据 库 按 6条 链 翻 译 成的蛋白 质 序列的数据 库 BLAST的查询序列和数据库的类型 41 BLAST算法图示 42 二、衍生 BLAST （ 一 ） PSI-BLAST 主要用于搜索与感兴趣的蛋白质关系较远的蛋白质 。（ 二 ） PHI-BLAST 用来帮助判断这个蛋白质属于哪个家族 。 （ 三 ） BLASTZ BLASTZ是在比对人和鼠的基因组中发展起来的 ，它适合于比对非常长的序列 。 43 三、 BLAT BLAT（ The BLAST-Like Alignment Tool） 与 BLAST搜索原理相似，但发展了一些专门针对全 基因组分析的技术。 BLAT的优点在于速度快，其比对速度要比 BLAST 快几百倍，其根本原因在于 : BLAST是将查询序列 索引化，而 BLAT则是将搜索数据库索引化， BLAT 把相关的呈共线性的比对结果连接成为更大 的比对结果。 44 四、 RNA序列搜索 RNA序列比对 /搜索算法可大致分成两类： 查询序列 （ query） 的结构未知，要找到数据库中 和其结构相近的同源序列。 45 利用查询序列的结构信息，在结构信息的使用上 又可以细分为： (a) 通过构建一个描述 RNA序列共性结构的概率模型 进行数据库检索 ； (b) 基于索引 （ index） 或者模体 （ motif） 描述的方 法定义 rna结构或共性结构，并进行数据库搜索 。 46 五、数据库搜索的统计显著性 一个典型的 BLAST搜索的输出包括 E值和得分， 后者又分原始得分 （ raw scores） 和比特得分 （ bit scores） 。 P=1-e-E P值和 E值是反映比对显著性的两种不同方式 ， 大部分 BLAST在线服务使用 E值而非 P值来 定义搜索的统计学显著性。 47 第四节 比对软件、参数与数据资源 Section 4 Alignment Software， Parameter and Resource 48 一、参数选择的一般原则 空格罚分涉及几个问题： 空格罚分是否大于失配罚分； 不同大小空缺的罚分； 空格的引入与延伸是否予以不同罚分。 49 如果一次数据库搜索产生了太多的返回结果，可采取 如下措施： 使用参考序列 （ 带 “refseq”的 ） 数据库，这样可减 少许多冗余结果； 使查询序列只包含一个结构域，减少多结构域带来 的多匹配； 根据查询序列与数据库序列的关系使用更合适的替 换计分矩阵； 降低 E值。 50 如果一次数据库搜索产生了太少的返回结果，可 采取如下措施： 提高 E值； 使用更大的 PAM矩阵或更小的 BLOSUM矩阵； 减小字长以及减小阈值。 51 二、主要比对软件 52 三、 EBI中的序列比对工具 双序列比对 多序列比对 特性 工具 工具 Global alignment Needle Clustal Omega Global alignment Stretcher ClustalW2 Local alignment Water DbClustal Local alignment Lalign Kalign Local alignment Matcher MAFFT Genomic alignment PromoterWise MUSCLE Genomic alignment GeneWise MView Genomic alignment Wise2DBA PRANK 53 四、 UCSC中的 BLAT比对工具 BLAT在 线 工具 输 入界面 54 BLAT在 线 工具 输 出 结 果 55 第五节 比对技术的发展 Section 5 Advances of Alignment Techniques 56 一、 glocal 比对 两个序列的局部、全局和 glocal比对所对应的路径 57 二、全基因组比对 全基因组比对主要揭示多个序列中保守的和非保守 的区段以及这些区段在基因组中的分布特征，这里 主要介绍 UCSC基因组浏览器 （ The UCSC Genome Browser） 中的全基因组比对方法。 58 UCSC基因组浏览器中所采用的多序列比对在多方面作 了改进 首先，它采用了参照序列 （ reference sequence） ， 使用 BLASTZ将每一个序列与参照序列进行局部配 对比对 ， 参照序列中的一个碱基