Previous works
A finer logic modelingResults and further

Kinetic Models and Qualitative
Abstraction for Relational Learning
in Systems Biology
Gabriel Synnaeve,
Katsumi Inoue, Andrei Doncescu, Taisuke Sato
Yoshitaka Kameya, Masakazu Ishihata, Hidetomo
Nabeshima2009 internship at NII (Tokyo),
now at E-Motion@INRIA / Collège de France (Paris)

January 27, 2011
1/29

Previous works
A finer logic modelingResults and further

Introduction

Problems: exploit experimental data, learn what rules
the cell.

Method: discretize metabolites concentration,
combine with existing pathways structures, use
kinetic models with inductive logic programming.

2/29

Previous works
A finer logic modelingResults and further

1

Previous works
Metabolic Pathways
Inductive Logic Programming
Bibliography

2

A finer logic modeling
The trap
Kinetic modeling
Implementation

3

Results and further
Ranked Results
Where next?

3/29

Previous works
A finer logic modelingResults and further

1

Previous works
Metabolic Pathways
Inductive Logic Programming
Bibliography

2

A finer logic modeling
The trap
Kinetic modeling
Implementation

3

Results and further
Ranked Results
Where next?

3/29Previous works
A finer logic modelingResults and further

1

Previous works
Metabolic Pathways
Inductive Logic Programming
Bibliography

2

A finer logic modeling
The trap
Kinetic modeling
Implementation

3

Results and further
Ranked Results
Where next?

3/29

Previous works
A finer logic modelingResults and further

Metabolic Pathways
Inductive Logic Programming
Bibliography(Metabolic) Pathways

Graphs of interconnectedreactionsGlucose enters ATP ⇒ADP
G6P
Chain of reactions to takeenergy and store it in
ATP/NADH (2 per moleculeof Glucose)
Acetyl CoA is at the originof the Krebs cycle (part ofcellular respiration)
4/29

Previous works
A finer logic modelingResults and further

Metabolic Pathways
Inductive Logic Programming
Bibliography

Glycolysis and Pentose Phosphate of E. Coli

glucosepg6

ribu5p

rib5p

g6p

xyl5p

sed7p

f6p
cell membrane
dhap

fdp

gap

pg3

pep

pyr

accoa

5/29

Previous works
A finer logic modelingResults and further

Metabolic Pathways
Inductive Logic Programming
Bibliography

Abduction & Induction
ILP strength lies in the fact that learnt rules/clauses are
directly useable in a logical program.
Induction & Abduction
From Background Knowledge ∧ Examples
 Find Hypotheses satisfying B ∧ H |= E and B ∪ H 2 ⊥Abduction: ground (or ∃ quant.) formulaes, directcauses of observations that are called explanations.
Induction: universally (∀) quantified formulaes (smallB), more general hypotheses.
R. J. Mooney: Integrating abduction and induction in machinelearning. IJCAI97 Workshop on Abduction and Induction in AI,
37–42 (1997).
Flach P. A., Kakas A. C.: Abduction and induction: Essays on
their relation and integration. Kluwer (2000).
6/29

Previous worksA finer logic modelingResults and furtherMetabolic Pathways
Inductive Logic Programming
Bibliography

Inverse Entailment (Consequence Finding)
ILP is interested in the formulas derived from B ∧ ¬E
that are not derived from B alone.
Inverse Entailment
The previous definition is equivalent to B ∧ ¬E |= ¬H
and B 2 ¬H.
We can then use a consequence finding procedure(resolution, tableaux) to find ¬H (SOLAR).
Inoue, K.: Linear resolution for consequence finding. Artificial
Intelligence 56:301-353 (1992).
Inoue K.: Induction as consequence finding. Machine Learning,
55:109–135 (2004).
Nabeshima H., Iwanuma K., and Inoue K.: SOLAR: A
Consequence Finding System for Advanced Reasoning.
TABLEAUX 2003, LNAI, Vol. 2796, pp. 257-263, Springer (2003).
7/29

Previous works
A finer logic modelingResults and further

Metabolic Pathways
Inductive Logic Programming
Bibliography

New age began there

The point for automatic qualitative reasoning
through ILP has been made.
King, R., Whelan, K., Jones, F., Reiser, P., Bryant, C., Muggleton, S., Kell, D., and Olivier, S. (2004). Functional genomic
hypothesis generation and experimentation by a robot
scientist. Nature, 427:247–252.
King, R., Garrett, S., and Coghill, G. (2005). On the use ofqualitative reasoning to simulate and identify metabolicpathways. Bioinformatics, 21(9):2017–2026.

8/29

Previous works
A finer logic modelingResults and further

Metabolic Pathways
Inductive Logic Programming
Bibliography

Inhibitionary effect of toxins

