GEDEVO

GEDEVO applies an evolutionary algorithm to minimize Graph Edit Distance for aligning biological networks to compare topology and infer functional and evolutionary relationships.

Key Features:

• Graph Edit Distance (GED) model: Uses a GED model that transforms one graph into another with minimal costs associated with edge insertions and deletions.
• Evolutionary optimization: Employs an evolutionary algorithm to minimize the GED and obtain optimal or near-optimal network alignments.
• Scalability: Targets real-world-sized biological networks modeled as graphs with thousands of nodes and tens of thousands of edges.
• Comparative performance: Demonstrated improved performance in comparative studies versus SPINAL, GHOST, CGRAAL, and MIGRAAL.
• Topology refinement: Capable of refining alignments that were initially suggested based solely on topological information.
• Biological data compatibility: Applied to protein-protein interaction networks from various organisms.

Scientific Applications:

• Network alignment: Aligns biological interaction networks to facilitate comparison of network topology across species or conditions.
• Function inference: Supports inference of protein and gene function based on conserved interaction patterns revealed by alignments.
• Evolutionary analysis: Enables assessment of evolutionary relationships between organisms through comparative network structure.
• PPI network analysis: Applied to protein-protein interaction networks to compare interaction architectures across organisms.

Methodology:

GEDEVO models alignment as minimizing Graph Edit Distance (edge insertion/deletion costs) and optimizes this objective using an evolutionary algorithm.