can find the optimal path fromstot[64]. Therefore, ifbhvðÞis set to
be the cost of an optimal path fromvtot, which can be found in
advance by the Dijkstra’s algorithm, A* search algorithm can still
determine the optimal path fromstot.
By combining the Dijkstra’s algorithm and A* search algo-
rithm, thekshortest paths betweensandtcan be enumerated as
follows:- The shortest path fromtto other nodes in the graph is discov-
ered using the Dijkstra’s algorithm, and the cost of each path is
stored. - A* search algorithm is used to search paths froms, withbhvðÞin
the evaluation function to be the value calculated in (1) for each
nodevin the graph. But, during this step, each node can be
visited more than once. Whentis visited thej-th time, the
corresponding path is thej-th shortest path fromstot.
5 Network Reconstruction and Analysis Software
We introduced many network reconstruction and analysis methods
in previous sections. To apply these methods, the easiest way for
biological scientists is to use software that has been developed based
on various algorithms. Therefore, some representative software for
network reconstruction and analysis will be described.5.1 ARACNE ARACNE [12, 65] is the most widely used network reconstruction
software based on information theory. It is proposed by Butte and
Kohane [66] and uses mutual information to measure genes’
expression pattern similarity. It requires each sample to be indepen-
dent from the others. Therefore, it is not suitable for analyzing
time-course gene expression profiles. The steady-state gene expres-
sion profile is the ideal input data. This software is easy to use and
has graphical user interface (GUI). It has been integrated into
geWorkbench.
5.2 WGCNA WGCNA is a popular co-expression network reconstruction soft-
ware. It calculates the co-expression coefficient between genes and
uses the scale-free property as criteria to determine the cutoff of
correlation coefficient. It not only constructs the co-expression
network but also identifies the co-expressed modules which may
be corresponding to certain pathways or biological processes.
Therefore, usually, researchers do functional enrichment on each
module and try to investigate the biological functions of the genes
within the module. The module with biological significance will be
selected for further studies.
148 Guangyong Zheng and Tao Huang