짧은 요약(Abstract) :    
* BLAST는 지역 유사성을 최적화하는 새로운 빠른 시퀀스 비교 방법으로, 최대 세그먼트 쌍 점수를 근사  
* 이 방법은 MSP 점수의 확률적 특성 분석을 통해 성능과 생성된 정렬의 통계적 유의성을 평가    
* BLAST는 단순하고 다양한 상황에서 적용 가능하며, 기존 도구보다 훨씬 빠른 속도를 제공  
Useful sentences :  
*


Paper link
Lecture link


단어정리

  • negligible: 하찮은, 미미한
  • auxiliary: 보조적인, 부가적인
  • delimi: 한계를 정하다


1. Introduction

  • 단백질 또는 단백질 가족과의 시퀀스 상동성 발견이 새로운 유전자의 기능에 대한 첫 번째 단서를 제공
  • DNA와 아미노산 시퀀스 데이터베이스가 커질수록, 새로운 유전자와 단백질 분석에 더 유용해지며, 이러한 상동성을 찾을 가능성이 더 높아짐
  • 시퀀스 데이터베이스를 검색하는 다양한 소프트웨어 도구들이 있지만, 모두 시퀀스 간의 유사성을 측정하는 어떤 기준을 사용하여 생물학적으로 유의미한 관계와 우연한 유사성을 구별
  • 가장 잘 연구된 측정 기준 중 하나는 동적 프로그래밍 알고리즘의 변형과 함께 사용되는 것으로, 이러한 방법들은 삽입, 삭제, 치환에 점수를 할당하고 두 시퀀스의 최소 비용 집합에 해당하는 정렬을 계산
  • 이러한 정렬은 비교되는 두 시퀀스 간의 진화적 거리를 최소화하거나 유사성을 최대화하는 것으로 간주

2. Methods

(a) The maximal segment pair measure

  • 최대 세그먼트 쌍(Maximal Segment Pair, MSP) 측정 방법은 시퀀스 유사성을 평가하는 일반적인 방식으로, 전역 유사성과 지역 유사성으로 분류
  • 전역 유사성 알고리즘은 두 시퀀스 전체의 정렬을 최적화하지만, 지역 유사성 알고리즘은 상대적으로 보존된 부분 서열만을 탐색하며, 단일 비교에서 여러 개의 독립적인 부분 서열 정렬을 생성할 수 있음
  • BLAST에서 사용하는 MSP 측정은 모든 가능한 잔기 쌍에 대해 정의된 유사성 점수 행렬로 시작

  • 이 행렬에서 정체성과 보존적 치환은 긍정적인 점수를 받고, 비현실적인 치환은 부정적인 점수를 받음

  • MSP는 두 시퀀스에서 선택된 동일 길이의 세그먼트 쌍 중 가장 높은 점수를 가진 쌍을 의미하며, MSP의 경계는 그 점수를 최대화하기 위해 선택
    *MSP 점수는 지역 유사성의 척도를 제공하며, BLAST는 이 점수를 휴리스틱 방법으로 계산하려고 시도
  • 두 단백질 간의 가장 높은 점수를 가진 쌍뿐만 아니라 모든 보존된 영역에 관심이 있을 수 있으므로, 점수를 향상시키거나 줄임으로써 개선될 수 없는 세그먼트 쌍을 지역적으로 최대로 정의

  • BLAST는 특정 절단 값 이상의 모든 지역적으로 최대 세그먼트 쌍을 탐색할 수 있음

  • MSP 점수와 같은 여러 유사성 측정은 간단한 동적 프로그래밍 알고리즘을 사용하여 두 시퀀스의 길이 곱에 비례하는 시간 내에 계산될 수 있음
  • MSP 측정의 중요한 장점 중 하나는 최근 수학적 결과를 통해 적절한 무작위 시퀀스 모델 하에서 MSP 점수의 통계적 유의성을 추정할 수 있고 특정 점수 행렬(예: PAM-120)에 대해 최대 세그먼트 내 쌍을 이루는 잔기의 빈도를 추정할 수 있으며, 이는 BLAST 알고리즘의 핵심적인 특징

