
Research
Abstracts  2007 
Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood TopologyRohit Singh, Jinbo Xu & Bonnie BergerIntroductionA 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 proteinprotein 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 sequencebased 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 functionoriented perspective that complements traditional sequencebased methods. It also facilitates annotation transfer from wellstudied 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 NPcomplete. 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: IsoRankThe algorithm is intuitive: a node i in graph G_{1} is mapped to a node j in G_{2} 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_{1} and j is from network G_{2}. Given network and sequence data, we construct an eigenvalue problem and solve it to compute R (the vector of all R_{ij}s). The second stage constructs the mapping for the alignment by extracting from R highscoring, pairwise, mutuallyconsistent 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 

