This process is repeated until the difference between two states
is small enough to stop.
At last, each gene on the network will be assigned with a
probability of being possible disease gene.
Based on RWR algorithm, Kohler et al. [48] developed
RWOAG, and Lee et al. [55] developed HumanNet.4.2 Shortest Path
Method
Shortest path-based method has been used for identifying the
genetic determinants of longevity [56] and disease genes [57–59].
Dijkstra’s algorithm [60] is most widely used to discover the
shortest paths between reported disease genes. The genes on the
shortest path between known disease genes can only reveal the
possible mechanism of disease progression but also indicate possi-
ble novel key disease genes. The procedure of Dijkstra’s algorithm
is as follows [60–62]:
LetG¼(V,E,w) be a weighted graph, whereVis the set of
vertices,Eis the set of edges, andwis a function fromEtoR+.
Supposeu 0 andv 0 are two vertices inG, the shortest path between
them can be discovered using the following procedures:- LetS¼{u 0 },S¼Vfgu 0 ,l(u 0 )¼0, andl(v)¼1for any
vertexv∈S{u 0 }. - For each vertexv∈Ssuch thatu^0 v∈E,whereu^0 ∈S.Ifl(v)
l(u^0 )þw(u^0 v), then continue; otherwise,l(v)¼l(u^0 )þw(u^0 v)
and Parent(v)¼u^0. - Find a vertexv
0
∈Ssuch thatlv
0
¼min lvðÞjv∈S
.
4.S¼S[{v^0 } andS¼S v 0
.- Ifv 0 ∈S, then continue; otherwise, return tostep2.
- The label Parent was used to find a shortest path fromu 0 tov 0.
4.3 Kth Shortest Path
Methods
The Dijkstra’s algorithm can only identify the shortest path
between two nodes. But sometimes, the second or third shortest
path may also include curtail information for understanding dis-
ease, especially when the weights on the network are not very
accurate. Therefore, finding Kth shortest paths in the graph
Gbetween each pair of genes (K>¼1) using A* search algorithm
[63] is very useful.
Given a weighted graphG¼(V,E,w), whereVis the set of
vertices,Eis the set of edges, andwis a function fromEtoR+, the
Kth shortest path problem is to find thekshortest paths between
two nodessandtin a weighted graph. A* search algorithm works
similarly with the Dijkstra’s algorithm but adds an evaluation func-
tionbfvðÞ¼bgvðÞþbhvðÞ, wheregvbðÞis the cost of the path fromsto
vwith minimum cost so far found by A* andbhvðÞis the estimate of
the cost of an optimal path fromvtot[64], to guide the search.
The evaluation function reduces the searching time, and ifbhvðÞ
is any lower bound on the cost of an optimal path fromvtot,A*The Reconstruction and Analysis of Gene Regulatory Networks 147