著者

プンサップ・アンヤーニー 加藤有己 阿久津 達也

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.128, pp.137-142, 2007-12-21

---

生体高分子の機能の解明にはその折り畳み構造を理解する必要があるとされている.特に,機能的非コード RNA が注目を集めている.RNA の立体構造を予測することは困難であるため,シュードノットを含む,または含まない2次構造を予測する研究が行われてきた.本稿では,整数計画法を2次構造予測に適用する手法を提案する.ここで,シュードノットを含まない構造と,任意の平面的シュードノット構造を予測するための2つの定式化を導入する.さらに,提案手法を使った構造予測に関するいくつかの実験結果を示す.Understanding the function of biological molecules requires knowledge of their folded structures. In particular, noncoding functional RNAs have received much attention. Due to the difficulty in predicting the three dimensional structure of RNA, research efforts have shifted to the prediction of secondary structure both with and without pseudoknots. In this paper, we present a method of applying integer programming (IP) to RNA secondary structure prediction. We introduce respective IP formulations for predicting pseudoknot-free structure as well as arbitrary planar pseudoknotted structure. Furthermore, we show some experimental results on structure prediction using the proposed method.

著者

加藤有己 関 浩之 嵩 忠雄

出版者

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

雑誌

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