確率的文脈自由文法

理論言語学と計算言語学では、確率文脈自由文法( PCFG )は、隠れマルコフモデルが正規文法を拡張するのと同様に、文脈自由文法を拡張します。各生成規則には確率が割り当てられます。導出 (構文解析) の確率は、その導出で使用される生成規則の確率の積です。これらの確率はモデルのパラメータと見なすことができ、大規模な問題では、機械学習によってこれらのパラメータを学習すると便利です。確率文法の妥当性は、トレーニング データセットのコンテキストによって制約されます。

PCFG は文法理論から生まれ、自然言語処理からRNA分子の構造の研究、プログラミング言語の設計まで、さまざまな分野に応用されています。効率的な PCFG を設計するには、スケーラビリティと汎用性の要素を考慮する必要があります。文法の曖昧さなどの問題を解決する必要があります。文法の設計は結果の精度に影響します。文法解析アルゴリズムには、さまざまな時間とメモリ要件があります。

導出: 文法から文字列を再帰的に生成するプロセス。

解析:オートマトンを使用して有効な導出を見つけます。

解析ツリー:文法をシーケンスに合わせます。

PCFG文法のパーサーの例としては、プッシュダウンオートマトンがある。このアルゴリズムは、スタックのような方法で左から右へ文法の非終端記号を解析する。この力ずくのアプローチはあまり効率的ではない。RNA二次構造予測では、Cocke-Younger-Kasami（CYK）アルゴリズムの変種が、プッシュダウンオートマトンよりも効率的な文法解析の代替手段を提供している。^{[1] PCFGパーサーの別の例としては、} Treebankを使用してトレーニングされたスタンフォード統計パーサーがある。^[2]

CFGと同様に、確率的文脈自由文法G は 次の 5 つの要素で定義できます。

${\displaystyle G=(M,T,R,S,P)}$

どこ

• Mは 非終端記号の集合である
• Tは 終端記号の集合である
• Rは 生成規則の集合である
• Sは 開始記号です
• Pは 生成規則の確率の集合である

PCFG モデルは、隠れマルコフモデルが正規文法を拡張するのと同じ方法で文脈自由文法を拡張します。

Inside -Outside アルゴリズムは、 Forward-Backward アルゴリズムに類似しています。これは、何らかの PCFG に基づいて、特定のシーケンスと一致するすべての導出の合計確率を計算します。これは、PCFG がシーケンスを生成する確率に相当し、シーケンスが特定の文法とどの程度一致しているかを直感的に測定します。Inside-Outside アルゴリズムは、モデルのパラメータ化で使用され、RNA の場合にトレーニング シーケンスから観測された以前の頻度を推定します。

CYK アルゴリズムの動的プログラミングのバリエーションは、PCFG モデルの RNA シーケンスのViterbi 解析を見つけます。この解析は、指定された PCFG によるシーケンスの最も可能性の高い導出です。

文脈自由文法は、自然言語をモデル化する試みからヒントを得た一連の規則として表現されます。^{[3] [4] [5]規則は絶対的であり、}バッカス・ナウア記法として知られる典型的な構文表現を持ちます。生成規則は終端記号と非終端記号のSで構成され、空白も終点として使用できます。CFG と PCFG の生成規則では、左側には非終端記号が 1 つだけありますが、右側には終端記号または非終端記号の任意の文字列を指定できます。PCFG ではヌルは除外されます。^[1]文法の例: ${\displaystyle \left\{a,b\right\}}$${\displaystyle \epsilon }$

${\displaystyle S\to aS,S\to bS,S\to \epsilon }$

この文法は、「|」（または）文字を使用して次のように短縮できます。

${\displaystyle S\to aS|bS|\epsilon }$

文法における終端記号は単語であり、文法規則によって非終端記号は終端記号および/または非終端記号の文字列に変換されます。上記の文法は、「非終端記号Sから始まる出力はaまたはbまたは」のいずれかを生成できると解釈されます。その導出は次のとおりです。 ${\displaystyle \epsilon }$

${\displaystyle S\Rightarrow aS\Rightarrow abS\Rightarrow abbS\Rightarrow abb}$

