BioPlayground

🧬
목록으로

OLC 어셈블리: 오버랩 그래프와 해밀턴 경로로 게놈을 재조립하기

긴 리드를 다시 이어붙이는 첫 어셈블리 프레임 OLC. 오버랩 그래프의 정의부터 해밀턴 경로의 NP-완전성, 그리고 왜 롱리드 시대에 OLC가 부활했는지.

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

리드를 다시 이어붙인다는 문제

시퀀서에서 나오는 것은 짧게 잘린 서열 조각(read)입니다. 100bp·150bp의 숏리드, 10～100kb의 롱리드. 원래 게놈은 수백만～수십억 bp짜리 하나의 긴 서열. 이 리드를 원래 게놈으로 되짚어 이어붙이는 문제가 어셈블리(assembly) 입니다.

두 가지 큰 프레임이 있습니다. OLC(Overlap-Layout-Consensus) 와 De Bruijn Graph. 이 편에서는 OLC를 다룹니다. 다음 편(M23)에서 De Bruijn을 다룰 것이고, 그 다음 편(M24)에서 최신 롱리드 표준 hifiasm으로 이어집니다. 이 세 편이 어셈블리 시리즈의 뿌리입니다.

OLC 세 단계

이름 그대로 세 단계입니다.

  1. Overlap: 모든 리드 쌍 사이의 겹치는 접미사·접두사를 찾는다
  2. Layout: 리드를 노드로, 오버랩을 엣지로 하는 그래프를 만들고 최적 경로를 찾는다
  3. Consensus: 경로를 따라 리드를 이어붙이고, 오버랩 구간에서 다수결로 오류를 정정한다

세 단계 모두 어렵지만, 특히 Layout 단계가 이 알고리즘의 심장입니다. 최적 경로 = 각 리드를 정확히 한 번씩 방문하는 경로 = 해밀턴 경로. 이건 NP-완전 문제입니다. 그래서 실제 도구들은 여러 휴리스틱으로 근사합니다.

Overlap 계산 — 어떻게 오버랩을 감지하나

리드 A와 리드 B가 있을 때, A의 접미사와 B의 접두사가 같은 길이(overlap length) o를 찾습니다. 예를 들어

text
A: ACGTACG
B:    TACGTAT

A의 접미사 TACG와 B의 접두사 TACG가 길이 4에서 매칭. 두 리드는 오버랩 4로 연결됩니다.

정공법은 모든 쌍 O(N²) × 각 쌍의 접미사·접두사 매칭 O(L)로 O(N² × L). N이 수백만이면 계산 불가능. 그래서 접미사 트리(M13)나 FM-index(M15)로 미리 인덱싱해서 O((N+L) log L)로 낮춥니다. 어셈블리 앞 단계에서 왜 문자열 인덱스 자료구조를 배웠는지가 여기서 드러납니다.

실무에서는 오버랩 최소 길이(예: 50bp)와 최소 정확도(예: 95%)를 임계로 설정합니다. 오류가 낀 리드는 오버랩을 살짝 놓치지만, 다른 리드와 여전히 연결됩니다.

오버랩 그래프

  • 노드: 각 리드
  • 엣지: 두 리드 사이 오버랩 (방향성 있음: A→B는 "A의 접미사가 B의 접두사와 겹침")
  • 엣지 가중치: 오버랩 길이 (혹은 정확도 점수)

이 그래프 위에서 모든 노드를 정확히 한 번씩 지나는 경로(해밀턴 경로)가 원래 게놈의 순서를 재구성합니다.

간단한 예제. 리드 5개.

text
R1: ACGTACG
R2:   GTACGT
R3:      CGTAT
R4: TTACGTA
R5: GTATGC

오버랩 표 (편의상 임계 = 3 이상 오버랩만):

FromToOverlap
R1R25 (GTACG)
R2R34 (CGTA)
R3R53 (TAT)
R4R15 (ACGTA)
R4R24 (ACGT)

그래프를 그리면 R4 → R1 → R2 → R3 → R5의 한 방향 경로가 나옵니다. 5개 노드 전부 방문. 이 경로를 따라 리드를 이어붙이면.

text
R4:  TTACGTA
R1:      ACGTACG
R2:         GTACGT
R3:            CGTAT
R5:                GTATGC

Consensus: TTACGTACGTATGC

