Algorithmic and Artificial Intelligence Methods for Protein Bioinformatics

Chapter 22

Protein–protein Interaction Network Alignment: Algorithms and Tools

VALERIA FIONDA

22.1 Introduction

Biological processes regulating cell lifecycle are determined from complex interactions among cell constituents (e.g., proteins); thus, cell behavior and functions can be better understood by analyzing complex protein interaction patterns than individual proteins. Starting from this observation, many techniques for properly mining protein interaction data and revealing possibly new, useful biological information, have been developed.

These tools leverage protein–protein interaction (PPI) networks as a formal model to encode protein interaction data. At its most basic abstraction level, the PPI network of a given organism can be represented as a graph, the nodes of which represent the proteins belonging to that organism, and an edge between two proteins encodes the fact that these two proteins interact.

Several tools have been proposed to perform the topological and functional analysis of PPI networks. Such techniques are able, by exploiting some specialized algorithms, to infer new information about cellular activity and evolutive processes of the species. These specialized algorithms are often based on the comparison of two or more PPI networks of different organisms with the aim of transferring biological knowledge from one species to another (or, possibly, more) species, thus allowing us to better characterize some previously inadequately characterized organisms.