Super Con2002本選課題(案)

SuperCon2002本選課題

「格子タンパク質の基底状態探索」

タンパク質は特異的な（ユニークな）立体構造をとることによってその機能を発現します。特異的な立体構造はタンパク質の配列によってのみ決まります。ここではエネルギー最低の状態だとしましょう。これを基底状態と言います。タンパク質の理論モデルとして，H(疎水基)とP(親水基)からなる配列(HP配列)がよく利用されます。例えば，

   HPHHPPHPHHPHP

といった配列です(現実のタンパク質はもっと大きい)。これを

 H₁P₁H₂P₂H₁P₁H₂P₁H₁P₁

と略記します。こういった配列が二次元格子の上を運動して，基底状態に辿り着き，働く(生理学的機能をもった)分子となることを想定します。このモデルをタンパク質の二次元格子模型と言います。HPからなるタンパク質では，HH，HP，PPの３組の相互作用が考えられますが，HHの隣り合った接触(HH接触)のみエネルギーをカウントします。ですから，HH接触が最大となる配置が，タンパクの基底状態となります。例のタンパクでは，図1のような配置(HP 格子)が HH接触数が5となり，基底状態を与えます。図2の赤点線はHH接触を表しています。

図1
図2

【問題】
与えられたHP配列から、HH接触数を最大とするようなHP格子を計算するプログラムを作成しなさい。
(入力データ)HP配列。例) HPHHPPHPHHPHP
(出力データ)与えられるHP配列の長さNとして、左下隅を(0,0)とする(2N+2) * (2N+2)の整数座標格子上にH、Pを配置。ただしHP配列の最初の要素の座標は任意とする。
出力一行目：座標ペアの列(各ペアには1から始まるインデックスが付く) 出力二行目：HH接触のペアの列(座標ペアのインデックスで指定、順不同) 出力三行目：HH接触数
先の例題を基にすると次のような出力になる。
13 13 13 14 14 14 14 15 13 15 13 16 14 16 15 16 15 15 15 14 15 13 14 13 14 12 1 12 3 12 3 11 4 9 4 7 5

順位について

2種類の問題A、Bを用意します。問題AはHP配列が短い場合でHH接触数最大のみを正解とします。また問題BはHP配列が長い場合で、必ずしもHH 接触数が最大である必要はありません。いずれの場合も実行時間に上限を設けます(実行時間はelapse timeで測定)。そして次のような配点を行います。

問題A、問題B共に100点とする。
問題Aの場合、正解でなければ0点。正解の中で実行時間の短い方を上位とし一番TOPに100点。以下順に10点減点する。
問題Bの場合、解が出たものを対象にHP接触数最大のチームに100点。以下順に10点減点。
問題A、問題Bの合計得点の高いチームをより上位とする。

本選で使用するスーパーコンピュータおよびプログラミングについて

本選で使用するスーパーコンピュータはSGI Origin2000(OSはUNIX)で、全部で256プロセッサあります。その内、コンテストでは各チームあたり最大64プロセッサを使うものとします。また、並列プログラミングにはMPIライブラリが用意されています。初めて並列プログラミングを経験する方のために、事前にMPIプログラミングにトライできる環境を用意しました(別紙参照)。