ASP Competition 2013: ChemicalClassification

Chemical Classification

Problem Description

We use logic programming (LP) rules with function symbols in the head to perform structure-based classification of molecular entities [1]. Initially, we deploy the chemical graph of a molecule with a set of LP skolemised existential rules. A fresh function symbol is used for each atom of the molecule. For example, consider the molecule of water which consists of one oxygen and two hydrogens that are connected through a single bond to the oxygen; water is represented with the following rules:

g_chebi_15377(X,f_chebi_15377_1(X),f_chebi_15377_2(X),f_chebi_15377_3(X)) :- chebi_15377(X).
h(Y1) :- g_chebi_15377(X,Y1,Y2,Y3).
o(Y2) :- g_chebi_15377(X,Y1,Y2,Y3).
h(Y3) :- g_chebi_15377(X,Y1,Y2,Y3).
hasAtom(X,Y1) :- g_chebi_15377(X,Y1,Y2,Y3).
hasAtom(X,Y2) :- g_chebi_15377(X,Y1,Y2,Y3).
hasAtom(X,Y3) :- g_chebi_15377(X,Y1,Y2,Y3).
single(Y1,X) :- g_chebi_15377(X,Y1,Y2,Y3).
single(X,Y1) :- g_chebi_15377(X,Y1,Y2,Y3).
single(Y1,Y2) :- g_chebi_15377(X,Y1,Y2,Y3).
single(Y2,Y1) :- g_chebi_15377(X,Y1,Y2,Y3).
molecule(X) :- chebi_15377(X).

