BioPlayground

🧬
목록으로

De Bruijn Graph와 오일러 경로: 숏리드 어셈블리의 다항 시간 우아함

OLC의 해밀턴 경로가 NP-완전이라면, De Bruijn의 오일러 경로는 다항 시간입니다. k-mer 정의부터 Hierholzer 알고리즘, k 선택의 트레이드오프까지.

심화
|
20분
|
검증 완료 (2026-07-20)
genome assemblyde bruijn graphshort-read sequencing
진행률0/34 (0%)

OLC의 벽에서 시작하기

M22에서 OLC(Overlap-Layout-Consensus)는 해밀턴 경로 문제를 풀어야 한다는 이유로 NP-완전 벽에 부딪힌다는 것을 확인했습니다. 리드 수백만 개면 정공법이 안 됩니다.

이 벽을 뛰어넘는 것이 De Bruijn Graph입니다. 노드 정의 하나만 바꿨을 뿐인데 문제가 다항 시간으로 바뀝니다. 이건 알고리즘 설계의 미학입니다. 이 편에서는 그 변환의 정수를 유도합니다.

k-mer 정의

De Bruijn의 첫 재정의는 노드입니다. 리드가 아니라 k-mer(길이 k의 부분 서열)를 노드로 씁니다.

리드 ACGTACG를 k=4로 조각내면 다음 4-mer들이 나옵니다.

text
ACGT · CGTA · GTAC · TACG

리드 하나에서 (L - k + 1)개의 k-mer가 나옵니다. 리드가 수백만이면 k-mer는 훨씬 더 많지만, 중복을 제거하면 게놈에 실제로 존재하는 서로 다른 k-mer 수로 압축됩니다. 이게 핵심 이득입니다.

De Bruijn Graph 정의

  • 노드: 서로 다른 (k-1)-mer
  • 엣지: 각 k-mer 하나 (그 k-mer의 앞 k-1자 → 뒤 k-1자로 방향성 엣지)

예를 들어 4-mer ACGT는 3-mer 노드 ACG → CGT로 이어지는 엣지가 됩니다.

리드 ACGTACG의 4-mer 4개를 De Bruijn Graph에 넣으면.

text
ACGT: ACG → CGT
CGTA: CGT → GTA
GTAC: GTA → TAC
TACG: TAC → ACG

노드 4개 (ACG, CGT, GTA, TAC), 엣지 4개. 원래 서열은 이 그래프의 엣지를 한 번씩 지나는 경로로 표현됩니다. 이게 오일러 경로.

오일러 경로 — 다항 시간의 왕도

오일러 경로 정리 (Euler, 18세기 쾨니히스베르크 다리 문제):

방향 그래프에 오일러 경로가 존재할 필요충분 조건은, (1) 그래프가 연결돼 있고, (2) 시작 노드는 outdeg - indeg = 1, 종료 노드는 indeg - outdeg = 1, 나머지는 outdeg = indeg인 것.

이 조건을 만족하면 Hierholzer 알고리즘으로 O(엣지 수) 시간에 오일러 경로를 찾습니다.

Hierholzer의 아이디어는 단순합니다.

  1. 임의 노드에서 시작해 갈 수 있는 엣지를 계속 따라간다
  2. 못 가는 데까지 갔으면 회로가 하나 완성. 이 회로에서 아직 못 쓴 엣지가 있는 노드로 돌아가 다시 회로를 만든다
  3. 두 회로를 합병한다
  4. 모든 엣지를 다 쓸 때까지 반복

O(N + E). 노드와 엣지 수의 합에 선형입니다. NP-완전이었던 해밀턴 경로가 다항 시간의 오일러 경로로 바뀌면서, 수백만 리드도 몇 분 안에 처리됩니다.

손으로 어셈블리해봅시다

관측 리드가 4개 있다고 합시다.

text
R1: ACGTAC
R2: CGTACG
R3: GTACGT
R4: TACGTA

k=4로 4-mer 조각. 각 리드에서 3개씩, 총 12개(중복 있음).

R1: ACGT · CGTA · GTAC R2: CGTA · GTAC · TACG R3: GTAC · TACG · ACGT R4: TACG · ACGT · CGTA

중복 제거 후 서로 다른 4-mer 4개: ACGT, CGTA, GTAC, TACG.

3-mer 노드로 De Bruijn Graph:

text
ACG → CGT (from ACGT)
CGT → GTA (from CGTA)
GTA → TAC (from GTAC)
TAC → ACG (from TACG)

노드 4개, 엣지 4개. 그래프 위상은 완전한 사이클. 오일러 회로가 존재합니다.

경로: ACG → CGT → GTA → TAC → ACG.

