進捗状況の確認 1. gj も gjp も動いた 2. gj は動いた 3. gj も動かない 2

(1)

1

連立

_{1次方程式の数値解法}

•  小規模な連立1次方程式の解法

–  消去法 •  Gauss消去法 •  Gauss-Jordan法

•  （大規模な連立1次方程式の解法）

–  （反復法） •  （Jacobi法）　　講義では扱わない

(2)

進捗状況の確認

1.  gj も gjp も動いた。

2.  gj は動いた。

3.  gj も動かない。

(3)

(4)

パターン認識

•  音や画像に中に隠れた

パターンを認識する。

–  音素・音節・単語・文・・・ –  基本図形・文字・指紋・物体・人物・顔・・・

•  「パターン」は唯一のデータではなく、

似通ったデータの集まりを表している。

–  多様性 –  ノイズ

•  「等しい」から「似ている」へ

•  「～だ」から「～らしい」へ

(5)

アラインメント

•  アラインメント

２つ（複数）の文字列の比較

–  音声認識・文字認識 –  DNAやタンパクの比較

GACGGATTAG と GATCGGAATAG

GA-CGGATTAG

GATCGGAATAG

ギャップ不一致

(6)

•  ぴったり同じでなくとも、

似ているかどうかを判定。

•  スコア

一致 +2 不一致 -1 ギャップ -2 足し合わせる _{à アラインメントの類似度}

•  類似度が最大の

アラインメント（ギャップの入れ方）を求める。

アラインメント

最適化

(7)

•  スコア

一致 +2 不一致 -1 ギャップ -2　　　　　　　15 12 9

アラインメントの例

第 7 章パターン認識 (v1.13, 2008/12/24 12:39:16) ある程度の誤りを許して似ている音素データの並びになっているかを判定しなければいけない。別の見方をすると、音素や単語に対して 1 つのデータを用意してそれとの一致を調べるかわりに、パターン認識では、音素や単語に対して「似ている」データの集まりを考え、実際のデータがその集まりに含まれるかどうかを判定していると言える。ただし、似たデータの集まりは有限集合とも限らず、また、どれだけ似ているかを比較することも必要となるので、パターン認識のアルゴリズムには様々な工夫が必要となってくる。

7.2 アラインメント

パターン認識の 1 つとして、2 つの文字列を、一致部分が対応するように並べるアラインメント問題をとりあげて、そのアルゴリズムを見てみよう。2 つの文字列の一致部分が多ければ多いほど似ている文字列ということになるので、例えば DNA の塩基配列の遺伝的な近さを調べる場合などに登場する問題である。例えば GACGGATTAG と GATCGGAATAG という 2 つの文字列のアラインメントとは以下のようなものである。 0 1 2 3 4 5 6 7 8 9 0 GA CGGATTAG GATCGGAATAG ◦ ◦ × ◦ ◦ ◦ ◦ #◦ ◦ ◦ このように並べると、上の文字列は下の文字列と比べて (左端を 0 文字目として) • 2 文字目が欠けている (そこでギャップを挿入して位置を揃えてある)、 • 7 文字目が異なっている (不一致)、 • その以外の文字目は一致していることが分かる。文字列の下の記号はその位置が一致 _(◦)、ギャップ _(×)、不一致 _(#) のどれであるかを表わしている。アラインメントはいくつも考えられる。上の例であれば、 0 1 2 3 4 5 6 7 8 9 0 GAC GGATTAG GAT CGGAATAG ◦ ◦ #× ◦ ◦ ◦ #◦ ◦ ◦ 0 1 2 3 4 5 6 7 8 9 0 GAC GG ATTAG GAT CGGAATAG ◦ ◦ ## ◦ × ◦ #◦ ◦ ◦ をはじめとして、沢山の可能性がある。そこで通常は情報科学 2009 年度版_!c 増原英彦 117 第 7 章パターン認識 (v1.13, 2008/12/24 12:39:16) ある程度の誤りを許して似ている音素データの並びになっているかを判定しなければいけない。別の見方をすると、音素や単語に対して 1 つのデータを用意してそれとの一致を調べるかわりに、パターン認識では、音素や単語に対して「似ている」データの集まりを考え、実際のデータがその集まりに含まれるかどうかを判定していると言える。ただし、似たデータの集まりは有限集合とも限らず、また、どれだけ似ているかを比較することも必要となるので、パターン認識のアルゴリズムには様々な工夫が必要となってくる。

7.2 アラインメント

