[Dynamic Programming] Sequence Alignment & 최대 공백 정사각형

다양한 Alignment 문제들을 의미한다. 

edit distance보다 좀 더 확장된 의미이다.

 

• Global, Local, Semi-local Alignment Problems
• Global Alignment는 두 개의 문자열을 gap symbol("-")을 포함하도록 확장하여 같은 길이의 문자열로 만드는 문제이다
  edit distance의 경우, gap 부분에 insert한다고 생각하면 된다
• 대응되는 문자들의 쌍에 대하여 score가 입력으로 주어진ㄴ다
• 대응되는 문자들의 쌍들의 score 합의 최대치가 되는 alignment를 구하는 것이 목적이다
• alignment 문제들은 대부분 동적 계획법으로 해결된다

Global Alignment

두 개의 스트링 acvcdb와 cadbd가 있을 때 두 스트링은 얼마나 비슷한가?

 

• 두 string의 유사도를 측정하는 기본적인 방법 : 두 string을 확장하여 같은 길이로 만든 후, 같은 위치에 있는 두 문자들을 서로 비교하는 것이다. 여기서 확장한다는 것의 의미는 적당한 수의 빈칸(-)을 삽입하는 것을 말한다
• acbcdb에 빈칸을 하나 넣어 acbcdb-로 확장
• cadbd에 빈칸을 두 개 넣어 -c-adbd로 확장하여 두 확장된 string을 비교한다

a	c	b	c	d	b	-
-	c	-	a	d	b	d

 

• 같은 위치에 있는 문자 쌍에 대한 유사도 점수를 계산하여 이를 모두 합하여 전체의 유사도를 구한다.
• 일반적으로 x = y이면 점수가 크고 x != y이면 점수가 작다
• 둘 다 빈칸일 경우, 같은 자리를 빈칸으로 확장한 것이므로 0점이나 음수 점수여야한다.

 

기저 조건

V(0,0) = 0

V(i,0) = V(i-1, 0) + score(ai, -) : 전부 빈칸을 넣을 수 밖에 없음

V(0,j) = V(0, j-1) + socre(-, bj) : 전부 빈칸을 넣을 수 밖에 없음

 

부분 문제들의 관계

V(i,j) = max{ V(i-1, j-1) + score(ai, bj), V(i-1,j) + score(ai, -), V(i, j-1) + score(-, bj)}

 

최대 공백 정사각형

주어진 n x n 크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈(empty) 정사각형을 구하기

 

모든 점에 대해서 0,1이 다 주어진다

모든 점을 한번씩 다 쳐다볼 수 있는 시간이 있다.

 

재귀적 서술 

모든 점에 대해서 오른쪽 아래로 가지는 가장 큰 정사각형을 계산한다.

배열의 "해"는 오른쪽 아래로 가지는 가장 큰 정사각형이다

 

지금 (x,y)가 5이려면 나머지가 모두 4이상이여야한다 (x-1, y-1) (x-1, y) (x, y-1)

 

m x m 크기의 픽셀로 이루어진 정사각형 S이 비어있다면 다음이 성립한다

• S의 가장 우측 하단의 픽셀이 비어있다.
• 좌측 상단, 좌측 하단, 우측 상단의 크기 (m-1) x (m-1) 정사각형이 비어있다.
• 역도 성립

DP로 해결

LES(x,y) : (x,y)를 우측 하단 꼭지점으로 하는 최대 정사각형의 크기

 

• 픽셀 (x,y)가 비어있지 않다면 LES(x,y) = 0
• 첫번째 행 또는 열의 픽셀 (x,y)가 비어있다면 LES(x,y) = 1
• 나머지 픽셀 (x,y)가 비어있다면 LES(x,y) = min(LES(x-1,y-1), LEX(x,y-1), LEX(x-1,y)} + 1

for x = 1 to n
    for y = 1 to n
        if (x,y) not empty
            LES[x,y] = 0
        else if x = 1 or y = 1
            LES[x,y] = 1
        else LES[x,y] = min(LES[x-1,y-1], LES[x, y-1], LES[x-1,y]) + 1