NetSolve Systemを用いた
PSA/GAcによるタンパク質立体構造予測
○ 青井 桂子
廣安 知之
三木 光範
岡本 祐幸
Jack Dongarra
同志社大学大学院
同志社大学工学部
同志社大学工学部
分子科学研究所
University of Tennessee
研究背景
 バイオインフォマティクスの課題の1つにタンパク質の構造,
機能の推定がある.
 タンパク質の機能と構造は密接に関係している.
→ 構造を予測することが重要.
 実験的な手法では,大量のタンパク質の構造を短い時間
で解析することは不可能である.
→ 実験環境に依存せず,一度に多くのタンパク質を短時
間で構造決定することが望まれる.
研究背景
 自然のタンパク質の立体構造はエネルギー最小状態に対
応している.
→ エネルギー最小化を行うことで,アミノ酸の配列情報のみか
ら立体構造予測が可能
 最適化アルゴリズムを用いたタンパク質のエネルギー最小
化を行う.
High energy
Low energy
最適化アルゴリズムと解探索能力
 ヒューリスティックな最適化アルゴリズム:
シミュレーテッドアニーリング(SA)
 遺伝的アルゴリズム(GA)

 確率的探索を行う最適化アルゴリズムでは試行によって最適解
が求められる場合と求められない場合がある.
 SAやGAの試行数を増やす.
→ 最適解発見回数が増加する.(解の信頼性が向上する)
 1度にできるだけ多くの計算を行い,早く確実に解を求める.
→ Gridを利用する.
Grid
 広域に点在する計算機,観測装置,データベースが結びつき,協調
作業できるもの.
 ユーザが意識することなく,セキュアかつ効率よく資源が供給される
ことが必要となる.




フォールトトレランス
スケジューリング
セキュリティ(認証)
各資源のシステム情報
→ これらを解決するためにミドルウェアが開発されている.
(Globus,Ninf,NetSolveなど)
NetSolve
 GridRPCシステム(Gridミドルウェアの代表的なモデル)
リモートシステム上のサブルーチンをネットワーク経由で呼び出す
 予めServerに用意されたライブラリを用いて実行
研究目的
 Grid環境におけるタンパク質立体構造予測システムを構築する.

Grid環境でアプリケーションを構築するためのツールとして
→ NetSolve を利用

最適化アルゴリズムとして
→ PSA/GAc [Hiroyasu,2002]を利用
 Grid環境に適したPSA/GAcの計算モデルを実装し,その有効
性を検討する.
 GridRPCを用いることで生じるオーバーヘッドを隠すメカニズム
を検討する.
タンパク質の持つエネルギー関数の形状

局所的 に無数の極小値を持ち,大域的 にもいくつかの極小値を持つ
 容易に局所解に陥らない高い探索能力を持ち,効率よく探索できる
アルゴリズムとして,SAが用いられる.
Grid上で実装する場合の並列化モデル
 並列SA(PSA)
 PSA/GAc
遺伝的交叉を用いた並列SA




局所的探索に優れるSA + 大域的探索に優れるGA
PSAの解の伝達に遺伝的交叉(Crossover)を用いる手法
交叉手法 : 設計変数間での一点交叉
交叉後の選択 : 親子の4個体からベストを2個体抽出
PSA/GAcは数十残基からなるペプチドのエネルギー最小化において,
優れた解探索性能を持つことが明らかとなっている
PSA/GAcの並列化と処理時間






PSA/GAcの探索の大部分を占める.(計算負荷が高い)
並列実行可能
→Serverで処理する
一定の交叉間隔で2つ以上の解を1つに集めて交叉を行う.
並列実行不可能
→Clientで処理する
SAのステップ数を変更できServerでの計算時間を調整できる.
対象問題に依存しない.
RPCを用いる場合の問題点
 SAの計算時間と通信時間は並列化可能.
 RPCを実行する部分は並列化不可能.
実行待ち時間のオーバーヘッドがかかる
 同期モデルにおける1回の交叉周期までの実行時間:
(個体数-1)×RPCの実行待ち時間+計算時間+1RPCの通信時間
→ 個体数が増えた場合に,高速化がはかれないと考えられる.
PSA/GAcの非同期モデル
 2個体ごとに同期をとり,交叉処理を行う.
 利点 : 高速化
実行時間が個体数に依存しない.
 処理の遅いServerを待たなくて良い.

 問題点 : 解探索性能

アルゴリズムが変わるため,解探索性能が異なる可能性がある.
e.g. 異なるステップの個体間での交叉
数値実験1
 Grid環境に最適化システムを構築する際,高速化と解探索性
