生物信息學第2章

1、人民衛(wèi)生出版社8年制及7年制臨床醫(yī)學等專業(yè)用生物信息學表3.1 等價矩陣表表3.3 轉(zhuǎn)移矩陣表3.2 BLAST矩陣jijiRij01其中Rij代表打分矩陣元素i、j分別代表字母表第i和第j個字符。A 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 22220212121111222212122V 12112022112122122212222T 112

2、21201221121222212222P 11212210222211222122222E 12121122012212222222122D 12122122101222212122212N 21221212210122212122212I 21211112221021122212222Q 22211221122201222122122R 21111211222110221111222F 21212122222122011222222Y 21222222211222101132212C 21122222222221110221222H 22212221211211212022212M 222

3、11112222121232202222W 21112222222221221220222Z 22221222122212222222122B 22222222211222212122212X 22222222222222222222222R 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 888810108888777766655544

4、3Z 8888101088887777666555443S 667788101010109999887777664N 666688101010109999888777664Q 666688101010109999888777664G 556688101010109999888877665X 555577999910101010998888775T 555577999910101010998888775H 555577999910101010999888775A 555577999910101010999888775C 4455668888999910109999885M 33446688889

5、9991010101099887P 33446678888899910101099987V 3344557778888891010101010987L 33335577778888999101010998I 33335577778888999101010998Y 2233446666777788999910108F 1122446666777788889910109W 001133444555556777888910PAM矩陣（矩陣（ point accepted mutaion） 基于氨基酸進化的點突變模型基于氨基酸進化的點突變模型 如果兩種氨基酸替換頻繁，說明自然界接受這種替換，那么這對氨

6、基酸替換得分就高 一個一個PAM就是一個進化的變異單位就是一個進化的變異單位, 即即1%的氨基酸改變的氨基酸改變但這并不意味但這并不意味100次次PAM后，每個氨基酸都發(fā)生變化，因為其中一些位置可能后，每個氨基酸都發(fā)生變化，因為其中一些位置可能會經(jīng)過多次突變，甚至可能會變回到原來的氨基酸。會經(jīng)過多次突變，甚至可能會變回到原來的氨基酸。PAM矩陣的制作步驟矩陣的制作步驟構(gòu)建序列相似（大于構(gòu)建序列相似（大于85）的比對）的比對計算氨基酸計算氨基酸 j 的相對的相對突變率突變率mj（j被其他氨基酸替換的次數(shù)）被其他氨基酸替換的次數(shù)）針對每個氨基酸對針對每個氨基酸對 i 和和 j , 計算計算 j 被

7、被 i 替換次數(shù)替換次數(shù)替換次數(shù)替換次數(shù)除以除以相對突變率相對突變率（mj）利用每個氨基酸出現(xiàn)的利用每個氨基酸出現(xiàn)的頻度頻度對對j 進行進行標準化標準化取常用對數(shù)取常用對數(shù)，得到，得到PAM-1(i, j)將將PAM-1自乘自乘N次次，可以得到，可以得到PAM-nTotal Mutation Rateis the total mutation rate of all amino acidsThis defines an evolutionary period: the period during which the 1% of all sequences are mutated (accept

8、ed of course)Mutation Probability Matrix Normalized Such that the Total Mutation Rate is 1%Mutation Probability Matrix (transposed) M*10000elements are shown multiplied by 10,000 From: http:/www.icp.ucl.ac.be/opperd/private/pam1.htmlPAM-250Two classes of widely used protein scoring matricesBLOSUM 62

9、Choice of Scoring Matrix針對不同的進化距離采用針對不同的進化距離采用PAM 矩陣矩陣序列相似度序列相似度 = 40% 50% 60% | | |打分矩陣打分矩陣 = PAM120 PAM80 PAM 60PAM250 14% - 27% 序列兩兩比對基本算法序列兩兩比對基本算法直接方法直接方法 生成兩個序列所有可能的比對，分別計算生成兩個序列所有可能的比對，分別計算代價函數(shù)，然后挑選一個代價函數(shù)，然后挑選一個代價最小代價最小的比對作為最終結(jié)果，的比對作為最終結(jié)果，需要計算需要計算 2300 次次天文數(shù)字天文數(shù)字ATTCCGAAGA AGTCGAAGGT假設比較300個氨

