分子生物情報学(3) 確率モデル(隠れマルコフモデル)に 基づく配列解析

Slides:



Advertisements
Similar presentations
パターン認識入門.
Advertisements

奈良女子大集中講義 バイオインフォマティクス (3) 配列アラインメント
動的計画法を用いたアラインメント  小菅孝史.
情報生命科学特別講義III (5)配列アラインメント
生命情報学基礎論 (2) 配列の比較と相同性検索
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
情報生命科学特別講義III (1) 文字列マッチング
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
奈良女子大集中講義 バイオインフォマティクス (8) タンパク質立体構造予測
Pattern Recognition and Machine Learning 1.5 決定理論
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
奈良女子大集中講義 バイオインフォマティクス (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年 村下 昇平.
生命情報学入門 タンパク質の分類法演習 2011年6月14日
情報生命科学特別講義III (11) RNA二次構造予測
7. 音声の認識:高度な音響モデル 7.1 実際の音響モデル 7.2 識別的学習 7.3 深層学習.
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による 化合物の性質予測(3) 配列アライメント
九州大学大学院 情報学専攻特別講義 (9) ブーリアンネットワークの 解析と制御
決定木とランダムフォレスト 和田 俊和.
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
数理科学特別講義 バイオインフォマティクスにおける 確率モデル
第9章 混合モデルとEM 修士2年 北川直樹.
教師なしデータ 学習データ  X1, X2, …, Xn   真の情報源 テストデータ  X  .
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
九州大学大学院 情報学専攻特別講義 (3) 配列解析
分子生物情報学(2) 配列のマルチプルアライメント法
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
情報生命科学特別講義III (13) 固定パラメータアルゴリズムと 部分k木
サポートベクターマシンを用いた タンパク質スレッディングの ためのスコア関数の学習 情報科学科4年 81025G 蓬来祐一郎.
ベイズ・アプローチによる グラフィカル・テスト理論
九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木
ベイジアンネットワーク概説 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) 進化系統樹
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
生物情報ソフトウェア特論 (10)固定パラメータアルゴリズムと 部分k木
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による化合物の性質予測(1) バイオインフォマティクス概観
配列解析アルゴリズム特論 配列アライメントI
分子生物情報学(0) バイオインフォマティクス
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

分子生物情報学(3) 確率モデル(隠れマルコフモデル)に 基づく配列解析 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

内容 最尤法、ベイズ推定、MAP推定 隠れマルコフモデルによる推定 文脈自由文法によるRNA二次構造予測

バイオインフォマティクスにおける確率統計 重要なのはデータからのモデル(もしくはパラメータ)の推定 最尤法 ベイズ推定 最大事後確率推定(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アルゴリズム) 出力記号列から状態列を推定 Parsing(構文解析) Baum-Welchアルゴリズム   (EMアルゴリズム) 出力記号列からパラメータを推定 Learning(学習)

時々いかさまをするカジノ サイコロの出目だけが観測可能、どちらのサイコロを振っているかは観測不可能 サイコロの出目から、どちらのサイコロを振っているかを推定 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 アルゴリズム(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(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により計算

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

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

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

Baum-WelchのEMによる解釈

配列アライメント 2個もしくは3個以上の配列の類似性の判定に利用 文字間の最適な対応関係を求める(最適化問題) 2個の場合:ペアワイズアライメント 3個以上の場合:マルチプルアライメント 文字間の最適な対応関係を求める(最適化問題) 配列長を同じにするように、ギャップ記号(挿入、欠失に対応)を挿入 入力配列が定数個(実用上は3個まで)の場合は動的計画法で多項式時間で最適解を計算可能、それ以外の場合はNP困難

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

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

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

講義のまとめ(HMM) HMMによる配列解析 最尤推定、ベイズ推定、MAP推定 隠れマルコフモデル(HMM) Viterbiアルゴリズム EMアルゴリズム Baum-Welchアルゴリズム、 前向きアルゴリズム、後向きアルゴリズム プロファイルHMM 参考文献 阿久津、浅井、矢田 訳: バイオインフォマティクス -確率モデルによる遺伝子配列解析―、医学出版、2001