정렬 거리

IT 위키

정렬 거리(영어: Alignment distance)는 두 문자열 또는 서열(sequence) 간의 정렬을 통해 측정되는 유사도 척도로, 두 서열을 최적으로 정렬했을 때 발생하는 불일치의 총 비용을 의미한다. 일반적으로 생물정보학에서 서열 정렬(sequence alignment)을 위한 거리 측정 지표로 사용된다.

1 개요[편집 | 원본 편집]

정렬 거리는 두 문자열이 얼마나 유사한지를 판단하기 위해 사용되는 거리 기반 지표로, 서열 정렬 과정에서 발생하는 삽입, 삭제, 치환 또는 갭(gap) 연산에 대한 비용의 총합으로 정의된다. 유전자, 단백질, RNA 서열 비교에서 자주 활용되며, 자연어 처리에서도 문장 간 유사도를 비교하는 데 쓰인다.

정렬 거리와 편집 거리의 개념은 유사하지만, 정렬 거리에서는 보통 갭(gap)에 대한 가중치나 패널티가 별도로 정의되며, 두 서열을 나란히 정렬하여 비교한다는 점에서 구체적인 적용 방식이 다를 수 있다.

2 정의[편집 | 원본 편집]

정렬 거리의 일반적인 구성 요소는 다음과 같다:

  • 일치(match): 두 문자가 같을 경우 (일반적으로 0 비용)
  • 불일치(mismatch): 두 문자가 다를 경우 (양의 비용)
  • 갭(gap): 한 문자가 다른 서열에 대응하지 않고 비어 있는 경우 (갭 패널티 비용)

정렬 거리는 두 서열을 정렬한 후, 각 위치마다 위 항목 중 하나에 해당하는 비용을 합산하여 계산된다.

3 알고리즘[편집 | 원본 편집]

정렬 거리는 동적 계획법(Dynamic Programming)을 통해 계산되며, 대표적인 알고리즘은 Needleman-Wunsch 알고리즘(전역 정렬)과 Smith-Waterman 알고리즘(국소 정렬)이 있다.

3.1 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]

3.2 동적 계획법 시뮬레이션[편집 | 원본 편집]

이 시뮬레이션은 동적 계획법 구성이 이해가 어려운 사람들을 위해, 이해를 돕기 위한 풀이이므로, 이해가 되는 사람은 그냥 위의 소스코드를 본느 것이 훨씬 간편하다.

문자열 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을 넣는다.
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을 입력한다.
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"이다.

3.3 백트래킹[편집 | 원본 편집]

하지만 최종 매트릭스만 가지고 어떤 선택의 결과가 "4"인지 알기는 어렵다. 이를 위해선 우리가 구한 최종 값, 즉 마지막 행 마지막 열에 있는 "4"를 시작점으로 역추적(백트래킹)이 필요하다. 백트래킹 규칙은 아래와 같다:

  1. 마지막 값이었던 "4"를 만들게 된 그 칸으로 따라간다.
  2. 예를 들어 대각선에서 1이 더해지거나 빼진 것이 "4"인지, 위 또는 왼쪽에서 2가 더해진 것이 "4"인지 파악한다.
    • 만약 두 값이 같다면 이 둘 다 답이다.
  3. 이렇게 해당되는 것을 표시하며 올라가다 보면 첫 칸에 닿게 된다. 이 때 표시된 지점들이 답이 될 수 있는 지점이다.
    • 2번에서 설명했듯이 값이 둘다 해당사항이 있다면 그건 여러 갈레로 갈라지는 것이다. 이 각 갈레들을 추적하면 여러개의 답을 모두 구할 수 있다.

먼저 하나의 경로만 추적해보자.

  • 아래는 대각선으로 갈 수 있으면 대각선으로 가고, 대각선으로 갈 수 없는 경우엔 왼쪽으로 가고, 왼쪽으로도 갈 수 없으면 위쪽으로 가는 규칙으로 만들어진 경로이다.
  • dp[6][7]의 (4)는 대각선 위에 있는 dp[5][6]의 = (5)에서 1이 빼진 값이다. 물론 왼쪽 dp[6][6]의 (2)에서 2가 더해진 값일 수도 있지만 여기선 해당 경로는 잠시 제쳐두겠다.
  • 그 다음 dp[5][6]의 (5)는 dp[4][5]의 (4)에서 1이 더해진 값이다.
  • 그 다음 dp[4][5]의 (4)는 dp[3][4]의 (4)에서 온 값이 아니다. 대각선을 기반으로 하려면 1이 더해지거나 빼져야 하는데 값이 같기 때문이다. 왼쪽 dp[3][3]의 (2)에서 2가 더해진 값일 수 있다.

이렇게 추적해나가다 보면 하나의 길이 그려진다. 이 과정에서 보았듯 여러 갈레의 길이 있었다. 각각의 다른 갈레가 나올 때 마다 다른 답이 나오는 것이다. 우선 이 경로를 어떻게 해석하는지 살펴보자. 첫번째 (0)은 제외하고 글자가 있는 칸부터 순서대로 선택해서 대응되는 글자들을 적어준다.

  • f - * (행엔 f가 있는데 열엔 값이 없다. 아래위 방향이므로 f가 삽입된 경우이다.)
  • i - i (동일한 값이 매칭된 경우이다.)
  • n - n (동일한 값이 매칭된 경우이다.)
  • * - f (좌우 방향이므로 f가 삭제된 경우이다.)
  • * - i (좌우 방향이므로 i가 삭제된 경우이다.)
  • a - l (대각선 방향으므로 치환된 경우이다.)
  • l - l (대각선 방향이므로 치환된 경우이다.

결국 아래와 같다. 

*  i  n  f  i  l  l 
f  i  n  *  *  a  l
2 -1 -1  2  2  1 -1 = 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)

4 응용[편집 | 원본 편집]

정렬 거리는 다음과 같은 분야에서 활용된다:

  • 유전자 및 단백질 서열 비교
  • 생물학적 계통수 재구성
  • 자연어 문장 비교 및 번역 평가
  • OCR 인식 결과 평가

5 관련 알고리즘[편집 | 원본 편집]

  • 편집 거리
  • 레벤슈타인 거리
  • Smith-Waterman 알고리즘
  • BLAST (Basic Local Alignment Search Tool)

6 같이 보기[편집 | 원본 편집]

7 참고 문헌[편집 | 원본 편집]

  • 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.

8 각주[편집 | 원본 편집]

원본 주소 "https://itwiki.kr/index.php?title=정렬_거리&oldid=40899"