第7章の練習，投票

ここは?

  1. 1/16
  2. 3/16
  3. 5/16
  4. 7/16
  5. 9/16

再帰版のアラインメント

align_rec.rb 
def max(x,y)
  if y < x	
    x
  else
    y
  end		
end

def g()
  -2
end

def q(x,y)
  if x==y
    2
  else
    -1
  end
end

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.rb 
def max(x,y)
  if y < x	
    x
  else
    y
  end		
end

def make1d(w)
  a=Array.new(w)
  for i in 0..(w-1)
    a[i]=0
  end
  a
end
def make2d(h,w)
  a=Array.new(h)
  for i in 0..(h-1)
    a[i]=make1d(w)
  end
  a
end

def g()
  -2
end

def q(c,d)
   if c == d
       return 2
   else
       return -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
#   ここを埋めます．      
    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

ここは?

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. -1
  7. -2
  8. -3
  9. -4

gap1は?

  1. 1000
  2. 0100
  3. 0010
  4. 0001
  5. 1100
  6. 0110
  7. 0011

練習