Download presentation
Presentation is loading. Please wait.
1
情報生命科学特別講義III （12） タンパク質立体構造の比較と予測
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
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の中に全部含まれるような PPP’ が存在。 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]
Similar presentations
