Fast network querying algorithm for searching large-scale biological networks

Network querying aims to search a large network for subnetwork regions that are similar to a given query network. In this paper, we propose a novel algorithm for querying large scale protein interaction networks. In this algorithm, we iteratively compute the correspondence scores between nodes in the query and the target networks using semi-Markov random walk. Based on these scores, we reduce the search space in the target network by discarding irrelevant nodes. The scores are re-estimated in each iteration after removing such nodes, which ultimately leads to more accurate querying result. Numerical experiments based on both synthetic and real networks show that the algorithm can efficiently find accurate querying results.