Diamond 단백질 검색 완전 이해 — BLAST의 100～10000배 가속, double indexing부터 실행까지

왜 지금 이 편이 필요한가

BLAST를 배웠으니 이제 프로테옴 전체를 검색해봅시다. 한 미생물 메타게놈 어셈블리에서 나온 단백질 예측 서열이 100만 개, NCBI nr 데이터베이스가 5억 개 서열. BLASTP를 그대로 돌리면 며칠이 걸립니다. 실무에서는 이 며칠짜리 배치가 하루에 한 번씩 돌아야 합니다. 그래서 2015년, Diamond라는 도구가 등장해서 BLAST와 같은 답을 100～10,000배 빠르게 뱉기 시작했습니다.

이 편에서는 Diamond가 어떻게 BLAST의 벽을 넘었는지 세 가지 재설계 아이디어를 원리 수준에서 유도합니다. 알고리즘의 정확도는 그대로 두고 상수 팩터만 줄이는 것이 어떻게 실무에서 게임 체인저가 되는지 감을 잡아봅시다.

벽에 부딪힌 BLASTP

M10에서 배운 BLAST의 골격을 잠깐 되짚어봅시다.

쿼리 서열을 k-mer 시드로 자른다 (단백질은 보통 k=3)
데이터베이스 색인에서 시드가 걸리는 위치를 찾는다
걸린 위치에서 양방향으로 확장해서 HSP(High-scoring Segment Pair)를 만든다
확장 점수가 임계를 넘으면 후보로 남긴다

이 흐름 자체는 아름답습니다. 문제는 2번 단계의 캐시 미스입니다. 데이터베이스가 커질수록 시드 하나가 걸리는 위치가 폭발적으로 늘어나고, 그때마다 랜덤 억세스로 데이터베이스 서열을 읽어옵니다. CPU 파이프라인이 절반 이상 대기 상태로 낭비됩니다.

메타게놈 시대에는 이 벽이 더 낮습니다. 쿼리도 크고 (100만+ 예측 단백질), 데이터베이스도 큽니다 (nr 5억+). 결과는 하나의 배치가 며칠. 이 격차를 좁힌 첫 도구가 Diamond입니다. Benjamin Buchfink 등이 Nature Methods에 2015년 처음 발표하고, 2021년에 v2로 최대 10,000배 가속을 달성했습니다.

Diamond의 세 가지 재설계 아이디어

아이디어 1 — Double indexing

BLAST는 쿼리만 색인합니다. 데이터베이스는 매번 훑습니다. Diamond는 쿼리와 데이터베이스 둘 다 색인해서 두 색인의 교집합에서 시드 매칭을 뽑습니다.

왜 이게 빠릅니까? 데이터베이스 색인은 한 번만 만들면 됩니다. 그리고 쿼리 색인은 배치 단위로 미리 만들어둡니다. 시드 매칭은 두 정렬된 리스트의 머지 조인 (SQL의 sort-merge join과 같은 구조) 한 번으로 끝납니다. 캐시 지역성이 극적으로 살아나고, 랜덤 억세스가 순차 억세스로 바뀝니다.

간단하게 표로 봅시다. 쿼리 서열 3개, 데이터베이스 서열 4개, k=3, 예시 시드 몇 개만 봅니다.

쿼리	시드 (k=3)	데이터베이스	시드 (k=3)
Q1	AGT · GTC	D1	AGT · GTA
Q2	GTC · TCA	D2	TCA · CAG
Q3	CAG · AGC	D3	AGC · GCT

BLAST 방식은 각 쿼리 시드마다 D 전체를 훑습니다. Diamond 방식은 두 리스트를 시드별로 정렬해서 한 번의 머지로 매칭을 뽑습니다.

text

정렬된 쿼리 시드 리스트:    (AGT, Q1) (AGC, Q3) (CAG, Q3) (GTC, Q1) (GTC, Q2) (TCA, Q2)
정렬된 데이터베이스 시드:    (AGT, D1) (AGC, D3) (CAG, D2) (GTA, D1) (GCT, D3) (TCA, D2)

같은 시드끼리 매칭 (AGT: Q1-D1, AGC: Q3-D3, CAG: Q3-D2, TCA: Q2-D2). 두 리스트가 미리 정렬돼 있으므로 두 포인터를 나란히 밀면서 한 번만 훑으면 됩니다.

아이디어 2 — Reduced alphabet과 spaced seed

단백질 알파벳은 20자입니다. k=3만 되어도 20³ = 8,000개 조합. 시드 특이도가 낮아서 오탐이 많습니다. Diamond는 화학적 유사성으로 그룹핑한 축약 알파벳 (11자 정도)을 씁니다. 시드는 여전히 4자 폭이지만 가운데 두 자리는 매칭을 요구하지 않는 spaced seed를 씁니다. 시드 모양이 **·** 같은 형태입니다.

