PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

纶醒禄
5 years ago
Views:

1 生物信息学第三章序列比对 I

2 为什么要序列比对? 寻找进化过程中的同源序列 ; 基于同源物鉴定的功能预测 ; 基本假设 : 序列的保守性通常功能的保守性注意 : 蛋白质一般在三级结构的层面上执行功能 ; 蛋白质序列的保守性决定于其编码 DNA 的保守性 ;

3 序列间比对的对应关系 Match (a,a): 匹配 Replace (a,b) : 替代 Delete (a,-) : 缺失 Insert (-,b) : 插入 PKDFC-ALV PK-FCKAIV

4 序列比对工具的开发 1970 年,Gibbs AJ 和 McIntyre GA, 点阵法进行氨基酸和核酸的序列比较 : 当相同的字母在两条序列中同时出现时, 在交叉处置点 1970 年,Needleman-Wunsch, 全局优化的序列比对算法 : 允许匹配错配和缺失动态规划的算法 : 任务可分割, 分成更小的子问题进行解决 1981 年,Smith-Waterman, 局部优化的序列比对算法 FASTA & BLAST 的开发, 启发式优化算法多序列比对 :CLustalW/X, POA, MUSCLE.

5 序列比对的全局优化 vs. 局部优化 ACTGTTCCGAA 100kbp AGCCTGA 100kbp ACTACTG ACGCCTG 全局优化 ACTGTTCCGAA 100kbp AGCCTGA 100kbp ACTACTG AC GCC TG 局部优化 ACTGTTCCGAA 100kbp A-GCCTGA 100kbp ACTACTG ACGCCTG

6 序列比对模型分类全局比对从全局序列出发, 考虑序列的整体相似性 ; 局部比对考虑序列部分区域的相似性 ; 生物学基础 : 蛋白质功能位点往往是由较短的序列片段组成, 具有相当大的保守性 ; 局部比对往往比全局比对具有更高的灵敏度, 其结果更具生物学意义

7 本章内容提要第一节 : 双序列比对算法 Dot matrix 动态规划算法 Needleman-Wunsch 算法 Smith-Waterman 算法 FASTA 和 BLAST 算法第二节 : 打分矩阵及其含义第三节 : 多序列比对

8 第一节, 双序列比对算法 1. Dot Matrix, 点阵法 2. 动态规划算法 : Global: Needleman-Wunsch Local: Smith-Waterman 3. Word or k-tuple 算法 :FASTA, BLAST

9 1, 点阵法 1970 年,Gibbs & McIntyre; 寻找两条序列间所有可能的比对 ; 发现蛋白质或者 DNA 序列上正向或者反向的重复 ; 发现 RNA 上可能存在的互补区域工具 :

10 两条 DNA 序列的点阵法比较 AGCTAGGA GACTAGGC

点阵法 : 自身的比对 A K G F K C A D E A 1 0 0 0 0 0 1 0 0 K 1 0 0 1 0 0 0 0

11 点阵法 : 自身的比对 A K G F K C A D E A K G F K C A D 1 0 E 1

12 点阵法 : 重复序列 A K G F D K G F E A K G F D K G F E 1

13 点阵法 : 自身反向对称的序列 A U G C A C G U A A U G C A C G U A 1 1

点阵法 : 不同序列的比对 Seq 1 Seq2 P K D F C K A L V P 1 0 0 0 0 0 0 0 0 K 1 0 0 0 1 0 0 0

14 点阵法 : 不同序列的比对 Seq 1 Seq2 P K D F C K A L V P K F T K A I 0 0 V 0 1 1:PKDFCKALV 2:PK-FTKAIV

15 点阵法的序列比对 Sequence 1# Sequence 2# 1 1 n - Delete - Delete m

16 计算效率用 CPU 的计算时间和内存占用量来衡量 ; 对于需要解决的问题, 其单位数量 n 在某算法下运算的基本操作重复执行次数表示为 f(n); 时间复杂度 : T(n)=O(f(n)); 如果需要解决的问题的大小与单位数量 n 的平方成正比, 则 O(n 2 ) 对于算法来说 : O(1) < O(log(n)) < O(n) < O(n 2 ) < O(a n ) < O(n!)

17 P/NP 问题 - 千禧年大奖难题之一 1900 年, 德国数学家 David Hilbert 提出的 23 个历史性数学难题千禧年大奖难题 : 美国克雷数学研究所 (Clay Mathematics Institute,CMI) 于 2000 年 5 月公布七个世界数学难题千禧年大奖难题 : P/NP 问题 :P = NP? 霍奇猜想庞加莱猜想 ( 已证明 ) 黎曼猜想杨 - 米尔斯存在性与质量间隙纳维 - 斯托克斯存在性与光滑性贝赫和斯维讷通 - 戴尔猜想

