Aligning graphs and finding substructures by a cavity approach

Abstract

We introduce a new distributed algorithm for aligning graphs or finding substructures within a given graph. It is based on the cavity method and is used to study the maximum-clique and the graph-alignment problems in random graphs. The algorithm allows to analyze large graphs and may find applications in fields such as computational biology. As a proof of concept we use our algorithm to align the similarity graphs of two interacting protein families involved in bacterial signal transduction, and to predict actually interacting protein partners between these families.

5 pages, 4 figures

References in corpus (7)

• Identification of direct residue contacts in protein-protein interaction by message passing
• Survey propagation: an algorithm for satisfiability
• Cross-species analysis of biological networks by Bayesian alignment
• Learning by message-passing in networks of discrete synapses
• Clustering by soft-constraint affinity propagation: Applications to gene-expression data
• Statistical Mechanics of Steiner trees
• Unsupervised and semi-supervised clustering by message passing: Soft-constraint affinity propagation

Cited by in corpus (8)

• Inferring interaction partners from protein sequences
• Simultaneous identification of specifically interacting paralogs and inter-protein contacts by Direct-Coupling Analysis
• Phylogenetic correlations can suffice to infer protein partners from sequences
• Correlations from structure and phylogeny combine constructively in the inference of protein partners from sequences
• Combining phylogeny and coevolution improves the inference of interaction partners among paralogous proteins
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Phase transitions for the cavity approach to the clique problem on random graphs
• DiffPaSS -- High-performance differentiable pairing of protein sequences using soft scores