NAIGO: An Improved Method to Align PPI Networks Based on Gene Ontology and Graphlets

Area of Science:

• Bioinformatics
• Computational Biology
• Systems Biology

Background:

• High-throughput technologies generate vast protein-protein interaction (PPI) networks, necessitating efficient computational alignment tools.
• Network alignment is crucial for predicting protein function, identifying conserved modules, and studying evolutionary relationships.
• Existing network alignment algorithms struggle with speed and accuracy for large-scale networks (e.g., human vs. yeast) due to the NP-complete nature of the problem.

Purpose of the Study:

• To introduce NAIGO (Network Alignment by Integrating Biological Process), a novel algorithm designed for fast and accurate PPI network alignment.
• To improve upon existing methods for aligning large biological networks, particularly across different species.

Main Methods:

• NAIGO divides networks into subnets using prior biological knowledge (e.g., Gene Ontology).
• It aligns subnet pairs using protein orthologous and local structural information.
• Global alignment is achieved by expanding local alignments and solving an assignment problem via the Hungarian method.

Main Results:

• NAIGO demonstrated superior performance compared to IsoRank, GRAAL, SANA, and NABEECO in aligning human and *Saccharomyces cerevisiae* PPI networks.
• The algorithm successfully identified more orthologous proteins and matched interactions.
• Identified potential functional orthologs (e.g., RRM2B in human and DNA2 in *S. cerevisiae*) involved in DNA repair and a conserved mismatch repair subnet.

Conclusions:

• NAIGO offers a significant advancement in computational tools for PPI network alignment, balancing speed and accuracy.
• The method facilitates the discovery of functional orthologs and conserved biological pathways.
• NAIGO aids in predicting protein functions and understanding evolutionary relationships, as exemplified by its application to DNA repair and autophagosome assembly pathways.