in general imply that each entry
of a sequence database is compared to the query sequence sequentially,
and the result is a list of database entries which are similar
to the query sequence. The receipt of this program type
reads as follows:
start program
initialise top-scoring list
for each entry in database
{
compare database sequence with query sequence
evaluate similarity as "score"
compare "score" to top-scoring list
if "score" better than lowest entry
{
place entry in top-scoring list
}
}
normalise top-scoring list
for each entry in top-scoring list
{
determine statistics
print out result
}
Depending on the algorithm or implementation, some of
the steps might be missing or integrated in other steps. Sophisticated
sequence searching which performs extremely fast might be based
on two approaches:
- Use of so-called rigorous searching
algorithms such as the Smith and Watermann type of search already
known from the 'bestfit'
program , doing an accurate comparison. These programs execute
the central searching loop in a specifically tuned fashion, and
run best on special hardware such as the MasPar and
Bioccelerator systems.
- Use of heuristic searching algorithms
which reduce the compute time needed in the central searching
loop. Approximations in comparison are based on the assumption
that sequence similarity can be expressed as tightly accumulated
regions of identical oligomers or short peptides. Either computed
on-the-fly ( 'fasta' type of program) or in
a pre-processing step ( 'blast' program type),
the heuristic searching programs will run on smaller, general-purpose
machines and even PCs might occasionally be used.
Sequence Searching with Heuristic Methods
Principle of Similarity Detection
A powerful heuristic of a fast screening can be expressed
as follows:
Two sequences are similar if a sufficient number of identical
oligomers is found at a given arrangement of the two.
The internal loop of a sequence searching program (see above)
requires the identification of a score, which
is a numerical value describing the quality of a sequence comparison.
The observed score depends on
- the heuristic used to determine the similarity
- the alphabet used for comparison (DNA / proteins)
- extensions of the heuristic to join several
hits in the same pair which can be combined to produce alignments
later.
The numerical values of scores are specific for a given program
and must not be used for comparison between different algorithms
or result output. Unless a statistical significance or another
type of normalisation is computed, (see below) the score values
are relative
in relation to the search sequence and its algorithm. The following
example shall demonstrate how a heuristic sequence search algorithm
might be implemented. We do this on DNA level but no fundamental
difference will be seen in protein comparisons, as the heuristic
algorithms score with identities of short sequence fragments
rather than using
comparison tables . To a certain extent, the comparison
using identities of oligomers can be visualised as a
dotplot-type of comparison. We reuse the example of earlier
chapters, with
atggtaatggcacaattgactttcctgaatttctga Seq. A (formerly, horizontal sequence)
tgatggtcaagtaaactatgaagagttt Seq. B (formerly, vertical sequence)
In contrast to the dotplot, however, we now create a
table of oligomers and note the location of
the occurrence of these oligomers in the sequences. We are going
to use di-nucleotides here, which is for the sake of brevity
only, as nucleotide sequences typically use larger "words" (such
as six or more). Sixteen oligomers are possible, but not all
of them are found in the two sequences:
A B A B
AA 6,14,28 9,13,14,21 CA 11,13 8
AC 12,19 15 CC 24 -
AG - 10,22,24 CG - -
AT 1,7,15,29 3,18 CT 20,25,33 16
GA 18,27,35 2,20,23 TA 5 12,17
GC 10 - TC 23,32 7
GG 3,9 5 TG 2,8,17,26,34 1,4,19
GT 4 6,11,25 TT 16,21,22,30,31 26,27
Having created such a table, we may compute now the largest
segment of identity between the two sequences. The question,
therefore, is whether we can find oligomers which match at a
given, but identical shift of the two sequences. This can be
readily achieved by calculating all observed differences and
their occurrence:
Shift
observed -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
(in A) ----------------------------------------------------------------------
Locations 25 8 13 7 11 2 14 1 6 22 18 4 5 6 9 16
26 14 8 14 2 12 21 21 6
27 30 9 3 15 22 14
28 31 19 4
20 17
27 18
30
31
JAMF source code
BioCompanion V2.x (1995)