Biology Reference
In-Depth Information
F
0
M
ð
F
M
ð
i
j
Þ
i
þ
j
þ
Þ
1
;
1
1
;
1
p
1
ð
x
i
y
j
Þ¼
F
e
W
1
β
sðx
i
;
y
j
ÞþW
2
SS
ð
ss
ðx
i
Þ
;
ss
ðy
j
ÞÞþW
3
SA
ð
sa
ðx
i
Þ
;
sa
ðy
j
ÞÞ
;
(3)
where
F
0
M
ð
is the partition function of all the reverse alignments
from the ending position (
n
1
,
n
2
) till position (
i
,
j
) with
x
i
aligned
to
y
j
.
The second kind of pairwise probability matrix
P
XY
is calcu-
lated by a pair hidden Markov model (HMM) combining both
Forward and Backward algorithm [
4
,
5
,
16
]. State emissions and
transitions are used in pair HMM to calculate the pairwise prob-
abilities. No secondary structure and solvent accessibility informa-
tion is used to generate the second type of pairwise probability
matrix
P
XY
.
Based on both
P
XY
and
P
XY
, the final posterior probability
matrix
P
XY
is calculated as the root mean square of them:
i
j
Þ
;
s
p
1
2
2
ð
x
i
y
j
Þ
þ
p
2
ð
x
i
y
j
Þ
p
ð
x
i
y
j
Þ¼
(4)
2
where
P
1
and
P
2
denote a posterior probability
element in two kinds of posterior probability matrices (
P
XY
and
P
XY
), respectively.
ð
x
i
y
j
Þ
ð
x
i
y
j
Þ
After the posterior probability matrix
P
XY
is built by dynamic
programming in the previous stage, an optimal sub-alignment
score matrix AS is calculated based on
P
XY
in terms of the Eq.
5
below. The optimal global alignment score Opt(
X
,
Y
) of the global
alignment is computed according to matrix AS. The optimal sub-
alignment score AS(
i
,
j
) represents the score of the optimal sub-
alignment ending at residues
i
and
j
in
X
and
Y
. The AS matrix is
recursively calculated as:
3.2 Calculation of
Pairwise Distance
Matrices from Both
Pairwise Posterior
Probabilities and
Pairwise Contact
Map Scores
<
:
AS
ð
i
1
j
1
Þþ
P
XY
ð
x
i
y
j
Þ
;
AS
ð
i
j
Þ¼
max
AS
ð
i
1
j
Þ
(5)
;
;
AS
ð
i
j
1
Þ
;
AS
is the optimal score of the full global alignment
between
X
and
Y
, which is denoted as Optscore
ð
n
1
n
2
Þ
;
ð
X
Y
Þ
.
Consequently, an optimal pairwise alignment of
X
and
Y
is
generated by tracing back through the matrix AS. We also intro-
duce a contact map score, CMscore
;
, for the optimal pairwise
alignment of
X
and
Y
, since it is believed that the spatially neigh-
boring residues of two aligned residues have higher possibility to
be aligned together. CMscore
ð
X
Y
Þ
;
is calculated from the
contact map correlation score matrix CMap
XY
based on the resi-
due-residue contact map matrices CMap
X
and CMap
Y
of
X
and
Y
.
ð
X
Y
Þ
;
