Lagrangian relaxation applied to sparse global network alignment

Mohammed El-Kebir, Jaap Heringa, Gunnar W. Klau

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 (US)
Title of host publicationPattern Recognition in Bioinformatics - 6th IAPR International Conference, PRIB 2011, Proceedings
Number of pages12
StatePublished - 2011
Externally publishedYes
Event6th IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2011 - Delft, Netherlands
Duration: Nov 2 2011Nov 4 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7036 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Lagrangian relaxation applied to sparse global network alignment'. Together they form a unique fingerprint.

Cite this