Common pharmacophore identification using frequent clique detection algorithm

Abstract

The knowledge of a pharmacophore, or the 3D arrangement of features in the biologically active molecule that is responsible for its pharmacological activity, can help in the search and design of a new or better drug acting upon the same or related target. In this paper, we describe two new algorithms based on the frequent clique detection in the molecular graphs. The first algorithm mines all frequent cliques that are present in at least one of the conformers of each (or a portion of all) molecules. The second algorithm exploits the similarities among the different conformers of the same molecule and achieves an order of magnitude performance speedup compared to the first algorithm. Both algorithms are guaranteed to find all common pharmacophores in the data set, which is confirmed by the validation on the set of molecules for which pharmacophores have been determined experimentally. In addition, these algorithms are able to scale to data sets with arbitrarily large number of conformers per molecule and identify multiple ligand binding modes or multiple binding sites of the target.

Figure 1

Example of graphs. G₁ is a clique, G₂ is not a clique.

Figure 2

Three graphs representing three conformations of the same molecule. The edge labels represent two-bin assignment of the distances.

Figure 3

Representations of graphs in Fig. 2: a) adjacency matrices for each conformer and b) unified conformational matrix.

Figure 4

The five molecules used for pharmacophore identification study (obtained from9).

Figure 5

The pharmacophore model for the compounds in set 1 (red regions indicate aromatic ring sites R and blue ones indicate the ammonium nitrogen that can be P or D).

Figure 6

The pharmacophore model for the compounds in set 2 (red regions indicate aromatic ring sites R and blue ones indicate the ammonium nitrogen that can be P or D).

Figure 7

The pharmacophore model for the compounds in set 3 (red regions indicate aromatic ring sites R and blue ones indicate the ammonium nitrogen that can be P or D).