| Issue |
EPL
Volume 89, Number 3, February 2010
|
|
|---|---|---|
| Article Number | 37009 | |
| Number of page(s) | 5 | |
| Section | Condensed Matter: Electronic Structure, Electrical, Magnetic and Optical Properties | |
| DOI | https://doi.org/10.1209/0295-5075/89/37009 | |
| Published online | 22 February 2010 | |
Aligning graphs and finding substructures by a cavity approach
1
International School for Advanced Studies (SISSA) - Via Beirut 2/4, I-34014 Trieste, Italy, EU
2
Politecnico di Torino - Corso Duca degli Abruzzi 24, I-10129 Torino, Italy, EU
3
Institute for Scientific Interchange - Viale Settimio Severo 65, I-10133 Torino, Italy, EU
Corresponding author: riccardo.zecchina@polito.it
Received:
2
October
2009
Accepted:
20
January
2010
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.
PACS: 75.10.Nr – Spin-glass and other random models
© EPLA, 2010
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.