From: wrp@cyclops.micr.Virginia.EDU (Bill Pearson)
Subject: Re: BLAZE survey
Organization: University of Virginia
Date: Fri, 8 Jan 1993 14:47:41 GMT

In article <16B501C66.LILMARA@YaleVM.YCC.Yale.Edu> MCKMICP@YaleVM.YCC.Yale.Edu (Michael McKenna) writes:

>Having read some of the literature that compares various algorithms,
>the articles tend to sort into two classes:
> 
>     1) Theoretically based papers discussing the various mathematical
>        merits of one algorithm versus another. The authors are likely to
>        have an investment in their favorite tool, and it's not always clear
>        (to me) how the math translates to the real world
> 
>     2) Very general papers which look at two or three sequences and
>        draw conclusions about algorithm strengths from a limited database.
> 
>It seems to me that all the algorithms have their unique strengths and
>weaknesses- and this is going to be strongly sequence dependent. That
>is why I made the original post, in an attempt to discern the relative
>strengths of the programs for different applications.

I (with bias, no doubt) recommend the paper:

	W. R. Pearson (1991) Genomics "Searching Protein Sequence Libraries:
	Comparison of the Sensitivity and Selectivity of the Smith-Waterman
	and FASTA Algorithms"  11:635-650

It examines the performance of FASTA, BLAST, and the Smith Waterman
algorithm (which is used by BLAZE) on about 34 different superfamilies
of proteins (all superfamilies with 20 or more members).  The bottom
line is that Smith-Waterman performs better than BLAST or FASTA, but
that FASTA will perform as well as Smith-Waterman if one optimizes all
the library scores (the -o option) and search about 10X faster than
Smith-Waterman (though not, of course, 10X faster than Smith-Waterman
on a MasPar). A description of the -o option and the reference to the
Genomics paper is provided with the FASTA documentation.

	In the past 6 months I have extended these studies to 75
superfamilies and used more rigorous statistical tests, but the result
is the same, if you use the -o option with FASTA, you will do as well
as Smith-Waterman. If you don't, you won't.

	These comments apply only to protein sequence searching.  I do
not believe that there is any advantage to slower, more rigorous,
algorithms for DNA sequence searches.  For DNA, if a significant
similarity exists in a non-protein-coding sequence, BLAST or FASTA
will find it as well as, or better than, Smith-Waterman.  With DNA,
selectivity is much more of a problem than sensitivity and both FASTA
and BLAST are more selective.

	Since the protein sequence libraries are considerably smaller
than the DNA sequence libraries (and will continue to be, even after
entire genomes are sequenced), I believe that it is reasonable for
most researchers to rely on FASTA with the -o option for protein
library searches and on FASTA or BLAST for DNA searches.

	There is one place where the Smith-Waterman algorithm should
be used, however - in the preparation of alignments for publication.
For some proteins with large variable-length loops, FASTA will not
allow gaps of the appropriate size (and BLAST does not construct
alignments with gaps, although it often shows several aligned
regions).  I am considering modifying FASTA to display rigorous
Smith-Waterman alignments rather than the approximate (gaps < 16
residues) it calculates currently.  A Smith-Waterman implementation
(SSEARCH) is available with the FASTA distribution.

Bill Pearson

Xref: sparky bionet.molbio.genbank:622 bionet.software:2393