Metabolic flux analysis through induction: rulesthat explain the concentration changes (up or down)
between 2 experiments, with and w/o toxin.
Doncescu, A., Inoue K., Yamamoto Y.: Knowledge Based
Discovery in Systems Biology Using CF-Induction. LNCS N.4570,
pages 395-404 (2007).

9/29

Previous works
A finer logic modelingResults and further

Metabolic Pathways
Inductive Logic Programming
Bibliography

Dealing with kinetics?
Main complete models use ordinary differentialequations.
Temporal logic combined with stochastic logic
programming ⇒ kinetic models.
Franco R. and Canela E.: Computer simulation of purine
metabolism. Eu- ropean Journal of Biochemistry, 144:305-315(1984).
Fages, F., Soliman, S., and France, I. R. (2008). Model revisionfrom temporal logic properties in systems biology. In:
Probabilistic Inductive Logic Programming. LNAI, volume 4911,
pages 287–304.

10/29

Previous works
A finer logic modelingResults and further

Metabolic Pathways
Inductive Logic Programming
Bibliography

Limits of The Previous Models
No models for dynamic transitions

just up (↑) / down (↓)

Not enough information to be precise enough:M1 ?
M2 ↓R1?

•R2

M3 ↑/R3M4 ↓• : not inhibited/ : inhibited

11/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Various levels just up (↑) / down (↓)

Dealing With More Knowledge

M1 ?
M2 ↓

M1 ↓⇓
M2 ↓R1?

•M3 ↑R2M4 ↓• : not inhibited/ : inhibited

R1•
•

/R3

M3

R2

↓⇓ : down OR big_down⇑/R3M4 ↓⇓ <↓<↑<⇑
12/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Be More Precise but Avoid Overfitting

currently
evolution
Generalization

ErrorsLearning

Complexity of the Hypothesis space

13/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Michaelis-Menten Kinetics
Speed of a one-way reactionv = #{products per second per mole of the enzyme}
d[S]
d[P]
sS → pP ⇒ v = − 1s dt = 1p dt

14/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Simplification of Michaelis-Menten Equation
kE + S k1−1 ES →k2 E + P
d[P]Michaelis − Menten equation :d[P]dt−→disc.time(1) and (2) =⇒ Vm

dt= Vm[S][S] + Km[P]T+timestep − [P]T(T + timestep) − T[S]T[S]T + Km≈

(1)

(2)

[P]T+timestep − [P]T(T + timestep) − T

We chose to work with a constant timestep :=⇒ [P]T+1 = Vm

[S]T[S]T + Km+ [P]T (3)15/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Additional work and tools

kegg2symb

KEGG

Symbolic
pathway
SOLAR

Hypotheses

Conversion

Experimental
Datapy-tsdisc

Discretizeddata
BDD-EM

HUP
Discretization: append

Rules, here akinetic model

Michaelis-Menten

Rankedhypotheses

16/29

Previous works
A finer logic modelingResults and further

The trapKinetic modeling
Implementation

HUP: HMM Utility Program
Clustering method that uses
Continuous Hidden Markov Model +Bayesian Score:# time, value
0, 100.1, 40.2, 1

HUP

KEGG

kegg2symb

Symbolic
pathwaypy-tsdisc

Discretized
data

SOLAR

Hypotheses

Conversion

Experimental
Data

BDD-EM
HUP
Discretization: append

Rules, here akinetic model

Rankedhypotheses### levels
21017/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Wrapping HUP
KEGG

kegg2symb

Symbolic
pathwaypy-tsdisc

Discretizeddata

SOLAR

Hypotheses

Conversion

Experimental
Data

BDD-EM
HUP
Discretization: append# time, C(A), C(B)0, 10, 2
0.1, 6, 4
0.2, 5, 5

options

Rankedhypotheses

12 metabolites

prepareconc(A, 3, 0)conc(B, 1, 0)conc(A, 2, 1)conc(B, 2, 1)

3 time steps

3000 time samples

12 metabolites

Rules, here akinetic model

12*3 = 36 "conc" predicates

HUP

18/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Logical Kinetic Modelingkegg2symb

KEGG

Symbolicpathway
SOLAR

Hypotheses

Conversion

ExperimentalData

py-tsdisc

Discretizeddata
BDD-EM

HUP: append

Rules, here akinetic model

Michaelis-Menten

Rankedhypotheses

Approximations for extreme values in:[P]T+1 = Vm

[S]T[S]T + Km+ [P]T

19/29

Previous works
A finer logic modelingResults and further

The trap
Kinetic modeling
Implementation

