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

Size: px

Start display at page:

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

かおりかみこ
6 years ago
Views:

1 連立 1 次方程式の数値解法小規模な連立 1 次方程式の解法消去法 Gauss 消去法 Gauss-Jordan 法 ( 大規模な連立 1 次方程式の解法 ) ( 反復法 ) (Jacobi 法 ) 講義では扱わない 1

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

3 パターン認識入門

4 パターン認識音や画像に中に隠れたパターンを認識する音素音節単語文基本図形文字指紋物体人物顔パターンは唯一のデータではなく似通ったデータの集まりを表している多様性ノイズ等しいから似ているへ ~ だから ~ らしいへ

5 アラインメントアラインメント 2つ ( 複数 ) の文字列の比較音声認識文字認識 DNAやタンパクの比較 GACGGATTAG と GATCGGA ギャップ不一致 GA-CGGATTAG GATCGGA

6 ぴったり同じでなくとも似ているかどうかを判定スコア一致 +2 不一致 -1 ギャップ -2 足し合わせる à アラインメントの類似度類似度が最大のアラインメント最適化アラインメント ( ギャップの入れ方 ) を求める

7 スコアアラインメントの例一致 +2 不一致 GA CGGATTAG GATCGGA ギャップ GAC GGATTAG GAT CGGA GAC GG ATTAG GAT CGGA 12 9

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)) アラインメントの計算 def align_rec(s,t) align_sub(s,t,s.length(),t.length()) align_rec.rb

9 アラインメントの計算 - 1 一方の文字がない前の文字がない --- ギャップ-2が XXX 後の文字数分後の文字がない XXXX ギャップ-2が ---- 前の文字数分両方ともない - 0 -

10 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)) アラインメントの計算 def align_rec(s,t) align_sub(s,t,s.length(),t.length()) align_rec.rb

11 アラインメントの計算 - 2 最後の 1 文字のスコア一致 +2 XXXA 1 文字前へ XXXA 1 文字前へ不一致 -1 XXXA 1 文字前へ XXXG 1 文字前へギャップ -2 XXX- 同じ位置 XXXA 1 文字前へ XXXA 1 文字前へ XXX- 同じ位置

12 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)) アラインメントの計算 g : ギャップのペナルティ q(c, d) : c と d の類似度 def align_rec(s,t) align_sub(s,t,s.length(),t.length()) align_rec.rb

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

14 練習 max.rb を用意する ( 教科書第 3 章 p.32) align_rec.rb をダウンロードし align_rec("aac","") を実行する実行時間を計測する irb(main):002:0> align_rec("aac", "") => 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, ) は実行した 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 個目は選択せず選択非選択

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) 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] c[i][i] = 1 c[n][k] combina,on_loop.rb

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 j i / /4 1/8 3/4 1/2 7/8 A と B は同じ強さと仮定

22 1. 1/ / / / /16 j i /2 3/4 7/ /4 1/2 1/8 ここは?

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) 例えば g() = -2 結局 a[0][j] = j*g() a[i][0] = i*g() となる要するにギャップばかり

25 スコア : 一致 +2 不一致 -1 ギャップ -2 A-AC t A T A G s A -2 A -4 C -6

26 スコア : 一致 +2 不一致 -1 ギャップ -2 t A T A C s A -2 A -4 C -6 ここは?

27 スコア : 一致 +2 不一致 -1 ギャップ -2 A-AC t A T A G s A -2 2 A -4 C -6

28 スコア : 一致 +2 不一致 -1 ギャップ -2 t A T A C s A -2 2 A -4 C -6 ここは?

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

30 スコア : 一致 +2 不一致 -1 ギャップ -2 A-AC t A T A G s A A C

31 スコア : 一致 +2 不一致 -1 ギャップ -2 A-A ATA t A T A G s A A C AAC ATA ここは? A-A

32 スコア : 一致 +2 不一致 -1 ギャップ -2 A-AC t A T A G s A A C A-A ATA A-A- AAC ATA

33 スコア : 一致 +2 不一致 -1 ギャップ -2 A-AC t A T A G s A A C A-A ATA A-A- AAC ATA A-AC

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() for i in 1..m a[i][0] = a[i-1][0] + g() for i in 1..m for j in 1..n # ここを埋めてみよう a 境界条件 align.rb

35 トレースバック最大の類似度を与えるアラインメントを提示するために配列の最後からそれまでの選択を振り返る ( トレースバック ) ギャップの入った文字列を ( 配列にして ) 二つ返す

36 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C

37 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C

38 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC i t A T A G s A A C A-A ATA A-AC

39 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C

40 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C

41 スコア : 一致 +2 不一致 -1 ギャップ -2 A A A- AT j t A T A G A-AC s i A A C

42 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C

43 u の前に - を追加 v の前に t[j-1] を追加 def traceback(a,s,t) u = "" v = "" i = s.length() j = t.length() 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() # ここを埋めてみよう [u,v] 条件 align.rb

44 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C

45 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C G C

46 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C AG AC

47 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C AG TAC

48 スコア : 一致 +2 不一致 -1 ギャップ -2 j A-AC t A T A G s i A A C A-AG ATAC

49 スコア : 一致 +2 不一致 -1 ギャップ -2 アラインメントは? t A T A G s A A C AAC 2.A-AC 3.AA-C 4.AAC-

50 スコア : 一致 +2 不一致 -1 ギャップ -2 アラインメントは? t A T A C s A -2 T -4 C ATC ATAC 2.A-TC ATAC 3.AT-C ATAC 4.ATC- ATAC

51 スコア : 一致 +2 不一致 -1 ギャップ -2 j i t A T A s A A C A-AC ATA- AAC ATA 必ずしも 1 通りではない!

52 練習 align.rb をダウンロードする align を完成させて align("aac","") を実行する RNase_P.rb をダウンロードし align(seq0(),seq1()) を実行する traceback を完成させて align_dp("aac","") を実行する align_dp(seq0(),seq1()) を実行する 1. align_dp(seq0(),seq1()) が動いた時点で投票してください

53 進捗状況の確認 1. align_dp が正しく動いた 2. align_dp(traceback) が動かない 3. align は動いたが traceback がまだできていない 4. align はできたがうまく動かない 5. align がまだできていない

11yama

11yama 連立 1 次方程式の数値解法小規模な連立 1 次方程式の解法消去法 Gauss 消去法 Gauss-Jordan 法 ( 大規模な連立 1 次方程式の解法 ) ( 反復法 ) (Jacobi 法 ) 講義では扱わない 1 進捗状況の確認 1. gj も gjp も動いた 2. gj は動いた 3. gj も動かない 2 パターン認識入門パターン認識音や画像に中に隠れたパターンを認識する音素