4.2 Clique detection

Answer: Clique detection - part of graph theory

Graph Theory Terminology:

graph	set of nodes and edges
nodes	objects ug = { ui }
edges	pairs of nodes eg = {(ui,uj) | ui,uj  ug} edge indicates a relationship between the nodes
adjacency	presence of edge between nodes
subgraph	subset of nodes and edges of a graph
completely connected subgraph	subgraph with edges between all node pairs
clique	maximal completely connected subgraph

Docking by clique detection:

• geometrical docking requires that all of the distances in a ligand subset
  can be mapped to equivalent distances in a subset of protein descriptors
• define distance equivalence as adjacency
• each adjacency defines an edge in the docking graph
• presence of a clique in the docking graph proves the existence of a match between ligand and protein provided that non-subset ligand atoms do not clash with the protein

Example:

• Assume successful match if at least 3 ligand atoms
  can be mapped to 3 protein descriptors.
• If the atoms are non-colinear, then the docking mode is uniquely defined
  (fixing of 6 degrees of freedom). Chiral ligands require at least 4 matches.

.

Crippen algorithm: single docking graph (implemented in DOCK 4)

node = pairing of ligand atom with protein descriptor edge = distance between 2 atoms equals distance between 2 descriptors |4 3| = |A B| or A4 is adjacent to B3 |4 3| = |B A| or B4 is adjacent to A3 |1 3| = |E B| = |B E| |1 4| = |E A| = |A E|

.

• Notice that we get duplicates with this algorithm.
  Can be avoided by using only the upper matrix triangle
• Has potential for flexible ligand docking:
  use upper and lower bounds instead of distances between nodes
  (distance geometry methods)
• CPU time considerations:
• systematic search matching without docking graph
  (i.e. no distance restraints):

number of possibilities	= nCNP x nPNL
	= NP! [n! (NP-n)]-1 x NL! (NL-n)-1
with:	NP = protein descriptor nodes NL = ligand nodes n = required matchings xCy = combinations (all groups of size x out of population y;  order irrelevant) xPy = permutations (all groups of size x out of population y;  order matters)

e.g. if NP=50; NL=20; n=4 then 10¹¹ possibilities

• matching with docking graph:

graph is a sparse matrix (typically 1 % filled) determined by distance tolerance and distance minimum

• distance tolerance: 0.5 Å
• distance minimum: 2.0 Å (avoid matching bond lengths)

typically only 10³-10⁵ possibilities

• additional constraints: coloring of the graph
  

allow only chemically compatible matches
e.g. exclude matching of H bond donor descriptor with carbonyl O