あいまいな文法を同形異義語に適用すると、同じ単語の並びが複数の解釈を持つ可能性があるため、あいまいな解析結果になることがあります。新聞の見出し「イラクの首長が武器を求める」などのしゃれ文は、あいまいな解析の例です。

曖昧な構文解析に対処する戦略の 1 つは (パーニニの時代に文法学者によって考案された)、さらに多くの規則を追加するか、規則に優先順位を付けて 1 つの規則が他の規則よりも優先されるようにすることです。ただし、これには規則が増殖し、管理が困難になることが多いという欠点があります。もう 1 つの問題は、過剰生成で、許可されていない構造も生成されることです。

確率的文法は、さまざまな生成を頻度の重みに基づいてランク付けすることでこれらの問題を回避し、「最も可能性の高い」(勝者総取り) 解釈をもたらします。通時的変化で使用パターンが変化すると、これらの確率的ルールを再学習して文法を更新することができます。

生成規則に確率を割り当てると、PCFG が作成されます。これらの確率は、モデル化される言語と類似した構成のトレーニング セットの分布を観察することによって通知されます。広範な言語のほとんどのサンプルでは、​​確率がデータから推定される確率文法は、通常、手動で作成された文法よりも優れています。PCFG と比較すると、CFG は RNA 構造予測には適用できません。なぜなら、CFG は配列構造の関係を組み込んでいるものの、配列構造の可能性を明らかにするスコアリング メトリックが欠けているからです^[6]

重み付き文脈自由文法（WCFG ）は、文脈自由文法のより一般的なカテゴリであり、各生成規則には数値の重みが関連付けられています。WCFG内の特定の構文解析木の重みは、木内のすべての規則の重みの積^[7]（または合計^[8]）です。各規則の重みは、木で規則が使用される回数だけ含まれます。WCFGの特殊なケースはPCFGであり、重みは（^{[9] [10]}の対数）確率です。

CYK アルゴリズムの拡張バージョンを使用すると、WCFG が与えられた場合に、文字列の「最も軽い」(最小の重み) 導出を見つけることができます。

木の重みがルールの重みの積である場合、WCFGとPCFGは同じ確率分布の集合を表現できる。^[7]

1990年代以降、PCFGはRNA構造のモデル化に応用されてきました。^{[11] [12] [13] [14] [15]}

エネルギー最小化^{[16] [17]}とPCFGは、同等の性能でRNAの二次構造を予測する方法を提供します。^{[11] [12] [1]}しかし、PCFGによる構造予測は、最小自由エネルギー計算ではなく確率的にスコア付けされます。PCFGモデルパラメータは、エネルギー最小化法の場合のように実験的に決定するのではなく、RNA構造のデータベースで観察されたさまざまな特徴の頻度から直接導出されます^{[6] 。 [18] [19]}

PCFG でモデル化できるさまざまな構造のタイプには、長距離相互作用、ペアワイズ構造、その他のネスト構造などがあります。ただし、擬似結び目はモデル化できません。^{[11] [12] [1]} PCFG は、各生成ルールに確率を割り当てることで CFG を拡張します。文法からの最大確率解析ツリーは、最大確率構造を意味します。RNA は一次配列にわたって構造を保持するため、比較配列分析からの進化情報と、そのような確率に基づく構造の妥当性に関する生物物理学的知識を組み合わせることで、RNA 構造予測を導くことができます。また、PCFG ルールを使用した構造相同体の検索結果は、PCFG 導出確率に従ってスコア付けされます。したがって、塩基対と一本鎖領域の動作をモデル化するための文法の構築は、関連する RNA の構造的多重配列アライメントの特徴を調査することから始まります。^[1]

${\displaystyle S\to aSa|bSb|aa|bb}$

上記の文法は、外側から内側への形式で文字列を生成します。つまり、終端の最も遠い端にある塩基対が最初に導出されます。したがって、次のような文字列は、内側に移動する前に、両側の 遠位のaを最初に生成することによって導出されます。${\displaystyle アバアバ}$

${\displaystyle S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabaabaa}$