18 P/NP/NPC 问题 P 问题 : Polynomial Problems 可以在多项式 ( polynomial ) 时间内解决的问题 ; NP: Non-deterministic Polynomial 多项式复杂程度的非确定性问题可以在多项式的时间里验证一个解 NPC: NP-complete 最不可能被化简为 P ( 多项式时间可决定 ) 的决定性问题的集合

19 NP 问题多项式时间 :O(n k ), k 3;O(n lg n) 较为容易处理非多项式时间 :O(a n ),O(n n ),O(n!) 解决途径 : 近似算法 / 优化算法, 求近似解

20 点阵法的时间复杂度 1 1 n O(n)=mn=n 2 m

2, 动态规划算法打分模型替代矩阵以及空位罚分动态规划算法在双序列比对中的应用 : 全局优化比对 Needleman-Wunsch 算法 http://zhanglab.ccmb.med.umich.edu/nw-align/ http://snippets.dzone.

21 2, 动态规划算法打分模型替代矩阵以及空位罚分动态规划算法在双序列比对中的应用 : 全局优化比对 Needleman-Wunsch 算法局部优化比对 Smith-Waterman 算法 N.W. & S.W. 算法 :

22 打分模型字符相同 :identity 字符替代 :similarity, 相似性氨基酸 / 碱基之间的替代和突变插入和缺失 : 空位罚分

23 BLOSUM62 替代矩阵

24 空位罚分线性罚分 :d, 每次罚分的分数 ;g, 空位数 r( g) gd 修正的罚分 :d, 第一次罚分的分数 ; g, 空位数 ;e, 修正后的参数 r ( g) d ( g 1) e

25 时间复杂度两条序列的比较, 无空位 : 时间复杂度为 O(n 2 ); 两条序列比对, 允许空位, 时间复杂度为 : 2n n (2n)! ( n!) 2 2 2n n 因此, 有空位的双序列比对, 时间复杂度为 : O(2 2n ), 指数增加!

26 递归和动态规划算法数学上保证提供最优解序列比对中最精确最基本的算法比较所有可能的字符对, 考虑匹配错配以及空位罚分替代矩阵 :BLOSUM62, 空位罚分 :11 延伸的空位罚分 :1 (BLAST 工具 )

27 递归和动态规划算法动态规划的基本思想是递归分解和解决重复动态规划是一种将问题实例分解为更小的相似的子问题, 并存储子问题的解而避免重复计算, 以解决最优化问题的算法策略动态规划法所针对的问题有一个显著的特征, 即它所对应的子问题树中的子问题呈现大量的重复动态规划法的关键就在于, 对于重复出现的子问题, 只在第一次遇到时加以求解, 并把答案保存起来, 让以后再遇到时直接引用, 不必重新求解

28 Needleman-Wunsch 算法 S ij = max of S i-1,j-1 + σ(x i, y j ) S i-1,j - d ( 从上到下 ) S i,j-1 - d ( 从左到右 )

29 例 1:Needleman-Wunsch 算法进行双序列全局比对两条序列如下 : V D S C Y V E S L C Y 目标 : 使用全局优化算法寻找比对的结果本例中 :gap: d=11, 线性罚分模型

30 Needleman-Wunsch 算法 Gap V D S C Y Gap 0 1gap 2gap V 1gap E 2gap S L C Y 本例 : 线性罚分 r( g) - - V.. V E S L C Y V.. V E S - L C Y gd

31 Needleman-Wunsch 算法 Gap V D S C Y Gap V -11 S ij E -22 S -33 L -44 C -55 Y -66 要求解 S ij 的分数, 我们必须先知道 S i-1, j-1, S i-1, j, 以及 S i, j-1 的分数, 这种方法叫做递归算法 ; 采用这种方法, 可以把大的问题分割成小的问题逐一解决, 即动态规划算法 ; 需要存储如何得到 S ij 分数的过程

32 Needleman-Wunsch 算法 i j Gap V D S C Y Gap V -11 S ij E -22 S -33 L -44 C -55 Y -66 Needleman-Wunsch 算法 ; S ij = max of S i-1, j-1 + σ(x i, y j ) S i-1, j - d ( 从上到下 ) S i, j-1 - d ( 从左到右 )

33 BLOSUM62 替代矩阵

34 Needleman-Wunsch 算法 j i Gap V D S C Y Gap V -11 S ij E -22 S -33 L -44 C -55 Y Needleman-Wunsch 算法 ; S ij = max of S i-1, j-1 + σ(x i, y j ) S i-1, j - d ( 从上到下 ) S i, j-1 - d ( 从左到右 )

