Tan Le

Andrei Doncescu
email: andrei.doncescu@laas.fr

Pierre Siegel
email: p.siegel@free.fr

Utilization of Default Logic for Analyzing a Metabolic System in Discrete Time

Metabolic pathways are seen as high criticalities in our understanding of mechanisms of biological functions. This article focuses on automatic synthesis of the metabolic pathways from factors in the domain of discrete time. An essential component of this approach is using default logic to acquire facts about biological knowledge of intracellular communication. By choosing an adequate representation of biological knowledge, the "reasoning" is able to assign in acquisition of the facts and extract interactions necessary for the synthesis of the metabolic pathways or signaling.

I.

INTRODUCTION

Today, increasingly specialized experts need an appropriate evaluation of their know-how corroborated with the available experimental data in order to discover new knowledge. This scientific approach apprehends the biology systems by hypotension and validation of it. In this context, in recent decades, biology has grown prolifically in all its facets. New fields of applications and studies such as biotechnology, nanotechnology and bioinformatics are immersed and take an important place in the context of current research with the goal of identifying, understanding and quantification of biological phenomena seen in within the biological system.

The System Biology is the research field, which handles biological complex system representation and analysis. The dynamic nature and non-linear inherence of biological course make the system identification difficult. By system identification we understand the model associated to biological system. The majority of kinetic models in biology could be described by a couple of differential equations [START_REF] Demongeot | Multi-stationarity and cell differentiation[END_REF]. It is almost impossible to find out an analytical solution to these non-linear systems [START_REF] Doncescu | Utilisation de la logique des hypothèses pour la modélisation des voies de signalisation dans la cellule[END_REF]. The only feasible approach is a bottom-up analysis allowing the solving and simulating of the biological systems.

From the standpoint of Artificial Intelligence cells are sources of information that include a myriad of intra and extra cellular signals that as the ultimate goal of optimal output describing metabolic proteins. Disease and cancer in particular can be seen as a pathological alteration in the signalling networks of the cell. The study of signalling events appears to be the key of biological, pharmacological and medical research. The spread of these types of signals are not changing the behaviour of proteins on three levels: regulation of the activity, interaction and expression. The three levels are synchronized in a strong momentum that leads to changes in protein activity. Since a decade signalling networks have been studied using analytical methods based on the recognition of proteins by specific antibodies. Parallel DNA chips (microarrays) are widely used to study the co-expression of candidate genes to explain the etymology of certain diseases, including cancer. This huge amount of data allows the modelling of gene interactions. The biological experts look for evidence of interactions between metabolites or genes. Therefore the representation by graphs is the best way of understanding of biological systems. This representation includes mathematical properties as connectivity; presence of positive and negative loops which is related to a main property of genetic regulatory networks. Biochemical reactions are very often a series of time steps instead of one elementary action. Therefore, one of the research directions in system biology is to capture or to describe the series of steps called pathways by metabolic engineering. All reactions that allow the transformation of one initial molecule to a final one constitute metabolic pathways. Each compound that participates in different metabolic pathways is grouped under the term metabolite.

The study of gene networks poses problems well identified and studied in Artificial Intelligence over the last thirty years. In this article we present how the possibility to reason from incomplete, uncertain, revisable, contradictory and multiple sources. Indeed, the logical or mathematical description of signalling pathways is not complete: biological experiments provide a number of protein interactions but certainly not all of them. On the other hand the conditions and sometimes the difficulties of the experiments involve these data are not always accurate. Some data may be very wrong and must be corrected or revised in the future. Finally the information coming from different sources and experiences can be contradictory. It is the goal of different logics and particularly the nonmonotonic logics to handle this kind of situations. Afterwards this interaction maps should be validates by biological experiments. Of course, these experiments are time consuming and expensive, but less than an exhaustive experiment.

The article goal is to analyse, understand and associate a logical model to biological systems. However, we want to build-up a knowledge based-system, able to discover biological mechanisms.

II. METABOLIC PATHWAY

In attempts to describe the behaviour of living systems, where the deductive model is not successful, the process by qualitative reasoning based on the function of molecules has shown its limits [START_REF] Doncescu | Characterization of bio-chemical signals by inductive logic programming[END_REF]. Similarly, if the properties are known, we cannot clearly deduce their function in the living cell, and from the characteristics of living cells, calculate their behaviour in a given environment. In general, the deductive approach fails because the functions of the living system components depend simultaneously of the interactions with other elements. The recurring problem of this reasoning is how the functional properties of the cell can be derived from properties of its components alone. In this context, with their ability to describe the complexity, the logic tools offer a perspective to analyse these structural elements organized in a complex network.