PCFGモデルの拡張性により、RNAのさまざまな特徴に関する期待を組み込むことで構造予測を制約することができます。このような期待は、例えばRNAが特定の構造を想定する傾向を反映している可能性があります。^[6] しかし、組み込む情報が多すぎるとPCFGのスペースとメモリの複雑さが増す可能性があるため、PCFGベースのモデルはできるだけシンプルであることが望ましいです。^{[6] [20]}

文法が生成するすべての可能な文字列x には、PCFG モデルが与えられた場合の確率の重みが割り当てられます。したがって、すべての可能な文法生成に対するすべての確率の合計は となります 。各ペアおよび非ペア残基のスコアは、二次構造形成の可能性を説明します。生成規則では、ループ長と塩基対の積み重ね順序のスコアリングも許可されるため、文法からの準最適な構造を含むすべての可能な生成の範囲を探索し、スコアしきい値に基づいて構造を受け入れたり拒否したりすることができます。^{[1] [6]}${\displaystyle P(x|\theta )}$${\displaystyle \theta}$${\displaystyle \sum _{\text{x}}P(x|\theta )=1}$

PCFG アプローチに基づく RNA 二次構造の実装は、次の場合に利用できます。

• MSA上の構造結合確率を最適化することによってコンセンサス構造を見つける。^{[20] [21]}
• データベース検索における相同性検出のための塩基対共変動のモデル化。^[11]
• 一対の同時折り畳みと整列。^{[22] [23]}

これらのアプローチにはさまざまな実装があります。たとえば、Pfoldは関連するRNA配列のグループからの二次構造予測に使用され、^[20]共分散モデルは相同配列のデータベース検索やRNAの注釈と分類に使用され、^{[11] [24]} RNApromo、CMFinder、TEISERはRNAの安定した構造モチーフを見つけるために使用されます。^{[25] [26] [27]}

PCFG の設計は二次構造予測の精度に影響します。PCFG に基づく有用な構造予測確率モデルは、予測精度をあまり損なうことなくシンプルさを維持する必要があります。単一配列で優れたパフォーマンスを発揮するモデルが複雑すぎると、拡張できない可能性があります。^[1]文法ベースのモデルは次のことができる必要があります。

• シーケンスと PCFG 間の最適なアライメントを見つけます。
• シーケンスとサブシーケンスの構造の確率をスコア付けします。
• シーケンス/構造をトレーニングしてモデルをパラメータ化します。
• 最適な文法解析ツリー (CYK アルゴリズム) を見つけます。
• あいまいな文法をチェックします (条件付き内部アルゴリズム)。

文法ごとに複数の構文解析ツリーが生成されると、文法の曖昧さが示されます。これは、文法のすべての可能な塩基対構造を明らかにするのに役立つ場合があります。ただし、最適な構造とは、構文解析ツリーと二次構造の間に 1 つの対応のみが存在する構造です。

2 種類のあいまいさを区別できます。構文解析ツリーのあいまいさと構造のあいまいさです。構造のあいまいさは、熱力学的アプローチには影響しません。最適な構造の選択は常に最低の自由エネルギースコアに基づいて行われるためです。 ^[6]構文解析ツリーのあいまいさは、シーケンスごとに複数の構文解析ツリーが存在することに関係しています。このようなあいまいさは、すべての可能な構文解析ツリーを生成してから最適なものを見つけることで、シーケンスのすべての可能な塩基対構造を明らかにすることができます。 ^{[28] [29] [30]}構造のあいまいさの場合、複数の構文解析ツリーが同じ二次構造を記述します。これにより、構文解析ツリーと構造の対応が一意ではないため、最適な構造を見つけるという CYK アルゴリズムの決定が不明瞭になります。^[31]文法のあいまいさは、条件付き内部アルゴリズムによってチェックできます。^{[1] [6]}

確率的文脈自由文法は、終端変数と非終端変数で構成されます。モデル化される各機能には、RNA 構造のトレーニング セットから推定された確率が割り当てられる生成規則があります。生成規則は、終端残基のみが残るまで再帰的に適用されます。

