chap3_序列比对2

《chap3_序列比对2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、序列比对（二）2012/9/16HuizhiZhao内容序列比对比对算法扩展数据库搜索序列比对动态规划算法最优子结构重叠子问题备忘录方法序列比对打分矩阵初始状态状态转换序列比对问题分解图3.1比对问题AGCAAACAGAAACC-AGCAAA-CAGAAACCAAAACG-AGAAA-GAAAAGCAGAAAC-AGCAA-AAGAACAAAAAG-AGAA-AAAAGA序列比对问题分解状态转移计算：Sim(s[1...i],t[1...j])为序列s[1..i]和t[1...j]的相似度量打分矩阵-ATCG-0-2-2-2-2A-21-1-1-1T-2-11-1-1

2、C-2-1-11-1G-2-1-1-11序列对比计算0AGC00(-,-)-2(-,A)-4(--,AG)-6(---,AGC)A-2(A,-)1(A,A)-1(A,AG)-3(A,AGC)A-4(AA,--)-1(AA,A)0(AA,AG)-2(AA,AGC)A-6(AAA,---)-3(AAA,A)-2(AAA,AG)-1(AAA,AGC)C-8(AAAC,----)-5(AAAC,A)-4(AAAC,AG)-1(AAAC,AGC)→sim(A,-)+sim(-,A)-4↓sim(-,A)+sim(A,-)-4↘sim(-,-)+sim(A,A)1→sim(A,A

3、)+sim(-,G)-1↓sim(-,AG)+sim(A,-)-6↘sim(-,A)+sim(A,G)-3→sim(A,AG)+sim(-,C)-3↓sim(-,C)+sim(A,C)-7↘sim(-,AG)+sim(A,C)-5→sim(AA,-)+sim(-,A)-6↓sim(A,A)+sim(A,-)-1↘sim(A,-)+sim(A,A)-1→sim(AAA,-)+sim(-,A)-8↓sim(AA,A)+sim(A,-)-3↘sim(AA,-)+sim(A,A)-5→sim(AAAC,-)+sim(-,A)-10↓sim(AAA,A)+sim(C,-)-5↘

4、sim(AAA,-)+sim(A,C)-7序列比对结果AAAC/-AGC序列比对结果AAAC-/-AG-C序列比对结果AAAC/AG-CAAAC/A-GC序列比对算法a[i,j]是s(1...i)和t(1...j)的打分值A(m+1,n+1)的矩阵时间复杂度O(mn)习题2问题：图3.1在新计分矩阵下的比对-ATCG-0-1-1-1-1A-11000T-10100C-10010G-100010AGC00-1-2-3A-110-1A-2010A-3-101C-4-2-11比对结果AAAC/-AGCAAAC/A-GCAAAC/AG-C0-1-2-3-110-1-2010-

5、3-101-4-2-110AGC0AAACLCS计分系统-ATCG-00000A01-2-2-2T0-21-2-2C0-2-21-2G0-2-2-210AGC00000A0100A0111A0111C0112习题5问题：在上两个计分系统下，两个序列的优化比对不同ACGTC/AGCGC在（-2,-1,1)计分系统下：A-CGTC/AGCG-C在（-1,0,1）计分系统下：ACGTC/AGCGC，A-CGTC/AGCG-C习题50ACGTC00-2-4-6-8-10A-21-1-3-5-7G-4-100-2-4C-6-30-1-1-1G-8-5-21-1-2C-10-7-

6、4-1000ACGTC00-1-2-3-4-5A-110-1-2-3G-20110-1C-3-11111G-4-20211C-5-3-1022(-2,-1,1)(-1,0,1)局部比对子串之间的比对得分可能高于整个字符串的比对得分从最高得分倒推AGC/AAC0000000100000AGC0AAAC00101001习题6(-2,-1,1):ACGGAGG/ACGTAGG0ATACTACGGAGGG000000000000000G00000000110111A01010010001000A01010010001000C00002002000000G00000000310

7、111T00100100020000A01020020003100G00000001011421G00000000210253C00001001010014G00000000200112T00100100000000A01020020001000T00200101000000半全局比对终端空格不计分原则空格不计分位置动作列序列的起始用0初始化第一行列序列的终端在最后一行寻找最大值行序列的起始用0初始化第一列行序列的终端在最后一列寻找最大值半全局匹配TGACT-/--ACTG0TGACT0000000A-2-1-11-1-1C-4-3-2-120T-6