中國科技大學(xué)課件系列:《生物信息學(xué)》
《中國科技大學(xué)課件系列:《生物信息學(xué)》》由會(huì)員分享,可在線閱讀,更多相關(guān)《中國科技大學(xué)課件系列:《生物信息學(xué)》(72頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第 三 章 序 列 比 對(duì) r第 一 節(jié) : 數(shù) 學(xué) 基 礎(chǔ) : 概 率 及 概 率 模 型r第 二 節(jié) : 雙 序 列 比 對(duì) 算 法 的 介 紹Dot matrix動(dòng)態(tài)規(guī)劃算法w(Needleman-Wunsch, Smith-Waterman算法) FASTA和BLAST算法r第 三 節(jié) : 打 分 矩 陣 及 其 含 義r第 四 節(jié) : 多 序 列 比 對(duì) r 1, 計(jì) 分 方 法r 2, Dayhoff: PAM系 列 矩 陣r 3, Henikoff: BLOSUM系 列 矩 陣 r匹 配 計(jì) 分 : UM矩陣(Unitary matrix)相同的氨基酸記1分,否則記0分。BLAS
2、T中核酸比對(duì)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可 觀 測(cè) 變 換 計(jì) 分 :PAM矩陣 (Point Accepted Mutation)BLOSUM矩陣 (BLOcks SUbstitution Matrix) r Margaret Dayhoff, 1978;r通 過 對(duì) 物 種 進(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)化的對(duì)稱性: A-B = B-
4、A;C. 擴(kuò)展性:通過對(duì)較短時(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) 行 多 重 比 對(duì) (不 含 空 位 );r 以 比 對(duì) 結(jié) 果
5、 構(gòu) 建 進(jìn) 化 樹 , 反 映 氨 基 酸 替 換 關(guān)系 ;r 計(jì) 算 每 種 氨 基 酸 轉(zhuǎn) 換 成 其 它 氨 基 酸 的 次 數(shù) ;r 計(jì) 算 每 種 氨 基 酸 突 變 率 ;r 計(jì) 算 每 對(duì) 氨 基 酸 突 變 率 , 得 到 突 變 概 率 矩 陣, 將 此 矩 陣 自 乘 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位 置 對(duì) 齊 , 多 重 比 對(duì) ( 不 考 慮 空 位 ) :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每 種 氨 基 酸 相 對(duì) 突 變 率 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)論證的問題:序列比對(duì)矩陣構(gòu)建打分進(jìn)行新的序列比對(duì);C. 數(shù)據(jù)集很??;r2. 打 分 矩 陣 的 改 進(jìn)A. 選用大量的序列數(shù)據(jù),構(gòu)建PAM矩陣;B. BLOSUM系列矩陣;C. 核酸的打分矩陣; r最 被 廣 泛 使 用 的 氨 基 酸 打 分 矩 陣 ;r根 據(jù) 蛋 白 質(zhì) 模 塊 數(shù) 據(jù) 庫 BLOCKS中 蛋 白 質(zhì)序 列 的 高 度 保 守 部 分 的 比 對(duì) 而 得 到 的 , 最 常用 的 是 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的 氨 基 酸 對(duì) 數(shù) 量 f;r 計(jì) 算 氨 基 酸 對(duì)
13、的 出 現(xiàn) 頻 率 q;r 計(jì) 算 每 種 氨 基 酸 的 期 望 頻 率 p;r 計(jì) 算 氨 基 酸 對(duì) 出 現(xiàn) 的 期 望 頻 率 e;r 計(jì) 算 BLOSUM62矩 陣 分 量 rij)/(lg2 2 eqrij r序 列 相 似 性 與 PAM及 BLOSUM矩 陣 的 大 致對(duì) 應(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 兩 類 : 全 局 或 局 部 的 多 序 列 比 對(duì) ; 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) 的 多 序 列 比 對(duì) , 其 兩 兩 序 列 之 間 的 比 對(duì)不 一 定 最 優(yōu) 。 最 優(yōu) 的 多 序 列 比 對(duì) 非 最 優(yōu) 的 雙 序 列 比 對(duì) rMSA - Multiple Sequenc
16、e AlignmentrDavid Lipman等 , 1989年 初 始 開 發(fā) ;r應(yīng) 用 多 維 動(dòng) 態(tài) 規(guī) 劃 算 法 , 得 到 最 優(yōu) 的 全 局比 對(duì) 。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. 全 局 多 序 列 比 對(duì) 的 隱 馬 爾 科 夫 模 型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. 將 所 有 序 列 兩 兩 比 對(duì) , 計(jì)
18、 算 距 離 矩 陣 ;r2. 構(gòu) 建 鄰 接 進(jìn) 化 樹 (neighbor-joining tree)/指 導(dǎo) 樹 (guide tree);r3. 將 距 離 最 近 的 兩 條 序 列 用 動(dòng) 態(tài) 規(guī) 劃 的 算 法進(jìn) 行 比 對(duì) ;r4. “漸 進(jìn) ” 的 加 上 其 他 的 序 列 。 兩兩比對(duì),構(gòu)建距離矩陣指 導(dǎo) 樹 的 構(gòu) 建漸 進(jìn) 比 對(duì) 每 條 序 列 的 權(quán) 值Score:BLO SUM62的 分 數(shù) r1. FASTA序 列 格 式 , 多 序 列 : r BioEdit, GeneDoc等 軟 件GeneDoc軟 件 , 導(dǎo) 入 .aln文 件 r1. 采 用 Clu
19、stal程 序 計(jì) 算 兩 兩 序 列 之 間 的 全局 最 優(yōu) 比 對(duì) 結(jié) 果 ;r2. 采 用 LALIGN程 序 計(jì) 算 兩 兩 序 列 之 間 的 局部 最 優(yōu) 比 對(duì) 的 結(jié) 果 ;r3. 設(shè) 計(jì) 加 權(quán) 系 統(tǒng) , 綜 合 考 慮 以 上 兩 類 結(jié) 果 的因 素 , 構(gòu) 建 指 導(dǎo) 庫 ;r4. 最 后 , 采 用 漸 進(jìn) 式 比 對(duì) 算 法 , 得 到 最 終 的結(jié) 果 。 同 時(shí) 進(jìn) 行 全 局 和 局 部 的雙 序 列 比 對(duì)對(duì) 以 上 打 分 的 結(jié) 果 設(shè) 計(jì)權(quán) 重 系 統(tǒng) , 找 到 序 列 中最 保 守 的 部 分漸 進(jìn) 方 法 的 比 對(duì) , 基 于 上 述計(jì) 算
20、 的 primary library r1. 距 離 最 近 的 , 有 兩 組 序 列 AB和 CD, 哪 組最 先 比 對(duì) ? 兩 種 方 案 :A. 分別、同時(shí)比對(duì)。但是,是以AB為準(zhǔn),加入CD,然后再加上其他序列,還是CD為準(zhǔn)?結(jié)果可能出入很大B. 隨機(jī)挑選一組作為基準(zhǔn)r2. 當(dāng) 序 列 差 異 較 大 時(shí) , 上 述 問 題 更 加 明 顯 。 r1. 三 條 序 列 :r2.若 Seq1,2先 比 對(duì), 再 加 入 Seq3:r3. Seq1,3先 比 對(duì) ,再 加 入 Seq2:r4. Seq2,3先 比 對(duì) ,再 加 入 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) 行多 序 列 比 對(duì) ;2. 基 于 多 序 列 比 對(duì) 的 結(jié) 果構(gòu) 建 進(jìn) 化 樹 ;3. 重 新 計(jì) 算 序 列 之 間 的 距離 , 再 用 “ 漸 進(jìn) ” 算 法 進(jìn) 行多 序 列 比 對(duì) ;4. 重 復(fù) 上 述 步 驟 , 直 到 結(jié)果 不 再 發(fā) 生 改 變 為 止 。 r1. 對(duì)
22、 所 有 序 列 進(jìn) 行 兩 兩 之 間 的 局 部 最 優(yōu) 化 的比 對(duì) ;r2. 找 到 所 有 能 夠 匹 配 的 部 分 M1; 將 重 疊 的、 前 后 連 續(xù) (consistency)的 匹 配 部 分 連 接起 來 (diagonals), 為 M2;r3. 將 剩 下 的 未 比 對(duì) 的 序 列 重 新 比 對(duì) , 再 發(fā) 現(xiàn)能 夠 匹 配 的 部 分 , 構(gòu) 成 新 M1, 將consistency部 分 構(gòu) 成 M2;r4. 重 復(fù) 上 述 步 驟 , 直 到 結(jié) 果 收 斂 。 r主 要 改 進(jìn) :1. 所 有 序 列 的 兩 兩 比 對(duì) , 通 過 profile H
23、MM的方 法 進(jìn) 行 雙 序 列 比 對(duì) ;2. 將 漸 進(jìn) 算 法 與 迭 代 算 法 整 合 ;3. 目 前 , 性 能 最 優(yōu) 。 r算 法 分 為 三 個(gè) 部 分 , 每 個(gè) 部 分 相 對(duì) 獨(dú) 立 ;r1. Draft progressive: (1) 對(duì)兩條序列,計(jì)算距離采用k-mer的思想;(2) 用UPGMA算法構(gòu)建引導(dǎo)樹;(3) 使用漸進(jìn)算法進(jìn)行多序列比對(duì);r優(yōu) 點(diǎn) : 兩 條 序 列 之 間 的 距 離 不 采 用 動(dòng) 態(tài) 規(guī) 劃算 法 進(jìn) 行 比 對(duì) , 節(jié) 省 時(shí) 間 。 r2. Improved progressive: (1)基于k-mer得到的樹可能會(huì)產(chǎn)生次優(yōu)結(jié)果
24、,因此,采用Kimura距離的方法對(duì)k-mer產(chǎn)生的樹重新計(jì)算距離矩陣;(2)重新用UPGMA構(gòu)建進(jìn)化樹;(3)使用漸進(jìn)算法進(jìn)行多序列比對(duì); r3. Refinement: (1)隨機(jī)從進(jìn)化樹上挑出一條邊,刪除;(2)得到兩組樹,對(duì)每組樹,計(jì)算profile;(3)將兩組profile進(jìn)行比對(duì);(4)如果最終得分提高,保留結(jié)果,否則丟棄。 r http:/ r1. BAliBASE: 基 于 蛋 白 質(zhì) 結(jié) 構(gòu) , 將 同 一 家族 的 蛋 白 質(zhì) 序 列 進(jìn) 行 多 序 列 比 較 。r2. 檢 驗(yàn) 多 序 列 比 對(duì) 工 具 的 性 能 : 是 否 能 夠 很好 的 重 復(fù) BAliBASE中 已 明 確 的 比 對(duì) 結(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: 目 前 最 流 行 的 多 序 列 比 對(duì) 工 具 ;
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年防凍教育安全教育班會(huì)全文PPT
- 2025年寒假安全教育班會(huì)全文PPT
- 初中2025年冬季防溺水安全教育全文PPT
- 初中臘八節(jié)2024年專題PPT
- 主播直播培訓(xùn)提升人氣的方法正確的直播方式如何留住游客
- XX地區(qū)機(jī)關(guān)工委2024年度年終黨建工作總結(jié)述職匯報(bào)
- 心肺復(fù)蘇培訓(xùn)(心臟驟停的臨床表現(xiàn)與診斷)
- 我的大學(xué)生活介紹
- XX單位2024年終專題組織生活會(huì)理論學(xué)習(xí)理論學(xué)習(xí)強(qiáng)黨性凝心聚力建新功
- 2024年XX單位個(gè)人述職述廉報(bào)告
- 一文解讀2025中央經(jīng)濟(jì)工作會(huì)議精神(使社會(huì)信心有效提振經(jīng)濟(jì)明顯回升)
- 2025職業(yè)生涯規(guī)劃報(bào)告自我評(píng)估職業(yè)探索目標(biāo)設(shè)定發(fā)展策略
- 2024年度XX縣縣委書記個(gè)人述職報(bào)告及2025年工作計(jì)劃
- 寒假計(jì)劃中學(xué)生寒假計(jì)劃安排表(規(guī)劃好寒假的每個(gè)階段)
- 中央經(jīng)濟(jì)工作會(huì)議九大看點(diǎn)學(xué)思想強(qiáng)黨性重實(shí)踐建新功