Identifying molecular complexes in biological networks through context sensitive network querying

The complicated interactions among numerous cellular constituents play important roles in carrying out essential functions in cells. Recent studies have shown that protein complexes and signaling pathways, conducting similar cellular functions, are often conserved across networks of different species, as a result of which, homologous cellular constituents and interactions are found across species. Network querying aims to detect such conserved network regions in a target biological network that are homologous to a known biomolecular complex that is used as a query. Identifying conserved complexes through network querying provides an effective and cost-efficient way of annotating novel biological networks as it can allow one to computationally predict putative biomolecular complexes in a large scale. In this work, we propose an efficient network querying algorithm based on a context-sensitive random walk model and an efficient seed and extension approach. We first select the seed region in the target network by based on node correspondence scores between the query and target nodes using a context-sensitive random walk model. The seed network is extended by incorporating the node that maximally minimizes the conductance of the network. Network extension continues until the conductance of the network cannot be further reduced or a prespecified size limit is reached. Finally, nodes that do not interact with any other nodes in the network are removed to get the final querying result. Through extensive querying simulations using more than 900 biological complexes, we demonstrate that the proposed method can more accurately identify conserved biological complexes than the current state-of-the-art algorithms.