Biology Reference
In-Depth Information
where
S
(
a
) is the score of the alignment under the given scoring
matrix. In this setting one can then treat the alignment score as
negative energy and
T
as the thermodynamic temperature, similar
to what is done in statistical mechanics. Analogous to the statistical
mechanical framework Miyazawa [
14
] defined the partition func-
tion of alignments as
X
e
SðaÞ T
=
Z
ð
T
Þ¼
;
(5)
a
2
A
where
A
is the set of all alignments of
x
and
y
. With the partition
function in hand the probability of an alignment
a
can now be
defined as
e
SðaÞ=T
(6)
As
T
approaches infinity all alignments are equally probable,
whereas at small values of
T
only the nearly optimal alignments have
the highest probabilities. Thus, the temperature parameter
T
can be
interpreted as a measure of deviation from the optimal alignment.
The alignment partition function can be computed using recur-
sions similar to the Needleman-Wunsch dynamic algorithm.
Let
Z
ij
represent the partition function of all alignments of
x
1
...
i
and
y
1
...
j
ending in
x
i
paired with
y
j
, and
S
ij
(
a
) represent the score of
alignment a of
x
1
...
i
and
y
1
...
j
. According to Eq.
2
.
Pa
ð
;
T
Þ¼
=
Z
ð
T
Þ
:
0
1
X
X
ðÞ
@
A
e
sx
i
;y
j
=
T
Z
i;j
¼
e
S
ij
ðaÞ T
=
e
S
i
1
;j
1
ðaÞ T
=
¼
;
(7)
a
2
A
ij
a
2
A
ij
¼
ij
1
where
A
ij
is the set of all alignments of
x
1
...
i
and
y
1
...
j
, and
s
(
x
i
,
y
j
)is
the score of aligning residue
x
i
with
y
j
. The summation in the
bracket on the right hand side of the above equation is precisely
the partition function of all alignments of
x
1
...
i 1
and
y
1
...
j1
.
We can thus compute the partition function matrices using
standard dynamic programming.
e
sx
i
;y
j
ðÞ
=
T
Z
i;j
¼
Z
i
1
;j
1
þ
Z
i
1
;j
1
þ
Z
i
1
;j
1
Z
i;j
¼
Z
i;j
1
e
g=T
Z
i;j
1
e
ext =
þ
(8)
Z
i;j
¼
Z
i
1
;j
e
g=T
Z
i
1
;j
e
ext =
þ
Z
i;j
þ
Z
i;j
þ
Z
i;j
:
Z
i;j
¼
Here
s
(
x
i
,
y
j
) represents the score of aligning residue
x
i
with
y
j
,
g
is
the gap open penalty, and
ext
is the gap extension penalty.
The matrix
Z
ij
represents the partition function of all alignments
ending in
x
i
paired with
y
j
. Similarly
Z
ij
represents the partition
function of all alignments in which
y
j
is aligned to a gap and
Z
ij
all
alignments in which
x
i
is aligned to a gap. Boundary conditions and
further details can be obtained from Miyazawa [
14
].
