BLAST 알고리즘의 탄생 배경
BLAST(Basic Local Alignment Search Tool) 알고리즘은 1990년경 미국 국립생물공학정보센터(NCBI)의 Altschul, Gish, Miller 등에 의해 개발되었습니다. BLAST는 서열 간의 기능적·진화적 관계를 도출하고, 유전자 패밀리(family)의 구성원을 식별하는 데 널리 활용되는 대표적인 생물정보학 도구입니다.
NCBI가 제공하는 BLAST 데이터베이스
NCBI 웹사이트에는 여러 표준 BLAST 데이터베이스가 마련되어 있습니다. 데이터 성격에 따라 핵산(nucleotide) 데이터베이스와 단백질(protein) 데이터베이스로 구분됩니다. 이 외에도 벡터 스크리닝(vector screening) 데이터베이스, 다양한 생물종의 게놈(genome) 데이터베이스, 트레이스(trace) 데이터베이스 등 특수 목적의 BLAST 데이터베이스도 함께 지원됩니다.
BLAST의 작동 원리: 휴리스틱 검색 방식
BLAST는 휴리스틱(heuristic) 접근법을 사용하여 질의(query) 서열과 데이터베이스 사이에서 가장 큰 국소 정렬(local alignment)을 빠르게 찾아냅니다. 검색 속도를 높이기 위해 비교 대상 서열을 '워드(word)'라 불리는 작은 조각들로 나누고, 먼저 이 워드들 사이의 일치 여부를 탐색하는 방식을 채택합니다.
워드(k-tuple)와 해시 테이블
BLAST에서 워드는 k-tuple 형태로 처리됩니다. DNA 염기서열의 경우 하나의 워드는 일반적으로 11개 염기로 구성되며, 단백질 서열의 경우에는 3개 아미노산으로 구성됩니다. BLAST는 근방(neighborhood) 워드, 즉 거의 일치하는 워드들의 해시 테이블을 생성하고, '근접성'의 기준은 통계학적 근거에 따라 설정됩니다. 탐색은 정확한 일치에서 출발하여 근방 워드로 확장됩니다.
통계 기반 판정과 선형 시간 탐색
좋은 정렬은 반드시 여러 개의 근접 일치를 포함하기 때문에, 통계를 활용하면 어떤 일치가 유의미한 것인지 판단할 수 있습니다. 해싱(hash) 기법 덕분에 일치 항목을 O(n)의 선형 시간 안에 발견할 수 있으며, 일치 영역을 양방향으로 확장함으로써 높은 점수의 최대 분절쌍(high-scoring segment pairs, HSP)을 다수 포함하는 고품질 정렬을 찾아냅니다.
BLAST의 다양한 버전과 확장형
BLAST 알고리즘은 여러 버전과 확장형으로 발전해 왔습니다. 예를 들어 MEGABLAST, Discontinuous MEGABLAST, BLASTN은 모두 핵산 서열을 식별하는 데 사용할 수 있습니다. 그중 MEGABLAST는 매우 유사한 서열 간의 긴 정렬을 효율적으로 찾도록 특별히 설계되었기 때문에, 질의 서열과 동일한 매치를 찾는 데 가장 적합한 도구로 평가됩니다.
워드 크기와 검색 민감도의 관계
BLAST 검색의 민감도(sensitivity)를 좌우하는 핵심 매개변수 중 하나는 초기 워드의 길이, 즉 워드 크기(word size)입니다. BLASTN에서는 워드 크기를 자유롭게 조정할 수 있으며, 기본값에서 최소 7까지 낮추어 검색 민감도를 높일 수 있습니다. 이러한 이유로 BLASTN은 서로 다른 생물종 간의 유연관계 있는 핵산 서열 정렬을 찾는 데 있어 MEGABLAST보다 우수한 성능을 보입니다.
단백질 검색 도구: BLASTP, PSI-BLAST, PHI-BLAST
표준 단백질-단백질 BLAST인 BLASTP는 질의 아미노산 서열을 식별하고, 단백질 데이터베이스에서 유사한 서열을 찾는 데 사용됩니다. 위치특이 반복(Position-Specific Iterated, PSI)-BLAST는 더 높은 민감도의 단백질 유사성 검색을 위해 개발된 도구로, 진화적으로 매우 멀리 떨어져 있는 단백질을 발견하는 데 특히 유용합니다.
패턴히트 개시(Pattern-Hit Initiated, PHI)-BLAST는 제한적인 단백질 패턴 검색을 수행할 수 있습니다. 사용자가 직접 정의한 패턴을 포함하면서, 해당 패턴의 인근 영역에서 질의 서열과 유사한 단백질을 찾아내도록 설계되어 있습니다.