生命情報学

Size: px

Start display at page:

Download "生命情報学"

まなぜんじゅう
5 years ago
Views:

1 生命情報学 5 隠れマルコフモデル阿久津達也京都大学化学研究所バイオインフォマティクスセンター

2 内容配列モチーフ最尤推定ベイズ推定 M 推定隠れマルコフモデル HMM Verアルゴリズム EMアルゴリズム Baum-Welchアルゴリズム前向きアルゴリズム後向きアルゴリズムプロファイル HMM

3 配列モチーフ

4 モチーフ発見配列モチーフ : 同じ機能を持つ遺伝子配列などに見られる共通の文字列パターン正規表現など文法表現を用いるもの例 : ロイシンジッパーモチーフ L-6-L-6-L-6-L ジンクフィンガーモチーフ C-2,4-C-3-[LIVMFYWC]-8-H-3,5-H 人間にとってわかりやすいが表現力が弱い確率的な表現法を用いるもの重み行列プロファイル C.5.3 HMM 隠れマルコフモデル人間にとってわかりにくいが一般に表現力は高い G T C G G score C

5 モチーフの例ジンクフィンガーモチーフ C-2,4-C-3-[LIVMFYWC]-8-H-3,5-H ロイシンジッパーモチーフ L-6-L-6-L-6-L

6 局所マルチプルアラインメント複数配列と長さ L が与えられた時スコア最大となるように各配列から長さ L の部分列を抽出モチーフ発見などに有用 Sequence T C G G T Sequence 2 T C C G T Sequence 3 T T C G G

7 相対エントロピースコアのもとでの局所マルチプルアラインメント相対エントロピースコアの定義 f a: モチーフ領域の列目における a の出現頻度 pa: a の出現頻度事前確率 L: モチーフ領域の長さ score L a f alog f a p a 実用的アルゴリズム Gs サンプリング, EM アルゴリズム

8 Gs サンプリング. 各配列からランダムに部分配列を選ぶ 2. 個の配列をランダムに選ぶ 3. の部分列を f ' [ ] L p ' [ ] に比例する確率で選ぶ 4. をでおきかえる 5. ステップ 2-4 を十分な回数だけ繰り返す []: 部分列の列目の文字 Sep Sep 2-3 roalsc Search Sep 4

9 最尤推定ベイズ推定 M 推定

10 最尤推定 D 尤度モデルパラメータのもとでのデータ D の出現確率最尤法例 D を最大化するを選ぶコインを5 回投げて表が3 回出た後裏が2 回出た p 表 a, p 裏 -a とすると Da 3 -a 2 a3/5の時 D は最大一般に表が出る頻度を f とすると af で尤度は最大

11 ベイズ推定と M 推定ベイズ推定 : 尤度とモデルパラメータの事前確率からベイズの定理により事後確率を推定 D D D ただし D ' D ' ' が連続値の時最大事後確率 M 推定 D を最大化するを計算が一様分布なら最尤推定と同じ

12 不正サイコロのベイズ推定公正サイコロと不正サイコロ公正 : 公正 /6 不正 : 6 不正 /2, 不正 /0 for 6 公正 0.99, 不正が 3 回続けて出た場合の事後確率不正不正不正

13 隠れマルコフモデル

14 隠れマルコフモデル HMM HMM 有限オートマトン確率定義出力記号集合 Σ 状態集合 S{,2, n} 遷移確率 l a l 出力確率 e 開始状態終了状態 0 : 0.2 B: : 0. B: 0.9 : 0.7 B: 0.3

15 HMM における基本アルゴリズム Ver アルゴリズム出力記号列から状態列を推定構文解析 Baum-Welch アルゴリズム EM アルゴリズム出力記号列からパラメータを推定学習 BBBBB : 0.2 B: BBBBB BBBBB BBBBBBB BBBBB : 0.2 B: 0.8 : 0. B: 0.9 : 0.7 B: : 0. B: 0.9 : 0.7 B: 0.3

16 時々いかさまをするカジノサイコロの出目だけが観測可能どちらのサイコロを振っているかは観測不可能サイコロの出目からどちらのサイコロを振っているかを推定 6,2,6,6,3,6,6,6, 4,6,5,3,6,6,,2 不正サイコロ 6,,5,3,2,4,6,3, 2,2,5,4,,6,3,4 公正サイコロ 6,6,3,6,5,6,6,, 5,4,2,3,6,,5,2 : /6 2: /6 3: /6 4: /6 5: /6 6: /6 途中で公正サイコロに交換公正サイコロ : /0 2: /0 3: /0 4: /0 5: /0 6: /2 不正サイコロ

17 Ver アルゴリズム

18 Ver アルゴリズム観測列出力配列データ L と状態列 ππ π L が与えられた時その同時確率は,πa 0 π Πe π a ππ 但し π L 0 が与えられた時最も尤もらしい状態列は π * argma π,π 例 : どちらのサイコロがいつ使われたかを推定 0.95 公不公公公不不不 ma π 2 3, π, 公公公