35 Needleman-Wunsch 算法 Gap V D S C Y Gap V E -22 S -33 L -44 C -55 Y

36 Needleman-Wunsch 算法 Gap V D S C Y Gap V S ij E -22 S -33 L -44 C -55 Y Needleman-Wunsch 算法 ; S ij = max of S i-1, j-1 + σ(x i, y j ) S i-1, j - d ( 从上到下 ) S i, j-1 - d ( 从左到右 )

37 Needleman-Wunsch 算法 Gap V D S C Y Gap V E -22 S -33 L -44 C -55 Y

38 Needleman-Wunsch 算法 Gap V D S C Y Gap V E S L ? C ? Y

39 回溯比对结果 V D S C Y V E S L C Y Gap V D S C Y Gap V E S L C Y

例 1: 比对结果得分序列 1: V D S C Y 序列 2: V E S L C Y 替代矩阵中的分数 : 4 2

40 例 1: 比对结果得分序列 1: V D S C Y 序列 2: V E S L C Y 替代矩阵中的分数 : 两序列比对的总分 : Score=Σ(AA pair scores) gap penalty = 15

42 Smith-Waterman 算法 S ij = max of 0 S i-1,j-1 + σ(x i, y j ) S i-1,j - d ( 从上到下 ) S i,j-1 - d ( 从左到右 )

43 例 2: Smith-Waterman 算法进行双序列局部比对两条序列如下 : L D S C H G E S L C K 目标 : 使用局部优化算法寻找比对的结果本例中 :gap: d=5, 线性罚分模型

44 Smith-Waterman 算法 Gap L D S C H Gap G 0 S ij E 0 S 0 L 0 C 0 K 0 Smith-Waterman 算法 ; S ij = max of S i-1, j-1 + σ(x i, y j ) S i-1, j - d ( 从上到下 ) S i, j-1 - d ( 从左到右 ) 0

45 Smith-Waterman 算法 Gap L D S C H Gap G 0 S ij E 0 S 0 L 0 C 0 K

46 Smith-Waterman 算法 Gap L D S C H Gap G E 0 S 0 L 0 C 0 K

47 Smith-Waterman 算法 Gap L D S C H Gap G E S L C K

48 局部比对结果 : L D S C H G E S L C K Gap L D S C H Gap G E S L C K ?

局部比对结果 : L D S C H G E S L C K Gap L D S C H Gap 0 0 0 0 0 0 G 0 0 0 0 0

49 局部比对结果 : L D S C H G E S L C K Gap L D S C H Gap G E S L C K

50 打分有何不同? L D S C H G E S L C K 局部优化比对 :10 分全局得分 : = 6 局部累计得分 : = 10 为何不同, 相同?

51 emboss/align/

52 3,FASTA 和 BLAST 启发式算法, heuristic algorithm; 不能保证搜索到最优的比对 ; 具有很好的灵敏度, 并且略为降低特异性 ; 大大缩短序列比对的时间 ; k-tup 算法 : 字符串匹配 ; 应用 : 大的数据库搜索 ; 时间复杂度 :< O(n 2 )

53 FASTA 基本思想 : 一个能够揭示出真实的序列关系的比对至少包含一个两个序列都拥有的片段字 (word), 把查询序列中的所用字编成索引, 然后在数据库搜索时查询这些索引, 以检索出可能的匹配, 这样那些命中的字很快被鉴定出来 FASTA 对 DNA 序列搜索的结果要比对蛋白质序列搜索的结果更敏感它对数据库的每一次搜索都只有一个最佳的比对, 一些有意义的比对可能被错过

54 FASTA k-tuple: 蛋白质序列 : 缺省为 2aa;DNA 序列 : 4~6nt. 以短序列 `word` 构建索引, 采用 hash 表存储方式 ; 对于需要比较的两条序列, 在 hash 表中查找所有完全匹配的片段 ;FASTA 给每一个匹配给定一个 tup 值 ; 将同一序列上的高分值区域连接在一起 ; 采用 Needleman-wunsch 或者 Smith-waterman 算法对该高分值区域重新打分

55 K-tup 算法原理 1. 对于两条序列 A, B, 若包含少量 gap, 则最优比对趋近对角线 A 序列长度 m B 序列长度 n 时间复杂度 :O(mn)

56 K-tup 算法原理 B 序列长度 n A 序列长度 m k 令 k 为一常数, 搜索限定区域内的最优比对时间复杂度 :O(kn)

57 K-tup 算法原理 : 缺点 A 序列长度 m B 序列长度 n 仅能搜索到图示的匹配部分 k

58 FASTA: 索引表构建以蛋白质序列为例 ; k=1. 氨基酸 tup 分值 A 5 C 5 K 5 N 5 P 5 R 5 S 5 T 5

