Editing Subgraph isomorphism problem (section)

==Applications==
As subgraph isomorphism has been applied in the area of [[cheminformatics]] to find similarities between chemical compounds from their structural formula; often in this area the term [[substructure search]] is used.<ref>{{harvtxt|Ullmann|1976}}</ref> A query structure is often defined graphically using a [[structure editor]] program; [[SMILES]] based database systems typically define queries using [[Smiles arbitrary target specification|SMARTS]], a [[SMILES]] extension.

The closely related problem of counting the number of isomorphic copies of a graph ''H'' in a larger graph ''G'' has been applied to pattern discovery in databases,<ref>{{harvtxt|Kuramochi|Karypis|2001}}.</ref> the [[bioinformatics]] of protein-protein interaction networks,<ref>{{harvtxt|Pržulj|Corneil|Jurisica|2006}}.</ref> and in [[exponential random graph]] methods for mathematically modeling [[social network]]s.<ref>{{harvtxt|Snijders|Pattison|Robins|Handcock|2006}}.</ref>

{{harvtxt|Ohlrich|Ebeling|Ginting|Sather|1993}} describe an application of subgraph isomorphism in the [[computer-aided design]] of [[electronic circuits]]. Subgraph matching is also a substep in [[graph rewriting]] (the most runtime-intensive), and thus offered by [[Graph rewriting#Implementations and applications|graph rewrite tools]].

The problem is also of interest in [[artificial intelligence]], where it is considered part of an array of [[pattern matching]] in graphs problems; an extension of subgraph isomorphism known as [[structure mining|graph mining]] is also of interest in that area.<ref>http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; expanded version at https://e-reports-ext.llnl.gov/pdf/332302.pdf</ref>