生物信息學(xué)第2章

1、人民衛(wèi)生出版社8年制及7年制臨床醫(yī)學(xué)等專業(yè)用生物信息學(xué)表3.1 等價(jià)矩陣表表3.3 轉(zhuǎn)移矩陣表3.2 BLAST矩陣jijiRij01其中Rij代表打分矩陣元素i、j分別代表字母表第i和第j個(gè)字符。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） 基于氨基酸進(jìn)化的點(diǎn)突變模型基于氨基酸進(jìn)化的點(diǎn)突變模型 如果兩種氨基酸替換頻繁，說(shuō)明自然界接受這種替換，那么這對(duì)氨

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

7、被 i 替換次數(shù)替換次數(shù)替換次數(shù)替換次數(shù)除以除以相對(duì)突變率相對(duì)突變率（mj）利用每個(gè)氨基酸出現(xiàn)的利用每個(gè)氨基酸出現(xiàn)的頻度頻度對(duì)對(duì)j 進(jìn)行進(jìn)行標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化取常用對(duì)數(shù)取常用對(duì)數(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針對(duì)不同的進(jìn)化距離采用針對(duì)不同的進(jìn)化距離采用PAM 矩陣矩陣序列相似度序列相似度 = 40% 50% 60% | | |打分矩陣打分矩陣 = PAM120 PAM80 PAM 60PAM250 14% - 27% 序列兩兩比對(duì)基本算法序列兩兩比對(duì)基本算法直接方法直接方法 生成兩個(gè)序列所有可能的比對(duì)，分別計(jì)算生成兩個(gè)序列所有可能的比對(duì)，分別計(jì)算代價(jià)函數(shù)，然后挑選一個(gè)代價(jià)函數(shù)，然后挑選一個(gè)代價(jià)最小代價(jià)最小的比對(duì)作為最終結(jié)果，的比對(duì)作為最終結(jié)果，需要計(jì)算需要計(jì)算 2300 次次天文數(shù)字天文數(shù)字ATTCCGAAGA AGTCGAAGGT假設(shè)比較300個(gè)氨

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

11、求最佳路徑算法分析：算法分析：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)d i , j空間復(fù)雜度：空間復(fù)雜度：O (mn)時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O (mn)由于在所考慮的子問(wèn)題空間中，總共有(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(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不計(jì)前綴0:t:i 的得分, 也不計(jì)刪除后綴的j+1:t:|t|得分不計(jì)刪除后綴的不計(jì)刪除后綴的j+1:t:|t|得分得分 處理最后一行處理最后一行):,:(),():,:(),():,:(max):,:() 1(000) 1(0) 1(0) 1(000jmmjmjmjmjmtsSsptsStsptsStsS+ p ( -, tj )不計(jì)前綴不計(jì)前綴0 0:t:t:i i 的得分的得分處理第一行處理第一行0):,:(000itsS最后一行不計(jì)代價(jià)最后一行不計(jì)代價(jià)子序列s在全序列t的后面出現(xiàn)時(shí)不會(huì)被罰分影響數(shù)據(jù)庫(kù)的搜索簡(jiǎn)數(shù)據(jù)庫(kù)的搜索簡(jiǎn)

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

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

17、僅通過(guò)部分而不是全部序列計(jì)算最適聯(lián)配值贏得搜索速度 比對(duì)統(tǒng)計(jì)學(xué)意義的評(píng)價(jià) E值值(E-Value)P值值(P-Value)(概率值概率值) BLAST程序中使用了E值而非P值，這主要是從直觀和便于理解的角度考慮。比如E值等于5和10，總比P值等于0.993和0.99995更直觀。但是當(dāng)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簡(jiǎn)介簡(jiǎn)介 FastA算法是由Lipman和Pearson于1985年發(fā)表的（Lipman和Pearson，1985）。FastA的基本思路是識(shí)別與代查序列相匹配的很短的序列片段，稱為k-tuple。 蛋白質(zhì)序列數(shù)據(jù)庫(kù)搜索時(shí)，短片段的長(zhǎng)度一般是12個(gè)殘基長(zhǎng)；DNA序列數(shù)據(jù)庫(kù)搜索時(shí)，通常采用稍大點(diǎn)的值，最多為6個(gè)堿基。通過(guò)比較兩個(gè)序列中的短片段及其相對(duì)位置，可以構(gòu)成一個(gè)動(dòng)態(tài)規(guī)劃矩陣的對(duì)角線方向上的一些匹配片段

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

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