Shannon Entropy

9.1Introduction

Chomskyは、言語をモデル化する試みとして、文脈自由文法(Cfg)を最初に形式化しました。 それ以来、それらはいろいろな計算機科学の適用で広く使用されました。 Cfgは再帰的な性質を持ち、単語とも呼ばれるアルファベットの文字列を駆動することができるルールのセットで構成されています。 文法によって生成された単語のセットは、その文法の言語と呼ばれます。 文法は、単語とその記述的派生の間に一対一の対応がある場合、明確であると言われています。 確率的Cfg(Scfg)は、各ルールに確率を割り当て、そのルールを導出するために使用されるルールの確率を乗算することによって、各単語に尤度値を割り当てます。 Grenander、Kuich、Hutchins、Souleなどは、生成関数技術を使用して、平均導出長、容量、またはShannonのエントロピー（Shannonエントロピー）の収束など、CfgおよびScfgの重要な特性を調査しました。 ＲＮＡの二次構造模式図も文脈自由な性質を有し、それをそのような文法によって記述することを可能にする。 ＲＮＡ二次構造は、ＳｍｉｔｈおよびＷａｔｅｒｍａｎによって最初に形式的に記載された。 ＲＮＡ二次構造の組合せ的特徴をＳｔｅｉｎおよびＷａｔｅｒｍａｎによって探求し、続いてＶｉｅｎｎｏｔおよびＶａｕｃｈａｕｓｓａｄｅ ｄ Ｅ Ｃｈａｕｍｏｎｔ，Ｈｏｆａｃｋｅｒらによって研究した。 ら、ｎｅｂｅｌ，Ｌｉａｏ ａｎｄ ｗａｎｇ，Ｄｏｓｌｉｃ ｅ ｔ ａ ｌ． そして、生成関数と確率生成関数を使用して他の人。ScfgはRNA二次構造研究に大きな影響を与えてきました。

ScfgはRNA二次構造研究に大きな影響を与えてきました。 RNA二次構造モデリングは、様々なクラスの非タンパク質コードRna（ncRNA）などの多くのRnaの機能がその構造に関連しているため、RNA構造とその後の生物学的機 典型的には、ＲＮＡ二次構造予測は、Ｂｏｌｔｚｍａｎｎ集団のような熱力学的に基づく折り畳みモデルの下で配列の折り畳みエネルギーを最小化することによって行われる。 一方、scfgは、より柔軟にRNA折りたたみを模倣することができる共分散モデルです。 SCFGベースの折り畳みモデルの場合、尤度値はRNA配列のすべての可能な折り畳みシナリオに割り当てられます。 そして、最尤法（Ｍ ｌ）値を有する構造をＲＮＡ配列の二次構造として予測する。 ＳＣＦＧベースのモデルのＭＬ予測はＣｏｃｋｅ-Ｙｕｎｇｅｒ-Ｋａｓａｍｉ（ＣＹＫ）アルゴリズムによって行うことができる。 エネルギー最小化と同様に、CYKアルゴリズムは動的計画法によって実装されます。 モデル設計の目標は、既知のRNA二次構造と可能な限り類似したML推定を得ることであり、したがって、ルールへの確率の割り当てを重要かつ困難な作業にすることである。 RivasはRNAの二次構造の模倣のさまざまな面により詳細な洞察力を提供する。

現在の期待値最大化（EM）モデル学習アプローチは、一般に、以下の二つのステップからなる：まず、CYKアルゴリズムは、トレーニングセットの各RNA配列の構造予 第二に、SCFGのルール確率は、予測におけるそれらの出現の数または頻度に基づいて再推定される（推定ステップ）。 これらの推定値は、Durbin et al.に説明されているLaplace prior approachを使用して計算することができます。 または同様の周波数ベースのアプローチを展開します。 反復Ｅ Ｍ手順は、結果として得られる規則確率が所望の精度をもたらすまで継続することができる。 モデル学習技術は、ML基準の定義（ジョイント対条件）またはルール確率推定技術のいずれかで異なる場合があります。 ＳＣＦＧベースのＲＮＡ折りたたみモデルは、わずかな文法規則を有する軽量ＳＣＦＧから構成され得るか、またはＲｉｖａｓらに記載されている超文法のような多くの規則からなる重量級の文法であることができる。 .

本研究では、ここでは文法空間（GS）エントロピーとして表されるSCFGのシャノンエントロピーを解析的に計算し、RNA二次構造モデリングにおける重要な文法特徴として導入した。 提示された定式化は、派生エントロピーとして知られている文法エントロピーの一般的な形式と一致しており、GrenanderとSouleで見つけることができます。 第9節で。図2に示すように、Grenanderで提示された導出エントロピー定式化と一致する構造的に明確なRNAモデリング文法1の無限に大きな確率空間のShannonエントロピーを計算するための定式化が提示されている。 いくつかの確立されたRNA折りたたみモデルのGSエントロピー値は、セクション9.3の異なるパラメータセットの下で計算されます。 セクション9.4では、GSエントロピーに基づいてSCFGベースのRNA二次構造モデル訓練の基準が提案されています。 最後に、セクション9.5は議論と結論で構成されています。