中國科技大學(xué)課件系列：《生物信息學(xué)》

《中國科技大學(xué)課件系列：《生物信息學(xué)》》由會員分享，可在線閱讀，更多相關(guān)《中國科技大學(xué)課件系列：《生物信息學(xué)》（72頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第 三 章 序 列 比 對 r第 一 節(jié) ： 數(shù) 學(xué) 基 礎(chǔ) ： 概 率 及 概 率 模 型r第 二 節(jié) ： 雙 序 列 比 對 算 法 的 介 紹Dot matrix動態(tài)規(guī)劃算法w(Needleman-Wunsch, Smith-Waterman算法) FASTA和BLAST算法r第 三 節(jié) ： 打 分 矩 陣 及 其 含 義r第 四 節(jié) ： 多 序 列 比 對 r 1， 計(jì) 分 方 法r 2， Dayhoff: PAM系 列 矩 陣r 3， Henikoff: BLOSUM系 列 矩 陣 r匹 配 計(jì) 分 ： UM矩陣(Unitary matrix)相同的氨基酸記1分，否則記0分。BLAS

2、T中核酸比對r結(jié) 構(gòu) 域 性 質(zhì) 計(jì) 分 ： SGM矩陣(Structure-Genetic Matrix) 主 要 根 據(jù) 氨 基 酸 的 結(jié) 構(gòu) 和 化 學(xué) 性 質(zhì) 的 相 似 程 度來 記 分 (如 D和 E， S和 T， V和 I有 很 高 的 相 似 性 )， 同時(shí) 還 考 慮 密 碼 子 之 間 相 互 轉(zhuǎn) 換 的 難 易 程 度 。r可 觀 測 變 換 計(jì) 分 ：PAM矩陣 (Point Accepted Mutation)BLOSUM矩陣 (BLOcks SUbstitution Matrix) r Margaret Dayhoff, 1978;r通 過 對 物 種 進(jìn) 化 的

3、 研 究 ， 根 據(jù) 一 種 氨 基 酸 被另 一 種 氨 基 酸 替 代 的 頻 度 而 提 出 的 ， 最 常 用的 是 PAM250;r Accepted point mutation (PAM): 可 接 受的 點(diǎn) 突 變 ， 氨 基 酸 的 改 變 不 顯 著 影 響 蛋 白 質(zhì)的 功 能 ； r71個(gè) 蛋 白 質(zhì) 家 族 的 1572種 變 化 ；r序 列 相 似 性 85%；r功 能 同 源 的 蛋 白 質(zhì) 通 過 中 性 進(jìn) 化 ， 引 入可 接 受 的 點(diǎn) 突 變 ；r 進(jìn) 化 模 型 ：A. 基本假設(shè)：中性進(jìn)化，Kimura,1968;B. 進(jìn)化的對稱性: A-B = B-

4、A;C. 擴(kuò)展性：通過對較短時(shí)間內(nèi)氨基酸替代關(guān)系的計(jì)算來計(jì)算較長時(shí)間的氨基酸替代關(guān)系； r 兩 個(gè) 蛋 白 質(zhì) 序 列 的 1%氨 基 酸 發(fā) 生 變 化 ；r 定 義 進(jìn) 化 時(shí) 間 以 氨 基 酸 的 變 異 比 例 為 準(zhǔn) ，而 不 是 時(shí) 間 ； 因 為 各 個(gè) 蛋 白 質(zhì) 家 族 進(jìn) 化 的 速度 并 不 相 等 ；r PAM2 = PAM1*PAM1 PAM3 = (PAM1)3 PAM250= (PAM1)250 r 選 取 多 個(gè) 家 族 的 相 似 性 85%的 保 守 序 列 ；r 根 據(jù) 匹 配 計(jì) 分 進(jìn) 行 多 重 比 對 (不 含 空 位 )；r 以 比 對 結(jié) 果

