生命情報学

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

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

配列モチーフ

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

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

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

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

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

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

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

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

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

隠れマルコフモデル

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

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

時々いかさまをするカジノ サイコロの出目だけが観測可能 どちらのサイコロを振っているかは観測不可能 サイコロの出目から どちらのサイコロを振っているかを推定 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.95 0.9 公正サイコロ 0.05 0. : /0 2: /0 3: /0 4: /0 5: /0 6: /2 不正サイコロ

Ver アルゴリズム

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

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

Ver アルゴリズム 3 0.95 公 0.05 0. 0.9 不 - 4 6 公 不 0. 0.95 0.05 0.9 公 不 0. 0.95 0.05 0.9 公 不 v 公 ma{ 0.95, 0. e 公 v 公 e 公 v 不 }

EM アルゴリズム

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

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

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

前向きアルゴリズム 配列 の生成確率,π を計算 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 0 2 3 a e a a2 a3 l

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

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 }

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 パラメータの更新式

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 の時 最大より はここでより および

プロファイル HMM

配列アラインメント 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

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

プロファイル 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

プロファイル 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

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