第3回 2019/4/22
- 講師：浅井 潔
前回の復習
割愛
The scoring model for biological sequences
- メモリ： \(O(L^2)\)
- 計算時間： \(O(L^2)\)
| 大域アラインメント | 局所アラインメント |
|---|---|
| Needleman-Wuncsh, 1970 | Smith-Waterman, 1981 |
|
$$F_{i,j} = \max\begin{cases}F_{i-1, j-1}+s\left(x_{i}, y_{j}\right), \\F_{i-1, j}-d, \\F_{i, j-1}-d\end{cases}\\$$
|
$$F_{i,j} = \min\begin{cases}0,\\F_{i-1, j-1}+s\left(x_{i}, y_{j}\right), \\F_{i-1, j}-d, \\F_{i, j-1}-d\end{cases}\\$$
|
| \(F(i,j)\): \(x_1,\ldots,x_i\) と \(y_1,\ldots,y_j\) の最適アラインメントのスコア | \(x_i\) と \(y_i\) で終わる最適局所アラインメントのスコア |
| \(s(x_i,y_j)\): スコア行列(置換行列) | \(s(x_i,y_j)\): スコア行列(置換行列) |
| \(d\): ギャップペナルティ(線形) | \(d\): ギャップペナルティ(線形) |
| 初期条件 $$\begin{aligned}&F(0,0) = 0\\&F(i,0) = -id\\&F(o,j) = -jd\end{aligned}$$
|
初期条件 $$F(i,0)=F(0,j)=0$$
|
アラインメントのスコア
ギャップなしアラインメント
- ２本の配列が進化的に関係があるモデル \(M_C\) (Correlated)
同じ文字が \(a\) と \(b\) に変異する確率（\(a\) と \(b\) が整列する確率）が \(p_{ab} = p_{ba}\)
$$P(x,y|M_c) = \prod_ip_{x_iy_i}$$
- ２本の配列に関係がないモデル \(M_R\) (Random)
文字 \(a\) が現れる確率が \(q_a\)
$$P(x,y|M_R) = \prod_iq_{x_i}\prod_iq_{y_i}$$
置換行列(Substitution Matrix)は通常、進化的に共通祖先を持つモデル \(M_C\) と、無関係なモデル \(M_R\) の対数尤度比（以下）で定義される。
$$s(a,b) = T\log\frac{p_{ab}}{q_aq_b}$$
したがって、これを用いるとアラインメントのスコアは以下で表される。
$$
\begin{aligned}
S
&=T \log \frac{P\left(x, y | M_{c}\right)}{P\left(x, y | M_{R}\right)}\\
&=T \log \frac{\prod_i p_{x_i y_i}}{\prod_i q_{x_i} \prod_i q_{y_i}}\\
&=T \sum_i \log \frac{p_{x_i y_i}}{q_{x_i} q_{y_i}}\\
&=\sum_{i} s\left(x_{i}, y_{i}\right)
\end{aligned}$$
ギャップありアラインメント
アラインメント \(A\) で \(x_i\) と \(y_j\) が整列することを \((i,j)\in A\) と表すことで、アラインメントのスコアは以下で表される。
$$\begin{aligned}
S(A)
&=T \log \frac{P\left(x, y, A | M_{C}\right)}{P\left(x, y | M_{R}\right)}\\
&=\sum_{(i, j) \in A} s\left(x_{i}, y_{j}\right)+\text {GapPenalty}
\end{aligned}$$
The Bayesian approach: model comparison
確率の基本定理
確率の基本定理
$$\begin{aligned}\text{加法定理: } &p(X) = \sum_Yp(X,Y)\\\text{乗法定理: } &p(X,Y) = p(Y|X)p(X)\end{aligned}$$
ベイズの定理
ベイズの定理
$$P(A | B)=\frac{P(B | A) P(A)}{P(B)}$$
ベイズモデル比較
モデルの事後分布 \(p\left(\mathcal{M}_{i} | \mathcal{D}\right)\) は、
- \(p(\mathcal{M}_{i})\): モデルの事前分布（どのモデルが良いかの好み）
- \(p\left(\mathcal{D} | \mathcal{M}_{i}\right)\): 周辺尤度（モデル \(\mathcal{M}_{i}\) の下でのデータ \(\mathcal{D}\) の出やすさ）
の積に比例する。（モデルの事前分布はわからないことが多い）
ここで、モデル \(M,R\) を比較する場合、\(p(M|x,y)\) と \(p(R|x,y)\) を比較することになるので、
$$\begin{aligned} P(M | x, y) &=\frac{P(x, y | M) P(M)}{P(x, y)} \\ P(R | x, y) &=\frac{P(x, y | R) P(R)}{P(x, y)} \end{aligned}$$
より、
$$\log \frac{P(M | x, y)}{P(R | x, y)}=\log \frac{P(x, y | M)}{P(x, y | R)}+\log \frac{P(M)}{P(R)}$$
となる。この時右辺の第１項は対数オッズ比（モデル \(R\) に対するモデル \(M\) のエビデンス比）と言い、ベイズ因子とも呼ばれる。なお、第２項は「モデル選択の事前分布」である。
アミノ酸間の類似度マトリックス
プリン塩基間、ピリミジン塩基間の方が変異が起こりやすいのと同じように、アミノ酸間にも「電気的な性質」「水に対する溶解性」「体積」などの理由から変異の起こりやすさが異なる。したがって、それらを考慮した類似度マトリックスが考察されている。
区分的線形ギャップコスト(Piecewise Linear Gap)
ギャップの長さによってギャップの伸長ペナルティが変化していく（大抵は傾きが緩くなっていく、ペナルティが小さくなる）場合を考える。
General Gap Cost
一般的な（ギャップが連続していようがいまいが関係ない）場合を考える。
$$
\begin{aligned}
D(i, j)
&=\min \left[
\begin{array}{l}
{D(i-1, j-1)+\delta\left(a_{i}, b_{j}\right)} \\
{F(i, j)} \\
{G(i, j)}
\end{array}
\right.
& (1)\\
F(i, j)
&=\min _{1 \leq k \leq i}\{D(i-k, j)+g(k)\}
& (2)\\
G(i, j)
&=\min _{1 \leq k \leq j}\{D(i, j-k)+g(k)\}
&(3)
\end{aligned}
$$
Affine Gap
区間線形ギャップの前に、その特殊な場合（一段階だけ）であるアフィンギャップ
$$g(k) = uk + v\qquad (4)$$
の場合の漸化式を一つ上の漸化式から導く。
式(4)の \(g(k)\) を式(2),(3)に代入すると、
$$
\begin{aligned}
F(i, j)
&=\min _{1 \leq k \leq i}\{D(i-k, j)+u k+v\} \\
&=\min \left[D(i-1, j)+u+v, \min _{2 \leq k \leq i}\{D(i-k, j)+u k+v\}\right] \\
&=\min \left[D(i-1, j)+u+v, \min _{1 \leq k \leq i-1}\{D((i-1)-k, j)+u k+v+u\}\right]
& (5)\\
&=\min [D(i-1, j)+u+v, F(i-1, j)+u\} ] \\
G(i, j)
&=\min [D(i, j-1)+u+v, G(i, j-1)+u\} ]
& (6)
\end{aligned}
$$
ここで、式(1)と合わせて考えて、
$$
D(i, j)=\min \left[ \begin{array}{c}{D(i-1, j-1)+\delta\left(a_{i}, b_{j}\right)} \\ {D(i-1, j)+u+v} \\ {D(i, j-1)+u+v}\end{array}\right.\\
F(i, j)=\min \left[ \begin{array}{c}{D(i-1, j)+u+v} \\ {F(i-1, j)+u}\end{array}\right.
G(i, j)=\min \left[ \begin{array}{c}{D(i, j-1)+u+v} \\ {G(i, j-1)+u}\end{array}\right.
$$
Piecewise Linear Gap
式(2)における \(g(k)\) を、\(L\) 個の区間
$$\left(K_{0}=0, K_{1}\right], \ldots,\left(K_{\alpha-1}, K_{\alpha}\right], \ldots,\left(K_{L-1}, K_{L}=\infty\right]$$
ごとに以下の線形関数をとる区間線形関数とする。
$$
\begin{aligned}
g(k)=g_{\alpha}(k) \equiv u_{\alpha} k+v_{\alpha}, \text { for } k \in\left(K_{\alpha-1}, K_{\alpha}\right](1 \leq i \leq L) \\ \text { where } u_{\alpha}>u_{\alpha+1} \geq 0, \quad g_{\alpha}\left(K_{\alpha}\right)=g_{\alpha+1}\left(K_{\alpha}\right), \quad \text { for } \quad 1 \leq \alpha \leq L-1 \end{aligned}\qquad (7)
$$
ここで、\(g_{\alpha}(k)\) は、\(g(k) = g_{\alpha}(k)\) となる区間では \(L\) 個の線形関数の中で最小となる（グラフをイメージすればわかる）から、以下が成り立つ。
$$g_{\alpha}(k)=\min _{\beta} g_{\beta}(k) \quad \text { if } \alpha \in\left(K_{\alpha-1}, K_{\alpha}\right]\qquad (8)$$
式(7)の \(g(k)\) を式(2)に代入すると、（\(i>K_{L-1}\) と仮定）
$$
\begin{aligned}
F(i,j)
&= \underset{1\leq k\leq i}{\min}\left\{D(i-k,j) + g(k)\right\}\\
&=\min \left[
\begin{array}{c}
{\min _{1 \leq k \leq K_{1}}\left\{D(i-k, j)+g_{1}(k)\right\}} \\
{\cdots} \\
{\min _{K_{\alpha-1} \leq k \leq K_{\alpha}}\left\{D(i-k, j)+g_{\alpha}(k)\right\}} \\
{\cdots} \\
{\min _{K_{L-1} \leq k \leq i}\left\{D(i-k, j)+g_{L}(k)\right\}}
\end{array}
\right.
\end{aligned}
$$
ここで、式(8)から、各区間 \(K_{\alpha-1} \leq k \leq K_{\alpha}\) 内では、その区間で最小となる線形ギャップ関数 \(g_{\alpha}(k)\) を用いたものが最小となるので、以下のように内側の \(\min\) の範囲を \([1,i]\) にして良い。
$$F(i, j)=\min _{\alpha}\left[\min _{1 \leq k \leq i}\left\{D(i-k, j)+g_{\alpha}(k)\right\}\right]$$
同様に、
$$G(i, j)=\min _{\alpha}\left[\min _{1 \leq k \leq i}\left\{D(i, j-k)+g_{\alpha}(k)\right\}\right]$$
ここで、以下を定義する。
$$
\begin{aligned} F_{\alpha}(i, j) & \equiv \min _{1 \leq k \leq i}\left\{D(i-k, j)+g_{\alpha}(k)\right\} \\ G_{\alpha}(i, j) & \equiv \min _{1 \leq k \leq j}\left\{D(i, j-k)+g_{\alpha}(k)\right\} \end{aligned}
$$
すると、\(F_{\alpha}(i,j),G_{\alpha}(i,j)\) に関して以下の漸化式が成り立つ。
$$
\begin{aligned}
F_{\alpha}(i, j)
&=\min \left[ \begin{array}{c}{D(i-1, j)+u_{\alpha}+v_{\alpha}} \\ {F_{\alpha}(i-1, j)+u_{\alpha}}\end{array}\right.\\
G_{\alpha}(i, j)
&=\min \left[ \begin{array}{c}{D(i, j-1)+u_{\alpha}+v_{\alpha}} \\ {G_{\alpha}(i, j-1)+u_{\alpha}}\end{array}\right.
\end{aligned}
$$
これを式(1)と統合して、
$$
\begin{aligned}
F_{\alpha}(i, j)
&=\min \left[ \begin{array}{c}{D(i-1, j)+u_{\alpha}+v_{\alpha}} \\ {F_{\alpha}(i-1, j)+u_{\alpha}}\end{array}\right.\\
G_{\alpha}(i, j)
&=\min \left[ \begin{array}{c}{D(i, j-1)+u_{\alpha}+v_{\alpha}} \\ {G_{\alpha}(i, j-1)+u_{\alpha}}\end{array}\right.\\
D(i, j)
&=\min \left[ \begin{array}{c}{D(i-1, j-1)+\delta\left(a_{i}, b_{j}\right)} \\ {\min _{\alpha} F_{\alpha}(i, j)} \\ {\min _{\alpha} G_{\alpha}(i, j)}\end{array}\right.
\end{aligned}
$$
Hirschbergアルゴリズム
- 漸化式で参照する値は限られている。 直前の列だけ記憶してメモリを \(O(L)\) に抑える。
- バックトラックするのには \(O(L^2)\) のメモリ？ 部分問題に分割して再帰的アルゴリズムで克服（必ず通る場所がわかると計算量が減る性質を利用。小さなブロックに分けていく。）