Gardiner E J, Artymiuk P J, Willett P
Krebs Institute for Biomolecular Research, University of Sheffield, UK.
J Mol Graph Model. 1997 Aug;15(4):245-53. doi: 10.1016/s1093-3263(97)00089-2.
The representation of chemical and biological molecules by means of graphs permits the use of a maximum common subgraph (MCS) isomorphism algorithm to identify the structural relationships existing between pairs of such molecular graphs. Clique detection provides an efficient way of implementing MCS detection, and this article reports a comparison of several different clique-detection algorithms when used for this purpose. Experiments with both small molecules and proteins demonstrate that the most efficient of these particular applications, which typically involve correspondence graphs with low edge densities, is the algorithm described by Carraghan and Pardalos. This is shown to be two to three times faster than the Bron-Kerbosch algorithm that has been used previously for MCS applications in chemistry and biology. However, the latter algorithm enables all substructures common to a pair of molecules to be identified, and not just the largest ones, as with the other algorithms considered here. The two algorithms can usefully be combined to increase the efficiency of database-searching systems that use the MCS as a measure of structural similarity.
通过图形来表示化学和生物分子，这使得我们能够使用最大公共子图（MCS）同构算法来识别此类分子图对之间存在的结构关系。团检测提供了一种实现MCS检测的有效方法，本文报告了几种不同的团检测算法在此目的下的比较。对小分子和蛋白质的实验表明，在这些特定应用中，效率最高的算法（这些应用通常涉及边密度较低的对应图）是Carraghan和Pardalos所描述的算法。结果表明，该算法比先前在化学和生物学的MCS应用中使用的Bron-Kerbosch算法快两到三倍。然而，后一种算法能够识别一对分子共有的所有子结构，而不仅仅是像这里考虑的其他算法那样只能识别最大的子结构。这两种算法可以有效地结合起来，以提高将MCS用作结构相似性度量的数据库搜索系统的效率。
