Good Math, Bad Math

As I mentioned back in the definitions post, a clique is a complete graph: a graph where all vertices are adjacent, where any pair of vertices has an edge connecting them.

The clique problem is an optimization problem which asks: given a graph G, what's the largest subgraph of G which is a clique? If we convert that to a decision problem, we get: "Is there a clique of N vertices contained in G?"

The maximal common subgraph problem is another optimization problem which asks: Given two graphs G and H, what is the largest subgraph of G which is isomorphic to a subgraph of H? In its representation as a decision problem, it becomes: is there a subgraph in G with N nodes which is isomorphic to a subgraph of H?

Following the usual pattern of these things, for both problems decision problem is NP complete, and the corresponding optimization problem is NP-hard. In both problems, in the worst case, you need to exhaustively consider all possible subgraphs in order to find the solution. In both cases, there are useful heuristics for pruning the search space, but like other NP complete/NP hard problems, either the heuristics sometimes fail to produce the optimal solution, or they sometimes wind up taking exponential time.

But still, heuristics are the key. In general, for applications of the graph clique problem (or the maximal subgraph), you want the optimum, but a solution which is not the ideal optimum, but is very close is nearly as good. Again, this is the common pattern for solutions of NP complete problems. Perfect solutions are hard to come by, but good ones are often not unknown.

(A great example of this comes from a talk I saw a few years ago by a software engineering researcher named Daniel Jackson. Daniel had built a really cool tool called Alloy, which did some neat analysis. In the course of his talk, he was describing how the analysis actually worked. The way he described it was: "The bad news is, it's reducible to 3-SAT, which is NP complete. The good news is, it's reducible to 3-SAT, which means we can compute the answer really fast.")

Anyway - the basic heuristics for these two problems are very similar; I'll describe the method for the clique problem; and starting from the largest common clique is a good heuristic for a starting point for getting the largest common subgraph.

For the maximum clique, there's a clever heuristic, which will, on average, find the maximal sub-clique. The idea is, find the set of all clique of size 2. Then, given that set, try to find cliques within it that can be merged. When you find two cliques that can be merged into a clique, remove those two, and replace them with their merge. Keep doing that until you can no longer merge any members of the set.

This can be implemented quite efficiently. (In fact, it's just a special case of the good old classic union-find algorithm, which I'll probably write about one of these days.) It's not a true solution to the problem, because it doesn't always produce the maximal clique. It produces a maximal clique over its members, but not necessarily the maximal clique over G.

Let's pause for just a moment, so that I can explain that last line, which sounds quite confusing.

Take a graph G=(V,E), and a set of vertices C={v₁,...,v_n}⊂V, such that the induced subgraph over C is a clique. C is a maximal clique over the vertices in C if there is no vertex is G that can be added to C producing a larger clique.

C is the maximal clique in G if and only if there is no larger clique contained in G.

The key difference is that in the first (a maximal clique over a set of vertices), we're asking for the largest clique containing that specific set of vertices; in the second, we're asking for the largest clique formed from any set of vertices in G.

For example, in the diagram below, the green clique is the maximal clique over the set of vertices, {F,D,L}. There is no larger possible clique in the graph containing those three vertices than the green 4-clique. But the maximal clique in G is actually the 6-clique containing the vertices {A, G, H, J, K, M}.

So, how does this became useful for biology?

• In evolutionary development, one of the ways of recognizing many processes is by looking at gene expression in terms of gene expression networks, which are graphs. Regulatory systems are often revealed as cliques in the expression network.
• When studying protein structures, one of the major techniques is to look at similar proteins, and find common cliques in the graph-based structural networks of the proteins.
• In pharmacology, the relationship between different chemicals is studied by finding the largest common subgraphs in the molecular graphs of the different substances.
• Again in pharmacology, there is a graph based method for searching for a compound that will interact with a specific biochemical target. One of the ways that this is done is to generate a large library of graphs describing known molecules. Then, given a particular target, you generate a complimentary graph describing its structure; then you search for graphs in the library that have large cliques in common with the complimentary graph of the target. The resulting list of molecules from the library form a set of likely candidates for a molecule that will produce the desired action by bonding with the target.