能が求められる.
 PSA/GAcの非同期モデルと同期モデルの性能比較:
最小エネルギーの平均値,総実行時間
 実験環境 : クラスタ環境,インターネット環境
 対象タンパク質 : C-peptide
アミノ残基数
13
二面角数
64
最小エネルギー構造
E≦ -42kcal/mol
C-peptide
実験1のパラメータ
エネルギー関数
設計変数
個体数
総MCsweep数
KONF90(ECEPP/2のパラメータ)
二面角(原子間の回転角)
2, 4, 8, 16
1500MCsweep×個体数
交叉間隔
10
試行回数
5
温度スケジュール
近傍幅
2.0 → 0.1
±180 °→ ±54°
終了条件はRPCを 個体数×150回になるまで繰り返し,1個体あたり
の平均評価計算回数が1500MCsweepとなるように設定した.
実験環境 (クラスタ環境)
 evolve Cluster System
evolve
100Mbps
reef-101~108
CPU
Memory
freund-101~106
forte01~24
reef-101~108
freund-101~106
forte01~24
Pentium Ⅲ 850MHz
Pentium Ⅲ 500MHz
Pentium Ⅲ 600MHz
256MB
512MB
256MB
Serverのスペックは不均質で,ネットワークは100Mbpsの
FastEthernetでつながれている.
実験環境 (インターネット環境)
 Galley,gp240(Doshisha)+msc,torc(UTK)
Doshisha
UTK
Agent :Galley
Client
100Mbps
Server
2Mbps
Server
gp240 (Doshisha)
CPU
Memory
Pentium 4
msc (UTK)
torc (UTK)
2.4GHz
Pentium Ⅲ 900MHz
Pentium Ⅲ 550MHz
512MB
256MB
512MB
Serverのスペックが異なる.また,ネットワークも不均質
クラスタ環境での実験結果
総実行時間
最小エネルギーの平均値
-2
2500
Blocking
Blocking
2000
Nonblocking
Elapsed time [sec ]
Energy [kcal/mol ]
-6
-10
-14
-18
-22
-26
Nonblocking
1500
1000
500
0
2
4
8
Population size
16
2
4
8
Population size
 解探索性能はほぼ同等である.
 個体数が増えるに従い,1試行の実行時間が増加している.
 非同期モデルは同期モデルに比べて高速化がはかれている.
16
インターネット環境での実験結果
総実行時間
最小エネルギーの平均値
-2
Blocking
Nonblocking
Nonblocking
Elapsed time [ sec ]
Energy [kcal/mol ]
-6
Blocking
10000
-10
-14
-18
-22
-26
8000
6000
4000
2000
0
2
4
8
Population size
16
2
4
8
Population size
16
 解探索性能はほぼ同等である.
 4個体までは非同期モデルは同期モデルに比べて短い時間で探索が
終了しているが,8,16個体で2つのモデルの計算時間が急増している.
各環境での処理時間
インターネット環境
クラスタ環境
1200
1000
交叉以外の待機時間
交叉処理の時間
Serverでの計算時間
通信時間
RPCの累積待機時間
14000
Elapsed time [ sec ]
Elapsed time [ sec ]
1400
800
600
400
12000
10000
8000
6000
4000
200
2000
0
0
2
4
8
Population size
16
交叉以外の待機時間
交叉処理の時間
Serverでの計算時間
通信時間
RPCの累積待機時間
2
4
8
Population size
16
 クラスタ環境のServerでの計算時間はオーバーヘッドより十分長い.
 インターネット環境では,計算時間に比べてオーバーヘッドが大きい.
→ 高速化 がはかれなかった.
NetSolveのオーバーヘッド
 NetSolveではジョブが実行される前に,5回の通信処理が行われる.
(1) AgentにServerの紹介依頼
(Client→Agent)
(2) 問題を解決できるServerを選択し,情報を渡す
(Agent→Client)
(3) ジョブが実行できる状態にあるかを確認する
(Client→Server)
(4-1) 状態がOKでなければ,Clientは(1)を行う
(Server→Client)
(4-2) 状態がOKであれば,サービスを起動し,サービスを通知する.
(5) Serverへデータを送信する
(Client→Server)
クラスタ環境
インターネット環境
0.05sec
2sec
実験1のまとめ
 クラスタ,インターネットの2つの環境で,非同期モデルは同期
モデルと解探索性能がほぼ同等であった.
 クラスタ環境においては同期モデルと比較して,非同期モデル
の高速化が示された.
 インターネット環境においては,個体数が増えた場合に高速化
