Back to Search
Start Over
Aligning graphs and finding substructures by a cavity approach
- Source :
- 2010 Europhys. Lett. 89 37009
- Publication Year :
- 2009
-
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.<br />Comment: 5 pages, 4 figures
Details
- Database :
- arXiv
- Journal :
- 2010 Europhys. Lett. 89 37009
- Publication Type :
- Report
- Accession number :
- edsarx.0905.1893
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1209/0295-5075/89/37009