Substructure search (SSS) is a method to retrieve from a database only those chemicals matching a pattern of atoms and bonds which a user specifies. It is an application of graph theory, specifically subgraph matching in which the query is a hydrogen-depleted molecular graph. The mathematical foundations for the method were laid in the 1870s, when it was suggested that chemical structure drawings were equivalent to graphs with atoms as vertices and bonds as edges. SSS is now a standard part of cheminformatics and is widely used by pharmaceutical chemists in drug discovery. There are many commercial systems that provide SSS, typically having a graphical user interface and chemical drawing software. Large publicly available databases like PubChem and ChemSpider can be searched this way, as can Wikipedia's articles describing individual chemicals.
Definitions Substructure search is used to retrieve from a database of chemicals those which contain the pattern of atoms and bonds specified by a user. It is implemented using a specialist type of query language and in real-world applications the search may be further constrained using logical operators on additional data held in the database. Thus "return all carboxylic acids where a sample of >1 g is available". One definition of "substructure" was provided in 2008: "given two chemical structures A and B, if structure A is fully contained in structure B, then A is a substructure of B, while B is a superstructure of A."
In this definition, the word "structure" is not synonymous with "compound". If it were, the structure for ethanol, CH3CH2OH would not be a substructure of propanol, CH3CH2CH2OH, since the terminal CH3 of ethanol is not fully contained at the propanol chain two atoms away from the OH group. Instead the query structure is, formally, a hydrogen-depleted molecular graph. The search is thus for substances which contain three atoms and two single bonds connected as C–C–O. Propanol is a "hit", as is diethyl ether, with C–C–O–C–C. If a user wished to limit the hits to alcohols, then the query structure would have to be drawn with an "explicit hydrogen", as C–C–O–H and ether would no longer match. In mathematical terms, finding substructures is an application of graph theory, specifically subgraph matching.
Examples Standard conventions used when chemists draw chemical structures need to be considered when implementing substructure search. Historically, the representation of tautomer forms and stereochemistry has posed difficulties. This can be illustrated using histidine.
The top row shows the standard two-dimensional chemical drawing for (S)-histidine (the natural isomer of this amino acid), its enantiomer (R)-histidine and a drawing which conventionally indicates the racemic mixture of equal amounts of the R and S forms. The bottom row shows the same three compounds with the imidazole ring drawn in its alternative tautomer form. For histidine, it has been experimentally determined by 15N NMR spectroscopy that the 1-H tautomer is preferred over the 3-H form in samples. Choice of representation for storage in a database can influence substucture searches. All six drawings are hits for a propanol substructure C–C–C–O, as shown in red. However, only the top row would, apparently, be a hit for the blue substructure of 1-H imidazole-4-methyl, as this is not fully contained in the other three compounds. In fact, each vertical pair is the same chemical substance: tautomers in general cannot be isolated as separate samples. In modern databases, substances are held in a single canonical form, with checks made for uniqueness. The InChIKey provides one way to do this. (S)-Histidine's standard key is HNDVDQJCIGZPNO-YFKPBYRVSA-N, (R)-histidine's key is HNDVDQJCIGZPNO-RXMQYKEDSA-N and (RS)-histidine's is HNDVDQJCIGZPNO-UHFFFAOYSA-N. The first block of 14 letters is identical for all these substances, as it encodes the molecular graph.
Query interfaces and search algorithms Most substructure search systems present the user with a graphical user interface with a chemical structure drawing component. Query structures may contain bonding patterns such as "single/aromatic" or "any" to provide flexibility. Similarly, the vertices which in an actual compound would be a specific atom may be replaced with an atom list in the query. Cis–trans isomerism at double bonds is catered for by giving a choice of retrieving only the E form, the Z form, or both. The algorithms for searching are computationally intensive, often of O (n3) or O (n4) time complexity (where n is the number of atoms involved) but the problem is known to be NP-complete. Speedups are achieved using fragment screening as a first step. This pre-computation typically involves creation of bitstrings representing presence or absence of molecular fragments. Target compounds that do not possess the fragments present in the query cannot be hits and are eliminated. Atom-by-atom-searching, in which a mapping of the query's atoms and bonds with the target molecule is sought, is usually done with a variant of the Ullman algorithm.
Implementations As of 2024, substructure search is a standard feature in chemical databases accessible via the web. Large databases such as PubChem, maintained by the National Center for Biotechnology Information and ChemSpider, maintained by the Royal Society of Chemistry have graphical interfaces for search. The Chemical Abstracts Service, a division of the American Chemical Society, provides tools to search the chemical literature and Reaxys supplied by Elsevier covers both chemicals and reaction information, including that originally held in the Beilstein database. PATENTSCOPE maintained by the World Intellectual Property Organization makes chemical patents accessible by substructure and Wikipedia's articles describing individual chemicals can also be searched that way. Suppliers of chemicals as synthesis intermediates or for high-throughput screening routinely provide search interfaces. Currently, the largest database that can be freely searched by the public is the ZINC database, which is claimed to contain over 37 billion commercially available molecules.
History
… excerpt ends here. Continue reading the full article.