59 给定两条蛋白质序列 : Protein1: NCSPTA Protein2: ACSPRK 氨基酸蛋白 1 中位置蛋白 2 中位置 tup 分值 A C K N 1-0 P R S T 5-0

60 给定两条蛋白质序列 : Protein1: NCSPTA Protein2: ACSPRK 氨基酸蛋白 1 中位置蛋白 2 中位置 tup 分值 A C K N 1-0 P R S T 5-0

61 两条序列匹配结果 Protein1: NCSPTA Protein2: ACSPRK

62 FASTA: 序列比对的过程 A. 找出完全匹配的区域 B. 保留分数最高的 10 个匹配 C. 将较好的匹配连接起来 D. 重新用动态规划算法计算最优比对

63 BLAST Basic Local Alignment Search Tool 目前应用最广泛的序列相似性搜索工具, 较 FASTA 有很多改进, 速度更快, 且建立在严格统计学基础之上基本思想 : 通过产生数量更少但质量更高的增强点以提高效率它集中于发现具有较高的相似性的局部比对, 且局部比对中不能含有空位 (blast2.0 引入了允许插入 gap 的算法 )

64 BLAST k-tup: DNA, 11nt; 蛋白质,3aa 蛋白质序列数据库, 构建由 3aa 组成的索引表, 采用 BLOSUM62 矩阵打分 ; 待查询序列, 分解成 3aa 的片段, 在上述数据库中的分值表中进行查询 ; 保留高于域值的结果, 并进行两端的延伸,HSP: high-scoring segment pair; 稍微降低灵敏度, 提高计算速度 ;

65 BLAST: 索引表构建 1. formatdb 命令, 将 fasta 格式的序列文件转换成 blast 能够识别的文件格式 ; 2. 构建索引表 : 建立长度 k=3 的索引表

66 BLAST: word 匹配两边延伸

67 BLAST: 扩展连接为更长片段比对

68 BLAST 程序包程序名查询序列数据库搜索方法 Blastn 核酸核酸用查询序列逐一搜索核酸数据库中的序列 Blastp 蛋白质蛋白质用查询序列逐一搜索蛋白质数据库中的序列 Blastx 核酸 ( 翻译 ) 蛋白质 Tblastn 蛋白质核酸 ( 翻译 ) TBlastx 核酸 ( 翻译 ) 核酸 ( 翻译 ) 将核酸序列翻译成蛋白质序列后逐一搜索蛋白质数据库中的序列用查询蛋白质序列逐一搜索核酸数据库中的核酸序列翻译后的蛋白质序列将核酸序列翻译成蛋白质序列后逐一搜索核酸数据库中的核酸序列翻译后的蛋白质序列

69 BLAST: 发展与改进早期的 BLAST 版本 : 无空位罚分 Gap Penalties: Existence: 11, Extension: 1 PSI-BLAST: Position-Specific Iterated BLAST PHI-BLAST: Pattern Hit Initiated BLAST

70 PSI-BLAST: 位点特异性迭代 BLAST 1. 使用普通的 blast 算法进行搜索 ; 2. 将搜索得到的序列, 包括输入的序列放在一起, 构建位点特异性的矩阵 (Position Specific Matrix); 3. 利用上面得到的矩阵谱 (profile), 再次在数据库中进行搜索 ; 4. 重复 2,3 步, 直到不再有新的序列出现 ; 优点 : 能够发现序列相似性非常低的同源序列 ; 缺点 : 常常得到假阳性的结果

71 PSI-BLAST: 迭代搜索

72 Sequence Profile: Position Specific Scoring Matrix (PSSM) 二十种氨基酸代表每一列矩阵中的数值 :: 当前位置上, 某种, 某种氨基酸出现的频率的 log 值 log 值

73 PHI-BLAST : 模式发现迭代 BLAST 搜索含有的特殊模式的序列 Valid characters for PHI-BLAST patterns: Protein: ABCDEFGHIKLMNPQRSTVWXYZU DNA: ACGT Example: PA [LIVMF]-G-E-x-[GAS]-[LIVM]-x(5,11)-R

Microsoft PowerPoint - chap4-1.ppt [兼容模式]

Microsoft PowerPoint - chap4-1.ppt [兼容模式] 生物信息学第四章双序列比对 (1) 为什么要序列比对基于同源序列鉴定的功能预测基本假设 : 序列的保守性功能的保守性注意 : 蛋白质一般在三级结构的层面上执行功能蛋白质序列的保守性决定于其编码 DNA 的保守性序列同源性模型中的进化假设所有的生物都起源于同一个祖先序列不是随机产生, 而是在进化上, 不断发生着演变基本假设 : 序列保守性结构保守性注意 : 反之可以不为真结构保守性