정렬 거리

정렬 거리(영어: 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]

응용

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

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

관련 알고리즘

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

같이 보기

• 레벤슈타인 거리
• 편집 거리
• Smith-Waterman 알고리즘
• 동적 계획법
• 서열 정렬

참고 문헌

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