パターン認識の 1 つとして、2 つの文字列を、一致部分が対応するように並べるアラインメント問題をとりあげて、そのアルゴリズムを見てみよう。2 つの文字列の一致部分が多ければ多いほど似ている文字列ということになるので、例えば DNA の塩基配列の遺伝的な近さを調べる場合などに登場する問題である。例えば GACGGATTAG と GATCGGAATAG という 2 つの文字列のアラインメントとは以下のようなものである。 0 1 2 3 4 5 6 7 8 9 0 GA CGGATTAG GATCGGAATAG ◦ ◦ × ◦ ◦ ◦ ◦ #◦ ◦ ◦ このように並べると、上の文字列は下の文字列と比べて (左端を 0 文字目として) • 2 文字目が欠けている (そこでギャップを挿入して位置を揃えてある)、 • 7 文字目が異なっている (不一致)、 • その以外の文字目は一致していることが分かる。文字列の下の記号はその位置が一致 _(◦)、ギャップ _(×)、不一致 _(#) のどれであるかを表わしている。アラインメントはいくつも考えられる。上の例であれば、 0 1 2 3 4 5 6 7 8 9 0 GAC GGATTAG GAT CGGAATAG ◦ ◦ #× ◦ ◦ ◦ #◦ ◦ ◦ 0 1 2 3 4 5 6 7 8 9 0 GAC GG ATTAG GAT CGGAATAG ◦ ◦ ## ◦ × ◦ #◦ ◦ ◦ をはじめとして、沢山の可能性がある。そこで通常は情報科学 2009 年度版_!c 増原英彦 117 第 7 章パターン認識 (v1.13, 2008/12/24 12:39:16) ある程度の誤りを許して似ている音素データの並びになっているかを判定しなければいけない。別の見方をすると、音素や単語に対して 1 つのデータを用意してそれとの一致を調べるかわりに、パターン認識では、音素や単語に対して「似ている」データの集まりを考え、実際のデータがその集まりに含まれるかどうかを判定していると言える。ただし、似たデータの集まりは有限集合とも限らず、また、どれだけ似ているかを比較することも必要となるので、パターン認識のアルゴリズムには様々な工夫が必要となってくる。

7.2 アラインメント

パターン認識の 1 つとして、2 つの文字列を、一致部分が対応するように並べるアラインメント問題をとりあげて、そのアルゴリズムを見てみよう。2 つの文字列の一致部分が多ければ多いほど似ている文字列ということになるので、例えば DNA の塩基配列の遺伝的な近さを調べる場合などに登場する問題である。例えば GACGGATTAG と GATCGGAATAG という 2 つの文字列のアラインメントとは以下のようなものである。 0 1 2 3 4 5 6 7 8 9 0 GA CGGATTAG GATCGGAATAG ◦ ◦ × ◦ ◦ ◦ ◦ #◦ ◦ ◦ このように並べると、上の文字列は下の文字列と比べて (左端を 0 文字目として) • 2 文字目が欠けている (そこでギャップを挿入して位置を揃えてある)、 • 7 文字目が異なっている (不一致)、 • その以外の文字目は一致していることが分かる。文字列の下の記号はその位置が一致 _(◦)、ギャップ _(×)、不一致 _(#) のどれであるかを表わしている。アラインメントはいくつも考えられる。上の例であれば、 0 1 2 3 4 5 6 7 8 9 0 GAC GGATTAG GAT CGGAATAG ◦ ◦ #× ◦ ◦ ◦ #◦ ◦ ◦ 0 1 2 3 4 5 6 7 8 9 0 GAC GG ATTAG GAT CGGAATAG ◦ ◦ ## ◦ × ◦ #◦ ◦ ◦ をはじめとして、沢山の可能性がある。そこで通常は情報科学 2009 年度版 c!増原英彦 117

(8)

def align_sub(s,t,i,j) if i==0 || j==0 i*g() + j*g() else v0 = align_sub(s,t,i, j-1) + g() v1 = align_sub(s,t,i-1,j-1) + q(s[i-1],t[j-1]) v2 = align_sub(s,t,i-1,j) + g() max(v0,max(v1,v2)) end end def align_rec(s,t) align_sub(s,t,s.length(),t.length()) end

アラインメントの計算

align_rec.rb

(9)

•  一方の文字がない

前の文字がない _--- _ギャップ_-2が _XXX _{後の文字数分} 後の文字がない _XXXX _ギャップ_-2が _---- _{前の文字数分} 両方ともない _- ₀ _-

アラインメントの計算

_{- 1}

(10)

アラインメントの計算

align_rec.rb

