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

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 (US)
Title of host publicationPattern Recognition in Bioinformatics - 6th IAPR International Conference, PRIB 2011, Proceedings
Pages225-236
Number of pages12
DOIs
StatePublished - 2011
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

Other

Other6th IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2011
CountryNetherlands
CityDelft
Period11/2/1111/4/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    El-Kebir, M., Heringa, J., & Klau, G. W. (2011). Lagrangian relaxation applied to sparse global network alignment. In Pattern Recognition in Bioinformatics - 6th IAPR International Conference, PRIB 2011, Proceedings (pp. 225-236). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7036 LNBI). https://doi.org/10.1007/978-3-642-24855-9_20