10강 / 20강

k-mer 색인을 직접 짓는다

31 글자로 자르고 사전에 담는다 · 왜 하필 31인가

발상은 단순합니다.

참조 전사체를 31 글자씩 잘라 사전에 담는다.
사전의 열쇠는 31 글자, 값은 그 조각이 나온 유전자 이름.

그러면 read 하나가 왔을 때, read 안의 31 글자를 하나 떼어 사전에서 찾아보기만 하면 됩니다. 사전 조회는 즉시 끝납니다.

고등학생k-mer 라는 발상

read 를 유전자에 붙이려면 무엇을 비교해야 하나? 76글자 전체를 290개 유전자 서열 전체와 하나씩 대보면 너무 느리다. 그래서 짧게 잘라서 사전을 만든다.

k-mer 란

서열을 k 글자씩 겹치게 잘라낸 조각이다. ACGTAC 를 k=3 으로 자르면 ACG, CGT, GTA, TAC — 네 개. 한 글자씩 밀면서 자르니 조각 수는 (길이 − k + 1) 개다.

단계	하는 일
색인 만들기	참조 유전자를 k-mer 로 잘라 사전에 저장
조회	read 의 k-mer 를 사전에서 찾음
판정	가장 많이 맞은 유전자로 결정

책 뒤 색인과 똑같다. 책 전체를 읽지 않고 단어로 찾아간다.

비교를 검색으로 바꾸는 것 — 이것이 현대 서열 분석의 기본 기법이다

TTTGCA 는 두 유전자에 다 들어 있습니다 — 13강의 문제가 벌써 보이네요.

Python 브라우저에서 실행

# 아주 작은 예로 원리를 봅니다.
ref = {"유전자A": "ACGTACGTTTGCA", "유전자B": "TTTGCAGGGTACC"}
K = 6

idx = {}
for g, s in ref.items():
    for i in range(len(s) - K + 1):
        idx.setdefault(s[i:i+K], set()).add(g)

print(f"{len(idx)} 개의 {K}-mer 가 사전에 들어갔습니다")
for kmer in sorted(idx):
    print(f"  {kmer}  →  {sorted(idx[kmer])}")

실제 색인입니다. 8칸마다 담아도 76bp read 는 여러 번 걸립니다.

Python 브라우저에서 실행

import bu, time

t = time.time()
idx = bu.index()                    # k=31, 8칸마다
print(f"색인 항목 {len(idx):,}개   ({time.time()-t:.1f}초)")
print()
print("사전에서 몇 개 꺼내 보면")
for kmer in list(idx)[:4]:
    print(f"  {kmer}  →  {idx[kmer]}")
print()
p = bu.panel()
print(f"참조 총 염기 {sum(len(s) for s in p.values()):,} 인데 항목은 {len(idx):,}개 —")
print("8 칸마다 하나씩만 담았기 때문입니다.")

고등학생왜 하필 31인가

k 를 정하는 것은 맞바꿈 이다.

	k 가 작으면	k 가 크면
우연히 일치	많음 — 가짜 매칭	적음
오류에 견딤	강함	약함 — 한 글자만 틀려도 실패
사전 크기	작음	큼

숫자로 따져 보자

k 글자짜리 조각의 가능한 종류는 4^k 다. k=31 이면 4³¹ ≈ 4.6 × 10¹⁸. 사람 유전체는 30억 글자, 즉 30억 개의 31-mer 가 있다. 가능한 종류가 실제 개수보다 10억 배 많다.

그러니 우연히 같은 31-mer 가 두 곳에 나올 확률은 사실상 0 이다. 31-mer 하나가 유전체 한 자리를 거의 확정한다.

홀수인 이유

k 가 홀수여야 어떤 k-mer 도 자기 자신의 역상보와 같아질 수 없다. 짝수면 회문(palindrome)이 생겨서 가닥 판정이 애매해진다. 31, 25, 21 처럼 홀수를 쓰는 관행은 여기서 나온다.

31 은 마법의 수가 아니라 "충분히 유일하고 아직 견딜 만한" 지점이다

숫자로 보면 왜 작은 k 가 쓸모없는지 바로 보입니다.

