Towards a Logical Analysis of Biochemical Reactions
Patrick Doherty and Steve Kertes and Martin Magnusson and Andrzej Szalas1
Abstract.
We provide a logical model of biochemical reactions and showhow hypothesis generation using weakest sufficient and strongest
necessary conditions may be used to provide additional informationin the context of an incomplete model of metabolic pathways.

1

A Logical Model for the Analysis of BiochemicalReactions

The analysis of biochemical pathways has been considered in numerous papers (see, e.g., [1, 2]). In this paper, a bipartite graph representation of chemical reactions will be used (see, e.g., [2]).
It is assumed that any reaction is specified by:α(n)n : c1 + . . . + ck −→ c01 + . . . + c0l ,1. constants and variables:0• constants naming reactions (n, n ), compounds (c, c , h2o, co2etc.), and reaction nodes (r, r0 )• variables representing reactions (N, N 0 ), compounds (C, C 0 ),and reaction nodes (R, R0 )for constants and variables we also use indices, when necessary
2. relation symbols reflecting static information:• in(C, N ) meaning that compound C is needed for reaction N• out(N, C) meaning that compound C is a product of reaction N3. relation symbols reflecting dynamic information:• prec(R, R0 ) meaning that reaction node R precedes reaction
node R0• chain(R, R0 ) meaning that there is a chain of reactions
R, R1 , R2 , . . . , Rk , R0 such that prec(R, R1 ), prec(R1 , R2 ),. . . ,prec(Rk−1 , Rk ), prec(Rk , R0 )• react(N, R) meaning that reaction N actually happened in reaction node R• av(C, R) meaning that compound C is available for reaction
represented by reaction node R.
1 Department of Computer and Information Science, SE-581 83 Linköping,Sweden, email: {patdo,g-steke,marma,andsz}@ida.liu.se• static information about reaction n:in(c1 , n) ∧ . . . ∧ in(ck , n)∧out(n, c01 ) ∧ . . . ∧ out(n, c0l )• linking nodes in graphs with reactions
react(n, R) →(1)where n is a label (name) of the reaction, c1 , . . . , ck are reactants(inputs for n), c01 , . . . , c0l are products of n and α(n) is a formulathat specifies additional conditions necessary for the reaction, suchas temperature, pressure, presence of catalyzers, etc.
In this paper, the classical first-order logic is used for specifying
reactions. Reaction nodes will be represented explicitly, while information about available compounds will be given via a suitable relation. Consequently, it is assumed that the following symbols areavailable:
0Let e, t be any expressions and s any subexpression of e. Bye(s/t) we shall mean the expression obtained from e by substituting each occurrence of s by t.
It is assumed that any formula is implicitly universally quantified
over all its variables that are not bound by a quantifier.
Any reaction of the form (1) is translated into the formula
react(n, R), where the following background theory is assumed:(2)α(n/R)∧
av(c1 , R) ∧ . . . ∧ av(ck , R)∧∀R0 . {prec(R, R0 ) → av(c01 , R0 )}∧...∧∀R0 . {prec(R, R0 ) → av(c0l , R0 )}.

2Hypotheses Generation Using Strongest
Necessary and Weakest Sufficient Conditions

Snc’s and wsc’s (see e.g. [5] for a definition) provide a powerfulmeans of generating hypotheses using abduction. Suppose one isgiven a (incomplete) specification of a set of interacting reactionsof the form shown in equation (1). We would use this set of formulas
as the background theory T . Suppose additionally, that a number ofobservations are made referring to reactions known to have occurred,or compounds known to be available for participation in a reaction,etc. Let α denote the formula representing these observations. Generally, it will not be the case that T |= α because T only provides anincomplete specification of the reactions.
We would like to generate a formula (candidate hypotheses) φ in a
restricted subset of the language of reactions P such that φ together
with the background theory T does entail the observations α. It is
important that we do not over commit otherwise we could just as
easily choose α itself as the hypothesis which wouldn’t do much
good. In fact, the W SC(α; T ; P ) does just the right thing since weknow that T ∧W SC(α; T ; P ) |= α and it is the weakest such formulaby definition.
W SC(α; T ; P ) actually represents alternative hypotheses for explaining α. If it is put in disjunctive normal form, each of the disjuncts makes W SC(α; T ; P ) true and represents a weakest hypothesis. To reason about what each candidate hypothesis might imply in terms of completing the reaction representation, one can add
both the background theory T and the candidate hypothesis α0 to alogic database and query the database as desired. For this purposethe approximate databases described in [3] are a suitable alternativethat enables reasoning about incomplete and approximate knowledge
through the use of rough set techniques.
Observe that:• wsc corresponds to a weakest abduction expressed in a given target language. For example, consider
W SC(av(f in, so3); T h; L),
where T h is the theory expressing properties of given reactions,as constructed in Section 1. Then
– if the target language L consists of av only, the resulting wsc
expresses what compound’s availability makes the required
output of reaction node f in feasible– if the target language consists of react, then the resulting wsc
expresses reactions necessary to make the required output off in feasible• snc allows one to infer facts from negative information. In fact, snc
expresses what would be possible under a given set of hypotheses.
For example, if a certain side product has not been observed, areaction can be excluded from the set of hypotheses.
The wsc’s and snc’s can be calculated efficiently for a large classof formulas by expressing them as second-order formulas, using anequivalence proved in [5], and obtaining logically equivalent firstorder formulas by applying the D LS∗ algorithm described, e.g.,in [4].

