Biology Reference
In-Depth Information
Fig. 3 Feedforward multilayer network with directed edges
The single-source optimal path problem [
3
] is a well-known
computer science problem that is addressed by dynamic program-
ming. Finding the optimal path in a directed multilayered network
has a direct correspondence with the sequence alignment problem
as we will see. Let's assume a multilayered network with a source
node, a sink node and
n
middle layers (Fig.
3
). Each middle layer
'
k
has a finite positive number of nodes
f
l
k;
1
;
l
k;
2
; ...;
l
k;j'
k
j
g
. Directed
edges exist from the previous layers
'
k
, and the vertices
in a layer are not connected. Each edge has a corresponding score,
and the optimal path problem is to find the highest scoring path
from the source to the sink where the score of a path is the sum of
the edges in that path. This problem can be divided into subpro-
blems and solved recursively as follows.
Assume that the optimal path visits node
l
k
,
i
. The set of the
paths from the source to
l
k
,
i
consists of the edges between
the layers
'
m
,
m
<
k
to
k
. On the other hand, the paths from
l
k
,
i
to
the sink consists of the edges between the layers
'
m
,
m
k
.Asa
result, the paths from the source to
l
k
,
i
and from
l
k
,
i
to the sink are
non-overlapping sets, and these two problems can be solved sepa-
rately. Thus
'
l
,
l
L
ð
source
;
sink
Þ¼
L
ð
source
;
l
k;i
Þþ
L
ð
l
k;i
;
sink
Þ;
(4)
where
L
(
x
,
y
) denotes the optimal path from node
x
to node
y
.
Based on this divisibility to subproblems property, the optimal path
to
l
k
,
i
can be defined recursively by dividing the optimal paths from
the source to the parent nodes of
l
k
,
i
(
l
k;j
) and from
l
k;j
to
l
k
,
i
:
; l
k;j
ðl
k;j
j'
L
ð
source
;
l
k;i
Þ¼
max
j
ð
L
ð
source
Þþ
L
;
l
k;i
ÞÞ;
1
j
j:
k
(5)