開始の非終端記号はループを生成します。文法の残りの部分は、ループがステムの開始であるか、または一本鎖領域の開始であるかを決定するパラメータと、ペアになった塩基を生成するパラメータに従って進行します。 ${\displaystyle \mathbf {\mathit {S}} }$${\displaystyle \mathbf {\mathit {L}} }$${\displaystyle \mathbf {\mathit {F}} }$

この単純な PCFG の形式は次のようになります。

${\displaystyle {\mathit {S\to LS|L}}}$

${\displaystyle {\mathit {L\to s|dFd}}}$

${\displaystyle {\mathit {F\to dFd|LS}}}$

PCFGを構造予測に適用するには、複数のステップが必要です。さらに、PCFG自体は、RNAの進化史を考慮したり、データベース内の相同配列を検索したりする確率モデルに組み込むことができます。進化史の文脈では、構造アラインメントのRNA構造の事前分布をPCFGの生成ルールに含めることで、優れた予測精度が得られます。^[21]

さまざまなシナリオで PCFG を利用するための一般的な手順の概要:

• シーケンスの生成ルールを生成します。
• 曖昧さをチェックします。
• 文法を使用して、可能な構造の解析ツリーを再帰的に生成します。
• 最も妥当なシーケンスの構文解析木をランク付けしてスコア付けする。^[1]

RNA 構造予測における PCFG ベースの確率モデルの側面を扱うアルゴリズムはいくつか存在する。たとえば、inside-outside アルゴリズムや CYK アルゴリズムなどである。inside-outside アルゴリズムは、期待値最大化パラダイムに従うことができる再帰動的プログラミング スコアリング アルゴリズムである。これは、何らかの PCFG に基づいて、特定のシーケンスと一致するすべての導出の合計確率を計算する。inside 部分は、構文解析ツリーからサブツリーをスコアリングし、したがって PCFG が与えられた場合のサブシーケンス確率をスコアリングする。outside 部分は、完全なシーケンスの完全な構文解析ツリーの確率をスコアリングする。^{[32] [33]} CYK は、inside-outside スコアリングを修正したものである。「CYK アルゴリズム」という用語は、PCFG を使用してシーケンスの最適な構文解析ツリーを見つける inside アルゴリズムの CYK バリアントを表していることに注意してください。これは、非確率 CFG で使用される実際のCYK アルゴリズムを拡張したものです。 ^[1]

内側のアルゴリズムは、部分シーケンス について、をルートとする 構文解析部分木全体の確率を計算します。外側のアルゴリズムは、 の計算を除いて、ルートからシーケンスxの完全な構文解析木の確率を計算します。変数αとβ は、 PCFG の確率パラメータの推定を精緻化します。モデル が与えられた場合のシーケンスxの確率で割ったαとβの積をすべて合計することで、導出で状態が使用される期待回数を見つけることで、PCFG アルゴリズムを再推定することができます。また、 αとβの値を利用する期待最大化によって、生成規則が使用される期待回数を見つけることも可能です。^{[32] [33]} CYK アルゴリズムは、最も確率の高い構文解析木を見つけるために を計算し、 を生成します。^[1]${\displaystyle \alpha (i,j,v)}$${\displaystyle i,j,v}$${\displaystyle W_{v}}$${\displaystyle x_{i},...,x_{j}}$${\displaystyle \beta (i,j,v)}$${\displaystyle x_{i},...,x_{j}}$${\displaystyle P(x|\theta )}$${\displaystyle \gamma (i,j,v)}$${\displaystyle {\hat {\pi}}}$${\displaystyle \log P(x,{\hat {\pi }}|\theta )}$

RNA 構造予測における一般的な PCFG アルゴリズムのメモリと時間の複雑さは、それぞれ と です。PCFGを制限すると、データベース検索方法の場合と同様に、この要件が変わる可能性があります。 ${\displaystyle O(L^{2}M)}$${\displaystyle O(L^{3}M^{3})}$

共分散モデル（CM）は、ホモログ、アノテーション、RNA分類のデータベース検索に応用される特殊なタイプのPCFGです。CMを使用すると、関連するRNAをコンセンサス二次構造で表すことができるPCFGベースのRNAプロファイルを構築できます。^{[11] [12]} RNA解析パッケージInfernalは、RNAアラインメントの推論にこのようなプロファイルを使用します。^[34] Rfamデータベースも、構造と配列情報に基づいてRNAをファミリーに分類するためにCMを使用します。^[24]

