第四章双序列比对的动态规划算法

第四章双序列比对

2概念同源（homology）-具有共同的祖先直向同源（Orthologous）共生同源（paralogous）相似（similarity）

同源序列一般是相似的，相似序列不一定是同源的

34通过点矩阵进行序列比较5编辑距离（EditDistance)6相似性得分7第二节打分矩阵（1）核酸打分矩阵设DNA序列所用的字母表为

={A，C，G，T}a.等价矩阵(unitarymatrix)b.BLAST矩阵c.转移矩阵（transition，transversion）（嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T）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.2BLAST矩阵8（2）蛋白质打分矩阵（i）等价矩阵（ii）氨基酸突变代价矩阵GCM（iii）疏水矩阵

（iv）PAM矩阵（PointAcceptedMutation） （Dayhoff模型：可接受点突变）

（v）BLOSUM矩阵（BlocksAminoAcidSubstitutionMatrices）其中Rij代表打分矩阵元素i、j分别代表字母表第i和第j个字符。9氨基酸突变代价矩阵GCM一个氨基酸残基转变到另一个氨基酸残基所需的密码子碱基变化数目

1或2只有Met到Tyr为31011ASGLKVTPEDNIQRFYCHMWZBXA01122111112222222222222S10112211221121111221222G11022122112221221221222L21202121222111122111222K22220212121111222212122V12112022112122122212222T11221201221121222212222P11212210222211222122222E12121122012212222222122D12122122101222212122212N21221212210122212122212I21211112221021122212222Q22211221122201222122122R21111211222110221111222F21212122222122011222222Y21222222211222101132212C21122222222221110221222H22212221211211212022212M22211112222121232202222W21112222222221221220222Z22221222122212222222122B22222222211222212122212X22222222222222222222222GCM矩阵12疏水矩阵RKDEBZSNQGXTHACMPVLIYFWR1010998866655555433333210K1010998866655555433333210D9910108876665555544433321E9910108876665555544433321B8888101088887777666555443Z8888101088887777666555443S667788101010109999887777664N666688101010109999888777664Q666688101010109999888777664G556688101010109999888877665X555577999910101010998888775T555577999910101010998888775H555577999910101010999888775A555577999910101010999888775C4455668888999910109999885M334466888899991010101099887P33446678888899910101099987V3344557778888891010101010987L33335577778888999101010998I33335577778888999101010998Y2233446666777788999910108F1122446666777788889910109W001133444555556777888910动态规划算法动态规划算法整体比对算法Needleman-Wunsch算法间隔罚分局部比对算法Simth-Waterman算法矩阵的基本形式是将两序列中匹配的残基所对应的单元设为1，不匹配的为0对矩阵中的每个单元进行连需求和，即把能够到达该位置的所有单元中的最大值与该位置的值相加第I行第j列单元的值为Ij本身的值+i+1行第j个单元之后所有单元的最大值或j+1列第i个单元之后所有单元的最大值举例说明让我们用一个例子来解释上述过程：CKHVFCRVCICKKCFCKCV若在匹配位置用1标出，而不匹配则留空。可得以下矩阵CKHVFCRVCIC111K1KC111F1C111K1C111V11CKHVFCRVCIC111K1KC111F1C111K1C111V11连续求和CKHVFCRVCIC111K1KC111F1C111K1C1110V1100从最后的单元开始CKHVFCRVCIC111K1KC111F1C111K1C1110V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C1111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C111110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C11110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C121110K111100C121010V100100CKHVFCRVCIC11110K11100K11100C21110F11100C21110K2322211100C2111121010V0001000100CKHVFCRVCIC11110K11100K11100C21110F11100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC211110K211100K211100C221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC3211110K3211100K3211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC33211110K33211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100从最高分值单元开始找出最大分值路径，也就是最佳匹配CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100序列比对结果CKHVFCRVCI||||CKKCFCDCV间隔罚分空位的缺失和插入，有助于获得最佳匹配但是不加限制的间隔，缺乏必要的生物学意义局部比对算法Simth-Waterman算法序列局部比对的标准算法在识别局部相似性时，有很高的灵敏性在矩阵最上面一行和最左边一列前分别添加一个边界行和边界列从左往右，从上往下，并沿对角线从左上角到右下角用三个函数分别计算由三条路径到达该单元的分值并找出其中的最大值，如此分值小于0，则用0代替函数1：当前单元对角线方向的前一格的分值与当前单元相似性之和，相似性数值匹配时为1.0，不匹配是为-0.333函数2：当前行前面各分值与相应空位罚分值之差，并取最大值；所求空位罚分值的函数为Wk=1.0+0.333k,k表示连续第k个空位函数3：当前列前面各分值与相应空位罚分值之差，并取最大值。如果出现负值就用0代替，表示没有相似性研究到当前位置XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.01.01.0D0.01.01.0L0.01.01.0G0.01.0R0.01.0T0.0Q0.01.0N0.0C0.01.0D0.01.01.0R0.01.0Y0.01.0Y0.01.0Q0.01.0XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.01.01.0D0.02.01.0L0.03.01.0G0.04.0R0.03.71.0T0.0Q0.01.0N0.0C0.01.0D0.01.01.0R0.01.0Y0.01.0Y0.01.0Q0.01.0XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.01.01.0D0.02.01.0L0.03.01.0G0.04.0R0.03.71.0T0.03.3Q0.03.01.0N0.02.7C0.02.31.0D0.01.02.01.0R0.01.71.0Y0.01.31.0Y0.02.3Q0.02.04.7XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.00.00.00.01.01.0D0.00.02.00.70.30.00.71.0L0.00.00.03.00.31.0G0.04.0R0.03.71.0T0.03.3Q0.03.01.0N0.02.7C0.02.31.0D0.01.02.01.0R0.01.71.0Y0.01.31.0Y0.02.3Q0.02.04.7XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.00.00.00.01.01.0D0.00.02.00.70.30.00.71.0L0.00.00.03.01.71.31.00.70.31.0G0.04.02.72.32.01.71.31.00.70.3R0.03.71.0T0.03.3Q0.03.01.0N0.02.7C0.02.31.0D0.01.02.01.0R0.01.71.0Y0.01.31.0Y0.02.3Q0.02.04.7XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.00.00.00.01.00.00.01.00.00.0D0.00.02.00.70.30.00.70.00.00.70.01.0L0.00.00.73.01.71.31.00.70.31.00.3G0.00.00.31.74.02.72.32.01.71.31.00.70.3R0.00.00.01.32.73.72.32.01.71.31.01.0T0.00.00.01.02.32.33.32.01.71.31.0Q0.00.00.00.72.02.02.03.01.71.31.01.0N0.00.00.00.31.71.71.71.72.71.31.0C0.00.00.00.01.31.31.31.31.32.3?D1.01.0R1.71.0Y0.31.31.0Y2.3Q2.04.7XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.00.00.00.01.00.00.01.00.00.00.10.00.00.00.0D0.00.02.00.70.30.00.70.00.00.70.01.00.00.00.00.0L0.00.00.73.01.71.31.00.70.31.00.30.00.70.00.00.0G0.00.00.31.74.02.72.32.01.71.31.00.70.30.30.00.0R0.00.00.01.32.73.72.32.01.71.31.00.71.00.00.00.0T0.00.00.01.02.32.33.32.01.71.31.00.70.30.70.00.0Q0.00.00.00.72.02.02.03.01.71.31.00.70.30.00.31.0N0.00.00.00.31.71.71.71.72.71.31.00.70.30.00.00.0C0.00.00.00.01.31.31.31.31.32.32.30.70.30.00.00.0D0.00.01.00.01.01.01.01.01.01.02.03.320.70.30.0R0.00.00.00.70.70.70.70.70.70.70.72.04.33.02.72.3Y0.00.00.00.00.30.30.30.30.30.30.31.73.05.33.73.3Y0.00.00.00.00.00.00.00.00.00.00.01.32.74.053.3Q0.00.00.00.00.00.00.00.00.00.00.01.02.33.73.76XADLGAVFALCDRYFQX0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0A0.01.00.00.00.01.00.00.01.00.00.00.10.00.00.00.0D0.00.02.00.70.30.00.70.00.00.70.01.00.00.00.00.0L0.00.00.73.01.71.31.00.70.31.00.30.00.70.00.00.0G0.00.00.31.74.02.72.32.01.71.31.00.70.30.30.00.0R0.00.00.01.32.73.72.32.01.71.31.00.71.00.00.00.0T0.00.00.01.02.32.33.32.01.71.31.00.70.30.70.00.0Q0.00.00.00.72.02.02.03.01.71.31.00.70.30.00.31.0N0.00.00.00.31.71.71.71.72.71.31.00.70.30.00.00.0C0.00.00.00.01.31.31.31.31.32.32.30.70.30.00.00.0D0.00.01.00.01.01.01.01.01.01.02.03.320.70.30.0R0.00.00.00.70.70.70.70.70.70.70.72.04.33.02.72.3Y0.00.00.00.00.30.30.30.30.30.30.31.73.05.33.73.3Y0.00.00.00.00.00.00.00.00.00.00.01.32.74.053.3Q0.00.00.00.00.00.00.00.00.00.00.01.02.33.73.76ADLGAVFALCDRYFQ||||||||||ADLGRTQN-CDRYYQ两种算法的比较起始部位不同最高分值所在部位不同53BLAST简介54BLAST程序是目前最常用的基于局部相似性的数据库搜索程序，它们都基于查找完全匹配的短小序列片段，并将它们延伸得到较长的相似性匹配。它们的优势在于可以在普通的计算机系统上运行，而不必依赖计算机硬件系统而解决运行速度问题。55BLAST数据库搜索策略BLAST仅通过部分而不是全部序列计算最适联配值——赢得搜索速度。5657比对统计学意义的评价--E值(E-Value)P值(P-Value)(概率值)BLAST程序中使用了E值而非P值，这主要是从直观和便于理解的角度考虑。比如E值等于5和10，总比P值等于0.993和0.99995更直观。但是当E<0.01时，P值与E值接近相同参数K和λ可分别被简单地视为搜索步长(searchspacesize)和计分系统(scoringsystem)的特征数58BLAST软件包实际上是综合在一起的一组程序，不仅可用于直接对蛋白质序列数据库和核酸序列数据库进行搜索，而且可以将检测序列翻