If the analytical models based on differential equations are impossible to solve and the multi-scale analysis seems utopic, we propose, in this paper, an elegant solution to find out the main metabolic reaction [START_REF] Doncescu | Knowledge-based discovery in systems biology using CF-induction[END_REF].

Fig. 1 gives a very simplified example of interactions in a cell. While the cells have different morphologies and structures and their roles in different organisms are different, their basic functionality is the same. One of these cell-based activities is to ensure their own survival. Its activity can be wholly summarized in two points. First, cells need to find the energy required for its activity. This energy is mainly obtained by the degradation of inorganic or organic molecules. Second, the cells need to make simple molecules necessary for their survival. The first is called catabolism and the second is called anabolism. These two major activities are grouped under the name of metabolism, and result from many mechanisms and biochemical reactions. Most of these reactions, which take place in a cell, are catalysed by special molecules called enzymes. Such a large amount of data on the metabolism is represented as a network, called a metabolic pathway, and has been stored and maintained in a database on a large scale [START_REF] Doncescu | Characterization of bio-chemical signals by inductive logic programming[END_REF]. Recently, the study of metabolic pathways is becoming increasingly important to use an integrated and systematic approach for simulation or optimization of cellular properties or phenotypes. One of these important properties is the metabolic flux defined as the rate of a biochemical reaction, which can be very often used to improve the production of metabolites in the industry. A basic approach, but powerful to understand the steady-state flux in balancing of metabolite flux, is based on the stoichiometric model of biochemical reactions. Figure 1 shows the simple topology of a metabolic pathway in a cell, which consists of five metabolites A, B, C, D and E and six reactions, each of which connects two certain metabolites. Each flux is placed on the corresponding reaction in Fig. 1. The concentrations of A, C, D and E are experimentally measurable, but the concentration of B cannot be measured. Therefore, B is the intracellular metabolite. On the basis of enzyme kinetics, the dynamic behaviour of the flow of an enzymatic reaction can be represented by the following differential equation [START_REF] Schwind | Modal Logic for Hypothesis Theory[END_REF]:

(1)
where C x is the concentration of a metabolite X, v in (resp. v out ) is the sum of net reactions for the production (resp. consumption) of X, and μC X represents the rate of growth of biomass in a cell. If all metabolites are at the steady state, the left term of equation ( 1) must be zero, because there are no changes of time series of concentrations, and also, we can assume that the dilution of components due to the biomass growth (corresponding to the duration of the last equation ( 1)) is neglected. This fact means that for each metabolite X, consumption flows of X are balanced with the production flows of X at steady state. The metabolic flux balancing is based on this simple notion. For example, the balance equations of the cell model (Fig. 1) can be represented by the following linear equations:

, , , , (2)
Then we can analyse the flow distribution on the basis of equations ( 2) with measurable flux rA, rC, rD and rE. In general, these equations cannot be solved deterministically as the number of unknown values as v 1 …,v 5 corresponding to intracellular enzymatic reactions flow become greater than the number of values corresponding to known measurable flow. The previously proposed methods such as analysis in primary mode and extreme pathway analysis functions use optimization in order to solve the equations. These introduced functions are typically constructed assuming the maximization of cell growth or minimization energy consumption. However, in the case of a large-scale metabolic pathway, we cannot solve the flux distribution with these approximation methods because of the enormous computational cost. Doncescu et al. propose a new approach that allows us to reduce the complexity of a given metabolic pathway. This approach is based on a bottom-up analysis, which takes into account the enzymatic activity [START_REF] Chassagnole | Differential evolutionary algorithms for in vivo dynamic analysis of glycolysis and pentose phosphate pathway in Escherichia Coli[END_REF]. An essential factor of enzyme activities is that all activities are not necessarily the same. There are enzymes whose activities are about 100 or 1000 times higher than other enzymes. This fact allows us to assume that each enzymatic reaction is in a state relatively activated or not. Then, if we can estimate that the enzymatic reactions are in an active or non-active state, we could simplify the pathway before ignoring the reactions in the non-active, which are estimated to have low flows. The smaller the target pathway is, the fewer the number of unknown values in the equations obtained from the pathway is. This implies the possibility of solving the equations with the approximation methods proposed previously. In the approach, we introduced a logic model that represents causal relations between enzymatic reaction states and changes in concentration of metabolites. Based on the default logic, we believe that the possible states can explain the observations that are done experimentally. In the follow, we focus on these causal relationships in enzymatic reactions.

