2.

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

FASTA가 적절한 서열을 찾아내는 방법은 다음과 같다. (그림 참조)
1) FASTA는 입력한 서열로부터 한개 (ktup=1) 혹은 두개 (ktup=2)의 단백질 서열 (혹은 3개 혹은 6개의 염기 서열)로 이루어진 “단어 (ktup)”들의 조합을 만든다. 그리고 데이터베이스의 임의의 한 서열에서 각 단어들과 일치하는 단어들을 찾아내어 각각의 단어들을 연결하는 대각선을 만든다. 물론 이때 중복된 단어들은 제거한다.

2) 점수가 높은 대각선 부분 10개를 선택해 PAM250과 같은 치환 행렬(replacement matrix)을 이용하여 값(score)들을 다시 계산한다. 이때 가장 큰 값을 가진 부분을 “init1”이라 정의한다.

3) gap을 허용하여 몇몇의 high-scoring 대각선 부분들을 합치고 가장 높은 점수를 initn이라고 한다.

4) initn이 높은 서열들을 선택하고 Smith-Waterman 알고리즘을 이용하여 두 서열을 최적화 배열 (optimal alignment) 하고 값(score)를 계산한다. 이 값을 optimized score (opt.)로 정의한다.

위의 방법에서 단어의 크기(ktup)를 1(한 개의 단백질을 1개의 단어로 정의)로 하는 것이 훨씬 더 정확하게 비교하는 방법이라는 것을 알 수 있다. 하지만 FASTA에서 기본 단어 값은 2로 되어 있다. 하지만 단어의 크기를 1로 하였을 때 비교 속도는 훨씬 느려지게 된다.

2-2. FASTA의 입력 형식
FASTA는 자체적으로 입력한 서열이 염기 인지 단백질인지를 판단한다. 판단 기준은 입력한 서열 중 A,C,G,T가 전체 서열의 85% 이상이 되면 염기로 판단하고 그렇지 않으면 단백질로 판단한다. FASTA는 standard text format sequence file을 이용한다. 첫 줄은 ‘>’나 ‘;’를 쓴 후 comment를 넣을 수 있다. 그 다음 줄부터 서열을 입력하면 된다. FASTA는 특수문자나 빈칸, tab등은 무시하고 single letter amino acid codes를 인식한다.

2-4. FASTA3.0
가장 최근에 나온 FASTA version으로 서비스 페이지 (http://www2.ebi.ac.uk/ fasta3/)에 가서 서열을 입력하시면 검색을 수행 할 수 있다. FASTA는 서열을 입력하면 자동으로 염기 서열인지 단백질 서열인지를 판단한다. 즉 전체 서열 중 ACGT의 서열이 80% 이상을 차지하면 염기 서열로, 그렇지 않은 경우에는 단백질 서열로 판단한다. 또한 많은 검색 파라미터를 제공하는데 그 중 가장 중요한 값은 ktup이다. FASTA에서 염기인 경우 6, 단백질인 경우 2가 기본값으로 되어 있다. 처음 FASTA가 개발되었을 경우 PAM 계열의 측정 행렬 밖에 제공되지 않았지만 최근 version의 경우에는 BLOSUM계열도 제공하고 있어 BLAST에 비해 더 좋은 sensitivity를 가진 것으로 보고되고 있다.

검색 파라미터는 다음과 같다.
YOUR EMAIL, SEARCH TITLE, RESULT, DATABASE등의 옵션은 Bic-sw와 동일하다. 단 DATABASE의 경우 Bic-sw에 비해 더 많은 종류를 제공하며 다음과 같다.

swall	SWALL Non-Redundant Protein sequence database Swissprot+Trembl+TremblNew
Swissprot	SWISS-PROT Protein Database
Swnew	Updates to SWISS-PROT
Trembl	TREMBL (Translated EMBL)
Tremblnew	TREMBLNEW
EMBL	The EMBL Database	Non Interactive
EFUN	EMBL Fungi
EINV	EMBL Invertebrates
EHUM	EMBL Human
EMAM	EMBL Mammalian
EORG	EMBL Organelles
EPHG	EMBL Phages
EPLN	EMBL Plants
EPRO	EMBL Prokaryote
EROD	EMBL Rodents
ESTS	EMBL STSs
ESYN	EMBL Synthetic
EUNA	EMBL Unclassified
EVRL	EMBL Viral
EVRT	EMBL Vertebrates
EEST	EMBL ESTs
EGSS	EMBL Genome Survey Sequences
EHTG	EMBL High Throughput Genome Sequences
EMNEW	EMBL New (Updates)
EMALL	EMBL + EMBL New (Updates)	Non Interactive

MATRIX: 검색에 사용되는 측정 행렬을 정할 수 있다. 기본 matrix는 BLOSUM62이다.
GAP PENALTIES: Bic-sw의 경우와 동일하다. GAPOPEN은 Bic-sw의 GAPWEIGHT, GAPEXT는 LINWEIHT에 해당한다. 주어진 기본값은 다음과 같다.

SCORES & ALIGNMENTS : Bic-sw의 "show number of alignment"와 "show number of scores"와 동일한 옵션이다.
KTUP/WORDSIZE : 위에서 설명한 KTUP을 결정할 수 있다.
HISTOGRAM : yes를 선택하면 결과에 histogram을 출력한다.
DNA STRAND : DNA의 경우 어떤 strand를 검색할 것인가를 결정 할 수 있다. 기본값은 upper strand만 검색하게 되어있고 옵션 선택에 따라 bottom도 할 수 있다.

2-5. FASTA의 검색 결과 (output) 분석
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의 그래프는 입력한 서열과 데이터베이스의 서열들이 임의로 유사성을 나타내는 것과 주목할 만한 유사성을 가진 서열들의 구별 기준을 제시해 준다.

FASTA	염기 서열 혹은 단백질 서열간의 유사성 검사
TFASTA	입력한 단백질 서열과 데이터베이스의 염기 서열을 translation 시킨 후 유사성 검사
LFASTA	두 단백질 혹은 염기 서열의 부분 유사성 검색(compare local similarity)을 수행한 후 부분 서열 배열(local sequence alignment)의 결과를 보여줌
PFASTA	두 서열의 부분 유사성 검색 후 부분 서열 배열의 결과를 그림으로 보여줌

	DNA	PROTEIN
GAPOPEN	-16	-12
GAPEXT	-4	-2