が示されなかった.
 ネットワーク環境によってオーバーヘッドが異なる.
→ オーバーヘッドを隠すためのメカニズムが必要
数値実験 2
 オーバーヘッドを隠すためのメカニズム:
Serverでの計算時間がオーバーヘッドに比べて十分長くする
 PSA/GAcの非同期モデルと同期モデルの性能比較:
最小エネルギーの平均値,総実行時間
 実験環境 : インターネット環境
 対象タンパク質:C-peptide
アミノ残基数
13
二面角数
64
最小エネルギー構造
E≦ -42kcal/mol
C-peptide
実験 2 のパラメータ
エネルギー関数
設計変数
個体数
総MCsweep数
KONF90(ECEPP/2のパラメータ)
二面角(原子間の回転角)
2, 4, 8, 16
1500MCsweep×個体数
交叉間隔
100
試行回数
5
温度スケジュール
近傍幅
2.0 → 0.1
±180 °→ ±54°
終了条件はRPCを 個体数×15回になるまで繰り返し,1個体あたりの
平均評価計算回数が1500MCsweepとなるように設定した.
インターネット環境での実験結果
総実行時間
最小エネルギーの平均値
1400
-20
Blocking
Nonblocking
-22
-24
-26
1200
Elapsed time [sec ]
Energy [kcal/mol]
Blocking
Nonblocking
1000
800
600
400
200
-28
0
2
4
8
Population size
16
2
4
8
Population size
16
 8個体までは2個体の場合と変わらない時間で探索が終了した.
 非同期モデルは同期モデルに比べて短い探索時間で探索を行うこと
が示された.
インターネット環境での処理時間
インターネット環境(100MCsweep)
インターネット環境 (10MCsweep)
2500
12000
10000
交叉以外の待機時間
交叉処理の時間
Serverでの計算時間
通信時間
RPCの累積待機時間
Elapsed time [ sec ]
Elapsed time [ sec ]
14000
8000
6000
4000
2000
1500
交叉以外の待機時間
交叉処理の時間
Serverでの計算時間
通信時間
RPCの累積待機時間
1000
500
2000
0
0
2
4
8
Population size
16
2
4
8
Population size
16
 ServerでのSAのステップ数を100MCsweep行ったものでは,オー
バーヘッドが十分に隠れている.
 オーバーヘッドが十分に隠れる交叉間隔を決定する方法が必要
交叉間隔と解探索性能 (C-peptide)
 Serverでの探索ステップ数=PSA/GAcの交叉間隔
 PSA/GAcには最適な交叉間隔が存在する.
C-peptide 16個体×6000MCsweep
Success ratio
1
Success ratio
0.8
0.6
0.4
0.2
0
1
2
4
8
16
32
Crossover Interval
64
100 PSA
実験2のまとめ
 Serverでの探索時間がオーバーヘッドに比べて十分長ければ,
同期モデルと比較して,非同期モデルの高速化が示された.
交叉間隔が32MCsweep以上 の場合,
 交叉間隔が短い場合
解探索性能
 高速化

向上
低下
 交叉間隔が長い場合
解探索性能
 高速化

トレードオフの関係
低下
向上
 オーバーヘッドが隠蔽できるだけの計算時間を要する探索を
Serverで行う必要があり,これを見積もることが重要.
エネルギー評価計算時間の見積り
 タンパク質の構造エネルギー式より,エネルギー評価計算時間
は原子数の組み合わせに比例すると考えられる.
3×nC2+n
静電力項
・・・nC2
レナードジョンズ項
・・・nC2
水素結合項
・・・nC2
ねじれ角項
・・・n
エネルギー評価計算時間の見積り
e.g. Met-enkephalinの計算時間からC-peptideの計算時間を見積もる.
原子数
Met-enkephalin
C-peptide
比率
75
3×75C2+75 =8400
218
3×218C2+218=71177
1
8.47
Elapsed time [sec]
0.010
C-peptide 計算値
0.008
C-peptide 実験値
0.006
0.004
計算値と実験値は
ほぼ同等
0.002
0.000
gp240
msc
Machine
torc
Serverで実行するMCsweep数の見積り
 交叉間隔の見積り:
