阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

Slides:



Advertisements
Similar presentations
北海道大学 Hokkaido University 1 情報理論 講義資料 2016/06/22 情報エレクトロニクス学科共通科目・2年次・第 1 学期〔必修 科目〕 講義「情報理論」第 5 回 第 3 章 情報源のモデル [ 後半 ] 3.5 情報源のエントロピー.
Advertisements

『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
パターン認識入門.
奈良女子大集中講義 バイオインフォマティクス (3) 配列アラインメント
動的計画法を用いたアラインメント  小菅孝史.
日本バイオインフォマティクス学会 バイオインフォマティクス カリキュラム中間報告
情報生命科学特別講義III (5)配列アラインメント
生命情報学基礎論 (2) 配列の比較と相同性検索
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
情報生命科学特別講義III (1) 文字列マッチング
タンパク質相互作用ネットワークの スケールフリーモデル
奈良女子大集中講義 バイオインフォマティクス (8) タンパク質立体構造予測
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
奈良女子大集中講義 バイオインフォマティクス (6) モチーフ発見・隠れマルコフモデル
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
時空間データからのオブジェクトベース知識発見
生命情報学入門 機械学習を用いたタンパク質の分類法 2011年6月7日
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
HMM:隠れマルコフモデル 電子情報工学科 伊庭 斉志 奈良女子大集中講義 バイオインフォマティクス (6)
京都大学 化学研究所 バイオインフォマティクスセンター
ベイズ基準によるHSMM音声合成の評価 ◎橋本佳,南角吉彦,徳田恵一 (名工大).
ベイジアンネットワーク概説 第3章 ベイジアンネットワークモデルの      数学的基礎 3.5 情報量基準を用いた構造学習 岩崎唯史.
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(5) 木構造データ間の編集距離
【小暮研究会2】 「ベイズのアルゴリズム」:序章 【1,2:計量経済分析と統計分析】 【 3:ベイズ定理】
京都大学 化学研究所 バイオインフォマティクスセンター
第13章 系列データ 修士 1年 村下 昇平.
奈良女子大集中講義 バイオインフォマティクス (10) スケールフリーネットワーク
生命情報学入門 タンパク質の分類法演習 2011年6月14日
情報生命科学特別講義III (11) RNA二次構造予測
k 個のミスマッチを許した点集合マッチング・アルゴリズム
生命情報学基礎論 (5) タンパク質立体構造予測
生命情報学入門 配列のつなぎ合わせと再編成
7. 音声の認識:高度な音響モデル 7.1 実際の音響モデル 7.2 識別的学習 7.3 深層学習.
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による 化合物の性質予測(3) 配列アライメント
決定木とランダムフォレスト 和田 俊和.
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
数理科学特別講義 バイオインフォマティクスにおける 確率モデル
第9章 混合モデルとEM 修士2年 北川直樹.
京都大学 化学研究所 バイオインフォマティクスセンター
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
九州大学大学院 情報学専攻特別講義 (3) 配列解析
生  物  数  学 斉木 里恵.
分子生物情報学(2) 配列のマルチプルアライメント法
分子生物情報学(3) 確率モデル(隠れマルコフモデル)に 基づく配列解析
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
第3章 線形回帰モデル 修士1年 山田 孝太郎.
経営学研究科 M1年 学籍番号 speedster
クロスバリデーションを用いた ベイズ基準によるHMM音声合成
最尤推定・最尤法 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
京都大学 化学研究所 バイオインフォマティクスセンター
HMM音声合成における 変分ベイズ法に基づく線形回帰
ベイズ基準による 隠れセミマルコフモデルに基づく音声合成
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
人工知能特論II 第8回 二宮 崇.
JNNS-DEX-SMI-玉川 公開講座 「交換モンテカルロ法とその応用」
奈良女子大集中講義 バイオインフォマティクス (7) 進化系統樹
生命情報学 (8) 生物情報ネットワークの構造解析
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による化合物の性質予測(1) バイオインフォマティクス概観
配列解析アルゴリズム特論 配列アライメントI
分子生物情報学(0) バイオインフォマティクス
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

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

講義予定 4月14日(月): 生命情報学の基盤 4月21日(月): 配列の比較と相同性検索 4月28日(月): 進化系統樹推定 4月14日(月): 生命情報学の基盤 4月21日(月): 配列の比較と相同性検索 4月28日(月): 進化系統樹推定 5月12日(月): 隠れマルコフモデル 5月19日(月): タンパク質立体構造予測 5月26日(月)、6月2日(月): カーネル法 6月9日(月): 生物情報ネットワークの構造解析 6月16日(月): 遺伝子ネットワークの解析と制御(田村) 6月23日(月): 代謝ネットワークの堅牢性(田村) 6月30日(月): 木の編集距離(田村) 7月7日(月): タンパク質相互作用予測(林田) 7月14日(月): タンパク質複合体予測(林田) 7月17日(木): 生物データの圧縮による比較(林田)

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

