BioPlayground

🧬
목록으로

다중 서열 정렬: ClustalW·MAFFT의 progressive alignment 원리와 실무

왜 3개 이상 서열은 pairwise가 아니라 progressive로 하는가. Guide tree 만들기, 점진적 병합, MAFFT의 FFT 최적화까지.

중급
|
18분
|
검증 완료 (2026-07-20)
multiple sequence alignmentphylogenetic treeprogressive alignment
진행률0/34 (0%)

왜 3개 이상 서열은 다른 이야기인가

M06～M09에서 두 서열의 정렬(pairwise alignment)을 다뤘습니다. Needleman-Wunsch로 격자 채우기. 그런데 실무에서는 여러 서열을 동시에 정렬해야 하는 경우가 훨씬 많습니다. 단백질 패밀리 진화 연구, 계통수 재구성, HMM 프로파일 훈련. 이때 필요한 것이 다중 서열 정렬(Multiple Sequence Alignment, MSA) 입니다.

이 편에서는 왜 pairwise를 여러 번 하는 것이 답이 아닌지, ClustalW가 처음 제시한 progressive alignment 전략이 어떻게 작동하는지, 그리고 왜 MAFFT가 오늘의 표준이 되었는지 다룹니다. Micro §M.6의 시작입니다.

Pairwise 여러 번은 왜 안 되는가

서열 A, B, C 세 개가 있을 때, A-B 정렬 · B-C 정렬 · A-C 정렬 각각 따로 하면 어떻게 될까요? 세 결과가 서로 모순됩니다.

예를 들어 A-B에서는 A의 5번째 자리에 갭이 생겼는데, A-C에서는 A의 5번째 자리에 문자가 그대로 남아있을 수 있습니다. 세 서열을 하나의 정렬표에 담으려면 갭 위치가 일관돼야 합니다.

정공법은 N차원 격자를 채우는 겁니다. Needleman-Wunsch의 확장. 서열 3개면 3차원 격자, 4개면 4차원, N개면 N차원. 시간·공간 복잡도가 O(L^N)으로 폭발합니다. 5개 서열, 각 500bp만 되어도 계산 불가능.

정확한 MSA는 NP-완전입니다. 그래서 실전 도구는 전부 근사 알고리즘. Progressive alignment가 그 대표작입니다.

Progressive Alignment — 3단계 전략

ClustalW(1994년, Higgins et al.)가 제시한 전략은 이렇습니다.

  1. Distance matrix: 모든 서열 쌍 사이의 pairwise 정렬 점수(또는 거리)를 계산
  2. Guide tree: 거리 행렬로 계통수를 만든다 (보통 NJ 또는 UPGMA 방식)
  3. Progressive merge: guide tree를 leaf에서 root로 순회하면서 가장 가까운 서열/그룹부터 하나씩 정렬을 병합

핵심 아이디어: 가까운 것부터 정렬한 뒤 그 정렬을 계속 유지하면서 먼 서열을 추가한다. 그러면 격자 확장이 필요 없고, 매 병합이 pairwise 정렬 하나로 끝납니다.

간단한 예제로 감 잡기

서열 4개, 각 6bp.

text
S1: ACGTAC
S2: ACGTAG
S3: ACCTAG
S4: TCCTAG

Step 1 — 거리 계산:

pairwise 정렬 점수(예: 일치 -1, 불일치 +1의 편집 거리 스타일)로 6개 쌍 계산.

S1S2S3S4
S10123
S21012
S32101
S43210

Step 2 — Guide tree 구성:

거리 행렬에서 가장 가까운 쌍부터 이어붙입니다. NJ 방식. 결과는 대략:

text
((S1, S2), (S3, S4))

Step 3 — 점진적 병합:

  1. 가장 가까운 쌍 정렬: S1-S2 정렬 → ACGTAC / ACGTAG
  2. 또 다른 쌍: S3-S4 정렬 → ACCTAG / TCCTAG
  3. 두 정렬 그룹을 병합 (profile-profile alignment)
