We study conservation of pathways in the context of comparative analysis of protein interaction networks. We specifically present a method based on a graph-matching algorithm to detect conserved pathways between two protein networks. Our algorithm is provably efficient unlike the search heuristics used in previous methods, and is novel in the broader field of graph-matching as well. We apply the method to compare the yeast network with the human, fruit fly and nematode worm networks, evaluate the detected conserved pathways using known yeast protein complexes, and demonstrate applications to function prediction.

We study evolution of pathways in the context of phylogenetic analysis of bacterial and archaeal pathways. We specifically present a tractable probabilistic model for pathway evolution that makes the assumptions about pathway evolution explicit, in contrast to the few past studies that use discrete pathway similarity based models. We then apply the model to estimate the phylogeny along which a pathway such as citric acid cycle or chemotaxis evolved from its unknown ancestral forms to extant forms. We interpret the estimated phylogenies of such pathways involved in essential metabolisms or stress responses using known species phylogenies and published cellular phenotypes.