A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks

Simon Larsen, Frederik G. Alkærsig, Henrik Ditzel, Igor Jurisica, Nicolas Alcaraz, Jan Baumbach

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.
Original languageEnglish
Title of host publicationGECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference
EditorsTobias Friedrich
PublisherAssociation for Computing Machinery
Publication date2016
Pages341-348
ISBN (Electronic)978-1-4503-4206-3
DOIs
Publication statusPublished - 2016
EventGenetic and Evolutionary Computation Conference - Denver, United States
Duration: 20. Jul 201624. Jul 2016
Conference number: 25th
http://gecco-2016.sigevo.org/index.html/HomePage#&panel1-4

Conference

ConferenceGenetic and Evolutionary Computation Conference
Number25th
Country/TerritoryUnited States
CityDenver
Period20/07/201624/07/2016
Internet address

Bibliographical note

Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO, July 20-24, 2016, Denver, USA. 2016: 341-348

Keywords

  • algorithms
  • bioinformatics
  • networks
  • Ant colony optimization
  • Local search
  • Network alignment
  • Heuristics
  • Simulated annealing
  • Graph algorithms

Fingerprint

Dive into the research topics of 'A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks'. Together they form a unique fingerprint.

Cite this