問題

問題を形式的に述べると以下のようになる. 入力として与えられるのは, 可能 なスタック領域の候補を全て並べたものであり, 各スタック領域は以下の形を している.

ここで, a, b, c, dは を満たす整数 で, スタック領域の位置を表す. 具体的には, aとd, a+1とd-1, a+2とd-2, bとcが水素結合をする可能性があることを示す. Eはこの水素結合が行なわれた時に得られるエネルギーを表す正の浮動小数 点数である. 全スタック領域の候補はEの大きさ順に並べられているものと する. 図5.2に, 入力の例を示す.

二つのスタック領域 と は, 以下の条件を見たす時, 共存可能 (compatible)であるという.

ここで, [A, B]は, を満たす整数xの集合を表している. 最 初の条件が満たされる時, スタック領域を構成する塩基同士は互いに離れた位 置にあり, したがって幾何的には図5.3左のように双方とも に水素結合を構成することができる. 二つ目のまたは三つ目の条件が満たされ る時は, 図5.3右のような形で両方のスタック領域が水素結 合可能である.

      図5.3: 可能な2つのスタック領域の配置 

問題は, 与えられたスタック領域の集合の部分集合で, その中のどの二つのス タック領域も共存可能であるような部分集合のうち, なるべく合計(安定化)エ ネルギーの大きなものを求めることである. より詳しくいうと, ここでは,

最大エネルギーの集合のエネルギーを として, そこから, あらかじめ与えられた閾値(以下, Tと書く)内のエネルギーを持つ集合を 全て求める, すなわち, 以上のエネルギーを持つ集 合を全て求める,

ことを問題とする.