License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.GCB.2013.68
URN: urn:nbn:de:0030-drops-42298
URL: https://drops.dagstuhl.de/opus/volltexte/2013/4229/
Ibragimov, Rashid ;
Malek, Maximilian ;
Guo, Jiong ;
Baumbach, Jan
GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment
Abstract
Introduction: With the so-called OMICS technology the scientific community has generated huge amounts of data that allow us to reconstruct the interplay of all kinds of biological entities. The emerging interaction networks are usually modeled as graphs with thousands of nodes and tens of thousands of edges between them. In addition to sequence alignment, the comparison of biological networks has proven great potential to infer the biological function of proteins and genes. However, the corresponding network alignment problem is computationally hard and theoretically intractable for real world instances.
Results: We therefore developed GEDEVO, a novel tool for efficient graph comparison dedicated to real-world size biological networks. Underlying our approach is the so-called Graph Edit Distance (GED) model, where one graph is to be transferred into another one, with a minimal number of (or more general: minimal costs for) edge insertions and deletions. We present a novel evolutionary algorithm aiming to minimize the GED, and we compare our implementation against state of the art tools: SPINAL, GHOST, \CGRAAL, and \MIGRAAL. On a set of protein-protein interaction networks from different organisms we demonstrate that GEDEVO outperforms the current methods. It thus refines the previously suggested alignments based on topological information only.
Conclusion: With GEDEVO, we account for the constantly exploding number and size of available biological networks. The software as well as all used data sets are publicly available at http://gedevo.mpi-inf.mpg.de.
BibTeX - Entry
@InProceedings{ibragimov_et_al:OASIcs:2013:4229,
author = {Rashid Ibragimov and Maximilian Malek and Jiong Guo and Jan Baumbach},
title = {{GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment}},
booktitle = {German Conference on Bioinformatics 2013},
pages = {68--79},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-59-0},
ISSN = {2190-6807},
year = {2013},
volume = {34},
editor = {Tim Bei{\ss}barth and Martin Kollmar and Andreas Leha and Burkhard Morgenstern and Anne-Kathrin Schultz and Stephan Waack and Edgar Wingender},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4229},
URN = {urn:nbn:de:0030-drops-42298},
doi = {10.4230/OASIcs.GCB.2013.68},
annote = {Keywords: Network Alignment, Graph Edit Distance, Evolutionary Algorithm, Protein-Protein Interactions}
}
|
Keywords: |
|
Network Alignment, Graph Edit Distance, Evolutionary Algorithm, Protein-Protein Interactions |
|
Collection: |
|
German Conference on Bioinformatics 2013 |
|
Issue Date: |
|
2013 |
|
Date of publication: |
|
09.09.2013 |
