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

Rashid Ibragimov, Maximilian Malek, Jiong Guo, Jan BaumbachGCB 2013 · OpenReview

TL;DR

This paper introduces GEDEVO, a novel evolutionary algorithm for aligning biological networks (like protein-protein interaction networks) by minimizing Graph Edit Distance. GEDEVO demonstrates superior performance compared to existing state-of-the-art methods, offering faster and more accurate alignments for large, complex biological networks.

What Problem Does This Paper Address?

The "post-genome era" has led to an explosion of biological data, particularly in the form of interaction networks. These networks, often representing how genes or proteins interact, can be massive, with millions of nodes and edges. Understanding the relationships and functions within these networks is crucial for deciphering biological processes. Network alignment, the task of finding correspondences between nodes in different networks, is a key technique for this, enabling the inference of biological function and evolutionary relationships. However, aligning these large-scale biological networks is computationally challenging, often described as "computationally hard and theoretically intractable." Existing methods struggle to scale effectively, failing to produce accurate results or even complete their computations within reasonable timeframes for real-world datasets.

Methods

GEDEVO tackles the network alignment problem by framing it as a Graph Edit Distance (GED) optimization problem. GED measures the minimum cost of transforming one graph into another through operations like node and edge insertions/deletions. GEDEVO employs an evolutionary algorithm (EA) to approximate the minimal GED.

Key aspects of their approach include:

  • Graph Edit Distance (GED) as the Fitness Function: Instead of directly optimizing metrics like Edge Correctness (EC), GEDEVO uses GED as the core optimization objective. This makes it more generalizable beyond biological networks.
  • Evolutionary Algorithm (EA): GEDEVO uses a population-based EA, mimicking natural selection. Individuals in the population represent potential network alignments (mappings between nodes).
  • Novel Offspring Generation: The EA utilizes a combination of operations (random generation, PMX-like mutation, and a directed "crossover") to generate new alignments. A key strategy is to swap "bad" pairs of node mappings more frequently to improve the overall alignment score.
  • Pair Score for Local Optimization: A "pair score" is used to evaluate how well individual node pairs align, incorporating both edge differences and graphlet degree signature distance (GSD) for topological similarity. This helps guide the EA towards better solutions.
  • Flexibility: While the paper focuses on topological criteria for comparability, GEDEVO is designed to incorporate other external biological information (like sequence similarity) into the pair score.

Datasets

The paper evaluates GEDEVO on several protein-protein interaction (PPI) networks. These include:

  • Bacterial networks: Campylobacter jejuni (cjejuni), Mesorhizobium loti (Meso), Synechocystis sp. (PCC6803) (Syne), and Escherichia coli (ecoli_fi).
  • Eukaryotic networks: Saccharomyces cerevisiae (yeast2, SC), Homo sapiens (HS, human1, ulitsky), and Drosophila melanogaster (DM).

These networks were chosen because they have been previously used to evaluate other state-of-the-art tools like C-GRAAL and MI-GRAAL, allowing for direct comparison. The paper provides a summary of these networks, including their source, number of proteins (nodes), and interactions (edges), in Table 2.

Key Insights and Ideas

  • GED as a Powerful Alignment Objective: Framing network alignment as a GED minimization problem is a robust approach that can generalize beyond specific biological contexts. It directly addresses the cost of transforming one network structure into another.
  • Evolutionary Algorithms are Well-Suited for Large-Scale Optimization: The paper demonstrates that EAs can effectively navigate the complex search space of network alignment problems, especially when dealing with large graphs where exact algorithms are infeasible.
  • Targeted Mutation Strategies Improve Convergence: The specific "PMX-like" mutation and directed swapping of "bad" pairs are crucial for efficiently improving alignment quality by focusing on problematic mappings.
  • Topological Information is Sufficient for High-Quality Alignments: GEDEVO's success using only topological features highlights the inherent structural similarities that can be leveraged for alignment, even between networks from different organisms.
  • Self-Alignment as a Robust Benchmark: Aligning a network to itself is a critical test case. GEDEVO's ability to achieve near-perfect (100%) Edge Correctness in these scenarios underscores its accuracy and robustness.

Key Results

GEDEVO consistently outperforms existing state-of-the-art tools (SPINAL, GHOST, C-GRAAL, MI-GRAAL) in terms of both alignment quality (measured by Edge Correctness - EC) and computational speed.

  • Superior Quality: GEDEVO achieved higher EC scores across most network pairs compared to its competitors. Notably, for the alignment of human1 vs. hprd, GEDEVO reached an EC of 89.37%, significantly outperforming MI-GRAAL (X, indicating failure to terminate) and C-GRAAL (47.07%).
  • Faster Execution: GEDEVO was significantly faster, often completing alignments in minutes where other tools took hours or failed to terminate within a 24-hour limit. For instance, aligning hprd and human1, GEDEVO took approximately 10 minutes, while C-GRAAL required up to 11 hours.
  • Robust Self-Alignment: GEDEVO achieved 100% EC when aligning networks to themselves in most cases, a feat not consistently matched by other tools.
  • Intermediate Results: The EA approach allows GEDEVO to provide intermediate alignment results, enabling users to terminate the process early if a satisfactory alignment is found, offering flexibility.

Limitations and Future Work

  • Computational Cost of GED: While GEDEVO approximates GED, the underlying computation can still be intensive, especially for very large graphs.
  • Population Size Influence: The paper notes that while larger population sizes generally lead to slightly better alignments, the algorithm is robust to different population sizes, suggesting that finding an optimal balance is key.
  • Future Work:
    • Improved Initialization: The authors suggest enhancing population initialization by incorporating assignment functions that consider degree differences between node pairs, aiming to speed up convergence.
  • Integration of External Data: While GEDEVO is flexible, future work will focus on integrating additional external node-to-node scoring functions (like BLAST) to further refine alignments, moving beyond purely topological information.

Summary updated

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
@inproceedings{ibragimov2013gedevo,
  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 = {GCB},
  year = {2013},
  url = {https://openreview.net/forum?id=0D6c6RgV6h},
}
Figure