Smith-Waterman 국소 정렬 완전 이해 — 격자에서 음수를 0으로 자르는 결정 (한국어)

왜 이 편이 필요한가

M06에서 Needleman-Wunsch는 두 서열을 전체 대 전체로 정렬하는 방법이라고 했습니다. 그런데 실무에서는 그런 상황이 오히려 드뭅니다. 예를 들어 새로 찾은 유전자 하나(2,000bp)를 인간 게놈(3 × 10⁹ bp)과 비교할 때, 전체 대 전체 정렬은 무의미합니다. 우리가 원하는 건 "게놈의 어느 지점이 이 유전자와 매우 유사한가"입니다.

이럴 때 필요한 게 국소 정렬(local alignment) 입니다. Temple Smith와 Michael Waterman이 1981년에 낸 알고리즘이 그 답입니다. 놀랍게도 Needleman-Wunsch를 딱 두 줄만 바꿔서 만듭니다. 이 편에서 그 두 줄을 뜯어봅시다.

격자에서 음수를 0으로 자르는 순간

Needleman-Wunsch의 점화식이 이랬습니다.

F(i, j) = \max \begin{cases} F(i-1, j-1) + s(x_i, y_j) \\ F(i-1, j) - d \\ F(i, j-1) - d \end{cases}

Smith-Waterman의 점화식은 하나만 다릅니다.

H(i, j) = \max \begin{cases} 0 \\ H(i-1, j-1) + s(x_i, y_j) \\ H(i-1, j) - d \\ H(i, j-1) - d \end{cases}

0이 하나 추가됐습니다. 그리고 경계 조건이 이렇게 바뀝니다.

H(i, 0) = 0 (Needleman-Wunsch는 $-i \cdot d$ 였음)
H(0, j) = 0 (Needleman-Wunsch는 $-j \cdot d$ 였음)

이 두 변경이 알고리즘의 성격을 완전히 바꿉니다.

왜 0을 넣는가

Needleman-Wunsch에서 셀 값이 음수가 되면, 그 셀을 지나는 경로는 계속 감점된 상태로 진행됩니다. 그런데 실무에서는 두 서열이 대부분 무관하다가 어느 지점에서만 유사할 수 있습니다. 그런 부분 유사성을 찾으려면, 셀 값이 음수가 되는 순간 리셋해서 새로 시작할 여지를 주면 됩니다. 그게 max에 0을 추가한 의미입니다.

왜 경계 조건이 0인가

Needleman-Wunsch는 격자의 (0, 0)에서 시작해 (m, n)에서 끝나야 했습니다. 즉 두 서열의 시작과 끝을 강제로 맞췄습니다. Smith-Waterman은 어디서 시작해도 되고, 어디서 끝나도 됩니다. 그래서 첫 행과 첫 열이 모두 0입니다. 실제 정렬은 격자의 어느 임의의 지점에서 시작할 수 있습니다.

최적 정렬을 어떻게 찾는가

Needleman-Wunsch는 최적 정렬이 항상 (m, n)에 있었습니다. Smith-Waterman은 격자 전체에서 최댓값을 갖는 셀이 최적 정렬의 끝점입니다.

\text{best} = \max_{(i, j)} H(i, j)

그 셀에서 시작해서 traceback을 하면, 0에 도달하는 순간 멈춥니다. 왜냐하면 0에 도달했다는 건 그 이전부터가 유의미하지 않았다는 뜻이기 때문입니다.

손으로 채우기

X = AGCACACA, Y = ACACACTA, 매치 +2, 불일치 −1, 갭 −2로 격자를 채워봅시다. 짧게 자르면 X = AGCA, Y = ACAC.

	A	C	A	C
−	0	0	0	0
A	+2	0	+2	0
G	0	+1	0	+1
C	0	+2	0	+2
A	+2	0	+4	0

H(4,3) = 4가 격자 전체 최댓값입니다. 여기서 traceback하면 ACA 대 ACA (매치 3개)라는 국소 정렬이 나옵니다. 점수 6이 아닌 4인 이유는 격자 값이 셀 안의 반복 경로 최적화 결과이기 때문입니다.

Needleman-Wunsch의 격자와 비교해보면, 음수가 없다는 게 눈으로 보입니다. 무관한 영역에서 셀이 자동으로 0으로 리셋됩니다.

파이썬 완전 구현

python

def smith_waterman(x, y, match=2, mismatch=-1, gap=-2):
    m, n = len(x), len(y)
    H = [[0] * (n + 1) for _ in range(m + 1)]

    best_score = 0
    best_pos = (0, 0)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            s = match if x[i-1] == y[j-1] else mismatch
            H[i][j] = max(
                0,                       # 여기가 Needleman-Wunsch와 다름
                H[i-1][j-1] + s,
                H[i-1][j]   + gap,
                H[i][j-1]   + gap,
            )
            if H[i][j] > best_score:
                best_score = H[i][j]
                best_pos = (i, j)

    return best_score, best_pos, H

