Protein function prediction as a graph-transduction game.

• For the first time the prediction of protein functions is modeled as a graph-transduction game. • The paper offers a newer perspective on the automatic protein function prediction problem. • Exploit at the same time the similarities at the level of proteins and functionalities. • Has better overall performances compared to other state-of-the-art graph-based methods. • Has been massively tested on 5 organisms, 3 ontologies with thousands of classes. Motivated by the observation that network-based methods for the automatic prediction of protein functions can greatly benefit from exploiting both the similarity between proteins and the similarity between functional classes (as encoded, e.g., in the Gene Ontology), in this paper we propose a novel approach to the problem, based on the notion of a "graph transduction game." We envisage a (non-cooperative) game, played over a graph, where the players (graph vertices) represent proteins, the functional classes correspond to the (pure) strategies, and protein- and function-level similarities are combined into a suitable payoff function. Within this formulation, Nash equilibria turn out to provide consistent functional labelings of proteins, and we use classical replicator dynamics from evolutionary game theory to find them. To test the effectiveness of our approach we conducted experiments on five different organisms and three ontologies, and the results obtained show that our method compares favorably with state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]