LocalAli

LocalAli reconstructs evolutionary histories of conserved network modules and performs local network alignment to identify functionally conserved subnetworks across multiple biological networks.

Key Features:

• Evolutionary framework: Reconstructs evolution of conserved modules from a common ancestral module through defined evolutionary events to interpret local alignments in evolutionary terms.
• Maximum-parsimony model: Uses a maximum-parsimony evolutionary model to facilitate interpretation of module evolution and local alignment relationships.
• Meta-heuristic optimization (simulated annealing): Applies simulated annealing to search for optimal or near-optimal inner nodes in the evolutionary tree representing ancestral modules.
• Performance and scalability: Validated on 26 real datasets and 1,040 randomly generated datasets, reporting superior coverage, consistency, scalability, and high precision in identifying functionally coherent subnetworks.

Scientific Applications:

• Protein function prediction: Infers protein functions by identifying conserved modules across protein interaction networks.
• Functional module identification: Detects functionally coherent subnetworks conserved across multiple biological networks.
• Phylogenetic analysis of modules: Reconstructs evolutionary relationships among network modules using sequence and protein interaction data.
• Molecular mechanism inference: Provides insight into molecular processes by highlighting evolutionarily conserved network modules.

Methodology:

Reconstruction of conserved-module evolutionary histories using a maximum-parsimony model and optimization of ancestral inner nodes via simulated annealing.