Information Technology Reference
In-Depth Information
It is easy to prove that P3 is upper bounded by P4. Now we will solve P4 and use
its solution to approximate P3 and thus, P1.
Since both z and y are binary variables, the last term in Eq. (
2.11
) can be
expanded as follows.
2
2
X
i
;
j
;
u
¼
2
X
z
i
;
j
y
i
;
j
i
;
j
;
u
ð
z
i
;
j
þ
y
i
;
j
2z
i
;
j
y
i
;
j
Þ
ð
2
:
12
Þ
For a
xed
k;
we can split P4 into the following two sub-problems.
argmax
X
k
y
¼
y
k
;
l
C
k
;
l
ð
SP1
Þ
ð
2
:
13
Þ
;
l
;
v
L
P
i
;
j
;
u
h
uv
v
k
;
l
2
where C
k
;
l
¼
1
i
;
j
;
k
;
l
z
i
;
j
k
2z
k
;
l
1
argmax
X
i
;
j
;
u
z
¼
z
i
;
j
D
i
;
j
ð
SP2
Þ
ð
2
:
14
Þ
i
;
j
þ
P
k
;
l
;
v L
h
i
;
j
2
ð
where D
i
;
j
¼ h
u
uv
i
;
j
;
k
;
l
y
v
u
y
u
i
;
j
Þ
The sub-problem SP1 optimizes the objective function with respect to y while
k
;
l
þ k
1
fixing z, and the sub-problem SP2 optimizes the objective function with respect to z
while
fixing y. SP1 and SP2 do not contain any quadratic term, so they can be
ef
ciently solved using the classical dynamic programming algorithm for sequence
or HMM-HMM alignment.
In summary, we solve P4 using the following procedure
Step 1 Initialize z by aligning the two MRFs without the edge alignment potential,
which can be done by dynamic programming. Accordingly, initialize L as
the length of the initial alignment.
Step 2 Solve (SP1)
first and then (SP2) using dynamic programming, each
generating a feasible alignment.
Step 3 If the algorithm converges, i.e., the difference between z and y is very small
or zero, stop here. Otherwise, we update the alignment length L as the
length of the alignment just generated and the Lagrange multiplier
k
using
subgradient descent as in Eq. (
2.15
), and then go back to Step 2.
n
þ
1
n
z
y
k
¼ k
q
ð
Þ
ð
2
:
15
Þ
Due to the quadratic penalty term in Eq. (
2.10
), this ADMM algorithm usually
converges much faster and also yields better solutions than without this term.
Empiric ally, it converges within 10 iterations for most protein pairs. See [
11
] for
the convergence proof of a general ADMM algorithm.
Search WWH ::
Custom Search