해밍 거리와 점 돌연변이 — 진화 거리 계산의 첫 수학 (한국어)

왜 이 편이 필요한가

두 서열이 얼마나 다른가? 이 질문은 바이오인포매틱스 전체를 관통합니다. 변이 검출은 리드와 참조의 차이를 세는 일이고, 계통수는 종 간 서열 차이로 진화 관계를 재구성하는 일이며, 약물 저항성 감시는 시간 순서상 앞뒤 서열의 차이를 추적하는 일입니다. 답은 결국 "얼마나 다른가"의 정의에 달려 있습니다.

가장 단순한 답이 해밍 거리(Hamming distance) 입니다. 이 편에서 우리는 해밍 거리를 정의하고, 파이썬 한 줄로 구현하고, 그것으로 실제 진화 거리를 재려고 시도해 봅시다. 그리고 왜 그것만으로는 부족한지 — 왜 Jukes-Cantor 같은 확률 모델이 필요한지 — 를 자연스럽게 만나 봅시다.

정의 — 같은 위치의 다른 문자

두 문자열 x와 y가 같은 길이일 때, 해밍 거리는 다음과 같습니다.

d_H(x, y) = |\{i : x_i \neq y_i\}|

즉 각 위치를 하나씩 비교해서, 다른 위치의 개수를 셉니다. 두 서열의 길이가 다르면 해밍 거리는 정의되지 않습니다(이 경우엔 편집 거리(edit distance) · 정렬(alignment)이 필요하고, M06 이후 편에서 다룹니다).

예시입니다.

text

x: GAGCCTACTAACGGGAT
y: CATCGTAATGACGGCCT
   * *   * ** *   *

* 위치가 서로 다른 곳입니다. 세어보면 7개입니다. d_H(x, y) = 7.

Rosalind HAMM 문제의 정확한 형식이 이것입니다. 두 DNA 문자열이 주어지고, 해밍 거리 하나만 뱉으면 됩니다.

파이썬 한 줄로 구현

python

def hamming_distance(x: str, y: str) -> int:
    assert len(x) == len(y), "해밍 거리는 같은 길이에서만 정의됩니다."
    return sum(a != b for a, b in zip(x, y))

# Rosalind HAMM 예시
x = "GAGCCTACTAACGGGAT"
y = "CATCGTAATGACGGCCT"
print(hamming_distance(x, y))  # 7

한 줄입니다. 이게 왜 이렇게 짧은가 하면, zip이 두 문자열의 위치를 짝지어주고, 제너레이터 표현식이 다름 여부를 True/False로 세기 때문입니다. True가 1로 취급되므로 sum이 곧 다름의 개수입니다.

그런데 이 수치가 정말 "다름"을 잘 대변하는가

여기서 잠깐 멈춰봅시다. 인간과 침팬지의 게놈 서열을 비교하면, 대략 위치의 1.2%가 다릅니다. 즉 해밍 거리 / 서열 길이 ≈ 0.012. 인간과 마우스는 대략 15% 다릅니다. 인간과 초파리는 대략 40% 다릅니다. 인간과 대장균은 …. 도중부터 무의미해집니다.

왜 무의미해지는가? 한 위치에서 여러 번 돌연변이가 일어날 수 있기 때문입니다. 예를 들어 A → G → A로 두 번 변했다면, 우리 눈에는 안 변한 것처럼 보입니다. 하지만 진화적으로는 두 개의 돌연변이가 축적된 상태입니다. 시간이 오래 지날수록 이런 "숨은 돌연변이"가 쌓여서, 해밍 거리는 진화 거리와의 관계가 비선형이 됩니다. 실제 서열 차이는 포화(saturation)에 가까워집니다.

Jukes-Cantor 보정 — 확률 모델의 첫 등장

Thomas Jukes와 Charles Cantor가 1969년에 낸 첫 확률 모델은 이렇게 시작합니다.

가정: 각 위치는 독립적으로 돌연변이 하고, 네 문자 사이 어떤 변화든 같은 확률입니다.

이 가정 하에서, 두 서열 사이에 시간 t가 흘렀다면 실제 돌연변이 발생 수(진화 거리 d)와 관측된 서로 다른 위치 비율 p 사이에 다음 관계가 성립합니다.

text

d = -\frac{3}{4} \ln \left( 1 - \frac{4}{3} p \right)
$$

`p`가 작을 때는 $d \approx p$입니다(로그 함수를 테일러 전개하면). 그런데 `p`가 3/4에 접근하면 `d`는 발산합니다. 이게 우리가 원했던 성질입니다. 관측된 차이는 3/4 이상 갈 수 없어도(네 글자 무작위 분포의 상한), 실제 진화 거리는 얼마든지 클 수 있어야 하니까요.

파이썬으로 옮겨보면 이렇습니다.
$$python
import math

def jukes_cantor_distance(hamming_frac: float) -> float:
    """관측 해밍 거리 비율(p)에서 진화 거리(d) 추정."""
    if hamming_frac >= 3/4:
        return math.inf
    return -0.75 * math.log(1 - (4/3) * hamming_frac)

# 인간-마우스 예시: p ≈ 0.15
p = 0.15
d = jukes_cantor_distance(p)
print(f"관측 p = {p:.3f}, 추정 진화 거리 d = {d:.3f}")
# 관측 p = 0.150, 추정 진화 거리 d = 0.168

관측 값 15%보다 실제 진화 거리는 16.8%로 조금 더 큽니다. 인간-마우스처럼 상대적으로 가까운 종 사이에서는 차이가 작지만, 관측 비율이 50%에 이르는 원거리 종 사이에서는 실제 진화 거리가 급격히 커집니다.

