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

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

立体構造アラインメント

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

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

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

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

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

基本アルゴリズムの性能解析(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」 を数回繰り返す 多くの場合、数秒程度でアライメント可能

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

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

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

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

構造のマルチプルアライメントの困難性 いくつかのアルゴリズム( 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困難 親水性アミノ酸 疎水性アミノ酸 スコア ＝－９ ＝－５ 配列

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

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

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

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

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

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

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

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