FASTA search algorithm

All of the three IC centers also provide facilities for sequence similarity search and alignment. The widely used database search algorithms are FASTA (Lipman and Pearson, 1985) at http //www.nbrf.georgetown.edu/pirwww/search/fasta.html and BLAST (Altschul et al., 1990) at http //www.ncbi.nlm.nih.gov/BLAST/. For BLAST... 

Pearson, W. R. (1991). Searching protein sequence libraries comparison of the sensitivity and the selectivity of the Smith-Waterman and FASTA algorithms. Genomics 11,635-50. 

The FASTA algorithm was originally described by Lipman and Pearson (1985) as a method of locating similar sequences by first identifying short words common to the compared sequences. The words are any short DNA or protein sequence (n-mer or k-tuple) k-tuple sizes of 1 or 2 are used for protein sequences, and up to 6 bases for DNA searches. In the first similarity search, the test sequence (or query) and comparison sequence are lined up, and under each position is recorded the number of elements that the comparison sequence must be moved to the right (+) or left (-) to achieve a match. If the two sequences are very similar in a particular region, then a particular displacement will occur frequently if not, all possible displacements will be found (Wilbur and Lipman 1983). 

Several implementations of this procedure are available, most prominently the SSEARCH program from the FASTA package [53], There exist implementations of the Smith-Waterman algorithm that are tuned for speed like one using special processor instructions [54] and, among others, one by Barton [55], Depending on implementation, computer, and database size, a search with such a program will take on the order of one minute. 

Algorithms. Although there are many mechanisms to search biodatabases, the most critical and extensively used is sequence similarity searching. Needleman-Wunsch, Smith-Waterman, FASTA, and BLAST represent the major similarity algorithms. They differ in algorithmic mechanism and computational speed, with Needleman-Wunsch being the most accurate but also the most computationally intense. At the time of its publication in 1970, it took days to return results. BLAST is the least accurate of... 

---