Information Technology Reference
In-Depth Information
problem of
finding the best alignment between two MRFs can be formulated as the
following quadratic optimization problem.
max
z
X
L
X
i
1
u
i
j
z
i
;
j
þ
uv
i
l
z
i
;
j
z
k
;
l
ðÞ
P1
i
;
j
;
u
h
v
h
ð
2
:
8
Þ
;
;
j
;
k
;
;
j
;
k
;
l
;
u
;
uv
i
;
j
;
k
;
l
are node and edge alignment potentials as described in previous
section. Meanwhile,
u
i
;
j
and
where
h
h
uv
i
h
l
is equal to 0 if either u or v is not a match state. L is the
;
j
;
k
;
alignment length and 1
=
L is used to make the accumulative node and edge potential
have similar scale. Note that L is unknown and we will describe how to determine it
later in this section. Finally, the solution of P1 is also subject to the constraint that
all those z
i
;
j
with value 1 shall form a valid alignment path. This constraint shall be
enforced to all the optimization problems described in this section.
It is computationally intractable to
find the optimal solution of P1. Below we
present an Alternating Direction Method of Multipliers (ADMM) method that can
ef
ciently solve this problem to suboptimal. See [
11
] for a tutorial of the ADMM
method. To use ADMM, we rewrite P1 as follows by making a copy of Z to y
;
but
without changing the solution space.
max
z
;
y
i
;
j
;
u
h
L
P
u
i
uv
i
j
z
i
;
j
þ
1
l
z
i
;
j
y
k
;
l
ðÞ
P2
i
;
j
;
k
;
l
;
u
;
v
h
;
;
j
;
k
;
ð
2
:
9
Þ
z
k
;
l
¼
y
k
;
l
s
:
t
: 8
k
;
l
;
v
;
Problem P2 can be augmented by adding a term to penalize the difference between z
and y.
2
max
z
;
y
i
;
j
;
u
h
L
P
i
;
j
;
k
;
l
z
i
;
j
y
k
;
l
2
i
;
j
;
u
u
i
;
j
z
i
;
j
þ
1
uv
z
i
;
j
y
i
;
j
ðÞ
P3
i
;
j
;
k
;
l
;
u
;
v
h
ð
2
:
10
Þ
s
:
t
: 8
i
;
j
;
u
;
z
i
;
j
¼
y
i
;
j
P3 is equivalent to P2 and P1, but converges faster due to the penalty term. Here
q
is a hyper-parameter in
fl
uencing the convergence rate of the algorithm. Empirically,
setting
to a constant (=0.5) enables our algorithm to converge within 10 iterations
for most protein pairs.
Adding the constraint z
i
;
j
¼
q
y
i
;
j
using a Lagrange multiplier
k
to Eq. (
2.10
), we
have the following Lagrangian dual problem:
min
k
max
z
;
y
X
L
X
i
1
u
i
;
j
z
i
;
j
þ
uv
i
;
j
;
k
;
l
z
i
;
j
y
k
;
l
ðÞ
P4
i
;
j
;
u
h
v
h
;
j
;
k
;
l
;
u
;
2
X
i
;
j
;
u
k
2
X
i
;
j
;
u
u
i
;
j
z
i
;
j
y
i
;
j
z
i
;
j
y
i
;
j
þ
ð
2
:
11
Þ
Search WWH ::
Custom Search