Dynamic Programming - Sequence Alignment

Sequence Alignment

• Global, Local, Semi-local Alignment Problems.
• 편집거리에서 insert 와 delete로 인한 길이 차이 발생을 방지.
  빈자리에 gap symbol(‘-’) 을 넣어서 매치시키기.
  즉, 두 문자열은 최종적으로 같은 길이의 문자열이 된다.
• 모든 문자들 쌍에 대한 score가 존재. score가 최대가 되도록 하는 답 구하기.

문자열 A, B 가 주어졌을 때 이에 대한 optimal global alignment V를 구해보자.

이때 각 문자 쌍에 대한 σ (Scoring Matrix)가 주어진다면 다음과 같이 계산하면 된다.
(편집 거리 코드에서 +1 되던 부분을 score 값으로 변경하면 된다.)

V(0, 0) = 0
V(i, 0) = V(i-1, 0) + σ(ai, -)
V(0, j) = V(0, j-1) + σ(-, bj)

V(i,j) = Max(V(i-1, j-1) + σ(ai, bj), V(i-1, j) + σ(ai, -), V(i, j-1) + σ(-, bj))