Computer Science – Data Structures and Algorithms
Scientific paper
2011-08-22
Computer Science
Data Structures and Algorithms
Scientific paper
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.
El-Kebir Mohammed
Heringa Jaap
Klau Gunnar W.
No associations
LandOfFree
Lagrangian Relaxation Applied to Sparse Global Network Alignment does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lagrangian Relaxation Applied to Sparse Global Network Alignment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lagrangian Relaxation Applied to Sparse Global Network Alignment will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-176610