期刊名称：International Journal of Combinatorial Optimization Problems and Informatics
印刷版ISSN：2007-1558
电子版ISSN：2007-1558
出版年度：2010
卷号：1
期号：2
页码：2-11
语种：English
出版社：International Journal of Combinatorial Optimization Problems and Informatics
其他摘要：The maximum common subgraph (MCS) problem has become increasingly important in matching protein structures of two proteins. Two proteins represented as graphs by simple contact map and product of these graphs was input to the proposed algorithm. A maximum clique in the product graph, found by the proposed algorithm, provides a measure of the structural similarity between the two proteins. The proposed algorithm produced optimal solution for most of the benchmark problem of the protein data bank and also for the public domain DIMACS benchmark problems of maximum clique. The computational results show that the prposed algorithm efficiently produces the common substructure of two proteins, used for protein structural analysis and protein classification.
关键词：Protein structure; maximum clique; vertex cover; vertex support; heuristic; NP-hard problem