19 Ver アルゴリズム 2 から π * argma π,π を計算そのためにはを出力し状態に至る確率最大の状態列の確率 v を計算 v ma e a π π π v は以下の式に基づき動的計画法で計算 π v l ma l e v a l

20 Ver アルゴリズム公不公不公不公不 v 公 ma{ 0.95, 0. e 公 v 公 e 公 v 不 }

21 EM アルゴリズム

22 EMEpecaon Mamzaon アルゴリズム欠けているデータのある場合の最尤推定のための一般的アルゴリズム : 観測データ y : パラメータ集合目標 : log : 欠けているデータ log,y の最大化最大化は困難であるので反復により尤度を単調増加させるよりを計算 HMM の場合欠けているデータは状態列 y

23 EM アルゴリズムの導出とすれば尤度は増大よって最後の項は相対エントロピーで常に正なのでとおくと右辺第項ををかけてについての和をとり両辺に arg ma log log,, log, log log, log,, log, log,, log, log log y y y Q Q Q y y y Q Q Q y y y y y y y y

24 EM アルゴリズムの一般形. 初期パラメータ Θ 0 を決定 0とする 2. Q y, log,y を計算 3. Q を最大化する * を計算し * とするとする 4. Qが増大しなくなるまで 2,3を繰り返す

25 前向きアルゴリズム配列の生成確率,π を計算 Ver アルゴリズムと類似 f,π を D により計算 f f 0 l 0, f 2 3 e l a a2 a3 f 0 0 L 2 3 f a f f f f a e a a2 a3 l

26 後向きアルゴリズム l l l l l e a e a a L 0 0 L π を D により計算 π f / a a2 a e a e a e a

27 Ver と前向きアルゴリズムの比較 a n,π π π π, Ver アルゴリズム ma π {,π } e Forward アルゴリズム a a2 a22 2 e, e,b a2 e2, e2,c B C π {,π } Π for BC { 2, 22, 22,222 }

28 HMM に対する EM アルゴリズム Baum-Welch アルゴリズム { } l l l f f l E e a 文字が状態から現れる回数の期待値番目の配列が使われる回数の期待値 l E a l : : : ' ' ' ' ˆ ˆ l l l l E E e a パラメータの更新式

29 Baum-Welch の EM による解釈 [ ] ' ' 0 0 0,, ' log log log log log,,, log,, l l l l M M l l l M M M M l l l π π M M l π l π M a E E e p q q p a e E a e E a e π π π Q π π Q E π l の時最大よりはここでよりおよび

30 プロファイル HMM

31 配列アラインメント 2 個もしくは 3 個以上の配列の類似性の判定に利用 2 個の場合 : ペアワイズアラインメント 3 個以上の場合 : マルチプルアラインメント文字間の最適な対応関係を求める最適化問題配列長が同じになるようギャップ記号を挿入 HB_HUMN VGHGEY HBB_HUMN VNVDEV MYG_HYC VEDVGH GLB5_ETM VYSTYET LGB2_LULU FNNIKH GLB_GLYDI IGDNGGV HB_HUMN V G - - H G E Y HBB_HUMN V N V D E V MYG_HYC V E - - D V G H GLB5_ETM V Y S - - T Y E T LGB2_LULU F N - - N I K H GLB_GLYDI I G D N G G V

32 プロファイル HMM 配列をアラインメントするためのHMM タンパク質配列分類やドメイン予測などに有用例 : ドメインの種類ごとに HMM を作る FMhp://pfam.wusl.edu/ 一致状態 M 欠失状態 D 挿入状態 I を持つ D D D I I I I BEGIN M M M END

33 プロファイル HMM 2 マルチプルアラインメントプロファイル HMM こうもり M M G M C D D D ラットネコ - G - G - C - I I I I ハエ - - C ヤギ G C BEGIN M M M END

34 プロファイル HMM 3 各配列ファミリーごとに HMM を作成スコア最大の HMM のファミリーに属すると予測 Known Seq. Tranng Daa class EM HMM Ver Score 9.5 wn! New Seq. Tes Daa class 2 EM HMM2 Ver Score 5.8

35 まとめ配列モチーフ局所マルチプルアラインメント Gs サンプリング HMM による配列解析最尤推定ベイズ推定 M 推定隠れマルコフモデル HMM Ver アルゴリズム Baum-Welch アルゴリズム EM アルゴリズムに基づく前向きアルゴリズム後向きアルゴリズムプロファイル HMM

5_motif 公開版.ppt

5_motif 公開版.ppt 配列モチーフ機能ドメイン機能部位機能的構造的に重要な部位は進化の過程で保存される傾向がある進化的に保存されたドメイン配列モチーフ機能ドメイン中の特徴的な保存配列パターンマルチプルアライメントから抽出配列モチーフの表現方法パターンプロファイル 2 n n n n n n n n ENCODE n PROSITE パターンの例 n C-x(2,4)-C-x(3)-[LIVMFYWC]-x(8)-H-x(3,5)-H.