확률 모델은 여기서 끝나지 않습니다

Jukes-Cantor는 시작일 뿐입니다. 이후 편들에서 다음 모델들이 이어집니다.

Kimura 2-parameter (K2P): 전이(purine ↔ purine 또는 pyrimidine ↔ pyrimidine)와 전환(purine ↔ pyrimidine)의 확률을 구분합니다. 실제로 전이가 전환보다 몇 배 자주 일어납니다.
HKY85, GTR: 네 글자 각각의 정상 상태 빈도가 다르다는 것까지 반영합니다. 대부분의 현대 계통수 도구가 GTR을 씁니다.
아미노산 · 코돈 모델: 단백질 수준의 진화. 20종 아미노산 사이의 치환 확률을 BLOSUM · PAM 행렬로 관측합니다(M09에서 유도).

M09 BLOSUM · PAM의 정확한 뿌리가 여기입니다. 관측 치환 빈도 → 확률 모델 → 정렬 점수의 흐름입니다.

실습 — Rosalind HAMM

Rosalind HAMM에 들어가서 데이터셋을 다운로드하고, 위 hamming_distance 함수 한 줄로 풀어봅시다. 5분 안에 채점 통과입니다.

그다음 자신이 관심 있는 두 서열(예: 인간 BRCA1과 침팬지 BRCA1)을 NCBI에서 다운로드해 실제 해밍 거리와 Jukes-Cantor 보정을 계산해봅시다. 어떤 위치가 유의미하게 변했는지 관찰하는 것도 재미있습니다.

자주 만나는 실무 함정

길이가 다른 서열에 억지로 해밍 거리 적용: 갭이 하나만 있어도 그 이후 위치가 전부 어긋납니다. 길이가 다르면 정렬 후 편집 거리를 계산해야 합니다(M06 이후).
N 문자 취급: 신뢰도 없는 위치의 N을 다름으로 셀지 무시할지 정책을 정합시다. 관례적으로 무시(pairwise deletion)합니다.
원거리 종에 Jukes-Cantor 무비판 적용: 매우 먼 종 사이에서는 K2P/GTR 같은 더 세밀한 모델이 필요합니다. Jukes-Cantor는 첫 근사입니다.
저복잡성 영역: 반복 서열이나 저복잡성 영역은 해밍 거리를 왜곡합니다. 계통수 분석에서는 필터링(RepeatMasker 등)을 먼저 합니다.

CS 매핑

해밍 거리: 오류 정정 부호(Reed-Solomon, BCH)에서 나오는 그 해밍 거리입니다. 코드워드 사이 최소 해밍 거리가 정정 가능한 오류의 상한을 정합니다. Richard Hamming(1950)이 벨 연구소에서 원자력 계산기 오류를 잡기 위해 도입했습니다.
편집 거리 (Levenshtein): 삽입 · 삭제 · 치환을 허용한 일반화입니다. M06에서 정렬 문제로 확장됩니다.
정보 이론과 확률 모델: Jukes-Cantor의 로그 보정은 최대우도 추정(MLE) 의 첫 사례입니다. 관측된 확률에서 실제 확률 파라미터를 추정하는 도구가 이후 편들의 GATK · DESeq2 · phylogenetic ML까지 쭉 이어집니다.

다음 편으로 이어지는 갈래

다음 편 (M04): GC 비율과 종 판별 — 알파벳 네 글자의 정상 상태 빈도가 종을 얼마나 잘 구별하는가.
두 편 뒤 (M05): 역상보 서열 — 왜 반대 가닥의 서열을 계산해야 하는가.
세 편 뒤 (M06): Needleman-Wunsch — 길이가 다른 서열을 어떻게 정렬하는가.
여섯 편 뒤 (M09): BLOSUM/PAM — 관측 치환 빈도에서 정렬 점수를 유도합니다. Jukes-Cantor의 아미노산 판.
스물여섯 편 뒤 (M28): 최대우도 계통수 — 이 편의 확률 모델이 계통수 재구성으로 확장됩니다.

더 깊게 파고 싶다면

본문은 BPD가 자체 재구성한 서술입니다. 심화는 아래로.

Harvard STAT115 — Xiaole Shirley Liu 교수의 Week 2: Sequence Comparison Basics (자막 완비, 자동 번역 우수). 해밍 거리에서 편집 거리로의 이행을 부드럽게 설명합니다.
원 논문: Jukes, T. H. & Cantor, C. R. (1969), Evolution of Protein Molecules, in Mammalian Protein Metabolism. 확률 진화 모델의 시조 편.
원 논문: Hamming, R. W. (1950), Error detecting and error correcting codes, Bell System Technical Journal 29, 147–160. CS 원류.
참고 무료 웹북: Felsenstein, J. Inferring Phylogenies Chapter 11. 진화 확률 모델의 정통 서적.
StatQuest — Hamming Distance and Sequence Comparison (자막 자동 번역 우수). 시각적으로 직관을 잡을 수 있습니다.

Rosalind에서 HAMM · GC · REVC를 이어서 풀어봅시다. 그리고 자기가 아는 두 유전자의 실제 서열로 해밍 거리를 계산하고 Jukes-Cantor 보정 값을 관찰해봅시다. 다음 편 M04에서 만날 GC 비율이 왜 종을 구별하는지가 자연스레 이어집니다.

BioPlayground

해밍 거리와 점 돌연변이: 진화 거리의 수학은 여기서 시작합니다