１．担当ＰＭ

　伊知地　宏　（ラムダ数学教育研究所　代表）

２．採択者氏名

３．プロジェクト管理組織

　株式会社サーバードメイン

４．委託金支払額

　4,442,006円

５．テーマ名

　 確率文脈自由文法に基づく遺伝子情報RNAデータベース検索システム

６．関連Webサイト

　なし

７．テーマ概要

　DNAの遺伝子でない領域から複製される機能RNAの役割が認識され，DNAの文字列データからこれらの機能RNAを高速に検索するソフトウェアが必要となっている．本プロジェクトでは，機能RNAを検索するソフトウェアの開発を行う．
　まず機能RNAのプロファイリングに使われている確率文脈自由文法のパーザジェネレータを開発し，次にこのパーザジェネレータを利用して検索システムを開発するという手順で開発を進めた．さらに，検索する機能RNAの選択と検索結果を確率文脈自由文法のツリーと対応づけて表示するGUIも作成した．

８．採択理由

　元々の提案は確率文脈自由文法に対応するパーサージェネレータを主に作ろうというものである．提案者は脳科学・遺伝子科学の研究に従事している研究者であり，パーサージェネレータだけで十分に未踏性があると考えていたようであるが，これはそんなに難しいものではない．その一方，提案資料にはこのパーサージェネレータを使って遺伝子情報RNAデータベースの検索システムを作れることが書いてあり，PMはこちらの話に興味を持って面接で詳しく話を聞いたところ，未踏性が高い仕事であると感じた．提案者はこの方面の専門家であり，ソフトウェアの実現もおそらく可能であることがわかり，実用的な面でも価値が非常に高いので，遺伝子情報RNAデータベースの検索システムを必ず作ることを条件に採択する．

９．開発目標

　本開発の目標は，実験などで得られた遺伝子文字列から，これらのプロファイリングされた機能RNAを高速に検索するシステムを開発することである．具体的には、GUIを備えたシステムで，ユーザーが機能RNAプロファイル (クエリと呼ぶ) を列挙されたアイコンから選び，検索対象の文字列 (ターゲットと呼ぶ) を入力し，検索ボタンを押すことにより，クエリのプロファイルでターゲットの部分文字列を順に構文解析し，構文解析を行った結果確率が一定の閾値を超える部分文字列を全て表示するものである．検索結果の表示は，ターゲットの文字列全体を表示し，構文解析を行った結果確率の値が閾値を超えた部分文字列を強調表示する．さらに，検索結果の部分文字列と確率文脈自由文法のツリーとの対応関係，および機能RNAの2次構造表示も行うものとする．

１０．進捗概要

　PMの予想以上に確率文脈自由文法のパーザーを開発するのに時間がかかり，機能RNAを検索し表示するシステムの開発にかける時間が短くなってしまった．開発者は検索システムのユーザインタフェースについてほとんどアイデアを持っておらず，PMが積極的に提案する状況となり，最後の2ヶ月であわててユーザインタフェースを開発するという事態になり，ぎりぎりでやっと少し格好が付く形となった．

１１．成果

　（１）RNA検索システムの検索部
　確率文脈自由文法による機能RNAのプロファイリングにおいて，広く共通に用いられているCM形式のプロファイルをクエリとして用いて検索を行う．

図1. CM形式のプロファイルの例

　CM形式のプロファイルはテキスト形式のデータとして配布されており，図1は典型的なCM形式のプロファイルの一部である．各行では「状態名（＝品詞名）」，「状態の通し番号」，「最後の親の通し番号」，「親の総数」，「最初の子の通し番号」，「子の総数」に続いて，各「子」への遷移確率の対数が負の小数で与えられている．
　確率文脈自由文法の効率的な構文解析アルゴリズムであるCYKアルゴリズムを用いて，CM形式のプロファイルをクエリとしてターゲット文字列の構文解析を行う．図2のように，プロファイルの長さの部分文字列をCYKアルゴリズムで構文解析し，構文解析の結果の確率がプロファイルの閾値を超える場合は出力を行い，解析対象の部分文字列をひとつ進めまた構文解析を行うという処理をターゲット文字列が終了するまで繰り返す．

図2. クエリによるターゲット文字列の検索

　（２）RNA検索システムのユーザインタフェース
　クエリの選択は，図3の画面中央部に列挙された「クエリ選択用アイコン」をクリックすることにより行う．各「クエリ選択用アイコン」には確率文脈自由文法のツリーを小さく表示する．「クエリ選択用アイコン」は、左右に配置された「クエリ選択用アイコンスクロールボタン」により左右にスクロールでき，クエリを選択すると「クエリ選択用アイコン」の上に重なった状態で確率文脈自由文法のツリーが表示される．ターゲット文字列は下部の「ターゲット文字列入力用テキストボックス」に入力する．
　「検索ボタン」を押すと，検索が実行されるとともに「クエリ選択用アイコン」が消え選択されたクエリのツリー表示だけが残り，図4のようにユーザインタフェースの中央部が「検索結果表示部2」となる．検索が終了すると，「検索結果表示部1」に検索結果のヒット数とヒットした文字列上の位置がテキストで表示される．また「検索結果表示部2」にターゲット文字列全体が塩基アイコンで表示され，最初のヒットした部分が強調表示される．

１２．プロジェクト評価

　確率文脈自由文法のパーザージェネレータ開発に時間がかかり過ぎて，本来の目標である機能RNA検索システムの開発にあまり時間がかけられなかった．特に検索システムのユーザインタフェースや機能に関して，重要な物でも未実装な物が多々あり，完成度は低い．

　・未踏性: B
　　RNAに関する解析ソフトウェアはあまりなく，開発目標の未踏性は本来であれば評価Aと非常に高いものだが，それに対する実装が伴っていない．
　・先進性: B
　　確率文脈自由文法のパーザージェネレータ開発は技術的に難しくなく，RNA検索システムの実装が十分でないので，技術的先進性はあまりない．
　・実用性: B-
　　機能がいろいろ不足しており，実用性は今の所低い．
　・社会への影響: C+
　　機能が不足しており，インパクトを与えるソフトウェアにはなっていない．
　　(A: 高い，B: 並，C: 低い)

１３．今後の課題

　まずは開発期間内に実装できなかった機能をちゃんと開発してもらいたい．その上で．RNA検索システムに求められる物が何なのかをしっかりと考えてもらいたい．このようなソフトウェアは今後非常に重要になってくるので，是非とも今のうちにちゃんとしたソフトウェアを開発して，遺伝子関連研究にちゃんと活かせるようにしてもらいたい．