双序列比对.

Presentation on theme: "双序列比对."— Presentation transcript:

1 双序列比对

2 什么是序列比对？ 序列比对(Sequence Alignment)是通过在序列中搜索一系列单个性状或性状模式来比较2个（双序列比对）或更多（多重序列比对）序列的方法 序列比对分类 双序列比对：两条序列的比对 多序列比对：三条或以上序列的比对

3 我们为什么关注序列比对 结构与功能预测:相似的序列可能具有相同的结构与功能 发现保守与易变区域 发现生物进化方面的信息
同源性(Homologous Genes) ：序列来自共同的祖先，或具有共同的进化史，相似的序列往往具有同源性(如图) 相似性(Similarity)：两序列根据某种参数相近，但相似的序列不一定具有同源性。相似性≠同源性，两基因只有同源与非同源关系

4 我们为什么关注序列比对（续） 直系同源(Orthologs)：具有共同祖先与相似功能的同源基因（无基因复制事件）
旁系同源(Paralogs)：两个物种A和B的同源基因，分别是共同祖先基因组中由复制事件而产生的不同拷贝的后代 趋同进化(Convergent evolution):序列中的相似区域可能不具有共同的祖先，而是通过两条进化路径独立获得相同的功能（如图）

5 同源序列与祖先序列关系 进化距离：一个序列变成另一个序列所需的步骤数。如A变为B的进化距离为：x+y

6 基因进化 AB：物种I与物种II中的a1是直系同源，a1与a2为旁系同源 C：趋同进化，物种I与物种II经历不同的进化途径，产生相同的功能
D：基因转移，称为水平转移基因

7 序列比对两种类型 Global Alignment Local L G P S S K Q T G K G S - S R I W D N
全局序列比对 定义：在全局范围内对两条序列进行比对打分的方法 适合于非常相似且长度近似相等的序列 局部序列比对 定义：一种寻找匹配子序列的序列比对方法 适合于一些片段相似而另一些片段相异的序列 　Global Alignment 　Local L G P S S K Q T G K G S - S R I W D N | | | | | | | L N - I T K S A G K G A I M R L G D A – – – – – – – T G K G – – – – – – – – | | | – – – – – – – A G K G – – – – – – – –

8 记分矩阵与空位罚分 DNA 计分矩阵 蛋白质计分矩阵 广泛使用的两种矩阵 PAM BLOSUM 空位罚分

9 DNA 计分矩阵 Sequence 1 Sequence 2 匹配: 1 错配: 0 分值：5
actaccagttcatttgatacttctcaaa taccattaccgtgttaactgaaaggacttaaagact A G C T A G C T 匹配: 1 错配: 0 分值：5

10 转换和颠换 C T A G  表示转换(transition)，表示颠换(transversions)  转换比颠换更容易发生 嘧啶
嘌呤   表示转换(transition)，表示颠换(transversions) 转换比颠换更容易发生

11 转换和颠换 A G T C 0.99 0.006 0.002 转换速率是颠换3倍时的模型

12 蛋白质计分矩阵 记分矩阵 T:G = -2 T:T = 5 Score = 48 Sequence 1
PTHPLASKTQILPEDLASEDLTI PTHPLAGERAIGLARLAEEDFGM 记分矩阵 C S T P A G N D . . C 9 S -1 4 T P A G N D . C S T P A G N D . . C 9 S -1 4 T P A G N D . T:G = -2 T:T = 5 Score = 48

