fasta20.doc

序列对齐 Compare a protein sequence to a protein sequence database or a DNA sequence to a DNA sequenc

    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.