This Title All WIREs
How to cite this WIREs title:
WIREs Comput Mol Sci
Impact Factor: 16.778

Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review

Full article on Wiley Online Library:   HTML PDF

Can't access this content? Tell your librarian.

Abstract The intuitive description of small and large molecules using graphs has led to an increasing interest in the application of graph concepts for describing, analyzing, and comparing small molecules as well as proteins. Graph theory is a well‐studied field and many applications are present in various scientific disciplines. Recent literature describes a number of successful applications to biological problems. One of the most applied concepts aims at finding a maximal common subgraph (MCS) isomorphism between two graphs. We review exact MCS algorithms, especially designed for graphs obtained from small and large molecules, and give an overview of their successful applications. © 2011 John Wiley & Sons, Ltd. WIREs Comput Mol Sci 2011 1 68–79 DOI: 10.1002/wcms.5 This article is categorized under: Structure and Mechanism > Molecular Structures Computer and Information Science > Chemoinformatics Computer and Information Science > Computer Algorithms and Programming

Maximal common induced subgraph (MCIS) versus maximal common edge subgraph (MCES). (a) Molecular graph of decalin (labels not shown). (b) Molecular graph of cyclodecane (labels not shown). (c) MCIS of (a) and (b). (d) MCES of (a) and (b).

[ Normal View | Magnified View ]

Backtracking search tree for 1,3,4‐oxadiazole and 1,3,4‐thiadiazole as shown in Figure 5(a) and (b). One solution is highlighted. Cut branches are shown in gray.

[ Normal View | Magnified View ]

Maximal clique in a compatibility graph. (a) Molecular graph of 1,3,4‐oxadiazole. (b) Molecular graph of 1,3,4‐thiadiazole. (c) Compatibility graph of (a) and (b). The graph has two maximal cliques indicated with red and black lines. (d) Maximal common subgraph (MCS) of 1,3,4‐oxadiazole and 1,3,4‐thiadiazole. Both cliques resemble the same MCS.

[ Normal View | Magnified View ]

Line graphs. Panels (a) and (b) show the molecular graph of cyclopentanone and epoxycylopentane. The highlighted subgraphs in (a) and (b) become topological equivalent in the corresponding line graphs (c) and (d). A differentiation is only possible by their vertex and edge labels.

[ Normal View | Magnified View ]

Classification of maximal common subgraph (MCS) algorithms.

[ Normal View | Magnified View ]

Connected versus disconnected maximal common subgraph (MCS). (a) Connected MCS (red). (b) Disconnected MCS (red).

[ Normal View | Magnified View ]

Browse by Topic

Computer and Information Science > Computer Algorithms and Programming
Computer and Information Science > Chemoinformatics
Structure and Mechanism > Molecular Structures

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts