Global alignment of protein-protein interaction networks by graph matching methods

Area of Science:

• Computational Biology
• Bioinformatics
• Network Science

Background:

• Aligning protein-protein interaction (PPI) networks across species is vital for identifying conserved pathways and functional orthologs.
• This process aids in understanding evolutionary conserved pathways and protein complexes.
• Current heuristic methods for PPI network alignment are limited.

Purpose of the Study:

• To reformulate protein-protein interaction network alignment as a graph matching problem.
• To develop and evaluate novel methods for PPI network alignment.
• To compare the performance of new methods against state-of-the-art algorithms.

Main Methods:

• Reforming PPI alignment as a graph matching problem.
• Investigating the application of state-of-the-art graph matching algorithms.
• Developing methods for two alignment scenarios: strict sequence similarity constraints and optimal compromise between similarity and interaction conservation.

Main Results:

• Proposed methods consistently outperform existing state-of-the-art algorithms.
• Achieved a 78% increase in retrieving conserved interactions compared to IsoRank for a specific sequence similarity level.
• Successfully aligned yeast and fly PPI networks using the new methods.

Conclusions:

• The developed graph matching approaches offer improved performance for PPI network alignment.
• These methods enhance the identification of conserved interactions and functional orthologs across species.
• The proposed techniques provide a more effective solution for the challenging PPI alignment problem.