Research Abstracts - 2007

Introduction

A fundamental goal of biology is to understand the cell as a system of interacting components and, in particular, how proteins in the cell interact with each other. A powerful way of analyzing these interactions is the protein-protein interaction (PPI) network: a network where each node corresponds to a protein and an edge indicates a direct physical interaction between the proteins. As more PPI data becomes available, comparative analysis of PPI networks (across species) is proving to be a valuable tool. Such analysis is similar in spirit to traditional sequence-based comparative genomic analyses; it also promises commensurate insights. Such an analysis can identify conserved functional components across species. As a phylogenetic tool, it offers a function-oriented perspective that complements traditional sequence-based methods. It also facilitates annotation transfer from well-studied species to others.

In this work, we focus on the global network alignment problem. The aim in global network alignment is to find the best overall alignment between the input networks. This problem is, provably, at least as hard as the Maximum Common Subgraph which itself is known to be NP-complete. We propose IsoRank, an algorithm for pairwise global network alignment of PPI networks which can compute an approximate solution efficiently; to the best of our knowledge, it is the first such algorithm of its kind. It simultaneously uses both PPI network data and sequence similarity data to compute the alignment, the relative weights of the two data sources being a free parameter.

Methods: IsoRank

The algorithm is intuitive: a node i in graph G₁ is mapped to a node j in G₂ if the neighborhood topologies of i and j are similar, i.e., the neighbors of i can be well mapped to the neighbors of j [1]. This approach has parallels to Google's PageRank technique. The algorithm works in two stages. It first associates a score with each possible match between nodes of the two networks. These scores are computed by constructing an eigenvalue problem which depends only the structure of the two graphs. Let R_ij be the score for the protein pair (i,j) where i is from network G₁ and j is from network G₂. Given network and sequence data, we construct an eigenvalue problem and solve it to compute R (the vector of all R_ijs). The second stage constructs the mapping for the alignment by extracting from R high-scoring, pairwise, mutually-consistent matches.

References

[1] Rohit Singh, Jinbo Xu and Bonnie Berger. Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology. In The Proceedings of the 11th International Conference on Research in Computational Molecular Biology (RECOMB) 2007