이 경로에서 3-mer를 이어붙이면 (첫 3자 유지, 각 노드의 마지막 문자만 이어 붙임).

text
ACG + T + A + C + ... = ACGTACG (원 게놈)

원 게놈이 재구성됩니다. 손 어셈블리가 이렇게 됩니다.

왜 다항 시간이 나오나

핵심은 엣지 = 관측된 k-mer라는 정의입니다. OLC에서는 오버랩이 확률적으로 있을 수도 없을 수도 있는 "가능한 관계"였습니다. De Bruijn에서는 엣지 하나하나가 "관측된 사실". 그 관측을 한 번씩 사용하는 경로를 찾는 것이 오일러 경로 문제로 정확히 매칭됩니다.

문제 정의를 그래프 이론의 다항 시간 문제로 정확히 매핑한 것. 이게 De Bruijn의 우아함입니다. 정보를 다르게 표현하는 것만으로 알고리즘의 근본 복잡도가 바뀌었습니다.

k 선택의 트레이드오프

De Bruijn Graph의 실전 성능은 k 값에 극단적으로 민감합니다.

k가 너무 작으면:

  • 서로 다른 위치에서 온 같은 k-mer가 겹쳐서 그래프에 반복 사이클이 많아짐
  • 반복 영역에서 여러 경로가 후보로 나타나서 정답을 특정 못함
  • 최종 어셈블리가 조각(contig)으로 잘게 부서짐

k가 너무 크면:

  • 오류가 든 k-mer가 그래프에서 고립되어 사용 불가
  • 각 리드에서 나오는 k-mer 수가 줄어들어 그래프가 성기고 끊김
  • 커버리지가 부족한 곳에서 갭 발생

실무에서는 SPAdes 같은 도구가 여러 k 값(21, 33, 55, 77, 99 등)으로 그래프를 만들어 합칩니다. 이 다중 k 접근이 SPAdes의 성공 비결이었습니다.

Bubble과 tip — 그래프 오류 복구

De Bruijn Graph의 실전에서는 오류가 든 리드가 그래프에 두 가지 위상 결함을 만듭니다.

Bubble: 두 노드 사이에 병렬 경로가 두 개 있으면 하나는 정답, 하나는 오류. 짧은 병렬 경로는 오류로 판정하고 잘라냅니다.

Tip: 그래프의 한쪽 끝에서 짧게 삐져나온 가지. 커버리지가 낮으면 오류 리드가 만든 가지일 확률이 높습니다. 임계 이하 길이의 tip은 삭제.

이 두 트릭이 De Bruijn Graph 어셈블러의 정확도의 80%를 책임집니다.

파이썬 미니 구현 (~40줄)

python
from collections import defaultdict


def build_de_bruijn(reads, k):
    """리드에서 De Bruijn Graph 생성. 노드 = (k-1)-mer, 엣지 = k-mer."""
    graph = defaultdict(list)
    indeg = defaultdict(int)
    outdeg = defaultdict(int)
    for read in reads:
        for i in range(len(read) - k + 1):
            kmer = read[i:i+k]
            u, v = kmer[:-1], kmer[1:]
            graph[u].append(v)
            outdeg[u] += 1
            indeg[v] += 1
    return graph, indeg, outdeg


def find_euler_path(graph, indeg, outdeg):
    """Hierholzer 오일러 경로."""
    # 시작 노드 결정
    start = None
    for node in list(outdeg.keys()) + list(indeg.keys()):
        if outdeg[node] - indeg[node] == 1:
            start = node
            break
    if start is None:
        start = next(iter(graph))  # 오일러 회로 존재 시 임의 시작


    # 그래프 복사 (원본 훼손 방지)
    g = {u: list(vs) for u, vs in graph.items()}
    stack = [start]
    path = []
    while stack:
        node = stack[-1]
        if g.get(node):
            stack.append(g[node].pop())
        else:
            path.append(stack.pop())
    return path[::-1]


def assemble(path):
    """오일러 경로에서 게놈 문자열 재구성."""
    if not path:
        return ""
    result = path[0]
    for node in path[1:]:
        result += node[-1]
    return result


reads = ["ACGTAC", "CGTACG", "GTACGT", "TACGTA"]
k = 4
graph, indeg, outdeg = build_de_bruijn(reads, k)
path = find_euler_path(graph, indeg, outdeg)
genome = assemble(path)
print("Path:", path)
print("Genome:", genome)

실행하면 사이클 형태의 오일러 경로가 나오고, 원래 게놈이 재구성됩니다. 40줄이 De Bruijn 어셈블리의 뼈대의 전부. SPAdes 같은 실전 도구는 여기에 다중 k · bubble/tip 제거 · repeat 처리 · 페어드엔드 정보를 얹은 거대한 엔지니어링입니다.