text
ACGTAC
ACGTAG
ACCTAG
TCCTAG

이렇게 하나의 MSA가 완성됩니다. 각 단계가 pairwise 정렬(N-W 알고리즘)이라서 계산 가능한 규모입니다.

Profile-profile alignment

Progressive merge의 3번 단계에서 두 정렬 그룹을 병합할 때, 각 그룹은 이미 여러 서열의 정렬. 이걸 하나의 컬럼별 profile(각 컬럼의 아미노산 빈도)로 요약하고, profile끼리 정렬합니다.

Profile A와 profile B의 정렬 점수는 컬럼별 확률 벡터의 내적(또는 log-odds ratio 합)으로 정의. Needleman-Wunsch의 격자 채우기 뼈대는 그대로, 점수 함수만 확장됩니다.

이 트릭 덕분에 그룹 크기와 무관하게 매 병합 단계가 pairwise alignment의 시간·공간 복잡도 O(mn)으로 유지됩니다.

Progressive alignment의 함정 — "Once a gap, always a gap"

ClustalW의 결정적 약점이 있습니다. 초기에 잘못 넣은 갭은 이후에 절대 수정되지 않습니다. Guide tree 상에서 잘못된 순서로 병합했다면, 그 갭이 계속 살아남습니다.

이 문제를 해결하는 두 가지 접근이 나왔습니다.

Iterative refinement (MUSCLE, T-Coffee): 초기 MSA를 만든 뒤 서열을 하나씩 다시 빼서 정렬하고 재삽입. 반복.

Consistency-based scoring (T-Coffee, ProbCons): pairwise 정렬 점수의 일관성(다른 서열을 경유해서 얻은 점수와 직접 점수의 일치도)을 함께 최적화.

MAFFT — 오늘의 표준

Katoh & Standley(NAR 2013)가 개발한 MAFFT가 지금 사실상 표준입니다. 이유 세 가지.

  1. FFT 최적화: 서열을 부피 밀도 벡터로 변환한 뒤 Fast Fourier Transform으로 고속 유사도 계산. Pairwise 정렬을 미리 그린 홈에서 안내
  2. 다양한 모드: --auto가 서열 수·길이에 맞춰 알고리즘을 자동 선택 (FFT-NS-2, L-INS-i 등)
  3. iterative refinement: FFT로 대량 서열을 빠르게 처리한 뒤, 정확도가 필요하면 iterative refinement 옵션(--maxiterate 1000 --localpair)

실무 감:

  • 서열 수백 개 이하 + 정확도 우선: mafft --localpair --maxiterate 1000 input.fasta > out.fasta (L-INS-i)
  • 서열 수천～수만 개 + 속도 우선: mafft --auto input.fasta > out.fasta
  • 매우 큰 세트: mafft --retree 1 --parttree 옵션으로 파티션 분할

실습 — MAFFT CLI

bash
# 설치 (Colab이나 Ubuntu)
sudo apt-get install mafft
mafft --version


# 소규모 정렬 (10개 이하 서열)
mafft --localpair --maxiterate 1000 my_proteins.fasta > my_msa.aln


# 대규모 정렬 (auto 모드)
mafft --auto my_proteins.fasta > my_msa.aln


# Stockholm 포맷으로 HMMER 호환 저장
mafft --auto --outputformat stockholm my_proteins.fasta > my_msa.sto

결과 정렬 파일을 열어보면 서열 앞에 갭(-)이 들어가서 각 컬럼이 상동 자리를 이루고 있음을 볼 수 있습니다. Jalview 같은 뷰어로 시각화하면 보존 영역·변이 영역이 색으로 드러납니다.

정렬 품질 평가

MSA는 정답이 없는 문제입니다(정확한 MSA는 NP-완전). 그럼에도 벤치마크 세트가 있습니다.

  • BAliBASE: 수작업 큐레이션된 정답 MSA 세트. 새 알고리즘의 표준 벤치마크
  • SP score: sum-of-pairs, 정답과 겹치는 페어 비율
  • TC score: 완전히 맞은 컬럼의 비율 (더 엄격)

