Premium
Comparison of Maximum Common Subgraph Isomorphism Algorithms for the Alignment of 2D Chemical Structures
Author(s) -
Duesbury Edmund,
Holliday John,
Willett Peter
Publication year - 2018
Publication title -
chemmedchem
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.817
H-Index - 100
eISSN - 1860-7187
pISSN - 1860-7179
DOI - 10.1002/cmdc.201700482
Subject(s) - subgraph isomorphism problem , isomorphism (crystallography) , induced subgraph isomorphism problem , algorithm , computer science , chemistry , theoretical computer science , crystallography , crystal structure , graph , voltage graph , line graph
The identification of the largest substructure in common when two (or more) molecules are overlaid is important for several applications in chemoinformatics, and can be implemented using a maximum common subgraph (MCS) algorithm. Many such algorithms have been reported, and it is important to know which are likely to be the useful in operation. A detailed comparison was hence conducted of the efficiency (in terms of CPU time) and the effectiveness (in terms of the size of the MCS identified) of eleven MCS algorithms, some of which were exact and some of which were approximate in character. The algorithms were used to identify both connected and disconnected MCSs on a range of pairs of molecules. The fastest exact algorithms for the connected and disconnected problems were found to be the fMCS and MaxCliqueSeq algorithms, respectively, while the ChemAxon_MCS algorithm was the fastest approximate algorithm for both types of problem.