왜 이 편이 필요한가

M06 · M07에서 다룬 정렬은 갭 하나에 상수 벌점을 매겼습니다. -d가 갭 하나당 점수였습니다. 그런데 실제 진화 관점에서 보면 이건 부정확합니다. 유전자 안에 삽입이 하나 일어날 때, 삽입이 시작되는 사건과 삽입이 계속 이어지는 것은 확률이 완전히 다릅니다. 삽입 사건 하나가 30bp를 통째로 넣는 경우가 흔한 반면, 서로 떨어진 두 곳에 각각 15bp씩 삽입이 나란히 일어나는 경우는 훨씬 드뭅니다.

이걸 반영한 것이 아핀 갭 페널티(affine gap penalty) 입니다. 그리고 알고리즘의 공간 복잡도를 O(mn)에서 O(n)으로 줄이는 Hirschberg 알고리즘을 함께 봅니다. 두 아이디어가 오늘의 정렬 도구(EMBOSS needle, stretcher, minimap2 등)에 그대로 살아 있습니다.

아핀 갭 — 두 개의 다른 벌점

갭 길이 k에 대한 벌점을 다음처럼 정의합니다.

• a: 갭 개시 벌점 (gap opening penalty) — 갭이 시작될 때 한 번 부과
• b: 갭 연장 벌점 (gap extension penalty) — 갭이 하나 이어질 때마다 부과

예를 들어 a = 10, b = 1이면, 갭 길이 5의 벌점은 -(10 + 5) = -15입니다. 상수 벌점(예: $-2 \cdot 5 = -10$)보다 크지만, 길이 20의 벌점은 -(10 + 20) = -30으로 상수 벌점 -40보다 작습니다. 즉 긴 갭 하나가 짧은 갭 여러 개보다 저렴해집니다.

이게 진화적으로 왜 맞는가? 한 번의 삽입/삭제 사건이 여러 염기를 통째로 옮기는 것이 흔한 반면, 여러 곳에서 각각 짧은 삽입이 나란히 일어날 확률은 낮기 때문입니다.

3-상태 DP — 아핀 갭을 어떻게 격자에 담나

Needleman-Wunsch의 격자 하나로는 아핀 갭을 표현하기 어렵습니다. "이 셀이 갭 안에 있는가, 갭이 방금 시작됐는가"를 추적해야 하기 때문입니다.

해법은 격자를 세 개 만들기입니다.

• M(i, j): 위치 (i, j)에서 매치/불일치로 도달한 최적 점수
• I_x(i, j): 위치 (i, j)에서 X에 갭이 열려 있는 상태의 최적 점수
• I_y(i, j): 위치 (i, j)에서 Y에 갭이 열려 있는 상태의 최적 점수

세 격자가 서로 참조하며 함께 채워집니다.

세 격자 각각 O(mn) 시간이니 총 시간은 여전히 O(mn)입니다. 공간은 3배가 되지만 상수배이므로 여전히 O(mn)입니다.

파이썬 구현

def affine_alignment(x, y, match=1, mismatch=-1, a=2, b=1):
    NEG_INF = float("-inf")
    m, n = len(x), len(y)
    M  = [[NEG_INF] * (n + 1) for _ in range(m + 1)]
    Ix = [[NEG_INF] * (n + 1) for _ in range(m + 1)]
    Iy = [[NEG_INF] * (n + 1) for _ in range(m + 1)]

    M[0][0] = 0
    for i in range(1, m + 1):
        Ix[i][0] = -a - b * i
    for j in range(1, n + 1):
        Iy[0][j] = -a - b * j

    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
            M[i][j] = max(
                M[i-1][j-1]  + s,
                Ix[i-1][j-1] + s,
                Iy[i-1][j-1] + s,
            )
            Ix[i][j] = max(
                M[i-1][j] - a - b,
                Ix[i-1][j] - b,
            )
            Iy[i][j] = max(
                M[i][j-1] - a - b,
                Iy[i][j-1] - b,
            )

    return max(M[m][n], Ix[m][n], Iy[m][n])

Rosalind GAFF 문제를 이 함수로 풀 수 있습니다. Traceback을 붙이면 실제 정렬도 뽑을 수 있습니다.

Hirschberg — 공간을 O(n)으로 줄이는 절묘한 트릭

여기서 잠깐 다른 방향의 문제로 넘어갑시다. 지금까지의 알고리즘은 격자 전체 O(mn)을 저장했습니다. 인간 게놈 크기의 서열에는 $3 \times 10^9 \times 3 \times 10^9 = 9 \times 10^{18}$ 바이트가 필요합니다. 완전히 무리입니다.

Daniel Hirschberg가 1975년에 낸 아이디어는 이렇습니다. 점수를 계산하려면 격자 한 줄만 있으면 됩니다. 각 행을 계산할 때 바로 이전 행 값만 참조하니, 오래된 행은 버려도 됩니다. 그러면 공간은 O(n)입니다.

문제는 정렬을 실제로 뽑으려면 전체 격자가 필요하다는 것이었습니다. Hirschberg는 이 문제를 분할 정복으로 뚫었습니다.

Hirschberg 아이디어

