%0 Journal Article
%T Global Alignment of Pairwise Protein Interaction Networks for Maximal Common Conserved Patterns
%A Wenhong Tian
%A Nagiza F. Samatova
%J International Journal of Genomics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/670623
%X A number of tools for the alignment of protein-protein interaction (PPI) networks have laid the foundation for PPI network analysis. Most of alignment tools focus on finding conserved interaction regions across the PPI networks through either local or global mapping of similar sequences. Researchers are still trying to improve the speed, scalability, and accuracy of network alignment. In view of this, we introduce a connected-components based fast algorithm, HopeMap, for network alignment. Observing that the size of true orthologs across species is small comparing to the total number of proteins in all species, we take a different approach based on a precompiled list of homologs identified by KO terms. Applying this approach to S. cerevisiae (yeast) and D. melanogaster (fly), E. coli K12 and S. typhimurium, E. coli K12 and C. crescenttus, we analyze all clusters identified in the alignment. The results are evaluated through up-to-date known gene annotations, gene ontology (GO), and KEGG ortholog groups (KO). Comparing to existing tools, our approach is fast with linear computational cost, highly accurate in terms of KO and GO terms specificity and sensitivity, and can be extended to multiple alignments easily. 1. Introduction Protein-protein interactions (PPI) are of central importance for virtually every process in a living cell. For example, information about these interactions improves our understanding of diseases and can provide the basis for new therapeutic approaches [1]. One of fundamental goals of system biology is to understand how proteins in the cell interact with each other. However, finding all protein interactions is costly and labor intensive. For example, to find all pairwise interactions for a species with 5000 proteins, one needs to do 12497500 pairwise tests. This is one reason that current known direct interactions are incomplete. High-throughput experimental techniques (e.g., yeast two-hybrid and coimmunoprecipitation test) can be helpful in this case. Integrated probability models are also used to predict the protein-protein interactions [1, 2]. Quite a few databases, DIP [3], IntAct [4], BioGRID [5], HPRD [6], and IntPro [7], are public available for collecting and storing PPI network data. Researchers [1, 8¨C14] are trying to identify conserved patterns such as ortholog groups and functional similar pathways/complexes across species using PPI network data. Figure 1 provides an example of global visualization of protein interaction networks. Figure 1: global visualization of protein interaction networks (from [ 15]). The exact
%U http://www.hindawi.com/journals/ijg/2013/670623/