序列分析PPT学习教案

1、会计学1序列分析序列分析第1页/共94页第2页/共94页直向同源（a1 in species I, a1 in species II)共生同源（a1 and a2 in species I）进化趋同进化趋同水平转移水平转移基因复制基因复制第3页/共94页第4页/共94页设有两个序列：GACGGATTAG，GATCGGAATAGAlignment2: GA CGGATTAGGATCGGAATAGAlignment1:GACGGATTAG GATCGGAATAG第5页/共94页第6页/共94页符 号含 义说 明GGGuanine AAAdenine TTThymine CCCytosineRG o

2、r APurine YT or CPyrimidine MA or CAmino KG or TKeto SG or CStrong interaction (3 H bonds) WA or TWeak interaction (2 H bonds) HA or C or TNot-GBG or T or Cnot-AVG or C or Anot-T(not-U) DG or A or Tnot-C NG or A or T or CAny 扩展的遗传学字母表或IUPAC编码第7页/共94页第8页/共94页ni:s:|s|suffix(s, |s|-i+1) 第9页/共94页第10页/共9

3、4页第11页/共94页第12页/共94页第13页/共94页GCATGACGAATCAG TATGACAAACAGC GCATGACGAATCAG TATGAC-AAACAGC 说明两条序列的相似程度说明两条序列的相似程度 定量计定量计算算 第14页/共94页第15页/共94页直接距离计算的不足直接距离计算的不足第16页/共94页ACCGACAATATGCATA ACTGACAATATGGATA 第二条序列头尾颠倒CTAGTCGAGGCAATCTGAACAGCTTCGTTAGT ？第17页/共94页反向互补序列反向互补序列RNA发夹式二级结构发夹式二级结构第18页/共94页第19页/共94页第2

4、0页/共94页第21页/共94页 序列序列1 序列序列2 实实 例例第22页/共94页 序列序列1 序列序列1 自我比自我比较较第23页/共94页滑动窗口技术滑动窗口技术两条序列中有很多匹配的字符对，因而在点矩阵两条序列中有很多匹配的字符对，因而在点矩阵中会形成很多点标记。中会形成很多点标记。第24页/共94页滑动窗口技术滑动窗口技术 使用滑动窗口代替一次一个位点的比较是解决使用滑动窗口代替一次一个位点的比较是解决这个问题的有效方法。这个问题的有效方法。 假设窗口大小为假设窗口大小为10，相似度阈值为，相似度阈值为8，则每次比，则每次比较取较取10个连续的字符，如相同的字符超过个连续的字符，如

5、相同的字符超过8个，个，则标记则标记 基于滑动窗口的点矩阵方法可以明显地降低点基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声，并且明确无误的指示出了两条序列阵图的噪声，并且明确无误的指示出了两条序列间具有显著相似性的区域。间具有显著相似性的区域。 第25页/共94页（a）对人类（）对人类（Homo sapiens）与黑猩猩（）与黑猩猩（Pongo pygmaeus）的）的球蛋白基因序列进行比较的完整点阵图。（球蛋白基因序列进行比较的完整点阵图。（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为

6、10个核苷酸，相似度阈值为个核苷酸，相似度阈值为8。 (a) (b) 第26页/共94页具有连续相似区域的两条具有连续相似区域的两条DNA序列的简单点阵图序列的简单点阵图第27页/共94页第28页/共94页 s:AGCACACAAGCACACA t:ACACACTAACACACTA Match(A, A)Match(A, A)Delete(G, - )Replace(G, C)Match(C, C)Insert( -, A)Match(A, A)Match(C, C)Match(C, C)Match(A, A)Match(A, A)Match(C, C)Match(C, C)Replace(A

7、, T)Insert( -, T)Delete(C, -)Match(A, A)Match(A, A)图3.6 序列AGCACACA和ACACACTA的两种比对结果Alignment -1 Alignment -2第29页/共94页第30页/共94页第31页/共94页最优时的距离。最优时的距离。第32页/共94页第33页/共94页ATCGA1000T0100C0010G0001ATCGA5-4-4-4T-45-4-4C-4-45-4G-4-4-45ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51表3.1 等价矩阵表表3.3 转移矩阵表3.2 BLAST矩阵第34页/共9

