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

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TitelGECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference
RedaktørerTobias Friedrich
ForlagAssociation for Computing Machinery
Publikationsdato2016
Sider341-348
ISBN (Elektronisk)978-1-4503-4206-3
DOI
StatusUdgivet - 2016
BegivenhedGenetic and Evolutionary Computation Conference - Denver, USA
Varighed: 20. jul. 201624. jul. 2016
Konferencens nummer: 25th
http://gecco-2016.sigevo.org/index.html/HomePage#&panel1-4

Konference

KonferenceGenetic and Evolutionary Computation Conference
Nummer25th
LandUSA
ByDenver
Periode20/07/201624/07/2016
Internetadresse

Fingeraftryk

Edge detection
Simulated annealing
Proteins
Heuristic algorithms
Program processors
Annealing
Local search (optimization)

Bibliografisk note

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

Citer dette

Larsen, S., Alkærsig, F. G., Ditzel, H., Jurisica, I., Alcaraz, N., & Baumbach, J. (2016). A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks. I T. Friedrich (red.), GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference (s. 341-348). Association for Computing Machinery. https://doi.org/10.1145/2908812.2908858
Larsen, Simon ; Alkærsig, Frederik G. ; Ditzel, Henrik ; Jurisica, Igor ; Alcaraz, Nicolas ; Baumbach, Jan. / A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks. GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. red. / Tobias Friedrich. Association for Computing Machinery, 2016. s. 341-348
@inproceedings{1325b414fe614e789721614164ded8b0,
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.",
keywords = "algorithms, bioinformatics, networks, Ant colony optimization, Local search, Network alignment, Heuristics, Simulated annealing, Graph algorithms",
author = "Simon Larsen and Alk{\ae}rsig, {Frederik G.} and Henrik Ditzel and Igor Jurisica and Nicolas Alcaraz and Jan Baumbach",
note = "Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO, July 20-24, 2016, Denver, USA. 2016: 341-348",
year = "2016",
doi = "10.1145/2908812.2908858",
language = "English",
pages = "341--348",
editor = "Tobias Friedrich",
booktitle = "GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery",
address = "United States",

}

Larsen, S, Alkærsig, FG, Ditzel, H, Jurisica, I, Alcaraz, N & Baumbach, J 2016, A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks. i T Friedrich (red.), GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, s. 341-348, Genetic and Evolutionary Computation Conference, Denver, USA, 20/07/2016. https://doi.org/10.1145/2908812.2908858

A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks. / Larsen, Simon; Alkærsig, Frederik G.; Ditzel, Henrik; Jurisica, Igor; Alcaraz, Nicolas; Baumbach, Jan.

GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. red. / Tobias Friedrich. Association for Computing Machinery, 2016. s. 341-348.

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

TY - GEN

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

AU - Larsen, Simon

AU - Alkærsig, Frederik G.

AU - Ditzel, Henrik

AU - Jurisica, Igor

AU - Alcaraz, Nicolas

AU - Baumbach, Jan

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

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - algorithms

KW - bioinformatics

KW - networks

KW - Ant colony optimization

KW - Local search

KW - Network alignment

KW - Heuristics

KW - Simulated annealing

KW - Graph algorithms

U2 - 10.1145/2908812.2908858

DO - 10.1145/2908812.2908858

M3 - Article in proceedings

SP - 341

EP - 348

BT - GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

A2 - Friedrich, Tobias

PB - Association for Computing Machinery

ER -

Larsen S, Alkærsig FG, Ditzel H, Jurisica I, Alcaraz N, Baumbach J. A Simulated Annealing Algorithm for Maximum Common Edge Subgraph Detection in Biological Networks. I Friedrich T, red., GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. Association for Computing Machinery. 2016. s. 341-348 https://doi.org/10.1145/2908812.2908858