ローカルサーチアルゴリズムの
意義とその戦略
小椋 信弥，廣安 知之，三木 光範
ISDL Report No. 20020508013
2002年 9月 19日
Abstract
1 はじめに
小掠らの研究において，小規模なタンパク質であるMet-enkephalinの立体構造予測に遺伝的交叉を用いた並列シミュレーテッドアニーリング(Parallel Simulated Annealing using Genetic Crossover : PSA/GAc)が有効であることが報告されている[1]． しかし今後，PSA/GAcを大規模なタンパク質に適用する際には，その探索の効率化を図る必要がある．
2 ローカルサーチの必要性
大規模なタンパク質の構造予測では計算量が非常に多くなるため，計算に膨大な時間を要する．したがって，大規模なタンパク質の立体構造予測を行うには，最適構造を得るまでの計算量を減らすことが重要となる．何らかの形で局所探索が可能であれば，結果として総計算量を減らすことができると考えられる．局所探索を行う対象として，我々は，非常に特徴的な構造を持つタンパク質の２次構造であるαへリックスに着目した．本研究では，αヘリックス構造が持つ特徴を利用したローカルサーチアルゴリズムを考案する．
3 αへリックスの特徴
αへリックスは，1本のポリペプチド主鎖が規則正しくらせん状に巻いた構造になっている．そこでは，すべてのペプチド結合が水素結合を形成しており，エネルギー的に最も安定な構造である[2]．αヘリックスの構造をFig.1に示す．Fig.1において，各球が原子を表し，原子間を結ぶ点線が水素結合を示している． また，構造中に見えるらせん状の線は，αへリックス構造を模式的に示したものである．
4 αへリックスに着目したローカルサーチ
4.1 ローカルサーチのアルゴリズム
本研究では，前節で述べたαへリックスの特徴を利用して，αへリックスの探索を効率化するためのアルゴリズムを提案する．提案するアルゴリズムは，タンパク質のエネルギー関数の探索中に，あるアミノ残基においてαへリックス構造の一部が見つかったとき，その前後のアミノ残基にαへリックスを拡張するというものである．ある設計変数の付近を局所的に探索する手法であるため，このαへリックス探索手法をローカルサーチと呼ぶ．
本研究では，このローカルサーチをPSA/GAcの探索に導入する．ローカルサーチを用いたPSA/GAcでは，一定期間の探索後，(φ,ψ)=(-70±30°,-37±30°)を持つアミノ残基を探し，みつかればそのアミノ残基が持つ(φ,ψ)の値を前後のアミノ残基の(φ,ψ)にコピーする．コピーすることによりタンパク質のエネルギー値が減少すれば，ローカルサーチの処理を受理する．逆にエネルギー値が増大すれば，コピーされた二面角値を破棄する．ローカルサーチを用いたPSA/GAcのアルゴリズムをFig.2に示す．
4.2 ローカルサーチの効果
本研究で提案するローカルサーチアルゴリズムは，αへリックスを拡張することにより，αへリックスの探索を効率化するものであることは前節で述べた．このローカルサーチアルゴリズムを，PSA/GAcによるタンパク質の立体構造予測に適用することにより，探索の初期でαへリックスが形成され，結果として探索の効率化につながると考えられる．また，大規模なタンパク質には，その構造中に複数のαへリックスが含まれることも少なくないため，今後さらに大規模なタンパク質を対象とする場合にも，本手法の有効性が期待される．
5 まとめ
従来の研究より，PSA/GAcが小規模なタンパク質の構造予測に有効であることが分かった．しかし，今後大規模なタンパク質を解くためには，PSA/GAcの探索を効率化することが必須である．そこで，本レポートではタンパク質の2次構造であるαへリックスの構造に着目したローカルサーチアルゴリズムを考案した．ローカルサーチによって，探索初期でαへリックスが形成され，結果として探索の効率化につながることが期待される．
Reference
- [1]
- 小掠 真貴，廣安 知之，三木 光範，角 美智子，岡本祐幸. 遺伝的交叉を用いた並列シミュレーテッドアニーリングの検討. 情報処理学会研究報告, 2001, 27, 57-60, 2001.
- [2]
- 池内 俊彦. 生命を学ぶ タンパク質の科学. オーム社, 70-6, 1999.
- [3]
- Ayori Mitsutake and Yuko Okamoto, Helix-coil transitions of amino-acid homo-oligomers in aqueous solution studied by multicanonical simulations, JOURNAL OF CHEMICAL PHYSICS, 112, 23, 10638-10646, 2000.
Copyright
Copyright (C) 2002 Shinya Ogura, All rights reserved. Copyright (C) 2002 Tomoyuki Hiroyasu, All rights reserved. Copyright (C) 2002 Mitsunori Miki, All rights reserved. No part of this document may be reproduced, copied, distributed, transferred, modified, or transmitted, in any form or by any means, without the prior written permission of the authors. In no event shall the authors be liable for any damages caused in any way out of the use of this document．