最大重みクリーク抽出アルゴリズムのRNAの二次構造予測への適用

概要

論文の詳細を見る
RNAの二次構造予測問題は,その機能解明等のためゲノム情報解析の一つとして重要であり,現在までに様々な研究報告がなされてきている.この予測法の一つとして,Zuker and Stieglerを代表とする,塩基対単位による動的計画法を用いた多項式時間アルゴリズムが広く利用されている.しかし,この手法では,例えばHIV-2のgag-pol領域(図2)中に見られるようなシュードノット構造を扱うことはできず,予測結果と実構造とが必ずしも一致しないことがあり得る.これに対し,Pipas and McMahonは,スタック領域と呼ばれる,連続する塩基対結合によって形成される梯状構造を単位として候補の抽出を行い,この可能な組合せの中でエネルギーが最小となるものを全探索で求める手法を提案した.この方法で最適解を得るにはスタック領域候補数の指数オーダの時間を要するため,秋山と古谷は,ニューラルネットワークを用いた多項式時間の近似解法を提案した.本研究では,文献[2],[3]の考え方に基づき,RNAの二次構造予測問題を,グラフ理論における組合せ最適化問題の一つである最大重みクリーク問題として形式化し,この分枝限定アルゴリズムを適用した結果等を示す.
一般社団法人情報処理学会の論文
1996-03-06