COPYRIGHT NOTICE

FASTA program and documentation may not be sold or incorporated

into a commercial product, in whole or in part, without written

consent of William R. Pearson and the University of Virginia.

For further information regarding permission for use or

reproduction, please contact: David Hudson, Assistant Provost for

Research, University of Virginia, P.O. Box 9025, Charlottesville,

VA 22906-9025, (804) 924-6853

The FASTA program package

Introduction

This documentation describes the version 2.0x of the FASTA

program package (see W. R. Pearson and D. J. Lipman (1988),

"Improved Tools for Biological Sequence Analysis", PNAS 85:2444-

2448, and W. R. Pearson (1990) "Rapid and Sensitive Sequence

Comparison with FASTP and FASTA" Methods in Enzymology 183:63-

98). Version 2.0 modifies version 1.8 to include explicit

statistical estimates for similarity scores based on the extreme

value distribution. In addition, FASTA protein alignments now

use the Smith-Waterman algorithm with no limitation on gap size.

FASTA and SSEARCH now use the BLOSUM50 matrix by default, with

options to change gap penalties on the command line. Version 1.7

replaces rdf2 and rss with prdf and prss, which use the extreme-

value distribution to calculate accurate probability estimates.

Although there are a large number of programs in this package,

they belong to four groups:

Library search programs: FASTA, FASTX, TFASTA, TFASTX, SSEARCH

Local homology programs: LFASTA, PLFASTA, LALIGN, PLALIGN, FLALIGN

Statistical significance: PRDF, RELATE, PRSS, RANDSEQ

Global alignment: ALIGN

In addition, I have included several programs for protein

sequence analysis, including a Kyte-Doolittle hydropathicity

plotting program (GREASE, TGREASE), and a secondary structure

prediction package (GARNIER).

The FASTA sequence comparison programs on this disk are

improved versions of the FASTP program, originally described in

Science (Lipman and Pearson, (1985) Science 227:1435-1441). We

have made several improvements. First, the library search

programs use a more sensitive method for the initial comparison

of two sequences which allows the scores of several similar

regions to be combined. As a result, the results of a library

search are now given with three scores, initn (the new initial

score which may include several similar regions), init1 (the old

fastp initial score from the best initial region), and opt (the

old fastp optimized score allowing gaps in a 32 residue wide

band).

These programs have also been modified to become "universal"

(hence FAST-A, for FASTA-All, as opposed to FAST-P (protein) or

FAST-N (nucleotides)); by changing the environment variable

SMATRIX, the programs can be used to search protein sequences,

DNA sequences, or whatever you like. By default, FASTA, LFASTA,

and the PRDF programs automatically recognize protein and DNA

sequences. Sequences are first read as amino acids, and then

converted to nucleotides if the sequence is greater than 85%

A,C,G,T (the '-n' option can be used to indicate DNA sequences).

TFASTA compares protein sequences to a translated DNA sequence.

Alternative scoring matrices can also be used. In addition to

the BLOSUM50 matrix for proteins, the PAM250 matrix or matrices

based on simple identities or the genetic code can also be used

for sequence comparisons or evaluation of significance. Several

different protein sequence matrices have been included;

instructions for constructing your own scoring matrix are

included in the file FORMAT.DOC.

The remainder of this document is divided into three sections:

(1) a brief history of the changes to the FASTA package; (2) A

guide to installing the programs and databases; (3) A guide to

using the FASTA programs. The programs are very easy to use, so

if you are using them on a machine that is administered by

someone else, you may want to skip to section (3) to learn how to

use the programs, and then read section (1) to look at some of

the more recent changes. If you are installing the programs on

your own machine, you will need to read section (2) carefully.

1. Revision History

1.1. Changes with version 2.0u

Version 2.0u provides several major improvements over

previous versions of FASTA (and SSEARCH). The most important is

the incorporation of explicit statistical estimates and

appropriate normalization of similarity scores. This improvement

is discussed in more detail below in the section entitled

Statistical Significance. In addition, all of the protein

comparison programs now use the BLOSUM50 matrix, with gap

penalties of -12, -2, by default. BLOSUM50 performs

significantly better than the older PAM250 matrix. PAM250 can

still be used with the command line option: -s 250. (DNA

sequence comparisons use a more stringent gap penalty of -16, -4,

which produces excellent statistical estimates when optimized

scores are used. TFASTA uses -16, -4 as well.)

The quality of the fit of the extreme value distribution to

the actual distribution of similarity scores is summarized with

the Kolmogorov-Smirnov statistic. The acceptance limits for this

statistic can be found in many statistics books. In general,

values <0.10 (N=30) indicate excellent agreement between the

actual and theoretical distributions. If this statistic is >

0.2, consider using a higher (more stringent) gap penalty, e.g.

-16, -4 rather than -12, -2. The default scoring matrix for DNA

has been changed to score +5 for an identity and -4 for a

mismatch. These are the same scores used by BLASTN.

With explicit expectation calculations, the program now

shows all scores and alignments with expectations less than 10.0

(with optimized scores, 2.0 without optimization) when the "-Q"

(quiet) mode is used. The expectation threshold can be changed

with the "-E" option.

Finally, the algorithm used to produce the final alignments

of protein sequences is now a full Smith-Waterman, with unlimited

gaps. (The older band-limited alignments are used for DNA

sequences and TFASTA by default, because Smith-Waterman

alignments are very slow for long sequences.) Both the optimized

