CSAIL Publications and Digital Archive header
bullet Research Abstracts Home bullet CSAIL Digital Archive bullet Research Activities bullet CSAIL Home bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line

 

Research Abstracts - 2007
horizontal line

horizontal line

vertical line
vertical line

Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology

Rohit Singh, Jinbo Xu & Bonnie Berger

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 G1 is mapped to a node j in G2 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 Rij be the score for the protein pair (i,j) where i is from network G1 and j is from network G2. Given network and sequence data, we construct an eigenvalue problem and solve it to compute R (the vector of all Rijs). 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

 

vertical line
vertical line
 
horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu