[동적계획법/Dynamic Programming]LCS 문제(최장 공통 부분 수열) 파이썬 코드

 

 

동적 계획법에 대한 자세한 내용 : 2020/12/13 - [알고리즘] - Dynamic Programming (동적 계획법)

 

 

what ia LCS?

• Longest Common Subsequence
• <bcdb>는 <abcbdab>의 subsequence이다. 
• <bca>는 <abcbdab>와 <bdcaba>의 common subsequence이다. 
• Longest common subsequence? common subsequence들 중 가장 긴것. 
• <bcba>는 <abcbdab>와 <bdcaba>의 LCS이다. 

 

1. optimal substructure

x=<x1,x2,...,xi>, yj=<y1,y2,...yj>, LCS z에 대해서 마지막 부분에 대응하는 값을 떼고 생각할 수 있다. 이런식으로 작은 문제로 쪼갤 수 있다.

 

2. recursive

LCS

x1

x2

...

xi-1

xi

y1

y2

y3

...

yj-1

yj

 

case1. xi=yi 이므로 그 이전 문자들의 LCS에 마지막 문자의 길이 1을 더해준다. 

case2. xi와 yi 가 다르면 xi 와 yj 모두가 LCS에 들어갈 수 없다. 즉 둘중 하나는 버려야하므로 각각을 버릴때 경우에서 큰 값을 택한다. 

 

3. 최적해를 계산한다. 

X / Y	0	B	D	C	A	B
0	0	0	0	0	0	0
A	0	0	0	0	1	1
B	0	1	1	1	1	2
C	0	1	1	2	2	2
B	0	1	1	2	2	3
D	0	1	2	2	2	3
A	0	1	2	2	3	LCS(6,5) = 3

점화식대로 문자가 같을때와 다를때로 나누어서 값을 채워넣는다. 

ABCBDA와 BDCAB의 LCS길이는 3이라는것을 알 수 있다. 

 

LCS 길이를 구하는 파이썬 코드(Python3)

 

위의 표가 코드에서의 m행 n열(mXn) 행렬이 된다.

위 예시의 경우에는 result : 7X6 행렬이다. 

또한 input X : "ABCBDA", Y : "BDCAB" 이다. 

점화식을 수행한 후 LCS(6,5)에 해당하는 result[6][5] 를 출력해주면 LCS의 길이 3이 나온다. 

 

# input array X,Y
# LCS 수행 함수. LCS길이를 구하며, 이를 구하기 위해 사용된 배열을 return한다.

def LCS(X,Y):
    m=len(X)+1  #표의 row 개수
    n=len(Y)+1  #표의 column 개수
    result=[["-" for _ in range(0,n)] for _ in range(0,m)]  # m by n 행렬을 만든다.
    # 점화식 구현
    for i in range(0,m):
        for j in range(0,n):
            if(i==0 or j==0):
                result[i][j]=0
            elif(X[i-1]==Y[j-1]):
                result[i][j]=result[i-1][j-1]+1
            else :
                result[i][j]=max(result[i][j-1],result[i-1][j])
            print("%-3d" %result[i][j], end=" ")
        print()
    print()
    print("LCS number of two DNA sequences is",result[-1][-1])  #배열의 맨 마지막 값 출력
    return result

 

해당 함수를 실행해보면 위 표와 같은 결과를 얻는것을 볼 수 있다.

 

Running time : 이차원 배열 m X n 에 대해 for문을 돌리므로 O(mn)

 

 

4. 최적해 방법을 구축한다. (최적해 일 때의 경로를 구한다.)

X / Y	0	B	D	C	A	B
0	0	0	0	0	0	0
A	0	0	0	0	1	1
B	0	1	1	1	1	2
C	0	1	1	2	2	2
B	0	1  ↖	1	2	2	3
D	0	1	2  ↖	2  ←	2	3
A	0	1	2	2	3  ↖	LCS(6,5) = 3  ←

 

LCS 문자를 구하는 파이썬 코드(Python3)

 

3번에서는 LCS의 길이와 각 길이를 기록한 배열을 얻었다. 이를 통해서 이제 LCS문자가 무었인지 구해본다. 

배열을 역추적하여 LCS 문자열을 구하는 함수를 작성한다.
배열 끝부분 부터 역추적하며 이동하며 X[i]와 Y[j]의 값이 같은 문자열만 저장한다.

두 문자가 같다면  이 문자를 이어붙인 후 ↖로 이동

두 문자가 다르다면 위 또는 왼쪽에 있는 값 중 큰 수로 이동한다. 

행렬값이 0인것은 LCS문자가 없는것이므로 종료한다. 
역추적 하였으므로 문자열이 거꾸로 저장되어있기 때문에 최종 답을 구할 때는 역순출력한다.

 

def print_LCS(X,Y,result):
    i=len(X)
    j=len(Y)
    LCS_word=[]
    # 배열의 맨 마지막부터 시작해서 i=0,j=0까지 반복한다.
    while(i!=0 and j!=0):
        # 두 문자가 같을때만 LCS_word에 저장한 후 ↖로 이동
        if (X[i-1]==Y[j-1]):
            LCS_word.append(X[i-1])
            i=i-1
            j=j-1
        # 두 문자가 같지 않다면 위 or 왼쪽 값 중 큰 수로 이동. 같으면 둘다 가능. 해당 코드는 왼쪽으로
        else:
            if result[i-1][j]>result[i][j-1]:
                i=i-1
            else:
                j=j-1
    answer = LCS_word[::-1]    #역순출력
    return (answer)

 

함수를 실행하면 

 

LCS는 "BDA"가 출력되는것을 볼 수 있다. 

 

Runnung time : 배열에서 왼쪽 또는 위로만 이동하므로 O(m+m)

 

 

LCS(Longest Common Subsequence) 활용사례 - DNA 염기 서열의 유사성 분석

 

다음과 같은 A,T,G,C 로 이루어진 염기서열 S1, S2가 있을 때 이 두 염기서열의 유사성은?

LCS를 사용한다!

# S1과 S2의 LCS를 구하기
S1=list("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA")
S2=list("GTCGTTCGGAATGCCGTTGCTCTGTAAA")

print("LCS word of two DNA sequences is", print_LCS(S1,S2,LCS(S1,S2)))

 

 

두 염기서열의 LCS 는 "GTCGTCGGAAGCCGGCCGAA" 이며 길이는 20이다.