
				20 April 1999

If you regularly install the latest version of the fasta3 package from
ftp://ftp.virginia.edu/pub/fasta, you may want to join the fasta_list
majordomo mailing list.  I plan to use this list to announce new
releases and solicit bug reports.

To join the mailing list, send the following email message to:
majordomo@virginia.edu

	subscribe fasta_list
	end

				August, 2000

Since December, 1999, the latest version of the fasta package is
version 3.3.  Version 3.3 provides a number of improved statistical
routines, including -z 2 and -z 6, which calculate maximum likelihood
estimates for lambda and K (-z 6 actually does a more complex
composition correction).

By default, the various Makefile's compile a suite of programs
fasta33(_t), fastx33(_t), ssearch33(_t), etc.  To compile programs
called fasta3(_t), etc, change the reference to "Makefile33.common" to
"Makefile.common" in the Makefile you use.

See the file "readme.v33t0" for more information about improvements
in fasta, version 3.3.

				December, 1998

The latest version of the fasta package is now version 3.2. Version
3.2 differs from previous versions in its ability to search both the
forward and reverse strands on a DNA sequence in a single run (fasta3,
fastx3, fasty3). Naturally, this slows those programs down 2-fold.  In
addition, more protein scoring matrices are available and the
fasts3/tfasts3 program, for searching with protein fragments, is
introduced.

				May, 1998

These programs contain version 3.1 of the fasta package.  Version 3.1
differs from version 3.0 with the inclusion of fasty and tfasty.  In
addition, the structure of the alignment routines has changed to allow
additional sequence comparison functions to be added.  Unfortunately,
these changes have rendered the alignment routines in the PVM version
non-functional.

Additional information is available in the files: readme.v31t0,
readme.v31t1, and readme.pvm_3.1.  Documentation for all the FASTA
programs, including those available in the fasta20 distribution, is
available in fasta20.me (fasta20.doc) and fasta3.1 (a Unix man page).

================================================================

				September 10, 1996


The following comparison functions are available:

	old 		new		threaded
	program		program 	version

	fasta		fasta3		fasta3_t
	
	tfasta		tfasta3		tfasta3_t

	tfastx		tfastx3		tfastx3_t

	fastx		fastx3		fastx3_t

			tfasty3		tfasty3_t

			fasty3		fasty3_t

	ssearch		ssearch3	ssearch3_t

At the moment, these are the only programs in the FASTA package that
are part of the new release.  You should rely on the older
fasta20u6.shar version for prss, prdf, lfasta, lalign, etc.

Improvements in FAST3.0:

(1) Better statistical estimates:

The FASTA2.0 version provided good statistical estimates for FASTA
searches, but TFASTA estimates were inaccurate.  When calculating the
parameters for the statistical estimates, FASTA3.0 samples 50,000
sequences from a database, rather than 20,000 for FASTA2.0.  In
addition, for tfasta3/tfasta3_t, only the best score from the six
reading frames is sampled, rather than all six scores.  Statistical
estimates from tfasta3/tfasta3_t seem quite accurate.

Since the statistical estimates for FASTA2.0/3.0 are based on sampling
the first 20,000/50,000 sequences in the database, estimates can be
improved by removing bias from the order of sequences in the database.
In particular, GenPept is ordered by organism, so that the sequences
at the beginning of the database are somewhat different in amino acid
composition from those at the end.  A better fit of the calculated to
observed score distribution can be obtained by shuffling the GenPept
database and searching the shuffled database.  A future version of
FASTA3.0 will sample throughout the database so that shuffling is not
necessary.

(2) Faster Smith-Waterman searches

The ssearch program now uses Phil Green's (U. Washington) SWAT
optimization.  This change speeds up the program about 30%.  However,
the program no longer calculates a similarity score for alignments
whose score is less than the penalty for the first residue in a gap.
Since this penalty is typically 12 - 16, problems are rarely
encountered.  However, the SWAT optimization cannot be used if very
high gap penalties (>50) are required.  For those rare cases, the
ssearch3 and ssearch3_t programs should be recompiled using the
dropnsw.c file.

Versions of fasta3 and fastx3 that use this optimization should be
available shortly.

(3) Faster execution on shared memory multiprocessors.

All of the programs in this package are now "threaded".  The code has
been successfully tested on Digital Alpha, Sun, and SGI
multiprocessors.  The *_t versions of the programs are designed to run
using threaded processes using pthreads (Alpha, SGI) or unix threads
(Sun Solaris) system calls.  On a four-processor machine, ssearch3_t
will run more than 3.5X as fast as ssearch3; fasta3 typically is i/o
bound on fast multiprocessors and will not show as much speedup.

With version 3.0t6, the Solaris implementation has been tested both
on Sparc and Solaris x86 machines.  Changes were made to allow the
threaded programs to run on more than 50% of the processors.

The threaded version of the FASTA package was written with the help of
Eammon O'Toole from the Digital Equipment Corporation Technical
Computing Group in Galway, Ireland.  The SGI version was tested and
modified with the help of Haruna Cofer and several co-workers from
SGI.

(4) Full-function network parallel database searching.

This distribution includes a functioning Makefile (Makefile.pvm) for a
network-parallel version of the program that uses the PVM (Parallel
Virtual Machine) parallel environment.  An MPI version should be
available soon.  The network parallel versions finally produce
sequence alignments.  Thus, one can perform a complete genome-genome
comparisons in reasonable time (10's of hours) on networks of
high-performance workstations.

Other changes with FASTA3.0:

The scoring matrix file used by FASTA2.0 is the same as that used by
the BLASTP programs and produced by the "pam" program distributed with
the BLASTP1.4 distribution.

Although the structure of the FASTA3.0 programs is quite different
from that the version 2.0 fasta, tfasta, fastx, and ssearch, I have
attempted to keep the "look" of the programs very similar.  In
particular, I have tried to preserve the major display features of the
older FASTA programs so that code designed to reformat FASTA output
should not be broken very often.

Future plans:

FASTA3.X provides a general framework for sequence database
searches.  It is very easy to add additional sequence comparison
functions, e.g. functions for profile searches or pattern matching. I
encourage software developers to consider using this framework for
their sequence comparison functions.  Because it provides serial,
threaded-parallel, and network-parallel environments, it is very easy
to debug a program in the conventional serial environment and then
obtain speedups with threaded- and network parallel computation.


Bill Pearson
wrp@virginia.edu

