MultiMCS: A Fast Algorithm for the Maximum Common Substructure Problem on Multiple Molecules
MultiMCS: A Fast Algorithm for the Maximum Common Substructure Problem on Multiple Molecules
复制标题
DOI：
10.1021/ci100297y
复制
发表时间：
2011-04-01
影响因子：
5.6
通讯作者：
Schuffenhauer, Ansgar
中科院分区：
文献类型：
--
作者：
Hariharan, Ramesh;Janakiraman, Anand;Schuffenhauer, Ansgar
文献中已经发表了几种有效的基于对应图的算法来确定一对分子的最大公共子结构(MCS)。然而，将问题扩展到三个或更多分子并不是微不足道的；在两分子情况下用于提高效率的启发式方法要么不适用于多分子情况，要么不能提供显著的加速比。我们在算法方面的具体贡献是双重的。首先，我们展示了对应图方法是如何实现的。两个分子的情况可以推广得到一个算法，该算法保证找到多个分子的最佳连接MCS，并且使用一种新的分而治之的策略在大多数分子家族上运行得很快，到目前为止还没有在本文中报道过。其次，我们给出了算法可能运行缓慢的复合族的特征，以及加速这些复合族的计算的启发式方法。我们还将上述算法扩展到启发式算法，以寻找多个分子的不连通的MCS，并将分子聚类成多个基团，每个基团共享一个实质性的MCS。我们的方法是灵活的，因为它们提供了对用于定义公共子结构的各种匹配标准的精细控制。
Several efficient correspondence graph-based algorithms for determining the maximum common substructure (MCS) of a pair of molecules have been published in the literature. The extension of the problem to three or more molecules is however nontrivial; heuristics used to increase the efficiency in the two-molecule case are either inapplicable to the many-molecule case or do not provide significant speedups. Our specific algorithmic contribution is two-fold. First, we show how the correspondence graph approach for the. two-molecule case can be generalized to obtain an algorithm that is guaranteed to find the optimum connected MCS of multiple molecules, and that runs fast on most families of molecules using a new divide-and-conquer strategy that has hitherto not been reported in this context. Second, we provide a characterization of those compound families for which the algorithm might run slowly, along with a heuristic for speeding up computations on these families. We also extend the above algorithm to a heuristic algorithm to find the disconnected MCS of multiple molecules and to an algorithm for clustering molecules into groups, with each group sharing a substantial MCS. Our methods are flexible in that they provide, exquisite control on various matching criteria used to define a common substructure.