パターン認識


プログラム


  1. 動的計画法によるアライメントの計算

    load("./make2d.rb")
    load("./max.rb")
    
    def g()
      -2
    end
    
    def q(c,d)
      if c == d
        2
      else
        -1
      end
    end
    
    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
          # a[i][j]を計算する
        end
      end
      a
    end
    
    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()
              # 上から求められた場合
            end
          end
        end
      end
      [u,v]
    end
    
    def align_dp(s,t)
      traceback(align(s,t),s,t)
    end
    

2016年11月13日作成
伊知地 宏
Copyright (C) Hiroshi Ichiji, 2016. All rights reserved.