確率的文脈自由文法

RNA secondary structure implementations based on PCFG approaches can be utilized in :

• Finding consensus structure by optimizing structure joint probabilities over MSA.^[20][21]
• Modeling base-pair covariation to detecting homology in database searches.^[11]
• pairwise simultaneous folding and alignment.^[22][23]

Different implementation of these approaches exist. For example, Pfold is used in secondary structure prediction from a group of related RNA sequences,^[20] covariance models are used in searching databases for homologous sequences and RNA annotation and classification,^[11][24] RNApromo, CMFinder and TEISER are used in finding stable structural motifs in RNAs.^[25][26][27]

PCFG design impacts the secondary structure prediction accuracy. Any useful structure prediction probabilistic model based on PCFG has to maintain simplicity without much compromise to prediction accuracy. Too complex a model of excellent performance on a single sequence may not scale.^[1] A grammar based model should be able to:

• Find the optimal alignment between a sequence and the PCFG.
• Score the probability of the structures for the sequence and subsequences.
• Parameterize the model by training on sequences/structures.
• Find the optimal grammar parse tree (CYK algorithm).
• Check for ambiguous grammar (Conditional Inside algorithm).

The resulting of multiple parse trees per grammar denotes grammar ambiguity. This may be useful in revealing all possible base-pair structures for a grammar. However an optimal structure is the one where there is one and only one correspondence between the parse tree and the secondary structure.

曖昧さには 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}=}$塩基が対になっていない確率。