III. LOGICAL MODEL OF METABOLISM

The cellular metabolic system has a sophisticated mechanism to dynamically control the activities of enzymes in response to needs of a cell. This regulatory mechanism can be represented as causal relationships between enzyme activities and concentration of metabolites changing. Three simple metabolic pathways are considered in [START_REF] Doncescu | Knowledge-based discovery in systems biology using CF-induction[END_REF]: the first consists of two reactions with three metabolites, the second consists of two reactions with three metabolites also, and the last consists of one reaction with two metabolites. Note that in the following figures, we describe the activity and nonactivity by reactions such as circles and slashes over arrows corresponding to the reactions, respectively. And also, an increase (resp. decrease) arrow represents the increase (resp. decrease) at a concentration of metabolites.

Fig. 2 corresponds to the metabolic pathway composed of three metabolites X, Y and Z, and two reactions. The figure shows that if the concentration of Y tends to be increased at some moment, provided that the state of enzymatic reaction Y → X (resp. X → Z) is activated (resp. non-activated), then the concentration X will also change upward. This causal relation is rational management based on equation [START_REF] Demongeot | Multi-stationarity and cell differentiation[END_REF]. Suppose that the increase in the concentration of X is designated by a dotted arrow in the figures. Then it will be possible to estimate the states of the concentration of Y and two reactions so that the estimated states cause concentration change of X. One possibility is that the concentration of Y is increased, the reaction of Y → X is activated and the reaction X → Z is non-activated. This is because the production of X from Y cannot be consumed and generates Z. Fig. 3 also corresponds to the metabolic pathway composed of three metabolites X, Y and Z, and two reactions. The figure shows that if the concentration of Y tends to be increased at some moment, provided that the state of enzymatic reaction Y → X (resp. X → Z) is non-activated (resp. activated), then the concentration X will change downward. This causal relation is rational management based on the equation [START_REF] Demongeot | Multi-stationarity and cell differentiation[END_REF]. Suppose that the decrease in the concentration of X which is observed is designated by a dotted arrow in the figures. Then it will be possible to estimate the states of the concentration of Y and two reactions so that the estimated states cause concentration change of X. One possibility is that the concentration of Y is increased, the reaction of Y → X is non-activated and the reaction X → Z is activated. This is because the production of X from Y may be consumed and generates Z. Next, we consider Fig. 4 which represents a metabolic pathway consisting of two metabolites X and Y, and one reaction. The figure shows that, although the reaction Y → X is activated, the concentration of X must be decreased if the concentration of Y is decreased. Therefore, if we observe that the concentration of X is decreased, presumably assume a decrease in the concentration of Y and Y → X reaction is activated as a possible case.

IV. LOGICAL REPRESENTATION

Genes and proteins are considered the same object (genes produce proteins). We will often restrict here to a propositional representation. In practice, the detailed study of interactions will require to represent increases or decreases in protein concentration. It therefore falls outside the scope propositional but the basic problems are the same. To represent a change in concentration, it is, for example possible to use predicates such as "increase" or "decrease" and to limit the use of these predicates.

To describe interactions between genes in the cell, we start from a classical logic language L (propositional or first order). In L, the proposition A (resp. ¬ A) means that A is true (resp. false). We can say, for example, react(A, B) to

X Y Z X Y Z X Y
say that there is one reaction between A and B. On the other hand, we might say, for example con(A, up, t i ) to say that the concentration of A is increased at the moment t i , or, con(A, down, t j ) to say that the concentration of A is decreased at the moment t j . We are in a logical framework, so it is possible to represent almost everything you want in a natural way. The price to pay, if we use the entire language can be the combinatorial explosion of algorithms.

Interactions among genes are a very simple form of causality. To express these interactions it is common to get to the point by giving two binary relations active(A, B) and non-active(A, B). The first relation means, for example, a protein A initiates the production of a protein B, while the second is an inhibition. In a conventional way, these relationships are represented in the network of genes, by A → B and A ⊣ B. Of course, this causality is basic and many works have been written to represent the causalities.

