Analyzing Protein Lists with Large Networks: Edge-Count Probabilities in Random Graphs with Given Expected Degrees

We present an analytical framework to analyze lists of proteins with large undirected graphs representing their known functional relationships. We consider edge-count variables such as the number of interactions between a protein and a list, the size of a subgraph induced by a list, and the number of interactions bridging two lists. We derive approximate analytical expressions for the probability distributions of these variables in a model of a random graph with given expected degrees. Probabilities obtained with the analytical expressions are used to mine a protein interaction network for functional modules, characterize the connectedness of protein functional categories, and measure the strength of relations between modules.