Graph Alignment: Fuzzy Pattern Mining for the Structural Analysis of Protein Active Sites

Graphs are frequently used to describe the geometry and also the physicochemical composition of protein active sites. Here, the concept of graph alignment as a novel method for the structural analysis of protein binding pockets is presented. Using inexact, approximate graph-matching techniques, our method enables the robust identification of fuzzily conserved areas in binding pockets. Thus, using multiple graph alignments, it is possible to characterize functional protein families independent of sequence or fold homology. This paper first introduces the problem of graph alignment in a formal way and discusses algorithmic solutions for this problem. Then, it is shown how the calculated graph alignments can be analyzed to identify structural features that are characteristic for a given protein family. In this connection, the related concept of a fuzzy consensus graph is introduced. The methods are applied to a substantial high-quality subset of the PDB database and their ability to successfully characterize and classify 10 highly populated functional protein families is shown.