|
- Introduction:
NetWalker is based on the random walk analysis described in Zhang et al (see the citation below). It is similar to GeneWanderer (Kohler et al., Am J Hum Genet, 2008). However, a statistical analysis is implemented to evaluate the random walk results.
The random walk technique exploits the global structure of a network (graph) by simulating the behavior of a random walker on a graph.
From a starting node, the walker selects a neighbor of it at random and moves to the neighboring node.
Then the walker selects a neighbor of this node at random and moves to it, so on and so forth.
The sequence of nodes selected this way is a random walk on the graph.
In a variant of the random walk implemented in NetWalker, the walker may also choose to teleport to the start node with a certain probability, called restart probability.
The restart probability enforces a restriction on how far the random walker can get away from the start node.
In the current version of NetWalker, the walker can start from an input list of nodes provided by a user with equal probability.
The final score of a node in the network is defined as the steady-state probability that the random walker would stay at the node.
To assess the statistical significance of the scores, we let the random walker start from the same number of randomly selected nodes to calculate random scores for each node.
This process is repeated to generate multiple (e.g. 1000) sets of random scores.
Then, for each node, a local p value is estimated by comparing the real score to random scores from the same node, and a global p value is estimated by comparing the real score to random scores from all nodes.
A significant global p value indicates the overall significance of the node with regard to the input nodes, while a significant local p value ensures that the significance is not simply due to network topology.
The software was developed in C++ on GNU/Linux operating system with support for multithreading. It is free for noncommercial use.
- Source code:
netwalker-1.0.tar.gz
- Citation:
Bing Zhang, Zhiao Shi, Dexter T Duncan, Naresh Prodduturi, Lawrence J Marnett, Daniel C Liebler. Relating protein adduction to gene expression changes: a systems approach. Molecular Biosystems. 7(7):2118-27, 2011
- Contact:
Zhiao Shi (zhiao.shiATbcm.edu)
Bing Zhang (bing.zhangATbcm.edu)
|
