The interpretation of protein structures based on graph theory and contact map

Purpose: The analysis of a protein’s structure allowing detailed exploration of the protein’s biological function is one of the most challenging problems in bioinformatics. There are efficient algorithms to calculate main properties of a protein structure, such as packing density, buried or surface residues, and accessible surface area. But these algorithms need the three-dimensional (3D) coordinates of the proteins. Methods: We used the contact map of a protein to construct a graph. By considering several features of the corresponding graph, we proposed some algorithms to discuss the above-mentioned properties of a protein. We also introduced a new measure for the hydrophobicity of an amino acid by defining an average degree for the amino acid as a vertex on the graph. Results: We compared our results with those obtained by some other existing algorithms. We found strong correlations between the popular methods, which use 3D coordinates, and our methods, which only use a predicted contact map. Conclusion: Many features of a protein can be predicted without having 3D coordinates, based on the contact map of the protein. The programs are freely available from http://www.bioinf.cs.ipm.ir/softwares/asa/asa.rar. Keywords: accessible surface area, buried residue, surface residue, packing density, hydrophobic