SANA

SANA applies simulated annealing to align biological networks, primarily protein–protein interaction networks, by optimizing objective functions that combine topological and functional similarity.

Key Features:

• Simulated Annealing Algorithm: Implements simulated annealing as the core search algorithm to iteratively explore and refine network alignments based on an objective function.
• Objective Function (M): Evaluates alignment quality using an objective function M that measures both topological and functional similarities.
• Topological Measure (S₃): Uses the S₃ topological measure and demonstrates that optimizing solely for S₃ can produce alignments with perfect S₃ scores while exhibiting "saturation of the topological score," where S₃'s correlation with alignment correctness diminishes before true alignment accuracy is achieved.
• Performance: In comparative evaluations against 12 recent algorithms, produced 5–10 times more correct node pairings when the true alignment was known.
• Convergence to Optimal Solutions: Rapidly converges to perfect alignments when supplied with an ideal objective function that encodes identity mapping.

Scientific Applications:

• Protein-Protein Interaction Networks: Aligns PPI networks to reveal functional similarities and evolutionary relationships between species.
• Network Biology: Applicable to analysis of metabolic pathways and gene regulatory networks through handling of complex topological structures.

Methodology:

Performs simulated annealing search that iteratively refines alignments using an objective function M and evaluates topological similarity with the S₃ measure.