정렬 거리
정렬 거리(영어: Alignment distance)는 두 문자열 또는 서열(sequence) 간의 정렬을 통해 측정되는 유사도 척도로, 두 서열을 최적으로 정렬했을 때 발생하는 불일치의 총 비용을 의미한다. 일반적으로 생물정보학에서 서열 정렬(sequence alignment)을 위한 거리 측정 지표로 사용된다.
개요
정렬 거리는 두 문자열이 얼마나 유사한지를 판단하기 위해 사용되는 거리 기반 지표로, 서열 정렬 과정에서 발생하는 삽입, 삭제, 치환 또는 갭(gap) 연산에 대한 비용의 총합으로 정의된다. 유전자, 단백질, RNA 서열 비교에서 자주 활용되며, 자연어 처리에서도 문장 간 유사도를 비교하는 데 쓰인다.
정렬 거리와 편집 거리의 개념은 유사하지만, 정렬 거리에서는 보통 갭(gap)에 대한 가중치나 패널티가 별도로 정의되며, 두 서열을 나란히 정렬하여 비교한다는 점에서 구체적인 적용 방식이 다를 수 있다.
정의
정렬 거리의 일반적인 구성 요소는 다음과 같다:
- 일치(match): 두 문자가 같을 경우 (일반적으로 0 비용)
- 불일치(mismatch): 두 문자가 다를 경우 (양의 비용)
- 갭(gap): 한 문자가 다른 서열에 대응하지 않고 비어 있는 경우 (갭 패널티 비용)
정렬 거리는 두 서열을 정렬한 후, 각 위치마다 위 항목 중 하나에 해당하는 비용을 합산하여 계산된다.
알고리즘
정렬 거리는 동적 계획법(Dynamic Programming)을 통해 계산되며, 대표적인 알고리즘은 Needleman-Wunsch 알고리즘(전역 정렬)과 Smith-Waterman 알고리즘(국소 정렬)이 있다.
Needleman-Wunsch 알고리즘
두 전체 서열을 정렬하는 전역 정렬 알고리즘이다. 점화식은 다음과 같다:
F(i, j) =
- F(i-1, j-1) + match/mismatch score
- F(i-1, j) + gap penalty
- F(i, j-1) + gap penalty
def needleman_wunsch(seq1, seq2, match=0, mismatch=1, gap=2):
m, n = len(seq1), len(seq2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i * gap
for j in range(n + 1):
dp[0][j] = j * gap
for i in range(1, m + 1):
for j in range(1, n + 1):
if seq1[i - 1] == seq2[j - 1]:
score = match
else:
score = mismatch
dp[i][j] = min(
dp[i - 1][j - 1] + score,
dp[i - 1][j] + gap,
dp[i][j - 1] + gap
)
return dp[m][n]
동적 계획법 시뮬레이션
문자열 X=infill, Y=final의 정렬 거리를 계산해보자. 비용은 아래와 같다.
- 일치(match): 보상 (예: -1)
- 불일치(mismatch): 벌점 (예: 1)
- 삽입/삭제(gap): 고정 비용 (예: 2)
우선 매트릭스는 아래와 같이 초기화된다.
- 여기서 0, 2, 4, ... 로 증가하는 것은 우선 아무것도 없는 것과 infill, final을 비교하는 것이다. 글자수만큼 삽입이 일어난다.
| i | n | f | i | l | l | ||
|---|---|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | |
| f | 2 | 1 | |||||
| i | 4 | ||||||
| n | 6 | ||||||
| a | 8 | ||||||
| l | 10 |
그 다음 f열부터 계산을 진행한다. 오른쪽으로 나아가며 비교를 하는 것은, "i", "in", "inf", "infi"와 같은 해당 인덱스까지의 문자열이다.
- "f"와 공백을 비교하면 삽입/또는 삭제가 일어나므로 2이다.
- "f"와 "i"를 비교하면, 불일치이기 때문에 1이다.
- "f"와 "in"를 비교한다. 3가지 경우로 비교를 해야 한다.
- "f*"와 "in": 앞서 이미 "f"와 "i"를 비교했으므로, 그 비용을 이용하고, "f"는 한 글자 밖에 없으니 "n"을 삽입한다.
- 즉 왼쪽 열을 이용할 수 있으며, 1+2 = 3이 된다.
- "in"과 "*f": "i"는 삽입하는 것으로 하고, "f"와 "n"을 치환한다.
- 즉 대각선 열을 이용할 수 있으며, 2+1 = 3이 된다.
- "in"과 "**": 그냥 f를 지워버리고 in을 삽입하는 것으로 한다.
- 즉 위쪽 열을 이용할 수 있으며, 4+2 = 6이 된다.
- 이렇게 3가지 비용을 비교해서 가장 작은 3을 넣는다.
- "f*"와 "in": 앞서 이미 "f"와 "i"를 비교했으므로, 그 비용을 이용하고, "f"는 한 글자 밖에 없으니 "n"을 삽입한다.
| i | n | f | i | l | l | ||
|---|---|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | |
| f | 2 | 1 | 3 | ||||
| i | 4 | ||||||
| n | 6 | ||||||
| a | 8 | ||||||
| l | 10 |
- "f"와 "inf"를 비교한다. 동일하게 3가지 경우로 비교를 해야 한다.
- 위쪽 열을 본다. 이는 f를 삭제하는 경우에 해당한다. "inf"가 공백, 즉 "***"과 비교되기 때문이다.
- 여기 "f"의 삭제비용까지 하면 8이다.
- 대각선 열을 본다. 이는 이전 비교 결과까진 그대로 두고, 마지막 글자끼리 비교하는 경우에 해당한다.
- 대각선은 "in"과 공백, 즉 "**"가 비교된 결과이다. 여기 "f"와 "f"의 정렬 비용을 더하는데, 같은 값이니 -1을 하면 3이 된다.
- 왼쪽 열을 본다. 이는 "inf"의 "f"를 삽입하는 경우에 해당한다.
- 왜냐하면 "in"과 "f"가 이미 비교가 되었으므로, "in"의 "f"는 그냥 삽입/삭제를 하는 것이다. 3+2 = 5가 된다.
- 즉 3가지를 비교하면 3이 가장 작으므로 3을 입력한다.
- 위쪽 열을 본다. 이는 f를 삭제하는 경우에 해당한다. "inf"가 공백, 즉 "***"과 비교되기 때문이다.
| i | n | f | i | l | l | ||
|---|---|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | |
| f | 2 | 1 | 3 | "3" | |||
| i | 4 | ||||||
| n | 6 | ||||||
| a | 8 | ||||||
| l | 10 |
- 이렇게, 각 칸에선 위, 대각선(↖), 왼쪽 열을 이용한 3가지 경우의 수 중 작은 것을 입력한다.
- 행에 해당하는 "X" 중 우리가 현재 선택한 것을 "x"라고 한다면,
- 위의 값을 이용하는 것은 x의 값을 "삭제"하는 경우에 해당하고,
- 대각선은 앞선 비교를 다 인정하고, "x"를 Y의 마지막 값과 비교하여 "치환(또는 일치)"하는 경우에 해당하고
- 왼쪽은 비교 대상 y를 "삽입"하는 경우에 해당한다.
- 즉 현재의 비용 기준을 고려하면, min(윗 값 + 2, 대각선 + 또는 - 1, 왼쪽 값 + 2)를 입력하는 단순한 반복이다.
| i | n | f | i | l | l | ||
|---|---|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | |
| f | 2 | 1 | 3 | 3 | 5 | 7 | 9 |
| i | 4 | ||||||
| n | 6 | ||||||
| a | 8 | ||||||
| l | 10 |
첫번째 열은 다 채웠다고 생각하고 다음 열의 3번째 로 넘어가보자. "fi"를 "infi"와 비교하고 있다.
- 일단 계산부터 하자면, 윗열 5+2, 대각선 열 3-1, 왼쪽 열 4+2를 비교해서 2가 들어가면 된다.
- 하지만 의미를 뒤짚어 보자면,
- 윗칸: "f와" infi"를 비교한 위치다. 즉, "f"와 "infi"를 비교한 걸 쓰고, 지금 "fi"의 "i"는 지워버리겠다는 거다.
- 대각선: "f"와 "inf"를 비교한 위치다. 즉 각각 앞글자까지의 비교값을 쓰고, "i"와 "i"를 비교하겠다는 거다. 같으므로 -1이 된다.
- 왼쪽칸: "fi"와 "inf"를 비교한 위치다. 즉 이 비교값을 쓰고, 뒤의 "infi"의 "i"를 삽입하겠다는 것이다.
| i | n | f | i | l | l | ||
|---|---|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | |
| f | 2 | 1 | 3 | 3 | 5 | 7 | 9 |
| i | 4 | 3 | 2 | 4 | "2" | ||
| n | 6 | ||||||
| a | 8 | ||||||
| l | 10 |
이렇게 매트리스를 다 채운다면 아래와 같이 된다. 정렬 비용은 매트리스에 이미 들어간 값이 업데이트 되는 경우는 없으므로, 최종 결과만 봐도 값이 나온 과정을 복기할 수 있다.
| i | n | f | i | l | l | ||
|---|---|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | |
| f | 2 | 1 | 3 | 3 | 5 | 7 | 9 |
| i | 4 | 1 | 2 | 4 | 2 | 4 | 6 |
| n | 6 | 3 | 0 | 2 | 4 | 3 | 5 |
| a | 8 | 5 | 2 | 1 | 3 | 5 | 4 |
| l | 10 | 7 | 6 | 3 | 2 | 2 | 4 |
정렬 비용은 가장 마지막에 위치한 "4"이다.
백트래킹
하지만 최종 매트릭스만 가지고 어떤 선택의 결과가 "4"인지 알기는 어렵다. 이를 위해선 우리가 구한 최종 값, 즉 마지막 행 마지막 열에 있는 "4"를 시작점으로 역추적(백트래킹)이 필요하다. 백트래킹 규칙은 아래와 같다:
| i | n | f | i | l | l | ||
|---|---|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | |
| f | 2 | 1 | 3 | 3 | 5 | 7 | 9 |
| i | 4 | 1 | 2 | 4 | 2 | 4 | 6 |
| n | 6 | 3 | 0 | 2 | 4 | 3 | 5 |
| a | 8 | 5 | 2 | 1 | 3 | 5 | 4 |
| l | 10 | 7 | 6 | 3 | 2 | 2 | 4 |
응용
정렬 거리는 다음과 같은 분야에서 활용된다:
- 유전자 및 단백질 서열 비교
- 생물학적 계통수 재구성
- 자연어 문장 비교 및 번역 평가
- OCR 인식 결과 평가
관련 알고리즘
- 편집 거리
- 레벤슈타인 거리
- Smith-Waterman 알고리즘
- BLAST (Basic Local Alignment Search Tool)
같이 보기
참고 문헌
- Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. *Journal of Molecular Biology*, 48(3), 443–453.
- Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998). *Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids*. Cambridge University Press.
