Biomedical Engineering Reference
In-Depth Information
Where
A
i
and
B
j
are the two sequences to be aligned;
H
ij
is the score at position
A
i
,
B
j
;
s
(
A
i
B
j
) is the
score for aligning the characters at positions
i
and
j
;
w
x
is the penalty of a gap of length
x
in
sequence
A
, and
w
y
is the penalty for a gap of length of
y
in sequence
B
.
The three special provisions of this algorithm that favors local alignments are:
Negative numbers are not allowed in the scoring matrix.
l
l
Inexact matches are penalized.
l
The best score is sought anywhere in the matrix, and not simply in the last column or row.
Even though dynamic programming guarantees to find the best local or global alignment because the
technique considers all possible alignments, the technique is computationally intensive. Short
pairwise comparisons using the Smith-Waterman algorithm can require several hours of workstation
processing. High-end parallel processing hardware, such as the UCSC Kestrel server, which provides
the equivalent of 40 times the processing power of a desktop workstation, requires several minutes
for pairwise alignment using the Smith-Waterman algorithm. Given the computational overhead of
dynamic programming, a variety of first-pass, heuristic-based methods have been developed to
support alignment on the desktop workstation. These techniques, often referred to as word methods,
include the ubiquitous FASTA and BLAST algorithms, as described in the next section.
