minimap2와 미니마이저 완전 이해 — 롱리드 시대의 정렬 알고리즘 (한국어)

왜 이 편이 필요한가

M15의 FM-index는 짧은 리드 정렬의 정답이었습니다. 100bp Illumina 리드를 인간 게놈에 초당 수십만 개씩 매핑합니다. 그런데 롱리드 시대에는 다른 도구가 필요했습니다. PacBio HiFi (10～25kb)와 Oxford Nanopore (10kb～수Mb) 리드의 크기와 오류 프로파일이 완전히 다르기 때문입니다.

Heng Li(BWA의 저자와 같은 사람)가 2018년에 발표한 minimap2가 롱리드 시대의 표준이 됐습니다. 놀랍게도 minimap2는 FM-index를 안 씁니다. 대신 미니마이저(minimizer) 라는 훨씬 단순한 seed 자료구조를 씁니다. 이 편에서 그 아이디어를 뜯어봅시다.

왜 FM-index가 롱리드에 안 맞는가

FM-index는 짧고 오류가 적은 리드(Illumina 100～300bp, Q30+)에 최적화됐습니다. 롱리드는 두 가지 도전을 가져옵니다.

길이: 100kb 리드 하나에 seed가 많이 있어야 합니다. 짧은 seed로는 우연 매치가 폭발합니다.
오류율: Nanopore는 5～15% 오류율. 정확 매치 seed 크기를 늘리면 진짜 유사한 위치를 놓칩니다.

FM-index의 백워드 서치는 정확 매치 기반이라 오류가 있는 리드에서 처음부터 매치를 놓칩니다. 대안이 필요했습니다.

미니마이저(Minimizer) — 대표 k-mer 뽑기

Michael Schleimer 등이 2003년에 제안한 개념입니다. 정의는 이렇습니다.

미니마이저는 크기 w의 슬라이딩 윈도우 안의 모든 k-mer 중, 사전순으로 가장 작은 k-mer입니다.

예를 들어 서열 ACGTACGTACGT에서 w = 4, k = 3이라면:

윈도우 1 (ACGT): 3-mer는 ACG, CGT. 최소 = ACG (위치 0).
윈도우 2 (CGTA): 3-mer는 CGT, GTA. 최소 = CGT (위치 1).
윈도우 3 (GTAC): 3-mer는 GTA, TAC. 최소 = GTA (위치 2).
...

윈도우 별 미니마이저를 뽑아 나열하면, 원본 서열의 대표 k-mer 집합이 됩니다. 전체 k-mer 대신 대표만 인덱싱하면 크기가 크게 줄어듭니다.

왜 미니마이저가 seed로 좋은가

두 가지 좋은 성질이 있습니다.

성질 1: 대표성

두 서열이 유사하면(정확 매치가 아니어도), 그들의 미니마이저 집합도 상당 부분 겹칩니다. 슬라이딩 윈도우의 최솟값이 문자 몇 개 오류에 대해 상대적으로 안정적이기 때문입니다.

성질 2: 밀도 제어

윈도우 크기 w를 조절해 미니마이저의 밀도를 정할 수 있습니다.

w = 10, k = 15: 대략 100bp 당 하나의 미니마이저. 인간 게놈이라면 약 3천만 개의 대표 k-mer.
w = 5, k = 15: 대략 50bp 당 하나. 밀도 2배.

FM-index가 모든 k-mer를 담아야 하는 것과 대조됩니다.

minimap2의 3단계 파이프라인

인덱싱: 참조 게놈에서 미니마이저를 추출해 해시 테이블 인덱스 구축. 인덱스 크기가 FM-index의 1/10～1/5.
Seeding: 쿼리 리드의 미니마이저 각각을 인덱스에서 찾아 참조 위치 후보 리스트를 만듭니다.
Chaining + Extension: 후보 위치들 중 대각선 상에서 정렬 가능한 것들을 chain으로 묶고, 그 주변만 아핀 이중선 갭 페널티로 확장 정렬.

핵심 통찰은 롱리드에는 seed가 여러 개 매치되므로 chain을 만들 수 있다는 것입니다. 짧은 리드는 seed가 하나둘밖에 없어 chain이 안 됩니다. 롱리드의 강점이 알고리즘 설계에 반영됐습니다.

아핀 이중선(Two-piece Affine) 갭 페널티

Nanopore 리드에는 매우 긴 인델(수 kb)이 자주 나타납니다. 이건 실제 구조 변이일 수도, 시퀀싱 오류일 수도 있습니다. 표준 아핀 갭 페널티는 긴 인델을 너무 크게 벌합니다.

minimap2는 갭 페널티를 두 조각으로 나눕니다.

\text{gap}(k) = \min(a_1 + b_1 k, \, a_2 + b_2 k)

a_1, b_1: 짧은 갭용 (큰 개시, 작은 연장).
a_2, b_2: 긴 갭용 (큰 개시, 매우 작은 연장).

즉 갭이 짧으면 첫 아핀 페널티가, 길면 두 번째가 적용됩니다. 이 하나의 정교화가 구조 변이 검출 정확도를 크게 올렸습니다.

미니마이저 인덱스 파이썬 구현

python

