Detection Method of Function Site of Proteins by Using a Graph-Theoretic Algorithm

We present a new detection method of amino acid residues, which play the role of the protein functional activities. The principle of the method is that proteins with the same function have similar amino acid residues at the similar 3D positions. Thus we assume that maximal amino acid residues existing in the similar 3D positions of proteins are their function site residues. The method first constructs the graph describing relations of 3D positions of all possible pairs of amino acid residues in two proteins and then extracts its maximal complete subgraph, which means the maximal amino acid residues at the similar three dimensional positions, by the algorithm of Carraghan and Pardalos. The method was tested using electron transport proteins: azurin and plastocyanin, and 6 reasonable amino acid residues as the function site residues of those proteins, were obtained. The method was also applied to acid proteases: porcine pepsin and Rhizopus pepsin. In this investigation, we restricted the formation of amino acid pairs only to the same ones, because of the limitation of computer memory. The result gave 11 amino acid residues, consisting in some active site residues, as the function residues of acid proteases. The results indicate the effectiveness of this new method.