We use the predicate symbol chebi_15377 instead of 'water', as 15377 is the id assigned to the water molecule in ChEBI ontology, which is where we extracted the chemical graphs from (http://www.ebi.ac.uk/chebi/searchId.do?chebiId=CHEBI%3A15377). We instantiate the short logic program above that describes water with the following fact:

chebi_15377(c_chebi_15377).

Subsequently, we use rules with negation-as-failure to derive superclasses of the molecules. For instance, the next rules capture the class of inorganic molecules:

carbonMolEntity(X) :- molecule(X), hasAtom(X,Y), c(Y).
inorganic(X) :- molecule(X), not carbonMolEntity(X).

One can use an LP engine to determine that inorganic(c_chebi_15377). is in the only stable model of the rules and the fact above and, thus, conclude that water is inorganic.

Predicates

Input format

Output format

Example(s)

The example contains the fact chebi_15377(c_chebi_15377). which will trigger the rule describing the molecule of water and, then, the rules defining chemical classes. The produced stable model is:

g_chebi_15377(c_chebi_15377, f_chebi_15377_1(c_chebi_15377), f_chebi_15377_2(c_chebi_15377), f_chebi_15377_3(c_chebi_15377)), chebi_15377(c_chebi_15377), molecule(c_chebi_15377), h(f_chebi_15377_1(c_chebi_15377)),  h(f_chebi_15377_3(c_chebi_15377)), o(f_chebi_15377_2(c_chebi_15377)), hasAtom(c_chebi_15377, f_chebi_15377_1(c_chebi_15377)), hasAtom(c_chebi_15377, f_chebi_15377_2(c_chebi_15377)), hasAtom(c_chebi_15377, f_chebi_15377_3(c_chebi_15377)), single(f_chebi_15377_1(c_chebi_15377), f_chebi_15377_2(c_chebi_15377)), single(f_chebi_15377_2(c_chebi_15377),f_chebi_15377_1(c_chebi_15377)), single(f_chebi_15377_2(c_chebi_15377), f_chebi_15377_3(c_chebi_15377)), single(f_chebi_15377_3(c_chebi_15377), f_chebi_15377_2(c_chebi_15377)), bond(f_chebi_15377_1(c_chebi_15377),f_chebi_15377_2(c_chebi_15377)), bond(f_chebi_15377_2(c_chebi_15377), f_chebi_15377_1(c_chebi_15377)), bond(f_chebi_15377_2(c_chebi_15377), f_chebi_15377_3(c_chebi_15377)), bond(f_chebi_15377_3(c_chebi_15377), f_chebi_15377_2(c_chebi_15377)), horc(f_chebi_15377_1(c_chebi_15377)), horc(f_chebi_15377_3(c_chebi_15377)), midOxygen(f_chebi_15377_2(c_chebi_15377)), bondAtLeast1(f_chebi_15377_1(c_chebi_15377)), bondAtLeast1(f_chebi_15377_2(c_chebi_15377)), bondAtLeast1(f_chebi_15377_3(c_chebi_15377)), bondAtLeast2(f_chebi_15377_2(c_chebi_15377)), bondExactly2(f_chebi_15377_2(c_chebi_15377)), bond1to3(f_chebi_15377_1(c_chebi_15377)), bond1to3(f_chebi_15377_2(c_chebi_15377)), bond1to3(f_chebi_15377_3(c_chebi_15377)), chalcogenMolEntity(c_chebi_15377), oxygenMolEntity(c_chebi_15377), hydrogenMolEntity(c_chebi_15377), inorganic(c_chebi_15377), notHydroCarbon(c_chebi_15377), notHaloHydroCarbon(c_chebi_15377), polyatomic(c_chebi_15377), cleanReachable(f_chebi_15377_1(c_chebi_15377), f_chebi_15377_2(c_chebi_15377), f_chebi_15377_3(c_chebi_15377)), cleanReachable(f_chebi_15377_3(c_chebi_15377), f_chebi_15377_2(c_chebi_15377), f_chebi_15377_1(c_chebi_15377))

From the above model, one can conclude that water is a chalcogen, oxygen, hydrogen, inorganic and polyatomic molecular entity.

Additional sample instances: download

Problem Peculiarities

Type: Search Competition: System Track

Inspite of the fact that the said rules contain function symbols in the head, computation of the model (i.e., chase) is guaranteed to terminate because we have carried out a suitable acyclicity check. For the employed acyclicity condition (see [2] for technical details), reasoning over acyclic datalog programs with existentials in the head is in 2EXPTIME. However, for the use case specified in this submission and because the function nesting level is at most one, reasoning is polynomial in l and m and exponential in n, where l, m and n are bounds on the number of molecules, the number of different predicates used and the size of the molecules, respectively.

Computation time: The current use case has not been previously submitted to the ASP competition. We used DLV on a computer with 3.7 GB of RAM, IntelCoreTM 2 Quad Processors running at 2.5 GHz and 64 bit Linux to calculate the stable model for each of the fifty instances that we provide. The time measurements for six of the instances are as follows:


Instance

Time in secs

1-chemclass-0-1.asp

16.429

10-chemclass-0-1.asp

24.389

20-chemclass-0-1.asp

53.647

30-chemclass-0-1.asp

92.077

40-chemclass-0-1.asp

145.105

50-chemclass-0-1.asp

242.933

The above performance results indicate that the problem is neither trivial nor too hard. Each instance file contains facts that trigger the molecule-describing rule. The encoding file contains rules that represent 700 molecules and the rules that encode the chemical classes. The parameter that varies for each instance is the number of the molecules that are represented via the occurrence of the relevant facts; each instance with name i-chemclass-0-1.asp represents i*14 molecules, where 1 <= i <= 50.

Notes and Updates

Author(s)

References

[1] Despoina Magka, Boris Motik and Ian Horrocks. Modelling Structured Domains Using Description Graphs and Logic Programming. In Proceedings of the 9th Extended Semantic Web Conference (ESWC 2012), Vol. 7295, Pages 330-344, Springer, 2012.

[2] Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik and Zhe Wang Acyclicity Conditions and their Application to Query Answering in Description Logics. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), AAAI Press, 2012.

ASP Competition 2013: ChemicalClassification (last edited 2012-11-20 22:16:30 by PatrikSchneider)