If the inference of classical logic A → B is formally described, with all the "good" mathematics and computer science properties (tautology, not contradiction, transitivity, contraposition, modus ponens, compactness ...), the description of formal properties causation is less straightforward. Causality cannot be seen as a logical classical relation. A basic example is that of the expression "If it rains, the grass is wet". This expression cannot be translated by the formula rain → grass-wet, which will signify that when it rains the grass is wet automatically. Indeed, there are may be exceptions to this rule (the grass is in a shed ...). You can also change the environment (we cover the grass...). These revisable rules and exceptions are well known in Artificial Intelligence. They create, in particular, non-monotonic logics and theories of review. On the other hand and more technical, we find here all the classical problems that arise when we want to try to formalize and use negation by failure in programming languages such as Prolog or Solar.

To give the links between our causal relations active and non-active, in a classical language (propositional calculus or first order logic), we must therefore do two things: -describe the internal properties in relations active and nonactive -describe the links between these relations and the classical logic All this take into account the problem of uncertain and revisable. For the first aspect we will explicitly give the minimum and necessary links between two causal relations. Links with classical logic will be described at the first time in default logic.

In our context, to give these linkages between the relations active and non-active, we will simply, use classical logic. The basic solution is then to explicitly give three schemes of axioms: (C1): con(A,up,t i )∧react (A,B) We believe that this axiomatic minimum system is necessary and probably sufficient for the application to the cell. At the moment there is no formal link between two relations. It is of course possible to add other axioms to take into account these links. But these formulations are problematic because there is a conflict. If for example we have a set of seven formulas F = {con(A, up, t i ), react(A, B), react(B, C), active(A, B), non_active(B, C), non_active(A, B), active(B, C)}, it goes both approaches above infer F, con(B, up, t i+1 ) and con(B, down, t i+1 ) which is a paradox. To resolve such conflicts, you can try using methods inspired by constraint programming, such as the use of negation by failure. It is also possible to use a defeasible reasoning, particularly a non-monotonic logic. The first approach poses many conceptual and technical problems if you leave the simple cases. These problems are often solved by adding properties to the formal system, properties that pose other problems ... and that leads to an explosion. We will study here a non-monotonic logic, initially, it is the default logic.

V. INTERACTION AND DEFAULT LOGIC

Default logic formalizes reasoning by default. It allows treating the rules by admitting exceptions without having to challenge the rules previously established whenever a new exception appears. A default theory consists of a set of facts W, which are formulas of propositional calculus from either of the first order logic, and a set of defaults D, which are rules of inference to specific contents. Defaults are used to manage incomplete information. In its most general form, a default is an expression of the form:

(3) where A x (X), B y (X) and C(X) (x = 1,2, ..., m, y = 1,2, ..., l) are well-formed formulas which contain first order as free variable X or X = (x 1 , x 2 , x 3 , …, x n ) as a vector of free variables. A x (X) are the prerequisites, B y (X) are the justifications and C(X) is the consequent. The default equation ( 3) means informally: if A x (X) are verified (at some moment t i ), if it is possible that B y (X) are real (B y (X) are consistent), and if it is possible that C(X) is true (at the moment t i+1 ), then we infer C(X) (at the moment t i+1 ).

The use of defaults increases the number of formulas derived from the knowledge base W: we get extensions that are sets of theorems derivable monotonically. An extension of the default theory Δ = (D, W) is a set E of formulas, closed for the deduction, containing W and satisfying the following property: if d is a default of D whose prerequisites A x (X, t i ) are in E, the negation of justifications B y (X) and of consequent C(X, t i+1 ) are not in E, then the consequent of d is in E. Formally, the extensions are defined as follows:

The calculation of extensions allows to study the defaults one by one and to retain those who respond to the problem and are compatible with each other. Each extension corresponds to a possible solution of the problem. To calculate an extension, we must verify that the negation of justification does not belong to E i . We can therefore use an incremental algorithm for computing extensions. For a default theory Δ = (D, W), with the set of defaults D and the knowledge base W, the calculation is extended according to the algorithm:

Figure 1 .

 1 Figure 1. Cell model.

Figure 2 .

 2 Figure 2. The first relationship between the states of reaction and concentrations

Figure 3 .

 3 Figure 3. The second relationship between the states of reaction and concentrations

Figure 4 .

 4 Figure 4. The third relationship between the states of reaction and concentrations

