Alignment of PPI Networks Using Semantic Similarity for Conserved Protein Complex Prediction

Network alignment is a computational technique to identify topological similarity of graph data by mapping link patterns. In bioinformatics, network alignment algorithms have been applied to protein-protein interaction (PPI) networks to discover evolutionarily conserved substructures at the system level. In particular, local network alignment of PPI networks searches for conserved functional components between species and predicts unknown protein complexes and signaling pathways. In this article, we present a novel approach of local network alignment by semantic mapping. While most previous methods find protein matches between species by sequence homology, our approach uses semantic similarity. Given Gene Ontology (GO) and its annotation data, we estimate functional closeness between two proteins by measuring their semantic similarity. We adopted a new semantic similarity measure, simVICD, which has the best performance for PPI validation and functional match. We tested alignment between the PPI networks of well-studied yeast protein complexes and the genome-wide PPI network of human in order to predict human protein complexes. The experimental results demonstrate that our approach has higher accuracy in protein complex prediction than graph clustering algorithms, and higher efficiency than previous network alignment algorithms.