Algorithms for Large, Sparse Network Alignment Problems

被引：94

作者：

Bayati, Mohsen ^{[1
]}

Gerritsen, Margot ^{[2
]}

Gleich, David F. ^{[3
]}

Saberi, Amin ^{[4
]}

Wang, Ying ^{[3
]}

机构：

[1] Stanford Univ, Dept Elect Engn, Stanford, CA 94305 USA

[2] Stanford Univ, Energy Resources Engn Dept, Stanford, CA 94305 USA

[3] Stanford Univ, ICME, Stanford, CA 94305 USA

[4] Stanford Univ, MS&E Dept, Stanford, CA 94305 USA

来源：

2009 9TH IEEE INTERNATIONAL CONFERENCE ON DATA MINING | 2009年

关键词：

network alignment; belief propagation; graph matching; message-passing; PROTEIN-INTERACTION NETWORKS; GLOBAL ALIGNMENT;

D O I：

10.1109/ICDM.2009.135

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We propose a new distributed algorithm for sparse variants of the network alignment problem, which occurs in a variety of data mining areas including systems biology, database matching, and computer vision. Our algorithm uses a belief propagation heuristic and provides near optimal solutions for this NP-hard combinatorial optimization problem. We show that our algorithm is faster and outperforms or ties existing algorithms on synthetic problems, a problem in bioinformatics, and a problem in ontology matching. We also provide a unified framework for studying and comparing all network alignment solvers.

引用

页码：705 / +

页数：2

共 23 条

[1]

[Anonymous], 1963, Low-Density Parity-Check Codes

[2]

[Anonymous], 2003, P KDD 2003 WORKSH DA

[3]

Bayati M, 2005, 2005 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), VOLS 1 AND 2, P1763

[4]

BAYATI M, 2009, 09073338 ARXIV

[5] 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

[6]

BRADDE S, 2009, 09051893 ARXIV

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

Braunstein, A ;

Zecchina, R .

PHYSICAL REVIEW LETTERS, 2006, 96 (03)

[8]

Conte Donatello, 2007, Journal of Graph Algorithms and Applications, V11, P99, DOI 10.7155/jgaa.00139

[9] Thirty years of graph matching in pattern recognition [J].

Conte, D ;

Foggia, P ;

Sansone, C ;

Vento, M .

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2004, 18 (03) :265-298

[10] Graemlin: General and robust alignment of multiple large interaction networks [J].

Flannick, Jason ;

Novak, Antal ;

Srinivasan, Balaji S. ;

McAdams, Harley H. ;

Batzoglou, Serafim .

GENOME RESEARCH, 2006, 16 (09) :1169-1181

← 1 2 3 →