ACKNOWLEDGMENT

We deeply thank to D.R. Jean-Charles Faye and C.R. Olivier Sordet of Claudius Regaud Cancer Institute (ICR). Moreover, we are particularly grateful to Vietnamese and French Gouverment to finace this work.

Input : E = θ; (set of extensions E is empty).

calcul_extension(E) :

{ that has not yet been inspected do [START_REF] Doncescu | Knowledge-based discovery in systems biology using CF-induction[END_REF] Select the default D, (3) Verify that the prerequisites A x (X) are true (at some moment t j ), [START_REF] Doncescu | Characterization of bio-chemical signals by inductive logic programming[END_REF] Verify that the justifications B y (X) are consistent with W, [START_REF] Chassagnole | Differential evolutionary algorithms for in vivo dynamic analysis of glycolysis and pentose phosphate pathway in Escherichia Coli[END_REF] Verify that the consequent C(X) is consistent with W (at the moment t j+1 ), (6) Add B y (X) and C(X, t j+1 ) to W. (10) calcul_extension(E). }

In our example, to provide links between these relationships active and non-active, the intuitive idea is to weaken the formulation of causation rules: The question is then formally described by possible. We use here a non-monotonic logic of the best known, default logic. In this logic, the rules (1), (2), and (3) will be expressed intuitively as: If we consider a pulse of glucose as input (A) at the time t 0 , this pulse will produce the decreasing of the concentration in B at t 1 and this metabolic configuration has a low concentration the output (E) at t 3 .

This algorithm is NP-complete. Of course the real problem of metabolic pathways is more complicated than the model presented in this paper. The practical complexity can then be accessible by controlling the numbers of defaults. If it is necessary to know, which molecule (a future drug), acts effectively we could represent this problem in a context of abductive reasoning. In simple terms, abduction find out the "minimum" information set added to a known facts F, able to deduce a result R which we would like to prove.

VI. CONCLUSION

We presented a first metabolic pathways model using default logic to represent, complete and to find out the main reaction. All this was done using the reasoning with default assumption. We show-up all possible main reactions in the case of a simple model, the next work will be devoted to real metabolic maps downloaded from KEGG.


Tan Le

Andrei Doncescu
email: andrei.doncescu@laas.fr

Pierre Siegel
email: p.siegel@free.fr

Default Logic for Diagnostic of Discrete Time System

Signaling pathways are seen as high criticalities in our understanding of mechanisms of biological functions. In this paper, we propose default logic for diagnostic of Discrete Time System (DTS) by focusing on automatic synthesis of the signaling pathways from factors within the cell. An essential component of this approach is using default logic to acquire facts about biological knowledge of intracellular communication. By choosing an adequate representation of biological knowledge, the "reasoning" is able to assign in acquisition of the facts and extract interactions necessary for the synthesis of the signaling pathways. I.

INTRODUCTION

Today, increasingly specialized experts need an appropriate evaluation of their know-how corroborated with the available experimental data in order to discover new knowledge. This scientific approach apprehends the biology systems by hypotension and validation of it. In this context, in recent decades, biology has grown prolifically in all its facets. New fields of applications and studies such as biotechnology, nanotechnology and bioinformatics are immersed and take an important place in the context of current research with the goal of identifying, understanding and quantification of biological phenomena seen in within the biological system.

The System Biology is the research field, which handles biological complex system representation and analysis. The dynamic nature and non-linear inherence of biological course make the system identification difficult. By system identification we understand the model associated to biological system. The majority of kinetic models in biology could be described by a couple of differential equations [START_REF] Demongeot | Multi-stationarity and cell differentiation[END_REF]. It is almost impossible to find out an analytical solution to these non-linear systems [START_REF] Doncescu | Utilisation de la logique des hypothèses pour la modélisation des voies de signalisation dans la cellule[END_REF]. The only feasible approach is a bottom-up analysis allowing the solving and simulating of the biological systems.

