Source-linked AI summary
Global alignment of protein-protein interaction networks by graph matching methods
Mikhail Zaslavskiy, Francis Bach, Jean-Philippe Vert
TL;DR
PPI network alignment asks how to match proteins across species while conserving interactions, a difficult combinatorial problem relevant to functional-ortholog identification. The paper formulates this task as graph matching, distinguishes constrained and balanced objectives, and evaluates new methods on yeast and fly networks. The new methods outperform existing approaches, including a 78% gain in conserved interactions over IsoRank at a given sequence-similarity level.
Problem
PPI alignment must match proteins across species while conserving interactions, but it is a difficult combinatorial problem and functional-ortholog ground truth is limited.
Method
The paper formulates global PPI alignment as graph matching and studies constrained and balanced formulations using new exact or approximate methods.
Results
78% more conserved interactions than IsoRank were obtained at the same average sequence-similarity level in the balanced-alignment comparison.
Takeaways & Limitations
The proposed methods produce better alignments under the paper’s conserved-interaction criterion than the compared state-of-the-art methods.
Takeaways & Limitations
Objective evidence that conserving more interactions improves functional-ortholog detection remains limited because large-scale curated ground truth is lacking.
Abstract
from arXiv · showhide
Aligning protein-protein interaction (PPI) networks of different species has drawn a considerable interest recently. This problem is important to investigate evolutionary conserved pathways or protein complexes across species, and to help in the identification of functional orthologs through the detection of conserved interactions. It is however a difficult combinatorial problem, for which only heuristic methods have been proposed so far. We reformulate the PPI alignment as a graph matching problem, and investigate how state-of-the-art graph matching algorithms can be used for that purpose. We differentiate between two alignment problems, depending on whether strict constraints on protein matches are given, based on sequence similarity, or whether the goal is instead to find an optimal compromise between sequence similarity and interaction conservation in the alignment. We propose new methods for both cases, and assess their performance on the alignment of the yeast and fly PPI networks. The new methods consistently outperform state-of-the-art algorithms, retrieving in particular 78% more conserved interactions than IsoRank for a given level of sequence similarity. Availability:http://cbio.ensmp.fr/proj/graphm\_ppi/, additional data and codes are available upon request. Contact: jean-philippe.vert@mines-paristech.fr
I. INTRODUCTION
PPI network alignment compares species by matching proteins while conserving interactions, supporting functional-ortholog identification. The paper formulates global alignment as graph matching and develops methods for constrained settings.
- PPI networks can reveal conserved biological organization across species and help identify functional orthologs through conserved interactions.
- Network alignment matches homologous proteins while seeking conservation between their interactions.
- Local methods find multiple conserved subgraphs, whereas global alignment seeks one consistent matching across all nodes.
- Global network alignment is computationally harder than local alignment because it searches among all possible global matchings.
- The paper formulates global alignment as graph matching and investigates exact and approximate methods under constrained protein associations.
II. CONSTRAINED AND BALANCED GNA PROBLEMS
The paper formalizes global network alignment as matching vertices between two PPI graphs while balancing sequence similarity and interaction conservation. It distinguishes constrained matching from a continuous balanced objective.
- PPI networks are represented as undirected graphs whose vertices are proteins and whose edges are protein interactions.
- Global network alignment seeks a correspondence between proteins that matches similar pairs and conserves interactions between matched pairs.
- A complete alignment is represented by a permutation, with dummy nodes allowing unequal network sizes or unmatched proteins.
- The conserved-interaction score J(P) counts interacting pairs in one network whose matched proteins also interact in the other.
- Constrained GNA restricts candidate matches using sequence-derived sets, such as Inparanoid clusters.
- Balanced GNA optimizes a global trade-off between sequence similarity and interaction conservation, controlled by λ.
III. METHODS
The methods section solves both constrained and balanced global network-alignment problems, using algorithms developed for the more general balanced formulation.
- Algorithms for balanced GNA can also solve constrained GNA, so the paper begins with methods for the balanced problem.
- The constrained and balanced formulations are treated within a common graph-matching framework.
- The method organization reflects the balanced problem’s greater generality relative to constrained matching.
A. Algorithms for the balanced GNA problem
The paper applies graph-matching methods to balanced PPI alignment, comparing PATH and a new gradient-ascent method with IsoRank. These methods optimize a difficult combinatorial objective through relaxations or spectral recursion.
- Balanced GNA is a difficult general graph-matching problem, so scalable approximate methods are needed for large, non-sparse graphs.
- The paper applies PATH and proposes a simpler gradient-ascent method for balanced PPI alignment, using IsoRank as a benchmark.
- PATH follows solutions between convex and concave relaxations over doubly stochastic matrices until reaching a permutation matrix.
- The GA method iteratively selects a permutation in the objective-gradient direction and can exploit a good constrained-alignment initialization.
- IsoRank recursively scores protein pairs according to the similarity of their network neighborhoods, estimating functional-ortholog likelihood.
- The balanced objective incorporates sequence-similarity information through a λ-controlled modification of the graph-matching formulation.
B. Algorithms for the constrained GNA problem
The constrained GNA problem restricts protein matches to predefined groups and can use interaction information to resolve ambiguous assignments. A message-passing method enables exact optimization when the resulting cluster graph has suitable structure, such as being loop-free.
- MRF method: MRF models assign binary orthology variables to candidate protein pairs and use neighboring assignments to maximize conserved interactions.Variables are connected when interaction evidence appears in one species and corresponding connectivity exists in the other.
- MP method for exact optimization: The MP method restricts matches to proteins within shared groups, such as Inparanoid clusters, and decomposes global matching into local cluster matchings.Dummy nodes equalize the number of proteins from each species within each cluster.
- MP method for exact optimization: The conserved-interaction objective decomposes into within-cluster terms J1(Pi) and between-cluster terms J2(Pi, Pj) over connected cluster pairs.This decomposition exposes dependencies among local permutations through the cluster graph.
- MP method for exact optimization: Message passing can optimize the decomposed objective efficiently when the cluster graph has suitable structure, including isolated nodes or no loops.For a tree, connected components can be optimized independently using a Viterbi-like forward and backward procedure.
- MP method for exact optimization: At the root, the forward pass returns the maximum value of J(P), and the backward pass recovers the local permutations achieving that optimum.The approach can also apply to graphs with small tree-width after grouping clusters.
IV. DATA
The experiments align yeast and fly PPI networks using data from prior work. Most clusters contain one protein from each species, while hundreds are ambiguous because they contain multiple proteins from at least one species.
- Dataset: The yeast–fly benchmark uses supplementary data from prior work and includes PPI networks from S. cerevisiae and D. melanogaster.The yeast network contains 4,389 proteins and 14,319 pairwise interactions.
- Clusters: 1,552 clusters contain exactly two proteins, one from fly and one from yeast, whereas 692 clusters contain multiple proteins from at least one species.The latter clusters are ambiguous because they do not determine a single fly–yeast functional-ortholog pairing.
V. RESULTS
The study evaluates whether graph-matching methods conserve interactions and whether that conservation improves functional-ortholog recovery. It uses three experiment sets covering constrained and balanced GNA formulations, while noting that ortholog-recovery evaluation lacks large-scale curated ground truth.
- Evaluation questions: The evaluation asks whether methods find alignments with many conserved interactions and whether conserved interactions help retrieve more functional orthologs.Interaction counts provide an unambiguous answer to the first question, whereas the second is harder to assess.
- Evaluation limitations: Large-scale curated ground truth is lacking, limiting direct assessment of whether conserving more interactions retrieves more functional orthologs.The conserved-interaction count itself can still be compared without ambiguity across methods and settings.
- Experimental design: Three experiment sets compare methods across constrained and balanced GNA formulations.They cover Inparanoid-constrained disambiguation, a noisier constrained setting with second-order interactions, and unconstrained alignment balancing protein similarity with interaction conservation.
- Experimental design: The Inparanoid benchmark permits exact MP optimization, whereas adding second-order interactions makes exact minimization intractable and requires approximate constrained-GNA methods.The third set discards Inparanoid clusters and directly searches a balanced global alignment.
A. Disambiguation of functional orthologs within Inparanoid clusters
The experiment uses PPI information to disambiguate functional orthologs within Inparanoid clusters, comparing graph-matching methods on conserved interactions and HomoloGene recovery. MP achieves the benchmark optimum, while sequence-based validation reveals an important evaluation caveat.
- The experiment restricts candidate orthologs to proteins within the same Inparanoid cluster and selects associations maximizing conserved interactions.
- 238 conserved interactions is the benchmark maximum, reached by MP, GA, and PATH but not MRF or IsoRank.
- MRF recovers 233 conserved interactions and IsoRank 228, corresponding to 2% and 4% fewer interactions than MP, GA, and PATH, respectively.
- MP can alter assignments to trade one conserved interaction for two gains, or two losses for three gains, relative to MRF.
- 41 HomoloGene pairs are recovered by MP, GA, and PATH, compared with 36 by MRF and 39 by IsoRank.
- The sequence-only alignment recovers 43 HomoloGene pairs but only 184 conserved interactions, showing that HomoloGene counts favor sequence-similarity matching.
B. Disambiguation of Inparanoid clusters with second-order interactions
Adding second-order interactions broadens the conserved-interaction definition but makes the Inparanoid-cluster network loopy and prevents exact optimization by MP. In this setting, PATH and GA still outperform MRF and IsoRank on conserved interactions.
- Case 4 counts pairs whose proteins have common neighbors in both species, extending conserved interactions beyond direct or one-sided second-order matches.
- Including cases 1–4 creates loops in the Inparanoid-cluster network, so the MP procedure is no longer suitable for exact optimization.
- PATH and GA conserve 3–4% more interactions than MRF and IsoRank when second-order interactions are added.
- The added second-order interactions produce no consistent HomoloGene advantage: MRF gains 3 pairs, IsoRank and PATH lose one, and GA is unchanged.
C. Global PPI network alignment by balancing sequence and interaction conservation
The balanced GNA experiments compare IsoRank, PATH, and GA by trading off sequence similarity against conserved interactions. GA achieves the strongest interaction-conservation results across the tested similarity range, while functional-orthology evidence remains inconclusive.
- The balanced GNA task seeks global alignments that compromise between sequence similarity and conserved interactions, including matches across Inparanoid clusters.
- For a fixed average sequence similarity, the preferred alignment maximizes the number of conserved interactions.
- 78% more conserved interactions than IsoRank were obtained by GA at IsoRank’s λ = 0.6 trade-off, while PATH achieved 20% more.IsoRank found 566 conserved interactions at average sequence similarity 15.26; PATH and GA found 678 and 1,006, respectively.
- Across the full average-sequence-similarity range, GA outperformed PATH, which outperformed IsoRank.
- Functional-orthology comparisons did not show clear differences among methods, with maximum mean GO coherence of 0.519 for IsoRank, 0.509 for GA, and 0.522 for PATH.The authors attribute the weak evidence partly to limited and imprecise functional annotations.
VI. DISCUSSION
The discussion presents constrained and balanced GNA as complementary formulations and reports that the new methods improve conserved-interaction retrieval. It also identifies open choices, extensions, and the difficulty of validating biological relevance.
- The paper distinguishes constrained GNA, based on allowed protein matches, from balanced GNA, which tunes sequence similarity against interaction conservation.
- MP finds the optimal constrained-GNA solution when applicable, while GA gives consistently good results for both formulations.
- Which GNA formulation best suits a given application and dataset remains an open question requiring systematic investigation.
- Potential extensions include weighted networks, multiple-species alignment, and many-to-many protein assignments for duplications or fusion events.PATH, GA, and IsoRank can be applied directly to weighted networks by replacing binary adjacency matrices with real-valued matrices.
- Biological relevance remains difficult to assess because HomoloGene and GO annotations are biased, scarce, or insufficiently precise for systematic evaluation.The authors argue that further experimental validation is needed.