Natalie 2.0: Sparse Global Network Alignment as a Special Case of Quadratic Assignment

Abstract : 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.
Type de document :
Article dans une revue
Algorithms, MDPI AG, 2015, 8 (4), 〈10.3390/a8041035〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01248544
Contributeur : Marie-France Sagot <>
Soumis le : mardi 30 mai 2017 - 14:03:51
Dernière modification le : mercredi 31 mai 2017 - 01:08:00
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 13:40:17

Fichier

algorithms-08-01035.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Mohammed El-Kebir, Jaap Heringa, Gunnar Klau. Natalie 2.0: Sparse Global Network Alignment as a Special Case of Quadratic Assignment. Algorithms, MDPI AG, 2015, 8 (4), 〈10.3390/a8041035〉. 〈hal-01248544〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

29