readme.v33t0

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

allow scoring matrices with unusual scaling to be used.  In v33t05,
there was a line that excluded all scores > 300 from the statistical
estimation procedure.  While 300 is a high score with any "normal"
scoring matrix, some investigators were using matrices scaled 10X, so
that a score of 300 was really a score of 30 with a conventional
matrix, and should not be excluded.  Unfortunately, removing the test
to exclude scores > 300 meant that when a rRNA sequence was used to
search the bacterial division, tens of thousands of high scoring
related sequences were treated as if they were unrelated, with the
result that the variance estimates were much too high, and thus high
real scores had low z-scores, and thus were not statistically
significant.  (There appear to be more than 20,000 rRNA sequences in
the bacterial division of Genbank, almost 25% of all sequences).

The solution to the problem is a substantial enhancement in the
strategies used to exclude high-scoring, related sequences, the -z 1,
4, and 5 parameter estimation strategies.  The programs now estimate
the expected high scoring sequence by calculating an ungapped Lambda
and K, and then use a relatively conservative threshold for excluding
scores that are higher than would be expected 0.01 times by chance.
By calculating Lambda and K, we can scale the cutoff thresholds to
allow scoring matrices with unusual scales.  For "normal" searches,
there should be little change, but there should be an improvement for
searches with large numbers of related sequences in the database.

As a result of testing for this change, a bug in the karlin() function
used with -z 6 was found and corrected.

=======
>>Sept. 9, 2000

Changes to manshowbest.c to include correct display coordinates.

Significant changes to structs.h, param.h, p2_complib.c,
p2_workcomp.c, to store and use a reliable a_struct for alignment
coordinates.

Other cosmetic changes.

>>Sept. 7, 2000

Minor changes to complib.c, showrss.c, so that prss33 -q uses 200
shuffles and prss33 provides bit scores, rather than z-scores.
(no version number change).

Modifications to p2_complib.c to include superfamily numbers for
ps4comp* ms4comp*.

>>Aug 22, 2000

Changes to mmgetaa.c, ncbl2_mlib.c, dropfs.c to accomodate AIX.
00README.1st updated to reflect the current version and correct
outdated information on threads.

>>Aug. 3, 2000

Modifications to initpam2() in initsw.c to correct a problem with pam_x
when the -S option is used.

Modifications to compacc.c, scaleswn.c to ensure that residue numbers
are calculated properly when more than 2 Gb of sequence is searched.

>>July 12, 2000

Modifications to dropnfa.c so that DNA matches to 'N' will be included
in the "ungapped %identity".  Thus, a sequence that is 100% identical
for 100 nt on either side of a 100 nt region that has been masked to
'NNNNN' will be reported as: "67% identical (100% ungapped)".  This
has been added to deal with masked BAC-end databases.  It would be
better if masking changed the letters to lowercase, but the mouse
BAC-end sequences at TIGR use 'NNNNN'.  This is currently available
only for the fasta function, not [t]fast[x/y], etc, and only for DNA
sequences.

mk_n_pam() in apam.c modified to ensure that mismatch scores of -1
remain -1.

>>June 25, 2000

Modification to nxgetaa.c, nmgetaa.c, mmgetaa.c to return Genbank Accession
number as part of the descriptive string.

>>June 11, 2000

(no version change - not yet released)

Modifications to calcons(), calc_id(), showbest(), p_workcomp.c to
provide ngap_q (number of alignment gaps in query) , ngap_l (number
of gaps in library) information for -m 9 output.

>>June 6, 2000

(no version change - not yet released)

Modified scaleswn.c to provide better support for unconventional
scoring scoring matrices, in particular, scoring matrices where every
value is 50-times higher.  Previous versions of the MLE estimator (-z
2) started with lambda = 0.2, which is too high for a scoring matrix
going from -500:+1500. The initial estimate for lambda is now
calculated using the formula: lambda = pi/sqrt(6*variance).  For the
default -z 1, a restriction to limit scores to a maximum of 300 for
the statistical analysis was removed.

>>June 3, 2000

