III. STRATEGIES FOR FINDING DISTANT SIMILARITIES
Finding a distant similarity means defining a new similarity group of
sequences and provide a description for it in terms of a sequence pattern
or profile. This description (i.e. the pattern) has to be diagnostic, i.e.
it has to cover only the members of the new group. In fact, such a diagnostic
pattern is sometimes regarded sufficient to prove the existence of the
group.
In principle, we can identify a group of sequences by some kind of a
database search. It can be simple database search, or profile search, or
pattern search. The process of identifying a group can be graphically depicted
as follows:
In the unsuccesful case, the members of the similarity group can not
be distinguished from other members of the database. In the successful case,
the new group is pulled out from underneath the pile of the other database
entries. There are four participants in this game: 1) query, 2) scoring
scheme (replacement matrix), 3) database, and 4) user. We
will now classify the search strategies based on these four factors.
As an hypothetical example, imagine that simple database search using
the BLAST program pulled out 2 sequences that are weakly similar to the
query sequence. All other suspected homologs of the query are buried somewhere
in the search results.
Using a better query, like a pattern, or using a better scoring scheme,
or a different database, will separate the known homologs from the unrelated
sequences and may reveal new members of the similarity group
Query-based strategies
The simplest thing one can do is to delete all unimportant parts of
the query and use only the suspected similarity region for database search.
Clearly, the unimportant parts of the query only provide "noise"
in the alignments, so it is better to get rid of them.
Second, we can replace the query with an alignment motif. Such a motif
can be derived intuitively, or we can use programs, such as PIMA or PROPAT for building
them. We will now use the new motif as a query. If it identifies a closed
group of sequences, we found the new similarity. If we do not succeed,
we can try to build a profile, and use that as a query, until we arrive
to a situation as shown in the above figure B. Naturally, one has to use
a great deal of biological knowledge in order to evaluate the group, e.g.
using the rules summarized in
Finally, there is a simple presentation strategy, based on the query:
Each alignment (obtained e.g. using BLAST) can be graphically mapped onto
the query and in this way the "conspicuous regions" of the query
can be easily picked up by inspection (graphic sorting).
Score-based strategies
If one can construct a special replacement matrix that is specific for a given similarity group, that matrix will eventually pull out the new similarity group in a database search. Naturally, one can not find a specific matrix for a group not yet found. However one can find a matrix that is more sensitive to most similarity groups. As already mentioned, some amino acids like C and P are structurally important while W and H are frequent participants in motifs. One can build a matrix that will assign a double cost (matrix diagonal value) for these amino acids. This matrix can be used with any search program, sometimes with good results.
We can build statistical replacement matrices based on the multiple alignments of known modules (domains). Both of these strategies are highly empirical, and there is no guarantee for success. They can provide a good starting point, however. Namely, the sequences that are fished out by this method can be further used to build motifs and profiles and the searches can be statistically evaluated.
Beside the matrix, careful choice of the gap penalty can also improve
the sensitivity. The philosophy of choosing a formula for gap penalty is
usually quite arbitrary. Some simple strategies like length dependent gaps,
improved sensitivity by themselves. One can build a gap penalty function
dependent on the predicted secondary structure of the query. For example
it is known that a-helices do not usually accept
insertions and deletions, so one can put a higher gap penalty for these
regions.
Database-driven strategies
We can also clean up the database, and create a streamlined database for distant similarity searching. "Cleaning up" means discarding a part of the sequences and concentrating on a given part of the database. One method is to discard the repetitive (low complexity) part of the database. This is a simple, automated procedure which leads to a database in which the repetitive sequences are substituted with X-es. A second strategy is to retain only those parts of the database in which the structure or function is known. This is the domain-library approach employed by SBASE. Finally, one can retain only those sequence-regions about which we know that they bear similarity to other sequences. This is the approach of PRODOM. In all of these cases we can use simple search programs, but we can also use profile-search and other advanced search strategies.
The last, and perhaps most important way for cleaning up a database
is to transform it into a database of patterns. To do this, we have to
identify the homology groups and generate pattern descriptions for them.
This process is laborious and lags behind the growing databases. Furthermore,
the descriptions are inevitably biased. Nevertheless, the pattern collections
(like PROSITE or PRINTS ) are easy to use and are the first things to try
whenever a new sequence is found.
Output-processing tools
Property patterns - Flexible patterns - Classical profile method - Improved profile methods - Automated pattern generation - Automated iterative motif search - Other recent methods
Many interesting patterns are not detected simply because the user overlooks
them. During pattern hunting, the user has to evaluate a large number of
alignments and some weak patterns may be buried between random hits. Sometimes
patterns coincide with the same or similar function in various proteins,
but the user has no time or patience to look up the annotation part of
the sequence entries in which the functional information is found. All
these problems lead to the user missing interesting patterns that are otherwise
present in a database serach output. There are a number of programs, sometimes
called as output processors, that help the user to process search
outputs.
In general these are simple programs that require very little additional
computer time.
PATCO is a program that collects recurrent patterns (in fact, consensus
sequences) from FASTA outputs. It is installed on ICGEBnet as a part of the
ICGEBprot program. It is a simple algroithm which is nevertheless able
to produce quite satisfactory patterns, useable to start pattern building
with more sophisticated methods.
FTHOM is a program that examines if BLAST alignments coincide with functionally
assigned domains in Swiss-Prot. The program compares the alignment endpoints
with the feature tables and assigns the scores to feature names according
to the overlap between a feature and the alignment.
Erik Sonhammers BLAST output processing tool is an excellent example of an interactive output processor. It contains several interesting features, for example a graphic representation (graphic sorting) of the alignments along a query. As BLAST produces a large number of short alignments, this is a very useful graphic summary.
Most "advanced strategies" use a combination of the above
approaches. For example, the SBASE search server uses a domain library
as the database, and the output is graphically sorted (projected onto the
query). The BCM search launcher also uses graphic sorting, and uses a variety
of automatically generated pattern databases. Some of the recent methods
were recently reviewed by Bork and Gibson.4
The program PROPAT, developed by Bork and colleagues,5
has been applied many times in the detection of distant homologies. This
method is able to generalise a pattern, even from a rather small learning
set, by automatically deriving distinct combinations of physicochemical
properties for each position; a vector of such properties is assigned to
each amino acid . It can be used for a single motif, combinations of motifs,
or for whole domains, and is already a step towards profile searching,
since a vector of weights (in this case penalties) is assigned to each
position of the alignment (including gaps). PROPAT can search 6frame
translations of DNA databases.
The flexible patterns of Barton and Sternberg6
combine features of motifs and profiles. The patterns can be set up in
various ways but are essentially permutations of conserved blocks, separated
by gaps of specified ranges, and are compared to sequences using a dynamic
programming approach. The Barton approach has been applied, for example,
in a recent survey of the DHR domain distribution.7
Profile analysis as implemented by Gribskov et al.8
performs exhaustive alignment by dynamic programming of a familybased
scoring matrix against test sequences. The profile is comprised of two
components for each position in the alignment: scores for the 20 amino
acids and variable gap opening and extension penalties. The amino acid
substitution scores are created by summing Dayhoff exchange matrix values
according to the observed amino acids in each column of the alignment.
Gap penalties are reduced at positions with gaps, according to the length
of the longest insertion spanning that point in the alignment. The programs
PROFILEMAKE, PROFILESEARCH and PROFILEGAP are widely available through
the GCG sequence analysis package,9
making them the most frequently used programs in the field of motif and
profile searches. However the GCG PROFILESEARCH (including version 8.0)
does not handle current database sizes while failing to warn the
user clearly that the search is incomplete. The TPROFILESEARCH version
(available from Peter Rice, EBI, Hinxton, UK) corrects this problem.
Starting from a set of sequences in the GCG format, you can build a
PROFILE using the GCG PROFILE program. You can submit a GCG PROFILE for
searching databases on the BIOCCELERATOR (Israel) at