Python 브라우저에서 실행

import bu

# k 를 바꿔 가며 '우연히 맞을' 위험을 재어 봅니다
p = bu.panel()
total = sum(len(s) for s in p.values())

print(f"{'k':>3}{'가능한 조합':>16}{'참조 염기':>12}{'우연히 있을 확률':>18}")
print("-" * 52)
for k in [8, 12, 16, 20, 25, 31]:
    combos = 4 ** k
    print(f"{k:>3}{combos:>16,}{total:>12,}{min(1, total/combos):>17.6f}")
print()
print("k=16 이면 이미 우연은 사실상 사라집니다.")
print("31 을 쓰는 것은 우연 때문이 아니라 '반복 서열과 유사 유전자' 때문입니다.")

read 안 오류 하나의 파급 범위를 세어 봅니다.

Python 브라우저에서 실행

import bu

# 오류 하나가 k-mer 를 몇 개 망가뜨리나
K = 31
L = 76
print(f"{L}bp read 안의 {K}-mer 개수 : {L - K + 1}")
print()
for pos in [0, 10, 38, 60, 75]:
    broken = sum(1 for i in range(L - K + 1) if i <= pos < i + K)
    print(f"  {pos+1:>3}번 자리에 오류 → {broken:>2}개 깨짐 → {L-K+1-broken:>2}개 남음")
print()
print("가운데에서 틀리면 31개가 다 깨지지만, 그래도 15개가 남습니다.")
print("끝에서 틀리면 거의 손해가 없고요. 이것이 k-mer 방식이 오류에 강한 이유입니다.")

고등학생사전을 어떻게 담나

파이썬에서는 딕셔너리(dict)로 담는다. 열쇠는 k-mer 문자열, 값은 유전자 이름. 조회가 상수 시간 이라는 것이 핵심이다.

왜 상수 시간인가

해시 함수가 문자열을 숫자로 바꾸고, 그 숫자가 곧 저장 위치가 된다. 사전에 항목이 100개든 1억 개든 찾는 시간이 같다. /ds 과목의 해시 테이블이 정확히 이 이야기다.

자료 구조	조회 시간	1억 항목에서
리스트를 처음부터 훑기	O(n)	1억 번 비교
정렬된 리스트 이분 탐색	O(log n)	약 27번
해시 사전	O(1)	1번

대가는 메모리

사람 유전체 전체를 31-mer 사전으로 만들면 수십 GB 다. 그래서 진짜 도구들은 압축된 색인(FM-index, minimizer 등)을 쓴다. 원리는 같고 저장 방식만 영리해진 것이다.

속도를 사는 값은 언제나 메모리다

🎮 k-mer 실험실

k 를 바꿔 가며 색인 크기와 충돌을 확인하세요.

고등학생k-mer 가 쓰이는 다른 곳들

k-mer 색인은 RNA-seq 정량 말고도 널리 쓰인다.

분야	쓰임
de novo 조립	k-mer 를 이어 붙여 유전체를 복원 (de Bruijn 그래프)
메타지놈 분류	k-mer 로 어느 세균에서 왔는지 판정 (Kraken)
시료 오염 탐지	다른 종의 k-mer 가 섞였나
유전체 크기 추정	k-mer 빈도 분포로 조립 전에 추정

공통된 발상 하나

전부 "긴 것을 짧은 조각으로 쪼개면 비교가 검색이 된다" 는 같은 발상이다. 서열 분석에서 이보다 널리 쓰인 아이디어는 드물다.

텍스트 검색 엔진이 문서를 단어로 쪼개 색인하는 것, 표절 검사기가 문장을 겹치는 조각으로 자르는 것도 같은 구조다. 분야가 달라도 같은 문제에는 같은 해법 이 나온다.

쪼개기 → 색인 → 조회. 이 세 걸음이 대용량 비교의 표준 답이다

🤔 확인 문제

k 가 너무 작으면 생기는 문제는?

🤔 확인 문제

read 한가운데 염기 하나가 틀렸을 때 31-mer 는 몇 개가 깨지는가?

🤔 확인 문제

색인을 8칸마다 만들어도 되는 이유는?