BLAST 알고리즘 완전 이해 — 휴리스틱 seed와 확장 원리 (한국어)

왜 이 편이 필요한가

M07에서 Smith-Waterman은 국소 정렬의 정확한 알고리즘이라고 했습니다. $O(mn)$ 시간이 필요합니다. 그런데 실무에서 만나는 서열 검색은 이런 형태입니다.

쿼리: 새로 찾은 유전자 하나 (~2,000bp)
참조: NCBI nr 데이터베이스 (~5 × 10¹¹ bp 이상, 계속 증가)

정확히 Smith-Waterman을 돌리면 $2000 \\times 5 \\times 10^{11} = 10^{15}$ 셀입니다. 최신 CPU로도 며칠 걸립니다. 이걸 실용적으로 뚫기 위해 나온 것이 BLAST (Basic Local Alignment Search Tool) 입니다. Stephen Altschul 등이 1990년에 발표했고, 지금도 바이오인포매틱스에서 가장 많이 인용되는 논문 중 하나입니다.

이 편에서 BLAST의 세 단계 — seed · extend · significance — 를 뜯어봅시다. 사고 방식은 지금 편(M10) · 다음 편(M11), 그리고 나중에 만날 BWA · minimap2까지 관통합니다.

아이디어 — Seed and Extend

BLAST의 핵심 통찰은 이렇습니다.

정말로 유사한 두 서열은, 그 안에 짧고 정확히 일치하는 조각(seed)이 반드시 존재한다.

그래서 BLAST는 이렇게 동작합니다.

Seed: 쿼리에서 짧은 k-mer들을 뽑고, 참조 데이터베이스에서 정확히 일치하는 위치를 인덱스로 빠르게 찾습니다.
Extend: 각 seed 위치 주변에서 Smith-Waterman으로 정렬을 확장합니다.
Significance: 얻은 정렬 점수의 통계적 유의성을 E-value로 재고, 유의한 것만 뱉습니다.

이렇게 하면 정렬 알고리즘 자체는 정확한 Smith-Waterman이지만, 적용 영역이 후보 위치 근처만입니다. 계산량이 극적으로 줄어듭니다.

1단계 — Seed의 크기 결정

k-mer의 크기 $k$ 가 결정적입니다. $k$ 가 작으면 seed가 너무 자주 매치돼서 후보가 폭발합니다. $k$ 가 크면 진짜 유사한 서열도 놓칠 수 있습니다.

BLASTN (DNA): 기본 $k = 11$ . megaBLAST는 $k = 28$ 까지 큽니다(고유사도 검색용).
BLASTP (단백질): 기본 $k = 3$ . 단, 여기서 seed는 정확 매치가 아니라 BLOSUM62 점수 임계 이상의 매치입니다.

왜 BLASTP의 seed 크기가 3인가? 아미노산 알파벳이 20종이라서 $20^3 = 8000$ 조합입니다. 이 정도면 참조 데이터베이스에서 각 조합이 나오는 위치를 해시 인덱스로 빠르게 찾을 수 있고, 진짜 유사한 단백질을 놓치지도 않는 균형점입니다.

2단계 — 두 방향 확장

각 seed에서 정렬을 확장합니다. 양쪽 방향(좌우) 으로 seed를 늘리면서, 정렬 점수의 누적을 관찰합니다.

점수가 계속 오르면 계속 확장.
점수가 드롭 임계(dropoff threshold) 를 넘어 떨어지면 확장 중단.

이 절차가 Smith-Waterman과 다른 점은 어디까지 확장할지를 확률적으로 결정한다는 것입니다. 정확한 국소 정렬은 아니지만, 대부분의 경우 진짜 최적 정렬과 매우 근접합니다.

BLAST 1.0(1990)은 갭 없는 확장만 지원했습니다. BLAST 2.0(1997, "gapped BLAST")부터 아핀 갭이 포함된 확장을 지원합니다. 오늘 우리가 쓰는 건 gapped BLAST입니다.

