Development of a Tool for Comparison of Protein 3D Structure using graph theoretic approach

Abstract

We have illustrated in detail about two novel methods for comparison of 3D structure using (1) graph partition and (2) graph properties. The both proposed methods have been implemented in MATLAB by writing codes for various functions. The performance of the developed methodologies are tested with two existing best methods such as CE and jFATCAT on 100 proteins benchmark dataset with SCOP (Structural Classification Of Proteins) database. First method “graph partitioning” method is comprises conversion of 3D graph into 2D graph, partitioning of 2D graph into sub-graphs and then aligning sub-graphs. Finally structure similarity has been calculated by identify local structural similarities between sub-graphs to global similarity of the whole graph. The proposed method has shown significant improvement over jFATCAT and accuracy has increased up to 12-15%. Prime notion of the method is the decomposition of structure to clusters than single residues and SSE, this could be basic interaction of non-bonded residues in the arrangement of structure elements within a structure. These interaction leads protein fold space and arrangement of SSE elements in 3D space. Then, aligned the structures based on atoms positions and association with other atoms within clusters and between clusters to identify similar geometry and similarity of the two structures. The proposed method performed better in terms of classification accuracy due to the inclusion of all atoms but CE and jFATCAT uses only backbone C-α atoms and non-bonded atoms in a cluster may plays important role to inclusion of folding information of protein while comparing the 3D structures. In second method, is based on concepts of construction of graph from real world problems, database for graph and graph mining, pattern recognition are rich fields of computational techniques to study structures, topologies and properties of graphs. In this method, we have demonstrated that converting protein 3Dstructures into graphs and into properties such as total degree, maximum degree, no of adjacencies, average number of degree, cluster coefficient, graph energy, spectrum and number of components etc. Exploitation of the graph properties and data mining technique to perform complex studies on protein 3D structure. The proposed method is fast in terms of computation time complexity. Regarding accuracy is little improved over jFATCAT method. In future, this work can be extended for including more number of graph properties and more research can be done to find out the best structural identity or similarity among protein structures.