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

110 Downloads (Pure)


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 .
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
Number of pages12
ISBN (Electronic)9783642248559
ISBN (Print)9783642248542
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
ISSN (Print)0302-9743


ConferenceProceedings 6th IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB 2011)


Dive into the research topics of 'Lagrangian Relaxation Applied to Sparse Global Network Alignment'. Together they form a unique fingerprint.

Cite this