Abstract
Recent advances in systems biology have provided us with massive amounts of pathway data that describe the interplay of genes and their products. The resulting biological networks can be modeled as graphs. By means of “omics” technologies, such as microarrays, the activity of genes and proteins can be measured. Here, data from microarray experiments is integrated with the network data to gain deeper insights into gene expression. We introduce KeyPathwayMiner, a method that enables the extraction and visualization of interesting subpathways given the results of a series of gene expression studies. We aim to detect highly connected subnetworks in which most genes or proteins show similar patterns of expression. Specifically, given network and gene expression data, KeyPathwayMiner identifies those maximal subgraphs where all but k nodes of the subnetwork are expressed similarly in all but l cases in the gene expression data. Since identifying these subgraphs is computationally intensive, we developed a heuristic algorithm based on Ant Colony Optimization. We implemented KeyPathwayMiner as a plug-in for Cytoscape. Our computational model is related to a strategy presented by Ulitsky et al. in 2008. Consequently, we used the same data sets for evaluation. KeyPathwayMiner is available online at http://keypathwayminer.mpi-inf.mpg.de .
Acknowledgments
HK and JB are grateful for financial support from the Cluster of Excellence for Multimodal Computing and Interaction (MMCI), Germany. NA would also like to acknowledge the Max Planck Institute for Informatics (MPII) and the International Max Planck Research School (IMPRS) for their financial support. JW and AW would like to acknowledge funding from the Biotechnology and Biological Sciences Research Council (BBSRC) Systems Approaches to Biological Research (SABR) initiative (Grant number BB/F006039/1). Furthermore, we wish to thank Igor Ulitsky (Whitehead Institute) for providing us with the data sets used in this study.
*Nicholas Alcaraz and Hande Kücük both contributed to this paper equally.