score, pos, table = smith_waterman("AGCACACA", "ACACACTA")
print(f"최적 국소 점수: {score}")  # 12
print(f"끝점: {pos}")

Needleman-Wunsch와 딱 한 줄(max의 첫 인자에 0 추가)만 다릅니다.

Rosalind로 채점받기

Rosalind LOCA에 들어가서 데이터셋을 다운로드하고, 위 코드에 traceback을 추가해 실제 정렬 서열을 출력해봅시다. 채점은 정렬 서열 자체를 확인합니다.

국소 정렬은 왜 BLAST로 이어지는가

Smith-Waterman은 정확한 알고리즘이지만 시간 O(mn)이라 인간 게놈에는 통째로 적용할 수 없습니다. 그래서 BLAST(M10) 같은 휴리스틱이 태어났습니다.

BLAST의 아이디어는 이렇습니다.

쿼리 서열에서 짧은 시드(seed) k-mer들을 뽑습니다.
각 시드를 참조 게놈의 인덱스에서 빠르게 찾습니다.
시드 주변만 Smith-Waterman으로 확장(extension)합니다.
통계적으로 유의한 정렬만 뱉습니다.

즉 BLAST는 Smith-Waterman의 축소판을 필요한 곳에만 적용하는 전략입니다. 근본은 이 편에서 다룬 국소 정렬입니다. M10 · M11 편에서 자세히 뜯어봅니다.

자주 만나는 실무 함정

매치 · 불일치 · 갭 점수의 균형: 매치 점수가 너무 낮거나 불일치/갭 벌점이 너무 낮으면 국소 정렬이 무의미하게 길어집니다. 실무에서는 서열 종류(DNA vs 단백질)와 예상 유사도에 따라 튜닝합니다. BLOSUM62(M09)가 단백질 국소 정렬의 표준 점수 행렬입니다.
여러 국소 정렬: 격자 전체 최댓값 하나만 뽑으면 놓치는 유사 영역이 있을 수 있습니다. 비겹침(non-overlapping) 상위 K개 정렬을 뽑는 확장이 실무에서 자주 필요합니다.
긴 참조 게놈: O(mn)이 곧 한계입니다. 3 × 10⁹ bp 인간 게놈과 100 bp 쿼리도 $3 \times 10^{11}$ 셀 → 하루가 걸립니다. 그래서 BLAST · BWA를 씁니다.
아핀 갭 페널티: 갭을 여는 것과 이어가는 것에 다른 벌점을 줘야 실제 진화적 이벤트와 맞습니다. M08에서 다룹니다.

CS 매핑

동적 계획법 (DP): Needleman-Wunsch와 같은 DP 골격입니다. 다만 최적 부분 구조의 정의가 미묘하게 다릅니다. "여기서 새로 시작할 수도 있다"는 옵션이 최적화 대상에 들어갑니다.
최대 부분 배열 (Kadane's algorithm): 1차원에서 "음수 누적을 0으로 리셋하는" 아이디어의 원형이 Kadane's algorithm입니다. Smith-Waterman은 그 2차원 판이라고 볼 수 있습니다.
분할과 정복 vs DP: 분할 정복은 문제를 반씩 자릅니다. DP는 문제를 격자 셀들의 관계로 재구성합니다. 두 접근이 만나는 자연스러운 지점이 서열 정렬입니다.

다음 편으로 이어지는 갈래

다음 편 (M08): 아핀 갭 페널티 + Hirschberg — 갭 벌점을 정교하게, 공간을 선형으로.
두 편 뒤 (M09): BLOSUM/PAM — 정렬 점수의 진화 확률적 정당화.
세 편 뒤 (M10): BLAST — Smith-Waterman을 게놈 스케일로 확장하는 휴리스틱.
네 편 뒤 (M11): BLAST E-value — 국소 정렬의 통계적 유의성.

더 깊게 파고 싶다면

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

MIT 7.91J — Christopher Burge 교수의 Local Alignment and BLAST 강의 (자막 완비, 자동 번역 95%+). Needleman-Wunsch → Smith-Waterman → BLAST의 흐름을 수학적으로 엄밀하게 다룹니다.
UCSD CSE 182 — Pavel Pevzner 교수의 Local Alignment: Smith-Waterman. 손 계산 예제가 풍부합니다.
원 논문: Smith, T. F. & Waterman, M. S. (1981), Identification of common molecular subsequences, J Mol Biol 147, 195–197. 두 페이지짜리 짧은 편지.
참고 교재: Compau & Pevzner Bioinformatics Algorithms. Rosalind와 연동된 무료 문제집.

Rosalind에서 LOCA · GAFF · MULT 등 정렬 관련 문제를 이어서 풀어봅시다. 다음 편 M08에서 만날 아핀 갭 페널티가 왜 필요한지 자연스럽게 이해됩니다. 손을 움직여야 합니다.

BioPlayground

DP 국소 정렬: Smith-Waterman과 격자에서 음수를 자르는 순간