축약 알파벳은 원거리 상동성(remote homology)을 잃지 않으면서도 시드 매칭 수를 줄입니다. Spaced seed는 무작위 오탐률을 낮추고 실제 정렬 신호는 유지합니다. 이 두 트릭이 조합되면서 후보 시드 수가 BLAST 대비 크게 줄고, 이후의 확장 단계 부담이 그만큼 가벼워집니다.

아이디어 3 — 블록 배치와 SIMD 벡터화

BLAST는 히트 하나를 만나면 즉시 확장합니다. Diamond는 일정 크기의 블록 (기본 2GB)로 데이터베이스를 잘라서 처리합니다. 블록 안에서 시드 매칭을 전부 모으고, 그다음 확장을 배치로 처리합니다.

배치가 왜 이득인가요? Smith-Waterman 확장은 격자 셀 하나를 계산할 때 이웃 셀 세 개 (위·왼쪽·대각선)만 필요합니다. 이 데이터 흐름은 SIMD 명령(SSE·AVX2)에 완벽히 맞습니다. 여러 서열 쌍의 확장을 나란히 세워서 한 명령으로 16～32개 셀을 동시에 채웁니다. CPU 하나의 처리량이 산술적으로 몇 배가 됩니다.

여기에 스레드 병렬화가 얹혀서, 8코어 서버에서 BLAST 대비 최대 4자릿수 가속이 나옵니다. v2에서는 GPU 확장까지 추가되면서 격차가 더 벌어졌습니다.

Sensitivity 모드의 트레이드오프

Diamond를 실무에서 쓸 때 가장 중요한 스위치가 sensitivity 모드입니다.

모드	시드 정책	상대 속도 (v2 기준)	용도
`default` (fast)	spaced seed 4x	500～1,000×	유전자 예측 근거 후보 스크리닝
`--mid-sensitive`	시드 짧게, 확장 임계 완화	100～300×	종 내 · 근연 원거리
`--sensitive`	4자리 spaced + 확장 완화	50～100×	균 - 균 사이
`--more-sensitive`	시드 3자리로 축소	10～50×	원거리 상동성
`--very-sensitive`	시드 폭 최소 · 확장 크게	5～20×	도메인 수준 검색
`--ultra-sensitive`	거의 exhaustive	2～5×	BLAST 대체용 최대 감도

BLAST의 결과를 그대로 재현하고 싶다면 --ultra-sensitive. 그럼에도 여전히 BLAST보다 2～5배는 빠릅니다. 반대로 후보 스크리닝만 필요하면 default로 두 자리 수 배수 가속이 무료로 붙습니다.

이 표를 외우기보다 원리를 기억합시다. 속도와 감도는 시드 특이도로 조정된다. 시드가 촘촘하면 후보는 적고 속도는 빠르지만, 원거리 상동성을 놓칩니다. 시드가 성기면 반대입니다. 실무에서 도구 선택보다 이 모드 선택이 결과 품질을 더 좌우합니다.

실습 — Diamond CLI로 첫 검색을 돌려봅시다

Colab이나 SageMaker Studio Lab 무료 CPU 인스턴스에서 그대로 됩니다.

bash

# 1) 설치 (conda 없이도 됩니다)
wget https://github.com/bbuchfink/diamond/releases/download/v2.1.9/diamond-linux64.tar.gz
tar xzf diamond-linux64.tar.gz
./diamond version

# 2) 소규모 데이터베이스 만들기 (예: SwissProt 5000개 서열)
wget -O sprot.fasta.gz https://ftp.uniprot.org/pub/databases/uniprot/current_release/knowledgebase/complete/uniprot_sprot.fasta.gz
gunzip sprot.fasta.gz
./diamond makedb --in sprot.fasta -d sprot

# 3) 쿼리 준비 (예: 인간 인슐린 P01308)
cat > insulin.fasta <<'EOF'
>P01308 Human Insulin
MALWMRLLPLLALLALWGPDPAAAFVNQHLCGSHLVEALYLVCGERGFFYTPKTRREAED
LQVGQVELGGGPGAGSLQPLALEGSLQKRGIVEQCCTSICSLYQLENYCN
EOF

# 4) 검색 실행 — default 모드
./diamond blastp -q insulin.fasta -d sprot -o hits.tsv \
  --threads 4 --outfmt 6 qseqid sseqid pident length evalue bitscore

# 5) 감도 모드 비교 — ultra-sensitive
./diamond blastp -q insulin.fasta -d sprot -o hits_us.tsv \
  --ultra-sensitive --threads 4 --outfmt 6 qseqid sseqid pident length evalue bitscore

# 6) 결과 라인 수 비교
wc -l hits.tsv hits_us.tsv

인슐린 같은 잘 보존된 단백질은 default 모드로도 종을 넘나드는 히트가 수십 개 잡힙니다. --ultra-sensitive로 바꾸면 원거리 상동체가 몇 배 더 걸리는 것을 볼 수 있습니다.

결과 포맷 다루기