8、4页jijiRij01其中Rij代表打分矩阵元素i、j分别代表字母表第i和第j个字符。第35页/共94页第36页/共94页第37页/共94页PAM矩阵（矩阵（Point Accepted Mutation） 基于进化的点突变模型基于进化的点突变模型 一个一个PAM就是一个进化的变异单位就是一个进化的变异单位, 即即1%的氨基酸改变的氨基酸改变 这类矩阵里列出同源蛋白质在进化过程中氨基酸变化的可能性。这类矩阵里列出同源蛋白质在进化过程中氨基酸变化的可能性。 这类矩阵式基于进化原理的这类矩阵式基于进化原理的 证据：证据： 编码相同蛋白质的基因随着进化发生分歧，相似度降低。编码相同蛋白质的基因随着进

9、化发生分歧，相似度降低。 科学科学 用得多用得多 第38页/共94页矩阵集合矩阵集合- PAM-N如，如，PAM120矩阵用于比较相距矩阵用于比较相距120个个PAM单位的序列单位的序列。一个一个PAM-N矩阵矩阵元素（元素（i，j）的值：的值： 反应两个相距反应两个相距N个个PAM单位的序列中第单位的序列中第i种氨基酸种氨基酸替换替换第第j种氨基酸的频率。种氨基酸的频率。第39页/共94页针对不同的进化距离采用针对不同的进化距离采用PAM 矩阵矩阵序列相似度序列相似度 = 40% 50% 60% | | |打分矩阵打分矩阵 = PAM120 PAM80 PAM 60PAM250 14% -

10、27% 第40页/共94页 归一化打分归一化打分实例实例第41页/共94页BLOSUM 62第42页/共94页1、序列两两比对基本算法、序列两两比对基本算法直接方法直接方法 生成两个序列所有可能的比对，分别计算代生成两个序列所有可能的比对，分别计算代价函数，然后挑选一个代价最小的比对作为最终结果。价函数，然后挑选一个代价最小的比对作为最终结果。本质问题：优化本质问题：优化动态规划寻优策略动态规划寻优策略动态规划算法（动态规划算法（Dynamic Programming）第43页/共94页最短路经问题最短路经问题起起点点终点终点C1 C2 W1 W2路径1：C1 + w1 ？路径2：C2 + w

11、2 ？ 取最小值！取最小值！算法求解算法求解: 从起点到终点逐层计算从起点到终点逐层计算第44页/共94页利用动态规划方法求解序列的两两比对利用动态规划方法求解序列的两两比对起起点点终点终点ATTCCGAAGA AGTCGAAGGTATTCCGAAG AGTCGAAGGAT+（1）ATTCCGAAGA AGTCGAAGG-T+（2）ATTCCGAAG AGTCGAAGGTA-+（3）第45页/共94页求解过程求解过程起起点点终点终点ATTCCGAAGA AGTCGAAGGT 从两个序列前端开始从两个序列前端开始 逐步推进逐步推进 直到两个序列的末端。直到两个序列的末端。第46页/共94页序列S

12、: i-1 i i+1序列t: j-1 j j+1序列S: i-1 i i+1序列t: j-1 j j+1Case1:匹配（si，tj )中间过程：比对中间过程：比对0:S:i 与与 0:T:j 第47页/共94页序列S: i-1 i i+1序列t: j-1 j j+1序列S: i-1 i i+1序列t: j-1 j j+1Case2:删除（si， -） 第48页/共94页序列S: i-1 i i+1序列t: j-1 j j+1序列S: i-1 i i+1序列t: j-1 j j+1Case3:插入（ -，tj ） 第49页/共94页设序列设序列s、t的长度分别为的长度分别为m和和n。考虑两个

13、前缀考虑两个前缀 0:s:i 0:t:j 假如已知序列假如已知序列0:s:i 和和0:t:j 所有较短子列的最优比对，即已知：所有较短子列的最优比对，即已知：（1）0:s:(i-1) 和和 0:t:(j-1) 的最优比对的最优比对（2） 0:s:(i-1) 和和 0:t:j 的最优比对的最优比对（3） 0:s:i 和和 0:t:(j-1) 的最优比对的最优比对则则0:s:i和和 0:t:j 的最优比对一定是上述三种情况之一的扩展的最优比对一定是上述三种情况之一的扩展（1）替换（）替换（si，tj）或匹配（）或匹配（si，tj ) ，这取决于，这取决于si 是否等于是否等于tj ；（2）删除（）