def get_minimizers(seq: str, w: int, k: int) -> list[tuple[str, int]]:
    """서열에서 미니마이저(k-mer, 위치) 리스트를 반환."""
    minimizers = []
    prev_minimizer = None
    for i in range(len(seq) - w - k + 2):
        window = seq[i:i+w+k-1]
        best_kmer = None
        best_pos = None
        for j in range(w):
            kmer = window[j:j+k]
            if best_kmer is None or kmer < best_kmer:
                best_kmer = kmer
                best_pos = i + j
        current = (best_kmer, best_pos)
        if current != prev_minimizer:
            minimizers.append(current)
            prev_minimizer = current
    return minimizers

# 사용
seq = "ACGTACGTACGT"
mins = get_minimizers(seq, w=4, k=3)
for kmer, pos in mins:
    print(f"위치 {pos}: {kmer}")

minimap2 CLI 실습

실제 minimap2 사용은 매우 단순합니다.

bash

# 설치
conda install -c bioconda minimap2 -y

# 참조 게놈 인덱스 구축 (자동)
# minimap2가 처음 실행 시 자동으로 인덱스 생성

# HiFi 리드 정렬
minimap2 -ax map-hifi reference.fasta hifi_reads.fastq.gz > hifi.sam

# Nanopore 리드 정렬
minimap2 -ax map-ont reference.fasta nanopore_reads.fastq.gz > ont.sam

# 매우 긴 유전자 정렬 (예: mRNA to genome)
minimap2 -ax splice reference.fasta cdna.fasta > cdna.sam

-ax map-hifi, -ax map-ont 같은 프리셋(preset) 이 minimap2의 실무 편의성의 정점입니다. 데이터 유형에 맞는 파라미터를 자동으로 설정합니다.

실무 응용

롱리드 참조 매핑: PacBio · Nanopore의 표준.
구조 변이 검출: 긴 갭을 잘 다뤄서 SV 검출 정확도가 좋음. Sniffles · CuteSV와 결합.
다중 종 매핑: asm5, asm10, asm20 프리셋으로 종간 유사도별 정렬.
긴 RNA 정렬: cDNA 서열을 게놈에 매핑할 때. STAR보다 유리한 경우가 많음.
어셈블리 결과 매핑: 다른 어셈블리로 얻은 contig를 참조에 매핑해 비교.

자주 만나는 실무 함정

프리셋 선택: 데이터 유형(HiFi vs Nanopore vs 스플라이스)에 맞는 프리셋을 반드시 씁니다. 기본값은 대개 안 좋음.
인덱스 크기: minimap2 인덱스는 FM-index보다 작지만, 매우 큰 참조(예: 여러 게놈 결합)에서는 여전히 큽니다. 인덱스를 미리 만들어 재사용 (-d ref.mmi 옵션).
SAM 출력의 flag: minimap2의 SAM에는 특유의 태그가 있습니다. NM (edit distance), AS (alignment score), de (divergence) 등을 알아두면 후속 분석에 도움.
버전별 변경: minimap2는 활발히 개발됩니다. 재현성을 위해 사용 버전 명시.

CS 매핑

미니마이저 (Winnowing): 문서 표절 검출 · MinHash · 로그 압축에서 쓰이는 winnowing과 같은 아이디어. 원 논문은 Schleimer et al. (2003).
해시 인덱스: 미니마이저 → 위치 리스트는 해시 테이블. FM-index의 정교한 자료구조와 대조.
Chaining: 후보 seed들을 대각선 상에서 정렬 가능한 chain으로 묶는 것은 DP의 응용. 실제 minimap2는 chaining에도 세부 최적화가 있음.
프리셋 시스템: 도구의 사용성을 결정하는 핵심 UX 요소. 실무 도구 설계의 좋은 예.

다음 편으로 이어지는 갈래

다음 편 (M17): DIAMOND — 단백질 검색용 미니마이저 사고의 확장.
여섯 편 뒤 (S03 · S04): BWA-MEM · STAR — 짧은 리드 정렬 실무.
열여덟 편 뒤 (S14): 구조 변이 검출 — minimap2 정렬 결과 위에서 SV 검출.
스물다섯 편 뒤 (M24): hifiasm — HiFi 리드 어셈블리에서 미니마이저 응용.

더 깊게 파고 싶다면

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

Nick Loman 랩 (Sanger) — Long-read Sequencing and minimap2 (자막 완비, 자동 번역 우수). 실무 사용법과 원리를 함께.
원 논문: Li, H. (2018), Minimap2: pairwise alignment for nucleotide sequences, Bioinformatics 34, 3094–3100. 시조.
원 논문: Schleimer, S. et al. (2003), Winnowing: local algorithms for document fingerprinting, SIGMOD. 미니마이저의 CS 뿌리.
참고 도구: paftools.js (minimap2에 포함) — SAM/PAF 결과 처리 헬퍼 유틸리티.
참고 저장소: lh3/minimap2 GitHub. 실무 튜닝 · 벤치마크 · 프리셋 상세.

Colab에서 무료 롱리드 데이터셋(예: EMBL-EBI의 예제)을 다운받아 minimap2로 정렬해봅시다. 짧은 리드 정렬(BWA)과 무엇이 다른지 SAM 파일을 비교해보면 감이 완전히 잡힙니다. 손을 움직여야 합니다.

BioPlayground

minimap2와 미니마이저: 롱리드 시대의 정렬 인덱스