sequences in the target database, creating two lists in the process. Here, the word length parameter is called ktup, which is the equivalent of W in BLAST. These lists of overlapping words are compared with one another in order to identify any words that are common to the two lists. The method then looks for word matches that are in close proximity to one another and connects them to each other (intervening sequence included), without introducing any gaps. This can be represented using a dotplot format (Figure 3.20a). Once this initial round of connections are made, an initial score (init1) is calculated for each of the regions of similarity.
In step 2, only the 10 best regions for a given pairwise alignment are considered for further analysis (Figure 3.20b). FASTA now tries to join together regions of similarity that are close to each other in the dotplot but that do not lie on the same diagonal, with the goal of extending the overall length of the alignment (Figure 3.20c). This means that insertions and deletions are now allowed, but there is a joining penalty for each of the diagonals that are connected. The net score for any two diagonals that have been connected is the sum of the score of the original diagonals, less the joining penalty. This new score is referred to as initn.
In step 3, FASTA ranks all of the resulting diagonals, and then further considers only the “best” diagonals in the list. For each of the best diagonals, FASTA uses a modification of the Smith–Waterman algorithm (1981) to come up with the optimal pairwise alignment between the two sequences being considered. A final, optimal score (opt) is calculated on this pairwise alignment.
Figure 3.20 The FASTA search strategy. (a) Once FASTA determines words of length ktup common to the query sequence and the target sequence, it connects words that are close to each other, and these are represented by the diagonals. (b) After an initial round of scoring, the top 10 diagonals are selected for further analysis. (c) The Smith–Waterman algorithm is applied to yield the optimal pairwise alignment between the two sequences being considered. See text for details.
In the fourth and final step, FASTA assesses the significance of the alignments by estimating what the anticipated distribution of scores would be for randomly generated sequences having the same overall composition (i.e. sequence length and distribution of amino acids or nucleotides). Based on this randomization procedure and on the results from the original query, FASTA calculates an expectation value E (similar to the BLAST E value), which, as before, represents the probability that a reported hit has occurred purely by chance.
Running a FASTA Search
The University of Virginia provides a web front-end for issuing FASTA queries. Various protein and nucleotide databases are available, and up to two databases can be selected for use in a single run. From this page, the user can also specify the scoring matrix to be used, gap and extension penalties, and the value for ktup. The default values for ktup are 2 for protein-based searches and 6 for nucleotide-based searches; lowering the value of ktup increases the sensitivity of the run, at the expense of speed. The user can also limit the results returned to particular E values.
The results returned by a FASTA query are in a significantly different format than those returned by BLAST. Consider a FASTA search using the sequence of histone H2B.3 from the highly regenerative cnidarian Hydractinia, one of four novel H2B variants used in place of protamines to compact sperm DNA (KX622131.1; Török et al. 2016), as the query. The first part of the FASTA output resulting from a search using BLOSUM62 as the scoring matrix and Swiss-Prot as the target database is shown in Figure 3.21, summarizing the results as a histogram. The histogram is intended to convey the distribution of all similarity scores computed in the course of this particular search. The first column represents bins of similarity scores, with the scores increasing as one moves down the page. The second column gives the actual number of sequences observed to fall into each one of these bins. This count is also represented by the length of each of the lines in the histogram, with each of the equals signs representing a certain number of sequences; in the figure, each equals sign corresponds to 130 sequences from UniProtKB/Swiss-Prot. The third column of numbers represents how many sequences would be expected to fall into each one of the bins; this is indicated by the asterisks in the histogram. The hit list would immediately follow, and a portion of the hit list for this search is shown in Figure 3.22. Here, the accession number and partial definition line for each hit is given, along with its optimal similarity score (opt), a normalized score (bit), the expectation value (E), percent identity and similarity figures, and the aligned length. Not shown here are the individual alignments of each hit to the original query sequence, which would be found by further scrolling down in the output. In the pairwise alignments, exact matches are indicated by a colon, while conservative substitutions are indicated by a dot.
Statistical Significance of Results
As before, the E values from a FASTA search represent the probability that a hit has occurred purely by chance. Pearson (2016) puts forth the following guidelines for inferring homology from protein-based searches, which are slightly different than those previously described for BLAST: an E value < 10−6 almost certainly implies homology. When E < 10−3, the query and found sequences are almost always homologous, but the user should guarantee that the highest scoring unrelated sequence has an E value near 1.
Comparing FASTA and BLAST
Since both FASTA and BLAST employ rigorous algorithms to find sequences that are statistically (and hopefully biologically) relevant, it is logical to ask which one of the methods is the better choice. There actually is no good answer to the question, since both of the methods bring significant strengths to the table. Summarized below are some of the fine points that distinguish the two methods from one another.
Figure 3.21 Search summary from a protein–protein FASTA search, using the sequence of histone H2B.3 from Hydractinia echinata (KX622131.1; Török et al. 2016) as the query and BLOSUM62 as the scoring matrix. The header indicates that the query is against the Swiss-Prot database. The histogram indicates the distribution of all similarity scores computed for this search. The left-most column provides a normalized similarity score, and the column marked opt gives the number of sequences with that score. The column marked E() gives the number of sequences expected to achieve the score in the first column. In this case, each equals sign