オーバーヘッドの時間に比べて,Serverでの計算時間を十分長くする
Serverでの計算時間 = オーバーヘッドの時間 × α
Serverでの計算時間
= エネルギー評価計算時間 × 二面角数 × MCsweep数
α=Serverでの計算時間を十分長くとるためのパラメータ
→ より早く,良好な解の探索
e.g. Met-enkephalinの評価計算時間= 6.2E-4 sec,
オーバーヘッド=2sec, α=16 この時のC-peptideの交叉間隔見積り
→ C-peptideの評価計算時間=5.25E-3sec
(オーバーヘッド×α = 評価計算時間 ×二面角数×MCsweep数)
2 ×16 =
5.25E-3 ×
64×MCsweep数
→ 約100MCsweep
まとめ
 Grid環境におけるタンパク質立体構造予測システムを構築

Grid環境でアプリケーションを構築するツール:NetSolveシステム
 最適化アルゴリズム:PSA/GAc
 Grid環境に適したPSA/GAcの計算モデルの検討
非同期モデルは同期モデルと解探索性能がほぼ同等であった.
 クラスタ,インターネット環境において,高速化が示された.
 個体数を増やすことで解の信頼性が向上.

 オーバーヘッドを隠蔽するメカニズムの検討
ネットワーク → オーバーヘッドの測定
 Serverでの単位計算量あたりの計算時間,対象問題の原子数と
二面角数

→ 適切な交叉間隔を決定
補足資料
NetSolveの環境設定
Agent : ジョブの調整
(1) Agentの起動
(2) Serverの起動
Server : ジョブの実行
server_config
PDF(問題記述ファイ
ル)
ライブラリ
NetSolveのAPIを用いたプログラムを作成
Client
(3) ジョブの実行要求
環境変数にNetSolve Agentを指定
request= netslnb(“problem()",arg1,arg2);
NetSolveとNinf
 NetSolveの特徴



タスクファーミング機能
Serverにプログラムを送り込んで,実行できる
Agentさえ知っていれば,実験ができる
 Ninfの特徴


Serverの指定ができる
NetSolveよりもオーバーヘッドが短い
交叉に選択される個体
個体16 がペアを組んだ回数
交叉ペアを組んだ回数
100
80
60
個体1
個体4
個体7
個体10
個体13
個体2
個体5
個体8
個体11
個体14
個体3
個体6
個体9
個体12
個体15
 Agentは問題を解決できるServer
をランダムに紹介する.
 同じ個体が同じServerに送られる
わけではないため,ランダム性が
保たれる.
40
 同じ個体とだけ交叉するわけでは
ない.
20
0
16
Population size
個体数16のときのオーバーヘッド
同期モデルの各処理時間
クラスタ環境
1200
Serverでの計算時間
通信時間
RPCの累積待機時間
14000
Elapsed time [ sec ]
Elapsed time [ sec ]
1400
インターネット環境
1000
800
600
400
12000
10000
8000
6000
4000
200
2000
0
0
2
4
8
Population size
16
Serverでの計算時間
通信時間
RPCの累積待機時間
2
4
8
Population size
16
 1台でも遅いServerが選ばれる可能性が高くなる.
 Agentでは問題を解決できるServerをランダムに選択するため,
紹介依頼→Agentから選択→状態の問合せ→・・・を繰り返す
(Ala)10の結果(クラスタ環境)
総実行時間
最小エネルギー到達率
200
1
Blocking
Blocking
Nonblocking
Elapsed time [sec ]
Success ratio
0.8
Nonblocking
150
0.6
100
0.4
50
0.2
0
0
2
4
8
Population size
16
2
4
8
16
Population size
 2つのモデルの解探索性能はほぼ同等である.
 2つのモデルは個体数が増えるに従い,1試行の実行時間が増加している.
 非同期モデルは同期モデルに比べて高速化がはかれている.
個体数と利用ノード)
Nonblocking
Blocking
RPCの実行回数
600
500
400
msc01
msc03
msc05
msc07
gp240-2
gp240-4
700
msc02
msc04
msc06
msc08
gp240-3
600
RPCの実行回数
700
300
500
400
200
100
100
0
0
4
8
Population size
16
msc02
msc04
msc06
msc08
gp240-3
300
200
2
msc01
msc03
msc05
msc07
gp240-2
gp240-4
2
4
8
Population size
16
 各ノードに,ほぼ同じ回数のRPCが投げられている.
 16個体のときには,mscに投げられる割合が多くなっている.
 NetSolveにおけるジョブのスケジューリングはServerやネットワークのシステム情報を
