Algorithm Analysis - Dynamic Programming 3 SERIES 3/4

Blog Logo
on



read

Algorithm Analysis: Dynamic Programming 3

알고리즘 관련 모든 글은 연세대학교 안형찬 교수님의 CSI_3108: Algorithm Analysis의 강의 내용과 자료입니다.

Minimum cost sequence alignment

Alignment problem

우선 matching이란 각 x와 y에 있는 원소들로 이루어진 순서쌍들의 집합이고 한 원소가 두 번 이상 등장하지 않습니다. 그리고 이런 matching 중에서 definition3처럼 crossing이 일어나지 않는 경우 이를 alignment라고 정의합니다. 그리고 하나의 alignment에 대한 cost는 만약 unmatched position이 있다면 그건 gap penalty가 적용되고, 순서쌍 내 원소가 서로 같은 글자가 아니면 mismatch cost가 생깁니다.

예시를 들어보면

s t o p -

- t o p s

이는 {(2,1),(3,2),(4,3)}이라는 alignment에 해당하게 됩니다. 이 경우에는 mismatch cost는 없고 gap penalty 2번만 있게 됩니다. 우리는 두 sequence 사이에서 가능한 여러 alignment 중에서 cost가 최소가 되는 것을 찾고 싶은 것입니다.

마지막 글자부터 align을 시작한다고 해볼 때, $OPT(i,j)$는 $x_1, x_2, … , x_i$ 와 $y_1, y_2, … , y_j$ 사이의 minimum cost라고 하겠습니다. 마지막 글자들의 쌍은 둘이 matching을 시키든지, 아니면 시키지 않든지 2가지가 가능합니다. 만약 matching이 되지 않는 경우라면 둘 중 하나는 다른 앞선 글자랑 matching이 되어야 합니다. 정리해보겠습니다.

  • 만약 (m,n) $\notin$ M인 경우, $x_m$ 또는 $y_n$ 둘 중 하나는 M에 존재하지 않습니다.
    • 증명: 만약 $x_m$ 과 $y_n$ 이 둘 다 서로가 아닌 다른 것과의 matching으로 M에 존재한다면, 이렇게 됩니다. $ i < m$ 인 어떤 $i$, $j<n$ 인 어떤 $j$가 존재하고 $(m,j), (n,i) \in M$ 이 성립합니다. 하지만 이는 우리의 “non-crossing”조건에 위배합니다. 왜냐하면 n보다 작은 j랑 m이 연결되고, m보다 작은 i랑 n이 연결되기 때문입니다(그림을 그려보면 쉽게 알 수 있습니다).

따라서 우리의 점화식은 총 3가지 경우의 수로 나뉘게 됩니다.

  • (m,n) 이 matching에 있는 경우: mismatch cost 항 발생
  • m이 혼자 다른 애랑 matching에 있고, n은 gap과 연결되는 경우: gap penalty 항 발생
  • n이 혼자 다른 애랑 matching에 있고, m은 gap과 연결되는 경우: gap penalty 항 발생

Lemma 1.

For all $i \ge 1\,\,and \,\,j \ge 1$ ,

$Proof.$

만약 $(i,j) \in M$ 라면 $OPT(i,j) =OPT(i-1,j-1)+\alpha_{x_i,x_j} $ 가 성립합니다.

왜냐하면 $M/{(i,j)}$ 은 $x_1, x_2, … , x_{i-1}$ 와 $y_1, y_2, … , y_{j-1}$ 의 어느 한 alignment일 뿐이고, 이런 어떤 alignment들에 $(i,j)$만 붙이면 $x_1, x_2, … , x_{i}$ 와 $y_1, y_2, … , y_{j}$ 을 얻을 수 있기 때문입니다. 더 상술해보면 , 우선 $OPT(i,j) - \alpha_{x_i,x_j} \ge OPT(i-1,j-1)$ 이 성립합니다. 왜냐하면 $M/{(i,j)}$ (M에서 $(i,j)$항을 제거한 alignment)는 $x_1, x_2, … , x_{i-1}$ 와 $y_1, y_2, … , y_{j-1}$ 의 어느 한 alignment일 뿐이니, $OPT(i-1,j-1)$보다 작을 수는 없기 때문입니다. 또 반대로 $OPT(i,j) \le OPT(i-1,j-1) + \alpha_{x_i,x_j} $ 도 성립합니다. 왜냐하면 $M$에 $(i,j)$를 갖다 붙인 것 또한 어느 한 alignment일 뿐이고, 이는 optimal한 $OPT(i,j)$보다 작을 수 없기 때문입니다. 비슷한 논리로 gap penalty가 발생하는 2가지 경우도 증명할 수 있습니다.


알고리즘 구현

점화식을 그대로 옮기면 되는 간단한 알고리즘입니다.

M[i,0]=i*delta for all i
M[0,j]=j*delta for all j

for i = 1 to m:
	for j = 1 to n:
		M[i,j]=min( M[i-1,j-1]+mismatch_cost(x_i,y_j), M[j,i-1]+delta, M[i-1,j]+delta )

return M[m,n]

시간복잡도

$O(mn)$ 입니다. 왜냐하면 i와 j에 대해 iterate하는데 두 sequence가 길이가 다를 수 있기 때문입니다.

정리

어느 한 문제를 Subproblem으로 쪼개거나 줄일 때 그 이전 단계와 decoupling 되는 원소 또는 지점에 대한 결정의 경우의 수가 점화식으로 이어집니다. 여기서도 마지막 글자에 대해 어떤 결정을 내릴지(3가지 가능성)에 따라 점화식이 3가지 경우 중 어느 하나를 취하는 형식이었습니다. 따라서 dynamic programming으로 문제를 접근할 때는 내가 내릴 수 있는 결정의 가지 수를 파악하는 것이 중요합니다.

Algorithm Analysis

Written by
Blog Logo

순록킴

Published

Supported by