10、基酸長度的兩條序列動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法 Dynamic Programming起點起點終點終點ATTCCGAAGA AGTCGAAGGTATTCCGAAG AGTCGAAGGAT+（1）ATTCCGAAGA AGTCGAAGG-T+（2）ATTCCGAAG AGTCGAAGGTA-+（3）最短路經(jīng)問題最短路經(jīng)問題起點起點終點終點C1 C2 W1 W2路徑1：C1 + w1 ？路徑2：C2 + w2 ？ 取最小值！取最小值！算法求解算法求解: 從起點到終點逐層計算從起點到終點逐層計算計算過程：計算過程：計算過程：計算過程：按行計算按行計算其他方式其他方式計算過程：計算過程：（3）求最佳路徑）

11、求最佳路徑算法分析：算法分析：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)d i , j空間復雜度：空間復雜度：O (mn)時間復雜度：時間復雜度：O (mn)由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 矩陣賦值算法矩陣賦值算法 forfor i=0 toto lengthlength(A) F(i,0) 0 forfor j=0 toto lengthlength(B) F(0,j) 0 forfor i=1 toto lengthlength(A) forfor j = 1 toto lengthlength(B) Choice1 F(i-1,

12、j-1) + S(A(i), B(j) Choice2 F(i-1, j) + d Choice3 F(i, j-1) + d F(i,j) maxmax(Choice1, Choice2, Choice3) 反向構(gòu)造匹配序列反向構(gòu)造匹配序列 AlignmentA AlignmentB i lengthlength(A) j lengthlength(B) whilewhile (i 0 andand j 0) Score F(i,j) ScoreDiag F(i - 1, j - 1) ScoreUp F(i, j - 1) ScoreLeft F(i - 1, j) ifif (Score

13、 = ScoreDiag + S(A(i-1), B(j-1) AlignmentA A(i-1) + AlignmentA AlignmentB B(j-1) + AlignmentB i i - 1 j j - 1 elseelse ifif (Score = ScoreLeft + d) AlignmentA A(i-1) + AlignmentA AlignmentB - + AlignmentB i i - 1 otherwiseotherwise (Score = ScoreUp + d) AlignmentA - + AlignmentA AlignmentB B(j-1) +

14、AlignmentB j j - 1 序列S:序列t: i j不計前綴0:t:i 的得分, 也不計刪除后綴的j+1:t:|t|得分不計刪除后綴的不計刪除后綴的j+1:t:|t|得分得分 處理最后一行處理最后一行):,:(),():,:(),():,:(max):,:() 1(000) 1(0) 1(0) 1(000jmmjmjmjmjmtsSsptsStsptsStsS+ p ( -, tj )不計前綴不計前綴0 0:t:t:i i 的得分的得分處理第一行處理第一行0):,:(000itsS最后一行不計代價最后一行不計代價子序列s在全序列t的后面出現(xiàn)時不會被罰分影響數(shù)據(jù)庫的搜索簡數(shù)據(jù)庫的搜索簡

15、介介第四節(jié) 雙序列比對工具 數(shù)據(jù)庫查詢?yōu)樯飳W研究提供了一個重要工具，在實際工作中經(jīng)常使用。然而，在分子生物學研究中，對于新測定的堿基序列或由此翻譯得到的氨基酸序列，往往需要通過數(shù)據(jù)庫搜索，找出具有一定相似性的同源序列，以推測該未知序列可能屬于哪個基因家族，具有哪些生物學功能。對于氨基酸序列來說，有可能找到已知三維結(jié)構(gòu)的同源蛋白質(zhì)而推測其可能的空間結(jié)構(gòu)。因此，數(shù)據(jù)庫搜索與數(shù)據(jù)庫查詢一樣，是生物信息學研究中的一個重要工具。 數(shù)據(jù)庫搜索的基礎(chǔ)是序列的相似性比對，即雙序列比對(pairwise alignment)。 新測定的、希望通過數(shù)據(jù)庫搜索確定其性質(zhì)或功能的序列稱作檢測序列(probe seq

16、uence)；通過數(shù)據(jù)庫搜索得到的和檢測序列具有一定相似性的序列稱目標序列(subject sequence)。 為了確定檢測序列和一個已知基因家族之間的進化關(guān)系，在通過數(shù)據(jù)庫搜索得到某些相似序列后，還需要判斷其序列相似性程度。如果檢測序列和目標序列的相似性程度很低，還必須通過其他方法或?qū)嶒炇侄尾拍艽_定其是否屬于同一基因家族 。BLAST程序是目前最常用的基于局部相似性的數(shù)據(jù)庫搜索程序，它們都基于查找完全匹配的短小序列片段，并將它們延伸得到較長的相似性匹配。它們的優(yōu)勢在于可以在普通的計算機系統(tǒng)上運行，而不必依賴計算機硬件系統(tǒng)而解決運行速度問題。BLAST數(shù)據(jù)庫搜索策略數(shù)據(jù)庫搜索策略 BLAST

17、僅通過部分而不是全部序列計算最適聯(lián)配值贏得搜索速度 比對統(tǒng)計學意義的評價 E值值(E-Value)P值值(P-Value)(概率值概率值) BLAST程序中使用了E值而非P值，這主要是從直觀和便于理解的角度考慮。比如E值等于5和10，總比P值等于0.993和0.99995更直觀。但是當Egi|224983683|pdb|3GBN|B Chain B, Crystal Structure Of Fab Cr6261 In Complex With The 1918 H1n1 Influenza Virus HemagglutininGLFGAIAGFIEGGWTGMIDGWYGYHHQNEQGS

18、GYAADQKSTQNAIDGITNKVNSVIEKMNTQFTAVGKEFNNLERRIENLNKKVDDGFLDIWTYNAELLVLLENERTLDFHDSNVRNLYEKVKSQLKNNAKEIGNGCFEFYHKCDDACMESVRNGTYDYPKYSEESKLNREEIDGVSGR序列sp|P31025|LCN1_HUMAN Lipocalin-1 OS=Homo sapiens GN=LCN1 PE=1 SV=1MKPLLLAVSLGLIAALQAHHLLASDEEIQDVSGTWYLKAMTVDREFPEMNLESVTPMTLTTLEGGNLEAKVTMLISGRCQEVKAV

19、LEKTDEPGKYTADGGKHVAYIIRSHVKDHYIFYCEGELHGKPVRGVKLVGRDPKNNLEALEDFEKAAGARGLSTESILIPRQSETCSPGSDFastA簡介簡介 FastA算法是由Lipman和Pearson于1985年發(fā)表的（Lipman和Pearson，1985）。FastA的基本思路是識別與代查序列相匹配的很短的序列片段，稱為k-tuple。 蛋白質(zhì)序列數(shù)據(jù)庫搜索時，短片段的長度一般是12個殘基長；DNA序列數(shù)據(jù)庫搜索時，通常采用稍大點的值，最多為6個堿基。通過比較兩個序列中的短片段及其相對位置，可以構(gòu)成一個動態(tài)規(guī)劃矩陣的對角線方向上的一些匹配片段

20、。 FastA程序采用漸進（heuristic approach）算法將位于同一對角線上相互接近的短片段連接起來。也就是說，通過不匹配的殘基將這些匹配殘基片段連接起來，以便得到較長的相似性片段。這就意味著，F(xiàn)astA輸出結(jié)果中允許出現(xiàn)不匹配殘基。這和BLAST程序中的成對片段類似。如果匹配區(qū)域很多，F(xiàn)astA利用動態(tài)規(guī)劃算法在這些匹配區(qū)域間插入空位。 由FastA搜索產(chǎn)生的典型輸出結(jié)果的第一行列出程序名稱和版本號，以及該程序發(fā)表的雜志。接下來列出所提交的序列，然后是所用參數(shù)和運行時間，緊跟這些一般信息的是數(shù)據(jù)庫搜索結(jié)果。 首先列出搜索得到的目標序列簡單說明，其數(shù)目可由用戶定義。所列出的目標序列

21、的信息包括：序列所在數(shù)據(jù)庫名稱的縮寫，目標序列的標識碼、序列號和序列名等部分信息。括號中標明匹配部分的殘基數(shù)。緊接著是由程序計算得到的初始化和優(yōu)化后的分數(shù)值。最后一列是期望值即E值，用來判斷比對結(jié)果的置信度。接近于0的E值表明兩序列的匹配不大可能是由隨機因素造成的。以兩條氨基酸序列的比較為例介紹算法的基本思路，算法可以分為以兩條氨基酸序列的比較為例介紹算法的基本思路，算法可以分為4步：步：第一步：第一步： FASTA首先找出進行比較的兩條序列所有長度為k-tuple 的連續(xù)的一致序列片段。例如以下兩條蛋白質(zhì)序列： 設k-tuple =2，則序列2中有兩個符合條件的片段(用下劃線表示)，相對于序列1的偏移(offset)分別是4和1對于一對開始位置為(x1,x2)的一致片段，偏移定義為x1-x2。在上例中有兩對(x1，x2)，即（5,1）和(5,4)。這種片段的一致性可以表示為對角線圖，兩條序列中的一對一致片段在圖中表示為一段對角線。序列FLWRTW和STWKTWT比較形成的對角線圖 對于圖中每一條完整的對角線(即同一偏移)上的一致片段，如果片段間距小于用戶界定的界限，則將片段連接起來作為一條一致片段。. 本例是兩條非常短的氨基酸序列，在實際比較長的蛋白質(zhì)序列或DNA序列時，對角線圖如圖A所示。 對這些片段