왜 이 편이 필요한가

Burrows-Wheeler Transform(BWT)은 1994년에 David Wheeler와 Michael Burrows가 데이터 압축을 위해 발명했습니다. 초기 응용은 bzip2 압축 프로그램이었습니다. 서열 검색과는 무관해 보였습니다.

그런데 2000년대 후반, BWT가 게놈 정렬의 판을 뒤집습니다. BWA (2009) 와 Bowtie (2009) 가 BWT 기반 FM-index를 사용해 짧은 리드를 인간 게놈에 초당 수십만 개씩 정렬하는 성능을 보였습니다. 오늘 우리가 쓰는 거의 모든 짧은 리드 정렬 파이프라인이 이 자료구조 위에 서 있습니다.

이 편에서 BWT의 원리 — 회전 정렬과 역변환 — 를 손 계산으로 유도합시다. 다음 편(M15)의 FM-index가 자연스럽게 이어집니다.

1단계 — 회전과 정렬

문자열 `T = BANANA``를 시작합시다. ```는 끝 표시(원본에 없는 특수 문자).

모든 회전을 만듭니다. 왼쪽 끝 문자를 오른쪽 끝으로 옮기는 것을 반복합니다.

BANANA$
ANANA$B
NANA$BA
ANA$BAN
NA$BANA
A$BANAN
$BANANA

사전순으로 정렬합니다.

$BANANA
A$BANAN
ANA$BAN
ANANA$B
BANANA$
NA$BANA
NANA$BA

이 정렬된 회전들의 마지막 열을 뽑아 붙인 것이 BWT입니다.

$BANANA → A
A$BANAN → N
ANA$BAN → N
ANANA$B → B
BANANA` → `
NA$BANA → A
NANA$BA → A

BWT(T) = "ANNB$AA"

왜 이게 압축에 좋은가

ANNBAA를 보면, 같은 문자가 연속으로 나타나는 경향이 있습니다. NN, AA. 원본 BANANA``보다 뭉쳐 있습니다.

이건 우연이 아닙니다. 정렬된 회전의 마지막 열은 반복 문자가 뭉쳐 나오는 경향이 있습니다. 왜냐하면 접미사 배열이 사전순으로 정렬되면, 같은 접두사를 가진 접미사들이 뭉쳐 있고, 그들의 바로 앞 문자(즉 마지막 열)도 자주 같기 때문입니다.

문자가 뭉쳐 있으면 Move-to-Front + Huffman · Arithmetic Coding으로 압축이 훨씬 잘 됩니다. 이게 bzip2의 원리입니다.

놀라운 성질 — BWT는 가역입니다

이게 자료구조로서 BWT의 진짜 마술입니다. BWT만으로 원본 문자열을 완전히 복원할 수 있습니다.

역변환 절차:

1. BWT의 각 문자를 사전순으로 정렬한 것이 정렬된 회전들의 첫 열입니다. AABNNAA → 사전순 → ``AAABNN (첫 열).
2. 각 문자에 "이 위치가 몇 번째 반복인가"를 태깅해서, 같은 문자를 구별합니다.
3. LF-mapping: 마지막 열의 i번째 문자와 첫 열의 i번째 문자는 원본 문자열에서 인접합니다(하나가 다른 것을 앞선다).
4. LF-mapping을 반복하면 원본 문자열을 뽑을 수 있습니다.

파이썬으로 옮기면 이렇습니다.

def bwt(text: str) -> str:
    text = text + "$"
    n = len(text)
    rotations = [text[i:] + text[:i] for i in range(n)]
    rotations.sort()
    return "".join(row[-1] for row in rotations)

def inverse_bwt(bwt_str: str) -> str:
    n = len(bwt_str)
    # 각 문자에 반복 번호 태깅
    last = list(bwt_str)
    first = sorted(bwt_str)

    # LF-mapping 만들기
    # 각 문자에 이 문자가 첫 열에서 몇 번째로 나타나는가
    from collections import defaultdict
    count = defaultdict(int)
    last_tagged = []
    for c in last:
        last_tagged.append((c, count[c]))
        count[c] += 1

    count = defaultdict(int)
    first_tagged = []
    for c in first:
        first_tagged.append((c, count[c]))
        count[c] += 1

    # 원본 문자열 재구성
    lf_map = {c: i for i, c in enumerate(last_tagged)}
    result = []
    i = last_tagged.index(("$", 0))
    for _ in range(n):
        result.append(first_tagged[i][0])
        i = lf_map[first_tagged[i]]
    return "".join(result).rstrip("$")

# 사용
original = "BANANA"
transformed = bwt(original)
print(f"BWT: {transformed}")  # ANNB$AA
recovered = inverse_bwt(transformed)
print(f"복원: {recovered}")  # BANANA

