Steiner minimal tree algorithm uses a greedy search strategy to merge the smaller trees into larger ones until only one tree connecting all input seeds is built [23]. We applied GenRev [24], a network-based software package to search the optimal intermediate nodes (genes) for the connection of input seed genes via the Steiner minimal tree algorithm, to extract a subnetwork from the human PPI network by using the 220 NAGenes as seeds. To test the non-randomness of this subnetwork, we first generated 1000 random networks with the same number of nodes and edges as the nicotine addiction-specific network using Erdos-Renyi model in R igraph package [25]. Then, we calculated the average values of the shortest-path distance and clustering coefficient. By counting the number of random networks with average shortest-path distance (nL) smaller than that of the nicotine addiction-specific network and the number of random networks with average clustering coefficient (nC) higher than the observed clustering coefficient, we were able to estimate the significance of non-randomness. Finally, we calculated the empirical p-value = nL/1000 and nC/1000, respectively.
