Biology Reference
In-Depth Information
Fig. 5 Needleman-Wunsch algorithm example
The space required for the reverse-scan phase is the same as the
length of the alignment that can be neglected. For the computation
of
S
(
i
,
j
), the operation number equals the number of the parents of
the cell
c
(
i
,
j
),
i
þ
j
þ
1. Then the total number of computations is
jXj
jY j
2
2
i
þ
j
¼
0
:
5
ðj
X
j
j
Y
jþj
X
jj
Y
j
þ
4
j
X
jj
Y
jÞ
(7)
i
j
n
3
so that the complexity is
. Similar to the space requirement,
the number of operations performed at the reverse-scan phase
equals the alignment size and it can be included in the cubic
complexity. Therefore, the original Needleman-Wunsch algorithm
runs in cubic time with quadratic space requirements.
Oð
Þ
The alignment algorithm discussed addresses the global alignment
in which a pair of sequences needs to be aligned entirely from
the first residues to the last ones. However in certain cases, the
similarity searched between two sequences might not be global.
For example, if we are searching for the location of a gene in a
genome, the gene sequence has to be aligned globally only in a local
region of a genome sequence. Overlapping fragment regions
are also the main interest in DNA fragment assembly problems.
In both problems, the flanking regions outside the locally aligned
parts are not of interest and they should be filled with gaps in the
alignment. This problem is referred as the semi-global alignment
problem. A variation of the Needleman-Wunsch algorithm can
address this problem by behaving liberal on the gaps that are at
the beginning or at the end of an alignment. The simple modifica-
tion is not punishing these gaps by assigning zero scores to the
edges at the boundaries of the alignment grid (i.e.,
e
0
;p
3.1 Extension to
Different Alignment
Problems
ð
0
;
q
Þ¼
