How Complexpander works
This program ('Complexpander') makes use of a database of protein interactions to determine
a degree of belief for partners in a protein complex, given a candidate set
of "core" complex proteins. The database need not be a complete databse
of protein interactions, since the program merely generates a degree of belief
based on available evidence. The addition of new evidence to the database
changes the state of belief about particular interactions, just as evidence
affects state of belief in the lab.
Experimental evidences for and against a particular protein interaction may
be combined to provide a degree of belief for that interaction. This belief
may be represented as a probability of that interaction existing.
The combined total of interactions may then be viewed as a graph, with proteins
representing nodes in the graph, edges representing interaction between pairs
of proteins, and edge weights representing the degree of belief that the edge
(i.e., the interaction) exists.
For any adjacent set of nodes, determining our degree of belief in their
connectivity is trivial - it is equal to the weight of the edge. But for
non-adjacent edges, the problem becomes more difficult, and it remains to
be demonstrated that a closed-form solution for such a degree of belief can
be found at all, for an arbitrary graph, in polynomial time.
To avoid this situation, we can approximate solutions using monte-carlo
simulations.
The complete network of protein interactions may be used to create a set of
simulated sparse networks. A sparse network is created by rolling a random
number between zero and one for each edge, comparing to the weight of the edge,
and then reassigning the edge a weight of either zero or one. Ten thousand
such sparse networks are generated and saved in a database.
In each sparse network, it is now trivial to determine our degree of belief
for connectivity, since edges now only have weight zero or one. If there
exists a path between two nodes, we believe they are connected.
The fraction of sparse networks in which we believe two nodes are connected
is a fair approximation for the degree of belief that these nodes are connected
in the complete network.