著者

加藤有己 関 浩之 嵩 忠雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告バイオ情報学(BIO) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.99, pp.33-40, 2006-09-15

---

シュードノットを含むRNA の2次構造をモデル化する形式文法がいくつか提案されている.本論文では,文脈自由文法の自然な拡張でありシュードノットを表現できる多重文脈自由文法(MCFG)に着目し,確率MCFG(SMCFG)と呼ばれる確率モデルに拡張する.次に,多項式時間で確率最大の導出木を求める構文解析アルゴリズム及びEM アルゴリズムに基づく確率パラメータ推定アルゴリズムを与える.さらに,SMCFG の構文解析アルゴリズムを用いたRNA シュードノット構造予測に関する実験結果を示す.Several formal grammars have been proposed for modeling RNA secondary structure including pseudoknots. In this paper, we focus on multiple context-free grammars (MCFGs), which are natural extension of context-free grammars and can represent pseudoknots, and extend MCFGs to a probabilistic model called stochastic MCFG (SMCFG). We present a polynomial time parsing algorithm for finding the most probable derivation tree and a probability parameter estimation algorithm based on the EM algorithm. Furthermore, we show some experimental results on RNA pseudoknot prediction using the SMCFG parsing algorithm.