Biology Reference
In-Depth Information
ðj
X
jþj
Y
j
k
Þ!
#
alignments with k residue matches
¼
Þ!
:
(1)
k
!ðj
X
j
k
Þ!ðj
Y
j
k
Summing up for the all possibilities of
k
matches gives the total
number of alignments
min
ðj
X
X
j;j
Y
jÞ
ðj
X
jþj
Y
j
k
Þ!
#
alignments
¼
Þ!
:
(2)
k
!ðj
X
j
k
Þ!ðj
Y
j
k
k
¼
0
Waterman function attains large numbers very rapidly. For
the example above, with
5, there are 7,183
possible alignments. This exceeds a million when we have
sequences of ten residues. As a real-life example, we can assume
aligning the
j
X
j¼
7 and
j
Y
j¼
β
2
microglobulin proteins of human and mouse (both
with 119 residues). If we had a computer capable of performing
one zetta-operations (10
21
operations per second), it would take
around 2
10
61
years to evaluate and find the best alignments.
Fortunately, best scoring alignments can be found without com-
puting the score of each alignment individually. Currently accepted
alignment scoring schemes can be formulated recursively. Dynamic
programming exploits this formation and attempts to solve
the problem by dividing the problem into subproblems [
2
]. The
computational simplification comes from the fact that a subprob-
lem is needed to be solved several times to compute the total
problem. The program basically “remembers” the solutions used
several times and calls it from the memory instead of evaluating
them over and over again.
Before going into the details of evaluating sequence alignments
using dynamic programming, we can briefly see how the method-
ology handles recursive computations efficiently. In computer
science terms, a recursive function is a finite step procedure that
contains itself in its definition and different argument instances are
drawn from an argument sequence for each time the function is
called. A minimal set of function values has to be known by the
computer to evaluate other instances. According to the top-down
computation procedure, the function is called for a given argument.
Another instance of the same function is called in the function due
to the definition. This recursive callings terminate when a known
instance of the function is met, and each function visited previously
is computed traversing back to the desired instance of the function,
where the recursion started.
Computation of Fibonacci numbers is a simple yet instructive
example to observe the top-down evaluation of recursive functions.
The
n
th Fibonacci number is defined as
2.1 The Optimum
Path Problem and
Dynamic Programming
(3)
Figure
2
a represents the top-down computation of
F
(5). By
the number definition
F
F
ð
n
Þ¼
F
ð
n
1
Þþ
F
ð
n
2
Þ;
F
ð
0
Þ¼
0
;
F
ð
1
Þ¼
1
:
ð
5
Þ¼
F
ð
4
Þþ
F
ð
3
Þ
, so the functions
F
(4)
