概要

RNAの構造予測問題は, 与えられた塩基(アデニン(A), ウラシル(U), グアニン (G), シトシン(C))の1次元配列から, その構造を予測するものである. これら の塩基の間は互いに引き寄せられると, 水素結合をつくって系を安定させるの に寄与する組合せがある. たとえば, G-Cが引き寄せられると, 水素結合が形 成される. 構造予測とは, 与えられた1次元の配列から, 系ができるだけ安定 になるようなRNAの構造を求めることである. 中でもRNAの2次構造予測 では, 実際にどの塩基同士が水素結合をすれば系が安定するかだけを求め る. これはRNAが実際にどのような立体構造をとるかまでを予測するわけでは ない. 図形的には, これらの情報から, そのRNAが平面上でどのような 構造を持つかを求めることができるようになる.

たとえば, 例として, [2] からとった, 5'-gggcgc aaaaaa gcgccg aaaaaa cggcgc aaaaaa ggcgcc aaaaaa ggcgcc aaaaaa gcgccg aaaaaa cggcgc aaaaaa gcgccc-3'という, 塩基配列に対して我々のアルゴリズムを適 用すると, 図5.1の二つの準安定解(suboptimal)がえられる. これらは, 2次構造としては明らかに異なった構造を持っているが, 達成され ている安定度(エネルギー)は似たようなものである. この節では,

最適な解に近いエネルギーを持つ解を全て求める

ことを問題とする. 我々は組合せ的な手法を用いてこの問題に取り組む.

      図5.1: 5'-gggcgc aaaaaa gcgccg aaaaaa cggcgc aaaaaa ggcgcc
             aaaaaa ggcgcc aaaaaa gcgccg aaaaaa cggcgc aaaaaa gcgccc-3'
             の二つの準安定解 

組合せ的な手法の基本的な考え方は考え方は単純で, 可能な水素結合を順に選 んでいき, なるべくエネルギーを最小にする, つまり得られる安定化を最大に する, というものである. ここで単純に一つ一つの塩基の対に対して水素結合 をするか否かを場合わけしていく変わりに, いくつかの水素結合が連続して現 れる領域をスタック領域と呼び, あるスタック領域全体を選ぶか選ばな いかで処理を場合わけしていく.

以下では問題の入力として, 与えられた塩基配列から可能なスタック領域全て をあらかじめ生成したものを仮定する. 一つのスタック領域は, 具体的には1 次元配列上の同じ長さの区間二つによって指定される. たとえば, [3, 10], [30, 37]によって指定されるスタック領域は, 配列上で3番目の塩基と37番目 の塩基, 4番目の塩基と36番目の塩基, 10番目の塩基と30番目の塩基 が水素結合をするということを示している. 同時に, この水素結合によって達 成される安定化エネルギーも与えられているものとする.