見るわけではなく,Serverの設定ファイルに記述された実行可能ジョブの数を見ている
エネルギーの平均値と中央値
インターネット環境
クラスタ環境
-5
-5
Blocking Average
Nonblocking Average
Blocking Median
Nonblocking Median
-7
-6
Energy [kcal/mol ]
Energy [kcal/mol ]
-6
-8
-9
-10
-7
-8
-9
-10
-11
-11
-12
-12
0
5
10
15
Population size
Blocking Average
Nonblocking Average
Blocking Median
Nonblocking Median
20
0
5
10
15
Population size
20
 エネルギーの中央値と平均値はどちらのモデルが良いとは言えない.
 非同期モデルはやや解探索性能にばらつきがあるものの,ほぼ同期
モデルと同等の性能を得ている.
対象タンパク質

最小エネルギー値が既知のタンパク質 : Met-enkephalin

5個のアミノ酸から成る

設計変数 : 19個の二面角

1MCsweepあたり19回のアニーリング

最小エネルギー構造 E ≦ -11 kcal/mol
アミノ残基数
二面角数
最小エネルギー構造
5
19
E ≦ -11 kcal/mol
シミュレーテッドアニーリング(SA)
 金属の焼き鈍しの物理現象を模倣した最適化手法
 改悪方向への推移を確率的に認める → 局所解からの脱出
受理率 P = 1
改悪方向
-(Enext-
exp
P
=
受理率
Ecurrent
)
Temperature
Metropolis基準
受理判定
推移
低温の場合
高温の場合
クーリング

単純なSAでは,大規模なタンパク質の構造予測は困難
→GAのオペレータの導入
energy
生成
改良方向
遺伝的アルゴリズム(GA)
 生物の進化を模倣した最適化手法
 遺伝的操作(選択,交叉,突然変異)を繰り返し個体を成長させる
 大域的な探索ができる
GAオペレータ
個体
母集団
選択
適合度の高い個体が
生き残る
交叉
個体間の情報交換
部分解を組み合わせる
突然変異
個体情報の変更
大規模なタンパク質にはα-helixやβsheetなど部分解が存在する
→ 交叉処理によって,より早く,よりエネルギーの低い構造を発見する
タンパク質のモデル化
 エネルギー関数: KONF90


ECEEP/2エネルギー関数のパラメータを用いている.
気相中を想定しており,溶媒の影響は考えない.
構造エネルギー = 静電力 + 分子間力 + 水素結合 + ねじれ角
 設計変数:主鎖と側鎖の二面角

原子間の回転角を変化させ,最もエネルギー値の低い
組み合わせを求める
Monte Carlo Sweep
二面角の配列
1
2
3
N
1
2
3
N
生成, 受理判定, 推移
1
2
3
N
生成, 受理判定, 推移
1
2
3
N
生成, 受理判定, 推移
各二面角において順にSAの生成,
受理判定,推移を行う.
1
2
3
N
生成, 受理判定, 推移
1 MCsweep
クラスタ環境での実験結果(Met-enkephalin)
総実行時間
最小エネルギー到達率
1
100
Success ratio
0.8
Blocking
Elapsed time [sec ]
Blocking
Nonblocking
0.6
0.4
80
60
40
0.2
20
0
0
2
4
8
Population size
16
Nonblocking
2
4
8
16
Population size
 2つのモデルの解探索性能はほぼ同等である.
 2つのモデルは個体数が増えるに従い,1試行の実行時間が増加している.
 非同期モデルは同期モデルに比べて高速化がはかれている.
インターネット環境での実験結果
総実行時間
最小エネルギー到達率
1
700
Blocking
Nonblocking
Elapsed time [sec ]
Success ratio
0.8
Blocking
600
0.6
0.4
Nonblocking
500
400
300
200
0.2
100
0
0
2
4
8
Population size
16
2
4
8
16
Population size
 クラスタ環境同様,2つのモデルの解探索性能はほぼ同等である.
 4個体までは非同期モデルは同期モデルに比べて短い時間で探索が終了し
ているが,8,16個体で2つのモデルの計算時間が急増している.
交叉間隔と解探索性能 (PTH(1-34))
 PTH(1-34)のような部分構造をもつタンパク質においては,
PSA/GAcの交叉を頻繁に行うことで解探索性能が向上する.
 210kcal/mol以下の時に最小エネルギー構造が得られたとした.
平均エネルギー値
最小エネルギー構造到達率
1
64個体×1500MCsweep
32個体×3000MCsweep
0.8
16個体×6000MCsweep
Success ratio
Energy [ kcal/mol ]
-190
-210
0.6
0.4
-230
64個体×1500MCsweep
0.2
32個体×3000MCsweep
16個体×6000MCsweep
-250
0
1
2
4
8
16
32
Crossover Interval
64
PSA
1
2
4
8
16
32
Crossover Interval
64
PSA
ダウンロード

インターネット環境