and Smith-Waterman scores are reported; if the Smith-Waterman

score is higher, then additional gaps allowed a better alignment

and similarity score to be calculated.

FASTA searches now optimize similarity scores by default

(this slows searches about 2-fold (worst case) for ktup=2). Thus,

the meaning of the "-o" option has been reversed; "-o" now turns

off optimization and reports results sorted by "initn" scores.

Optimization significantly improves the sensitivity of FASTA, so

that it almost matches Smith-Waterman. With version 2.0, the

default band width used for optimized calculations can be varied

with the "-y" option. For proteins with ktup=2, a width of 16

(-y 16) is used; 16 is also used for DNA sequences. For proteins

and ktup=1, a width of 32 is used. Searches that disable

optimization with the "-o" option will work fine for sequences

that share 25% or more identity in general, but to detect

evolutionary relationships with 20% - 25% identity, the more

sensitive default optimization is often required. Optimization

is required for accurate statistical estimates with either

protein or DNA sequences.

The FASTA package now includes FASTX, a program that

compares a DNA sequence to a protein sequence database by

translating the DNA sequence in three frames (the reverse frames

are selected with the -i option) and aligning the three-frame

translation with the sequences in the protein database.

Alignment scores allow frameshifts so that a cDNA or EST sequence

with insertion/deletion errors can be aligned with its homologues

from beginning to end.

With release 20u6, there is also a TFASTX program, which is

a replacement for TFASTA. TFASTA treats each of the six reading

frames of a DNA library sequence as a different sequence; TFASTX

compares a protein sequence against only two sequences from each

DNA sequence - the forward and reverse orientation. For a given

orientation, TFASTX calculates a similarity score for alignments

that allow frameshifts, thus considering all possible reading

frames.

Another new program is included - randseq - which will

produce a randomly shuffled (uniform or local shuffle) from an

input sequence. This randomly shuffled sequence can be used to

evaluate the statistical estimates produced by FASTA, SSEARCH, or

BLAST.

1.2. Changes with version 1.7

Version 1.7 has been released to provide the PRDF and PRSS

programs for shuffling sequences and estimating accurately the

probabilities of the unshuffled-sequence scores.

PRDF a version of RDF2 that uses calculates the probability

of a similarity score more accurately by using a fit to

an extreme value distribution. Code to fit the extreme

value distribution parameters and the impetus to update

RDF2 was provided by Phil Green, U. of Washington.

PRSS a version of PRDF that uses a rigorous Smith-Waterman

calculation to score similarities

1.3. Changes with version 1.6

FASTA version 1.6 uses a new method for calculating optimal

scores in a band (the optimization or last step in the FASTA

algorithm). In addition, it uses a linear-space method for

calculating the actual alignments. FASTA v1.6 package includes

several new programs:

SSEARCH a program to search a sequence database using the