(11)

•  最後の１文字のスコア

一致 +2 _XXXA _{1文字前へ} _XXXA _{1文字前へ} 不一致 -1 _XXXA _{1文字前へ} _XXXG _{1文字前へ} ギャップ -2 _XXX- _同じ位置 _XXXA _{1文字前へ} _XXXA _{1文字前へ} _XXX- _同じ位置

アラインメントの計算

_{- 2}

(12)

アラインメントの計算

g : ギャップのペナルティ q(c, d) : c と d の類似度 align_rec.rb

(13)

def max(x,y) if x>y x else y end end def g() -2 end def q(c,d) if c == d 2 else -1 end end 文字 c と文字 d の類似度を返す一致不一致いわずもがな、 x と y の最大値ギャップのペナルティ align_rec.rb max.rb

(14)

練習

•  max.rb を用意する。(教科書第3章 p.32)

•  align_rec.rb をダウンロードし、

align_rec("AAC","ATAG") を実行する。

•  実行時間を計測する。

irb(main):002:0> align_rec("AAC", "ATAG") => 1

irb(main):003:0> require(“benchmark") => true

irb(main):004:0> Benchmark.measure{ align_rec("GACGGA", "GATCGGA") }.real => 0.06

(15)

進捗状況の確認

1.  実行時間が計測できた時点で投票して

ください。

2.  align_rec(“AAC”,“ATAG”) は実行した。

3.  align_rec.rbが走らない。

(16)

動的計画法

•  テーブルを用意して、

再帰的な計算の重複を避ける。

•  テーブルの中身を順に埋めることにより、

求める値を計算する。

•  各種の最適化問題に適用。

–  アラインメント –  DNA・RNAのエネルギー最小化 –  構文解析

(17)

組合せ数の計算

•  パスカルの三角形

combination(n, k) = combination(n-1, k-1) + combination(n-1, k) n個から k個を選択する = n-1個から k-1個を選択して n個目も選択 + n-1個から k個を選択して n個目は選択せず 1 1 1 1 1 1 2 3 4 3 6 4 選択非選択 1 1 3 2 1 4 0 3 2 1 0

(18)

def combina,on(n,k)

if k > n

0 else

if k == 0

1 else

combina,on(n-‐1,k-‐1) + combina,on(n-‐1,k)

end

_{combina,on.rb}

組合せ数の計算

(19)

配列と繰り返しを使った

組み合わせ数の計算

(20)

load ("./make2d.rb")

def combina,on_loop(n,k)

c = make2d(n+1,n+1)

for i in 0..n

c[i ][0] = 1

for j in 1..(i-‐1)

c[i][j] = c[i-‐1][j-‐1] + c[i-‐1][j]

end

c[i][i] = 1

end

c[n][k]

(21)

動的計画法

•  プロ野球日本シリーズでの優勝の確率

P(i, j): Aは残り i 勝、Bは残り j 勝という状況で、最終的にAが優勝する確率 P(i, j) = 1 i=0 かつ j>0 = 0 i>0 かつ j=0

= (P(i-1, j) + P(i, j-1))/2 i>0 かつ j>0

1 1 1 0 0 0 1/2 1/4 1/8 3/4 1/2 7/8 j i ₁ AとBは同じ強さと仮定 0 0 1 2 3 4 1 2 3

(22)

1.  1/16

2.  3/16

3.  5/16

4.  7/16

5.  9/16

ここは？

1 1 1 0 0 0 1/2 1/4 1/8 3/4 1/2 7/8 1 j i 0 0 1 2 3 4 1 2 3

(23)

アラインメントの動的計画法

•  二つの配列 s と t の間の類似度

•  a[i][j] : s の部分配列 s[0],...,s[i-1] と

t の部分配列 t[0],...,t[j-1] の間の類似度 •  a[i][j] = max{ a[i][j-1] + g(),

a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g() } g() : ギャップのペナルティ（負の数） q(c, d) : c と d の類似度 c と d が等しければ適当なスコア（正）似ていればそれなりのスコア似ていなければ不一致のペナルティ（負）

(24)

境界条件

_{(初期条件)}

•  a[0][0] = 0

•  a[0][j] = a[0][j-1] + g() (j>0)

•  a[i][0] = a[i-1][0] + g() (i>0)

•  結局

a[0][j] = j*g()

_{a[i][0] = i*g()}

•  となる。要するに、ギャップばかり。

(25)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A G s 0 -2 -4 -6 -8 A -2 A -4 C -6

A-AC

ATAG

(26)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A C s 0 -2 -4 -6 -8 A -2 A -4 C -6

1.  1

2.  2

3.  3

4.  4

5.  0

6.  -1

7.  -2

8.  -3

9.  -4

ここは？

(27)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A G s 0 -2 -4 -6 -8 A -2 2 A -4 C -6

A-AC

ATAG

(28)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A C s 0 -2 -4 -6 -8 A -2 2 A -4 C -6

1.  1

2.  2

3.  3

4.  4

5.  0

6.  -1

7.  -2

8.  -3

9.  -4

ここは？

(29)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A G s 0 -2 -4 -6 -8 A -2 2 0 A -4 0 C -6

A-AC

ATAG

(30)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A G s 0 -2 -4 -6 -8 A -2 2 0 -2 -4 A -4 0 1 2 0 C -6 -2 -1 0

A-AC

ATAG

(31)

1.  1

2.  2

3.  3

4.  4

5.  0

6.  -1

7.  -2

8.  -3

9.  -4

A-A- ATAG A-A ATA AAC ATA

ここは？

(32)

A-AC

ATAG

A-A ATA A-A- ATAG AAC ATA

(33)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A G s 0 -2 -4 -6 -8 A -2 2 0 -2 -4 A -4 0 1 2 0 C -6 -2 -1 0 1 A-AC ATAG

A-AC

ATAG

A-A ATA A-A- ATAG AAC ATA

(34)

def align(s,t) m = s.length() n = t.length() a = make2d(m+1,n+1) a[0][0] = 0 for j in 1..n a[0][j] = a[0][j-1] + g() end for i in 1..m a[i][0] = a[i-1][0] + g() end for i in 1..m for j in 1..n # ここを埋めてみよう end end a end 境界条件 align.rb

(35)

トレースバック

•  最大の類似度を与えるアラインメントを

提示するために、配列の最後から、それ

までの選択を振り返る（トレースバック）。

•  ギャップの入った文字列を（配列にして）

二つ返す。

(36)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A G s 0 -2 -4 -6 -8 A -2 2 0 -2 -4 A -4 0 1 2 0 C -6 -2 -1 0 1

A-AC

ATAG

→j

→

i

(37)

A-AC

ATAG

→j

→

i

(38)

A-AC

ATAG

A-AC ATAG A-A ATA

→j

→

i

(39)

A-AC

ATAG

→j

→

i

(40)

A-AC

ATAG

→j

→

i

(41)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A G s 0 -2 -4 -6 -8 A -2 2 0 -2 -4 A -4 0 1 2 0 C -6 -2 -1 0 1 A A A- AT

→j

→

i

A-AC

ATAG

(42)

A-AC

ATAG

→j

→

i

(43)

while i>0 || j>0

if j>0 && a[i][j] == a[i][j-1] + g() u = "-" + u

v = t[j-1 .. j-1] + v j = j - 1 # go left else

if i>0 && j>0 &&

a[i][j] == a[i-1][j-1] + q(s[i-1], t[j-1]) # ここを埋めてみよう

else

if i>0 && a[i][j] == a[i-1][j] + g() # ここを埋めてみよう end end end end [u,v] end def traceback(a,s,t) u = "" v = "" i = s.length() j = t.length()

align.rb u の前に - を追加 v の前に t[j-1] を追加条件

(44)

A-AC

ATAG

→j

→

i

(45)

A-AC

ATAG

→j

→

i

G C

(46)

A-AC

ATAG

→j

→

i

AG AC

(47)

A-AC

ATAG

→j

→

i

-AG TAC

(48)

A-AC

ATAG

→j

→

i

A-AG ATAC

(49)

スコア：一致 +2 不一致 -1 ギャップ -2

1. -AAC

ATAG

2. A-AC

ATAG

3. AA-C

ATAG

4. AAC-

ATAG

アラインメントは？

t A T A G s 0 -2 -4 -6 -8 A -2 2 0 -2 -4 A -4 0 1 2 0 C -6 -2 -1 0 1

(50)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A C s 0 -2 -4 -6 -8 A -2 T -4 C -6

1. -ATC

ATAC

2. A-TC

ATAC

3. AT-C

ATAC

4. ATC-

ATAC

アラインメントは？

(51)

スコア：一致 +2 不一致 -1 ギャップ -2 t A T A s 0 -2 -4 -6 A -2 2 0 -2 A -4 0 1 2 C -6 -2 -1 0

A-AC

ATA-

→j

→

i

AAC

ATA

必ずしも１通りではない！

(52)

練習

•  align.rb をダウンロードする。 •  align を完成させて、 align("AAC","ATAG") を実行する。 •  RNase_P.rb をダウンロードし、 align(seq0(),seq1()) を実行する。 •  traceback を完成させて、 align_dp("AAC","ATAG") を実行する。 •  align_dp(seq0(),seq1()) を実行する。

進捗状況の確認 1. gj も gjp も動いた 2. gj は動いた 3. gj も動かない 2

連立

1次方程式の数値解法

• 小規模な連立1次方程式の解法

• （大規模な連立1次方程式の解法）

進捗状況の確認

1. gj も gjp も動いた。

2. gj は動いた。

3. gj も動かない。

パターン認識

• 音や画像に中に隠れた

パターンを認識する。

• 「パターン」は唯一のデータではなく、

似通ったデータの集まりを表している。

• 「等しい」から「似ている」へ

• 「～だ」から「～らしい」へ

アラインメント

• アラインメント

２つ（複数）の文字列の比較

GACGGATTAG と GATCGGAATAG

GA-CGGATTAG

GATCGGAATAG

• ぴったり同じでなくとも、

似ているかどうかを判定。

• スコア

• 類似度が最大の

アラインメント（ギャップの入れ方）を求める。

アラインメント

• スコア

アラインメントの例

7.2

アラインメント

7.2

アラインメント

7.2

アラインメント

アラインメントの計算

• 一方の文字がない

アラインメントの計算

- 1

アラインメントの計算

• 最後の１文字のスコア

アラインメントの計算

- 2

アラインメントの計算

練習

• max.rb を用意する。(教科書第3章 p.32)

• align_rec.rb をダウンロードし、

align_rec("AAC","ATAG") を実行する。

• 実行時間を計測する。

進捗状況の確認

1. 実行時間が計測できた時点で投票して

ください。

2. align_rec(“AAC”,“ATAG”) は実行した。

3. align_rec.rbが走らない。

動的計画法

• テーブルを用意して、

再帰的な計算の重複を避ける。

• テーブルの中身を順に埋めることにより、

求める値を計算する。

• 各種の最適化問題に適用。

組合せ数の計算

• パスカルの三角形

def combina,on(n,k)

if k > n

0

else

if k == 0

1

else

combina,on(n-­‐1,k-­‐1) + combina,on(n-­‐1,k)

end

end

end

combina,on.rb

組合せ数の計算

配列と繰り返しを使った

組み合わせ数の計算

load ("./make2d.rb")

def combina,on_loop(n,k)

_{1次方程式の数値解法}

•  小規模な連立1次方程式の解法

•  （大規模な連立1次方程式の解法）

1.  gj も gjp も動いた。

2.  gj は動いた。

3.  gj も動かない。

•  音や画像に中に隠れた

•  「パターン」は唯一のデータではなく、

•  「等しい」から「似ている」へ

•  「～だ」から「～らしい」へ

•  アラインメント

•  ぴったり同じでなくとも、

•  スコア

•  類似度が最大の

•  スコア

•  一方の文字がない

_{- 1}

•  最後の１文字のスコア

_{- 2}

•  max.rb を用意する。(教科書第3章 p.32)

•  align_rec.rb をダウンロードし、

•  実行時間を計測する。

1.  実行時間が計測できた時点で投票して

2.  align_rec(“AAC”,“ATAG”) は実行した。

3.  align_rec.rbが走らない。

•  テーブルを用意して、

•  テーブルの中身を順に埋めることにより、

•  各種の最適化問題に適用。

•  パスカルの三角形

combina,on(n-‐1,k-‐1) + combina,on(n-‐1,k)

_{combina,on.rb}

for j in 1..(i-‐1)

c[i][j] = c[i-‐1][j-‐1] + c[i-‐1][j]

•  プロ野球日本シリーズでの優勝の確率

1.  1/16

2.  3/16

3.  5/16

4.  7/16

5.  9/16

_{(初期条件)}

•  a[0][0] = 0

•  a[0][j] = a[0][j-1] + g() (j>0)

•  a[i][0] = a[i-1][0] + g() (i>0)

•  結局

•  となる。要するに、ギャップばかり。

1.  1

2.  2

3.  3

4.  4

5.  0

6.  -1

7.  -2

8.  -3

9.  -4

1.  1

2.  2

3.  3

4.  4

5.  0

6.  -1

7.  -2

8.  -3

9.  -4

1.  1

2.  2

3.  3

4.  4

5.  0

6.  -1

7.  -2

8.  -3

9.  -4