Global alignment of PPI networks

Abstract

Given multiple PPI networks from different species, the global PPI network alignment problem is that of providing a global mapping between the nodes of the networks or subnetworks within them. Functional orthology detection, protein function prediction or verification, detection of common orthologous pathways, and reconstruction of the evolutionary dynamics of various species are some of the notable application areas of the global PPI network alignment problem. We focus on describing the basics of the problem, providing various formal definitions in the form of combinatorial optimization functions together with their computational complexities, and the algorithmic pillars of the suggested approaches. We also describe the common metrics employed in evaluating and comparing different global PPI network alignment outputs. Finally, we provide a discussion of relatively less studied aspects of the problem that may suggest potential open problems in need of further research on the topic.