Detection of Changes in Transitive Associations by Shortest-path Analysis of Protein Interaction Networks Integrated with Gene Expression Profiles

Shortest-path (SP) clustering can detect transitive associations in co-expression networks. In this work, we show that it can detect changes of transitive associations caused by perturbations in a protein interaction network (PIN). Specifically, we compare SPs between genes under perturbation and in a reference state. The PIN under perturbation can be obtained through integration with gene expression profiles, using either marginal or partial correlations. The default reference state of network is the unweighted PIN. The changes in transitive associations caused by perturbation can be detected and ranked by comparing the SP traversal patterns between the weighted and unweighted networks. We have applied this approach to a gene expression time series data set generated by a glucose pulse perturbation in Saccharomyces cerevisiae. Using a list of genes involved in the fermentation, TCA, and glyoxylate pathways, we demonstrate that transitive associations with significant ranks are consistent with known responses to glucose perturbations. This network based analysis does not require a cutoff value for correlation coefficient and provides an alternative approach to clustering analysis of gene expression data. In comparison to other network analysis approaches, this approach is unique in its ability to detect perturbation changes through a reference network state. Key software is implemented in an open-source package, available at http://bioinformatics.org/bna/.