PROPER: global protein interaction network alignment through percolation matching

Ehsan Kazemi, Seyed Hamed Hassani, Matthias Grossglauser, Hassan Pezeshgi Modarres

Introduction

Biological systems are fundamentally organized as protein-protein interaction (PPI) networks, where nodes represent proteins and edges signify physical interactions. Aligning these networks across different species—such as human and mouse—is a critical task in bioinformatics. Successful alignment enables the transfer of biological knowledge, the identification of conserved pathways, and the prediction of protein functions in less-studied organisms.

However, network alignment is a notoriously difficult graph matching problem. PPI data is inherently "noisy," often containing false positives and missing real interactions. Furthermore, as networks scale to include tens of thousands of proteins, existing algorithms struggle to maintain a balance between biological similarity (amino acid sequences) and structural similarity (topological connectivity).

The PROPER Methodology

To address these challenges, researchers have developed PROPER (PROtein-protein interaction network alignment based on PERcolation). This algorithm utilizes a two-step strategy designed to decouple sequence data from noisy network topology.

1. Seed Generation

The process begins by identifying a small set of high-confidence "seed" pairs. These are proteins from different species that exhibit very high sequence similarity, typically calculated via BLAST bit-scores. By treating these high-confidence matches as a reliable foundation, PROPER avoids the mathematical pitfalls of trying to optimize sequence and structure simultaneously from the outset.

2. MapPercolation

The core innovation of the algorithm is the MapPercolation process. Starting from the initial seeds, the algorithm iteratively "percolates" through the network to expand the alignment.

Conceptual overview of the MapPercolation process between two networks $G_1$ and $G_2$, illustrating how matches are propagated through local topology.

During this phase, PROPER identifies unmatched pairs that share the highest number of common neighbors already present in the alignment. In cases where multiple pairs share the same score, a tie-breaking rule favors structural consistency by choosing the pair with the most similar "degree" (number of connections). This decoupling allows the algorithm to find functional matches even when sequence similarity is low, provided the structural roles are conserved.

Experimental Evaluation

PROPER was evaluated using a combination of real-world and synthetic datasets:

  • Real PPI Networks: Data for five major species (C. elegans, D. melanogaster, H. sapiens, M. musculus, and S. cerevisiae) sourced from the IntAct and Isobase databases.
  • Biological Benchmarks: The KEGG PATHWAY database was used to assess the recovery of known biological pathways, while Gene Ontology (GO) terms measured functional similarity.
  • Synthetic Networks: Noisy versions of the yeast PPI network were utilized to test robustness against data errors.

Results and Discussion

Performance and Accuracy

PROPER demonstrates a massive speedup over existing tools. In a 10-way pairwise alignment test, PROPER completed the task in just 317 seconds. In contrast, competing tools like L-GRAAL required 4 hours, and PINALOG took over 2 days. Beyond speed, PROPER consistently achieved higher Gene Ontology Consistency (GOC) and Induced Conserved Structure (ICS) scores compared to state-of-the-art methods like MAGNA++ and IsoRank.

Performance comparison of PROPER against state-of-the-art alignment algorithms, showing its competitive edge in structural and biological metrics.

Pathway Recovery

The algorithm proved significantly better at detecting conserved biological pathways. For instance, it successfully identified a connected subgraph of the "Cancer" pathway between humans and mice consisting of 37 nodes and 42 edges—a larger and more coherent result than any other tested algorithm.

Conclusion

PROPER represents a significant advancement in global network alignment by demonstrating that sequence data is an excellent "starter," while network structure serves as a superior "expander." By separating these two components, the algorithm achieves unprecedented speed and accuracy.

Future work may involve refining the model to account for evolutionary complexities such as gene duplication events and specific network motifs. Additionally, while PROPER is a global aligner, future iterations could be tuned to detect smaller, high-density protein complexes with even greater precision.

Summary updated

Abstract

Background The alignment of protein-protein interaction (PPI) networks enables us to uncover the relationships between different species, which leads to a deeper understanding of biological systems. Network alignment can be used to transfer biological knowledge between species. Although different PPI-network alignment algorithms were introduced during the last decade, developing an accurate and scalable algorithm that can find alignments with high biological and structural similarities among PPI networks is still challenging. Results In this paper, we introduce a new global network alignment algorithm for PPI networks called PROPER. Compared to other global network alignment methods, our algorithm shows higher accuracy and speed over real PPI datasets and synthetic networks. We show that the PROPER algorithm can detect large portions of conserved biological pathways between species. Also, using a simple parsimonious evolutionary model, we explain why PROPER performs well based on several different comparison criteria. Conclusions We highlight that PROPER has high potential in further applications such as detecting biological pathways, finding protein complexes and PPI prediction. The PROPER algorithm is available at http://proper.epfl.ch .
BibTeX
@article{kazemi2016proper,
  author = {Ehsan Kazemi and Seyed Hamed Hassani and Matthias Grossglauser and Hassan Pezeshgi Modarres},
  title = {{PROPER: global protein interaction network alignment through percolation matching}},
  journal = {BMC Bioinformatics},
  year = {2016},
  doi = {10.1186/s12859-016-1395-9},
}
Figure