From the standpoint of Artificial Intelligence, cells are sources of information that include a myriad of intra and extra cellular signals that as the ultimate goal of optimal output describing proteins. Disease and cancer in particular can be seen as a pathological alteration in the signaling networks of the cell. The study of signaling events appears to be the key of biological, pharmacological and medical research. The spread of these types of signals are not changing the behavior of proteins on three levels: regulation of the activity, interaction and expression. The three levels are synchronized in a strong momentum that leads to changes in protein activity. Since a decade signaling networks have been studied using analytical methods based on the recognition of proteins by specific antibodies. Parallel DNA chips (microarrays) are widely used to study the co-expression of candidate genes to explain the etymology of certain diseases, including cancer. This huge amount of data allows the modeling of gene interactions. The biological experts look for evidence of interactions between proteins or genes. Therefore, the representation by graphs is the best way of understanding of biological systems. This representation includes mathematical properties as connectivity; presence of positive and negative loops which is related to a main property of genetic regulatory networks. Biochemical reactions are very often a series of time steps instead of one elementary action. Therefore, one of the research directions in system biology is to capture or to describe the series of steps called pathways by signaling engineering.

The study of gene networks poses problems well identified and studied in Artificial Intelligence over the last thirty years. In this article we present how the possibility to reason from incomplete, uncertain, revisable, contradictory and multiple sources. Indeed, the logical or mathematical description of signaling pathways is not complete: biological experiments provide a number of protein interactions but certainly not all of them. On the other hand, the conditions and sometimes the difficulties of the experiments involve these data are not always accurate. Some data may be very wrong and must be corrected or revised in the future. Finally, the information coming from different sources and experiences can be contradictory. It is the goal of different logics and particularly the nonmonotonic logics to handle this kind of situations. Afterwards this interaction maps should be validates by biological experiments. Of course, these experiments are time consuming and expensive, but less than an exhaustive experiment.

The article goal is to analyze, understand and associate a logical model to biological systems. However, we want to build-up a knowledge based-system, able to discover biological mechanisms.

The rest of this paper is organized as follows. Section II gives the problem from a biological point of view. Section III presents the causal relations between enzymatic activities. Section IV introduces the logical representation of these relations. Section V shows experimental results obtained by application of the default logic for estimation of possible reaction states from given observations. Section VI concludes this paper.

II. SIGNALING PATHWAY

In attempts to describe the behavior of living systems, where the deductive model is not successful, the process by qualitative reasoning based on the function of molecules has shown its limits [START_REF] Doncescu | Characterization of bio-chemical signals by inductive logic programming[END_REF]. Similarly, if the properties are known, we cannot clearly deduce their function in the living cell, and from the characteristics of living cells, calculate their behavior in a given environment. In general, the deductive approach fails because the functions of the living system components depend simultaneously of the interactions with other elements. The recurring problem of this reasoning is how the functional properties of the cell can be derived from properties of its components alone. In this context, with their ability to describe the complexity, the logic tools offer a perspective to analyze these structural elements organized in a complex network.

If the analytical models based on differential equations are impossible to solve and the multi-scale analysis seems utopic, we propose in this paper an elegant solution to find out the main signaling reaction [START_REF] Doncescu | Knowledge-based discovery in systems biology using CF-induction[END_REF].

While the proteins have different morphologies and structures and their roles in different organisms are different, their basic functionality is the same. One of these cell-based activities is to ensure their own division (production). Its activity can be wholly summarized in two points. First, proteins can promote an activity of others, which is called cause. Second, proteins can inhibit an activity of others, which is called block. Most of these reactions, which take place in a cell, are catalyzed by special molecules called enzymes. Such a large amount of data on the signaling is represented as a network, called a signaling pathway, and has been stored and maintained in a database on a large scale [START_REF] Doncescu | Characterization of bio-chemical signals by inductive logic programming[END_REF].

Fig. 1 gives a very simplified example of interactions in a cell. Through different mechanisms not shown here, ultraviolet (UV) is the cell apostasies (it actually becomes immortal) from cancer. This is shown by an arrow. On the other hand, the UV activates the production of the protein p53. This protein will activate protein A which will block the cancer. But p53, bounds to the protein Mdm2, will produce B, which will block A. For a biologist, the question is how to block the cancer by blocking B. Biological experiments have shown that X could be a candidate for this block. Fig. 2 and Fig. 3 provide two types of interactions with X to explain blocking B [START_REF] Doncescu | Utilisation de la logique des hypothèses pour la modélisation des voies de signalisation dans la cellule[END_REF]. The problem is, in the domain of discrete time, how the interactions like. For example, at a moment, t 0 , UV activates cancer and p53. At the next moment, t 1 , p53 will activate A. On the other hand, p53 will bind to the Mdm2 for active B, who will block A at the moment t 2 , etc. In this paper, we have completed the graph by hand, and by using the computer to do this, too. This example is a very basic case, of course. In practice this graphical representation of the network signaling pathways may involve several thousands of genes. But the problem is still not trivial because the discovery (abduction) will be firstly on the presence of protein C and secondly on the addition of links between proteins. Genes and proteins are considered as a same object (genes produce proteins). We will often restrict here to a propositional representation. In practice, the detailed study of interactions will require to represent increases or decreases in protein concentration. It therefore falls outside the scope propositional, but the basic problems are the same. To represent a change of concentration, for example, is possible to use predicates such as "increase" or "decrease" and to limit the use of these predicates.