CMはコンセンサスRNA構造から設計されています。CMはアラインメント内で無制限の長さのインデルを許可します。ターミナルはCM内の状態を構成し、インデルが考慮されない場合は状態間の遷移確率は1です。^[1] CMの文法は次のとおりです。

${\displaystyle P\to aWb}$

16 通りのペア間の相互作用の確率

${\displaystyle L\to aW}$

左側の4つの可能な単一塩基を生成する確率

${\displaystyle R\to Wa}$

右側の4つの可能な単一塩基を生成する確率

${\displaystyle B\to SS}$

確率1の分岐

${\displaystyle S\to W}$

確率1から始まる

${\displaystyle E\to \epsilon }$

確率1で終了

このモデルには6つの可能な状態があり、各状態文法には非終端の異なるタイプの二次構造確率が含まれています。状態は遷移によって接続されています。理想的には、現在のノード状態はすべての挿入状態に接続され、後続のノード状態は非挿入状態に接続されます。複数の塩基の挿入を可能にするために、挿入状態はそれ自体に接続されます。^[1]

CM モデルをスコアリングするために、インサイドアウトサイドアルゴリズムが使用されます。CM は CYK のわずかに異なる実装を使用します。最適な構文解析ツリーのログオッズ放出スコアは、放出状態から計算されます。これらのスコアはシーケンス長の関数であるため、最適な構文解析ツリー確率スコアを回復するためのより識別的な尺度は、整列されるシーケンスの最大長を制限し、ヌルに対するログオッズを計算することによって達成されます。このステップの計算時間はデータベースのサイズに比例し、アルゴリズムのメモリ複雑度は です。^[1]${\displaystyle \log {\hat {e}}}$${\displaystyle P,~L,~R}$${\displaystyle \log {\text{P}}(x,{\hat {\pi }}|\theta )}$${\displaystyle O(M_{a}D+M_{b}D^{2})}$

KnudsenとHeinによるKH-99アルゴリズムは、RNAの二次構造を予測するPfoldアプローチの基礎を築きました。^[20]このアプローチでは、パラメータ化には、列と突然変異の確率に加えて、アラインメントツリーから得られた進化履歴情報が必要です。文法確率はトレーニングデータセットから観測されます。

構造アラインメントでは、対になっていない塩基の列と対になっている塩基の列の確率は、他の列とは独立しています。単一塩基位置と対になっている位置の塩基を数えると、ループとステムの塩基の頻度が得られます。塩基対XとYの場合、の出現はの出現としてもカウントされます。 などの同一の塩基対は2 回カウントされます。 ${\displaystyle XY}$${\displaystyle YX}$${\displaystyle XX}$

あらゆる可能な方法でシーケンスをペアリングすることにより、全体的な突然変異率が推定されます。妥当な突然変異を回復するには、シーケンスの同一性しきい値を使用して、類似のシーケンス間で比較を行う必要があります。このアプローチでは、ペアリング シーケンス間で 85% の同一性しきい値を使用します。最初に、シーケンス ペア間の単一塩基位置の差異 (ギャップのある列を除く) がカウントされ、2 つのシーケンスの同じ位置に異なる塩基X、Yがあった場合、各シーケンスの差異のカウントが増加します。

${\displaystyle X\neq Y}$
               最初のシーケンスペアと2番目のシーケンスペア${\displaystyle C_{\text{XY}}+1}$
               ${\displaystyle C_{\text{YX}}+1}$

突然変異率を計算します。
               塩基 X から塩基 Y への突然変異とします。  塩基${\displaystyle r_{\text{XY}}=}}$${\displaystyle ={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}}$
               X から他の塩基への突然変異率の負の値は、塩基が対になっていない確率とします  。${\displaystyle r_{\text{XX}}=}}$${\displaystyle =-\sum r_{\text{XY}}}$
               ${\displaystyle P_{s}=}$