Logical Kinetic Modeling (rules)[S]  Km
reaction(S, P, Km) ∧ concentration(S, 0, 0) ∧concentration (Km, 2, 0) ∧ concentration(P, L, 0) →concentration(P, L, 1)[S] ' Km
reaction(S, P, Km) ∧ concentration(S, 1, 0) ∧concentration(Km, 1, 0) ∧ concentration(P, L, 0) →concentration(P, L, 1)[S]  Km
reaction(S, P, Km) ∧ concentration(S, 2, 0) ∧concentration(Km, 0, 0) → concentration(P, 2, 1)

20/29

Previous works
A finer logic modelingResults and further

Ranked Results
Where next?

Data-centric schema

kegg2symb

KEGG

Symbolic
pathway
SOLAR

Hypotheses

Conversion

Experimental
Datapy-tsdisc

Discretizeddata
BDD-EM

HUP
Discretization: append

Rules, here akinetic model

Michaelis-MentenRanked
hypotheses

21/29

Previous works
A finer logic modelingResults and furtherRanked Results
Where next?

Inputs
Structure of the pathway(s) + Background knowledge(MM) + Metabolites concentrations

22/29

Previous works
A finer logic modelingResults and further

Ranked Results
Where next?

Ranking the hypotheses with BDD-EM
Hyp. no.
H130
H392
H216
H196
H356
H94

Probability≈ 1.0
4.879.E−1
7.567.E−2
6.930.E−2
5.621.E−2
3.692.E−2

H251
H286

3.497.E−23.382.E−2

H405
H167.
.
H378

2.796.E−2
2.743.E−2
1.974.E−8

Abducted concentrations levels at T=0
pg3: 2, adp: 0
sed7p: 0, e4p: 2, f6p: 0, pg3: 2, adp: 0
pg3: 2, adp: 0, pep: 0, atp: 2, pyr: 2
fdp: 0, dhap: 2, gap: 0, pg3: 2, adp: 0
pg3: 2, adp: 0, g6p: 1, nadph: 1
sed7p: 0, e4p: 2, f6p: 0, pg3: 2, adp: 0,pep: 0, atp: 2, pyr: 2
glucose: 2, adp: 0, pg3: 2
sed7p: 0, e4p: 2, f6p: 0, fdp: 0, dhap: 2,gap: 0, pg3: 2, adp: 0
pg3: 2, adp: 0, pep: 2, atp: 0
sed7p: 0, e4p: 2, f6p: 0, pg3: 2, adp: 0,g6p: 1, nadph: 1

KEGG

kegg2symb

Symbolic
pathwaypy-tsdisc

Discretized
data

SOLAR

Hypotheses

Conversion

Experimental
Data

BDD-EM
HUP: append

Rules, here akinetic model

Rankedhypotheses

glucose: 2, adp: 0, sed7p: 0, e4p: 2, f6p: 0,fdp: 0, dhap: 2, gap: 0, pg3: 2, pep: 0, atp: 2,pyr: 2, g6p: 0, nadph: 2, pg6: 1

23/29

Previous works
A finer logic modelingResults and furtherRanked Results
Where next?

Is is correct?

Ok with: glucose + 2ADP + 2P + 2NAD+ →2 pyruvate + 2ATP + 2(NADH, H+ ) + 2H2 O

Agree with:Peters-Wendisch, P., Schiel, B., Wendisch, V., and et al., E. K.
(2001).Pyruvate carboxylase is a major bottleneck forglutamate and lysine production by corynebacterium
glutamicum. Molecular Microbiol. Biotechnol., 3(2).

24/29

Previous works
A finer logic modelingResults and further

Ranked Results
Where next?

Full system
Backgroundknowledge

Automated

Discretization

Hypotheses
Generator(SOLAR)

Databases

Observations

Logicallypossible
hypotheses

Hypotheses Evaluator(BDD-EM)

Enhancer

Most probablehypotheses

Experiments

25/29

Previous works
A finer logic modelingResults and further

Ranked Results
Where next?

Future tracks:

Enhancing of the knowledge base, 2 simple andsound algorithms (one in the paper):most probable hypotheses firstsmallest number of hypothesis additions (biggestabducibles coverage first)

Finer discretization: trivial with our continuous
HMMs with parameter tying.
Automatic generation of MM rules (for orders > 3).

26/29

Previous works
A finer logic modelingResults and further

Ranked Results
Where next?

Conclusion
We presented and validated a method and tools towork on real data.

Working with other experiments on more complex
organisms and pathways (for instance S. Ce) will
require:Enhancing of the KB
Finer discretization
Kinetic rules

27/29

Previous works
A finer logic modelingResults and further

Ranked Results
Where next?

ThanksThank you for your attention.

28/29

Previous works
A finer logic modelingResults and further

Ranked Results
Where next?

Any questions?

Any questions?

Me: gabriel.synnaeve@gmail.com
Prof. Inoue: ki@nii.ac.jp

29/29