5、 構(gòu) 建 進(jìn) 化 樹 ， 反 映 氨 基 酸 替 換 關(guān)系 ；r 計(jì) 算 每 種 氨 基 酸 轉(zhuǎn) 換 成 其 它 氨 基 酸 的 次 數(shù) ；r 計(jì) 算 每 種 氨 基 酸 突 變 率 ；r 計(jì) 算 每 對 氨 基 酸 突 變 率 ， 得 到 突 變 概 率 矩 陣， 將 此 矩 陣 自 乘 n次 ；r 將 突 變 概 率 矩 陣 轉(zhuǎn) 化 為 PAMn矩 陣 。 r 已 知 3個(gè) 蛋 白 質(zhì) 家 族 若 干 保 守 序 列 片 段 ：家族一：FKILK，F(xiàn)KIKK，F(xiàn)FILL，F(xiàn)FIKL家族二：IIFFF， IIFIF ， IKFFL ， IKFIL家族三： KIFKK，KIFLK，KLFKL，

6、KLFLL按 Doyhoff方 法 構(gòu) 建 PAM1與 PAM2矩 陣 r位 置 對 齊 ， 多 重 比 對 （ 不 考 慮 空 位 ） ：r統(tǒng) 計(jì) 每 種 氨 基 酸 出 現(xiàn) 的 頻 率 ；fi = 氨 基 酸 i的 數(shù) 目 /總 氨 基 酸 數(shù) 目fL = 12/60 = 0.2. 家 族 一 家 族 二 家 族 三F K I L K I I F F F K I F K KF K I K K I I F I F K I F L KF F I L L I K F F L K L F K LF F I K L I K F I L K L F L L r最 大 簡 約 法家族一:wL和K間相互轉(zhuǎn)

7、換次數(shù)：N (LK) = 3家族二，家族三 FKILKFKIKK FKIKK FFIKLFFILLFFIKL(LK) (KF)(LK) (LK) r計(jì) 算 每 種 氨 基 酸 轉(zhuǎn) 換 成 其 它 氨 基 酸 的 次 數(shù) 。r假 設(shè) 兩 種 氨 基 酸 間 相 互 轉(zhuǎn) 換 一 樣 。e.g. N(LK)= 3 + 0 + 3 = 6K F I LK 1 1 6F 1 2 1I 1 2 1L 6 1 1 r每 種 氨 基 酸 相 對 突 變 率 miri： 第 i種 氨 基 酸 ；rfi ： 每 種 氨 基 酸 出 現(xiàn) 的 頻 率 ；mK = 8/(122 fK 100) = 0.0125 100

8、2 ii fim總替換數(shù)總共發(fā)生替換數(shù)氨基酸 r氨 基 酸 i替 換 為 j的 突 變 率 mije.g.mKK = 1- mK = 0.9875mKF = mF 1/4 = 0.001389 iii iij mmji j jimmji 1時(shí)，總共發(fā)生替換數(shù)氨基酸相互替換的次數(shù)與氨基酸時(shí)， r氨 基 酸 突 變 概 率 一 步 轉(zhuǎn) 移 概 率 矩 陣 M1ij原 氨 基 酸K F I L替 換 氨基 酸 K 0.9875 0.001563 0.001563 0.009375F 0.001389 0.994444 0.002778 0.001389I 0.001786 0.003571 0.99

