Global Alignment of Pairwise Protein Interaction Networks for Maximal Common Conserved Patterns

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.

• Publication year

  2013

• Venue

  International Journal of Genomics

• Publication date

  2013-03-27

• Fields of study

  Biology, Medicine, Computer Science

• Identifiers
  DOI 10.1155/2013/670623PMID 23710435PMCID 3654364
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Supplementary Table 1

  2015cited by this paper
• Intact

  2011cited by this paper
• Automatic Parameter Learning for Multiple Local Network Alignment

  2009cited by this paper
• Aligning Biomolecular Networks Using Modular Graph Kernels

  2009influential reference
• From pull-down data to protein interaction networks and complexes with biological relevance

  2008cited by this paper
• Global alignment of multiple protein interaction networks with application to functional orthology detection

  2008cited by this paper
• Fast and Accurate Alignment of Multiple Protein Networks

  2008influential reference
• Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology

  2007influential reference
• Global Alignment of Multiple Protein Interaction Networks

  2007cited by this paper
• Graemlin: general and robust alignment of multiple large interaction networks.

  2006influential reference
• Modeling cellular machinery through biological network comparison

  2006cited by this paper
• Systematic identification of functional orthologs based on protein network comparison.

  2006cited by this paper
• MIPS: analysis and annotation of proteins from whole genomes in 2005

  2006cited by this paper
• In silico discovery of enzyme-substrate specificity-determining residue clusters.

  2005cited by this paper
• MIPS: analysis and annotation of proteins from whole genomes in 2005

  2005cited by this paper
• From the Cover : Conserved patterns of protein interaction in multiple species

  2005influential reference
• Munich Information Center for Protein Sequences Plant Genome Resources. A Framework for Integrative and Comparative Analyses1[w]

  2005cited by this paper
• Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution

  2005cited by this paper
• Human Protein Reference Database

  2004cited by this paper
• The FunCat, a functional annotation scheme for systematic classification of proteins from whole genomes.

  2004cited by this paper
• Conserved pathways within bacteria and yeast as revealed by global protein network alignment

  2003cited by this paper
• Specificity and Stability in Topology of Protein Networks

  2002cited by this paper
• A note on the calculation of empirical P values from Monte Carlo procedures.

  2002cited by this paper
• Automatic clustering of orthologs and in-paralogs from pairwise species comparisons.

  2001influential reference
• The yeast protein interaction network evolves rapidly and contains few redundant duplicate genes.

  2001cited by this paper
• Gene Ontology: tool for the unification of biology

  2000cited by this paper
• KEGG: Kyoto Encyclopedia of Genes and Genomes

  2000cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Pacific Symposium on Biocomputing 14:99-110 (2009) Pacific Symposium on Biocomputing 14: (2009) PAIRWISE ALIGNMENT OF INTERACTION NETWORKS BY FAST IDENTIFICATION OF MAXIMAL CONSERVED PATTERNS *

  year unknowncited by this paper

• A Survey of Graph Comparison Methods with Applications to Nondeterminism in High-Performance Computing

  2023cites this paper
• Multi-SANA: Comparing Measures of Topological Similarity for Multiple Network Alignment

  2022cites this paper
• A comparison of algorithms for the pairwise alignment of biological networks

  2014cites this paper
• Pin-Align: A New Dynamic Programming Approach to Align Protein-Protein Interaction Networks

  2014cites this paper
• Multiobjective Optimization for the Alignment of Protein Networks

  2014cites this paper
• On Pattern Preserving Graph Generation

  2013cites this paper