3단계 — Two-hit vs One-hit

효율성을 위해 gapped BLAST는 two-hit 기준을 씁니다.

한 대각선 위에서 두 개의 seed가 근접(예: 40bp 이내)해서 발견되어야만 확장을 시작한다.

즉 우연히 하나의 seed가 매치된 경우는 대부분 무시합니다. 실제로 유사한 서열은 여러 seed가 인접해서 발견될 확률이 높기 때문에, 이 필터가 대부분의 우연 매치를 걸러냅니다.

이 아이디어는 이후 BWA · minimap2에서도 반복됩니다. "짧은 정확 매치 여러 개를 신호로 삼는다"는 것이 seed-and-extend 계보의 근본 사고입니다.

파이썬으로 축소판 BLAST 만들기

실제 BLAST를 100줄로 재현하지는 못하지만, 원리를 이해하기 위한 축소판을 만들 수 있습니다.

python

from collections import defaultdict

def build_kmer_index(reference: str, k: int) -> dict[str, list[int]]:
    """참조 서열에서 k-mer → 위치 리스트 인덱스."""
    index = defaultdict(list)
    for i in range(len(reference) - k + 1):
        index[reference[i:i+k]].append(i)
    return index

def mini_blast(query: str, reference: str, k: int = 11, extend: int = 20) -> list[dict]:
    """축소판 BLAST — seed 매치 위치를 찾고 좌우로 확장."""
    index = build_kmer_index(reference, k)
    hits = []
    for q_pos in range(len(query) - k + 1):
        seed = query[q_pos:q_pos+k]
        for r_pos in index.get(seed, []):
            # 좌우 확장 (단순화 — 실제 BLAST는 dropoff 임계 사용)
            left = max(0, min(q_pos, r_pos) - extend)
            right = min(len(query), q_pos + k + extend)
            q_seg = query[q_pos - (min(q_pos, r_pos) - left):right]
            r_seg = reference[r_pos - (min(q_pos, r_pos) - left):
                              r_pos + k + (right - q_pos - k)]
            matches = sum(a == b for a, b in zip(q_seg, r_seg))
            hits.append({
                "q_pos": q_pos, "r_pos": r_pos,
                "identity": matches / max(len(q_seg), 1),
                "length": len(q_seg),
            })
    return hits

# 사용
reference = "AAAAGGCCTTGGCCAATTGGCCTTAAAA"
query = "GGCCTT"
for hit in mini_blast(query, reference, k=6, extend=5):
    print(hit)

이 축소판이 실제 BLAST와 다른 점:

BLASTP의 근접(neighbor) seed 확장 없음
Two-hit 필터 없음
E-value 통계 없음 (다음 편)
아핀 갭 없음
인덱스가 인메모리 (실제 BLAST는 디스크 mmap)

그래도 아이디어의 핵심 — 인덱스로 seed 찾고 그 주변만 확장 — 은 그대로입니다.

NCBI BLAST 웹으로 실습

가장 쉬운 실습은 NCBI BLAST 웹입니다.

NCBI BLAST로 가서 blastn 또는 blastp 선택.
관심 서열(예: BRCA1 인간 CDS의 200bp 조각)을 붙여넣기.
데이터베이스는 nr 또는 refseq_rna.
실행하면 몇 초～몇 분 안에 정렬된 결과가 나옵니다.

결과에서 관찰할 것:

Score: 정렬 점수(BLOSUM62 로그 우도비 합)
E-value: 통계적 유의성 (다음 편에서)
Identity: 매치 비율
Alignment: 시각적 정렬 결과

각 hit의 Score가 BLOSUM62 로그 우도비 합이라는 것을 M09 편의 눈으로 다시 봐두면 좋습니다.

BLAST의 한계와 후속 도구들

