Natalie 2.0: sparse global network alignment as a special case of quadratic assignment
type: Item
instance of: scholarly article
title: Natalie 2.0: sparse global network alignment as a special case of quadratic assignment
zbMATH Open document ID: 1461.90065
author: Mohammed El-Kebir
author: Jaap Heringa
author: Gunnar W. Klau
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is still 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. 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. We exploit that network alignment is a special case of the well-studied quadratic assignment problem (QAP). We focus on sparse network alignment, where each node can be mapped only to a typically small subset of nodes in the other network. This corresponds to a QAP instance with a symmetric and sparse weight matrix. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the open source 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 established and recent state-of-the-art methods.
Mathematics Subject Classification ID: 90B80
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 92E10
zbMATH DE Number: 7042299
zbMATH Keywords: global network alignment
zbMATH Keywords: bioinformatics
zbMATH Keywords: graph matching
zbMATH Keywords: network analysis
zbMATH Keywords: network comparison
describes a project that uses: SPINAL
describes a project that uses: GHOST
describes a project that uses: Natalie
describes a project that uses: IsoRank
describes a project that uses: HubAlign
describes a project that uses: NETAL
describes a project that uses: NatalieQ
describes a project that uses: L-GRAAL
describes a project that uses: MAGNA++
describes a project that uses: KEGG
describes a project that uses: STRING
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a8041035
OpenAlex ID: W2173355656
Wikidata QID: Q60142893
cites work: Reducibility among Combinatorial Problems
cites work: The quadratic assignment problem
cites work: Q4321548
cites work: Q5519710
cites work: Algorithms for the Assignment and Transportation Problems
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Paths, Trees, and Flowers
cites work: Lagrangean relaxation. (With comments and rejoinder).
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: A Heuristic Method for the Set Covering Problem
cites work: Algorithm engineering for optimal alignment of protein structure distance matrices
DOI: 10.3390/A8041035
description: scientific article; zbMATH DE number 7042299