(b) Rapid approximation of MSP scores

  • MSP 점수의 빠른 근사화는 대규모 시퀀스 데이터베이스를 검색할 때, 소수의 시퀀스만이 조회 시퀀스와 상동성을 보일 것임을 고려한 BLAST의 핵심 전략
  • 연구자는 특정 임계값 S 이상의 MSP 점수를 가진 시퀀스 항목만을 식별하는 데 관심이 있으며, 이러한 시퀀스에는 조회 시퀀스와 매우 높은 유사성을 공유하는 시퀀스뿐만 아니라, 경계선에 있는 점수를 가진 시퀀스도 포함될 수 있음
  • 후자의 집합에는 높은 점수를 받은 무작위 일치 시퀀스와 조회 시퀀스와 멀리 관련된 시퀀스가 포함될 수 있음

  • 높은 점수를 받은 시퀀스의 생물학적 중요성은 거의 유사성 점수를 기반으로 추론될 수 있으며, 경계선에 있는 시퀀스의 생물학적 맥락은 생물학적으로 흥미로운 관계를 구별하는 데 도움이 될 수 있음

  • BLAST는 고정된 길이 w의 ‘단어 쌍’(word pair)이라고 하는 세그먼트 쌍을 통해 이러한 근사화를 달성
  • BLAST의 주요 전략은 적어도 T 이상의 점수를 가진 단어 쌍을 포함하는 세그먼트 쌍만을 찾는 것
  • 시퀀스를 스캔하면서, w 길이의 단어가 조회 시퀀스와 쌍을 이루어 T 이상의 점수를 가진 단어 쌍을 생성할 수 있는지 빠르게 결정
  • 이러한 적중(hit)은 S 이상의 점수를 가진 세그먼트 쌍 내에 포함되어 있는지를 결정하기 위해 확장
  • T의 임계값이 낮을수록 S 이상의 점수를 가진 세그먼트 쌍이 적어도 T 이상의 점수를 가진 단어 쌍을 포함할 가능성이 높아짐
  • 그러나 T의 작은 값은 적중 횟수와 따라서 알고리즘의 실행 시간을 증가
  • 무작위 시뮬레이션을 통해 이러한 고려 사항을 균형있게 조정할 수 있는 T 임계값을 선택할 수 있음

(c) Implementation

  • BLAST 구현은 세 가지 알고리즘 단계(높은 점수를 가진 단어 목록 작성, 데이터베이스에서 적중 찾기, 적중 확장)에 따라 달라질 수 있는데, 이는 데이터베이스가 단백질 시퀀스를 포함하고 있는지 DNA 시퀀스를 포함하고 있는지에 따라 다름
  • 단백질의 경우, 목록은 조회 시퀀스의 어떤 단어와 비교했을 때 최소한 T 점수를 얻는 모든 단어들로 구성
  • 따라서 조회 단어는 목록에 단어가 없을 수도 있고(PAM-120 점수를 사용하는 일반적인 단어들의 경우) 많은 단어로 표현될 수도 있음

  • 우리가 가장 유용하다고 판단한 w와 T 값에 대해, 일반적으로 조회 시퀀스의 각 잔기마다 목록에 약 50개의 단어가 있으며, 예를 들어 길이가 250인 시퀀스의 경우 12,500개의 단어가 됨

  • 스캔 단계에서는 긴 시퀀스에서 특정 짧은 시퀀스의 모든 발생을 찾는 전형적인 알고리즘 문제가 제기

  • 우리는 두 가지 접근 방식을 조사
    ** 첫 번째 접근 방식을 단순화하면, w=4로 가정하고 각 단어를 1부터 204 사이의 정수로 매핑하여 크기가 204인 배열에 인덱스로 사용
    ** 이 배열의 i번째 항목은 조회 시퀀스에서 i번째 단어의 모든 발생을 가리키도록 함
    **     따라서 데이터베이스를 스캔할 때 데이터베이스의 각 단어가 즉시 해당 적중으로 이어집니다. 일반적으로 204가능한 단어 중 몇 천 개만이 이 테이블에 있으며, 훨씬 적은 포인터를 사용하도록 접근 방식을 수정하는 것은 쉬움
    ** 두 번째 접근 방식은 결정론적 유한 오토마톤 또는 유한 상태 기계의 사용을 탐구
    ** 우리 구축의 중요한 특징은 상태가 아닌 전환에 수용 신호를 보내는 것(Mealy 패러다임)
    **     이 방법은 시간과 공간을 절약하는 데 도움이 되었으며, 일반적인 사용을 위해 이 접근 방식을 선호
    *** 전형적인 조회 길이와 매개변수 설정을 사용할 때, 이 버전의 BLAST는 단백질 데이터베이스를 약 500,000개의 잔기/초의 속도로 스캔

  • 적중을 확장하여 해당 적중을 포함하는 지역적으로 최대 세그먼트 쌍을 찾는 것은 간단
    ** 시간을 절약하기 위해, 우리는 짧은 확장에 대해 찾은 최고 점수보다 특정 거리 이하로 떨어지는 세그먼트 쌍에 도달했을 때 한 방향으로의 확장 과정을 종료
    ** 이는 보장된 MSPs를 찾는 이상에서 추가적인 벗어남을 도입하지만, 추가된 부정확성은 실험과 분석을 통해 무시할 수 있을 만큼 작음(예를 들어, 단백질 비교의 경우 기본 거리는 20이고 더 높은 점수의 확장을 놓칠 확률은 약 0.001)

