確率的文脈自由文法

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}} }$ループがステムの開始点か一本鎖領域sかを決定するパラメータ${\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ベースの確率モデルの側面を扱うアルゴリズムはいくつか存在する。例えば、インサイドアウトサイドアルゴリズムとCYKアルゴリズムである。インサイドアウトサイドアルゴリズムは、期待値最大化パラダイムに従うことができる再帰的動的計画法スコアリングアルゴリズムである。これは、あるPCFGに基づいて、与えられた配列と一致するすべての派生の総確率を計算する。内部部分は、構文解析ツリーからの部分木をスコアリングし、したがってPCFGが与えられた場合の部分シーケンスの確率をスコアリングする。外部部分は、完全な配列の完全な構文解析ツリーの確率をスコアリングする。^{[ 32 ] [ 33 ]} CYKはインサイドアウトサイドスコアリングを修正する。「CYKアルゴリズム」という用語は、PCFGを使用して配列の最適な構文解析ツリーを見つけるインサイドアルゴリズムのCYKバリアントを説明することに注意されたい。これは、非確率的CFGで使用される実際のCYKアルゴリズムを拡張したものである。 ^{[ 1 ]}

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

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

共分散モデル (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の少し異なる実装を使用します。最適な構文解析ツリーの対数オッズ放出スコア -${\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})}$[ ^{1 ]​}

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

その間${\displaystyle X\neq Y}$${\displaystyle C_{\text{XY}}+1}$最初の配列ペア${\displaystyle C_{\text{YX}}+1}$2番目の配列ペア

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