Objects can be said to be structured when their representation also contains their parts. While OWL in general can describe structured objects, description graphs are a recent, decidable extension to OWL which support the description of classes of structured objects whose parts are related in complex ways. Classes of chemical entities such as molecules, ions and groups (parts of molecules) are often characterised by the way in which the constituent atoms of their instances are connected via chemical bonds. For chemoinformatics tools and applications, this internal structure is represented using chemical graphs. We here present a chemical knowledge base based on the standard chemical graph model using description graphs, OWL and rules. We include in our ontology chemical classes, groups, and molecules, together with their structures encoded as description graphs. We show how role-safe rules can be used to determine parthood between groups and molecules based on the graph structures and to determine basic chemical properties. Finally, we investigate the scalability of the technology used through the development of an automatic utility to convert standard chemical graphs into description graphs, and converting a large number of diverse graphs obtained from a publicly available chemical database.
Objects can be said to be structured when their representation also contains their parts. While OWL in general can describe structured objects, description graphs are a recent, decidable extension to OWL which support the description of classes of structured objects whose parts are related in complex ways [1{3].
Classes of chemical entities such as molecules, ions and groups (parts of
molecules) are often characterised by the way in which the constituent atoms of
their instances are connected via chemical bonds. For example, a cyclic
hydrocarbon such as benzene is characterised as six carbon atoms, each of which is
connected to two other carbon atoms in such a way that it forms a single
cycle (or ring). For various cheminformatics applications, chemical structures are
represented as chemical graphs, comprising of atoms as vertices and bonds as
edges. These can be encoded as connection tables [
A classic chemoinformatic application is chemical classi cation by
comparing all substructures such general descriptions are subsumed by more complex
and re ned substructures. The Web Ontology Language (OWL), as it currently
stands, is incapable of representing the required complex structures,
particularly cycles [
In this paper, we present a method for transforming chemical graphs into description graphs, and apply this method to create an OWL knowledge base of chemical entities enhanced with the structures of the chemical entities as description graphs. We will consider to what extent the formalism of description graphs, together with rules for expressing conditionality, supports the type of reasoning which domain experts would expect from a structure-enhanced chemical knowledge base, such as classi cation based on chemical structures, and determination of chemical properties based on the structures. Finally, we assess the scalability of the technology by evaluating the times taken to reason over knowledge bases of varying sizes. 2 2.1
OWL 2 [
A description graph is a directed graph G = (V; E; ) in which each vertex i 2 V is labeled with a set of (possibly negated) class names hii; and each edge hi; ji 2 E is labeled with a set of atomic properties hi; ji. Each description graph has a main class, which indicates the object whose structure is being modelled in the graph, and it is this main class that will be used to link to the remainder of the ontology that the description graph is a part of.
In order to preserve the decidability of reasoning, some important constraints
must be observed within a graph-enhanced knowledge base [
Thus chemical classi ciation must be expressed with rules. Further, these rules must be role-safe, that is, they must not refer simultaneously to properties used in the graphs and those used in the OWL ontology axioms.
A graph-extended OWL knowledge base is thus a 4-tuple K = (T; G; P; A) where T is a set of OWL class axioms, G is a set of description graphs, P is a set of rules, and A is a set of OWL assertions. T is allowed to refer only to tree properties, G and P are allowed to refer only to the graph properties, and A is allowed to refer to both graph and tree properties [1{3]. 2.2
At the molecular level, all of matter is composed of atoms of di erent kinds (such as Carbon and Oxygen) joined together through chemical bonds of di erent strengths. Covalent bonds (the strongest kind of chemical bond) join atoms together into composite units called molecules. Chemical entities are usually categorised into chemical classes by virtue of sharing common substructure or activity. An example of a chemical class is `carboxylic acids', which groups together all molecules that share the important carboxy functional group and therefore hold the disposition to behave similarly in certain chemical reactions involving that group.
The structure of a molecule is nicely represented by a chemical graph, which
describes the atomic connectivity within a molecule in terms of labelled nodes
for the atoms or groups within the molecule, and labelled edges for the (usually
covalent) bonds between the atoms or groups [
The purpose of our experiment is to evaluate the utility and scalability of
description graphs and rules for the representation of, and reasoning over,
chemical structures. The knowledge base6 consists of i) a simple ontology describing
classes pertaining to chemical entities, ii) auto-generated description graphs from
structures in the ChEBI database, and iii) rules for structure-based classi cation.
We used the HermiT [
Our evaluation criteria considers the following three aspects expected by domain experts: { Can chemical entities be classi ed based on their substructures? { Can basic chemical properties be determined from the description graphs? { How scalable is the resulting knowledge base? We now describe the structure of the implemented knowledge base. 3.1
At the root of the ontology is the node `chemical entity', beneath which are nodes for the primary division in kind of entity, namely `group', `atom', `molecule', and `ion'. `Atom' is further divided into the concrete types of atoms as per the periodic table, such as `carbon atom' and `oxygen atom'.
An illustration of the overall structure of the core terms of the ontology is shown in Figure 1. 3.2
Description graphs were automatically generated8 from a MOL le connection
table format [
Each description graph consists of a vertex for the description graph main class which is a subclass of `molecule' in the ontology, a vertex for each atom which is a subclass of the atom type e.g. `carbon atom' in the ontology, and a vertex for each bond which is a subclass of the bond type in the ontology e.g. `single'. Each atom vertex is connected to the molecule by the has atom property. Atom vertices are associated with bonds with has bond. Figure 2 shows an illustration of the description graph for cyclobutane. 6 Ontology availabe in two les, the main ontology at http://www.ebi.ac.uk/~hastings/owled2010/chemistry dgs ontology.owl and the graphs at http://www.ebi.ac.uk/~hastings/owled2010/chemistry dgs graphs.owl 7 Version 1.2.2 with slight customisation for input and output of graphs which is currently only partially supported by the HermiT library and the OWL API. 8 Our software for this experiment is available in source and binary at http://www.ebi.ac.uk/~hastings/owled2010/descgraphs.zip
The vertices (but not the properties) of the description graphs are also classi ed in the main OWL ontology. The main class is classi ed beneath `molecule' in the main ontology, the atoms beneath `atom' and the bonds beneath `bond'. We implemented rules to classify chemical structures based on their composition and their connectivity. Rules were devised for the classi cation of cyclic compounds, which contained a cycle of connected atoms.
For example, a rule to determine cycles of length three atoms is (slightly simpli ed for readability, the full generated version also includes DifferentFrom statements to ensure non-trivial cycles)
Rules were also devised to determine parthood between chemical structures. If all atoms of A are atoms of B, and all bonds of A are bonds of B, then A is a subgraph of B. The term group is commonly used to denote arbitrary chemical parts, while the terms molecule, ion and so on refer to entire (complete) structures. Rules were devised for each group so as to identify these groups in the molecule. However, a consequence of the strong separation requirement is that a single rule cannot refer to both graph properties and tree properties. For this reason, even if we determine that a given graph is a subgraph of another graph, we cannot assert a relationship such as has part between the two main classes at the ontology level. A workaround for this is to create a class for every group, such that if the group's structure is a subgraph of the molecule's structure, then the molecule can be classi ed as belonging to that class. Rules for parthood determination are of the form where M is an arbitrary individual of type molecule; A1 { An are group atoms; bonds exist between the group atoms Ai1 { Ain and Aj1 { Ajn, and Class is a class the identity of which depends on the group used to generated the rule, for example `carboxylic acid' for the `carboxy group'.
The properties used as the graph edges (has atom, has bond) are available for use in the rules, as long as a rule does not mix graph properties with properties used in OWL axioms in the main ontology.
In the next section, we present the results of reasoning over the knowledge base.
Reasoning with the rules over the combined knowledge base resulted in classication of description graph-enriched classes as cyclic molecules and as classes containing speci c de ned groups such as carboxylic acids9. We nd this result positive in terms of overcoming the previously explicit limitation of OWL knowledge bases in expressing arbitrarily structured objects at the class level and performing classi cation based on the structure.
However, we acknowledge that the types of conditionality that can be expressed in rules potentially provide the facility for only a limited set of chemical properties relative to those required by chemists. For example, it is di cult to express rules that must apply to all atoms from a given molecule's graph without speci cally naming those atoms, since there is no forAll operator in SWRL.
To evaluate the performance, we executed reasoning over iteratively increasing sizes of the knowledge base, both with and without rules. The results are summarised in Figure 310. We do not attempt to control the size of the graphs which we randomly selected for inclusion into our knowledge base, but note that the average size of a molecule in the ChEBI database is around 30 atoms11.
The scalability of the reasoner against the knowledge base enriched with desciption graphs appears workable, with reasoning time growing to a maximum of 23 minutes (1388 seconds) for a knowledge base enriched with 180 graphs. However, including the graphs alone { without rules { does not allow for any classi cation based on the information encoded in the graphs. The rules are this essential to expose the structure in the graphs to the reasoner. Unfortunately, we nd that reasoning over the knowledge base enriched with graphs and rules 9 The resulting inferred ontology is available at http://www.ebi.ac.uk/~hastings/owled2010/chemistry dgs inferred.owl 10 Tested on a Dell twin core laptop. 11 Excluding hydrogen atoms, which are commonly implicit, as these can be `added back' by calculations to determine their predicted positions. appears to grow very rapidly into unmanageable durations, with the highest duration that we recorded for a knowledge base enriched with 140 graphs taking four hours (14380 seconds) to classify. This scalability is a ected dramatically by the number and complexity of the generated rules, therefore this would appear to be a limiting factor in following our approach in a more complete fashion, where many chemical properties and subgraph relations might be reasonably expected to be included in the same knowledge base. 5
Our results have shown that it is possible to create a chemical knowledge base using OWL, description graphs and rules. The main strength of our approach is the direct encoding of complex structures at the class level in the ontology, and the encoding of rules for determining properties such as being cyclic, which are not able to be expressed as OWL axioms. We thereby show that this approach allows properties to be calculated by the reasoner rather than requiring these to be pre-computed and added to the asserted hierarchy of the ontology.
The main weaknesses are the limitations of rules for arbitrary property encoding and in particular the lack of quanti cation operators; and that there seems to be a scalability performance problem with using rules in this fashion. Pragmatically, the performance of the system was not where it would need to be to handle thousands or even millions of chemical graphs as are included in public databases. However, if ontologies are restricted to particular sub-domain areas of limited size, this might not be too much of a limitation.
Other approaches for partially including chemical structural information in
knowledge bases have been described in recent years. Armengol and Plaza (2005)
[
The ChEBI ontology is a well known ontology for chemical entities, providing
a deep classi cation according to the physical composition and chemical
structure of chemical entities. While containing an ever-growing number of chemical
entities, ChEBI is maintained entirely by hand, with no automated link
between the structure of the chemicals captured in the chemical database and the
structural de nition of ontology classes. As a result, the ChEBI database has
been able to grow at a much faster rate than the ChEBI ontology, with the
sizes currently12 at around 550000 for the database and 22000 for the ontology.
Chemical structures are exported into the ontology as annotations in the InChI
[
In 2007, Dumontier and Villaneuva-Rosales developed an OWL ontology for
the classi cation of chemical compounds based on the presence of speci ed
chemical functional groups [
Taking the desiderata of chemical ontology as the ability to center the knowledge base around an accurate representation of the structures of chemical entities, and to automatically determine the properties of chemical entities from those structures within the knowledge base, we nd that the description graphs and rules extensions to OWL are a big step forward on the standard OWL language for this purpose. 6
Our approach uses OWL, description graphs, and rules to implement a structureenriched knowledge base for chemicals with classi cation based on the chemical structures and rules. We see this work as a contribution to the evaluation of new OWL-related technology towards the requirements of the chemistry application domain.
Cheminformatics tools and techniques do already exist to detect chemical
properties and subgraphs / graph isomorphisms, and the CDK [
Next steps will be to investigate whether di erent representation strategies and/or rule implementations could alleviate the performance overhead in reasoning with the rules; to implement a system to allow visualisation of the chemical description graphs being created; to extend the rules to determine several additional chemical properties; and to investigate the incorporation of a `chemical datatype' into OWL based on InChI strings.
We acknowledge the detailed comments from three anonymous reviewers whose input helped to signi cantly improve the nal result. We further wish to acknowledge invaluable discussions and suggestions from Kirill Degtyarenko, Stefan Schulz, Colin Batchelor, and Birte Glimm. This work has been partially supported by the BBSRC, grant agreement number BB/G022747/1 within the \Bioinformatics and biological resources" fund.