FASTA - BioHackersNet

데이타베이스의 모든 서열과 PairwiseAlignment 하는 HeuristicAlgorithm으로 접근한 서열분석 프로그램

http://bioweb.pasteur.fr/seqanal/interfaces/fasta.html

gapped BLAST가 나온 이후 거의 사용되지 않는다.

FASTA는 임의의 서열과 유사성을 가진 서열을 서열 데이터베이스로 부터 찾는 프로그램이다. FASTA는 단백질 서열간의 비교를 위해 제작되었지만 염기 서열간의 비교도 가능하다. 특히 FASTA의 경우 입력한 단백질 서열과 염기 서열 데이터베이스간의 비교도 가능하다. 즉 염기 서열 데이터베이스를 6 frame으로 translation하여 입력한 단백질 서열과 비교하는데 이 기능은 임의의 단백질 서열과 EST 데이터베이스를 검색하는데 좋은 방법으로 알려져 있다.

Algorithm

FASTA는 우선 두 서열간의 dot blot을 그림으로서 비교를 시작한다. Dot blot에서 일치하는 가진 부분은 대각선으로 표시하고 그려진 대각선들의 합을 계산한다. SmithWatermanAlgorithm과 FASTA의 가장 큰 차이점은 FASTA는 데이터베이스에 있는 모든 서열들과 dot matrix를 그리지 않고 대신 FASTA는 "word"를 기반으로 한 방법을 이용한다는 점이다.

FASTA는 입력한 서열로부터 한개 (ktup=1) 혹은 두개 (ktup=2)의 단백질 서열 (혹은 3개 혹은 6개의 염기서열)로 이루어진 "단어 (ktup)" 들의 조합을 만든다. 그리고 데이터베이스의 임의의 한 서열에서 각 단어들과 일치하는 단어들을 찾아내어 각각의 단어들을 연결하는 대각선을 만든다. 물론 이때 중복된 단어들을 제거한다.
점수가 높은 대각선 부분 10개를 선택해 치환행렬을 이용하여 score들을 다시 계산한다. 이때 가장 큰 값을 가진 부분을 "init1" 이라 정의한다.
gap을 허용하여 몇몇의 high-scoring 대각선 부분들을 합치고 가장 높은 점수를 initn이라고 한다.
initn이 높은 서열들을 선택하고 Smith-Waterman알고리즘을 이용하여 두 서열을 최적화배열하고 값을 계산한다. 이값을 opt. 라고 정의한다. 이 방법은 단어의 크기를 1(한개의 단백질을 1개의 단어로 정의)로 하는 것이 훨씬 더 정확한 방법임을 알 수 있다.

FASTA program의 종류

FASTA : 염기 서열 혹은 단백질 서열간의 유사성 검사
TFASTA : 입력한 단백질 서열과 데이터베이스의 염기서열을 translation 시킨후 유사성 검사
LFASTA : 두 단백질 혹은 염기서열의 부분 유사성 검색(compare local similarity)을 수행한 후 부분 서열 배열 (local sequence alignment)의 결과를 보여줌
PFASTA : 두 서열의 부분 유사성 검색후 부분 서열 배열의 결과를 그림으로 보여줌
FASTA 3.0 : 가장 최근에 나온 FASTA version으로 서비스 페이지 ( http://www2.ebi.ac.uk/fasta3/ ) 에 가서 서열을 입력하면 검색을 할 수 있다. FASTA는 서열을 입력하면 자동으로 염기 서열인지 단백질 서열인지를 판단한다. 즉 전체 서열 중 ACGT의 서열이 80%이상 차지하면 염기 서열로, 그렇지 않은 경우에는 단백질 서열로 판단한다. 또한 많은 검색 파라미터를 제공하는데 그 중 가장 중요한 값은 ktup이다. 처음 FASTA가 개발되었을 경우 PAM 계열의 측정 행렬 밖에 제공되지 않았지만 최근 version의 경우 BLOSUM 계열도 제공하고 있어 BLAST 에 비해 더욱 좋은 sensitivity를 가진것으로 보고되고 있다.

FASTA 검색결과의 분석

FASTA는 E( )-value (expectation of significance)를 계산한다.

E( )-value 는 결과에 나온 서열이 query 서열과 우연히 배열해 특정 score 이상을 가지는 확률을 뜻한다. 결과에 나온 서열이 생물학적으로 의미가 있다면 E( )-value는 작은 값을 갖는다.
결과에서 보여주는 히스토그램은 데이터베이스의 서열들이 Z-score들의 분포를 보여준다.
Z-score는 opt score에 서열의 길이를 계산하여 normalization한 것으로 서열의 길이에 영향을 받지 않는 값이다. 의미 있는 서열인 경우 Z-score는 가능한 큰 값을 갖는다.
Z-score 와 expect value 의 그래프는 입력한 서열과 데이터베이스의 서열들이 임의로 유사성을 나타내는 것과 주목할 만한 유사성을 가진 서열들의 구별 기준을 제시해준다.

BioSequence를 ASCII모드로 적는 가장 간단한 포맷을 FastaFormat이라고 한다. FASTA프로그램사용에서 유래했다고 생각된다.