1. 서열 X를 반으로 자릅니다: X = X_1 X_2.
2. 정방향 점수 계산: X_1 대 Y의 모든 부분 정렬 점수를 마지막 행만 저장하며 계산. $O(m/2 \cdot n)$ 시간, O(n) 공간.
3. 역방향 점수 계산: X_2의 역상보 대 Y의 역상보의 모든 부분 정렬 점수도 마지막 행만 저장하며 계산. $O(m/2 \cdot n)$ 시간, O(n) 공간.
4. 결합: 위 두 결과의 합이 최댓값이 되는 Y의 지점 j^*을 찾습니다. 이 j^*가 최적 정렬에서 X_1과 X_2가 갈리는 정확한 지점입니다.
5. 재귀: X_1 대 Y[0:j^*], X_2 대 Y[j^*:n]에 대해 같은 절차를 재귀적으로 반복.

시간은 $O(mn) + O(mn/2) + O(mn/4) + \cdots = O(mn)$ (총합은 여전히 O(mn)이지만 상수배가 2배로 늘어납니다). 공간은 O(n)입니다.

왜 이게 동작하는가

핵심 통찰은 최적 정렬은 반드시 Y의 어느 한 지점에서 X_1과 X_2의 경계를 통과한다는 것입니다. 그 지점만 알면 문제가 두 개의 작은 문제로 쪼개집니다. 각각의 작은 문제는 다시 같은 트릭으로 쪼갤 수 있습니다.

실무에서 아핀 갭과 Hirschberg가 살아 있는 곳

• EMBOSS needle: 아핀 갭 페널티가 기본. -gapopen, -gapextend 옵션이 그것입니다.
• BLAST: 갭이 있는 정렬(gapped BLAST)에서 아핀 갭을 사용합니다.
• minimap2 (M16): 롱리드의 큰 인델을 다루기 위해 아핀 갭 페널티를 확장한 아핀 이중선(affine two-piece) 페널티를 사용합니다.
• BWA-SW: BWA의 확장 정렬 단계에서 Hirschberg의 선형 공간 정렬 아이디어를 씁니다.

자주 만나는 실무 함정

• 갭 파라미터 튜닝: a와 b의 상대적 크기가 결과를 크게 바꿉니다. 단백질 정렬은 관례적으로 a = 10, b = 1 (BLOSUM62 사용 시). DNA 정렬은 서열 유형에 따라 다양합니다.
• 아핀과 상수의 차이 실감: 짧은 서열 정렬에서는 두 페널티의 차이가 미미할 수 있습니다. 100bp 이상 · 진화적으로 먼 서열에서 차이가 극명해집니다.
• Hirschberg의 상수배 오버헤드: 이론상 시간은 같지만, 실제로는 2배 정도 느립니다. 공간이 진짜 병목일 때만 씁니다. 짧은 서열에는 오히려 손해입니다.
• 다중 정렬로의 확장: 아핀 갭은 다중 서열 정렬(MSA, M25)에서 매우 중요합니다. 원거리 종을 정렬할 때 아핀 갭이 없으면 오답이 나옵니다.

CS 매핑

• 다중 상태 DP: 아핀 갭은 상태 공간을 하나에서 세 개로 확장한 것입니다. 이 아이디어는 자동차 경로 최적화 · 게임 AI · 시계열 예측 등 다양한 CS 문제에서 반복됩니다.
• 분할 정복 + DP: Hirschberg는 분할 정복과 DP를 결합한 첫 사례 중 하나입니다. CLRS 교과서의 정렬 알고리즘 장에도 소개돼 있습니다.
• 공간-시간 트레이드오프: 시간을 조금 더 쓰고 공간을 크게 줄이는 이 트레이드오프는 CS의 핵심 원리 중 하나입니다. 압축 · 캐시 설계 · 데이터베이스 인덱싱 모두 같은 원리가 작동합니다.

다음 편으로 이어지는 갈래

• 다음 편 (M09): BLOSUM/PAM — 정렬 점수의 진화 확률적 정당화. 아핀 갭의 파라미터 튜닝 근거.
• 두 편 뒤 (M10): BLAST — 아핀 갭이 들어간 gapped BLAST.
• 여섯 편 뒤 (M14 · M15): BWT · FM-index — 정렬을 게놈 스케일로 확장.
• 여덟 편 뒤 (M16): minimap2 — 아핀 이중선 페널티의 실무 응용.

더 깊게 파고 싶다면

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

• UC Berkeley CS176 — Yun Song 교수의 Sequence Alignment with Affine Gap Penalties (자막 완비). 3-상태 DP 유도를 상세히 다룹니다.
• 원 논문: Hirschberg, D. S. (1975), A linear space algorithm for computing maximal common subsequences, Comm ACM 18, 341–343. CS 정통.
• 원 논문: Gotoh, O. (1982), An improved algorithm for matching biological sequences, J Mol Biol 162, 705–708. 아핀 갭 3-상태 DP의 원류.
• 참고 교재: Durbin et al. Biological Sequence Analysis Chapter 2. 서열 정렬의 정통 교과서.
• 참고 도구: Biopython (Bio.pairwise2.align.globalds) — 실무에서는 이 함수 한 번이면 됩니다. 지금은 원리 이해를 위해 손으로 짜본 것.

Rosalind에서 GAFF · MULT · GCON 문제를 풀어봅시다. 다음 편 M09의 BLOSUM/PAM이 왜 특정 숫자로 이루어져 있는지 이해할 수 있게 됩니다.