2003年度本選問題：
「ゲノム解析：最大タンパク質ファミリーの探索」
遺伝子の本体であるゲノムの実態は，4 種類のヌクレオチドがひも状に繋が
った生体高分子：DNA（デオキシリボ核酸）です．この DNA の遺伝情報に基
づき，細胞骨格や酵素であるタンパク質が合成されます．タンパク質はアミ
ノ酸が繋がった生体高分子で，例えば大腸菌のゲノムには 4300 本のタンパ
ク質（それぞれ アミノ酸が 100 から 1000 程度繋がったアミノ酸配列）の
設計図が書かれています．タンパク質（アミノ酸配列）は配列が似ていれば
働きも似ています．よって，ある生物がどの種類のタンパク質を多く利用し
てるのかを調べる時に，似たタンパク質の集合（「タンパク質ファミリー」
と言われているが，以下では，単に「ファミリー」と呼ぶ）を見つけること
はたいへん重要です．
【問題】与えられたタンパク質セット（アミノ酸配列の集合）中から配列類
似度 25 ％以上のファミリーで，できるだけ大きなものを見つけるプログラ
ムを作成しなさい．
- 注１）
-
「配列類似度」や「ファミリー」などの用語については補足説明を参照．
- 注２）
-
プログラムは，大きなファミリーが見つかる度に，それを出力するようなも
のを作成してもらいます．ただし，ファミリーになっていないものを出力し
てはいけません．制限時間内に何度か出力がある場合には，その中で最後に
出力されたものを答えとみなします．なお，出力方法については，本選開始
時に指示します．
［例題について］
ファイル proteins-smallexample.txt，
proteins.txt
にタンパク質セット（アミノ酸配列の集合）の例を
与えておきます．類似度を求めるプログラム scoreout.c，
seqid.c
の働きや性能を見て，
あらかじめ対策を立てるのに使用してください．皆さんのプログラムの評価
には，この例のアミノ酸配列集合と同程度の大きさ，個数のものを使います
が，集合自体は違います．評価に使うアミノ酸配列集合と同じような性質，
傾向を持つアミノ酸配列集合の例は，本選開始時にあらためて配布します．
［評価について（案）］
あるアミノ酸配列集合に対してプログラムを実行し，制限時間以内に出力さ
れたファミリーの大きさによって順位を決めます．同じ大きさのファミリー
を出力した場合には，それが出力されるまでの計算時間によって順位を決め
ます．
［本選で使用するスーパーコンピュータおよびプログラミングについて］
本選で使用するスーパーコンピュータは SGI Origin2000（OS はUNIX）で，
全部で 256 プロセッサあります．その内，コンテストでは各チームあたり
最大 64 プロセッサを使うものとします．また，並列プログラミングには
MPI ライブラリが用意されています．初めて並列プログラミングを経験する
方のために，事前に MPI プログラミングにトライできる環境を用意しまし
た．これについては追ってアナウンスいたします．
補足
問題に登場する用語を簡単に説明します．
用語１：タンパク質の類似度（sequence identity）
(注）以下の説明では，簡潔にするために「記号の一致箇所」をもとにして
類似度の定義を説明します．本当の類似度の定義は「スコア」と呼ば
れるものをもとに定義します．詳しくは alignment.txt をご覧下さい．)
アミノ酸は 20 種類ありますが，それらを仮に記号 A 〜 T で表わすことに
します．（本当は少し違いますが，ここでは仮に A 〜 T としておきます．
）つまり，タンパク質の配列は，記号 A 〜 T からなる記号列です．たとえ
ば，次のような配列 X や Y になります．（これは例として人為的に作った
ものです．）
X: CBADDKDDBBTPPEP （長さ 15 の列）
Y: CGAEEDDKDDBBTEEFGKKK （長さ 20 の列）
X, Y の類似度は，２本の配列を並べた時に上下で記号が一致する箇所の割
合で定義されます．ここでは
Xと Y の類似度 = 記号が一致した箇所の数 / X と Y のうち短い配列の長さ * 100
（注：小数点以下切捨て）
と定義します．この例では「X と Y のうち短い配列の長さ」は 15 です．
次に「記号が一致する箇所」について述べます．たとえば，
X: CBADDKDDBBTPPEP
Y: CGAEEDDKDDBBTEEFGKKK
* * *
と並べると * で示した 3 箇所で記号が一致していますから，
「記号が一致した箇所の数」＝ 3
となります．ただし，両配列をよく見比べると，少しずらしてみると一致す
る場所が多くなることがわかります．たとえばXの始めの位置を少しずらし
て，
X: CBADDKDDBBTPPEP
Y: CGAEEDDKDDBBTEEFGKKK
********
と並べると8 箇所一致します．さらに，途中でずらして(配列の途中に - を
入れます），
X: CBA--DDKDDBBTPPEP
Y: CGAEEDDKDDBBT--EEFGKKK
* * ******** *
のようにならべると 11 箇所で一致するようになります．（ちなみに，これ
が最大です．）アミノ酸配列を並べる時，上下に並んだアミノ酸の性質がも
っとも似るようにならべることになっています．「最も似る」，ということ
と，「一致する箇所が最大になる」，ということはだいたい同じことを指し
ていますが厳密には少し違います．また最後の例のように配列の途中に -
を入れ続けると配列の「変形」が激しくなります．つまり，無理をして似
せることになります．こういう変形は好ましくない場合もあるので，実際に
は，この「不自然さ」も考慮したバランスのよい並べ方が求められます．こ
れらについての正確な説明はアミノ酸列の並べ方
とスコアを参照して下さい．
用語２：アミノ酸配列 X, Y の類似度が 25％ 以上のとき，この X, Y は
「似ている」
と考えることにします．あるタンパク質（アミノ酸配列）の集
合があり，そのすべての要素同士が「似ている」とき，その集合を「タンパ
ク質ファミリー」（単に「ファミリー」）と呼ぶことにします．つまり，集
合 S = {X1, X2, ..., Xk} がファミリーならば，そのどの 2 要素 Xi, Xj
をとっても Xi, Xj の類似度が 25 ％以上になってるのです．今回の課題は，
与えられたタンパク質の集合から，できるだけ大きなファミリーを見つける
ことです．
以上
|