A GPU Based Maximum Common Subgraph Algorithm for Drug Discovery Applications

The maximum common subgraph of two graphs, G
₁
and G
₂
, is the largest subgraph in G
₁
that is isomorphic to a subgraph in G
₂
. Finding the maximum common subgraph of two given graphs is known to be a NP-complete problem. An exact solution for the maximum common subgraph problem can be found by an algorithm that transforms the maximum common subgraph problem into a maximal clique enumeration problem. However, as the size of the graph increases, the solution space of the maximal clique enumeration problem increases combinatorially. A serial solution to the computationally intensive problem of complete maximal clique enumeration is tedious. This paper presents a parallel approach using Graphic Processing Unit to compute the maximum common subgraph of the given graphs. The parallel procedure achieves more than tenfold improvement in computational performance. As an application of the proposed parallel maximum common subgraph algorithm, two new tools, LIGANDMATCHER and GRAPHSCREEN are developed. These tools can be used to narrow down the large ligand search space to a small number in the screening phase of drug discovery process.