Modified aligment output, and -m 9 and -m10, to report an "ungapped"
identity as well as the traditional "gapped" identity.  The
traditional "gapped" identity reports the number of identities divided
by the overall length of the alignment, including gaps.  The
"ungapped" identity does not include gaps in the length of the
alignment.  This new value is included for alignments that include
introns; thus, a tfastx33 search might find the 100% identical genomic
sequence but report the gapped percent identity if a short intron were
included in the alignment (the alignment probably would not span a
long exon) as 66%.  The "ungapped" identity would remain 100%.  The
ungapped identity value is also shown in the "-m 9" output line after
the "gapped" fraction identical.

>>June 1, 2000

Modified -m 9 output to provide fraction identical, alignment boundary
information with the initial list of high scoring sequences, just as
the pv3comp and mp_comp versions do.  The -m 9 option now shows the
same alignment display as -m 0, but the width of the alignment is
increased by 40.  Thus, by default, -m 9 will show the list of best
hits, with percent identity, Smith-Waterman score, and alignment
boundaries initially, and then show alignments standard (-m 0)
alignments with 100 residues/line.

>>May 29, 2000

Correct some problems with reading data files with <CR>'s under unix.

nmgetaa.c/nxgetaa.c/mmgetaa.c have been modified to convert <TAB>
('\t') to <SPC> (' ') in descriptive lines.

=======

>>May 3, 2000

  Corrected problem with very low mean_var in fit_llen() in scaleswn.c.

>>May 2, 2000
  (no version number change - previous version not released)

  Merged fasta33t05d2 with fasta33t06.  Also removed restriction on
"-M size-range" to proteins - the size range now can be applied to DNA
as well.

>>May 1, 2000
 (changes to v33t05d merged into v33t06) 

Introduced changes to include '*' as a valid sequence character, which
indicates termination.  Thus, 'TGA', 'TAG', and 'TAA' are now
tranlated to '*' rather than 'X', and the protein PAM matrices have
been modified to provide a match score of approximately 1/2 the max
identity score for a '*:*' match.  Otherise, '*' is the same as 'X'.
This change only affects query sequences that include a '*' to
indicate an end of sequence, the '*' is not there by default.

The inclusion of '*' broke some things in tfasts33, tfastf33, fasty33,
and tfasty33, which were fixed today.

>>March 28, 2000/April 24, 2000
 --> v33t06

(a) -z 6 statistics that factor in composition
(b) -smatrix-offset pam-offset parameter

(a) This release provides a new statistics option, -z 6, which
provides a more sophisticated model that accounts for sequence
composition.  When -z 6 is used (only for fasta33(_t) and
ssearch33(_t)), the program calculates a composition parameter
comp=1/lambda using a modified version of the Karlin-Altschul karlin()
function.  As a result, every sequence in the database has an
associated length (n1) and composition (comp).

The length n1 and composition comp are used in the maximum likelihood
estimation described by Mott (1992) Bull. Math. Biol. 54:59-75.  Four
parameters are estimated, a0, a1, a2, and b1, and the probability of
obtaining a score is then:

p(s >= x) = 1-exp(-exp(-( a0 + a1*comp + a2*comp*log(n0*n1) + x)/(b1*comp)))

The maximum likelihood estimates of a0, a1, a2, and b1 are calculated
using the Nelder-Mead simplex search strategy.

The average Lambda is reported for the search using Lambda =
1/(b1*ave_comp).  Where ave_comp is the geometric mean of the comp values
calculated during the statistical estimates.

The "lambda/comp" calculation can fail for sequences with very biased
amino acid composition.  When this occurs, 'comp' is set to -1.0 (as
is 'H', the information content parameter) and the 'ave_comp' value is
used to calculate statistical significance.  (But obviously 'ave_comp'
is not really appropriate, since if the sequence had an average 'comp'
value, it would have been calculated.)  When -z 6 is used, the
alignment display shows the 'comp' and 'H' values for that library
sequence.

(b) Scoring matrix offsets - The main reason that the "lamdba/comp"
calculation fails is that, for the particular query/library sequence
pair, the expected score is not < 0, instead, Sum {p_ij S_ij} >= 0.0.
This problem is reported to 'stderr' when it occurs.  The simplest
solution to the problem is to provide an offset to the scoring matrix;
for example, to use Blosum62 - 1, which ranges from +10 to -5, rather
than the standard +11 to -4.  This option used to be available with
the -S offset option, but -S is now used to specify a lower-case
seg-ed database.  The offset can now be specified as part of the
scoring matrix name.  Thus, "-s BL62-1" uses Blosum62 reduced by 1 at
each entry.  The '-' character is used to indicate an offset, so
scoring matrix files must not have a '-' in their name.
Alternatively, "-s BL80+1" or "-s BL80--1" would add one to each value.

