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 language | English |
---|---|
Title of host publication | GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference |
Editors | Tobias Friedrich |
Publisher | Association for Computing Machinery |
Publication date | 2016 |
Pages | 341-348 |
ISBN (Electronic) | 978-1-4503-4206-3 |
DOIs | |
Publication status | Published - 2016 |
Event | Genetic and Evolutionary Computation Conference - Denver, United States Duration: 20. Jul 2016 → 24. Jul 2016 Conference number: 25th http://gecco-2016.sigevo.org/index.html/HomePage#&panel1-4 |
Conference
Conference | Genetic and Evolutionary Computation Conference |
---|---|
Number | 25th |
Country/Territory | United States |
City | Denver |
Period | 20/07/2016 → 24/07/2016 |
Internet address |
Bibliographical note
Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO, July 20-24, 2016, Denver, USA. 2016: 341-348Keywords
- algorithms
- bioinformatics
- networks
- Ant colony optimization
- Local search
- Network alignment
- Heuristics
- Simulated annealing
- Graph algorithms