왜 이 편이 필요한가

M10 · M11의 BLAST는 해시 기반 k-mer 인덱스를 썼습니다. 빠르지만 두 가지 한계가 있습니다.

1. k가 고정: 인덱스를 만들 때 k를 정해야 합니다. 다른 k를 원하면 다시 만들어야 합니다.
2. 부분 매치 처리가 어색: 정확한 매치는 잘 찾지만, 접미사 · 접두사의 다양한 조합 검색이 자연스럽지 않습니다.

접미사 트리(suffix tree) 와 접미사 배열(suffix array) 은 이 한계를 뚫습니다. 임의 길이의 패턴을 O(m) 시간(m = 패턴 길이)에 찾을 수 있습니다. 참조 게놈의 크기와 무관합니다. 이 편에서 우리는 두 자료구조의 원리와 차이를 다룹니다. 이 편이 정착되면 M14～M15의 BWT · FM-index가 자연스럽게 이어집니다.

접미사(Suffix)란 무엇인가

문자열 `T = BANANA``의 모든 접미사입니다(```는 끝 표시).

0: BANANA$
1: ANANA$
2: NANA$
3: ANA$
4: NA$
5: A$
6: $

총 7개(길이 + 1개). 각 접미사가 문자열의 어느 위치에서 시작하는지 표시했습니다.

접미사 트리 — 모든 접미사를 트리에 삽입

접미사 트리는 위 접미사들을 하나의 트리로 묶어 저장한 자료구조입니다. 각 경로가 하나의 접미사에 해당합니다.

BANANA$
       /
      /       A
[root]--- NA$
      \    NANA$
       \
        $

핵심 성질:

• 리프 개수 = 접미사 개수 = 문자열 길이 + 1
• 각 리프에 원래 문자열에서의 시작 위치가 저장됨
• 두 접미사의 공통 접두사가 같은 경로를 공유

이 구조 덕분에 다음이 가능합니다.

• 패턴 P가 T에 존재하는가: P를 트리 뿌리부터 따라 내려가면 O(m) 시간.
• P가 몇 번 등장하는가: 도달한 노드 아래 리프 개수를 세면 됨.
• 가장 긴 반복 부분 서열: 두 리프의 최소 공통 조상(LCA) 문제로 환원됨.
• 두 문자열의 공통 부분 서열: 두 개의 접미사 트리 결합.

Ukkonen 알고리즘 — O(n) 시간에 트리 만들기

접미사 트리 구축을 순진하게 하면 O(n^2)이지만, Esko Ukkonen이 1995년에 O(n) 선형 시간 알고리즘을 발표했습니다. 원리는 접미사 링크(suffix link)라는 트릭입니다. 세부는 복잡하므로 여기서는 개념만 남깁니다.

• 접미사를 하나씩 트리에 추가.
• 이미 있는 접미사와 겹치는 부분을 재활용.
• 접미사 링크로 다음 삽입 위치로 점프.

세부는 Dan Gusfield의 Algorithms on Strings, Trees, and Sequences (1997) Chapter 6에 정통적으로 정리돼 있습니다.

파이썬으로 (단순화된) 접미사 트리 구현

교육용으로 순진한 O(n^2) 구현을 봅시다.

class SuffixTreeNode:
    def __init__(self):
        self.children = {}
        self.suffix_indices = []

class SuffixTree:
    def __init__(self, text: str):
        self.text = text + "$"
        self.root = SuffixTreeNode()
        for i in range(len(self.text)):
            self._insert(self.text[i:], i)

    def _insert(self, suffix: str, index: int):
        node = self.root
        for c in suffix:
            if c not in node.children:
                node.children[c] = SuffixTreeNode()
            node = node.children[c]
        node.suffix_indices.append(index)

    def search(self, pattern: str) -> list[int]:
        node = self.root
        for c in pattern:
            if c not in node.children:
                return []
            node = node.children[c]
        # 이 노드 아래의 모든 리프의 인덱스 수집
        result = []
        self._collect_indices(node, result)
        return sorted(result)

    def _collect_indices(self, node, result):
        result.extend(node.suffix_indices)
        for child in node.children.values():
            self._collect_indices(child, result)

# 사용
tree = SuffixTree("BANANA")
print(tree.search("ANA"))  # [1, 3]

ANA가 BANANA에 위치 1과 3에서 나타난다는 것을 O(m) 시간에 찾습니다.

접미사 배열 — 접미사 트리의 압축 버전

접미사 트리는 강력하지만 메모리 사용이 크다는 단점이 있습니다. 대략 20n 바이트(문자당 20바이트). 인간 게놈이라면 60GB.

접미사 배열은 훨씬 작습니다. 각 접미사의 시작 위치를 사전순으로 정렬한 정수 배열입니다. 인간 게놈이라면 대략 4n 바이트, 즉 12GB.

BANANA$의 접미사 배열:

접미사 시작 위치를 사전순으로 정렬:
$        → 6
A$       → 5
ANA$     → 3
ANANA$   → 1
BANANA$  → 0
NA$      → 4
NANA$    → 2