13 PAM( Accepted Point Mutation)矩阵
氨基酸记分系统需要替换的模式来提高灵敏度以检测弱的相似性 氨基酸容易被其它生化、物理特性相似的氨基酸替换 PAM矩阵给出了进化过程中同源蛋白质从一个氨基酸变到另一个氨基酸的似然率(Likelihood) PAM1(1个PAM单位）被定义为每100个残基出现一个被接受的点突变(氨基酸的置换不引起蛋白质功能上的显著变化） PAMn是PAM1自乘n次 PAM250、PAM120、PAM80和PAM60矩阵可用于相似性分别为20%、40%、50%和60%的序列比对

14 PAM 250 C W W -8 17 A R N D C Q E G H I L K M F P S T W Y V B Z

15 BLOSUM矩阵 (Blocks Substitution Matrix)
在模块比对的每一列中，分别计算 两两氨基酸的变化情况,来自所有 模块的数值被用来计算BLOSUM矩阵 矩阵后面的数字表示构建此矩阵所用的 序列的相似程度，如BLOSUM62表示由 相似度为62%的序列构建 A C E A C E A - C = 4 A - E = 2 C - E = 2 A - A = 1 C - C = 1

16 BLOSUM62

17 如何选择合适的评分矩阵？ 一般来说,在局部相似性搜索上， BLOSUM 矩阵较PAM要好 当比较距离相近的蛋白时，应选择低的PAM或高的BLOSUM矩阵；当比较距离较远的蛋白时，应选择高的PAM或低的BLOSUM矩阵 　 对于数据库搜索来说一般选择BLOSUM62矩阵 PAM矩阵可用于寻找蛋白质的进化起源，BLOSUM矩阵用于发现蛋白质的保守域

18 空位罚分(Gap Penalties) 空位为了获得两个序列最佳比对，必须使用空位和空位罚分
空位罚分分为：空位开放罚分(Gap opening penalty)和空位扩展罚分(Gap extension penalty) 最优的序列比对通常具有以下两下特征： 尽可能多的匹配 尽可能少的空位 插入任意多的空位会产生较高的分数，但找到的并不一定是真正相似序列

19 空位罚分 ? 不允许有空位 Score: -21 匹配 = 5 错配 = -4 允许空位但不罚分 Score: 55
1 GTGATAGACAC ||| 1 GTGCATAGACAC　 匹配 = 5 错配 = -4 允许空位但不罚分 Score: 55 ? 1 GTG-ATAGACAC ||| |||||||| 1 GTGCATAGACAC　 1 GTG--ATAGACAC ||| |||||||| 1 GTGC-ATAGACAC　

20 Wx=g+r(x-1) 空位罚分公式 Wx 为总空位记分，g为空位开放罚分，r为空位扩展罚分，x为空位长度
A T G T T A T A C T A T G T G C G T A T A 总分：4 匹配= 1 错配= 0 T A T G T G C G T A T A insertion / deletion A T G T T A T A C 空位参数: g= 3 (空位开放罚分) r = 0.1 (空位扩展罚分) x = 3 (空位长度) Wx= -3 - (3 -1) 0.1 = -3.2 总分： = 4.8

21 双序列比对方法 点阵序列比较(Dot Matrix Sequence Comparison)
动态规划算法(Dynamic Programming Algorithm) 词或K串方法(Word or K-tuple Methods) 贝叶斯统计方法(Bayesian Statistical Methods)

22 点阵序列比较(Dot Matrix Sequence Comparison)
点阵分析是一种简单的图形显示序列相似性的方法,Gibbs&McIntyre(1970) 沿X轴上序列1中的每一个单元（核苷酸或氨基酸）与沿Y轴的第二个序列中的每一个单元进行比较，相同的区域在点阵图中显示为由点组成的对角线，对角线之外零散的点为背景噪音

23 I O N Z A T

24 点阵分析中的插入或删除 T A C G T A C T G T T C A T T A C T G - T C A T
Sequence 2 T A C G T A C T G T T C A T 插入空位 Sequence 1 T A C T G - T C A T | | | | | | | | | T A C T G T T C A T

25 点阵分析的应用 自身比对 对两条序列的相似性作整体的估计 寻找序列中的正向或反向重复序列 蛋白质的重复结构域(domain)
相同残基重复出现的低复杂区(Low Complexity) RNA二级结构中的互补区域等 对两条序列的相似性作整体的估计

26 点阵分析的应用 正向重复 自身比对发现 正向重复序列 具有连续相似区域的两条 DNA序列的简单点阵图

27 点阵分析实例 编码噬菌体λcⅠ（水平轴）和噬菌体P22 c2（垂直轴）的氨基酸序列间的点阵分析 相同的点全部打印，很难找到有用的信息

28 使用滑动窗口技术降低噪声 T A C G G T A T G Window=3 Word Size = 3 A C A G T A T C
C T A T  G A C A T A C G G T A T G T A C G G T A T G A C A G T A T C T A C G G T A T G A C A G T A T C T A C G G T A T G A C A G T A T C 

29 使用滑动窗口技术降低噪声 a b （a）对人类（Homo sapiens）与黑猩猩（Pongo pygmaeus）的β球蛋白基因序列进行比较的完整点阵图 （b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸， 　　 相似度阈值为8，即10个核苷酸中有8个相同时就打一个点

30 点阵分析的优缺点 优点 直观性，整体性 点阵分析不依赖空位(gap)参数，可寻找两序列间所有可能的残基匹配
不依赖任何先决条件，是一种可用于初步分析的理想工具 点阵分析允许随时动态地改变最高和最低界限值，可以用来摸索区分信号和背景标准的严格程度

31 点阵分析的优缺点 缺点 不能很好地兼容距离矩阵 滑动窗口和阈值的选择过于经验化 信噪比较低 不适合进行高通量的数据分析

32 点阵分析程序 DNA Strider (Macintosh) http://www.cellbiol.com/soft.htm
Dotter (Unix/Linux, X-Windows) COMPARE, DOTPLOT in GCG PLALIGN (FASTA) Dotlet

33

34 动态规划算法 动态规划算法(Dynamic Programming Algorithm)是综合运用分级决策方法和最优化原理而形成的数学方法。
主要思路是把一个复杂问题分成若干个关联的子问题，找出子问题的最优解，进而得出原来复杂问题的最优解。

35 动态规划算法 在序列比对尤其是双序列比对中非常重要。将比对过程分为若干步，每一步增加一个位置。可提供序列间最优的对位排列。
应用最多的两种动态规划算法： Needleman-Wunsch（全局比对） Smith-Waterman（局部比对）

36 动态规划算法 确定递归计算方法 构建矩阵 填充矩阵 矩阵回溯

37 动态规划算法的简单描述 序列a 序列 b

38 动态规划算法的正式表述 Si,j这个位置的分数为图中箭头所示三个方向值中最大的一个 i -x i -1 j -1 i -y j i
Si - x,j - wx Si –1, j s(ai , bj) Si, j - y - wy Si, j Si,j这个位置的分数为图中箭头所示三个方向值中最大的一个

39 动态规划算法的数学形式 公式一的简化 Sij=max{Si-1,j-1,+s(aibj)} , max x≥1 (Si-x,j-wx), max y ≥ 1 (Si,j-y-wy) Sij=max{Si-1,j-1,+s(aibj)} , max x≥1 (Si-1,j-w), max y ≥ 1 (Si,j-1-w) 公式一 公式二 说明：Sij是序列a在位置i和序列b在位置j的分值，s(aibj)是位置i和j上比对分值，wx是在序列a 中长度为x的空位罚分，wy是序列b中长度为y的空位罚分。

40 动态规划算法举例 (Needleman-Wunsch算法)
例:用动态规划算法比对以下两条序列 序列a: ACTTCG 序列b: ACTAG 记分规则: 匹配＝3 错配＝-2 空位＝-2

41 Scoring Matrix A C T G

42 Scoring Matrix A C T G

43 Scoring Matrix A C T G -2

44 Scoring Matrix A C T G -2 -4 -6 -8 -10 -12

45 Scoring Matrix A C T G -2 -4 -6 -8 -10 -12

46 Scoring Matrix A C T G -2 -4 -6 -8 -10 -12 3

47 Scoring Matrix A C T G A C T - T C A G 回溯 -2 -4 -6 -8 -10 -12 3 1 -1
-2 -4 -6 -8 -10 -12 3 1 -1 -3 -5 -7 6 4 2 9 7 5 8 A C T - T 回溯 C A G

48 回溯(backtracking) 当完成所有矩阵单元的分值计算后，接下来就是从高分值单元开始找出最大分值路径，也就是找出最佳匹配。这个过程被称为回溯(backtracking)。 由于在计算过程中到达每一个矩阵单元的最优路径都被储存在回溯矩阵中，所以就可以方便地找出最优路径（红色箭头表示最优路径）。

49 Scoring Matrix A C T G A C T T - C A G 什么是第三种可能？ -2 -4 -6 -8 -10 -12 3
-2 -4 -6 -8 -10 -12 3 1 -1 -3 -5 -7 6 4 2 9 7 5 8 A C 什么是第三种可能？ T T - C A G

50 Scoring Matrix A C T G A C T T A C - G -2 -4 -6 -8 -10 -12 3 1 -1 -3
-2 -4 -6 -8 -10 -12 3 1 -1 -3 -5 -7 6 4 2 9 7 5 8 A C T T A C - G

51 Smith-Waterman算法 Needleman－Wunsch算法适用于整体水平上相似性程度较高的两个序列。
如果两个序列的亲缘关系较远，它们在整体上可能不具有相似性，但在一些较小的区域上却可能存在局部相似性。 1981年Smith和Waterman提出了一种用来寻找并比较这些具有局部相似性区域的方法，即常用的Smith-Waterman算法 同样是基于矩阵的方法，而且也同样是运用回溯法建立允许空位插入的比对，不同之处在于Smith-Waterman算法要从任何可能导致最大分值的地方才开始计分，矩阵中的每个单元均可以是比对结果序列片段的终点

52 Smith-Waterman算法 Smith-Waterman算法记分矩阵的两个关键点: 1.记分系统必须包括错配的负分值
2.当记分为负时,此值设为0,其作用是使任何比对都在那一点终止 从这一算法的本身可以看出，它属于局部相似性比对，而不是整体相似性比对。

53 Smith-Waterman算法 Sij=max{Si-1,j-1,+s(aibj)} , max x≥1 (Si-1,j-w),
max y ≥ 1 (Si,j-1-w) max 0

54 谢谢！