Diamond의 기본 출력은 BLAST의 outfmt 6을 그대로 계승합니다. 컬럼 순서를 명시적으로 지정할 수 있고, 이건 후처리 스크립트를 짤 때 필수입니다.

python

# 파이썬으로 간단한 필터
import csv

MIN_PIDENT = 30.0
MIN_LENGTH = 50
MAX_EVALUE = 1e-10

with open("hits.tsv") as f:
    reader = csv.reader(f, delimiter="\t")
    for row in reader:
        qseqid, sseqid, pident, length, evalue, bitscore = row
        if (float(pident) >= MIN_PIDENT and
            int(length) >= MIN_LENGTH and
            float(evalue) <= MAX_EVALUE):
            print(qseqid, sseqid, pident, evalue)

실무에서는 이 자리에 다시 pandas가 들어가고, 히트 결과에 taxonomy를 조인하고, 유전자 이름으로 다시 조인하고, 최종적으로 한 장의 표로 정리합니다. 여기서 중요한 것은 필터 임계를 미리 정하고 문서화하는 습관입니다. 감도 모드와 후처리 임계를 같이 정하지 않으면 재현이 안 됩니다.

복잡도와 실무의 감

이론적 시간 복잡도는 BLAST와 같은 O((m + n) × 시드 후보 수)이지만, 상수 팩터가 두세 자릿수 다릅니다. Diamond가 노리는 지점은 정확히 상수 상수 팩터의 재설계입니다. 알고리즘의 점근적 클래스는 그대로지만, 실제 실행 시간이 하드웨어 특성에 맞춰 최적화되면 실무 체감은 완전히 달라집니다.

이건 CS의 흔한 교훈 하나를 실증합니다. 점근 복잡도가 같아도 상수 팩터를 재설계하면 게임이 바뀝니다. 데이터 지역성, SIMD, 배치 처리, 스레드 병렬화 — 이 네 가지 도구가 조합되면서 BLAST 시대에는 서버 팜에서 며칠 걸리던 배치가 노트북에서 몇 시간이면 끝나게 되었습니다.

CS 매핑 — 해싱과 배치 처리의 결혼

DryBench에서 다룬 해시 기반 색인과 배치 조인이 여기서 결합됩니다.

해시 색인: 시드 → 위치 매핑. 축약 알파벳으로 해시 공간 축소
머지 조인: 두 정렬된 시드 리스트의 교집합 (SQL sort-merge join과 동형)
캐시 지역성: 랜덤 억세스 → 순차 억세스로 재설계
SIMD 벡터화: 확장 단계 격자 셀 병렬 계산
배치 처리: 블록 단위로 시드를 모아 확장을 몰아 처리

CPU 아키텍처가 파이프라인 · 캐시 · 벡터 명령의 세 축으로 진화해왔다는 사실을 알고리즘 설계자가 인지하고 있느냐 아니냐가, 이런 도구가 나올 수 있느냐 없느냐를 결정합니다.

다음 편으로 이어지는 갈래

다음 편 (M18): HMM 기초 + Viterbi 알고리즘 — 서열 정렬의 확률 모델판. 각 위치의 상태를 확률로 다룹니다.
두 편 뒤 (M19): HMM Forward-Backward — 상태 확률의 전방·후방 계산.
실무 확장: --taxon-classify 옵션으로 메타게놈 taxonomy 분류, --iterate 옵션으로 PSI-BLAST 유사 반복 검색.

BLAST의 유산은 사라지지 않았습니다. Diamond를 쓴다는 것은 BLAST가 세운 알고리즘 뼈대 위에 하드웨어 시대의 재설계를 얹은 것에 지나지 않습니다. 다음 편에서는 뼈대 자체가 다른 확률 모델로 갈아탑니다.

더 깊게 파고 싶다면

본문은 BPD가 자체 재구성한 서술입니다. 원리를 이미 이해했다면 아래 원 논문과 정통 강의로 심화해도 좋습니다.

Buchfink, Xie, Huson (2015), Fast and sensitive protein alignment using DIAMOND, Nature Methods — 원 논문. Double indexing과 축약 알파벳 아이디어.
Buchfink, Reuter, Drost (2021), Sensitive protein alignments at tree-of-life scale using DIAMOND, Nature Methods — v2 논문. 5개 감도 모드와 SIMD 세부.
Diamond 공식 문서: https://github.com/bbuchfink/diamond/wiki — CLI 옵션 전량 · 감도 모드 벤치마크.
EMBL-EBI Training — 실무 튜토리얼 재생목록. 메타게놈 파이프라인 문맥에서 Diamond를 다룹니다.

시간이 있다면 UniRef50 같은 중간 크기 데이터베이스로 감도 모드별 히트 수와 실행 시간을 직접 재봅시다. Diamond가 파이프라인의 병목을 어디에서 얼마나 풀어내는지 체감하는 것이, 이 편이 목표한 진짜 학습입니다.

BioPlayground

Diamond와 단백질 초고속 검색: BLAST를 100～10,000배 앞지른 재설계