九州大学大学院 情報学専攻特別講義 （５）タンパク質立体構造の比較と予測

Presentation on theme: "九州大学大学院 情報学専攻特別講義 （５）タンパク質立体構造の比較と予測"— Presentation transcript:

1 九州大学大学院 情報学専攻特別講義 （５）タンパク質立体構造の比較と予測
九州大学大学院　情報学専攻特別講義 （５）タンパク質立体構造の比較と予測 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 講義内容 バイオインフォマティクス概論（資料なし） 配列アラインメント 配列解析 RNA二次構造予測 タンパク質立体構造の比較と予測
固定パラメータアルゴリズムと部分k木 グラフの比較と列挙 ニューラルネットワークの離散モデル ブーリアンネットワークの解析と制御 講義の進展状況によっては内容に変更の可能性あり

3 立体構造アラインメント

4 配列が似ていなくても構造類似の蛋白質が多数存在 構造分類データベース
タンパク質立体構造比較の必要性 立体構造と機能の間には密接な関係 配列が似ていなくても構造類似の蛋白質が多数存在 構造分類データベース SCOP（人間が分類） FSSP（DALIプログラムにより分類） CATH（SSAPプログラムなどにより分類）

5 立体構造アラインメント 立体構造の類似性判定のために有用
どのように回転、平行移動すれば、最適な残基間の対応づけ（アラインメント）が得られるかを計算 配列アラインメントの場合と異なり、決定版というようなアルゴリズムが無い

6 構造アライメント例 ヘモグロビン ミオグロビン

7 RMSD(Root Mean Square Deviation)
点（e.g., Cα原子）の対応関係がわかっている場合に最適な重ね合わせとなる回転・平行移動を計算 行列計算により O(n) 時間で計算可能 p1 p2 q1 p3 q4 q3 q2 p4 T

8 構造アラインメントプログラム: stralign
広くは利用されていないが、理論（計算幾何学）的考察に基づいてアルゴリズムが設計されている 東大HGCよりダウンロード可能 [Akutsu 1996] 問題の定義 入力： ３次元点列: P=( p1,…, pm ), Q=(q1,…, qn),および、 実数δ　　　（m ≦ n とする） 出力： 以下を満たし、かつ、長さ（アラインされる点のペアの個数）が最大となる P,Q 間のアライメント M （および、付随する平行・回転移動 T ）

9 stralign の基本アルゴリズム M0← {} for all triplets PP=(pi1,pi2,pi3) from P do
for all triplets QQ=(qj1,qj2,qj3) from Q do Compute rigid motion TPP,QQ from PP to QQ Compute alignment M between TPP,QQ(P) and Q if |M| > |M0| then M0 ← M Output M0

10 TPP,QQ q3 p1 q1 q2 p3 p2 回転・平行移動 TPP,QQ の計算法
PP=(p1,p2,p3)、QQ=(q1,q2,q3) に対するTPP,QQ の計算法 p1 が q1 に重なるように PP を並行移動 p1p2 と q1q2 が同一直線上にあるように、 PP を回転移動 PP と QQ が同一平面上にあるように、PP を p1p2 を軸として回転移動 p1 q1 q2 p3 p2 TPP,QQ

11 T(P) と Q に対するアライメント M の計算
cδ q1 q2 q3 q4 p1 p2 p3

12 T(p) p3 p p2 p1 q TPP,QQ(p) 基本アルゴリズムの性能解析(1) T TPP,QQ
補題： PP=(p1,p2,p3), QQ=(q1,q2,q3)とし、T を |T(pi) - qi| ≦δ (i=1,2,3) を満たす変換とすると、 任意の p  reg(p1,p2,p3) について以下が成立 　　　|T(p) - q| ≦ δ ならば |T PP,QQ(p) - q| ≦ 8δ ≦δ ≦8δ q p T(p) TPP,QQ(p) T TPP,QQ p3 p2 p1

13 基本アルゴリズムの性能解析(2) 定理：　 δに対する最適アラインメントを MOPT とすると、基本アルゴリズムは O(n8) 時間で、以下を満たすアラインメント M （と変換 T）を出力する 証明概略 MOPT に現れる P,Q の部分集合を、それぞれ、P’,Q’ とする。すると、P’ がregの中に全部含まれるような PPP’ が存在。 MOPT において、PP に対応する QQ も存在し、補題の仮定を満たす。よって、T(P’) は Q’ と 8δ 以内でマッチするため、アルゴリズムは |M|≧|MOPT| を満たすアライメントを出力。 注： （かなり大きくなるが）定数倍の時間をかければ、8δ は δ に近づけることが可能

