1 Search Results for "Ibragimov, Rashid"


Document
GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment

Authors: Rashid Ibragimov, Maximilian Malek, Jiong Guo, and Jan Baumbach

Published in: OASIcs, Volume 34, German Conference on Bioinformatics 2013


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.

Cite as

Rashid Ibragimov, Maximilian Malek, Jiong Guo, and Jan Baumbach. GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 68-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{ibragimov_et_al:OASIcs.GCB.2013.68,
  author =	{Ibragimov, Rashid and Malek, Maximilian and Guo, Jiong and Baumbach, Jan},
  title =	{{GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{68--79},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.68},
  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}
}
  • Refine by Author
  • 1 Baumbach, Jan
  • 1 Guo, Jiong
  • 1 Ibragimov, Rashid
  • 1 Malek, Maximilian

  • Refine by Classification

  • Refine by Keyword
  • 1 Evolutionary Algorithm
  • 1 Graph Edit Distance
  • 1 Network Alignment
  • 1 Protein-Protein Interactions

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail