Sciences and methods > Biosciences > Programs > BLAST > PHI-BLAST
 
Tehdyt toimenpiteet

PHI-BLAST

PHI-Blast
---------

PHI-BLAST (Pattern-Hit Initiated BLAST) is a search
program that combines matching of regular expressions
with local alignments surrounding the match.
The most important features of the program have been
incorporated into the BLAST software framework
partly for user convenience and partly so that
PHI-BLAST may be combined seamlessly with PSI-BLAST.
Other features that do not fit into the BLAST framework
will be released later as a separate program and/or
separate Web page query options.

One very restrictive way to identify protein motifs
is by regular expressions that must contain each instance
of the motif. The PROSITE database is a compilation of
restricted regular expressions that describe protein motifs.
Given a protein sequence S and a regular expression pattern P
occurring in S, PHI-BLAST helps answer the question:
What other protein sequences both contain an occurrence of P
and are homologous to S in the vicinity of the pattern occurrences?
PHI-BLAST may be preferable to just searching for pattern occurrences
because it filters out those cases where the pattern occurrence is
probably random and not indicative of homology.
PHI-BLAST may be preferable to other flavors of BLAST because
it is faster and because it allows the user to express
a rigid pattern occurrence requirement.

The pattern search methods in PHI-BLAST are based on the
algorithms in:

R. Baeza-Yates and G. Gonnet, Communications of the ACM 35(1992), pp. 74-82.
S. Wu and U. Manber, Communications of the ACM 35(1992), pp. 83-91.

The calculation of local alignments is done using a method
very similar to (and much of the same code as) gapped BLAST.
However, the method of evaluating statistical significance is different, and
is described below.

In the stand-alone mode the typical PHI-BLAST usage looks like:
blastpgp -i -k -p patseedp

where -i is followed by the file containing the query in FASTA format
where -k is followed by the file containing the pattern in a syntax given below
and "patseedp" indicates the mode of usage, not representing any file.

The syntax for the query sequence is FASTA format as for all other
BLAST queries. The syntax for patterns follows the rules of
PROSITE and is documented in detail below.
The specified pattern is not required to be in the PROSITE list.
Most of the other BLAST flags can be used with PHI-BLAST.
One important exception is that PHI-BLAST requires gapped
alignments (i.e. forbids -g F in the flags) because ungapped
alignments do not make sense for almost all patterns in PROSITE.


There is a second mode of PHI-BLAST usage that is important when
the specified pattern occurs more than 1 time in the query.
In this case, the user may be interested in restricting the
search for local alignments to a subset of the pattern occurrences.
This can be done with a search that looks like:
blastpgp -i -k -p seedp

in which case the use of the "seedp" option requires the user to
specify the location(s) of the interesting pattern occurrence(s)
in the pattern file. The syntax for how to specify pattern
occurrences is below. When there are multiple pattern occurrences in the
query it may be important to decide how many are of interest because
the E-value for matches is effectively multiplied by the number
of interesting pattern occurrences.

The PHI-BLAST Web page supports only the "patseedp" option.

PHI-BLAST is integrated with PSI-BLAST. In the command-line
mode, PSI-BLAST can be invoked by using the -j option, as usual.
When this is done as:
blastpgp -i -k -p patseedp -j

then the first round of searching uses PHI-BLAST and all subsequent
rounds use PSI-BLAST.
In the Web page setting, the user must explicitly invoke one round
at a time, and the PHI-BLAST Web page provides the option to
initiate a PSI-BLAST round with the PHI-BLAST results.
To describe a combined usage, use the term "PHI-PSI-BLAST"
(Pattern-Hit Initiated, Position-Specific Iterated BLAST).

Determining statistical significance.

When a query sequence Q matches a database sequence D in PHI-BLAST,
it is useful to subdivide Q and D into 3 disjoint pieces
Qleft Qpattern Qright
Dleft Dpattern Dright

The substrings Qpattern and Dpattern contain the pattern specified
in the pattern file. The pieces Qpattern and Dpattern are aligned
and that alignment is displayed as part of the PHI-BLAST output,
but the score for that alignment is mostly ignored.
The "reduced" score r of an alignment is the sum of the scores obtained
by aligning Qleft with Dleft and by aligning Qright with Dright.

The expected number of alignments with a reduced score >= x
is given by:
CN(Lambda*x + 1)e^(-Lambda *x)
where:

C and Lambda are "constants" depending on the score matrix and the
gap costs.
N is (number of occurrences of pattern in database) * (number of
occurrences of pattern in Q)
e is the base of the natural logarithm.

It is important to understand that this method of computing
the statistical significance of a PHI-BLAST alignment is mathematically
different from the method used for BLAST and PSI-BLAST alignments.
However, both methods provide E-values, so they the E_values are
displayed with a similar output syntax.

Rules for pattern syntax for PHI-BLAST.

The syntax for patterns in PHI-BLAST follows the conventions
of PROSITE. When using the stand-alone program, it
is permissible to have multiple patterns in a file separated
by a blank line between patterns. When using the Web-page
only one pattern is allowed per query.

Valid protein characters for PHI-BLAST patterns:
ABCDEFGHIKLMNPQRSTVWXYZU

Valid DNA characters for PHI-BLAST patterns:
ACGT

Other useful delimiters:
[ ] means any one of the characters enclosed in the brackets
e.g., [LFYT] means one occurrence of L or F or Y or T
- means nothing (this is a spacer character used by PROSITE)
x with nothing following means any residue
x(5) means 5 positions in which any residue is allowed (and similarly for any other
single number in parentheses after x)
x(2,4) means 2 to 4 positions where any residue is allowed,
and similarly for any other two numbers separated by a comma;
the first number should be < the second number.
> can occur only at the end of a pattern and means nothing
it may occur before a period
(another spacer used by PROSITE)

. may be used at the end of the pattern and means nothing

When using the stand-alone program, the pattern should
be in a file, with the first line starting:
ID
followed by 2 spaces and a text string giving the pattern a name.

There should also be a line starting
PA
followed by 2 spaces followed by the pattern description.

All other PROSITE codes in the first two columns are allowed,
but only the HI code, described below is relevant to PHI-BLAST.

Here is an example from PROSITE.

ID CNMP_BINDING_2; PATTERN.
AC PS00889;
DT OCT-1993 (CREATED); OCT-1993 (DATA UPDATE); NOV-1995 (INFO UPDATE).
DE Cyclic nucleotide-binding domain signature 2.
PA [LIVMF]-G-E-x-[GAS]-[LIVM]-x(5,11)-R-[STAQ]-A-x-[LIVMA]-x-[STACV].
NR /RELEASE=32,49340;
NR /TOTAL=57(36); /POSITIVE=57(36); /UNKNOWN=0(0); /FALSE_POS=0(0);
NR /FALSE_NEG=1; /PARTIAL=1;
CC /TAXO-RANGE=??EP?; /MAX-REPEAT=2;


The line starting
ID
gives the pattern a name.
The lines starting
AC, DT, DE, NR, NR, CC
are relevant to PROSITE users, but irrelevant to PHI-BLAST.
These lines are tolerated, but ignored by PHI-BLAST.

The line starting
PA
describes the pattern as:
one of LIVMF
followed by
G
followed by
E
followed by
any single character
followed by
one of GAS
followed by
one of LIVM
followed by
any 5 to 11 characters
followed by
R
followed by
one of STAQ
followed by
A
followed by
any single character
followed by
one of LIVMA
followed by
any single character
followed by
one of STACV

In this case the pattern ends with a period.
It can end with nothing after the last specifying symbol
or any number of > signs or periods or combination thereof.

Here is another example, illustrating the use of an HI line.

ID ER_TARGET; PATTERN.
PA [KRHQSA]-[DENQ]-E-L>.
HI (19 22)
HI (201 204)

In this example, the HI lines specify that the pattern
occurs twice, once from positions 19 through 22 in the
sequence and once from positions 201 through 204 in the
sequence.
These specifications are relevant when stand-alone PHI-BLAST is
used with the
seedp
option, in which the interesting occurrences of the pattern
in the sequence are specified. In this case the
HI lines specify which occurrence(s) of the pattern
should be used to find good alignments.

In general, the seedp option is more useful than the
standard patternp option ONLY when the
pattern occurs K > 1 times in the sequence AND
the user is interested in matching to J < K of those
occurrences.
Then using the HI lines enables the user to specify which
occurrences are of interest.

Additional functionality related to PHI-BLAST.

PHI-BLAST takes as input both a sequence and a query containing
that sequence and searches a sequence database for
other sequences containing the same pattern and having a good alignment.
One may be interested in asking two related, simpler questions:

1. Given a sequence and a database of patterns, which patterns occur
in the sequence and where?

2. Given a pattern and a sequence database, which sequences contain the
pattern and where?

These queries can be answered wih software closely related to PHI-BLAST,
but they do not fit into the output framework of BLAST because the
answers are simple lists without alignments and with no notion of
statistical significance.

The NCBI toolbox includes another program, currently called
seedtop
to answer the two queries above.

Query 1 can be asked with:
seedtop -i -k -p patmatchp

Query 2 can be asked with:
seedtop -d -k -p patternp

The -k argument is used similarly in all queries and the file
format is always the same. The standard pattern database is
PROSITE, but others (or a subset) can be used.
There are plans afoot to offer the patmatchp query (number 1) on
the PHI-BLAST web page or in its vicinity, but this would
be restricted to having PROSITE as the pattern database.


References

Zhang, Zheng, Alejandro A. SchŠffer, Webb Miller, Thomas L. Madden,
David J. Lipman, Eugene V. Koonin, and Stephen F. Altschul (1998),
"Protein sequence similarity searches using patterns as seeds", Nucleic
Acids Res. 26:3986-3990.

Altschul, Stephen F., Thomas L. Madden, Alejandro A. Schaffer,
Jinghui Zhang, Zheng Zhang, Webb Miller, and David J. Lipman (1997),
"Gapped BLAST and PSI-BLAST: a new generation of protein database
search programs", Nucleic Acids Res. 25:3389-3402.

Karlin, Samuel and Stephen F. Altschul (1990). Methods for
assessing the statistical significance of molecular sequence
features by using general scoring schemes. Proc. Natl. Acad.
Sci. USA 87:2264-68.

Karlin, Samuel and Stephen F. Altschul (1993). Applications
and statistics for multiple high-scoring segments in molecu-
lar sequences. Proc. Natl. Acad. Sci. USA 90:5873-7.

Schaffer, Alejandro A., L. Aravind, Thomas L. Madden, Sergei Shavirin
John L. Spouge, Yuri I. Wolf, Eugene V. Koonin, and Stephen F. Altschul (2001),
Improving PSI-BLAST Protein Database Search Sensitivity with Composition-Based
Statistics and Other Refinements. Nucleic Acids Res. 29:2994-3005.