3

A Metabolic Pathway Example

Consider a fragment of the aromatic amino acid pathway of yeast,shown in Figure 1 (this is a fragment of a larger structure used in [1]).
In the graph there are two types of nodes: compound nodes (depicted by circles) and reaction nodes (depicted by rectangles). An
edge from a compound node to a reaction node denotes a substrate.
An edge from a reaction node to a compound node denotes a productof the reaction. We additionally allow conditions placed in the boxes
and in this case rectangles are labelled with enzyme names, meaningthat a respective enzyme is to be available for reaction, i.e., that avholds. For example, av(ydr127w, r) is necessary, when the label ofr is “YDR127W”.
C02652

C00006

1-q
1 YDR127W

C00493

C00005- YDR127W*? RC00002 C03175¾
YGL148W?

?

C01269¾

YDR127W+?

C00009 C00251

C00008C00009IC00074

Figure 1. A fragment of the aromatic amino acid pathway of yeast.

Figure 1 depicts the following reactions:n1 : C02652 + C00005

YDR127W−→

C00006 + C00493

n3 : C03175 + C00074

YDR127W

C01269 + C00009

n4 : C01269

YGL148W−→−→

C00009 + C00251.

It is assumed that reaction
n2 : C00493 + C00002

YDR127W−→

C03175 + C00008

depicted by the dashed box is, in fact, missing.
The above set of reactions is expressed by formulas as defined inSection 1. For example, the first reaction is expressed by:react(n1 , R) →av(ydr127w, R)∧av(c02652, R) ∧ av(c00005, R)∧∀R0 . [prec(R, R0 ) → av(c00006, R0 )]∧∀R0 . [prec(R, R0 ) → av(c00493, R0 )].
The missing reaction is also present, among many other reactions, inthe database, and is expressed by:react(n1 , R) →av(ydr127w, R)∧av(c00493, R) ∧ av(c00002, R)∧∀R0 . [prec(R, R0 ) → av(c03175, R0 )]∧∀R0 . [prec(R, R0 ) → av(c00008, R0 )].
We assume that the underlying database contains partial information
about the observed chain of reactions:react(n1 , r1 ) ∧ react(n3 , r3 ) ∧ react(n4 , r4 )together with a description of reactions n1 , n3 , n4 and many other reactions, including n3 . Let the considered knowledge base be denoted
by K DB.
We can now consider, e.g., W SC(α; K DB; av), wheredefα ≡ ∃N.[react(N, r2 ) ∧ prec(r1 , r2 ) ∧ prec(r2 , r3 )],providing one with the weakest requirement expressed in terms of av
only, making α true, provided that the background theory given by
K DB holds.
In our case, the generated hypotheses will contain the disjunctav+ (c00002, r2 ), reflecting, among others, sufficient conditions forprec. The S NC(α; K DB;{out}) will contain the disjunctout+ (N, c03175) ∧ out+ (N, c00008),
reflecting, among others, necessary conditions for prec. If one of
the compounds c03175, c00008 has not been observed during thereaction chain, one can reject the hypothesis that reaction N in noder2 was n2 .

REFERENCES[1] C.H. Bryant, S.H. Muggleton, S.G. Oliver, D.B. Kell, P. Reiser, andR.D. King, ‘Combining inductive logic programming, active learningand robotics to discover the function of genes’, Linkoping Electronic Articles in Computer and Information Science, 6(12), (2001).
[2] Y. Deville, D. Gilbert, J. van Helden, and S. Wodak, ‘An overview of data
models for the analysis of biochemical pathways’, Briefings in Bioinformatics, 4(3), 246–259, (2003).
[3] P. Doherty, J. Kachniarz, and A. Szałas, ‘Using contextually closed
queries for local closed-world reasoning in rough knowledge databases’,in Rough-Neuro Computing: Techniques for Computing with Words, eds.,S.K. Pal, L. Polkowski, and A. Skowron, Cognitive Technologies, pp.
219–250. Springer–Verlag, (2003).
[4] P. Doherty, W. Łukaszewicz, and A. Szałas, ‘Computing circumscription
revisited’, Journal of Automated Reasoning, 18(3), 297–336, (1997).
[5] P. Doherty, W. Łukaszewicz, and A. Szałas, ‘Computing strongest necessary and weakest sufficient conditions of first-order formulas’, International Joint Conference on AI (IJCAI’2001), 145 – 151, (2000).