14 実用版 stralign 基本アルゴリズムは O(n8) 時間かかるので非実用的
ランダムサンプリング や sparse DP などを用いると O(n5) 時間くらいに近づけることができるが、それでも非実用的 そこで、理論的な性能保証はあきらめ、実用的なアルゴリズムを開発 PP,QQ として 長さ 10～20残基程度の連続した fragment を利用し、TPP,QQ は rmsd の計算法により求める 全部で O(n2) ペアしか調べないので、 O(n2)×DPの計算量= O(n4)時間 。実際には rmsd が大きいペアには DP を行わないため、より高速。 解の精度を高めるため、「アライメント ⇒ rmsd fitting」 を数回繰り返す 多くの場合、数秒程度でアライメント可能

15 他の構造アラインメント・アルゴリズム 数多くの構造アライメント手法が提案 例 DALI（距離行列のアラインメント）
SSAP(二重DP) [Taylor & Orengo 1989] CE (Combinatorial Expansion) [Shindyalov & Bourne 1998] VAST (Vector Alignment Search Tool) [Gibrat et al. 1998] DP+Iterative Improvement [Gernstein & Levitt 1998] StrMul (二重ＤＰを基にした多重構造アラインメント） [Daiyasu & Toh 2000]

16 DALI (Alignment of Distance Matrices)
Distance Matrix のアラインメント [Holm & Sander 1993] Distance Matrix （同一タンパク P 内の）残基間の距離を行列形式で表現したもの P と Q の distance matrix （ただし、アラインメントされる残基のみから構成される行列）ができるだけ類似するようなアラインメントを計算 Simulated Annealing に類似した方法を用いて、アラインメントを計算 3 5 8 6 1 4 2 7 G L A D V E R - アラインメント

17 Contact Map Overlap (CMO) 問題 （１）
立体構造をグラフで表現 {vi,vj}E ⇔ 残基 vi と vj 間の距離がθ以内 以下の制約のもとでアラインされる残基ペアを最大化 アライメントにおいて (vi,uk) と (vj,ul) が対応するなら、 {vi,vj}E　⇔ {uk,ul}E’ K L V A U C I P G H

18 Contact Map Overlap (CMO) 問題 （２）
NP困難 [Goldman et al. 1999] しかし、実際多くのタンパク質立体構造について最適解が計算可能 [Caprara et al. 2004] 整数計画法の利用 分枝限定法の利用 グラフの最大クリーク問題に還元可能（下図参照） 深く関連する問題 RNA二次構造比較 [G-H. Lin et al. 2002] ペアエネルギー関数のもとでのスレッディング [Akutsu & Miyano 1999] vi vj uk ul

19 構造のマルチプルアライメントの困難性 いくつかのアルゴリズム( CE-MC, StrMul, … ) が提案されているが、ヒューリスティクスに基づいており、解の性能保証は無い 配列のマルチプルアラインメントと同様に本質的な困難さ(NP困難)があると予想される 実際、以下の問題として解釈すると、NP困難 最大共通部分点集合問題(LCP) [Akutsu & Halldorson 2000] 入力： d 次元空間上の点集合 S1, S2, …, SN 出力： 以下を満たし、最大の要素数を持つ d 次元空間上の点集合 C 各集合 Si に対し、等長変換 Ti が存在し、 T1(S1)  T2(S2) …TN(SN) = C

20 タンパク質立体構造予測

21 タンパク質立体構造予測 アミノ酸配列から、タンパク質の立体構造（３次元構造）をコンピュータにより推定 実験よりは、はるかに精度が悪い
だいたいの形がわかれば良いのであれば、４～５割近くの予測率

22 立体構造予測法の分類 物理的原理に基づく方法 (ab initio法) ホモロジーモデリング ２次構造予測 格子モデル スレッディング
　立体構造予測法の分類 物理的原理に基づく方法 (ab initio法) エネルギー最小化、分子動力学法 ホモロジーモデリング 配列アラインメントにより主鎖のだいたいの配置を決定した後、主鎖や側鎖の配置の最適化を分子動力学法などで実行 ２次構造予測 各アミノ酸がα、β、それ以外のいずれかにあるかを予測 ランダムに予測すれば33.3…%の予測率であるが、高性能の手法を用いれば80%近い予測率 格子モデル スレッディング 予測したい配列と既知構造の間のアラインメントを計算 フラグメント・アセンブリー法 数残基から十数残基からなる複数のフラグメント候補をデータベース検索により選択した後、分子動力学法などを用いてそれらをつなげ合わせる

23 格子モデル 折れ畳み経路のシミュレーションによる定性的理解 →フォールディングファンネル エネルギー最小の構造の計算法→NP困難 スコア
折れ畳み経路のシミュレーションによる定性的理解　→フォールディングファンネル エネルギー最小の構造の計算法→NP困難 親水性アミノ酸 疎水性アミノ酸 スコア ＝－９ ＝－５ 配列

24 格子モデル タンパク質構造予測のための、最も単純な数理モデル 平面、もしくは、空間の格子点の中で折り曲げる
隣にくる赤点（疎水性アミノ酸）の個数を最大にする 　　　　　　　　　　　　（ただし、もともと隣にある点は対象外） 配列 親水性アミノ酸 疎水性アミノ酸 スコア＝９ スコア最大＝最適解 スコア＝５

25 格子モデルの最適解の計算 最適解（最大値を持つ答）の計算はとても難しい
スーパーコンピュータを使っても1000アミノ酸の問題は（たぶん）解けない 最大値が計算できないなら、近似解（最適解に近い値を持つ答）は計算できないだろうか？ ⇒最適解はわからなくても、最適解の4分の1程度 　　以上の値の答なら、いつでも速く計算可 最適解がわからないのに、何でそんなことが できるのだろうか？

26 格子モデル（HPモデル）の近似に関する理論的結果
２次元で1/4近似、３次元で3/8近似 　　　　　　　　　　　 　(Hart & Istrail, 1995) ３次元でNP-Hard (Berger,Leighton,1998) ２次元でNP-Hard (Crescenzi et al.,1998) ２次元で1/3近似 (Newman, 2002)

27 最大値の見積もり 性質（１） 奇数番目の点は、偶数番目の点としか隣り合わない 偶数番目の点は、奇数番目の点としか隣り合わない 性質（２）
以降ではわかりやすくするため、偶数番目の赤点は青点に書き換える 性質（２） （はしの２点以外は）１個の点は２個の点としか隣り合わない X : 赤点の個数 Y : 青点の個数 X ≦Y とする (逆の時も同様） 最大値 ≦2X+2

28 近似解の計算 （１） もとの配列を中間くらいで切る 前半分を青点が1個おきに並ぶように折り曲げる
前半に青点の半分以上、後半に赤点の半分以上が来るように切る 　　（そうできない場合には、赤と青を入れ替えれば大丈夫） 前半分を青点が1個おきに並ぶように折り曲げる 後半分を赤点が1個おきに並ぶように折り曲げる

29 近似解の計算 （２） もとの配列を中間くらいで切る 前半分を青点が1個おきに並ぶように折り曲げる
後半分を赤点が1個おきに並ぶように折り曲げる 折り曲げたものを向かい合わせにする

30 近似解の解析 下側の赤点には、必ず青点が結合 最適解（の値）は 2X+2 以下だった 近似解は赤点の半分以上 ⇒ X/2 以上 よって、
もとの配列を中間くらいで切る 前半に青い点の半分以上、後半に赤い点の半分以上が来るように切る 前半分を青点が1個おきに並ぶように折り曲げる 後半分を赤点が1個おきに並ぶように折り曲げる 折り曲げたものを向かい合わせにする 下側の赤点には、必ず青点が結合 最適解（の値）は 2X+2 以下だった 近似解は赤点の半分以上　⇒　X/2 　以上 よって、

31 まとめ 補足 タンパク質立体構造アラインメント タンパク質立体構造予測 タンパク質構造比較に利用、決定版（定式化）は無い
比較的単純なアルゴリズムにより定数近似が可能 タンパク質立体構造予測 様々な定式化、方法が存在 HPモデルはNP困難であるが、定数近似が可能 補足 構造アラインメントに関して、今回と似た定式化のもとで O(n32) 時間で厳密解が計算可能 [Ambuhl et al.: Proc. ESA 2000] RMSDを用いた部分構造検索は平均的に高速に実行可能 [Shibuya: J. Comp. Biol. 2007] HPモデルの2次元の場合の近似は1/3まで改善 [Newman: Proc. SODA 2002]