To describe interactions between genes in the cell, we start from a classical logic language L (propositional or first order). In L, the proposition A (resp. ¬ A) means that A is true (false). We can say, for example, give(UV) to say that the cell is subjected by ultraviolet, or even glass-screen → ¬ give(UV) to say that a glass screen protects from ultraviolet rays. We are in a logical framework, so it is possible to represent almost everything you want in a natural way. The price to pay, this can be the combinatorial explosion of algorithms.

Interactions among genes are a very simple form of causality. To express these interactions, it is common to use two binary relations cause(A, B) and block(A, B). The first relation means, for example, protein A initiates the production of protein B, while the second inhibits it. Conventionally, these relationships are represented in the network of genes by A → B and A ⊣ B. Of course, this causality is basic and many works have been written for represent the causalities.

If the inference of classical logic A → B is formally described perfectly, the description of formal properties causation, is less straightforward. Causality cannot be seen as a logical classical relation. A basic example is that of the expression "If it rains, the grass is wet". This expression cannot be translated by the formula rain → grass-wet, which will signifier that when it rains, the grass is wet automatically. Indeed, there may be exceptions to this rule (the grass is in a shed ...). We can also change the environment (we cover the grass). These revisable rules and exceptions are well known in Artificial Intelligence. They create, in particular, non-monotonic logics and theories of review. On the other hand, and more technical, we find here all the classical problems that arise when we want to try to formalize and use negation by failure in programming languages such as Prolog or Solar.

To give the links between our causal relations cause and block, in a classical language (propositional calculus or first order logic), it must therefore do two things: -describe the internal properties in relations cause and block -describe the links between these relations and the classical logic All this take into account the problem of uncertain and revisable. For the first aspect we will explicitly give the links minimum and necessary between two causal relations. Links with classical logic will be described in a first time in default logic. Then, to take into account the aspect of discovery (abduction, field of production) we will use the default logic.

In our context, to give these links between the relations cause and block, we will more simple, use classical logic. The basic solution is then to explicitly give two schemes of axioms:

(

C1) cause(A,B) ˄ cause(B, C) → cause(A, C) (C2) cause(A, B) ˄ block(B, C) → block(A, C)

We believe that it is axiomatic minimum system necessary and probably sufficient for the application to the cell. At the moment, there is no formal link between two relations. It is of course possible to add other axioms to take into account these links.

IV. LOGICAL REPRESENTATION

In a first approach, the first properties that we want to give can be expressed naturally, by the rules of the type:

(1) If A cause B and if A is true, so B is true.

(2) If A block B and if A is true, so B is false.

Depending on the context, the true can be called the known, certain ... or, more technically, in a demonstration automatically system proved. The first idea is to express these laws in classical logic by axioms:

cause(A, B) ˄ A → B block(A, B) ˄ A → ¬B
We can also express more weakly the laws by inference rules of modus ponens nearby: cause(A, B) ˄ A / B block(A, B) ˄ A / ¬B But these two formulations are problematic because there is a conflict. For example, if we have a set of four formulas F = {A, B, cause(A, C), block(B, C)}, it goes to both approaches above data inferred from F, C and ¬C, which is inconsistent. To resolve this type of conflict, we can try to use methods inspired by constraint programming, such as the use of negation by failure. It is also possible to use a revisable reasoning, especially a non-monotonic logic. The first approach poses many conceptual and technical problems if you leave the simple cases. These problems are often solved by adding properties to the formal system, that pose other problems ... and we arrive at a beautiful gas plant. We will study here a non-monotonic approach. At first, we use the default logic.

V. INTERACTION AND DEFAULT LOGIC