rigorous Smith-Waterman algorithm (this program is

about 100-fold slower than FASTA with ktup=2 (for

proteins).

LALIGN A rigorous local sequence alignment program that will

display the N-best local alignments (N=10 by default).

PLALIGN a version of lalign that plots the local alignments to

a tektronix display.

FLALIGN a version of lalign that plots the local alignments to

a GCG Figure file.

The LALIGN/PLALIGN/FLALIGN programs incorporate the "sim"

algorithm described by Huang and Miller (1991) Adv. Appl. Math.

12:337-357. The SSEARCH and PRSS programs incorporate algorithms

described by Huang, Hardison, and Miller (1990) CABIOS 6:373-381.

LFASTA and PLFASTA now calculate a different number of local

similarities; they now behave more like LALIGN/PLALIGN. Since

local alignments of identical sequences produce "mirror-image"

alignments, lalign and lfasta consider only one-half of the

potential alignments between sequences from identical file names.

Thus

lfasta mchu.aa mchu.aa

Displays only two alignments, with earlier versions of the

program, it would have displayed five, including the identity

alignment. PLFASTA does display five alignments; when two

identical filenames are given, it draws the identity alignment,

calculates the two unique local alignments, draws them, and draws

their mirror images. LFASTA/PLFASTA and LALIGN/PLALIGN use the

filenames, rather than the actual sequences, to determine whether

sequences are identical; you can "trick" the programs into

behaving the old way by putting the same sequence in two

different files.

1.4. Changes with version 1.5

FASTA version 1.5 includes a number of substantial revisions

to improve the performance and sensitivity of the program. It is

now possible to tell the program to optimize all of the initn

scores greater than a threshold. The threshold is set at the

same value as the old FASTA cutoff score. Alternatively, you can

tell FASTA to sort the results by the init1, rather than the

initn, score by using the -1 option. FASTA -1 ... will report

the results the way the older FASTP program did.

A new method has been provided for selecting libraries. In

the past, one could enter the name of a sequence file to be

searched or a single letter that would specify a library from the

list included in the $FASTLIBS file. Now, you can specify a set

of library files with a string of letters preceded by a '%'.

Thus, if the FASTLIBS file has the lines:

Genbank 70 primates$1P/seqlib/gbpri.seq 1

Genbank 70 rodents$1R/seqlib/gbrod.seq 1

Genbank 70 other mammals$1M/seqlib/gbmam.seq 1

Genbank 70 vertebrates $1B/seqlib/gbvrt.seq 1

Then the string: "%PRMB" would tell FASTA to search the four

libraries listed above. The %PRMB string can be entered either

on the command line or when the program asks for a filename or

library letter.

FASTA1.5 also provides additional flexibility for specifying

the number of results and alignments to be displayed with the -Q

(quiet) option. The -b number option allows you to specify the

number of sequence scores to show when the search is finished.

Thus

FASTA -b 100 ...

tells the program to display the top 100 sequence scores. In the

past, if you displayed 100 scores (in -Q mode), you would also

have store 100 alignments. The -d option allows you to limit the

number of alignments shown. FASTA -b 100 -d 20 would show 100

scores and 20 alignments.

Finally, FASTA can provide a complete list of all of the

sequences and scores calculated to a file with the -r (results)

option. FASTA -r results.out ... creates a file with a list of

scores for every sequence in the library. The list is not

sorted, and only includes those scores calculated during the

initial scan of the library.

2. Installing the FASTA package

2.1. Installing the programs

2.1.1. Unix version

The FASTA distribution comes with several makefile's that

can be used to compile the FASTA programs. Over the years, as

ATT Unix System 5 and BSD unix have converged, these files have

become very similar. To begin with, I recommend using the

standard Makefile. There are two values in the makefile that

should be checked against the values used on your system: the HZ

value, which is the frequency in ticks per second used by the

times() system call, this value can usually be found by running:

grep HZ /usr/include/sys/*

and the functions available to return random numbers. If you

have a rand48() function that returns a 32-bit random number, use

it and use the lines:

NRAND=nrand48

RANFLG= -DRAND32

If not, you will need to use the rand() function call and

determine whether it returns a 16-bit or a 32-bit value. These

functions are used by PRDF and PRSS. If you have problems

compiling the programs, you may want to examine the makefile.unx

and makefile.sun files, to look for differences. I have tried to

use very standard unix functions in these programs, and they have

been successfully compiled, with very small changes to the

Makefile, on Sun's (Sun OS 4.1), IBM RS/6000's (AIX), and MIPS

machines (under the BSD environment).

2.1.2. IBM-PC/DOS version

For the IBM-PC/DOS version, the FASTA source code disk

contains the complete source code to all of the programs on the

other disks. The programs were compiled with Borland's Turbo

'C++', using Borland's MAKE utility. The graphics programs

(PLFASTA, TGREASE) use the graphics device drivers supplied with

the Turbo 'C' V2.0 package. Also included are the documentation

files PROGRAMS.DOC and FORMAT.DOC. You do not need any of the

files the source code disk to run the programs. The files on

this disk are identical to the UNIX and VMS versions that run on

larger machines. Also included is the code to compile

ALIGN0.EXE. ALIGN0 is the same as ALIGN, but does not penalize

for end-gaps.

If you have the DOS or Macintosh version of the FASTA

package, to install the programs you should:

(1) Make a new directory (folder) for the FASTA programs.

This need not be the same as the directory for your

sequence databases.

(2) Copy the files from the FASTA source disk to the new

directory.

(3) (DOS only) Edit your AUTOEXEC.BAT file to (a) modify your

PATH command to include the FASTA directory and (b) add

the line:

set FASTLIBS=c:\yourfastadirectory\fastgbs

On the Macintosh, you may need to edit the "environment"

file and change the line that reads:

FASTLIBS=fastgbs

to indicate the full directory path for the fastgbs file,

for example:

FASTLIBS=Q105:FASTA:fastgbs

(4) Finally, you will need to edit the fastgbs file. This is

usually the most confusing part of the installation. An

example of this file is shown below; to customize this

file for your machine, you will need to change the file

names from those provided in the fastgbs file to ones that

reflect the directory names and file names you use on your

machine. This is explained in more detail below. In

addition, some entries in the fastgbs file refer to other

files of file names. These files of file names (as

opposed to actual database files) may also need to be

edited.

2.2. Installing the libraries

2.2.1. The NBRF protein sequence library

The FASTA program package does not include any protein or

DNA sequence libraries. You can obtain the PIR protein sequence

database from:

National Biomedical Research Foundation

Georgetown University Medical Center

3900 Reservoir Rd, N.W.

Washington, D.C. 20007

In addition, this database is available via anonymous ftp from

the host "ftp.bchs.uh.edu". It is available in two formats, VMS

and CODATA format. The "VMS" format (library type 5 below) can

be searched much faster, can be easily reformatted for use by the

"BLAST" rapid searching program, and is compatible with the

Genetics Computer Group package of programs. The CODATA format

is used by the EUGENE/MBIR computing package from Baylor (library

type 2).

2.2.2. The GENBANK DNA sequence library

FASTA, and TFASTA search sequences from the GENBANK

"flatfile" (not ASN.1) DNA sequence library in the flat-file

format distributed by the National Center for Biotechnology

Information and the PIR format used by EBI/EMBL. CD-ROMs can be

obtained from:

Genbank

National Center for Biotechnology Information

National Library of Medicine

National Institutes of Health

8600 Rockville Pike

Bethesda, MD 20894

The GenBank DNA sequence library is also available via

anonymous FTP from ncbi.nlm.nih.gov.

2.2.3. The EBI/EMBL CD-ROM libraries

The European Bioinformatics Institute (EBI) is now

distributing the EMBL CD-ROM that contains both the complete EMBL

DNA sequence database (which should be essentially identical to

the GenBank DNA sequence database) and the SWISS-PROT protein

sequence database. SWISS-PROT is derived from the NBRF Protein

sequence database with additions from the EBI/EMBL DNA sequence

database. This CD-ROM is a "best-buy," since it provides both

DNA and protein sequence libraries. It is available from:

European Bioinformatics Institute

Hinxton Genome Campus, Hinxton Hall

Hinxton, Cambridge CB10 1RQ,

United Kingdom

Tel: +44 1223 4944

Fax: +44 1223 494468

Email: DATALIB@ebi.ac.uk

In addition, the SWISS-PROT protein sequence database is

available via anonymous FTP from ncbi.nlm.nih.gov.

2.3. Finding the libraries: FASTLIBS

FASTA and TFASTA use the environment variable FASTLIBS to

find the protein and DNA sequence libraries. The FASTLIBS

variable contains the name of a file that has the actual

filenames of the libraries. The FASTGBS file on is an example of

a file that can be referred to by FASTLIBS. To use the FASTGBS

file, type:

setenv FASTLIBS /usr/lib/fasta/fastgbs (BSD UNIX/csh)

export FASTLIBS=/usr/lib/fasta/fastgbs (SysV UNIX/ksh)

Then edit the FASTGBS file to indicate where the protein and DNA

sequence libraries can be found. If you have a hard disk and

your protein sequence library is kept in the file

/usr/lib/aabank.lib and your Genbank DNA sequence library is kept

in the directory: /usr/lib/genbank, then fastgbs might contain:

NBRF Protein$0P/usr/lib/seq/aabank.lib 0

SWISS PROT 10$0S/usr/lib/vmspir/swiss.seq 5

GB Primate$1P@/usr/lib/genbank/gpri.nam

GB Rodent$1R@/usr/lib/genbank/grod.nam

GB Mammal$1M@/usr/lib/genbank/gmammal.nam

^ 1 ^^^^ 4 ^ ^

23 (5)

The first line of this file says that there is a copy of the NBRF

protein sequence database (which is a protein database) that can

be selected by typing "P" on the command line or when the

database menu is presented in the file /usr/lib/seq/aabank.lib.

Note that there are 4 or 5 fields in the lines in fastgbs.

The first field is the description of the library which will be

displayed by FASTA; it ends with a '$'. The second field (1

character), is a 0 if the library is a protein library and 1 if

it is a DNA library. The third field (1 character) is the

character to be typed to select the library.

The fourth field is the name of the library file. In the

example above, the /usr/lib/seq/aabank.lib file contains the

entire protein sequence library. However the DNA library file

names are preceded by a '@', because these files (gpri.nam,

grod.nam, gmammal.nam) do not contain the sequences; instead they

contain the names of the files which contain the sequences. This

is done because the GENBANK DNA database is broken down in to a

large number of smaller files. In order to search the entire

primate database, you must search more than a dozen files.

In addition, an optional fifth field can be used to specify

the format of the library file. Alternatively, you can specify

the library format in a file of file names (a file preceded by an

'@'). This field must be separated from the file name by a space

character (' ') from the filename. In the example above, the

aabank.lib file is in Pearson/FASTA format, while the swiss.seq

file is in PIR/VMS format (from the EMBL CD-ROM). Currently,

FASTA can read the following formats:

0 Pearson/FASTA (>SEQID - comment/sequence)

1 Uncompressed Genbank (LOCUS/DEFINITION/ORIGIN)

2 NBRF CODATA (ENTRY/SEQUENCE)

3 EMBL/SWISS-PROT (ID/DE/SQ)

4 Intelligenetics (;comment/SEQID/sequence)

5 NBRF/PIR VMS (>P1;SEQID/comment/sequence)

6 GCG (version 8.0) Unix Protein and DNA (compressed)

11 NCBI Blast1.3.2 format (unix only)

In particular, this version will work with the EMBL and PIR VMS

formats that are distributed on the EMBL CD-ROM. The latter

format (PIR VMS) is much faster to search than EMBL format. This

release also works with the protein and DNA database formats

created for the BLASTP and BLASTN programs by SETDB and PRESSDB

and with the new NCBI search format. If a library format is not

specified, for example, because you are just comparing two

sequences, Pearson/FASTA (format 0) is used by default. To

change this default, you may set the LIBTYPE environment variable

to a number. For example,

setenv LIBTYPE 1

would cause the program to use the GenBank LOCUS format by

default for libraries (or the second sequence file), but the

Pearson/FASTA format would still be used for the query sequence.

You can specify a group of library files by putting a '@'

symbol before a file that contains a list of file names to be

searched. For example, if @gmam.nam is in the fastgbs file, the

file "gmam.nam" might contain the lines:

</usr/lib/genbank

gbpri.seq 1

gbrod.seq 1

gbmam.seq 1

In this case, the line beginning with a '<' indicates the

directory the files will be found in. The remaining lines name

the actual sequence files. So the first sequence file to be

searched would be:

/usr/lib/genbank/gbpri.seq

The notation "<PIRNAQ:" might be used under the VAX/VMS operating

system. Under UNIX, the trailing '/' is left off, so the library

directory might be written as "</usr/seqlib".

With version 1.4 of the FASTA package, the FASTA and TFASTA

programs can search a library composed of different files in

different sequence formats. For example, you may wish to search

the Genbank files (in GenBank flat file format) and the EMBL DNA

sequence database on CD-ROM. To do this, you simply list the

names and filetypes of the files to be searched in a file of

filenames. For example, to search the mammalian portion of

Genbank, the unannotated portion of Genbank, and the unannotated

portion of the EMBL library, you could use the file:

</usr/lib/DNA

gbpri.seq 1

# (this '#' causes the program to display the size of the library)

gbrod.seq 1

gbmam.seq 1

gbuna.seq 1

unanno.seq 5

You do not need to include library format numbers if you

only use the Pearson/FASTA version of the PIR protein se-

quence library. If no library type is specified, the

program assumes that type 0 is being used (unless you

have set LIBTYPE).

Support for the old compressed GenBank files, which have not been

distributed for more than four years, has been removed from

programs in the FASTA package.

Test the setup by running FASTA. Enter the sequence file

'MUSPLFM.AA' when the program requests it (this file is included

with the programs). The program should then ask you to select a

protein sequence library. Alternatively, if you run the TFASTA

program and use the MUSPLFM.AA query sequence, the program should

show you a selection of DNA sequence libraries. Once the fastgbs

file has been set up correctly, you can set FASTLIBS=fastgbs in

your AUTOEXEC.BAT file, and you will not need to remember where

the libraries are kept or how they are named.

FASTA and TFASTA must open a large number of files when

searching and reporting the results of a GENBANK floppy disk

format library search. You may have problems with the large

number of files under DOS on IBM-PC's (Unix and VMS users will

not have these problems). If you are going to search the GENBANK

floppy disk format DNA sequence library under DOS, you should add

the line:

FILES=16

to your CONFIG.SYS file. (Typically this is already done for

programs like Windows or WordPerfect.)

3. Using the FASTA Package

3.1. Overview

The FASTA sequence comparison programs all require similar

information, the name of a query sequence file, a library file,

and the ktup parameter. All of the programs can accept arguments

on the command line, or they will prompt for the file names and

ktup value.

To use FASTA, simply type:

FASTA

and you will be prompted for :

the name of the test sequence file

the name of the library file

and whether you want ktup = 1 or 2. (or 1 to 6 for DNA sequences)

ktup of 2 is about 5 times faster than ktup = 1.

For a 200 aa sequence against a 10,000,000 aa

library, the program takes about 30 min with

ktup = 2, 150 min with ktup = 1, on a 12 Mhz 286

IBM-PC.

The program can also be run by typing

FASTA test.aa /lib/bigfile.lib ktup (1 or 2)

Included with the package are the test files, MUSPLFM.AA,

LCBO.AA, MCHU.AA and BOVPRL.SEQ. To check to make certain that

everything is working, you can try:

fasta musplfm.aa lcbo.aa

and

tfasta musplfm.aa bovprl.seq

To test the local similarity programs LFASTA and PLFASTA, try:

lfasta mchu.aa mchu.aa

and

plfasta mchu.aa mchu.aa (use this only on an IBM-PC with graphics

or on a Tektronix terminal under UNIX or VMS)

MCHU (calmodulin) has four duplicated calcium binding sites that

are clearly detected by LFASTA. For a more complicated example,

try MWRTC1.aa, myosin heavy chain.

3.2. Sequence files

The FASTA programs know about three kinds of sequence files

(four under VMS): (1) plain sequence files that can only be used

as query sequences or for LFASTA, PRDF, and ALIGN. (2) Standard

library files. These are the same as plain sequence files, each

sequence is preceded by a comment line with a '>' in the first

column. (3) distributed sequence libraries (this is a broad class

that includes the NBRF/PIR VMS and blocked ascii formats, Genbank

flat-file format, EMBL flat-file format, and Intelligenetics

format. All of the files that you create should be of type (1)

or (2). Type (2) files (ones with a be used as query or library

sequence files by all of the programs.

I have included several sample test files, *.AA. The first

line may begin with a '>' or ';' followed by a comment. The

text after ';' in other lines will be ignored. Spaces and

tabs (and anything else that is not an amino-acid code) are

ignored.

Library files should have the form:

>Sequence name and identifier

A F A S Y T .... actual sequence.

F S S .... second line of sequence.

>Next sequence name and identifier

This is often referred to as "FASTA" or "Pearson" format. You

can build your own library by concatenating several sequence

files. Just be sure that each sequence is preceded by a line

beginning with a '>' with a sequence name.

The test file should not have lines longer than 120

characters, and sequences entered with word processors should use

a document mode, with normal carriage returns at the end of

lines.

Program Summary

3.3. Sequence search programs

FASTA universal sequence comparison. Defaults to comparing

protein sequences; if the sequences are > 85% A+C+G+T

or the -n option is used, a DNA sequence is assumed.

FASTX Search a protein sequence library using amino acid

sequence comparison to the forward three frames of a

translated DNA query sequence. (The reverse frames are

specified with the -i option.) Alignment scores allow

frameshifts; the final alignment uses a Smith-Waterman

type alignment routine (no limit on gaps) that allows

frameshifts.

TFASTA Search DNA library for a protein sequence by

translating the DNA sequence to protein in all six

frames (three forward frames with the -3 command line

option). TFASTA with ktup=2 is about as fast as a DNA

FASTA with ktup=4, and is substantially more sensitive.

(also reads the GENBANK library)

TFASTX Search DNA library for a protein sequence by

translating the DNA sequence to protein in all six

frames (three forward frames with the -3 command line

option) calculating similarity scores that allow

frameshifts. TFASTX produces an optimal Smith-Waterman

alignment of the query and translated-library sequence.

SSEARCH Universal sequence comparison using the Smith-Waterman

algorithm ( T. F. Smith and M. S. Waterman (1981) J.

Mol. Biol. 147:195-197). This program uses code

developed by Huang and Miller (X. Huang, R. C.

Hardison, W. Miller (1990) CABIOS 6:373-381) for

calculating the local similarity score and code from

the ALIGN program (see below) for calculating the local

alignment. SSEARCH is about 50-times slower than FASTA

with ktup=2 (for proteins).

ALIGN optimal global alignment of two sequences with no

short-cuts. This program is a slightly modified

version of one taken from E. Myers and W. Miller. The

algorithm is described in E. Myers and W. Miller,

"Optimal Alignments in Linear Space" (CABIOS (1988)

4:11-17).

3.4. Local similarity programs

LFASTA local similarity searches showing local alignments.

The algorithm used to calculate the local alignment in

a band has been improved (Chao, Pearson, and Miller,

submitted).

PLFASTA local similarity searches with plot output (on the IBM,

this program requires that the environment variable

BGIDIR be set).

PCLFASTA (unix only) local similarity searches with plot output

using pic commands.

LALIGN Calculates the N-best local alignments using a rigorous

algorithm. (N=10 by default.) The algorithm was

developed by Huang and Miller (X. Huang and W. Miller

(1991) Adv. Appl. Math. 12:337-357), which is a

linear-space version of an algorithm described by M. S.

Waterman and M. Eggert (J. Mol. Biol. 197:723-728).

Like SSEARCH, LALIGN is rigorous, but also very slow.

PLALIGN A version of LALIGN that plots its output to a screen

or to a Tektronix terminal emulator.

3.5. Statistical Significance

With version 2.0 of the FASTA program distribution, FASTA,

TFASTA, and SSEARCH now provide estimates of statistical

significance for library searches. Work by Altschul, Arratia,

Karlin, Mott, Waterman, and others (see Altschul et al. (1994)

Nature Genetics 6:119 for an excellent review) suggests that

local sequence similarity scores follow the extreme value

distribution, so that P(s > x) = 1 - exp(-exp(-lambda(x-u)) where

u = ln(Kmn)/lambda and m,m are the lengths of the query and

library sequence. This formula can be rewritten as: 1 - exp(-Kmn

exp(-lambda x), which shows that the average score for an

unrelated library sequence increases with the logarithm of the

length of the library sequence. FASTA and SSEARCH use simple

linear regression against the the log of the library sequence

length to calculate a normalized "z-score" with mean 50,

regardless of library sequence length, and variance 10. These

z-scores can then be used with the extreme value distribution and

the poisson distribution (to account for the fact that each

library sequence comparison is an independent test) to calculate

the number of library sequences to obtain a score greater than or

equal to the score obtained in the search. The original idea and

routines to do the linear regression on library sequence length

were provided Phil Green, U. Washington. This version of FASTA

and SSEARCH uses a slightly different strategy for fitting the

data than those originally provided by Dr. Green.

The expected number of sequences is plotted in the histogram

using an "*". Since the parameters for the extreme value

distribution are not calculated directly from the distribution of

similarity scores, the pattern of "*'s" in the histogram gives a

qualitative view of how well the statistical theory fits the

similarity scores calculated by FASTA and SSEARCH. For FASTA, if

optimized scores are calculated for each sequence in the database

(the default), the agreement between the actual distribution of

"z-scores" and the expected distribution based on the length

dependence of the score and the extreme value distribution is

usually very good. Likewise, the distribution of SSEARCH Smith-

Waterman scores typically agrees closely with the actual

distribution of "z-scores." The agreement with unoptimized

scores, ktup=2, is often not very good, with too many high

scoring sequences and too few low scoring sequences compared with

the predicted relationship between sequence length and similarity

score. In those cases, the expectation values may be

overestimates.

The statistical routines assume that the library contains a

large sample of unrelated sequences. If this is not the case,

then the expectation values are meaningless. Likewise, if there

are fewer than 20 sequences in the library, the statistical

calculations are not done.

For protein searches, library sequences with E() values <

0.01 for searches of a 10,000 entry protein database are almost

always homologous. Frequently sequences with E()-values from 1 -

10 are related as well. Remember, however, that these E() values

also reflect differences between the amino acid composition of

the query sequence and that of the "average" library sequence.

Thus, when searches are done with query sequences with "biased"

amino-acid composition, unrelated sequences may have

"significant" scores because of sequence bias. The programs

below, PRDF and PRSS, can address this problem by calculating

similarity scores for random sequences with the same length and

amino acid composition.

If optimization is not used ("-o"), E-values for DNA

sequences overestimate the significance of the scores that are

obtained and unrelated sequences frequently have E()-values <

0.0005. With optimization, the agreement between E()-value

compares favorably with protein sequence comparison. This is in

part due to the use of more stringent gap penalties for DNA

sequence comparison, -16, -4 rather than -12, -2. With the

latter penalties, many unrelated sequences appear to have

significant similarity. Nevertheless, since protein sequence

comparison is much more sensitive, DNA sequence comparison should

not be used to identify sequences that encode protein. Even with

ktup=6, optimization rarely increases run-times more than 50%

with mRNA-size query sequences. Optimization should be used

whenever possible.

Similar comments apply to TFASTA, where higher gap

penalties (-16,-4) are required for accurate statistical

estimates. Because TFASTA produces so many artificial "coding"

sequences with atypical amino acid compositions, the statistical

estimates with TFASTA are often over estimates. With optimized

scores, ktup=1, and gap penalties of -16, -4, unrelated sequences

will sometimes have E() values of 0.1. If initn scores are used,

unrelated sequences may have have E() values < 0.01.

PRDF improved version of RDF program that includes accurate

probability estimates for all three scoring methods

(includes local or window shuffle routine)

PRSS A version of PRDF that uses the rigorous Smith-Waterman

calculation used by SSEARCH.

RANDSEQ produces a randomly shuffled sequence from a query

sequence.

RELATE significance program described by Dayhoff (Atlas of

Protein Sequence and Structure, Vol. 5, Supplement 3).

Each chunk of 25 residues in one sequence is compared

to every 25 residue fragment of the second sequence.

Sequences which are genuinely related will have a large

number of scores greater than 3 standard deviations

above the mean score of all of the comparisons.

3.6. Other analysis programs

AACOMP calculate the amino acid composition and molecular

weight of a sequence.

BESTSCOR calculate the best self-comparison score.

GREASE Kyte-Doolittle hydropathicity profile

TGREASE graphic plot of Kyte-Doolittle profile

FROMGB convert from GenBank LOCUS format (also used by the

IBI-Pustell programs) to Pearson/FASTA format.

GARNIER A secondary structure prediction program using the

method of Garnier, Osgusthorpe, and Robson, J. Mol.

Biol., (1978) 120:97-120.

3.7. Options

These programs have a number of output options, which are

invoked by the environment variables LINLEN, SHOWALL, and MARKX.

Alternatively, these values can be controlled by command line

options. The number of sequence residues per output line is now

adjustable by setting the environment variable LINLEN, or the

command line option -w. LINLEN is normally 60, to change it set

LINLEN=80 before running the program or add -w 80 to the command

line. LINLEN can be set up to 200. SHOWALL (-a) determines

whether all, or just a portion, of the aligned sequences are

displayed. Previously, FASTP would show the entire length of

both sequences in an alignment while FASTN would only show the

portions of the two sequences that overlapped. Now the default is

to show only the overlap between the two sequences, to show

complete sequences, set SHOWALL=1, or use the -a option on the

command line.

The differences between the two aligned sequences can be

highlighted in three different ways by changing the environment

variable MARKX or the -m option. Normally (MARKX=0) the program

uses ':' do denote identities and '.' to denote conservative

replacements. If MARKX=1, the program will not mark identities;

instead conservative replacements are denoted by a 'x' and non-

conservative substitutions by a 'X'. If MARKX=2, the residues in

the second sequence are only shown if they are different from the

first. MARKX=3 displays the aligned library sequences without the

query sequence; these can be used to build a primitive multiple

alignment. MARKX=4 provides a graphical display of the

boundaries of the alignments. Thus the five options are:

MARKX=0 MARKX=1 MARKX=2 MARKX=3 MARKX=4

MWRTCGPPYT MWRTCGPPYT MWRTCGPPYT MWRTCGPPYT

::..:: ::: xx X ..KS..Y... MWKSCGYPYT ----------

MWKSCGYPYT MWKSCGYPYT

(fasta20u4, Feb. 1996) In addition MARKX=10 is a new, parseable

format for use with other programs. See the file"readme.v20u4"

for a more complete description.

3.8. Command line options

It is now possible to specify several options on the

command line, instead of using environment variables. The

command line options are preceded by a dash; the following

options are available:

-a same as showall=1

-A force Smith-Waterman alignments for DNA sequences and

TFASA. By default, only FASTA protein sequence

comparisons use Smith-Waterman alignments.

-b # Number of sequence scores to be shown on output. In

the absence of this option, fasta (and tfasta and

ssearch) display all library sequences obtaining

similarity scores with expectations less than 10.0 if

optimized score are used, or 2.0 if they are not. The

-b option can limit the display further, but it will

not cause additional sequences to be displayed.

-c # Threshold score for optimization (OPTCUT). Set "-c 1"

to optimize every sequence in a database. (This slows

the program down about 5-fold).

-E # Limit the number of scores and alignments shown based

on the expected number of scores. Used to override the

expectation value of 10.0 used by default. When used

with -Q, -E 2.0 will show all library sequences with

scores with an expectation value <= 2.0.

-d # Number of alignments to be reported by default. (Used

in conjunction with -Q). No longer necessary, see "-b"

above.

-f Penalty for the first residue in a gap (-12 by default

for proteins, -16 for DNA or for TFASTA).

-g Penalty for additional residues in a gap (-2 by default

for proteins, -4 for DNA and TFASTA ).

-h Penalty for frameshift (FASTX, TFASTX only).

-H Omit histogram.

-i Invert (reverse complement) the query sequence if it is

DNA. For TFASTX, search the reverse complement of the

library sequence only.

-k # Threshold for joining init1 segments to build an initn

score (GAPCUT).

-l file Location of library menu file (FASTLIBS).

-L Display more information about the library sequence in

the alignment.

-m # MARKX = # (0, 1, 2, 3, 4, 10)

-n Force the query sequence to be treated as a DNA

sequence. This is particularly useful for query

sequences that contain a large number of ambiguous

residues, e.g. transcription factor binding sites.

-O Send copy of results to "filename." Helpful for

environments without STDOUT.

-o Turn off default optimization of all scores greater

than OPTCUT. Sort results by "initn" scores.

-Q,-q Quiet - does not prompt for any input. Writes scores

and alignments to the terminal or standard output file.

-r file Save a results summary line for every sequence in the

sequence library. The summary line includes the

sequence identifier, superfamily number (if available)

position in the library, and the similarity scores

calculated. This option can be used to evaluate the

sensitivity and selectivity of different search

strategies (see W. R. Pearson (1991) Genomics 11:635-

650.)

-s file SMATRIX is read from file. Several SMATRIX files are

provided with the standard distribution. For protein

sequences: codaa.mat - based on minimum mutation

matrix; idnaa.mat - identity matrix; pam250.mat - the

PAM250 matrix developed by Dayhoff et al (Atlas of

Protein Sequence and Structure, vol. 5, suppl. 3,

1978); pam120.mat - a PAM120 matrix. The default

scoring matrix is BLOSUM50, PAM250 is available with

"-s 250", BLOSUM62 ("-s BL62") is also available.

-v (LINEVAL) values used for line styles in plfasta

-w # Line length (width) = number (<200)

-x Specifies offsets for the beginning of the query and

library sequence. For example, if you are comparing

upstream regions for two genes, and the first sequence

contains 500 nt of upstream sequence while the second

contains 300 nt of upstream sequence, you might try:

fasta -x "-500 -300" seq1.nt seq2.nt

If the -x option is not used, FASTA assumes numbering

starts with 1. This option will not work properly with

the translated library sequence with tfasta. (You

should double check to be certain the negative

numbering works properly.)

-y Set the width of the band used for calculating

"optimized" scores. For proteins and ktup=2, the width

is 16. For proteins with ktup=1, the width is 32 by

default. For DNA the width is 16.

-z Turn off statistical calculations.

-1 sort output by init1 score (as FASTP used to do).

-3 (TFASTA, TFASTX only) translate only three forward

frames

For example:

fasta -w 80 -a seq1.aa seq.aa

would compare the sequence in seq1.aa to that in seq2.aa and

display the results with 80 residues on an output line, showing

all of the residues in both sequences. Be sure to enter the

options before entering the file names, or just enter the options

on the command line, and the program will prompt for the file

names.

Not all of these options are appropriate for all of the

programs. The options above are used by FASTA and TFASTA. RELATE

uses the -s option, ALIGN uses the -w, -m, and -s options, and

the PRDF program uses -c, -f, -k, and -s.

4. Environment variable summary

Environment variables allow you to set search parameters

that will be used frequently when you run a program; for example,

if you prefer to use the PAM250 scoring matrix, you might "set

SMATRIX=250." Command line parameters, if used, always override

environment variable settings. The following environment

variables are used by this program:

AABANK the file name of the default sequence library.

FASTLIBS the location of the file which contains the list of

library files to be searched.

GAPCUT threshold used for joining init1 regions in the second

step of FASTA. Normally set based on sequence length

and ktup.

LIBTYPE used to specify the format of the library sequence for

FASTA and TFASTA.

LINLEN output line length - can go up to 200

LINEVAL used by plfasta to determine the relationship between

line style and similarity score (-v). This should be a

string of three numbers, e.g. "200 100 50"

MARKX symbol for denoting matches, mismatches. Note that this

symbol is only used across the optimized local region;

sequences that are outside this region are not marked.

OPTCUT Set the threshold to be used for optimization in a band

around the best initial region. Normally the OPTCUT

value is calculated from the length of the sequence and

the ktup value (for a 200 residue sequence, it is about

28). If OPTCUT=1, every sequence in the database will

be optimized. This is the most sensitive option.

PAMFACT This version of fasta uses a more sensitive method for

identifying initial regions. Instead of using a

constant factor (fact) for each match in a ktup, it

uses the scoring matrix (PAM) scores. While this works

well for protein sequences, it has not been as

carefully tested for DNA sequences, so by default, this

modification is used for proteins but not for DNA.

Setting the PAMFACT environment variable to 1 forces

the option on; PAMFACT=0 turns it off.

SHOWALL on output, show the complete sequence instead of just

the overlap of the two aligned sequences.

SMATRIX alternative scoring matrix file.

TEKPLOT (IBM-PC only, Unix and VMS versions generate Tektronix

graphics by default) Generate Tektronix output.

Normally, PLFASTA and TGREASE plot graphs using the

Turbo C graphics library. Unfortunately, often these

plots cannot be printed out without special programs.

However, if you set TEKPLOT=1, tektronix graphics

commands will be used. Tektronix commands can be used

together with the PLOTDEV program, available from

Microplot Systems. They no lonter sell this program,

but it can be downloaded from

http://iquest.com/~microplt/index1.html. PLOTDEV also

allows you to print out graphics on the screen.

As always, please inform me of bugs as soon as possible.

William R. Pearson

Department of Biochemistry

Box 440, Jordan Hall

U. of Virginia

Charlottesville, VA

wrp@virginia.EDU