{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 12-Solving Protein Folding Problem by HUBO Solver" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/OpenJij/OpenJijTutorial/blob/master/source/ja/012-ProteinFoldingHubo.ipynb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2012年に、Alejandroらがタンパク質折り畳み問題を量子アニーリングマシン(D-wave)を用いて解きました[1]。\n", "\n", "ここでタンパク質折り畳み問題とは、「アミノ酸配列という1次元的情報からそのタンパク質の3次元的立体構造を予測すること」を意味します。\n", "タンパク質はアミノ酸配列によって特徴付けられ、1つのアミノ酸配列に対して固有の立体構造が対応することが知られています。\n", "タンパク質はその固有の立体構造を持って初めて生体高分子としての機能を果たすため、アミノ酸配列の情報からそのタンパク質の立体構造を予測することは非常に重要な問題です。\n", "しかし、アミノ酸配列とタンパク質の立体構造との因果関係はまだよくわかっておらず、非常に難しい問題です。\n", "\n", "このチュートリアルでは、OpenJijのHUBOソルバーを用いてタンパク質折り畳み問題を解き、その結果を論文[1]と比較します。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 問題の概要とHydrophobic-Polar(HP)モデル、Miyazawa-Jernigan(MJ)モデル \n", "\n", "### 問題概要\n", "タンパク質の立体構造をラティスフォールディングモデルという単純な格子モデルとして捉え、HUBOの形式にエンコードしこれを解くことで立体構造を決定します。\n", "ラティスフォールディングモデルにはいくつか種類があり、 以下代表的な2つのモデル、HPモデルとMJモデルについて紹介します。\n", "論文[1]では、2次元上の構造問題とみなして以下で説明するMJモデルを利用しています。\n", "\n", "### HPモデル \n", "タンパク質は数十から数百程度のアミノ酸配列からなるポリペプチドが折り畳まった安定した立体構造を持ちます。\n", "その立体構造を決定するために、ポリペプチドの3次元立体構造をそのままの状態で扱うのは、計算量が膨大でスーパーコンピュータ等を利用しても難しいのが現状です。\n", "なぜなら、タンパク質分子のエネルギーを計算するには、水素結合、静電相互作用、ファンデルワールス力、疎水性相互作用等の様々な力を考慮する必要があるからです。\n", "しかし、疎水性相互作用だけを扱った極めて単純なモデルでもある程度のことが説明できます。\n", "\n", "LauとDillは疎水性相互作用のみを考慮した格子モデルであるHPモデル[2]を提案しました。\n", "このモデルは、アミノ酸を疎水性(H: hydrophobic)と親水性(P: polar)の2種類のみに分類し、タンパク質のアミノ酸配列をHとPの配列として表現します。\n", "そして、Hモノマー同士が最近接格子にきた場合、エネルギーが下がるというモデルです。\n", "\n", "参考:\n", "\n", "- https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/96792/1/KJ00004709268.pdf\n", "- http://www.iba.t.u-tokyo.ac.jp/iba/AI/HP.pdf\n", "\n", "\n", "### MJモデル\n", "HPモデルでは、アミノ酸を単純化して疎水性と親水性の2種類のみに分類しました。つまり、アミノ酸同士の相互作用の大きさの違いは考慮していません。\n", "より精度の高いモデルを構築しようとした場合、この違いを考慮することが考えられます。それがMJモデルです。\n", "\n", "MJモデルは、立体構造が既知のタンパク質を多数集め、それらの中から互いに近距離にあるアミノ酸ペアの個数を数え上げ、それらの統計的な情報をアミノ酸間の相互作用エネルギーとして表現したものです。\n", "立体構造群の中でのアミノ酸ペアの数が多ければ、そのアミノ酸ペアに働く相互作用エネルギーの絶対値は大きくなります。\n", "この相互作用エネルギーは、アミノ酸ペアを形成しやすい・しにくいという傾向を表現していると考えられます。\n", "\n", "論文[1]では参考論文[3]のTable3に報告されている値を利用しています。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 解法の概要\n", "ここでは論文[1]で扱っているモデルの構築方法について説明します。\n", "今回使用するアミノ酸配列は、Proline-Serine-Valine-Lysine-Methionine-Alanineの6アミノ酸配列(1文字のアミノ酸配列表記ではP-S-V-K-M-A)です。\n", "ここでP-S-V-K-M-Aというアミノ酸の順番は固定されていることに注意してください。\n", "2次元の格子上でこれらのアミノ酸列の折りたたみ問題を考えます。\n", "ただし、6種類とはいえアミノ酸配列を全て一度に処理するのは難しいので、すでにいくつかの折り畳まれたパターンを起点に考えてモデルを構築します。\n", "以下では簡単な例として論文[1]のscheme3について解説します。\n", "\n", "本チュートリアルでは以下の順で詳細な解法手順を説明します。\n", "\n", "1. ラティスフォールディングのビット表現方法\n", "2. コスト関数の定式化\n", "3. HUBOの直接解法\n", "4. HUBOによる直接解法と参考論文[1]の結果との比較" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1. ラティスフォールディングのビット表現方法\n", "ここでは2次元上のアミノ酸の立体構造とビット列を対応付ける方法を説明します。P-S-V-K-M-A列の構造を例に考えますが、より現実的な3次元の立体構造も同様の方針で対応付けることができます。\n", "方法は非常に簡単です。今は2次元格子を考えているためアミノ酸の折りたたみ方としては、上、下、左、右の4種類あります。これらに対して2つのビットを次のように割り当てます。\n", "$$\n", "00(下向き)、01(右向き)、10(左向き)、11(上向き)\n", "$$\n", "これにより、$2\\times 6=12$個のビット列と6個のアミノ酸列の2次元格子上の構造が1対1で対応します。\n", "例えば010101010101というビット列は左から2ビットずつ区切って読むことで、右、右、右、右、右、右という列に翻訳されます。\n", "よってP-S-V-K-M-Aという順番でアミノ酸が右向きに横一直線に並んだ構造に対応します。\n", "より複雑な例が図1に示してあります。\n", "\n", "実は、簡単な考察から最初の3ビットは010に固定できることが分かります。\n", "まず、平面の対称性からPの右側にSが折りたたまれていると仮定しても一般性を失わないことが分かります。よって最初の2ビットは01列で固定できます。\n", "さらにSの上にVが折りたたまれることと、下に折りたたまれることは、やはり平面の対称性から同じことなので、ここでは下に折りたたまれる場合のみ考えます。\n", "またVがSの左に折りたたまれてPと重なるパターンも排除します。以上の考察と仮定からVはSの右か下に折りたたまれる場合のみを考えても良いことになります。\n", "したがって3ビット目が0に決まります。よって残りの$12-3=9$ビットの配列を決定すれば良いことになります。\n", "\n", "