Graph mining and module detection in protein-protein interaction networks

Graphs are intuitive representations of relational data. Graphs have been widely used to represent biological molecular networks that operate in the living systems. In the study of systems biology, using graph mining techniques and graph-theory-based algorithms to analyze molecular interaction networks has been a widely adopted approach. In this research we perform comparative analysis of cancer-related protein-protein interaction networks using graph mining and graph-theory-based algorithms. Graph analysis is inherently complicated due to the multi-dimensionality of the data to be analyzed. How to reduce data complexity and effectively manage the search space have been the topics of interest in devising graph analysis algorithms. We designed canonical labeling to represent graph patterns for quick comparison of graph isomorphism. We developed methods and algorithms for identifying frequent common patterns and distinct patterns in cancer PPI networks, and validated them using biological reference databases and literature-based approaches. The methods we developed in this research are generic and can be applied in graph analysis of other domains for the discovery of important substructures.