Database Searching - Blast and FastA

heu-ris-tic adj. (Computer Science) Relating to or using a problem-solving technique in which the most appropriate solution of several found by alternative methods is selected at successive stages of a program for use in the next step of the program.

Both FastA and Blast are examples of heuristic methods for identifying similar sequences in databases. Although they do it in quite different ways, both programs first identify very short exact matches between the query sequence and the databases sequences. In the next stage, the best short hits from the first stage are extended to see if more similarity can be found, and eventually, the best hits are optimized with some form of dynamic programming and displayed.

This is in contrast to SSEARCH or other full Smith-Waterman search tools, which effectively make all possible pairwise comparisons to all of the sequences in the database. As we saw in the last exercise, while this approach is the most sensitive for searching databases, it is also computationally expensive and very slow. Heuristic methods like Blast and FastA make a number of assumptions and approximations to speed up the search process significantly.

In making these approximations, both sensitivity (ability to identify truly related sequences) and selectivity (ability to avoid finding unrelated sequences) can be affected. To rectify these problems, statistical parameters have been incorporated into both program families and in practice, the sensitivity and selectivity of both search tools is very close to that of the Smith-Waterman algorithm.

In the following exercises, we will use both FastA and Blast (and members of their families) for identifying closely and distantly related proteins. We will also address several important issues to consider when doing database searches in general.

Next - The Blast and FastA Families
Up - Main Page