Discovering frequent patterns of functional associations in protein interaction networks for function prediction

Predicting function from protein interaction networks has been challenging because of the intricate functional relationships among proteins. Most of the previous function prediction methods depend on the neighborhood of or the connected paths to known proteins, and remain low in accuracy. In this paper, we propose a novel approach for function prediction by detecting frequent patterns of functional associations in a protein interaction network. A set of functions that a protein performs is assigned into the corresponding node as a label. A functional association pattern is then represented as a labeled subgraph. Our FASPAM (frequent functional association pattern mining) algorithm efficiently finds the patterns that occur frequently in the network. It iteratively increases the size of frequent patterns by one node at a time by selective joining, and simplifies the network by a priori pruning. Using the yeast protein interaction network extracted from DIP, the FASPAM algorithm found more than 1,400 frequent patterns. By leave-one-out cross validation, our algorithm predicted functions from the frequent patterns with the accuracy of 86%, which is higher than the results from most previous methods.