복잡도

  • 그래프 구축: O(총 k-mer 수) = O(N × L). N은 리드 수
  • 오일러 경로: O(V + E). 노드·엣지 수의 합에 선형
  • 총: 리드 수백만이어도 몇 분

OLC의 지수 시간 대비 결정적 이득. 대신 롱리드 시대에는 리드 자체가 커져서 k를 키워도 되고, 오히려 OLC가 더 안정적이라는 게 M22에서 다룬 이야기입니다.

SPAdes — 숏리드 시대의 왕좌

SPAdes(Bankevich et al. 2012)는 De Bruijn 어셈블러의 대표작입니다. 세균 유전체와 메타게놈 어셈블리의 표준. 핵심 특징.

  • 다중 k: 21, 33, 55, 77, 99를 순차적으로 사용 (--only-assembler 옵션)
  • hybrid mode: 숏리드 De Bruijn에 롱리드(--pacbio, --nanopore)를 얹어 갭 채움
  • plasmid mode: 플라스미드 특이 어셈블리 옵션
  • metaSPAdes: 마이크로바이옴 특화 모드

실습:

bash
# SPAdes 설치
wget https://github.com/ablab/spades/releases/download/v4.0.0/SPAdes-4.0.0-Linux.tar.gz
tar xzf SPAdes-4.0.0-Linux.tar.gz
./SPAdes-4.0.0-Linux/bin/spades.py --version


# 소규모 세균 어셈블리 (paired-end)
spades.py -1 reads_R1.fastq.gz -2 reads_R2.fastq.gz -o my_assembly \
          -k 21,33,55,77 -t 4


# 결과 확인
grep -c "^>" my_assembly/scaffolds.fasta

세균 게놈(~5Mb)은 노트북에서 수십 분 만에 어셈블됩니다. 사람 게놈 스케일은 클러스터 필요.

CS 매핑 — 문제 재정의의 힘

DryBench에서 다룬 문제 변환의 실전 사례입니다.

  • 해밀턴 경로 (NP-완전) ← 노드가 리드
  • 오일러 경로 (다항 시간) ← 노드가 k-mer, 엣지가 리드

같은 물리적 문제(리드를 이어붙임)를 다르게 표현했더니 계산 복잡도가 근본적으로 바뀝니다. 알고리즘 설계에서 가장 강력한 기술은 문제를 다시 정의하는 것입니다. 하드한 표현에서 이지한 표현으로 매핑할 수 있으면 승자가 됩니다.

이 교훈은 다른 곳에도 나타납니다. FFT는 다항식 곱셈을 점 표현으로 바꿔 O(n²)을 O(n log n)으로 줄였습니다. Linear Programming의 dual은 원문제의 하드 부분을 이지한 부분으로 옮깁니다. 표현이 알고리즘이다.

Rosalind에서 채점받기

Rosalind DBG 문제. k-mer 리스트가 주어지고 De Bruijn Graph를 만들어야 합니다. 위 파이썬 구현의 build_de_bruijn 함수를 그대로 씁니다.

Rosalind EULR: 오일러 경로 문제. find_euler_path 함수를 그대로 씁니다.

다음 편으로 이어지는 갈래

  • 다음 편 (M24): hifiasm — PacBio HiFi 리드로 다이플로이드 조립. 부모 특이(trio binning)까지. OLC의 최신 실전. Micro Tier 어셈블리 시리즈의 왕관
  • Assembly 시리즈 이후 (M25): 다중 서열 정렬 — Progressive alignment · MAFFT
  • 확장: string graph (Myers) — OLC와 De Bruijn의 통합 이론

더 깊게 파고 싶다면

  • Pevzner, Tang, Waterman (2001), An Eulerian path approach to DNA fragment assembly, PNAS — De Bruijn을 어셈블리에 처음 적용한 논문. Pevzner의 큰 통찰.
  • Bankevich et al. (2012), SPAdes: A New Genome Assembly Algorithm and Its Applications, J Comput Biol — SPAdes 원 논문. 다중 k 접근의 정수.
  • UC Berkeley CS176 — Yun S. Song 교수의 어셈블리 강의. De Bruijn 위상도를 판서로 봅니다.
  • Ben Langmead (JHU) — 유튜브 어셈블리 재생목록. 그래프 손 유도.
  • Compau & Pevzner Bioinformatics Algorithms Chapter 3 — Rosalind와 연동된 De Bruijn 튜토리얼.

다음 편으로 넘어가기 전에, 위 파이썬 코드에 오류가 든 리드 몇 개를 넣어봅시다. bubble과 tip이 어떻게 만들어지는지, 그리고 그것을 어떻게 제거해야 하는지 손으로 확인하는 것이 이 편의 진짜 실습입니다.