원래 게놈이 재구성됩니다. 이게 OLC의 실전입니다.

해밀턴 경로 — 왜 어려운가

위 예제는 노드가 5개라 눈으로 풀립니다. 리드 수백만 개면 이야기가 달라집니다. 해밀턴 경로 문제는 NP-완전. 알려진 다항 시간 알고리즘이 없습니다.

실무 도구는 몇 가지 트릭을 씁니다.

  • 탐욕법(greedy): 매 단계에서 최장 오버랩 엣지를 골라 이어간다. 지역 최적으로만 수렴하지만 실전 게놈에서는 대부분 잘 동작
  • string graph 축약: transitive edge (A→C 있고 A→B→C도 있으면 A→C 제거) 제거로 그래프를 훨씬 작게 만든다. Myers의 원 통찰
  • repeat 분리: 반복 서열은 여러 위치에서 온 리드가 하나의 노드로 모여 그래프 위상이 꼬인다. paired-end 정보 · 롱리드 span으로 풀어낸다

Celera Assembler(사람 게놈 프로젝트에서 Venter 팀이 사용)가 이 접근의 대표작이었습니다. 이후 miniasm, Canu, Falcon 같은 롱리드 도구도 OLC 계열입니다.

왜 OLC가 롱리드 시대에 부활했나

숏리드 시대(2010년대 초·중반)에는 De Bruijn Graph(다음 편)가 표준이었습니다. 리드 길이가 100bp라서 오버랩 자체가 어렵고, k-mer 기반 De Bruijn이 훨씬 효율적이었기 때문입니다.

롱리드 시대(2020년대)가 되면서 상황이 뒤집혔습니다. 리드 하나가 10～100kb. 오류율은 5～15%로 높지만 원거리 구조 정보가 풍부합니다. 오버랩 감지가 안정적이고 반복 영역을 span할 수 있습니다. OLC가 다시 표준으로 올라온 이유입니다.

hifiasm 같은 최신 도구는 OLC의 뼈대에 HiFi 리드(고정확도 롱리드)의 특성을 얹었습니다. 이 이야기는 M24에서 다룹니다.

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

원리 확인용 장난감 구현. 실전 도구를 대체하는 게 아닙니다.

python
def overlap(a, b, min_length=3):
    """a의 접미사와 b의 접두사가 겹치는 최장 길이 반환."""
    start = 0
    while True:
        start = a.find(b[:min_length], start)
        if start == -1:
            return 0
        if b.startswith(a[start:]):
            return len(a) - start
        start += 1


def build_overlap_graph(reads, min_length=3):
    """모든 리드 쌍의 오버랩을 계산."""
    graph = {}
    for a in reads:
        for b in reads:
            if a == b:
                continue
            olen = overlap(a, b, min_length)
            if olen > 0:
                graph.setdefault(a, []).append((b, olen))
    for a in graph:
        graph[a].sort(key=lambda x: -x[1])  # 오버랩 큰 순
    return graph


def greedy_hamiltonian(reads, min_length=3):
    """탐욕 해밀턴 경로 (근사)."""
    graph = build_overlap_graph(reads, min_length)
    remaining = set(reads)
    # 인엣지가 없는 노드부터 시작 (없으면 임의 시작)
    in_deg = {r: 0 for r in reads}
    for a, edges in graph.items():
        for b, _ in edges:
            in_deg[b] += 1
    start = min(reads, key=lambda r: in_deg[r])
    path = [start]
    remaining.remove(start)


    current = start
    while remaining:
        candidates = graph.get(current, [])
        for nxt, _ in candidates:
            if nxt in remaining:
                path.append(nxt)
                remaining.remove(nxt)
                current = nxt
                break
        else:
            # 연결 끊김 → 남은 노드에서 다시 시작
            current = remaining.pop()
            path.append(current)
    return path


def consensus(path, min_length=3):
    """경로를 따라 오버랩만큼 잘라내며 이어붙임."""
    result = path[0]
    for i in range(1, len(path)):
        olen = overlap(path[i-1], path[i], min_length)
        result += path[i][olen:]
    return result


reads = ["ACGTACG", "GTACGT", "CGTAT", "TTACGTA", "GTATGC"]
path = greedy_hamiltonian(reads, min_length=3)
print("Layout:", path)
print("Consensus:", consensus(path, min_length=3))

