集中講義（九州大学数理学研究院）バイオインフォマティクスにおけるカーネル法およびグラフ理論 (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) 時間で計算可能 d rms ( P, Q)  n 1 2 min | T ( p )  q |  i i T n i 1 p2 p1 q1 p3 p4 T q2 q3 q4 構造アライメントプログラム:    stralign 広くは利用されていないが、理論（計算幾何学）的考察に基づいてアルゴリズムが設計されている東大HGCよりダウンロード可能 [Akutsu 1996] 問題の定義  入力：３次元点列: P=( p1,…, pm ), Q=(q1,…, qn), および、実数δ （m ≦ n とする）  出力：以下を満たし、かつ、長さ（アラインされる点のペアの個数）が最大となる P,Q 間のアライメント M （および、付随する平行・回転移動 T ） max | T ( pi )  q j |   ( pi ,q j )M 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 の計算法  PP=(p1,p2,p3)、 QQ=(q1,q2,q3) に対するTPP,QQ の計算法    p1 が q1 に重なるように PP を並行移動 p1p2 と q1q2 が同一直線上にあるように、 PP を回転移動 PP と QQ が同一平面上にあるように、PP を p1p2 を軸として回転移動 q3 p1 q1 q2 p3 p2 TPP,QQ T(P) と Q に対するアライメント M の計算 q1 p1 q2 p2 q3 p3 cδ q4  S[i  1, j ]  S[i, j ]  max S[i, j  1] S[i  1, j  1]  w ij  1 if | T ( pi )  q j |  c wij   0 otherwise p1 q1 p2 q2 p3 q3 q4 基本アルゴリズムの性能解析(1)  補題： 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δ T p3 p1 p2 p T(p) ≦δ q ≦8δ TPP,QQ TPP,QQ(p) reg( p1, p2 , p3 )  { x | | x  p1 |  | p2  p1 |, dist( x, p1 p2 )  dist( p3 , p1 p2 ) } 基本アルゴリズムの性能解析(2)  定理： δに対する最適アライメントを MOPT とすると、基本アルゴリズムは O(n8) 時間で、以下を満たすアライメント M （と変換 T）を出力する。 max | T ( pi )  q j |  8 and | M |  | M OPT | ( pi ,q j )M  証明概略   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を二重に用いる  High level DP    [Taylor & Orengo 1989] 通常の配列アライメントと同様残基間のスコア 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  D[i  1, j ]  g  D[i, j ]   D[i, j  1]  g  D[i  1, j  1]  S [i  I , j  J ] ij  注：I,J は適当な定数  Sij [k  1, l ]  g  Sij [k , l ]   Sij [k , l  1]  g S [k  1, l  1]  s kl  ij 注：詳細は異なる DALI (Alignment of Distance Matrices)  Distance Matrix のアライメント  Distance Matrix   [Holm & Sander 1993] （同一タンパク P 内の）残基間の距離を行列形式で表現したもの P と Q の distance matrix （ただし、アライメントされる残基のみから構成される行列）ができるだけ類似するようなアライメントを計算 Simulated Annealing に類似した方法を用いて、アライメントを計算  G L A D V 0 3 5 8 6 3 0 1 5 4 5 1 0 2 7 8 5 2 0 3 6 4 7 3 0 G A E R V 0 5 8 1 6 5 0 2 5 7 8 2 0 2 2 1 5 2 0 3 6 7 2 3 0 アライメント G L A D - V G - A E R V G A D V G 0 5 8 6 A 5 0 2 7 D 8 2 0 3 V 6 7 3 0 G A E V G 0 5 8 6 A 5 0 2 7 E 8 2 0 2 V 6 7 2 0 他の構造アライメントアルゴリズム   数多くの構造アライメント手法が提案例   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’ V K U A L V V A L A C L P I K G H G Contact Map Overlap (CMO) 問題 (2)  CMO問題に関する結果   NP困難 [Goldman et al. 1999] しかし、実際多くのタンパク質立体構造について最適解が計算可能 [Caprara et al. 2004]     整数計画法の利用分枝限定法の利用グラフの最大クリーク問題に還元可能（下図参照）深く関連する問題   RNA二次構造比較 [G-H. Lin et al. 2002] ペアエネルギー関数のもとでのスレッディング [Akutsu & Miyano 1999] vi vj vi uk vi vj vi uk uk ul vj ul uk ul vj 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 タンパク質立体構造予測    アミノ酸配列から、タンパク質の立体構造（３次元構造）をコンピュータにより推定実験よりは、はるかに精度が悪いだいたいの形がわかれば良いのであれば、４～５割近くの予測率アミノ酸配列 T C A V F G L G G V R L S D V コンピュータタンパク質立体構造立体構造予測法の分類  物理的原理に基づく方法 (ab initio法)    ホモロジーモデリング     配列アライメントにより主鎖のだいたいの配置を決定した後、主鎖や側鎖の配置の最適化を分子動力学法などで実行２次構造予測   エネルギー最小化分子動力学法各アミノ酸がα、β、それ以外のいずれかにあるかを予測ランダムに予測すれば33.3…%の予測率であるが、高性能の手法を用いれば80%近い予測率格子モデルスレッディング格子モデルに関する研究   折れ畳み経路のシミュレーションによる定性的理解 →フォールディングファンネルエネルギー最小の構造の計算法 →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)   精密な３次元構造ではなく、だいたいの形（fold)を予測立体構造は1000 種類程度の形に分類される、との予測(Chotia, 1992) に基づくアミノ酸配列 T C A V F G L G G V R L S D V 1000個のテンプレート構造タンパク質スレッディング立体構造スレッディング：立体構造（テンプレート）とアミノ酸配列の間のアライメント T C A V F G L G K V R L S D V アミノ酸配列スレッディングとアライメントスレッディング立体構造アライメント A L G F G S L Y G A L G G V S L G A L G F G A L G T C A V F G L G K V R L S D V 入力アミノ酸配列 S L Y G G V S L G スレディング法の分類  プロファイルを用いたスレッディング     ３Ｄ-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) プロファイル残基４   アライメントにおけるスコア行列と類似スレッディングの場合、残基位置ごとにスコア(位置依存スコア) 残基３立体構造残基２残基1 残基1 残基2 残基3 残基4 A 3.8 -3.5 1.2 2.3 C 1.5 1.3 -0.3 -4.6 D -1.5 -2.9 4.2 3.1 E 0.2 2.1 3.7 -1.3 プロファイルによるアライメント   動的計画法 (DP)により最適解が計算可能スコア行列のかわりにプロファイルを使うアミノ酸配列： AED ...... プロファイル：残基1 残基2 残基3 残基4 A 3.8 -3.5 1.2 2.3 C D 1.5 1.3 -0.3 -4.6 -1.5 -2.9 4.2 3.1 E 0.2 -4.1 3.7 -1.3 アライメント 123 ..... AED ..... 1234 ..... A-ED ..... 1- 23 ..... AEDC ... スコア 3.8-4.1+4.2 =3.9 3.8-2.0+3.7+ 3.1=8.7 3.8-2.0-2.9+ -0.3=-1.4 ポテンシャル型スコア関数を用いたスレッディング  残基ペア間のエネルギー（スコア）の和（Σfd(X,Y)）を最小化 f d (T, G) d f d (T, G) エネルギー関数 T T L A V G H f (T ,L)  f (T ,V)  f (T ,G)  f (L, V)  f (L, G)  f (V, G)  2  gap_penalty d G d 最適スレッディング計算問題のＮＰ困難性  MAX CUT    入力：無向グラフ G(V,E) 出力： U と V-U 間の辺数が最大となる U MAX CUT ⇒ スレッディング   配列： ALAL…AL スコア関数： g ( x, y , t i , t j )   1, if {vi , v j }  E and   x y 0, otherwise  (U V ) RAPTOR (1)    Ming Li らが開発 (Xu et al., 2003) CASP5, CASP6 でも好成績概要       スレッディング問題を整数計画問題として定式化整数計画問題を線形計画問題に緩和整数解が得られれば解を出力して終了整数解が得られなければ、実数解をもとに分枝限定法を適用して整数解を計算ほとんどの場合に最後のステップは不要コア領域（α、β）にはギャップ無しと仮定 RAPTOR (2)  g(i,j,l,k)   i 番目のコアが l 残基目に、j 番目のコアが k 残基目にアラインされた際のコア i とコア j の間の擬似エネルギーあらかじめ全てのコアと位置の組み合わせについて計算コア立体構造コア l j i k アミノ酸配列 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 をアライン可能な位置の集合 min    y( i ,l )( j ,k ) g (i, j , l , k ) ( Ci ,C j )E lD[ i ] kR[ i , j ,l ] s.t. x lD[ i ] i ,l  1, i  1,2,  , M , xi ,l  0, l  D[i ], i  1,2,  , M , y(i ,l )( j ,k )  0, l  D[i ], k  D[ j ], i, j  1,2,  , M , y  xi ,l , (Ci , C j )  E , y  x j ,k , (Ci , C j )  E. ( i ,l )( j , k ) kR[ i , j ,l ] ( i ,l )( j , k ) kR[ j ,i , k ] 立体構造予測コンテスト：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. レポート課題  以下の中からいずれか１題を選択し、２ページ以上のレポートにまとめよ（提出期限８月１日）。     公開されているネットワークデータを用いて次数分布を調べ、結果について考察せよ。講義で説明した以外の関数でカーネルの条件を満たし、バイオインフォマティクスにも応用できると思われるものを一つあげ、説明せよ。バイオインフォマティクスに関する予測を行う公開サーバーを利用して、その結果について考察せよ。ただし、サーバーに負担をかけ過ぎないように気をつけること。講義で話したいずれかの問題と（自分の専門とする）数理科学のトピックとの関連について議論せよ。