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

1、第第四章章 双序列比对双序列比对 2概念概念 同源（同源（homology）- 具有共同的祖先具有共同的祖先 直向同源（直向同源（Orthologous ） 共生同源（共生同源（paralogous ） 相似（相似（similarity）同源序列一般是相似的，相似序列不同源序列一般是相似的，相似序列不一定是同源的一定是同源的34通过点矩阵进行序列比较通过点矩阵进行序列比较 5编辑距离（编辑距离（Edit Distance)6相似性得分 7第二节第二节 打分矩阵打分矩阵 （1）核酸打分矩阵设DNA序列所用的字母表为 = A，C，G，T a. 等价矩阵 (unitary matrix)b. BLA

2、ST矩阵 c. 转移矩阵（transition，transversion） （嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T） 表3.1 等价矩阵表表3.3 转移矩阵表3.2 BLAST矩阵8（2）蛋白质打分矩阵 （i）等价矩阵等价矩阵 （ii） 氨基酸突变代价矩阵氨基酸突变代价矩阵GCM （iii）疏水矩阵）疏水矩阵 （iv）PAM矩阵（矩阵（Point Accepted Mutation） （Dayhoff模型：可接受点突变）模型：可接受点突变） （v） BLOSUM矩阵矩阵 （Blocks Amino Acid Substitution Matrices）jijiRij01其中Ri

3、j代表打分矩阵元素i、j分别代表字母表第i和第j个字符。9 氨基酸突变代价矩阵氨基酸突变代价矩阵GCM一个氨基酸残基转变到另一个氨基酸残基一个氨基酸残基转变到另一个氨基酸残基所需的所需的密码子碱基密码子碱基变化数目变化数目 1 或或 2只有只有Met到到Tyr为为 31011A S G L K V T P E D N I Q R F Y C H M W Z B X A 01122111112222222222222S 10112211221121111221222G 11022122112221221221222L 21202121222111122111222K 22220212121111

4、222212122V 12112022112122122212222T 11221201221121222212222P 11212210222211222122222E 12121122012212222222122D 12122122101222212122212N 21221212210122212122212I 21211112221021122212222Q 22211221122201222122122R 21111211222110221111222F 21212122222122011222222Y 21222222211222101132212C 21122222222221

5、110221222H 22212221211211212022212M 22211112222121232202222W 2111222222222122122022212疏水矩阵疏水矩阵R K D E B Z S N Q G X T H A C M P V L I Y F W R 1010998866655555433333210K 1010998866655555433333210D 9910108876665555544433321E 9910108876665555544433321B 8888101088887777666555443Z 88881010888877776665554

6、43S 667788101010109999887777664N 666688101010109999888777664Q 666688101010109999888777664G 556688101010109999888877665X 555577999910101010998888775T 555577999910101010998888775H 555577999910101010999888775A 555577999910101010999888775C 4455668888999910109999885动态规划算法动态规划算法 动态规划算法 整体比对算法 Needleman-Wu

7、nsch算法 间隔罚分 局部比对算法 Simth-Waterman算法 矩阵的基本形式是矩阵的基本形式是 将两序列中匹配的残基所对应的单元设将两序列中匹配的残基所对应的单元设为为1，不匹配的为，不匹配的为0 对矩阵中的每个单元进行连需求和，即对矩阵中的每个单元进行连需求和，即把能够到达该位置的所有单元中的最大把能够到达该位置的所有单元中的最大值与该位置的值相加值与该位置的值相加举例说明 让我们用一个例子来解释上述过程：让我们用一个例子来解释上述过程： CKHVFCRVCI CKKCFCKCV 若在匹配位置用若在匹配位置用1标出，而不匹配则留空。标出，而不匹配则留空。可得以下矩阵可得以下矩阵CK

8、HVFCRVCIC111K1KC111F1C111K1C111V11CKHVFCRVCIC111K1KC111F1C111K1C111V11连续求和CKHVFCRVCIC111K1KC111F1C111K1C1110V1100从最后的单元开始CKHVFCRVCIC111K1KC111F1C111K1C1110V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C1111K1100C11010V1100CKHVFCRVCI

9、C111K1KC111F1C111110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C11110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C121110K111100C121010V100100CKHVFCRVCIC11110K11100K11100C21110F11100C21110K2322211100C2111121010V0001000100CKHVFCRVCIC11110K11100K11100C21110F11100C4222221110K2322211100C2111121010V000100010

10、0CKHVFCRVCIC211110K211100K211100C221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC3211110K3211100K3211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC33211110K33211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100C

11、KHVFCRVCIC333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100 从最高分值单元开始找出最大分值路径，也就是最佳匹配CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F322

12、2311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100序列比对结果C K H V F C R V C I|C K K C F C D C V间隔罚分间隔罚分局部比对算法局部比对算法 Simth-Waterman 算法算法 序列局部比对的标准算法序列局部比对的标准算法 在识别局部相似性时，有很高的灵敏性在识别局部相似性时，有很高的灵敏

13、性 在矩阵最上面一行和最左边一列前分别添加一在矩阵最上面一行和最左边一列前分别添加一个边界行和边界列个边界行和边界列 从左往右，从上往下，并沿对角线从左上角到从左往右，从上往下，并沿对角线从左上角到右下角右下角 用三个函数分别计算由三条路径到达该单元的用三个函数分别计算由三条路径到达该单元的分值并找出其中的最大值，如此分值小于分值并找出其中的最大值，如此分值小于0，则用则用0代替代替 函数1：当前单元对角线方向的前一格的分值与当前单元相似性之和，相似性数值匹配时为1.0，不匹配是为-0.333 函数2：当前行前面各分值与相应空位罚分值之差，并取最大值；所求空位罚分值的函数为Wk=1.0+0.3

14、33k, 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

15、.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.0

16、Y0.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

17、.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.

18、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

19、?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.

20、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

21、.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

22、.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

23、.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.76A D L G A V F A L C D R Y F Q|A D L G R T Q N - C D R Y Y Q两种算法的比较 起始部位不同 最高分值所在部位不同53BLAST 简介54BLAST程序是目前最常用的基于局部相似性的数据库搜索程序，它们都基于查找完全匹配的短小序列片段，并将它们延伸得到较长的相似性匹配。它们的优势在于可以在普通的计算机系统上运行，而不必依赖计算机硬件系统而解决运行速度问题。55BLAST数据库搜索策略 BLAST仅通过部分而不是全部序列计算最适联配值赢得搜索速度