실행하면 위 손 계산과 일치합니다. 이 40줄이 OLC의 진짜 심장입니다. 실전 도구는 여기에 인덱싱·transitive 축약·repeat 처리를 얹은 거대한 엔지니어링이지만, 뼈대는 이 코드에서 벗어나지 않습니다.

복잡도

  • Overlap 단계: O(N² × L) 정공법 → 인덱싱으로 O((N+L) log L)
  • Layout 단계: 해밀턴 경로 = NP-완전. 탐욕 근사 O(N)
  • Consensus 단계: 경로 길이 O(N × L)

Overlap이 병목입니다. 리드 수백만 개에 대해 인덱스 없이는 계산 자체가 안 됩니다. 접미사 트리·FM-index를 미리 배운 이유가 여기서 결실을 봅니다.

OLC vs De Bruijn — 왜 두 프레임이 공존하나

항목OLCDe Bruijn
노드 정의리드k-mer
엣지 정의오버랩k-1 접미사·접두사 매칭
목표해밀턴 경로 (NP-완전)오일러 경로 (다항 시간)
적합 리드롱리드 (10kb+)숏리드 (100～150bp)
대표 도구Celera, Canu, hifiasmVelvet, SPAdes, ABySS
부활 시점2020년대 (롱리드)2010년대 (숏리드 붐)

두 프레임의 결정적 차이는 노드 정의입니다. OLC는 리드 단위, De Bruijn은 k-mer 단위. 이 선택 하나가 알고리즘 복잡도와 적합 리드 종류를 결정합니다. 자세한 비교는 다음 편에서 이어집니다.

CS 매핑 — 그래프 알고리즘의 어려움

DryBench에서 다룬 NP-완전 개념이 여기서 실전 사례로 등장합니다.

  • 해밀턴 경로: 모든 노드 정확히 한 번 방문 → NP-완전
  • 오일러 경로: 모든 엣지 정확히 한 번 방문 → 다항 시간

한 글자 차이(노드 vs 엣지)로 계산 복잡도가 정반대. 문제를 어떻게 정의하느냐가 해결 난이도를 근본적으로 바꿉니다. 알고리즘 설계의 미학이 여기서 드러납니다. De Bruijn Graph를 다음 편에서 배우면서 이 대비를 다시 봅시다.

Rosalind에서 채점받기

Rosalind에는 OLC 문제 여러 개가 있습니다. OverlapGraphs(BA3C), LongOverlapMerge(BA3M) 등. 위 파이썬 구현의 overlap 함수를 재활용해서 그대로 풉니다. 오버랩 함수를 안정적으로 짜는 것이 이 시리즈의 실무 기초입니다.

다음 편으로 이어지는 갈래

  • 다음 편 (M23): De Bruijn Graph — k-mer 노드 + 오일러 경로. 숏리드 시대의 표준. 다항 시간의 아름다움
  • 두 편 뒤 (M24): hifiasm — PacBio HiFi 다이플로이드 조립. OLC의 최신 실전. 부모 특이 assembly (trio binning)
  • 확장: string graph (Myers 2005) — OLC의 그래프 축약 이론의 정수. hifiasm의 이론적 뿌리

더 깊게 파고 싶다면

  • Myers (2005), The fragment assembly string graph, Bioinformatics — String graph의 원 논문. transitive edge 축약의 정수.
  • Chin et al. (2016), Phased diploid genome assembly with single-molecule real-time sequencing, Nature Methods — Falcon 논문. 롱리드 OLC의 실전 파이프라인.
  • Stanford CS262 — Gill Bejerano 교수의 assembly 강의 (자막 완비). OLC vs De Bruijn 대비를 판서로 봅니다.
  • Ben Langmead (JHU) — 재생목록에 assembly 편이 있습니다. 그래프 위상을 시각적으로 봅니다.
  • Compau & Pevzner Bioinformatics Algorithms — Rosalind와 연동. Chapter 3이 어셈블리 편.

다음 편으로 넘어가기 전에, 위 파이썬 구현에 리드 20～50개를 랜덤 생성해서 넣어봅시다. 탐욕 알고리즘이 언제 실패하는지, 반복 서열이 있으면 어떻게 꼬이는지 손으로 확인하는 것이 이 편의 진짜 실습입니다.