集中講義（九州大学数理学研究院） バイオインフォマティクスにおける カーネル法およびグラフ理論 (4) タンパク質立体構造の比較と予測 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義内容 立体構造比較（構造アライメント) 立体構造予測 RMSD stralign 発見的手法: SSAP/DALI/CE/… Contact Map Overlap 問題 構造のマルチプルアライメントの困難さ 立体構造予測 予測法の分類 スレッディング法 プロファイルを用いるスレッディング ポテンシャル型スコア関数を用いるスレッディング ＣＡＳＰ

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

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

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

構造アライメント例 (2) アクチン vs. シャペロンタンパク

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

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

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

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

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

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 p1 p2 p3

基本アルゴリズムの性能解析(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δ は δ に近づけることが可能

実用版 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」 を数回繰り返す 多くの場合、数秒程度でアライメント可能

SSAP (Double Dynamic Programming) DPを二重に用いる [Taylor & Orengo 1989] High level DP 通常の配列アライメントと同様 残基間のスコア Sij を求めるのに、low level DP を利用 Low level DP pi P と qj Q の間のスコアを、 (i,j) を始点( Sij[i,j] = 0 )としてDPにより計算 pk , ql （k≧i, l≧j）の間のスコア skl として以下を利用（a,b は適当な定数） skl = a / (| | pk - pi | - | ql – qj| | + b) 角度などを考慮した、より精密な方法も存在 High level DP Low level DP 注：詳細は異なる 注：I,J は適当な定数

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 - アライメント

他の構造アライメントアルゴリズム 数多くの構造アライメント手法が提案 例 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]

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

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

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

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

立体構造予測法の分類 物理的原理に基づく方法 (ab initio法) ホモロジーモデリング ２次構造予測 格子モデル スレッディング 　立体構造予測法の分類 物理的原理に基づく方法 (ab initio法) エネルギー最小化 分子動力学法 ホモロジーモデリング 配列アライメントにより主鎖のだいたいの配置を決定した後、主鎖や側鎖の配置の最適化を分子動力学法などで実行 ２次構造予測 各アミノ酸がα、β、それ以外のいずれかにあるかを予測 ランダムに予測すれば33.3…%の予測率であるが、高性能の手法を用いれば80%近い予測率 格子モデル スレッディング

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

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

フォールド予測（Fold Recognition) 立体構造は1000種類程度の形に分類される、との予測(Chotia, 1992)に基づく

　タンパク質スレッディング スレッディング：立体構造（テンプレート）とアミノ酸配列の間のアライメント

　スレッディングとアライメント スレッディング アライメント

スレディング法の分類 プロファイルを用いたスレッディング ポテンシャル型スコア関数を用いた スレッディング 　スレディング法の分類 プロファイルを用いたスレッディング ３Ｄ-1D法 (Bowie et al., 1991) PSI-BLAST Profile-Profile アライメント　　　etc. ポテンシャル型スコア関数を用いた 　スレッディング ヒューリスティックな計算法 Frozen approximation, Double dynamic programming 最適解を計算可能な手法 分枝限定法 (Lathrop & Smith, 1996) 分割統治法 (Xu et al., 2000) 線形計画法を用いる方法 (Xu et al., 2003)

　プロファイル アライメントにおけるスコア行列と類似 スレッディングの場合、残基位置ごとにスコア(位置依存スコア)

　プロファイルによるアライメント 動的計画法(DP)により最適解が計算可能 スコア行列のかわりにプロファイルを使う

ポテンシャル型スコア関数を用いたスレッディング 残基ペア間のエネルギー（スコア） 　　の和（Σfd(X,Y)）を最小化

最適スレッディング計算問題のＮＰ困難性 MAX CUT MAX CUT ⇒ スレッディング 入力： 無向グラフ G(V,E) 出力： U と V-U 間の辺数が最大となる U MAX CUT ⇒　スレッディング 配列： ALAL…AL スコア関数：

コア領域（α、β）にはギャップ無しと仮定 RAPTOR (1) Ming Li らが開発 (Xu et al., 2003) CASP5, CASP6 でも好成績 概要 スレッディング問題を整数計画問題として定式化 整数計画問題を線形計画問題に緩和 整数解が得られれば解を出力して終了 整数解が得られなければ、実数解をもとに分枝限定法を適用して整数解を計算 ほとんどの場合に最後のステップは不要 コア領域（α、β）にはギャップ無しと仮定

