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

第四章雙序列比對

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

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

34通過點矩陣進行序列比較5編輯距離（EditDistance)6相似性得分7第二節(jié)打分矩陣（1）核酸打分矩陣設(shè)DNA序列所用的字母表為

={A，C，G，T}a.等價矩陣(unitarymatrix)b.BLAST矩陣c.轉(zhuǎn)移矩陣（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轉(zhuǎn)移矩陣表3.2BLAST矩陣8（2）蛋白質(zhì)打分矩陣（i）等價矩陣（ii）氨基酸突變代價矩陣GCM（iii）疏水矩陣

（iv）PAM矩陣（PointAcceptedMutation） （Dayhoff模型：可接受點突變）

（v）BLOSUM矩陣（BlocksAminoAcidSubstitutionMatrices）其中Rij代表打分矩陣元素i、j分別代表字母表第i和第j個字符。9氨基酸突變代價矩陣GCM一個氨基酸殘基轉(zhuǎn)變到另一個氨基酸殘基所需的密碼子堿基變化數(shù)目

1或2只有Met到Tyr為31011ASGLKVTPEDNIQRFYCHMWZBXA01122111112222222222222S10112211221121111221222G11022122112221221221222L21202121222111122111222K22220212121111222212122V12112022112122122212222T11221201221121222212222P11212210222211222122222E12121122012212222222122D12122122101222212122212N21221212210122212122212I21211112221021122212222Q22211221122201222122122R21111211222110221111222F21212122222122011222222Y21222222211222101132212C21122222222221110221222H22212221211211212022212M22211112222121232202222W21112222222221221220222Z22221222122212222222122B22222222211222212122212X22222222222222222222222GCM矩陣12疏水矩陣RKDEBZSNQGXTHACMPVLIYFWR1010998866655555433333210K1010998866655555433333210D9910108876665555544433321E9910108876665555544433321B8888101088887777666555443Z8888101088887777666555443S667788101010109999887777664N666688101010109999888777664Q666688101010109999888777664G556688101010109999888877665X555577999910101010998888775T555577999910101010998888775H555577999910101010999888775A555577999910101010999888775C4455668888999910109999885M334466888899991010101099887P33446678888899910101099987V3344557778888891010101010987L33335577778888999101010998I33335577778888999101010998Y2233446666777788999910108F1122446666777788889910109W001133444555556777888910動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法整體比對算法Needleman-Wunsch算法間隔罰分局部比對算法Simth-Waterman算法矩陣的基本形式是將兩序列中匹配的殘基所對應的單元設(shè)為1，不匹配的為0對矩陣中的每個單元進行連需求和，即把能夠到達該位置的所有單元中的最大值與該位置的值相加第I行第j列單元的值為Ij本身的值+i+1行第j個單元之后所有單元的最大值或j+1列第i個單元之后所有單元的最大值舉例說明讓我們用一個例子來解釋上述過程：CKHVFCRVCICKKCFCKCV若在匹配位置用1標出，而不匹配則留空。可得以下矩陣CKHVFCRVCIC111K1KC111F1C111K1C111V11CKHVFCRVCIC111K1KC111F1C111K1C111V11連續(xù)求和CKHVFCRVCIC111K1KC111F1C111K1C1110V1100從最后的單元開始CKHVFCRVCIC111K1KC111F1C111K1C1110V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C1111K1100C11010V1100CKHVFCRVCIC111K1KC111F1C111110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C11110K11100C111010V10100CKHVFCRVCIC111K1KC111F1C121110K111100C121010V100100CKHVFCRVCIC11110K11100K11100C21110F11100C21110K2322211100C2111121010V0001000100CKHVFCRVCIC11110K11100K11100C21110F11100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC211110K211100K211100C221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC3211110K3211100K3211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC33211110K33211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100從最高分值單元開始找出最大分值路徑，也就是最佳匹配CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100CKHVFCRVCIC5333211110K3433211100K3333211100C4333221110F3222311100C4222221110K2322211100C2111121010V0001000100序列比對結(jié)果CKHVFCRVCI||||CKKCFCDCV間隔罰分空位的缺失和插入，有助于獲得最佳匹配但是不加限制的間隔，缺乏必要的生物學意義局部比對算法Simth-Waterman算法序列局部比對的標準算法在識別局部相似性時，有很高的靈敏性在矩陣最上面一行和最左邊一列前分別添加一個邊界行和邊界列從左往右，從上往下，并沿對角線從左上角到右下角用三個函數(shù)分別計算由三條路徑到達該單元的分值并找出其中的最大值，如此分值小于0，則用0代替函數(shù)1：當前單元對角線方向的前一格的分值與當前單元相似性之和，相似性數(shù)值匹配時為1.0，不匹配是為-0.333函數(shù)2：當前行前面各分值與相應空位罰分值之差，并取最大值；所求空位罰分值的函數(shù)為Wk=1.0+0.333k,k表示連續(xù)第k個空位函數(shù)3：當前列前面各分值與相應空位罰分值之差，并取最大值。如果出現(xiàn)負值就用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程序是目前最常用的基于局部相似性的數(shù)據(jù)庫搜索程序，它們都基于查找完全匹配的短小序列片段，并將它們延伸得到較長的相似性匹配。它們的優(yōu)勢在于可以在普通的計算機系統(tǒng)上運行，而不必依賴計算機硬件系統(tǒng)而解決運行速度問題。55BLAST數(shù)據(jù)庫搜索策略BLAST僅通過部分而不是全部序列計算最適聯(lián)配值——贏得搜索速度。5657比對統(tǒng)計學意義的評價--E值(E-Value)P值(P-Value)(概率值)BLAST程序中使用了E值而非P值，這主要是從直觀和便于理解的角度考慮。比如E值等于5和10，總比P值等于0.993和0.99995更直觀。但是當E<0.01時，P值與E值接近相同參數(shù)K和λ可分別被簡單地視為搜索步長(searchspacesize)和計分系統(tǒng)(scoringsystem)的特征數(shù)58BLAST軟件包實際上是綜合在一起的一組程序，不僅可用于直接對蛋白質(zhì)序列數(shù)據(jù)庫和核酸序列數(shù)據(jù)庫進行搜索，而且可以將檢測序列翻