不対塩基の場合、XからYへの突然変異の流れが可逆的であることを満たす4×4の突然変異率行列が使用される：^[35]

${\displaystyle PX^{r}XY=PY^{r}YX}$

塩基対の場合、16×16の速度分布行列も同様に生成される。^{[36] [37]} PCFGは構造の事前確率分布を予測するために使用され、事後確率はインサイドアウトサイドアルゴリズムによって推定され、最も可能性の高い構造はCYKアルゴリズムによって見つけられる。^[20]

列の事前確率を計算した後、すべての可能な二次構造を合計することによってアラインメント確率が推定される。長さlの配列D の二次構造の任意の列Cは、アラインメントツリーTと突然変異モデルMに関してスコアリングできる。PCFGによって与えられる事前分布はである。系統樹Tは、最大尤度推定によってモデルから計算できる。ギャップは未知の塩基として扱われ、合計は動的計画法によって行うことができることに留意されたい。^[38]${\displaystyle \sigma}$${\displaystyle D=(C_{1},~C_{2},...C_{l})}$${\displaystyle P(\sigma |M)}$

${\displaystyle P(D|T,M)}$

${\displaystyle =\sum P(D,\sigma |T,M)}$

${\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |T,M)}$

${\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |M)}$

文法の各構造には、トレーニングデータセットの構造から考案された生成確率が割り当てられています。これらの事前確率は、予測の精度に重み付けされます。^{[21] [32] [33]}各ルールが使用される回数は、その特定の文法機能のトレーニングデータセットからの観測によって異なります。これらの確率は文法形式で括弧内に書かれ、各ルールの合計は100％になります。^[20]たとえば、

${\displaystyle S\to LS(80\%)|L(20\%)}$

${\displaystyle L\to s(70\%)|dFd(30\%)}$

${\displaystyle F\to dFd(60.4\%)|LS(39.6\%)}$

データの事前アライメント頻度が与えられれば、文法によって予測されたアンサンブルから最も可能性の高い構造を、CYKアルゴリズムを通じて最大化することで計算することができます。正しい予測の予測数が最も高い構造がコンセンサス構造として報告されます。^[20]${\displaystyle P(\sigma |D,T,M)}$

${\displaystyle \sigma _{MAP}=\arg {\underset {\sigma }{\max }}P(D|\sigma ,T^{M}L,M)P(\sigma |M)}$

PCFGベースのアプローチは、スケーラブルで汎用性が高いことが求められます。精度のために速度を犠牲にすることは、可能な限り最小限に抑える必要があります。Pfoldは、スケーラビリティ、ギャップ、速度、精度に関してKH-99アルゴリズムの限界に対処します。^[20]

• Pfold ではギャップは不明として扱われます。この意味で、ギャップのある列の確率は、ギャップのない列の確率と同じです。
• Pfold では、ツリーT はPCFG 文法による最大尤度ではなく、近傍結合による構造予測の前に計算されます。枝の長さのみが最大尤度推定値に合わせて調整されます。
• Pfold の前提は、すべての配列が同じ構造を持つということです。配列同一性のしきい値と、任意のヌクレオチドが別のヌクレオチドになる確率を 1% にすることで、アライメント エラーによるパフォーマンスの低下を制限します。

PCFGはRNAの二次構造を予測する強力なツールであることが証明されているが、タンパク質配列解析の分野での使用は限られている。実際、アミノ酸アルファベットのサイズとタンパク質に見られる相互作用の多様性は、文法推論をはるかに困難にしている。^[39]結果として、形式言語理論のタンパク質解析への応用のほとんどは、局所的な相互作用に基づく単純な機能パターンをモデル化するための表現力の低い文法の生成に主に限定されてきた。^{[40] [41]}タンパク質構造は一般に、入れ子や交差関係を含む高次の依存関係を示すため、CFGの能力を明らかに超えている。^[39]それでも、PCFGの開発により、それらの依存関係の一部を表現し、より広範囲のタンパク質パターンをモデル化する機能を提供できる。

• 統計解析
• 確率文法
• Lシステム

• Rfam データベース
• 地獄の
• スタンフォードパーサー: 統計パーサー
• pyStatパーサー