Comparative Analysis of Biological Networks: Algorithmic and Analytical Methods for Cross-Species Analysis of Biomolecular Interactions

Recent developments in molecular biology have resulted in experimental data that entails the relationships and interactions between biomolecules. Biomolecular interaction data, generally referred to as biological or cellular networks, are frequently abstracted using graph models. In systems biology, comparative analysis of these networks provides understanding of functional modularity in the cell by integrating cellular organization, functional hierarchy, and evolutionary conservation. In this study, we address a number of algorithmic issues associated with comparative analysis of molecular interaction networks. We first discuss the problem of identifying common sub-networks in a collection of molecular interaction networks belonging to diverse species. With a view to understanding the conservation and divergence of functional modules, we also develop network alignment techniques, grounded in theoretical models of network evolution. Finally, we probabilistically analyze the existence of highly connected and conserved subgraphs in random graphs, in order to assess the statistical significance of the patterns identified by our algorithms.