title: Pairwise alignment of protein interaction networks.
abstract: With an ever-increasing amount of available data on protein-protein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Although available data on protein-protein interactions is currently limited, recently developed algorithms have been shown to convey novel biological insights through employment of elegant mathematical models. The main challenge in aligning PPI networks is to define a graph theoretical measure of similarity between graph structures that captures underlying biological phenomena accurately. In this respect, modeling of conservation and divergence of interactions, as well as the interpretation of resulting alignments, are important design parameters. In this paper, we develop a framework for comprehensive alignment of PPI networks, which is inspired by duplication/divergence models that focus on understanding the evolution of protein interactions. We propose a mathematical model that extends the concepts of match, mismatch, and gap in sequence alignment to that of match, mismatch, and duplication in network alignment and evaluates similarity between graph structures through a scoring function that accounts for evolutionary events. By relying on evolutionary models, the proposed framework facilitates interpretation of resulting alignments in terms of not only conservation but also divergence of modularity in PPI networks. Furthermore, as in the case of sequence alignment, our model allows flexibility in adjusting parameters to quantify underlying evolutionary relationships. Based on the proposed model, we formulate PPI network alignment as an optimization problem and present fast algorithms to solve this problem. Detailed experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively, in terms of both accuracies and computational cost.
authors.affiliation: Department of Computer Sciences, Purdue University, West Lafayette, IN 47907, USA. koyuturk@cs.purdue.edu
authors.forename: Mehmet
authors.initials: M
authors.lastname: Koyutürk
authors.forename: Yohan
authors.initials: Y
authors.lastname: Kim
authors.forename: Umut
authors.initials: U
authors.lastname: Topkara
authors.forename: Shankar
authors.initials: S
authors.lastname: Subramaniam
authors.forename: Wojciech
authors.initials: W
authors.lastname: Szpankowski
authors.forename: Ananth
authors.initials: A
authors.lastname: Grama
mesh_terms: D000465:Algorithms; D000818:Animals; D017173:Caenorhabditis elegans / Q000378:metabolism; D029742:Caenorhabditis elegans Proteins / Q000378:metabolism*; D003198:Computer Simulation; D017124:Conserved Sequence; D029721:Drosophila Proteins / Q000378:metabolism*; D004331:Drosophila melanogaster / Q000378:metabolism; D019143:Evolution, Molecular; D025941:Protein Interaction Mapping; D020543:Proteome / Q000378:metabolism*; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism*; D016415:Sequence Alignment; D015398:Signal Transduction / Q000502:physiology
chemical_list: D029742:Caenorhabditis elegans Proteins; D029721:Drosophila Proteins; D020543:Proteome; D029701:Saccharomyces cerevisiae Proteins