PrimAlign: PageRank-inspired Markovian alignment for large biological networks

Area of Science:

• Computational Biology
• Bioinformatics
• Systems Biology

Background:

• Cross-species analysis of protein-protein interaction (PPI) networks aids in understanding evolutionary principles of cellular functions.
• Network alignment algorithms predict conserved protein functions and interactions by leveraging sequence similarity and conserved network topology of orthologous proteins.
• Current network alignment methods face challenges in achieving high accuracy and scalability.

Purpose of the Study:

• To introduce PrimAlign, a novel pairwise global network alignment algorithm.
• To enhance the accuracy and scalability of predicting conserved protein-protein interactions across species.

Main Methods:

• PrimAlign models network alignment as a Markov chain, utilizing iterative transitions to convergence.
• The algorithm incorporates PageRank principles to improve alignment quality.
• Evaluation involved human, yeast, and fruit fly PPI networks, alongside synthetic networks.

Main Results:

• PrimAlign demonstrated statistically significant improvements over prevalent methods in multiple evaluation metrics.
• The algorithm achieved superior runtime performance with linear asymptotic time complexity, indicating high scalability.
• Analysis of synthetic networks suggested that common topological measures may not accurately reflect alignment precision.

Conclusions:

• PrimAlign offers a significant advancement in network alignment for cross-species PPI analysis.
• The algorithm provides a scalable and accurate solution for identifying conserved protein interactions and functions.
• Further research may be needed to refine topological measures for evaluating alignment accuracy in real-world biological networks.