.png){kind=icon}
返回
MultiMCS: A Fast Algorithm for the Maximum Common Substructure Problem on Multiple Molecules
.png){kind=icon}
PRE
AI
DOI：10.1021/ci100297y.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
INFORMATION
PROGRAM
GRAPHS
QSAR
期刊
IF:
5.3
论文数:
9.1K
被引数:
4.0W
机构
引用论文
PubChem: a public information system for analyzing bioactivities of small moleculesPubChem: 用于分析小分子生物活性的公共信息系统.png)
NUCLEIC ACIDS RESEARCH
OAAI
NUCLEIC ACIDS RESEARCHIF13.1
OAAI分享收藏分享收藏
查看更多内容