9、2857 0.001786L 0.0125 0.002083 0.002083 0.983333 r由 突 變 率 mij計(jì) 算 計(jì) 分 矩 陣 中 的 分 值 rij：r將 rij = rji取 平 均 值 ， 再 取 整 數(shù) ；（ 按 先 前 假 設(shè) ， rij = rji） rKK = 10lg(mkk/ fk) = 5.6857 6 (rKF + rFK )/2 = -22.833 -23 )/lg(10 iijij fmr r三 個(gè) 家 族 序 列 片 段 得 到 的 PAM1計(jì) 分 矩 陣 ：K F I LK 6F -23 5I -22 -19 6L -13 -22 -20 7 r

10、將 氨 基 酸 突 變 概 率 矩 陣 自 乘 一 次 ， 得 到 兩步 轉(zhuǎn) 移 概 率 矩 陣 M2ij M2ij = M1ij M1ijr三 個(gè) 家 族 序 列 片 段 得 到 的 PAM2計(jì) 分 矩 陣 ：K F I LK 6F -20 5I -19 -16 6L -10 -19 -18 7 r PAM250: 250%期 望 的 突 變 ；r 蛋 白 質(zhì) 序 列 仍 然 有 15-30%左 右 的 相 似 性 ； rPAM250: 15-30%的 序 列 相 似 性；rPAM120: 40%的 序 列 相 似 性 ；rPAM80: 50%rPAM60: 60%r如 何 選 擇 最 合

11、適 的 矩 陣 ？r 多 種 嘗 試 r1. PAM系 列 矩 陣 存 在 的 問 題 ：A. 氨基酸的打分矩陣，不關(guān)心核酸；B. 進(jìn)化模型的構(gòu)建需要系統(tǒng)發(fā)育樹的分析，因此，成為一個(gè)循環(huán)論證的問題：序列比對矩陣構(gòu)建打分進(jìn)行新的序列比對；C. 數(shù)據(jù)集很??；r2. 打 分 矩 陣 的 改 進(jìn)A. 選用大量的序列數(shù)據(jù)，構(gòu)建PAM矩陣；B. BLOSUM系列矩陣;C. 核酸的打分矩陣; r最 被 廣 泛 使 用 的 氨 基 酸 打 分 矩 陣 ;r根 據(jù) 蛋 白 質(zhì) 模 塊 數(shù) 據(jù) 庫 BLOCKS中 蛋 白 質(zhì)序 列 的 高 度 保 守 部 分 的 比 對 而 得 到 的 ， 最 常用 的 是 BL

12、OSUM62;rBLOCK: 蛋 白 質(zhì) 家 族 保 守 的 一 段 氨 基 酸 ， 無gap， 一 般 幾 個(gè) 至 上 百 個(gè) 氨 基 酸 ；rProsite家 族 ： 至 少 有 一 個(gè) BLOCK存 在 于 該家 族 的 所 有 蛋 白 質(zhì) 序 列 中 ；rBLOSUM62: 序 列 的 平 均 相 似 性 為 62%的BLOCK構(gòu) 建 的 打 分 矩 陣 ； r 提 取 Prosite數(shù) 據(jù) 庫 中 504個(gè) 家 族 的 2萬 多 蛋白 質(zhì) 序 列 ， 合 并 其 中 相 似 性 62%的 序 列 ；r 統(tǒng) 計(jì) 各 BLOCK的 氨 基 酸 對 數(shù) 量 f；r 計(jì) 算 氨 基 酸 對

13、的 出 現(xiàn) 頻 率 q；r 計(jì) 算 每 種 氨 基 酸 的 期 望 頻 率 p；r 計(jì) 算 氨 基 酸 對 出 現(xiàn) 的 期 望 頻 率 e；r 計(jì) 算 BLOSUM62矩 陣 分 量 rij)/(lg2 2 eqrij r序 列 相 似 性 與 PAM及 BLOSUM矩 陣 的 大 致對 應(yīng) 關(guān) 系 ：序 列 相 似 性 % 99 90 80 70 60 50 40 30 20PAM數(shù) 值 1 11 23 38 56 80 112 159 246BLOSUM數(shù) 值 90 80 62-45 r 不 同 物 種 中 ， 許 多 基 因 的 功 能 保 守 ， 序 列 相似 性 較 高 ， 通 過

14、多 條 序 列 的 比 較 ， 發(fā) 現(xiàn) 保 守與 變 異 的 部 分 ；r 可 構(gòu) 建 HMM模 型 ， 搜 索 更 多 的 同 源 序 列 ；r 構(gòu) 建 進(jìn) 化 的 樹 的 必 須 步 驟 ；r 比 較 基 因 組 學(xué) 研 究 ；r 兩 類 ： 全 局 或 局 部 的 多 序 列 比 對 ； Made by GENEDOC GapVDSCYGap0-11-22-33-44-55V-114-7-18-29-40E-22-76-5-16-27S-33-18-510-1-12L-44-29-16-19-3C-55-40-27-1287Y-66-51-38-23-3154 2時(shí)間復(fù)雜度：O(n2)

15、三 條 序 列 ： 時(shí) 間 復(fù) 雜 度 ： O(lmn) = O(n3)四 條 序 列 ： 時(shí) 間 復(fù) 雜 度 ： O(n4)， 非 多 項(xiàng) 式 時(shí) 間 ！多項(xiàng)式時(shí)間復(fù)雜度要求：O(n3)m條 序 列 ： 時(shí) 間 復(fù) 雜 度 ： O(nm)， NPC問 題 ！ Sequence ASequence B Sequence C 搜 索 有 限 空 間 ， 類 似 于 BLAST算 法 r 最 優(yōu) 的 多 序 列 比 對 ， 其 兩 兩 序 列 之 間 的 比 對不 一 定 最 優(yōu) 。 最 優(yōu) 的 多 序 列 比 對 非 最 優(yōu) 的 雙 序 列 比 對 rMSA - Multiple Sequenc

16、e AlignmentrDavid Lipman等 ， 1989年 初 始 開 發(fā) ；r應(yīng) 用 多 維 動 態(tài) 規(guī) 劃 算 法 ， 得 到 最 優(yōu) 的 全 局比 對 。r工 具 資 源 ：http:/www.ncbi.nlm.nih.gov/CBBresearch/Schaffer/msa.htmlhttp:/www.psc.edu/general/software/packages/msa/manual/manual.php r1. 漸 進(jìn) 方 法 ： progressive methods代表：ClustalW/X, T-Coffeer2. 迭 代 方 法 ： iterative meth

17、ods 代表: PRRP, DIALIGNr3. 部 分 有 向 圖 算 法 ：Partial Order Algorithm (POA)r4. 全 局 多 序 列 比 對 的 隱 馬 爾 科 夫 模 型profile HMMr5. 整 合 算 法 ： MUSCLE r(1) ClustalW/Xr(2) T-Coffee r1. Clustal: 1988年 開 發(fā) ；r2. ClustalW: 1994年 ， Julie D. Thompson等 人 改 進(jìn) 、 發(fā) 展 ；r3. ClustalX: 1997年 ， 圖 形 化 軟 件 ； r1. 將 所 有 序 列 兩 兩 比 對 ， 計(jì)

18、 算 距 離 矩 陣 ；r2. 構(gòu) 建 鄰 接 進(jìn) 化 樹 (neighbor-joining tree)/指 導(dǎo) 樹 (guide tree)；r3. 將 距 離 最 近 的 兩 條 序 列 用 動 態(tài) 規(guī) 劃 的 算 法進(jìn) 行 比 對 ；r4. “漸 進(jìn) ” 的 加 上 其 他 的 序 列 。 兩兩比對，構(gòu)建距離矩陣指 導(dǎo) 樹 的 構(gòu) 建漸 進(jìn) 比 對 每 條 序 列 的 權(quán) 值Score:BLO SUM62的 分 數(shù) r1. FASTA序 列 格 式 ， 多 序 列 ： r BioEdit, GeneDoc等 軟 件GeneDoc軟 件 ， 導(dǎo) 入 .aln文 件 r1. 采 用 Clu

19、stal程 序 計(jì) 算 兩 兩 序 列 之 間 的 全局 最 優(yōu) 比 對 結(jié) 果 ；r2. 采 用 LALIGN程 序 計(jì) 算 兩 兩 序 列 之 間 的 局部 最 優(yōu) 比 對 的 結(jié) 果 ；r3. 設(shè) 計(jì) 加 權(quán) 系 統(tǒng) ， 綜 合 考 慮 以 上 兩 類 結(jié) 果 的因 素 ， 構(gòu) 建 指 導(dǎo) 庫 ；r4. 最 后 ， 采 用 漸 進(jìn) 式 比 對 算 法 ， 得 到 最 終 的結(jié) 果 。 同 時(shí) 進(jìn) 行 全 局 和 局 部 的雙 序 列 比 對對 以 上 打 分 的 結(jié) 果 設(shè) 計(jì)權(quán) 重 系 統(tǒng) ， 找 到 序 列 中最 保 守 的 部 分漸 進(jìn) 方 法 的 比 對 ， 基 于 上 述計(jì) 算

20、 的 primary library r1. 距 離 最 近 的 ， 有 兩 組 序 列 AB和 CD， 哪 組最 先 比 對 ？ 兩 種 方 案 ：A. 分別、同時(shí)比對。但是，是以AB為準(zhǔn)，加入CD，然后再加上其他序列，還是CD為準(zhǔn)？結(jié)果可能出入很大B. 隨機(jī)挑選一組作為基準(zhǔn)r2. 當(dāng) 序 列 差 異 較 大 時(shí) ， 上 述 問 題 更 加 明 顯 。 r1. 三 條 序 列 ：r2.若 Seq1,2先 比 對， 再 加 入 Seq3：r3. Seq1,3先 比 對 ，再 加 入 Seq2:r4. Seq2,3先 比 對 ，再 加 入 Seq1:Seq1: ARKCVSeq2: ARCVSe

21、q3: AKCVARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV r1. 部 分 解 決 漸 進(jìn) 算 法 存 在 的 問 題 ,主 要 是ClustalW/X存 在 的 問 題 ；r2. PRRPr3. DIALIGN 1. 先 用 “ 漸 進(jìn) ” 算 法 進(jìn) 行多 序 列 比 對 ;2. 基 于 多 序 列 比 對 的 結(jié) 果構(gòu) 建 進(jìn) 化 樹 ；3. 重 新 計(jì) 算 序 列 之 間 的 距離 ， 再 用 “ 漸 進(jìn) ” 算 法 進(jìn) 行多 序 列 比 對 ；4. 重 復(fù) 上 述 步 驟 ， 直 到 結(jié)果 不 再 發(fā) 生 改 變 為 止 。 r1. 對

22、 所 有 序 列 進(jìn) 行 兩 兩 之 間 的 局 部 最 優(yōu) 化 的比 對 ；r2. 找 到 所 有 能 夠 匹 配 的 部 分 M1； 將 重 疊 的、 前 后 連 續(xù) (consistency)的 匹 配 部 分 連 接起 來 (diagonals)， 為 M2；r3. 將 剩 下 的 未 比 對 的 序 列 重 新 比 對 ， 再 發(fā) 現(xiàn)能 夠 匹 配 的 部 分 ， 構(gòu) 成 新 M1， 將consistency部 分 構(gòu) 成 M2；r4. 重 復(fù) 上 述 步 驟 ， 直 到 結(jié) 果 收 斂 。 r主 要 改 進(jìn) ：1. 所 有 序 列 的 兩 兩 比 對 ， 通 過 profile H

23、MM的方 法 進(jìn) 行 雙 序 列 比 對 ；2. 將 漸 進(jìn) 算 法 與 迭 代 算 法 整 合 ；3. 目 前 ， 性 能 最 優(yōu) 。 r算 法 分 為 三 個(gè) 部 分 ， 每 個(gè) 部 分 相 對 獨(dú) 立 ；r1. Draft progressive: (1) 對兩條序列，計(jì)算距離采用k-mer的思想；(2) 用UPGMA算法構(gòu)建引導(dǎo)樹；(3) 使用漸進(jìn)算法進(jìn)行多序列比對；r優(yōu) 點(diǎn) ： 兩 條 序 列 之 間 的 距 離 不 采 用 動 態(tài) 規(guī) 劃算 法 進(jìn) 行 比 對 ， 節(jié) 省 時(shí) 間 。 r2. Improved progressive: (1)基于k-mer得到的樹可能會產(chǎn)生次優(yōu)結(jié)果

24、，因此，采用Kimura距離的方法對k-mer產(chǎn)生的樹重新計(jì)算距離矩陣；(2)重新用UPGMA構(gòu)建進(jìn)化樹；(3)使用漸進(jìn)算法進(jìn)行多序列比對； r3. Refinement: (1)隨機(jī)從進(jìn)化樹上挑出一條邊，刪除；(2)得到兩組樹，對每組樹，計(jì)算profile；(3)將兩組profile進(jìn)行比對；(4)如果最終得分提高，保留結(jié)果，否則丟棄。 r http:/ r1. BAliBASE： 基 于 蛋 白 質(zhì) 結(jié) 構(gòu) ， 將 同 一 家族 的 蛋 白 質(zhì) 序 列 進(jìn) 行 多 序 列 比 較 。r2. 檢 驗(yàn) 多 序 列 比 對 工 具 的 性 能 ： 是 否 能 夠 很好 的 重 復(fù) BAliBASE中 已 明 確 的 比 對 結(jié) 果 。 r ProbCons： 目 前 綜 合 性 能 最 好 ；r T-Coffee： 序 列 相 似 性 高 時(shí) 最 準(zhǔn) 確 ；r DIALIGN: 序 列 相 似 性 低 時(shí) 最 準(zhǔn) 確 ；r POA： 性 能 接 近 T-Coffee和 DIALIGN， 速度 最 快 ；r ClustalW/X: 最 經(jīng) 典 、 被 廣 泛 接 受 的 工 具 ；r MUSCLE: 目 前 最 流 行 的 多 序 列 比 對 工 具 ；