A Simple Algorithm for Maximum Clique and Matching Protein Structures

The maximum common subgraph (MCS) problem has become increasingly important in matching protein structures of two proteins. Two proteins represented as graphs by simple contact map and product of these graphs was input to the proposed algorithm. A maximum clique in the product graph, found by the proposed algorithm, provides a measure of the structural similarity between the two proteins. The proposed algorithm produced optimal solution for most of the benchmark problem of the protein data bank and also for the public domain DIMACS benchmark problems of maximum clique. The computational results show that the prposed algorithm efficiently produces the common substructure of two proteins, used for protein structural analysis and protein classification.