RAPTOR (2) g(i,j,l,k) i 番目のコアが l 残基目に、j 番目のコアが k 残基目にアラインされた際のコア i とコア j の間の擬似エネルギー あらかじめ全てのコアと位置の組み合わせについて計算

RAPTOR (3) 定式化：整数計画問題 y(i,l)(j,k): コア i が位置 l に、コア j が位置 k にアラインされた時に１、それ以外は０ xi,l: コア i が位置 l にアラインされた時に１、それ以外は０ D[i]: コア i をアライン可能な位置の集合 R[i,j,l]: コア i を位置 l にアラインした際に、コア j をアライン可能な位置の集合

　立体構造予測コンテスト：CASP CASP (Critical Assessment of Techniques for Protein Structure Prediction) ブラインドテストにより予測法を評価 半年以内に立体構造が実験により決定する見込みの配列（数十種類）をインターネット上で公開 参加者は予測結果を送付 構造決定後、正解とのずれなどを評価、順位づけ

　CASPの経過と結果の公表 CASP1 (1994), CASP2(1996), CASP3(1998), CASP4(2000), CASP5(2002), CASP6(2004) CAFASP(1998,2000,2002,2004) 完全自動予測法の評価 結果の公表 会議 ホームページ http://prediction center.llnl.gov/ 学術専門誌(Proteins)　(E.E. Lattman et al. 2003)

　参考文献 T. Akutsu, IEICE Trans. Information and Systems, E79-D, 1629-1636, 1996. T. Akutsu & S. Miyano, Theoretical Computer Science, 210, 261-275, 1999. T. Akutsu & M. M. Halldorson, Theoretical Computer Science, 233, 33-55, 2000. B. Berger, F.T. Leighton, J. Comp. Biol., 5, 27-40, 1998. J.U. Bowie et al., Science, 253, 164-179, 1991. A. Caprara et al., J. Comp. Biol., 11, 27-52, 2004. P. Crescenzi et al., J. Comp. Biol., 5, 423-466, 1998. H. Daiyasu & H. Toh, J. Mol. Evol., 5, 433-445, 2000. M. Gernstein & M. Levitt, Protein Sci., 7, 445-456, 1998. J-F. Gibrat et al., Curr. Opin. Struct. Biol., 6, 377-385, 1996. D. Goldman et al., Proc. IEEE Symp. Found. Comp. Sci. (FOCS), 512-522, 1999. W.E. Hart & S. Istrail, Proc. 27th ACM Symp. Theory of Computing, 157-168, 1995. L. Holm & C. Sander, J. Mol. Biol., 233, 123-138, 1993. R.H. Lathrop & T.F. Smith, J. Mol. Biol., 255, 641-665, 1996. E.E. Lattman et al., Proteins: Structure, Function, and Genetics, 53(S6), 2003. G-H. Lin et al., J. Comput. Syst. Sci., 65, 465-480, 2002. A. Newman, Proc. 13th ACM-SIAM Symp. Disc. Alg., 876-884, 2002. I.N. Shindyalov & P.E. Bourne, Protein Engineering, 11, 739-747, 1998. W.R. Taylor & C.A.Orengo, J. Mol. Biol., 208, 1-22, 1989. J. Xu et al., J. Bioinform Comput Biol., 1, 95-117, 2003.   Y. Xu et al., J. Comp. Biol., 5, 597-614 ,1998.

レポート課題 以下の中からいずれか１題を選択し、２ページ以上のレポートにまとめよ（提出期限８月１日）。 　レポート課題 以下の中からいずれか１題を選択し、２ページ以上のレポートにまとめよ（提出期限８月１日）。 公開されているネットワークデータを用いて次数分布を調べ、結果について考察せよ。 講義で説明した以外の関数でカーネルの条件を満たし、バイオインフォマティクスにも応用できると思われるものを一つあげ、説明せよ。 バイオインフォマティクスに関する予測を行う公開サーバーを利用して、その結果について考察せよ。ただし、サーバーに負担をかけ過ぎないように気をつけること。 講義で話したいずれかの問題と（自分の専門とする）数理科学のトピックとの関連について議論せよ。