접미사 배열: SA = [6, 5, 3, 1, 0, 4, 2]

파이썬으로 만드는 방법은 놀랍도록 간단합니다.

def suffix_array(text: str) -> list[int]:
    text = text + "$"
    n = len(text)
    return sorted(range(n), key=lambda i: text[i:])

# 사용
sa = suffix_array("BANANA")
print(sa)  # [6, 5, 3, 1, 0, 4, 2]

이 간단한 정렬 기반 구현은 $O(n^2 \log n)$ 시간입니다. 실제 도구는 SA-IS · DC3 같은 O(n) 시간 알고리즘을 씁니다.

접미사 배열로 검색하기

접미사 배열은 정렬돼 있으므로 이진 탐색으로 패턴을 찾을 수 있습니다.

def sa_search(text: str, sa: list[int], pattern: str) -> list[int]:
    text_with_end = text + "$"
    n = len(text_with_end)
    m = len(pattern)

    # 이진 탐색으로 첫 매치 찾기
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if text_with_end[sa[mid]:sa[mid]+m] < pattern:
            lo = mid + 1
        else:
            hi = mid
    left = lo

    # 이진 탐색으로 마지막 매치 찾기
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if text_with_end[sa[mid]:sa[mid]+m] <= pattern:
            lo = mid + 1
        else:
            hi = mid
    right = lo

    return sorted(sa[left:right])

# 사용
text = "BANANA"
sa = suffix_array(text)
print(sa_search(text, sa, "ANA"))  # [1, 3]

시간 복잡도는 $O(m \log n)$입니다. 트리보다 조금 느리지만 메모리가 훨씬 작습니다.

접미사 트리 vs 접미사 배열 트레이드오프

실무에서는 대개 접미사 배열이 이깁니다. 메모리 이득이 검색 속도의 소폭 손실을 이깁니다.

Rosalind로 실습

Rosalind SUFF에서 접미사 배열을 만들어보는 문제를 풀 수 있습니다. 파이썬 3～5줄이면 됩니다.

자주 만나는 실무 함정

• **끝 표시 문자 **: 반드시 원본에 없는 특수 문자를 씁니다. 대개 또는 \0. 없으면 접미사 트리가 부분적으로 붕괴합니다.
• 긴 반복 서열: 반복 서열이 많은 게놈은 트리 · 배열의 실제 크기가 이론적 예상보다 커집니다. 특히 인간 게놈의 텔로미어 · 센트로미어 영역.
• 문자 집합 크기: DNA는 알파벳 4～5글자로 트리의 팬아웃이 작습니다. 단백질은 20글자, 유니코드 텍스트는 훨씬 큽니다.
• 디스크 vs 메모리: 참조 게놈이 크면 접미사 배열을 디스크에 두고 mmap으로 사용해야 합니다. BWA · Bowtie가 이 방식.

CS 매핑

• 트리 자료구조: 접미사 트리는 트라이(Trie)의 특수 케이스입니다. 문자열 자료구조 이론의 정통.
• 이진 탐색: 접미사 배열의 검색은 이진 탐색입니다. 정렬된 데이터의 로그 시간 검색이라는 CS의 기본 원리.
• 캐시 친화성: 접미사 배열이 실무에서 접미사 트리를 이기는 큰 이유. 현대 CPU의 캐시 계층 특성이 알고리즘 선택을 결정합니다.
• 압축: BWT(다음 편) · FM-index는 접미사 배열을 압축된 형태로 저장해 메모리를 더 줄입니다. 정보 이론과 자료구조의 합작.

다음 편으로 이어지는 갈래

• 다음 편 (M14): Burrows-Wheeler Transform — 접미사 배열의 사촌. 압축과 검색 자료구조의 결합.
• 두 편 뒤 (M15): FM-index — BWT + 랭크/셀렉트로 완성되는 초고속 매핑 자료구조. BWA · Bowtie2의 심장.
• 세 편 뒤 (M16): minimap2 · 미니마이저 — 롱리드용 인덱스 사고.
• 열 편 뒤 (S03): BWA-MEM 실무 — 지금 만든 자료구조의 실제 응용.

더 깊게 파고 싶다면

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

• UC Berkeley CS176 — Yun Song 교수의 Suffix Trees and Arrays (자막 완비). Ukkonen · SA-IS 알고리즘을 상세히.
• 원 논문: Ukkonen, E. (1995), On-line construction of suffix trees, Algorithmica 14, 249–260. 접미사 트리 선형 구축의 원류.
• 원 논문: Manber, U. & Myers, G. (1993), Suffix arrays: A new method for on-line string searches, SIAM J Comput 22, 935–948. 접미사 배열의 시조.
• 참고 교재: Gusfield, D. Algorithms on Strings, Trees, and Sequences (1997). 정통 교과서.
• 참고 도구: sais-py (Python용 SA-IS 구현). 실무에서 접미사 배열 하나가 필요하다면.

Rosalind에서 SUFF · LREP · REVP 같은 문자열 검색 문제를 풀어봅시다. 다음 편 M14의 BWT가 왜 접미사 배열의 사촌인지 자연스럽게 이해됩니다.