Default logic formalizes reasoning by default. It allows treating the rules by admitting exceptions without having to challenge the rules previously established whenever a new exception appears. A default theory consists of a set of facts W, which are formulas of propositional calculus from either of the first order logic, and a set of defaults D, which are rules of inference to specific contents. Defaults are used to manage incomplete information. In its most general form, a default is an expression of the form: [START_REF] Demongeot | Multi-stationarity and cell differentiation[END_REF] where A x (X), B y (X) and C(X) (x = 1,2, ..., m, y = 1,2, ..., l) are well-formed formulas which contain first order as free variable X or X = (x 1 , x 2 , x 3 , …, x n ) as a vector of free variables. A x (X) are the prerequisites, B y (X) are the justifications and C(X) is the consequent. The default equation ( 1) means informally: if A x (X) are verified, if it is possible that B y (X) are real (B y (X) are consistent), and if it is possible that C(X) is true, then we infer C(X).

The use of defaults increases the number of formulas derived from the knowledge base W: we get extensions that are sets of theorems derivable monotonically. An extension of the default theory Δ = (D, W) is a set E of formulas, closed for the deduction, containing W and satisfying the following property: if d is a default of D whose prerequisites A x (X) are in, the negation of justifications B y (X) and of consequent C(X) are not in E, then the consequent of d is in E. Formally, the extensions are defined as follows:

The calculation of extensions allows to study the defaults one by one and to retain those who respond to the problem and are compatible with each other. Each extension corresponds to a possible solution of the problem. To calculate an extension, we must verify that the negation of justification does not belong to E i . We can therefore use an incremental algorithm for computing extensions. For a default theory Δ = (D, W), with the set of defaults D and the knowledge base W, the calculation is extended according to the algorithm:

Input : E = θ; (set of extensions E is empty). The question is then formally described by possible. We use here a non-monotonic logic of the best known, default logic. In this logic, the rules (1) and (2) will be expressed intuitively as:

calcul_extension(E) :

(1') If cause(A,B) is true, and if A is true, and if B is not contradictory, then B is true (2') If block(A,B) is true, and if A is true, and if ¬B is not contradictory, then ¬B is true In the default logic, these rules will be represented by the set of defaults D and be written: If it is necessary to know, which molecule (a future drug), acts effectively we could represent this problem in a context of abductive reasoning. In simple terms, abduction find out the "minimum" information set added to a known facts F, able to deduce a result R which we would like to prove.

VI. CONCLUSION

We presented a first signaling pathways model using default logic to represent, complete and to find out the main reaction. All this was done using the reasoning with default assumption. We show-up all possible main reactions in the case of a simple model, the next work will be devoted to real signaling maps downloaded from KEGG.

Figure 1 .

 1 Figure 1. One example of interactions in a cell

Figure 2 .

 2 Figure 2. One possible solution

Figure 3 .

 3 Figure 3. Another possible solution III. LOGICAL MODEL OF SIGNALING

{

  that has not yet been inspected do (2) Select the default D, (3) Verify that the prerequisites A x (X) are true, (4) Verify that the justifications B y (X) are consistent with W, (5) Verify that the consequent C(X) is consistent with W, (6) Add B y (X) and C(X) to W. (7) end while (8) End of the calculation for an extension.

( 9 )

 9 Backtracking (deleting the last C(X) and B y (X) added to W).

( 10 )

 10 calcul_extension(E). }In our example, to provide links between these relationships cause and block, the intuitive idea is to weaken the formulation of causation rules: (1) If cause(A,B) is true (A causes B), and if A is true, and if it is possible that B, then B is true (2) If block(A,B) is true (A blocks B), and if A is true, and if it is possible that B is false, then B is false

¬

  We have also two general defaults, where X ∈ {uv, p53, mdm2, a, b}: The conflict was resolved.With the default theory Δ = (D, W), in which D = {d1, d2, d3, d4, d5, d6, d7, d8, d9} and W = {uv,mdm2}, by applying the algorithm above, we have 18 extensions. The next are two could be easily interpreted that correspond to Fig.2and Fig.3, respectively:This algorithm is almost NP -problem. Of course the real problem of signaling pathways is more complicated than the model presented in this paper. The practical complexity can then be accessible by controlling the numbers of defaults.

ACKNOWLEDGMENT

We deeply thank to D.R. Jean-Charles Faye and C.R. Olivier Sordet of Claudius Regaud Cancer Institute (ICR). Moreover, we are particularly grateful to Vietnamese and French Government to finance this work.