Aritalab:Lecture/Bioinformatics/Homology - Revision history

Adm: /* 漸化式 */

2012-07-24T00:49:49Z

‎漸化式

2012-07-24T00:49:05Z

‎漸化式

2011-12-18T12:18:57Z

‎最長共通部分列

2011-12-15T05:02:41Z

‎アライメントスコア

2011-12-15T05:01:50Z

‎スコア行列とアルゴリズム

2011-12-15T02:12:06Z

‎アライメントスコア

2011-12-14T21:37:37Z

‎大域・局所アライメント

2011-12-14T20:08:32Z

‎アルゴリズム

2011-12-14T07:49:42Z

‎大域・局所アライメント

2011-12-14T07:49:23Z

‎アライメントスコア

@@ Line 72: / Line 72: @@
 </center>
-当たり前ですが s, t が長さ 0 の場合、LCS(x,y) = if (x = y) then x else 0 となっています。最後の if then だけでなく、LCS(sx, t) などが必要な理由は、新しく付け加えた文字 x, y のどちらか片方だけを LCS として使うことを許すためです。
+当たり前ですが s, t が長さ 0 の場合、LCS(x,y) = if (x = y) then x else "" となっています。最後の if then だけでなく、LCS(sx, t) などが必要な理由は、新しく付け加えた文字 x, y のどちらか片方だけを LCS として使うことを許すためです。
 ===スコア行列とアルゴリズム===

@@ Line 67: / Line 67: @@
 <center>
 <math>
-\mbox{LCS} (sx, ty) = max \begin{cases} \mbox{LCS}(sx, t) \\ \mbox{LCS}(s, ty) \\
+| \mbox{LCS} (sx, ty) | = max \begin{cases} | \mbox{LCS}(sx, t) | \\ | \mbox{LCS}(s, ty) | \\
-\mbox{if} \ (x = y) \ \mbox{then} \ \mbox{LCS}(s,t)+x  \ \mbox{else} \ \mbox{LCS}(s,t) \end{cases}
+\mbox{if} \ (x = y) \ \mbox{then} \ | \mbox{LCS}(s,t)+x | \ \mbox{else} \ | \mbox{LCS}(s,t) | \end{cases}
 </math>
 </center>

@@ Line 59: / Line 59: @@
 ==最長共通部分列==
-配列が与えられた時、共通して現れる部分文字列（連続する必要はない）のうち、最長のものを求めるアルゴリズムを考えてみましょう。これを最長共通部分列 (LCS: longest common subsequence) と呼びます。
+配列が与えられた時、共通して現れる部分文字列（連続する必要はない）のうち、最長のものを求めるアルゴリズムを考えてみましょう。これを最長共通部分列 (LCS: longest common subsequence) と呼び、文字列 s と t を与えられたとき、それらの LCS を LCS(s, t) と書きます。
-ある文字列 s と t を与えられたとき、それらの LCS を LCS(s, t) と書きましょう。 s と t が 1 文字ずつ長くなって、それぞれ sx, ty になったとしましょう（x, y はアルファベット 1 文字）。このとき、以下の等式が成り立ちます。（ちょっとわかりにくいですが、LCS(s,t)+x とは s と t の最長共通部分列に x を付加したものを意味しています。）
+===漸化式===
 <center>

@@ Line 288: / Line 288: @@
 を考えます。ここで &mu;, &sigma; は 1 塩基あたりのペナルティスコアで、マッチのスコアを 1 とした相対値で表します。LCSアルゴリズムにおける動的計画法のスコア s は以下のように記せます。
-<math> s_{i,j} = max \begin{cases} s_{i-1,j} - \sigma \\ s_{i,j-1} - \sigma \\ s_{i-1,j-1} - \mu & \mbox{if } x \ne y \\ s_{i-1,j-1} +1 & \mbox{if } x = y
+<math> D_{i,j} = max \begin{cases} D_{i-1,j} - \sigma \\ D_{i,j-1} - \sigma \\ D_{i-1,j-1} - \mu & \mbox{if } s_i \ne t_j \\ D_{i-1,j-1} +1 & \mbox{if } s_i = t_j
 \end{cases}</math>

@@ Line 136: / Line 136: @@
 各セルの値を埋めるときは、左隣、真上、左上の 3 箇所のセルの値だけをみれば良いことに気づきます。左隣の値、真上の値、それからセルに対応する文字が一致している場合は左上のセルの値 + 1 、そうでない場合は左上のセルの値のうち、最大値をとって埋めていけばよいのです。これを数式で表すと以下のようになります。
-<math>s_{i,j} = max \begin{cases} s_{i-1,j} \\ s_{i,j-1} \\ s_{i-1,j-1} + 1 & \mbox{if } x = y\end{cases} </math>
+<math>D_{i,j} = max \begin{cases} D_{i-1,j} \\ D_{i,j-1} \\ D_{i-1,j-1} + 1 & \mbox{if } s_i = t_j \end{cases} </math>
 |width="30%"|

@@ Line 283: / Line 283: @@
 <center>
-(マッチ数) &minus; &mu;(ミスマッチ数) &minus; &sigma;(ギャップ数)
+(マッチ数) &minus; &mu;(ミスマッチ数) &minus; &sigma;(ギャップスペース数)
 </center>

@@ Line 296: / Line 296: @@
 <center>
-局所アライメント = 与えられた配列の全ての部分配列のペア中で、その大域アライメントのスコアを最大にするもの
+局所アライメント = 与えられた２つの配列それぞれの全ての部分配列のペア中で、大域アライメントのスコアを最大にするもの
 </center>
-すべての部分配列のペアを考える部分が面倒に思えますが、実際は動的計画法において初期設定を変更するだけで大域アライメントと同様に計算できます。具体的なアルゴリズムを別ページでみていきましょう。
+すべての部分配列のペアを考える部分が面倒に思えますが、実際は動的計画法において初期設定を変更するだけで大域アライメントと同様に計算できます。
 ;参考
 <references/>

← Older revision		Revision as of 07:49, 14 December 2011
Line 300:		Line 300:

	すべての部分配列のペアを考える部分が面倒に思えますが、実際は動的計画法において初期設定を変更するだけで大域アライメントと同様に計算できます。具体的なアルゴリズムを別ページでみていきましょう。		すべての部分配列のペアを考える部分が面倒に思えますが、実際は動的計画法において初期設定を変更するだけで大域アライメントと同様に計算できます。具体的なアルゴリズムを別ページでみていきましょう。
		+
		+
		+	;参考
		+	<references/>