プロバライン

Probalignは、分配関数事後確率を用いて最大期待精度のアライメントを計算する配列アライメントツールです。 [ 1 ]塩基対確率は、 ボルツマン分布に類似した推定値を用いて推定されます。分配関数は動的計画法を用いて計算されます。

アルゴリズム

以下はprobalignが塩基対確率を決定するために使用するアルゴリズムについて説明しています。[ 2 ]

アライメントスコア

2 つの配列のアライメントをスコアリングするには、次の 2 つが必要です。

  • 類似度関数（例：PAM、BLOSUM、...）σ（×、y）{\displaystyle \sigma (x,y)}
  • アフィンギャップペナルティ:グラム（け）＝α+βけ{\displaystyle g(k)=\alpha +\beta k}

アライメント a の スコアは次のように定義されます。S（1つの）{\displaystyle S(a)}

S（1つの）＝∑×私−yj∈1つのσ（×私、yj）+ギャップコスト{\displaystyle S(a)=\sum _{x_{i}-y_{j}\in a}\sigma (x_{i},y_{j})+{\text{ギャップコスト}}}

アライメント a のボルツマン重み付けスコアは次のようになります。

eS（1つの）T＝e∑×私−yj∈1つのσ（×私、yj）+ギャップコストT＝（∏×私−y私∈1つのeσ（×私、yj）T）⋅eグラム1つのpcostT{\displaystyle e^{\frac {S(a)}{T}}=e^{\frac {\sum _{x_{i}-y_{j}\in a}\sigma (x_{i},y_{j})+{\text{ギャップコスト}}}{T}}=\left(\prod _{x_{i}-y_{i}\in a}e^{\frac {\sigma (x_{i},y_{j})}{T}}\right)\cdot e^{\frac {ギャップコスト}{T}}}

はスケーリング係数です 。T{\displaystyle T}

ボルツマン分布を仮定した整列の確率は次のように与えられる。

Pr[1つの|×、y]＝eS（1つの）TZ{\displaystyle Pr[a|x,y]={\frac {e^{\frac {S(a)}{T}}}{Z}}}

ここで、パーティション関数、つまりすべてのアライメントのボルツマン重みの合計です。 Z{\displaystyle Z}

動的計画法

接頭辞との分割関数をとします。3つの異なるケースが考えられます。 Z私、j{\displaystyle Z_{i,j}}×0、×1、。。。、×私{\displaystyle x_{0},x_{1},...,x_{i}}y0、y1、。。。、yj{\displaystyle y_{0},y_{1},...,y_{j}}

  1. Z私、jM:{\displaystyle Z_{i,j}^{M}:}一致して終わる 2 つのプレフィックスのすべてのアライメントのパーティション関数。
  2. Z私、j私:{\displaystyle Z_{i,j}^{I}:}挿入で終わる 2 つのプレフィックスのすべてのアライメントのパーティション関数。（−、yj）{\displaystyle (-,y_{j})}
  3. Z私、jD:{\displaystyle Z_{i,j}^{D}:}削除で終わる 2 つのプレフィックスのすべてのアラインメントのパーティション関数。（×私、−）{\displaystyle (x_{i},-)}

次に次のようになります。Z私、j＝Z私、jM+Z私、jD+Z私、j私{\displaystyle Z_{i,j}=Z_{i,j}^{M}+Z_{i,j}^{D}+Z_{i,j}^{I}}

初期化

行列は次のように初期化されます。

  • Z0、jM＝Z私、0M＝0{\displaystyle Z_{0,j}^{M}=Z_{i,0}^{M}=0}
  • Z0、0M＝1{\displaystyle Z_{0,0}^{M}=1}
  • Z0、jD＝0{\displaystyle Z_{0,j}^{D}=0}
  • Z私、0私＝0{\displaystyle Z_{i,0}^{I}=0}

再帰

2つの配列とをアラインメントする分割関数は で与えられ、これは再帰的に計算できます。 ×{\displaystyle x}y{\displaystyle y}Z|×|、|y|{\displaystyle Z_{|x|,|y|}}

  • Z私、jM＝Z私−1、j−1⋅eσ（×私、yj）T{\displaystyle Z_{i,j}^{M}=Z_{i-1,j-1}\cdot e^{\frac {\sigma (x_{i},y_{j})}{T}}}
  • Z私、jD＝Z私−1、jD⋅eβT+Z私−1、jM⋅eグラム（1）T+Z私−1、j私⋅eグラム（1）T{\displaystyle Z_{i,j}^{D}=Z_{i-1,j}^{D}\cdot e^{\frac {\beta}{T}}+Z_{i-1,j}^{M}\cdot e^{\frac {g(1)}{T}}+Z_{i-1,j}^{I}\cdot e^{\frac {g(1)}{T}}}
  • Z私、j私{\displaystyle Z_{i,j}^{I}}同様に

塩基対確率

最後に、位置とが塩基対を形成する 確率は次のように与えられます。×私{\displaystyle x_{i}}yj{\displaystyle y_{j}}

P（×私−yj|×、y）＝Z私−1、j−1⋅eσ（×私、yj）T⋅Z私′、j′′Z|×|、|y|{\displaystyle P(x_{i}-y_{j}|x,y)={\frac {Z_{i-1,j-1}\cdot e^{\frac {\sigma (x_{i},y_{j})}{T}}\cdot Z'_{i',j'}}{Z_{|x|,|y|}}}}

Z′、私′、j′{\displaystyle Z',i',j'}逆塩基対文字列で 再計算されたそれぞれの値です。Z{\displaystyle Z}

参照

参考文献

  1. ^ U. RoshanとDR Livesay、「Probalign：パーティション関数事後確率を用いた多重配列アライメント」、バイオインフォマティクス、22(22):2715-21、2006年（ PDF）
  2. ^フライブルク大学での講義「バイオインフォマティクス II」
「 https://en.wikipedia.org/w/index.php?title=Probalign&oldid=1285162101」より取得