Biology Reference
In-Depth Information
Fig. 1 Pairwise sequence alignment as a directed graph
lower-right of the grid. Each alignment can be represented by a
unique path, conversely, each path corresponds to a unique align-
ment. Thus, the set of the alignments and the set of the described
paths in the graph have one-to-one mapping and can be used
interchangeably for practical purposes.
A sequence alignment program should search for the alignment
which makes the most biological sense. Practically, this is achieved
by assigning alignment scores to each of the alignments by a
defined computation procedure, and searching for the best scores
among the valid alignments. Every alignment has to be considered
as a candidate and evaluated in a search procedure. According to
this, all alignment paths in the alignment grid have to be considered
in the search space. However, the cardinality of this search set grows
rapidly with the length of the sequences. The number of possible
alignments can be computed using the function
f
of Waterman [
1
].
This function considers the cases given that
k
residues of
X
and
Y
match and the rest are aligned with gaps. In this case, (
j
X
j
k
)
residues of
X
and (
k
) residues of
Y
are aligned with a gap.
The total length of the alignment is then
j
Y
j
ðj
X
j
k
Þþðj
Y
j
k
Þþ
k
¼
j
X
jþj
Y
j
k
. Out of
ðj
X
jþj
Y
j
k
Þ!
permutations, picking the
valid ones with the correct ordering of
X
and
Y
residues,