3. Results

  • BLAST 결과 섹션 상세 설명

(a) 무작위 시퀀스와의 BLAST 성능

  • 무작위 시퀀스 비교에서 MSP 점수의 분포에 관한 이론적 결과를 바탕으로, 개별 잔기의 발생 확률과 잔기 쌍을 정렬할 때의 점수 세트를 고려하여, MSP 점수의 통계적 유의성을 평가할 수 있는 두 파라미터(λ와 K)를 제공
  • 두 무작위 시퀀스를 비교할 때, 특정 점수 S 이상의 세그먼트 쌍을 찾을 확률이 제공되며, 이는 두 시퀀스가 여러 개의 구별되는 유사성 영역을 공유할 때, 개별적으로 통계적으로 유의미하지 않은 세그먼트 쌍이라도 유의미한 관련성을 갖는 것으로 탐지될 수 있음을 나타냄

(b) 단어 길이와 임계값 매개변수 선택

  • BLAST를 실행할 때 특정 단어 길이(w)와 임계값(T) 매개변수를 어떻게 선택할지에 대한 기준을 설명
  • 단어 길이는 BLAST 실행 시간에 영향을 미치며, 더 긴 단어를 검사할수록 잠재적인 MSP에 대한 정보가 증가
  • 따라서, 주어진 민감도 수준을 유지하면서 단계 3에서 소요되는 시간을 줄이기 위해 w 매개변수를 증가시킬 수 있음
  • 그러나 w가 큰 경우에는 단어 목록을 컴파일하는 데 더 많은 시간이 소요되고 메모리 요구량도 증가

  • 단백질 검색의 경우, 단어 크기 4가 최적의 타협점이라는 것을 발견

  • 임계값 T를 낮추면 BLAST에 의한 MSP 점수의 근사치가 개선되지만 실행 시간이 증가
  • 따라서 민감도와 시간 사이에서 합리적인 타협점을 제공하는 T 값에 대한 데이터를 제공

(c) BLAST를 이용한 유사 시퀀스 성능 분석

  • 실제 데이터에서 BLAST의 성능을 분석하기 위해 다양한 단백질을 각각의 슈퍼패밀리와 비교
  • 단어 길이 4와 다양한 T 매개변수 설정을 사용하여 진정한 MSP 점수와 BLAST 근사치를 계산
  • 멀리 관련된 단백질이 많이 포함된 슈퍼패밀리만이 이전 섹션의 무작위 모델과 유용하게 비교

(d) 두 긴 DNA 시퀀스 비교

  • 73360 bp 인간 게놈 섹션과 해당하는 44595 bp 토끼 게놈 섹션을 비교하여, 유전자, 긴 삽입 반복 그리고 예상된 약한 유사성 등 세 가지 주요 클래스의 지역적으로 유사한 영역을 조사
  • BLAST 알고리즘은 간격 없이 정렬할 수 있는 지역적으로 유사한 영역을 찾는 데 사용
  • BLAST는 무작위 시퀀스와 실제 유사 시퀀스 모두에서 높은 성능을 보여주며, 특히 긴 DNA 시퀀스를 비교하는 데 효과적인 도구임을 보여줌

4. Conclusion

  • BLAST의 기본 개념은 단순하고 견고하여 다양한 방식으로 구현되고 여러 맥락에서 활용될 수 있음
  • BLAST는 빠른 데이터베이스 검색 프로그램을 구축할 수 있으며, 수학적 분석에 적합한 추가적인 이점을 제공
  • 기본 아이디어의 변형과 대안적 구현을 통해 이 방법은 다양한 상황에 맞게 조정될 수 있음
  • 시퀀스 데이터베이스의 크기가 증가함에 따라 BLAST는 분자생물학자에게 귀중한 도구
  • BLAST의 C 프로그래밍 언어 버전은 요청 시 저자로부터 제공받을 수 있으며, BSD와 AT&T System V UNIX 운영 체제에서 실행