確率文脈自由文法とRNA

ゲノム配列・遺伝子多型解析論
第６回（2003年１１月１０日）
確率文脈自由文法とRNA
浅井潔
変形文法
変形文法の定義
• 有限個の記号
– 非終端記号（抽象的な概念）
– 終端記号（観測される文字列）
• 書き換え規則（生成規則）
– α→β の形
– 左辺は少なくとも1つの非終端記号を含む
– 書き換えは、右辺が終端記号だけになるまで続く
• 文法による配列の構文解析
– 配列の位置を文法の非終端記号に割り当てるこ
と
– 書き換えの文字列の系列を導出と呼ぶ
チョムスキー階層
句構造文法
文脈依存文法
文脈自由文法
正規文法
チョムスキー階層
• W: 非終端記号 α,β,γ: 任意の記号列
• 正規文法 (Regular Grammar; RG)
– W1 → aW2 と W3 → a
• 文脈自由文法 (Context Free Grammar; CFG)
– W→β、左辺はちょうど1個の非終端記号
– A->BC, D->a
• 文脈依存文法 (Context Dependent Grammar)
– α1Wα2 →α1βα2
• 句構造文法 (Phrase Structure Grammar)
– α1Wα2 → γ
正規文法
• 生成規則の形
– W → aW
–W→a
– W → ε （空文字列）
• 配列を左から右に発生
• 離れた位置の終端記号の相関を記述できな
い
• 一次配列のモデル
例：奇数正規文法
• S 開始非終端記号
• S → aT | bS
• T → aS | bT | ε
有限状態オートマトン
Finite State Automaton; FSA
•
•
•
•
正規文法に対応する構文解析オートマトン
有限個の状態からなる
状態は状態遷移によって互いに結合
入力文字列から一度に1記号ずつ読む
– 記号が受理されると新しい状態に遷移する
– 記号が棄却されたとき停止し、文字列を棄却する
• 正規文法と比較すると
– 状態 (FSA)
⇔ 非終端記号（正規文法）
– 状態遷移 (FSA) ⇔ 生成規則（正規文法）
決定性オートマトンと
非決定性オートマトン
• 決定性オートマトン
– 任意の状態において、特定の入力記号を受理す
る状態遷移は1個以下
– 構文解析は非常に効率的（高速）
– BLASTに使われている
• 任意の非決定性オートマトンは決定性オート
マトンに変換可能
• grep, sed, awk, vi等のテキスト検索プログラ
ムは効率的な非決定性オートマトンを使って
いる
PROSITE
• PROSITEのエントリは、モチーフの配列パ
ターンを正規表現で表現したもの
• アラインメントに対するスコアと違い、
PROSITEパターンは一致するか、しないか
の二者択一
• PROSITEは、正規文法の生物学への応用
正規文法で表現できないこと
• 回文言語
– aa, bb, abba, ababa のような、逆から読んでも同一な
文字列すべてを含む言語
• 複写言語
– aa,bb,abab, aabaab のような、同一の2個の部分からな
る文字列すべてを含む言語
• 正規文法は、その言語の一部として、回文や複写
文の文字列を発生できる
• 正規文法では回文だけを発生することはできないか
ら、正しい回文とそうでない文字列を区別できない
回文言語と複写言語
正規言語
a b a a a b
（正規文法）
回文言語
a a b b a a
（文脈自由文法）
複写言語
a a b a a b
？？？？
文脈自由文法
Context Free Grammar; CFG
• 文字列の生成の仕方
– 正規文法：
左側から右側へ
– 文脈自由文法：外側から内側へ
• 回文言語は文脈自由文法によって扱われる
– 文脈自由文法は入れ子の位置の相関を表現
– 回文言語を生成するCFGの例
S →aSa | bSb | aa | bb
導出 S → aSa → aaSaa → aabSbaa →
aabaabaa
• RNAの二次構造は、回文言語の一種
RNA２次構造
• １本鎖RNA上の互いに相補的な領域同士が
結合し、２次構造をつくる
配列
GUAAGUGCGCUCCGCUGA
2次構造
A G UCGC C U
C
G U A AGUG C G
RNAステムループのCFG
seq.1
A
G
G
A
C
A
A
C
U
G
seq.2
C
G
U
C
G
A
A
A
G
C
seq.3
C A
G
A
U xC
C xU
G xG
C A G G A A A C U G seq.1
G C U G C A A A G C seq.2
G C U G C A A C U G seq.3
X
• seq.1とseq.2は異なった配列だが、同じ塩基対のパ
ターンを持っているので同一の二次構造をとる
• seq.3は、前半はseq.2、後半はseq.1と同一だが、
似た構造をとることができない。
構文解析木 (parsing tree)
•
•
•
•
•
文脈自由文法の構文解析のエレガントな表現
構文解析木の根は開始非終端記号S
葉は配列中の終端記号
内部の節は非終端記号
部分木
– 内部の節を根とする構文解析木の断片
– 配列の連続した断片を導出する
• CFGの構文解析アルゴリズムは、より大きな部分
配列に対する最適な構文解析木を再帰的に構築
して全体に対する構文解析木を構築する
文脈自由文法の構文解析木
• ２次構造は文脈自由文法によって表現できる
構文解析木
文法規則
P→aWu | uWa | cWg | gWc
L→aW | uW | cW | gW
W→P | L
P
P
P
L
P,L,Wは非終端記号
a,c,g,uは終端記号
L
G U G C C C A C
プッシュダウン・オートマトン
• CFGはプッシュダウン・オートマトンで構文解
析できる
• 有限状態オートマトンでは、現在の状態を保
持する以外のメモリはいらなかったが、プッ
シュダウン・オートマトンでは、プッシュダウ
ン・スタックという記号に関する有限のメモリ
が必要
文脈依存文法
Context Dependent Grammar
•
•
•
•
α1Wα2 →α1βα2
複写言語は文脈依存文法を必要とする
線形有界オートマトンで構文解析できる
多項式時間の構文解析アルゴリズムは知ら
れていない
句構造文法
• 生成規則の両辺が任意の記号の組み合わ
せ
• 構文解析オートマトンはチューリング機械
• 文字列が句構造文法から導出できるかどう
かを有限時間で決定することが保証されたア
ルゴリズムは存在しない
• 可能な導出の数が無限に増加する可能性が
あるので、チューリング機械は停止する保証
がなく、実用性はない
確率文法
変形文法と確率文法
• チョムスキー階層のどの文法も、生成規則に
確率を付与することにより、確率文法となる
HMMは確率正規文法である
• HMMは通常ムーア機械として記述される
– 遷移にかかわりなく、状態から記号を出力
• 確率正規文法はミーリー機械
– 非終端記号への遷移から記号を出力
• ムーア機械とミーリー機械は互いに変換可能
• アラインメント、スコア付け、学習のアルゴリ
ズムは同一
確率文脈自由文法
• ２種類の確率
– Prob(v →yz)
• vからyとzへの遷移確率：tv(y,z)
– Prob(v →a)
• vにてaを出力する確率：ev(a)
• 学習アルゴリズム
– 期待値最大化（EM）パラメータ推定法
• HMMのBaum-Welch法に相当する
• forward-backwardアルゴリズムに相当する内側・外側アルゴリ
ズム
– 最適アラインメント推定法（CYKアルゴリズム）
• Viterbiアルゴリズムに相当する最尤推定
２次構造と文脈自由文法
• ２次構造は文脈自由文法によって表現できる
構文解析木
文法規則
P→aWu | uWa | cWg | gWc
L→aW | uW | cW | gW
W→P | L
P
P
P
L
P,L,Wは非終端記号
a,c,g,uは終端記号
L
G U G C C C A C
内側アルゴリズム
• 配列の区間[i, j]が、vを根
とする部分木によって生
成される確率α(i, j, v)を
与える
• [i, j]の幅を大きくしながら、
再帰的に求めていく
• 配列尤度
P(x|θ)=α(1,L,1)
M
M
j −1
v
y
z
1
L
i
k k+1
j
Prob(v → yz )
α (i, j , v) = ∑∑∑ α (i, k , y )α (k + 1, j , z )tv ( y, z )
y =1 z =1 k =i
外側アルゴリズム
• 配列の区間[i, j]を除く
領域に対応する部分木
の根yから、区間[i, j]に
対応するvに遷移する
確率β(i, j, v)を与える
• [i, j]の幅を小さくしなが
ら、再帰的に求めていく
• 事前にαを求めておく
必要がある
y
v
z
1
L
i
k
j j+1
あるいは
y
v
z
1
L
k
j-1 i
j
SCFGの構文解析
CYKアルゴリズム
最適のアラインメントは、プッシュダウンスタックを用
いて(i, j, v)をプッシュ、ポップし、ポインタτ(i, j, v)
を用いてトレースバックする
パラメータ再推定
• SCFGのパラメータ
– 生成規則v→yzの確率 tv(y,z) （遷移確率）
• α、β、元のtv(y,z)
– 生成規則v→aの確率 ev(a) （出力確率）
• α、β、元のev(a)
– HMMのγに相当するSCFGのγ
γ i , j (v ) =
α v (i, j ) β v (i, j )
P( x)
配列の区間[i, j]がvを根とする
部分木から生成された確率
RNA２次構造の文法規則
• ギャップ（挿入・欠失）なし
– P→xWy
– L→xW
– R→Wx
– B→SS
– S→W
– E→ε
ペアワイズ出力
左側出力
右側出力
枝分かれ
開始
終了
• WはP,L,R,B,S,Eのどれか
• x,yはa,c,g,u(リボ核酸)のどれか
２次構造とアラインメント
２次構造の表現
アラインメント

Download Report