Biology Reference
In-Depth Information
Fig. 2 Basic pair-HMM model for sequence alignment of two sequences
3.3 Partition
Function
The partition function of alignments calculates the pairwise
posterior probabilities by generating suboptimal alignments using
dynamic programming. For all global alignments of protein
sequences
X
and
Y
ending at position (
i
,
j
), define
Z
(
i
,
j
) to denote
the partition function,
Z
M
(
i
,
j
) to denote the partition function
with
X
i
aligned to
Y
j
,
Z
E
(
i
,
j
) to denote the partition function with
Y
j
aligned to a gap, and
Z
F
(
i
,
j
) to denote the partition function
with
X
i
aligned to a gap. The partition function can then be defined
recursively as
ð
Þ
e
βsX
i
;Y
j
Z
M
ð
i
;
j
Þ¼
Z
ð
i
1
;
j
1
Þ
e
βρ
þ
e
βσ
Z
E
ð
i
;
j
Þ¼
Z
M
ð
i
;
j
1
Þ
Z
E
ð
i
;
j
1
Þ
(2)
e
βρ
þ
e
βσ
Z
F
ð
i
;
j
Þ¼
Z
M
ð
i
1
;
j
Þ
Z
F
ð
i
1
;
j
Þ
Z
ð
i
;
j
Þ¼
Z
M
ð
i
;
j
Þþ
Z
E
ð
i
;
j
Þþ
Z
F
ð
i
;
j
Þ;
where
s
(
X
i
,
Y
j
) is the substitution score between residues
X
i
and
Y
j
,
ρ
(
ρ
0) is the gap open penalty,
σ
(
σ
0) is the gap extension
penalty, and
measures the deviation between suboptimal and
optimal alignments.
Once having the alignment partition function matrices con-
structed, the posterior probability
P
(
X
i
β
Y
j
) can be computed as
Z
0
M
ð
Z
M
ð
i
1
;
j
1
Þ
i
þ
1
;
j
þ
1
Þ
ð
Þ
;
e
βsX
i
;Y
j
P
ð
X
i
Y
j
Þ¼
(3)
Z
where
Z
0
M
(
i
,
j
) represents the partition function of all the reverse
alignments starting from position (|
X
|, |
Y
|) and ending at (
i
,
j
) with
X
i
aligned to
Y
j
, for 1
|
Y|
. As mentioned
above, a pair-HMM and a partition function are combined together
to compute the pairwise posterior probability matrix. After com-
puting the probability matrix
P
a
XY
using the pair-HMM and matrix
P
b
XY
using the partition function, the final probability matrix
P
XY
is
calculated by combining these two matrices as the root mean square
of the corresponding values in
P
a
XY
and
P
b
XY
:
i
|
X
| and 1
j
s
P
XY
ð
2
2
X
i
Y
j
Þ
þ
P
XY
ð
X
i
Y
j
Þ
P
XY
ð
X
i
Y
j
Þ¼
:
(4)
2