配列モチーフ

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

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

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

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

Gibbs サンプリング 1. 各配列 xj からランダムに部分配列 tj を選ぶ 2. 1個の配列 xi をランダムに選ぶ 3. xi の部分列 ti’ を   に比例する確率で選ぶ 4. ti をti’ でおきかえる 5. ステップ2-4を十分な回数だけ繰り返す ( ti[j]: 部分列ti のj列目の文字 )

最尤推定、ベイズ推定、MAP推定

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

ベイズ推定とMAP推定 ベイズ推定:尤度とモデル(パラメータ)の事前確率から、ベイズの定理により、事後確率を推定 最大事後確率(MAP)推定 P(D|θ)P(θ) を最大化する θ を計算 P(θ) が一様分布なら最尤推定と同じ

不正サイコロのベイズ推定 公正サイコロと不正サイコロ 6が3回続けて出た場合の事後確率 公正: P(i|公正)=1/6 不正: P(6|不正)=1/2, P(i|不正)=1/10 for i≠6 P(公正)=0.99, P(不正)=0.01 6が3回続けて出た場合の事後確率

隠れマルコフモデル

隠れマルコフモデル(HMM) ek(b) HMM≒有限オートマトン+確率 定義 出力記号集合Σ 状態集合 S={1,2,…n} akl 出力確率 ek(b) (開始状態= 終了状態= 0)

HMMにおける基本アルゴリズム Viterbiアルゴリズム Baum-Welchアルゴリズム (EMアルゴリズム) 出力記号列から   状態列を推定 構文解析 Baum-Welchアルゴリズム   (EMアルゴリズム)   パラメータを推定 学習

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

Viterbiアルゴリズム

Viterbiアルゴリズム(1) 観測列(出力配列データ) x=x1…xLと状態列π=π1…πLが与えられた時、その同時確率は  P(x,π)=a0 π1Πeπi (xi)aπiπi+1 但し、πL+1=0 x が与えられた時、最も尤もらしい状態列は π*=argmaxπ P(x,π) 例:どちらのサイコロがいつ使われたかを推定

Viterbiアルゴリズム(2) x から、π*=argmaxπ P(x,π) を計算 そのためには x1…xi を出力し、状態 k に至る確率最大の状態列の確率 vk(i) を計算 vk(i)は以下の式に基づき動的計画法で計算

Viterbiアルゴリズム(3)

EMアルゴリズム

EM(Expectation Maximization)アルゴリズム 「欠けているデータ」のある場合の最尤推定のための一般的アルゴリズム 最大化は困難であるので、反復により尤度を単調増加させる(θtよりθt+1を計算) HMMの場合、「欠けているデータ」は状態列

EMアルゴリズムの導出

EMアルゴリズムの一般形 初期パラメータ θ0 を決定。t=0とする Q(θ|θt)=∑P(y|x, θt) log P(x,y|θ) を計算 Q(θ|θt)を最大化するθ*を計算し、     θt+1 = θ* とする。t=t+1とする Qが増大しなくなるまで、2,3を繰り返す

前向きアルゴリズム 配列 x の生成確率 P(x)=∑P(x,π) を計算 Viterbiアルゴリズムと類似 fk(i)=P(x1…xi,πi=k)  をDPにより計算

後向きアルゴリズム bk(i)= P(xi+1…xL|πi=k)  をDPにより計算 P(πi=k|x) = fk(i)bk(i)/P(x)

Viterbi と前向きアルゴリズムの比較 Forwardアルゴリズム

HMMに対するEMアルゴリズム (Baum-Welchアルゴリズム)

Baum-WelchのEMによる解釈 配列は1個のみを仮定

プロファイルHMM

配列アラインメント 2個もしくは3個以上の配列の類似性の判定に利用 文字間の最適な対応関係を求める(最適化問題) 2個の場合:ペアワイズアラインメント 3個以上の場合:マルチプルアラインメント 文字間の最適な対応関係を求める(最適化問題) 配列長が同じになるよう、ギャップ記号を挿入

プロファイルHMM (1) 配列をアラインメントするためのHMM タンパク質配列分類やドメイン予測などに有用 PFAM(http://pfam.wustl.edu/) 一致状態(M)、欠失状態(D)、挿入状態(I)を持つ

プロファイルHMM (2) マルチプル アラインメント プロファイル HMM

プロファイルHMM (3) 各配列ファミリーごとに HMM を作成 スコア最大のHMMのファミリーに属すると予測

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