著者

関 浩之 鯵坂 恒夫

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.28, no.3, pp.3_61-3_69, 2011-07-26 (Released:2011-09-26)

---

ソフトウェアサイエンスになじみ深い形式言語理論の枠組みであるチョムスキー階層をあらためて探検する.文法の記述の方法および4つの文法クラス間の隙間に注目し,とくに機械と人間(生物)の間を攻めるともいえる弱文脈依存文法についてはやや詳しく解説する.

著者

加藤有己 関 浩之 嵩 忠雄

出版者

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

雑誌

情報処理学会研究報告バイオ情報学(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.

著者

田中 翔 加藤 有己 関 浩之

出版者

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

雑誌

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

巻号頁・発行日

vol.2009, no.25, pp.37-40, 2009-02-26

---

シュードノットを含むRNAの2次構造予測に対するアプローチとして,文脈自由文法(CFG)より表現能力の高い形式文法(MCFQTAG等)の構文解析アルゴリズムに基づく手法が提案されている。また,汎用性と精度の向上を目指し,複数の1次構造同士の比較解析に基づく2次構造予測法もいくつか提案されている。本稿では,比較解析ができるようにMCFを拡張したペア確率多重文脈自由文法(Pair-SMCFG)を新たに定義し,これに基づくRNAの2次構造予測法を提案する。長さ70程度のRNA配列に対して2次構造予測を行ったところ,RNAの特定のファミリーに対する文法の特化を全く行わないという条件下であっても,適合率63.2%,再現率62.0%という結果を得た。Several methods for the prediction of RNA secondary structure including pseudoknots have been proposed based on parsing algorithms for formal grammars such as MCFG and TAG, of which generative power is greater than CFG. Also, comparative sequence analysis, which compares several RNAs and predicts their secondary structures, is a promissing approach. In this paper, we define pair-stochastic multiple context-free grammar (Pair-SMCFG) and propose a prediction method based on Pair-SMCFG. Pair-SMCFG is an extension of MCFG for comparative sequence analysis. Experimential results show that for RNA which have about 70 bases, the precision and recall of our algorithm are 63.2% and 62.0% respectively.