Paper Info
Title
A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks.
Abstract
Network alignment is a challenging computational problem that identifies node or edge mappings between two or more networks, with the aim to unravel common patterns among them. Pairwise network alignment is already intractable, making multiple network comparison even more difficult. Here, we introduce a heuristic algorithm for the multiple maximum common edge subgraph problem that is able to detect large common substructures shared across multiple, real-world size networks efficiently. Our algorithm uses a combination of iterated local search, simulated annealing and a pheromone-based perturbation strategy. We implemented multiple local search strategies and annealing schedules, that were evaluated on a range of synthetic networks and real protein-protein interaction networks. Our method is parallelized and well-suited to exploit current multi-core CPU architectures. While it is generic, we apply it to unravel a biochemical backbone inherent in different species, modeled as multiple maximum common subgraphs.
Year
DOI
Venue
2016
10.1145/2908812.2908858
GECCO
Keywords
Field
DocType
Graph algorithms, Network alignment, Heuristics, Simulated annealing, Local search, Ant colony optimization
Ant colony optimization algorithms,Computer science,Theoretical computer science,Artificial intelligence,Iterated local search,Simulated annealing,Pairwise comparison,Computational problem,Mathematical optimization,Biological network,Heuristic (computer science),Local search (optimization),Machine learning
Conference
Citations 
PageRank 
References 
2
0.37
18
Authors
6
Name
Order
Citations
PageRank
Simon J. Larsen120.37
Frederik G. Alkærsig220.37
Henrik J Ditzel3100.86
Igor Jurisica461645.55
Nicolas Alcaraz5191.75
Jan Baumbach614822.11