23. 최장 공통 부분 수열(lcs) [10 2주차]

23. 최장 공통 부분 수열(LCS) [10-2주차]

2024년 1월 14일 일요일

오전 2:58

<최장 공통 부분 수열(LCS)>

X = ACCGGTCGACGTAAGCCGGCCAA,
Y = TTTCCCACTCGTGTCGACGTGTAAGCCTTAAGGCCAA
 

두 개의 DNA 순서열 (sequence)이 있을 때, 이 두 개가 얼마나 유사한지를 측정하는 일이 자주 발생한다.

이 때 이 둘이 얼마나 유사한지를 측정할 때, 둘의 LCS를 구하여 이것이 길면 길수록 둘은 더 유사하다고 할 수 있다.

LCS를 정의하기 위해, 먼저 부분서열(subsequence)를 정의한다.

• 부분서열 : 주어진 서열에서 일부 문자를 삭제한 뒤, 남은 문자들을 순서대로 연결한 서열
• X와 Y의 공통 부분서열 : X의 부분 서열이면서 Y의 부분 서열이 되는 것.
• LCS : 공통 부분서열 중 가장 긴 것

LCS를 구하기 위해, X의 모든 부분 서열에 대해 Y의 모든 부분 서열을 비교하는 브루트포스 방법을 시도할 수 있다. X의 모든 부분 서열을 구하는 것만 해도, 경우의 수가 mC0 + mC1 + … + mCm = 2^m으로 지수 시간이 걸린다.

동적계획법을 통해 LCS를 구하는 방법을 알아보자

<동적계획법으로 LCS 구하기>

LCS(i, j)를 x[1..i], y[1..j]의 최장 공통 부분 수열 길이로 정의한다.

z[1..k]를 LCS가 저장된 문자열이라 가정한다.

이때, LCS의 점화식은 편집 거리 점화식과 비슷한 방식으로 구해진다.

x와 y의 마지막 문자부터 서로 비교하여 LCS를 구할 때, 다음 세 가지 경우를 생각해 볼 수 있다.

1.     x[m] == y[n]인 경우

해당 문자를 LCS에 추가하고 x[1..n-1]과 y[1..m-1]의 LCS를 구한다.

LCS(n, m) = LCS(n-1, m-1) + 1,    z[k] == x[m] == y[n]

2.     x[m] != y[n], z[k] != y[n]인 경우

y[n]를 버리고 x[1..m]과 y[1..n-1]의 LCS를 구한다.

LCS(n, m) = LCS(m, n-1)

3.     x[m] != y[n], z[k] != x[m]인 경우

x[m]를 버리고 x[1..m-1]과 y[1..n]의 LCS를 구한다.

LCS(n, m) = LCS(m-1, n)

2, 3번의 경우, 더 큰 값을 LCS(i, j)에 저장하면 된다.

이를 일반화하여 점화식을 세우면 다음과 같다.

점화식이 편집 거리 식과 비슷하다. 단 change연산의 경우가 없고 min이 아니라 max를 구해야 한다.

편집 거리를 구할 때와 마찬가지로, 점화식을 이용해 아래와 같이 2차원 배열을 만들어 LCS를 구할 수 있다.

change연산의 경우가 없으므로 문자가 서로 같은 경우에만 대각선 방향 연산을 할 수 있다. 문자가 서로 같으면 대각선 방향 연산 비용 + 1을, 다르면 나머지 두 연산 중 max를 선택.