GRAAL

GRAAL performs global alignment of protein-protein interaction (PPI) networks to identify evolutionarily and functionally conserved proteins and interactions for transfer of functional information across species.

Key Features:

• Global Network Alignment: Performs global alignments between PPI networks to uncover conserved pathways, protein complexes, and functional orthologs.
• Optimization of Functional Conservations: Simultaneously optimizes conservation of proteins and their interactions to produce biologically relevant alignments.
• Alignment Search Heuristic: Employs integer programming combined with Lagrangian relaxation to search for optimal alignments and address the NP-complete sub-graph isomorphism problem.
• Performance Metrics: Quantifies alignment quality by identifying largest common sub-graphs using edge-correctness and symmetric sub-structures scores.
• Biological Quality Assessment: Evaluates protein mapping quality using semantic similarity computed from Gene Ontology annotations.
• Interaction Semantic Similarity: Implements a measure for assessing semantic similarity of mapped interactions to detect functionally conserved interactions.
• Prediction of New Interactions: Demonstrates capability to predict novel PPIs through alignments between baker's yeast and human networks.
• Topological vs. Sequence Information: Emphasizes topological information over sequence data for identifying functionally conserved interactions.

Scientific Applications:

• Evolutionary Conservation and Functional Orthology: Reveals conserved pathways, complexes, and orthologous relationships across species via network alignment.
• PPI Prediction and Experimental Hypothesis Generation: Enables prediction of novel protein-protein interactions for subsequent experimental validation.
• Functional Information Transfer: Facilitates transfer of functional annotations and insights between aligned networks.
• Disease Mechanisms and Therapeutic Target Identification: Supports comparative network analyses to study disease mechanisms and identify potential therapeutic targets.

Methodology:

Uses an alignment search heuristic based on integer programming with Lagrangian relaxation; optimizes protein- and interaction-conservation scores; evaluates alignments with edge-correctness and symmetric sub-structures metrics; computes semantic similarity from Gene Ontology for proteins and interactions; implemented in C++.