Lagrangian Relaxation Applied to Sparse Global Network Alignment

M. El-Kebir, J. Heringa, G.W. Klau

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. In this paper we present a method for global network alignment that is fast and robust, and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. It is based on an integer linear programming formulation, generalizing the well-studied quadratic assignment problem. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the software tool natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative state-of-the-art methods with respect to quality and running time. An extended version of this paper including proofs and pseudo code is available at http://arxiv.org/pdf/1108.4358v1 .
Original languageEnglish
Title of host publicationPattern Recognition in Bioinformatics
Subtitle of host publication6th IAPR International Conference on PRIB 2011, Delft, The Netherlands, November 2-4, 2011, Proceedings
EditorsMarco Loog, Lodewyk Wessels, Marcel J.T. Reinders, Dick de Ridder
Place of PublicationBerlin
PublisherSpringer
Pages225-236
Number of pages12
ISBN (Electronic)9783642248559
ISBN (Print)9783642248542
DOIs
Publication statusPublished - 2011
EventProceedings 6th IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB 2011) -
Duration: 2 Nov 20114 Nov 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume7036
ISSN (Print)0302-9743

Conference

ConferenceProceedings 6th IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB 2011)
Period2/11/114/11/11

Fingerprint

Topology
Molecular interactions
Electric network analysis
Linear programming
Proteins

Cite this

El-Kebir, M., Heringa, J., & Klau, G. W. (2011). Lagrangian Relaxation Applied to Sparse Global Network Alignment. In M. Loog, L. Wessels, M. J. T. Reinders, & D. de Ridder (Eds.), Pattern Recognition in Bioinformatics: 6th IAPR International Conference on PRIB 2011, Delft, The Netherlands, November 2-4, 2011, Proceedings (pp. 225-236). (Lecture Notes in Computer Science; Vol. 7036). Berlin: Springer. https://doi.org/10.1007/978-3-642-24855-9_20
El-Kebir, M. ; Heringa, J. ; Klau, G.W. / Lagrangian Relaxation Applied to Sparse Global Network Alignment. Pattern Recognition in Bioinformatics: 6th IAPR International Conference on PRIB 2011, Delft, The Netherlands, November 2-4, 2011, Proceedings. editor / Marco Loog ; Lodewyk Wessels ; Marcel J.T. Reinders ; Dick de Ridder. Berlin : Springer, 2011. pp. 225-236 (Lecture Notes in Computer Science).
@inproceedings{ffa520a44f91408d8a019b547d6ce6cb,
title = "Lagrangian Relaxation Applied to Sparse Global Network Alignment",
abstract = "Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. In this paper we present a method for global network alignment that is fast and robust, and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. It is based on an integer linear programming formulation, generalizing the well-studied quadratic assignment problem. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the software tool natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative state-of-the-art methods with respect to quality and running time. An extended version of this paper including proofs and pseudo code is available at http://arxiv.org/pdf/1108.4358v1 .",
author = "M. El-Kebir and J. Heringa and G.W. Klau",
year = "2011",
doi = "10.1007/978-3-642-24855-9_20",
language = "English",
isbn = "9783642248542",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "225--236",
editor = "Marco Loog and Lodewyk Wessels and Reinders, {Marcel J.T.} and {de Ridder}, Dick",
booktitle = "Pattern Recognition in Bioinformatics",

}

El-Kebir, M, Heringa, J & Klau, GW 2011, Lagrangian Relaxation Applied to Sparse Global Network Alignment. in M Loog, L Wessels, MJT Reinders & D de Ridder (eds), Pattern Recognition in Bioinformatics: 6th IAPR International Conference on PRIB 2011, Delft, The Netherlands, November 2-4, 2011, Proceedings. Lecture Notes in Computer Science, vol. 7036, Springer, Berlin, pp. 225-236, Proceedings 6th IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB 2011), 2/11/11. https://doi.org/10.1007/978-3-642-24855-9_20

Lagrangian Relaxation Applied to Sparse Global Network Alignment. / El-Kebir, M.; Heringa, J.; Klau, G.W.

Pattern Recognition in Bioinformatics: 6th IAPR International Conference on PRIB 2011, Delft, The Netherlands, November 2-4, 2011, Proceedings. ed. / Marco Loog; Lodewyk Wessels; Marcel J.T. Reinders; Dick de Ridder. Berlin : Springer, 2011. p. 225-236 (Lecture Notes in Computer Science; Vol. 7036).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Lagrangian Relaxation Applied to Sparse Global Network Alignment

AU - El-Kebir, M.

AU - Heringa, J.

AU - Klau, G.W.

PY - 2011

Y1 - 2011

N2 - Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. In this paper we present a method for global network alignment that is fast and robust, and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. It is based on an integer linear programming formulation, generalizing the well-studied quadratic assignment problem. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the software tool natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative state-of-the-art methods with respect to quality and running time. An extended version of this paper including proofs and pseudo code is available at http://arxiv.org/pdf/1108.4358v1 .

AB - Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. In this paper we present a method for global network alignment that is fast and robust, and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. It is based on an integer linear programming formulation, generalizing the well-studied quadratic assignment problem. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the software tool natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative state-of-the-art methods with respect to quality and running time. An extended version of this paper including proofs and pseudo code is available at http://arxiv.org/pdf/1108.4358v1 .

U2 - 10.1007/978-3-642-24855-9_20

DO - 10.1007/978-3-642-24855-9_20

M3 - Conference contribution

SN - 9783642248542

T3 - Lecture Notes in Computer Science

SP - 225

EP - 236

BT - Pattern Recognition in Bioinformatics

A2 - Loog, Marco

A2 - Wessels, Lodewyk

A2 - Reinders, Marcel J.T.

A2 - de Ridder, Dick

PB - Springer

CY - Berlin

ER -

El-Kebir M, Heringa J, Klau GW. Lagrangian Relaxation Applied to Sparse Global Network Alignment. In Loog M, Wessels L, Reinders MJT, de Ridder D, editors, Pattern Recognition in Bioinformatics: 6th IAPR International Conference on PRIB 2011, Delft, The Netherlands, November 2-4, 2011, Proceedings. Berlin: Springer. 2011. p. 225-236. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-24855-9_20