Bioinformation序列比对制作人:孙振东2018.4.11相似为了清楚两序列之间的相似性，推断序列功能和进化关系，所以要进行序列比
对。功能相似？结构相似？序列比对双序列比对全局比对局部比对多序列比对动态规划算法：通过拆分问题，使得问题能够以递推的方式去解决。思
想：大问题分解为小问题Eg.匹配=1,非匹配=0,空位罚分=-1Sequence1:CACGASequence2:CGA
第一个位点剩余序列得分CACGA+1CGAgapCACGA-1CGACACGA-1gapCGA全局比对也叫Needleman和W
unsch算法，指将参与比对的两条序列里面的所有字符进行比对，用来寻找两者的相似性。使可能的情况能够涉及，允许进行必要的插入或缺失
，但为控制无限的空位插入，我们引进了罚分概念。X:x1,x2,…,xi,…,xnY:y1,y2,…,yj,…,ym两序列间
的最佳比对可以有三种情况1、xi与yj配对2、xi与一个空位配对3、yj与一个空位配对F(0,0)=0F(i,0)=diF(
0,j)=dj①F(i-1,j-1)+s(xi,yj)F(i,j)=max②F(i-1,j)-d③F(i,j-1)-d
j-1jPQXabYc?i-1i序列X:ATTGCGA序列Y:ACTTGG为简化运算，简单规定匹配，错配，空位罚
分的分数匹配加1，错配减1，插空位减1替换记分矩阵序列回溯序列X:A_TTGCGA序列Y:ACTTG_G_ATTGCGA0-1-2
-3-4-5-6-7A-110-1-2-3-4-5C-200-1-2-1-2-3T-3-1110-1-2-3T-4-20210-1
-2G-5-3-113210G-6-4-202232局部比对Smith-Waterman算法，也叫局部比对算法，为了寻找序列中一
些小的、具有局部相似性的片段，而不是序列的整体相似性。Eg：真核生物的基因表达中，因内含子的剪切拼接，导致基因和表达产物（蛋白质
）并非一一对应，因此用局部比对找出部分的相似序列。序列X:ATTGCGA序列Y:ACTTGG匹配加1，错配减1，插空位减
1局部回溯序列X:A_TTGCGA序列Y:ACTTG_GATTGCGA00000000A01000001C00000100T001
10000T00121000G00013210G00002232F(0,0)=0F(i,0)=diF(0,j)=dj0
F(i-1,j-1)+s(xi,yj)F(i,j)=maxF(i-1,j)-dF(i,j-1)-dThanks |
|
