第6回 2019/7/22
ペアワイズアラインメント
バイナリ変数を用いた定式化
| 問題1 |
|---|
| \(2\) 本の生物配列（DNA,RNA,protein） \(x,x'\) に対して、\(x\) と \(x'\) のペアワイズアラインメントを求める。 |
この問題を数学的に定式化する。
\(I^{(0)} = \left\{(i,k) | 1\leq i \leq |x|, 1\leq k\leq |x'|\right\}\) に対して、バイナリ変数 \(\theta_{ik}\left((i,k)\in I^{(0)}\right)\) を以下のように定義する。
このバイナリ変数用いることにより、\(x\) と \(x^{\prime}\) のアラインメントは \(\theta = \left\{\theta_{ik}\right\}_{(i,k)\in I}\in \{0,1\}^{|x|}\times\{0,1\}^{|x^{\prime}|}\) と表現可能である。
ここで、\(x\) と \(x^{\prime}\) の可能なアラインメント \(\theta\) の集合（空間）を \(\mathcal{A}(x,x^{\prime})\) と表記する。
注意！！ この条件下では、配列 \(x\) のある位置を \(x^{\prime}\) の \(2\) つの異なる位置と整列させることができてしまうので、\(\theta = \left\{\theta_{ik}\right\}_{(i,k)\in I}\in \{0,1\}^{|x|}\times\{0,1\}^{|x^{\prime}|}\) がコンシステントなアラインメントになるとは限らない。
この \(\mathcal{A}(x,x^{\prime})\) を用いることにより、配列アラインメントの問題は以下の通り記述できる。
| 問題1' |
|---|
| 2本の生物配列（DNA,RNA,protein配列）\(x,x^{\prime}\) に対して、アラインメント \(y\in\mathcal{A}(x,x^{\prime})\) を求める。 |
バイナリ空間上の点推定問題
上の問題は、下記の抽象的な問題の一例である。
| バイナリ空間上の点推定問題 |
|---|
| データセット \(D\) と予測空間 \(Y\subset\{0,1\}^n\)（予測候補集合）が与えられているとする。この時、予測空間 \(Y\) の \(1\) 点 \(y\) を予測しなさい。 |
ただし、これだけではこの定式化に意味がないので、以下の仮定をおく。
| デコーディング問題 |
|---|
| データセット \(D\) と予測空間 \(Y\subset\{0,1\}^n\)（予測候補集合）が与えられているとする。ここで、予測空間 \(Y\) 上の確率分布 \(p(y\mid D)\) が与えられているという条件下で予測空間 \(Y\) の \(1\) 点 \(y\) を予測しなさい。 |
最尤推定量
確率値が最も高くなる予測を行う場合、デコーディング問題に対してベイズ事後確率 \(p(y|D)\) を最大化する推定量（ベイズ最尤推定量）
がよく利用される。
スコア最大化やエネルギー最小化の推定方法も、ベイズ最尤推定量として解釈可能な場合が多い。
例えば、あるスコアモデル（置換行列、ギャップスコア等）が与えられた場合、スコア最大化のアラインメントを予測することは、以下の \(\mathcal{A}(x,x^{\prime})\) 上の確率分布に対する最尤推定値に等しい。
- \(S(\theta) \left(= \sum_{\theta_{ij}=1}s(x_i,x_j) - (\text{penalty for gaps})\right)\) は、与えられたスコアモデルにおけるアラインメント \(\theta\in\mathcal{A}(x,x^{\prime})\) のスコア
- \(T(>0)\) は温度パラメタ
- \(Z(T)\) は正規化定数
最尤推定量の問題
ここで「最尤推定量は良い推定量か？」ということが疑問になる。
実際、高次元離散空間上の推定問題においては、最尤推定量が優れた推定を与えないことが多い。
- 解の候補の数が膨大になる。
- 予測空間には互いに類似した解が多数含まれる。
- 最も確率が高くなる解の確率値が極めて小さくなる（\(10^{-20}\) とか）場合がある。
これらの問題を回避するために、解空間上の確率分布 \(p(y|D)\) 全体を考慮した推定量を設計する。
期待利益最大化推定量
まず、利益関数(gain function)を以下のように定義する。
この利益関数を用いることで、先ほどのデコーディング問題に対して別の推定解を与えることができる。（\(G(\theta,y)\) には別の評価指標を用いてもよい）
この \(\hat{y}^{(M E G)}\) を期待利益最大化推定量(MEG推定量)と呼ぶ。
\(G(\theta, y)=\delta(\theta, y)\) の場合にMEG推定量がベイズ最尤推定と一致することは明らか。
なお、利益関数が \(G(\theta,y)\) に利用されている場合、これを「期待精度最大化推定量」と呼ぶ。
期待制度最大化推定量は、バイオインフォマティクスの推定問題において成功を収めている。
\(\gamma\) セントロイド推定量
\(\gamma\) セントロイド推定量は、MEG推定量の一種であり、以下のように表される。
※なお、ここで \(I(\cdot)\) はindicator関数（条件が成立すれば \(1\) を、そうでない時には \(0\) をとる関数）を表す。
\(\gamma=1\) の場合は、セントロイド推定量（ハミング距離の期待値を最小化する推定量）と等価である。
解釈
\(\gamma\) 推定量の解釈を行う。まず、\(\theta,y\in Y\) に対して、以下を定義する。
なお、\(y\) が予測、\(\theta\) が正解（リファレンス）である場合、それぞれ真陽性の数、真陰性の数、偽陽性の数、偽陰性の数と等しい。
一般に、\(\mathrm{TP,TN}\) は多く、\(\mathrm{FP,FN}\) が少ない予測が優れているので、正の定数 \(\alpha_k\) に対して、以下の利益関数を導入する。
なお、この時 \(I\left(\theta_{i j}=0\right)=1-I\left(\theta_{i j}=1\right)\) であるから、上式の利益関数を用いたMEG推定量は \(\gamma=\frac{\alpha_{1}+\alpha_{4}}{\alpha_{2}+\alpha_{3}}\) の場合の \(\gamma\) セントロイド推定量と等しいことがわかる。
また、そのことから、\(\gamma\) セントロイド推定は、\(\mathrm{TP,TN.FP,FN}\) から計算される以下の評価指標に対して適した推定量であることがわかる。
\(\gamma\) セントロイド推定量の \(\gamma\) が大きいほど \(\mathrm{SEN}\) に対して有利な予測となり、小さいほど \(\mathrm{PPV}\) に有利な予測となる。
\(\gamma\) セントロイドアラインメント
以下の問題に対して \(\gamma\) セントロイド推定量（\(\gamma\) セントロイドアラインメント）を計算する。
問題
2本の生物配列（DNA,RNA,protein配列）\(x,x^{\prime}\) に対して、アラインメント \(y\in\mathcal{A}(x,x^{\prime})\) を求める。ただし、予測空間 \(Y\) 上の確率分布 \(p(y\mid D)\) は与えられているとする。
計算方法
- 前向き・後ろ向きアルゴリズムを用いて \(\{p_{ik}\}_{i,k}\left(p_{ik} = \sum_{\theta}I(\theta_{ik}=1)p(\theta|x,x^{\prime})\right)\) を計算する。
- Needleman-Wunschアルゴリズムと同タイプの以下の動的計画法によってアラインメントを計算する。
$$M_{i, k}=\max \left\{\begin{array}{l}{M_{i-1, k-1}+(\gamma+1) p_{i k}-1} \\ {M_{i-1, k}} \\ {M_{i, k-1}}\end{array}\right.$$※ここで、\(M_{i,k}\) は、\(x_1,\ldots,x_i\) と \(x^{\prime}_1,\ldots,x^{\prime}_k\) の間の最適アラインメントのスコアを保存する。
なお \(\gamma<1\) の場合の \(\gamma\) セントロイドアラインメントは以下の \(y^{\ast} = \left\{y_{ik}^{\ast}\right\}_{i,k}\) と一致するため、DPを行わずに計算が可能である。