Aligning graphs and finding substructures by a cavity approach

被引：24

作者：

Bradde, S. ^{[1
,2
]}

Braunstein, A. ^{[2
]}

Mahmoudi, H. ^{[3
]}

Tria, F. ^{[3
]}

Weigt, M. ^{[3
]}

Zecchina, R. ^{[2
]}

机构：

[1] Int Sch Adv Studies SISSA, I-34014 Trieste, Italy

[2] Politecn Torino, I-10129 Turin, Italy

[3] Inst Sci Interchange, I-10133 Turin, Italy

来源：

EPL | 2010年 / 89卷 / 03期

关键词：

PROTEIN-INTERACTION; ALIGNMENT; PROPAGATION; NETWORKS;

D O I：

10.1209/0295-5075/89/37009

中图分类号：

O4 [物理学];

学科分类号：

070305 [高分子化学与物理];

摘要：

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. Copyright (C) EPLA, 2010

引用

页数：5

共 21 条

[1]

[Anonymous], 2001, RANDOM GRAPHS

[2]

Statistical mechanics of Steiner trees [J].

Bayati, M. ;

Borgs, C. ;

Braunstein, A. ;

Chayes, J. ;

Ramezanpour, A. ;

Zecchina, R. .

PHYSICAL REVIEW LETTERS, 2008, 101 (03)

[3]

Local graph alignment and motif search in biological networks [J].

Berg, J ;

Lässig, M .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2004, 101 (41) :14689-14694

[4]

Cross-species analysis of biological networks by Bayesian alignment [J].

Berg, Johannes ;

Lassig, Michael .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2006, 103 (29) :10967-10972

[5]

APPROXIMATING MAXIMUM INDEPENDENT SETS BY EXCLUDING SUBGRAPHS [J].

BOPPANA, R ;

HALLDORSSON, MM .

BIT, 1992, 32 (02) :180-196

[6]

Learning by message passing in networks of discrete synapses [J].

Braunstein, A ;

Zecchina, R .

PHYSICAL REVIEW LETTERS, 2006, 96 (03)

[7]

Survey propagation:: An algorithm for satisfiability [J].

Braunstein, A ;

Mézard, M ;

Zecchina, R .

RANDOM STRUCTURES & ALGORITHMS, 2005, 27 (02) :201-226

[8]

Clustering by passing messages between data points [J].

Frey, Brendan J. ;

Dueck, Delbert .

SCIENCE, 2007, 315 (5814) :972-976

[9]

Karp R.M., 1972, PLENUM PRESS SURV ST, P85, DOI 10.1007/978-1-4684-2001-2_9

[10]

From protein interactions to functional annotation: graph alignment in Herpes [J].

Kolar, Michal ;

Laessig, Michael ;

Berg, Johannes .

BMC SYSTEMS BIOLOGY, 2008, 2

← 1 2 3 →