2個体分散遺伝的アルゴリズムによる タンパク質立体構造のエネルギー最小化 同志社大学 同志社大学 ○ 同志社大学大学院 国立分子科学研究所 廣安 知之 三木 光範 岩橋 崇史 岡本 祐幸 研究背景 バイオインフォマティクス Bio (生物学) ＋ informatics (情報学) 情報技術を用いて，生命現象を解明 バイオインフォマティクス分野の課題 遺伝子の特定と機能の推定 タンパク質立体構造の推定 遺伝子ネットワークの推定 タンパク質立体構造の推定 タンパク質 生物の生命現象の中で重要な役割を担っている タンパク質の機能 タンパク質の立体構造 タンパク質の立体構造の解明 新薬の開発 病理の発現機構の解明 アルツハイマー 狂牛病 C-peptide タンパク質の立体構造に関する研究 実験的手法 NMR法，X線結晶構造解析 実験環境が解析結果に影響 純粋なタンパク質が 大量に必要 分子シミュレーション 運動方程式を用いて， 立体構造を予測 アミノ酸の配列情報のみが 必要 タンパク質の立体構造 タンパク質 アミノ酸が連なっている エネルギーの最も低い状態で存在 High Energy エネルギー最小構造を 求めることにより，タンパク質の 立体構造を予測可能 Low Energy 最適化問題としてとらえる タンパク質のモデル化 設計変数：二面角 タンパク質の原子間の回転角 目的関数：エネルギー関数(KONF90) [岡本,1991] タンパク質の持つエネルギー値を定義する式 二面角 原子間の回転角 Energy : 3243 A B C D 二面角 原子間の回転角 Energy : 3243 A A 二面角を回転 B B C D C D 二面角 原子間の回転角 立体構造が変化 エネルギー値が変化 Energy : 3243 Energy : 231 A A 二面角を回転 B B C D C D エネルギー最小化 二面角の組み合わせを最適化 Optimum タンパク質の立体構造予測 e.g. 5つのアミノ酸残基を持つMet-enkephalin Energy : - 11 タンパク質のエネルギー関数 タンパク質の持つエネルギー値（Ep）を定義する式 ECEPP/2のエネルギーパラメータを採用したKONF90 静電力項 レナードジョーンズ項 水素結合項 ねじれ角項 タンパク質のエネルギー関数 局所的に無数の極小値を持ち， 大域的にもいくつかの極小値 を持つ 高い探索能力を持つ最適化手法が必要 シミュレーテッドアニーリング(SA)が良く用いられている 遺伝的アルゴリズム(GA)では，困難であると報告されている [Laurence，1996] 遺伝的アルゴリズム(GA) 生物の進化を模倣した最適化アルゴリズム 母集団に対して，遺伝的操作を繰り返し適用 多点探索により，大域的な探索に優れている 個体 母集団 対象タンパク質 Met-enkephalin 5個のアミノ酸から構成される 最小エネルギー構造 E ≦ ー11 [kcal/mol] 19個の二面角 Met-enkephalin 実験パラメータ 個体数 800, 1600, 3200, 6400 設計変数(二面角数) 19 染色体長 171 (=19×9) 交叉率 交叉法 突然変異率 0.6 1点交叉 0.006 (=1/171) 終了条件 1.9×106評価 試行回数 30 実験結果 全ての個体数において，最適解発見率が低い 解探索が早熟収束することを確認した 早熟収束を回避した 多様性を維持する探索を行うGAモデルが有効 分散遺伝的アルゴリズム(DGA) 母集団をサブ母集団(島)に分割 島内でGAの遺伝的操作を行う 移住による島間の個体の交換 サブ母集団 (島) DGAの特徴 島数の増加による多様性の向上 パラメータ設定の複雑化 サブ母集団サイズ，移住率，移住間隔 2個体分散遺伝的アルゴリズム(Dual DGA) 島内の個体数が 2 島内の個体数に適した遺伝的操作 Dual DGAの遺伝的操作（移住） 移住 2個体のうち，一方のコピーを他の島へ送る 適合度の低い個体と移住個体を交換する 他の島へ 移住 移住個体 高 低 移住個体と 適合度の低い個体を交換 Dual DGAの遺伝的操作（交叉，突然変異） 交叉 親個体を交叉し，子個体を生成 突然変異 子個体の一部を変化 Dual DGAの遺伝的操作（選択） 選択 親個体から適合度の高い方の個体を選ぶ 子個体から適合度の高い方の個体を選ぶ 低 高 低 高 次世代へ生き残る Dual DGAの特徴 多様性を維持した探索 DGAよりもパラメータ設定が減少 設定すべきパラメータが固定 サブ母集団サイズ 2 移住率 0.5 交叉率 1.0 タンパク質立体構造のエネルギー最小化に 有効な手法だと考えられる 数値実験 DualDGAによるMet-enkephalinの立体構造 のエネルギー最小化 DualDGAとタンパク質立体構造の エネルギー最小化に用いられている 他の最適化手法の比較 実験パラメータ GA DGA 母集団サイズ サブ母集団サイズ 400, 800, 1600, 3200, 6400 - 4, 8, 16 設計変数（二面角の数） 2 19 染色体長 171 (=19×9) 交叉率 交叉法 Dual DGA 0.6 1.0 1点交叉 突然変異率 0.006 (=1/171) 移住間隔 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 移住率 - 0.25 0.5 終了条件 1.9×106 評価 試行回数 30 個体数の変化による最適解発見率 DualDGA 個体数が増すことにより， 最適解発見率が向上 個体数が6400のとき， 最も最適解発見率が高い DGA 島内の個体数により， 最適解発見率が異なる GA 全ての個体数において， 最適解発見率が低い 解探索履歴(個体数6400) DualDGA，DGAは早熟収束することなく， 有効な解探索を行っている 他手法との比較 タンパク質立体構造のエネルギー最小化に 用いられている他手法と比較する シミュレーテッドアニ－リング(SA) [岡本,1993] 金属の物理現象を模倣した最適化手法 遺伝的交叉を用いた並列SA(PSA/GAc) [廣安,2002] SAとGAを組み合わせたハイブリッドアルゴリズム タンパク質立体構造のエネルギー最小化に 有効な手法であると報告されている 他手法との比較結果 SAよりも最適解発見率が 高い PSA/GAcと最適解発見率 がほぼ等しい値を示した まとめ GAによるタンパク質立体構造のエネルギー最小化 は困難であると報告されていた 早熟収束に注目し，多様性を維持した探索を行う GAモデルの検討を行った Dual DGAは小規模のタンパク質（Metenkephalin）の立体構造のエネルギー最小化に対 して 有効な手法であることを示した 個体数は多いほど，解探索能力が増す SAよりも，解探索能力が高い PSA/GAcとほぼ同等の解探索能力である Fin Appendix タンパク質の機能 タンパク質は生物の生命現象に重要な役割を担っている センサー(受容器) 外界からの刺激を感知し，情報を伝える． (ex.神経伝達物質) ヘモグロビン 酸素を筋肉などの組織に運ぶ 免疫 身体防御システム(ex.抗体) 酵素 生体内での化学反応を調整 細胞 体を構成する要素 (ex.筋肉,皮膚,DNA) 実験によるタンパク質の立体構造解析 X線結晶構造解析法 空気中の立体構造を知るための方法 結晶化したタンパク質にX線を当てることにより， 解析を行う 生理条件下でのタンパク質の立体構造を解析不可能 核磁気共鳴(NMR)法 水溶液(溶媒)中での立体構造を知るための方法 溶媒中でタンパク質を高速に回転し，解析を行う 小規模なタンパク質のみ解析が可能 タンパク質のモデル化 全原子型モデル 設計変数は二面角 立体構造予測が困難 予測の精度は高い 格子型モデル 設計変数はアミノ酸 立体構造予測が容易 予測の精度は低い GAベースによる他の研究 格子型モデル モンテカルロ法を用いたGA (MCGA) [Unger, Moult ,1993] ローカルサーチを組み込んだGA (Multimeme Algorithms ) [N.Krasnogor，2002] 全原子型モデル UNDXを用いた実数値GA [友部，1998] ビットストリング型と実数値型を 組み合わせた階層型GA [高橋，1999] 早熟収束 早熟収束により， 解探索序盤に局所解に陥る場合がある 低 適合度 高 早熟収束を回避するために， 多様性を維持した探索を行う必要がある 移住間隔の変化 (個体数1600) 移住間隔の変化 (個体数3200) 移住間隔の変化 (個体数6400) 移住間隔の変化 (個体数12800) 最適な移住間隔 DualDGA 母集団サイズ DGA(8) 移住間隔 母集団サイズ 移住間隔 400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 800 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 800 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1600 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1600 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 3200 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 3200 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 6400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 6400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 DGA(4) DGA(16) 母集団サイズ 移住間隔 母集団サイズ 移住間隔 400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 800 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 800 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1600 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1600 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 3200 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 3200 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 6400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 6400 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 最適な移住間隔 DGA(8) DualDGA 母集団サイズ 移住間隔 400 400 1, 10 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9 9,, 10 800 800 1, 7, 8, 8, 9, 9, 10 10 1, 2, 2, 3, 3, 4, 4, 5, 5, 6 6,, 7, 1600 1600 1, 10 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9 9,, 10 3200 3200 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7 7,, 8, 8, 9, 9, 10 10 6400 6400 1, 7, 8, 8, 9, 9, 10 10 1, 2, 2, 3, 3, 4, 4, 5, 5, 6 6,, 7, DGA(16) DGA(4) 母集団サイズ 母集団サイズ 移住間隔 移住間隔 400 400 1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10 10 800 1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10 800 10 1600 1, 1600 1,2, 2,3, 3,4, 4,5, 5,6, 6,7, 7,8, 8,99, 10 , 10 3200 1,1,2,2,3,3,4,4,5,5,6,6,77, ,8,8,9,9,10 3200 10 6400 1,1,2,2,33, 6400 4,5, 5,6, 6,7,7,8,8,9,9,10 10 , 4, DualDGA，DGAともに 個体数によって，最適な 移住間隔が異なる DGAでは，島内の個体数 により，最適な移住間隔 が異なるため，最適な パラメータ設定が困難で ある 移住率の違いによる最適解発見率 DGA(4)は移住率0.5の方が 解探索能力が高い DGA(8)，DGA(16)は 移住率0.25の方が解探索能力 が高い DualDGAの解探索履歴（個体数6400） 移住間隔が大きくなるにつれて，多様性を維持した探索を 行うが，解探索終盤において収束性を失う DGA(16)の解探索履歴（個体数6400） 移住間隔の大きさの違いにより， 解探索履歴に大きな差は現れなかった DualDGA，DGA(16) (個体数6400，移住間隔10) DualDGA DGA(16) DualDGA 移住後，解探索は停滞する DGA(16) 移住後においても，解探索は進む 評価計算回数 3.8×106 (= 1.9×106 × 2) 最大評価計算回数を伸ばすことによって， 最適解発見率が向上する 有効な解探索を行うには移住が重要である 対象タンパク質 タンパク質 Met-enkephalin 二面角 19 30 64 (Ala)10 C-peptide Met-enkephalin (Ala)10 最適解領域 E ≦ ー11 [kcal/mol] E ≦ ー9.7 [kcal/mol] E ≦ ー42 [kcal/mol] C-peptide 実験結果（DualDGA，DGA） タンパク質 Met-enkephalin 二面角 (Ala)10 C-peptide Met-enkephalin DualDGA 19 93 % 30 64 (Ala)10 DGA 90 % 96 % 0% C-peptide 87 % 0% MGGの実験パラメータ 母集団サイズ 400 生成個体数 100 設計変数（二面角の数） 19 染色体長 171 (=19×9) 交叉率 交叉法 突然変異率 1.0 2点交叉 0.006 (=1/171) 終了条件 1.9×106 評価 試行回数 30 DualDGA，MGG，GAの解探索履歴 MGGよりもDualDGAの方が，多様性を維持した探索 を行っている 実験結果（DualDGA，MGG） タンパク質 Met-enkephalin 二面角 (Ala)10 C-peptide Met-enkephalin DualDGA 19 93 % 30 64 (Ala)10 MGG 60 % 96 % 0% C-peptide 0% 0% シミュレーテッドアニーリング(SA) 金属の物理現象を模倣した最適化手法 改悪方向への推移を確率的に認める 局所解への脱出 単純なSAでは，大規模なタンパク質立体構造の エネルギー最小化は困難である 受理率 P = 1 改悪方向 －(Enext－ exp P = 受理率 Ecurrent ) Temperature Metropolis基準 受理判定 推移 クーリング 低温の場合 高温の場合 energy 生成 改良方向 遺伝的交叉を用いた並列SA（PSA/GAc） SAとGAのハイブリッドアルゴリズム SAは局所的な探索に優れている GAは大域的な探索に優れている 並列SA + 遺伝的交叉 遺伝的交叉を用いた並列SA 大域的にも局所的にも良好な探索が行える PSA/GAcのメカニズム PSAの解の伝達に遺伝的交叉(Crossover)を用いる手法 PSA/GAcにおける交叉処理 遺伝的交叉の処理：設計変数間交叉 e.g. 3設計変数の連続関数最小化問題 SA, PSA/GAcの実験パラメータ SA 個体数 PSA/GAc 1 20 100000 4992 交叉間隔 --- 32 試行回数 10 10 MCsweep数 / 個体 温度スケジュール 近傍幅 2.0 → 0.1 ±180 → ±54 DualDGAとDGAの比較実験 Rastrigin関数: n 2 F x 10n xi 10cos2xi i 1 5.12 xi 5.12 n 10次元 Griewank関数: 2 n xi xi F x 1 cos i i 1 4000 i 1 512 xi 512 n 10次元 n Rosenbrock関数: n 1 F x 100 xi 1 xi i 1 1 x 2 2 2 i 2.048 xi 2.048 n 10次元 DualDGAとDGAの比較実験 DGA 母集団サイズ Dual DGA 400 サブ母集団サイズ 4, 8, 16 2 設計変数 10 遺伝子長 10 (=10×10) 交叉率 交叉法 突然変異率 移住間隔 移住率 1.0 1点交叉 0.01 (=1/100) 5 0.5 終了条件 4.0×104評価 試行回数 100 実験結果（Rastrigin関数） DualDGAの方がDGAよりも解収束が遅い DGAよりも多様性を維持した探索を行っている 実験結果（Griewank関数） DualDGAの方がDGAよりも有効な解探索を 行っている 多様性を維持し，解探索終盤に解収束している 実験結果（Rosenbrock関数） DualDGAの方がDGAよりも有効な解探索を 行っている 多様性を維持し，解探索終盤に解収束している DGAの汎用パラメータ 母集団サイズ 400, 800, 1600, 3200, 6400 サブ母集団サイズ 10 設計変数（二面角の数） 19 染色体長 171 (=19×9) 交叉率 交叉法 突然変異率 移住間隔 移住率 1.0 1点交叉 0.006 (=1/171) 5 0.5 終了条件 1.9×106 評価 試行回数 30 実験結果 DualDGA，PSA/GAcの利点 DualDGA 多様性を維持した探索を行う 粒度が小さいため，並列化効率が高い PSA/GAc 並列SAによる局所的探索を行う 遺伝的交叉により部分解の交換を行う 選択操作の検討 親個体と子個体から適合度の高い個体を2個体選択 従来の選択手法とほぼ同等の解探索能力 ハミング距離の比較 Huming Distance 600000 DualDGA 500000 DGA(8) 400000 300000 200000 100000 0 0 500000 1000000 # Evaluation 1500000
© Copyright 2024 ExpyDoc