MAFFT L-INS-i가 BAliBASE에서 top-tier. ClustalW는 legacy 도구(속도는 빠르지만 정확도 하락).

복잡도

  • Pairwise 거리 계산: N개 서열 × O(L²) = O(N² × L²). 이 단계가 실제 병목
  • Guide tree 구축: O(N³) (NJ) 또는 O(N² log N) (fast NJ)
  • Progressive merge: N-1번의 pairwise = O(N × L²)
  • 총: O(N² × L²)

MAFFT의 FFT 최적화가 pairwise 계산의 상수 팩터를 몇 배 줄입니다. 실무에서 서열 1000개 × 길이 500bp가 노트북에서 분 단위.

MSA는 왜 이후 모든 것의 재료인가

다중 서열 정렬은 그 자체가 목적이 아니라 다른 분석의 입력입니다.

  • 계통수: MSA의 컬럼별 변이 패턴이 계통수의 재료 (M26～M28)
  • HMM Profile: 도메인 HMM은 MSA에서 방출·전이 확률 학습 (M21)
  • 보존 분석: 컬럼별 보존도로 기능 자리 예측
  • AlphaFold2 MSA: 단백질 구조 예측의 결정적 재료 (F02)

MSA 품질이 이후 모든 분석의 상한을 결정합니다. 정렬이 잘못되면 아래에 세운 것이 다 흔들립니다.

CS 매핑 — 탐욕적 트리 순회

DryBench의 탐욕 알고리즘과 트리 순회의 결합입니다.

  • 탐욕: 매 단계 지역 최적(가장 가까운 쌍) 선택
  • 트리 순회: guide tree의 post-order로 병합 순서 결정
  • 점진적 병합: 이미 결정된 정렬은 수정 불가 (그래서 "once a gap, always a gap")

이 알고리즘의 함정은 명확합니다. 지역 최적의 연쇄가 전역 최적이 아닐 수 있습니다. Iterative refinement는 이 함정을 사후에 부분적으로 벗어나려는 시도입니다.

Rosalind에서 채점받기

MSA 자체는 Rosalind 문제가 없지만, MULT(BA5G) 같은 문제로 3-way 정렬의 격자 채우기를 손 유도해볼 수 있습니다. progressive alignment의 필요성을 몸으로 느끼는 실습.

다음 편으로 이어지는 갈래

  • 다음 편 (M26): 계통수 거리 기반 — NJ, UPGMA — MSA의 컬럼 정보를 거리 행렬로 바꿔서 트리 구축
  • 두 편 뒤 (M27): 파시모니 — Fitch, Sankoff — 최소 변이 수를 기준으로 트리 평가
  • 세 편 뒤 (M28): 최대우도 — IQ-TREE, RAxML — 통계적 우도를 최대화하는 트리

MSA → 계통수의 파이프라인이 M25～M28의 이야기입니다. MSA는 재료 준비 단계, 이후 3편이 트리 알고리즘 3대 접근.

더 깊게 파고 싶다면

  • Thompson, Higgins, Gibson (1994), CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment, NAR — ClustalW 원 논문. 지금 봐도 유효.
  • Katoh & Standley (2013), MAFFT multiple sequence alignment software version 7, NAR — MAFFT v7 논문. 실전 최고 성능.
  • Edgar (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput, NAR — MUSCLE 원 논문. iterative refinement의 정수.
  • EMBL-EBI Training — MSA 실전 재생목록 (자막 완비).
  • MIT 7.91J — Christopher Burge 교수의 MSA 편. progressive alignment의 함정을 판서로 봅니다.

MAFFT로 유명 단백질 패밀리(예: 헤모글로빈, p53)의 상동체 100개를 정렬해봅시다. 그 결과를 Jalview로 열어서 어느 컬럼이 보존되어 있는지 눈으로 확인하는 것이, 이 편의 진짜 실습입니다.