nxgetaa.c, nmgetaa.c, and mmgetaa.c have been edited to avoid string
run-off problems after strncpy().

Fixed problem where positive gap extension penalties in ssearch33
were not converted to negative values.

>>April 8, 2000

Fixed problem in calculating corrected sequence lengths for
Altschul-Gish probabilities.

>>March 30, 2000
  (no version change, date updated to March 30, 2000)

Corrected problem with -m 9 option.

The '*' character is now available to allow translated alignments to
extend through the termination codon. Thus, if a protein sequence ends
with a '*', and matches in to a translated termination codon, the
score will be increased.  The *:* match score is set to 1/2 the max
positive score for the matrix (see upam.h).  This strategy can also be
used to upweight a match that extends all the way to the end of a
full-length sequence by putting '*' at the end of both the query and
library protein sequences.  Recognition of '*' will probably become a
command line option.

>>March 21, 2000
  (no version change, previous version not distributed)

Changes to map_db.c, list_db.c, and mmgetaa.c to accomodate large
sequence files.  Long (64-bit on some systems) variables are now used
to specify file and memory position for the memory mapped functions.
As a result, there are now two *.xin (memory mapped index) file
formats: MP0, which uses 32-bit longs, and MP1, which uses 64-bit
longs. On 64-bit machines, MP0 32-bit indices are read properly, but
limit the database size to 2 or 4 Gb; MP1 64-bit indices allow very
large databases.  Blast2.0 formatdb databases are still limited to
4Gb.  To compile map_db.c to generate 64-bit index files, include the
compile time option -DBIG_LIB64 in the Makefile.  (Currently this
option has been tested only on the DEC Alpha and SGI platforms, and
will work only with Unix versions that provide 64-bit longs and 64-bit
ftell()'s.)

The -R results file now uses sfn_cmp() to report a matching
superfamily number, if one exists, and '0' otherwise.

>>March 12, 2000
  (no version change, previous version not distributed)

Provide new strategy for specifying library abbreviations.  In
addition to:

	fasta33 query.aa %anr

one can also specify:

	fasta33 query.aa %pir1+sp+nr
or
	fasta33 query.aa +pir1+sp+nr
or 
	fasta33 query.aa %+pir1+sp+nr

where the + anywhere in the library name string indicates that
variable length library names, separated by '+', are being used (the
last '+' is optional).  The FASTLIBS file then becomes:

================
PIR1 Annotated Protein Database (rel 56)$0+pir1+/slib2/blast/pir1.lseg
NBRF Protein database (complete)$0+nbrf+@/seqlib/lib/NBRF.nam
NRL_3d structure database$0D/seqlib/lib/nrl_3d.seq 5
NCBI/Blast non-redundant proteins$0+nr+/slib2/blast/nr.lseg
NCBI/Blast Swissprot$0+sp+/slib2/blast/swissprot.lseg
================

The two abbreviation types, single letter and +word+, cannot be
intermixed, and at least initially, +word+ specifiers are
case-sensitive (single letter abbreviations are not) and will not be
available interactively, only on the command line.

Removed 'K' estimate for Expectation_n, Expectation_i fits to the
distribution of unrelated similarity scores.  'K' cannot be calculated
from the data available.  'Lamdba' can be calculated, it is
1.28255/sqrt(mean_var), and is still available.

>>March 3, 2000 
 (no version change)

changed Makefile33.common, Makefile.common, to incorporate $(NRAND)
rather than "rand48".  Provide nrandom.c which uses random(), as
replacement for nrand.c, which uses rand48().

>>February 8, 2000
  --> v33t05

Fixes to scaleswn.c (proc_hist_ml) to set num_db_entries properly.
Scaleswn.c also provides Lambda estimates for -z 1/11 (Expectation_n),
and -z 1/14 (Expectation_i) statistical estimates.

Modifications to calc_id() to correct bug in counting identities.
Modified showalign() to use calc_id() with -m 9, for simpler
debugging.

Additional modifications to dropfa*.c files to deal properly with 'n's