14、删除（si， -）；）；（3）插入（）插入（ -，tj ）。）。 第50页/共94页):, :(00jitsS令：令：为序列为序列0:s:i和与序列和与序列 0:t:j 比对的得分比对的得分按下述方法求解按下述方法求解 第51页/共94页其初值为：其初值为：for i=1 , 2 ,., mfor j=1 , 2 ,., n),():, :(),():,:(),():,:(max):, :()1(000)1(0)1(0)1(000jjiijijijijitptsSsptsStsptsStsS),():,:():,:(),():,:():, :(0):,:()1(00000000)1(00000

15、000jjjiiitptsStsSsptsStsStsS第52页/共94页距离矩阵距离矩阵按照上述方法，对于给定的得分函数按照上述方法，对于给定的得分函数p，两个序列所有前缀的得分定义了一个两个序列所有前缀的得分定义了一个(m+1) (n+1)的距离矩阵的距离矩阵D = ( d i , j )其中其中d i , j = S (0:s:i , 0:t:j ) d i , j的计算公式如下：的计算公式如下：),(),(),(max1, 11, 1,jjiijijijijitpdspdtspdd第53页/共94页d i , j 最小值的三种选择决定了各矩阵元素之间的关系，最小值的三种选择决定了各矩阵

16、元素之间的关系，用下图表示：用下图表示：di,jdi,j-1di-1,jdi-1,j-1 距离矩阵元素d i , j 的计算S (0:s:i , 0:t:j )S (0:s:i-1 , 0:t:j )S (0:s:i-1 , 0:t:j-1 )S (0:s:i , 0:t:j-1 )第54页/共94页动态规划算法计算过程：动态规划算法计算过程： 计算过程从计算过程从d 0 , 0开始开始 可以是按行计算，每行从左到右，也可以是按列计算，每可以是按行计算，每行从左到右，也可以是按列计算，每列从上到下。列从上到下。 当然，任何计算过程，只要满足在计算当然，任何计算过程，只要满足在计算d i , j

17、时时 d i-1 , j、d i-1 , j-1、和、和d i, j-1都已经被计算这个条件即可。都已经被计算这个条件即可。 在计算在计算d i , j后，需要保存后，需要保存d i , j是从是从d i-1 , j、d i-1 , j-1、或、或d i, j-1中的哪一个推进的，或保存计算的路径，以便于后续处理中的哪一个推进的，或保存计算的路径，以便于后续处理。上述计算过程到上述计算过程到d m , n结束。结束。 第55页/共94页最优路径求解：最优路径求解：与计算过程相反与计算过程相反 从从d m , n开始，反向前推。开始，反向前推。 假设在反推时到达假设在反推时到达d i ,j，根据

18、保存的计算路径判，根据保存的计算路径判断断d i , j究竟是根据究竟是根据d i-1 , j、d i-1 , j-1、和、和d i, j-1中的那一中的那一个计算而得到的。找到这个点以后，再从此点出发个计算而得到的。找到这个点以后，再从此点出发，一直到，一直到d 0 , 0为止。为止。 走过的这条路径就是最优路径（即代价最小路径走过的这条路径就是最优路径（即代价最小路径），其对应于两个序列的最优比对。），其对应于两个序列的最优比对。 第56页/共94页计算过程：计算过程：（1）初始化）初始化第57页/共94页计算过程：计算过程：（2）反复计）反复计算算按列计算按列计算第58页/共94页计算过

19、程：计算过程：（2）反复计）反复计算算按行计算按行计算其他方式其他方式第59页/共94页计算过程：计算过程：（3）求最佳路径）求最佳路径第60页/共94页t ts s ACACACTAAGCACACA例：例：s = AGCACACAt = ACACACTA 得分矩阵得分矩阵D （99 9）第61页/共94页t ts s ACACACTA0-1-2-3-4-5-6-7-8A-1G-2C-3A-4C-5A-6C-7A-8初始化初始化第62页/共94页计算计算d（2，2）t ts s ACACACTA0-1-2-3-4-5-6-7-8A-110-1-2-3-4-5-6G-201C-3A-4C-5A-

20、6C-7A-8第63页/共94页最终的得分矩最终的得分矩阵阵及序列比对及序列比对t ts s ACACACTA0-1-2-3-4-5-6-7-8A-110-1-2-3-4-5-6G-2010-1-2-3-4-5C-3-11110-1-2-3A-4-2021210-1C-5-3-1132321A-6-4-2024333C-7-5-3-113543A-8-6-4-202455AGCACAC A| | |A CACACTA第64页/共94页序列长度的影响序列长度的影响：令令cw(s, t) 表示两个长度分别为表示两个长度分别为m和和n的序列的相似性得分的序列的相似性得分设设cw(s, t) = 99

21、如果如果 m=n=100 - 则可以说这两个序列非常相似则可以说这两个序列非常相似但如果但如果m=n=1000，则仅有，则仅有10% 相同相同相对长度的得分相对长度的得分sim（s，t）= 2*cw(s, t) /(m+n) 算法分析：算法分析：数据结构数据结构d i , j空间复杂度：空间复杂度：O (mn)时间复杂度：时间复杂度：O (mn)第65页/共94页第66页/共94页序列S:序列t: i j不计前缀0:t:i 的得分, 也不计删除后缀的j+1:t:|t|得分第67页/共94页不计前缀不计前缀0:t:i 的得分的得分处理第一行处理第一行t ts s ACACACTA00000000

22、0AGCACACA0):,:(000itsS第68页/共94页不计删除后缀的不计删除后缀的j+1:t:|t|得分得分 处理最后一行处理最后一行):,:(),():,:(),():,:(max):,:()1(000)1(0)1(0)1(000jmmjmjmjmjmtsSsptsStsptsStsS第69页/共94页dm,jdm,j-1dm-1,jdm-1,j-1S (0:s:i , 0:t:j )S (0:s:i-1 , 0:t:j )S (0:s:i-1 , 0:t:j-1 )S (0:s:i , 0:t:j-1 )不计代价不计代价第70页/共94页距离矩阵初始化时，对第一行进行如下处理：距离

23、矩阵初始化时，对第一行进行如下处理：d0,j = 0 for 0 j n 最后一行的计算应该是：最后一行的计算应该是：同样，同样，d m, n依然是最优局部比对的得分，而匹配的子列依然是最优局部比对的得分，而匹配的子列i:t:j 按如下方式寻找：按如下方式寻找： （1） j = min k d m ,k = d m ,n （2）反推比对路径，最终通过斜线（非空位）到达（）反推比对路径，最终通过斜线（非空位）到达（0，i）。）。 （3-10）（3-11） 1, 11, 1,),(),(maxjmmjmjmjmjmdspdtspdd第71页/共94页序列S:序列t: i ji j第72页/共94页

24、第73页/共94页(3-13)0),(),(),(max1, 11, 1,jjiijijijijitpdspdtspdd第74页/共94页第75页/共94页TATA|TATA第76页/共94页序列序列1 长度为长度为8序列序列2 长度为长度为18（a）6个匹配，个匹配，1个失配，个失配，1个空位个空位 （b）8个匹配个匹配第77页/共94页jmnjdtssim,1max),(3-14)序列S:序列t: i ji j空位后缀第78页/共94页序列S:序列t: i ji j空位前缀第79页/共94页第80页/共94页ACACTGATCG|ACACTG第81页/共94页第82页/共94页第83页/共94页为比较序列s（长度为m）和序列t（长度为n），我们使用三个（m+1）（n+1）的矩阵 各矩阵第一行和第一列初始值的设定如下： )()(00,00,0iwcjwbaij （3-16）（3-17）（3-18） 递归计算过程如下： )()(max)()(maxmax),(,1, 11, 11, 1,kwbkwackwckwabcbajipajkijkijikjikjijijijijiji (3-20) for 1 k jfor 1 k jfor 1 k ifor 1 k i(3-19) (3-21)第84页/共94页上述算法