이 역변환이 가능한 이유는 정렬된 회전의 첫 열과 마지막 열이 원본에서 인접하기 때문입니다. 좀 더 정확히는, 마지막 열의 문자 뒤에 오는 것이 첫 열의 같은 위치 문자입니다.

LF-mapping의 우아함

LF-mapping은 이 편의 핵심 개념입니다. Last-to-First mapping의 줄임말입니다.

정의: 마지막 열의 i번째 위치에 있는 문자와 첫 열의 어느 위치에 있는 같은 문자가 원본에서 같은 자리인가?

답: 마지막 열의 i번째 문자 c가 마지막 열에서 j번째 반복 c라면, 첫 열에서도 j번째 반복 c가 원본의 같은 자리입니다.

이 아름다운 성질 하나로 원본 복원이 가능하고, 더 나아가 다음 편의 FM-index에서 임의 패턴을 초고속으로 찾을 수 있습니다.

접미사 배열과의 관계

BWT는 사실 접미사 배열의 변형된 표현입니다.

• 접미사 배열 SA: 정렬된 접미사의 시작 위치.
• BWT: 각 정렬된 접미사의 바로 앞 문자.

수식으로는 이렇습니다.

BWT[i] = T[SA[i] - 1] \quad \text{(SA[i] = 0이면 } T[n-1] \text{)}

즉 BWT는 접미사 배열의 각 시작 위치의 바로 이전 문자를 뽑아 놓은 것입니다.

Rosalind로 실습

Rosalind BWT에서 BWT를 계산하는 문제를 풀 수 있습니다. 위의 bwt 함수 한 줄이면 됩니다.

자주 만나는 실무 함정

• 끝 표시 문자의 필수성: $가 없으면 정렬된 회전 중에 원본을 구별할 방법이 없어져 역변환이 실패합니다. 반드시 원본에 없는 특수 문자 사용.
• 문자 집합 크기: 알파벳이 큰 문자열(예: 유니코드)은 LF-mapping의 크기가 커집니다. DNA(4～5글자)에는 매우 효율적.
• 회전 정렬의 실제 구현: 위의 파이썬 코드는 교육용이라 $O(n^2 \log n)$입니다. 실제 BWA는 접미사 배열을 SA-IS로 O(n)에 만든 후 BWT를 O(n)에 유도합니다.
• 디스크 저장: 인간 게놈 BWT는 대략 3GB (원본과 같은 크기). BWA는 이걸 압축해 디스크에 두고 mmap으로 사용합니다.

CS 매핑

• 회전 정렬(rotation sorting): 압축과 검색이 겹치는 지점의 정통 예시입니다.
• Move-to-Front · Huffman · Arithmetic Coding: bzip2의 압축 파이프라인이 BWT → MTF → Huffman → 결과.
• LF-mapping: 자료구조 이론의 우아한 항등식입니다. 이 성질이 없으면 BWT는 그저 압축 변환일 뿐입니다.
• 압축과 인덱싱의 이중성: 압축이 잘 되는 형태가 검색에도 좋다는 관찰은 정보 이론의 근본 원리와 얽혀 있습니다.

다음 편으로 이어지는 갈래

• 다음 편 (M15): FM-index — BWT + Rank/Select로 완성되는 초고속 매핑 자료구조.
• 두 편 뒤 (M16): minimap2 · 미니마이저 — 롱리드 시대의 인덱스.
• 아홉 편 뒤 (S03): BWA-MEM 실무 — 지금 만든 자료구조의 실제 응용.
• 열여섯 편 뒤 (S22 · S23): 어셈블리 — BWT가 조립에도 응용됩니다.

더 깊게 파고 싶다면

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

• MIT 7.91J — David Gifford 교수의 BWT and Read Mapping 강의 (자막 완비, 자동 번역 우수). BWT의 자료구조와 압축 응용을 함께 다룹니다.
• CMU 02-510 — Ben Langmead 교수(Bowtie 저자)의 Data Structures for Genome Indexing (자막 완비, 자동 번역 우수). BWT · FM-index를 매우 명확하게 설명합니다.
• 원 논문: Burrows, M. & Wheeler, D. (1994), A block-sorting lossless data compression algorithm, Digital Systems Research Center Technical Report 124. BWT의 시조.
• 원 논문: Ferragina, P. & Manzini, G. (2000), Opportunistic data structures with applications, FOCS. FM-index의 시조.
• 참고 도구: bzip2 소스코드. BWT의 압축 응용을 실제 구현으로.

Rosalind에서 BWT · SUFF 문제를 풀어봅시다. 다음 편 M15의 FM-index가 왜 BWT의 자연스러운 확장인지 이해됩니다.