BLAST는 1990년대의 게놈 스케일에 맞춰 설계됐습니다. 오늘의 짧은 리드 시퀀싱(Illumina) · 롱리드(Nanopore/PacBio) 규모에는 새 도구들이 나왔습니다.

BWA-MEM (2013): 짧은 리드 정렬 표준. seed-and-extend + FM-index. M14～M15 편.
Bowtie2 (2012): BWA와 비슷한 시대. FM-index + 국소 정렬.
minimap2 (2018): 롱리드 표준. 미니마이저 seed + 아핀 이중선 갭. M16 편.
DIAMOND (2015): 단백질 대규모 검색용 BLAST 대체. 인덱싱 최적화로 100배 이상 빠름. M17 편.

이들 모두 BLAST의 seed-and-extend 사고를 계승했습니다. BLAST는 그 아이디어의 원조입니다.

자주 만나는 실무 함정

저복잡도 필터: BLAST의 기본 옵션에는 저복잡도 마스킹(dust · seg)이 켜져 있습니다. 이걸 끄면(-dust no) 반복 서열이 결과를 오염시킵니다.
데이터베이스 크기와 E-value: E-value는 검색한 데이터베이스 크기에 비례합니다. nr(전체) vs refseq(고품질만)의 E-value가 다른 이유. 다음 편에서 자세히.
word_size 튜닝: -word_size 옵션으로 seed 크기를 조절할 수 있습니다. 유사도가 낮은 서열 검색에는 작게(예: 7), 매우 유사한 서열은 크게(예: 28) 설정합니다.
로컬 vs 원격: NCBI BLAST 웹은 트래픽에 따라 느립니다. 매일 대량 검색이 필요하면 BLAST+ CLI로 로컬 실행(M12에서 다룹니다). 서버 부담도 줄이고 재현성도 좋습니다.

CS 매핑

해시 기반 인덱스: k-mer → 위치 리스트는 정확히 해시 테이블입니다. CS에서 배운 그대로.
Seed-and-extend: "빠른 근사 필터 + 정확한 확장"의 전형입니다. 얼굴 인식 · 문서 검색 · 코드 검색 모두 같은 골격.
확률적 필터링: two-hit 기준은 거짓 양성을 줄이기 위한 확률적 필터입니다. Bloom filter · MinHash · locality-sensitive hashing과 같은 계보.

다음 편으로 이어지는 갈래

다음 편 (M11): BLAST E-value 통계 — 정렬 점수를 어떻게 확률로 바꾸는가.
두 편 뒤 (M12): 로컬 BLAST+ 서버 — 자신의 데이터베이스로 로컬 BLAST 구축.
세 편 뒤 (M13): 접미사 트리 · 배열 — BLAST 인덱스의 정교화.
다섯 편 뒤 (M15): FM-index — BWA · Bowtie2의 자료구조.

더 깊게 파고 싶다면

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

Harvard STAT115 — Xiaole Shirley Liu 교수의 Week 3: BLAST Algorithm Deep Dive (자막 완비, 자동 번역 우수). Seed · extend · 통계까지 정통.
원 논문: Altschul, S. F. et al. (1990), Basic Local Alignment Search Tool, J Mol Biol 215, 403–410. BLAST의 시조.
원 논문: Altschul, S. F. et al. (1997), Gapped BLAST and PSI-BLAST, Nucleic Acids Res 25, 3389–3402. Gapped BLAST의 시조.
NCBI Handbook — The BLAST Sequence Analysis Tool. 실무 파라미터 튜닝의 정통.
참고 교재: Durbin et al. Biological Sequence Analysis Chapter 4.

NCBI BLAST 웹에서 관심 서열을 검색해보고, 결과의 Score와 E-value가 어떻게 계산됐는지 다음 편 M11의 준비로 삼읍시다. 손을 움직여야 다음 편의 통계가 살아 있는 지식이 됩니다.

BioPlayground

BLAST 알고리즘: 휴리스틱 seed와 확장으로 게놈 스케일을 뚫습니다