Heuristics for simulated annealing search of active sub-networks in bio-molecular interaction networks

Abstract

Different kinds of ‘omics’ data for several organisms and bio-molecular interaction networks (e.g. reconstructed networks of biochemical reactions and protein-protein physical interactions) are becoming very common nowadays. These bio-molecular networks are being used as a platform to integrate genome-scale ‘omics’ datasets. Identification of sub-networks in these large networks that show maximum collective response to a perturbation is one the interesting problems to solve by using an integrative analysis. Sub-networks can be hypothesized to represent significant collective biological activity due to the underlying interactions between the bio-molecules. The biological activity can be estimated in several ways- for example coordinated change in the expression level (e.g. mRNA). Identifying these regions reduce complexity of the network to be analyzed in greater detail by revealing the regions that are perturbed by a conditionremoving the interactions that are potentially false-positive and not related to the response under study. As the simulated annealing does not guarantee to find the global optimum and may lead to an incomplete picture of the biological phenomenon, we report a method to estimate the theoretical optimal score curve. The simulated annealing algorithm (SA) used in this study is a slightly modified version of the algorithm by Ideker et al.. Each node in the graph is associated with a binary variable turning the node visible or invisible and therefore inducing several sub-graphs. In the standard formulation, the initial solution is obtained by randomly attributing 0 or 1 to the nodes of the graph. Based in concepts described above, we propose an alternative initialization method to improve the performance of the simulated annealing algorithm.