第四章雙序列比對的動(dòng)態(tài)規(guī)劃算法

1、第第四章章 雙序列比對雙序列比對 2概念概念 同源（同源（homology）- 具有共同的祖先具有共同的祖先 直向同源（直向同源（Orthologous ） 共生同源（共生同源（paralogous ） 相似（相似（similarity）同源序列一般是相似的，相似序列不同源序列一般是相似的，相似序列不一定是同源的一定是同源的34通過點(diǎn)矩陣進(jìn)行序列比較通過點(diǎn)矩陣進(jìn)行序列比較 5編輯距離（編輯距離（Edit Distance)6相似性得分 7第二節(jié)第二節(jié) 打分矩陣打分矩陣 （1）核酸打分矩陣設(shè)DNA序列所用的字母表為 = A，C，G，T a. 等價(jià)矩陣 (unitary matrix)b. BLA

2、ST矩陣 c. 轉(zhuǎn)移矩陣（transition，transversion） （嘌呤：腺嘌呤A，鳥嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T） 表3.1 等價(jià)矩陣表表3.3 轉(zhuǎn)移矩陣表3.2 BLAST矩陣8（2）蛋白質(zhì)打分矩陣 （i）等價(jià)矩陣等價(jià)矩陣 （ii） 氨基酸突變代價(jià)矩陣氨基酸突變代價(jià)矩陣GCM （iii）疏水矩陣）疏水矩陣 （iv）PAM矩陣（矩陣（Point Accepted Mutation） （Dayhoff模型：可接受點(diǎn)突變）模型：可接受點(diǎn)突變） （v） BLOSUM矩陣矩陣 （Blocks Amino Acid Substitution Matrices）jijiRij01其中Ri

3、j代表打分矩陣元素i、j分別代表字母表第i和第j個(gè)字符。9 氨基酸突變代價(jià)矩陣氨基酸突變代價(jià)矩陣GCM一個(gè)氨基酸殘基轉(zhuǎn)變到另一個(gè)氨基酸殘基一個(gè)氨基酸殘基轉(zhuǎn)變到另一個(gè)氨基酸殘基所需的所需的密碼子堿基密碼子堿基變化數(shù)目變化數(shù)目 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動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法 動(dòng)態(tài)規(guī)劃算法 整體比對算法 Needleman-Wu

7、nsch算法 間隔罰分 局部比對算法 Simth-Waterman算法 矩陣的基本形式是矩陣的基本形式是 將兩序列中匹配的殘基所對應(yīng)的單元設(shè)將兩序列中匹配的殘基所對應(yīng)的單元設(shè)為為1，不匹配的為，不匹配的為0 對矩陣中的每個(gè)單元進(jìn)行連需求和，即對矩陣中的每個(gè)單元進(jìn)行連需求和，即把能夠到達(dá)該位置的所有單元中的最大把能夠到達(dá)該位置的所有單元中的最大值與該位置的值相加值與該位置的值相加舉例說明 讓我們用一個(gè)例子來解釋上述過程：讓我們用一個(gè)例子來解釋上述過程： CKHVFCRVCI CKKCFCKCV 若在匹配位置用若在匹配位置用1標(biāo)出，而不匹配則留空。標(biāo)出，而不匹配則留空?？傻靡韵戮仃嚳傻靡韵戮仃嘋K

8、HVFCRVCIC111K1KC111F1C111K1C111V11CKHVFCRVCIC111K1KC111F1C111K1C111V11連續(xù)求和CKHVFCRVCIC111K1KC111F1C111K1C1110V1100從最后的單元開始CKHVFCRVCIC111K1KC111F1C111K1C1110V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C1111K1100C11010V1100CKHVFCRVCI

9、C111K1KC111F1C111110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C11110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C121110K111100C121010V100100CKHVFCRVCIC11110K11100K11100C21110F11100C21110K2322211100C2111121010V0001000100CKHVFCRVCIC11110K11100K11100C21110F11100C4222221110K2322211100C2111121010V000100010

10、0CKHVFCRVCIC211110K211100K211100C221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC3211110K3211100K3211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC33211110K33211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100C

11、KHVFCRVCIC333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100 從最高分值單元開始找出最大分值路徑，也就是最佳匹配CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F322

12、2311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100序列比對結(jié)果C K H V F C R V C I|C K K C F C D C V間隔罰分間隔罰分局部比對算法局部比對算法 Simth-Waterman 算法算法 序列局部比對的標(biāo)準(zhǔn)算法序列局部比對的標(biāo)準(zhǔn)算法 在識(shí)別局部相似性時(shí)，有很高的靈敏性在識(shí)別局部相似性時(shí)，有很高的靈敏

13、性 在矩陣最上面一行和最左邊一列前分別添加一在矩陣最上面一行和最左邊一列前分別添加一個(gè)邊界行和邊界列個(gè)邊界行和邊界列 從左往右，從上往下，并沿對角線從左上角到從左往右，從上往下，并沿對角線從左上角到右下角右下角 用三個(gè)函數(shù)分別計(jì)算由三條路徑到達(dá)該單元的用三個(gè)函數(shù)分別計(jì)算由三條路徑到達(dá)該單元的分值并找出其中的最大值，如此分值小于分值并找出其中的最大值，如此分值小于0，則用則用0代替代替 函數(shù)1：當(dāng)前單元對角線方向的前一格的分值與當(dāng)前單元相似性之和，相似性數(shù)值匹配時(shí)為1.0，不匹配是為-0.333 函數(shù)2：當(dāng)前行前面各分值與相應(yīng)空位罰分值之差，并取最大值；所求空位罰分值的函數(shù)為Wk=1.0+0.3

14、33k, k表示連續(xù)第k個(gè)空位 函數(shù)3：當(dāng)前列前面各分值與相應(yīng)空位罰分值之差，并取最大值。如果出現(xiàn)負(fù)值就用0代替，表示沒有相似性研究到當(dāng)前位置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程序是目前最常用的基于局部相似性的數(shù)據(jù)庫搜索程序，它們都基于查找完全匹配的短小序列片段，并將它們延伸得到較長的相似性匹配。它們的優(yōu)勢在于可以在普通的計(jì)算機(jī)系統(tǒng)上運(yùn)行，而不必依賴計(jì)算機(jī)硬件系統(tǒng)而解決運(yùn)行速度問題。55BLAST數(shù)據(jù)庫搜索策略 BLAST僅通過部分而不是全部序列計(jì)算最適聯(lián)配值贏得搜索速度