Chiang Mai Journal of Science

Paper Type 

Title 

Author 

Email 

It is known that Proteins play crucial roles in most biological processes. It is also known that the function of a protein is determined by its structure. Thus, knowledge of the structures of proteins provides us a way toward the understanding of life science. However, common experimental methods, e.g., X-ray crystallography and NMR spectroscopy, are labored and high cost. Therefore, many studies have been made for the protein structural similarity. In this paper, we propose an improved algorithm based on graph theoretic approach for this problem. At first, a protein is transferred into a labeled graph according to its secondary structures, chemical properties, and topological relations. Next, for two graphs, the maximum common edge subgraph is computed for measuring the structural similarity of the corresponding proteins. By performing a practical technique, a maximum common edge subgraph of two graphs can be found efficiently. Finally, a common substructure of the given proteins can be found by a backtracking from the maximum common edge subgraph. Experimental results show that our method outperforms the RMSD method, especially in the evolutionary relatedness among various strains. This graph-based approach provides a practical direction for measuring protein structural similarity. Keywords: graph theory, protein similarity, bioinformatics, RMSD

Start & End Page 

Received Date 

Revised Date 

Accepted Date 

Full Text 

Keyword 

Volume 

DOI 

SDGs