Figure 22.3 presents a classical simplified pathway of interactions in a cell (Inoue et al., 2013). It shows the interactions between cancer and ultraviolets and the genes:

• The arrow → shows the direction of the activation. For example, UV → Cancer means that the ultraviolet causes cancer, but → p53 means that p53 is activated.

• The inhibition is represented by the symbol . For example, A Cancer means that A blocks cancer.

• The binding means that two genes bind together to create a compound, such as p53 and Mdm2. This compound activates B.

From a biological point of view, Mdm2 is a cellular antagonist of p53 that maintains a balanced cellular level of p53. The two proteins are linked by a negative regulatory feedback loop and physically bind to each other via a putative helix formed by residues 18–26 of p53 transactivation domain (TAD).

Intuitively, the causal graph represented in Figure 22.3 shows through different mechanisms (not shown) that an ultraviolet (UV) drives the cell to develop cancer. This is represented by an arrow: UV → cancer. On the other hand, the UV activates the protein P53: UV → P53. Protein B activates protein A: P53 → A, and protein A blocks cancer: A cancer. In addition, Mdm2 binds protein P53, the complex activates B, and B blocks A.

Obviously, this explication lacks coherence. If it is known that UV is an active input and mdm2 is not, then the cancer is triggered. But, if p53 is activated, then A is activated and cancer is inhibited or blocked. Therefore, the cancer is both activated and blocked, which is inconsistent.

This example is very simple, but it is helpful to explain our representation for gene networks and the algorithms used for biological knowledge discovery. To analyze real biological systems, which contain many pathways with thousands of genes, it is obvious that computational complexity has to be handled.

3.2 Logic representation

A biological function is not the result of only one macro-molecule. Indeed, a group of macromolecules including genes and proteins acts simultaneously and results in the activation of one or more signaling pathways. In this logical model, genes and proteins are considered i the same object, even though they are different biologically (Tran and Baral, 2007).

In this chapter, biological events are often described using propositional logic. However, to design a new plan of experiments, the study of interactions is based on queries. Queries are used to ask whether something is a logical consequence of a knowledge base or not. With propositional queries, a user can ask yes-or-no questions. Queries with variables allow the system to return the values of the variables that make the query a logical consequence of the knowledge base. Therefore, the representation of concentration changes. It is possible, for example, using predicates such as increased or decreased, and the query is whether the concentration of protein A increases or decreases. Some of these queries fall outside the scope of propositional logic, but the basic problems are the same: the protein concentration is rarely precise, and often in practice, the experiments encounter some difficulty in defining thresholds.

The dynamic aspect of protein interactions is based on first-order logic and propositional logic. For example, stimulation(UV) means that the DNA is subjected to ultraviolet, and GlassScreen → ¬stimulation(UV) means a glass screen protects against ultraviolet light.

The advantage of such a logical framework is the possibility of representing almost everything in a very natural way that is close to natural language. The tradeoff of this first-order language representation is the combinatorial complexity algorithms. Therefore, it is essential to reduce the expressive power of language.

3.3 Causality and classical inference

Interactions between genes can be seen as a very simple form of causality (Kayser and Levy, 2004). To express basic interactions in logic, it is common to use two binary relations, trigger(A, B) and block(A, B), as well as the ternary relation bind(A, B, C). The first relation means that the protein A triggers or stimulates or activates the production of protein B. The second relation is the inhibition. These two relations are graphically represented by A → B and A B. The third relation means that A and B bind to produce C (in Figure 22.3, for instance, p53 and Mdm2 bind to produce B).

These relations are a basic form of causality. The main purpose of causality is to distinguish between what is caused and what is true. That means that not all inferences obtained are true in the case of biological systems.

In this chapter, we describe and use the simplest logical form of causality, and show that cell modeling can be validated by either biological knowledge or biological experiments. This approach could be improved or replaced by Bayesian approaches or much better probabilistic logics (Sato and Kameya, 2003), and another option is modal logics.

The inferences of classical logic A → B or A B are fully described formally, with all the so-called good logic properties (tautology, noncontradiction, transitivity, contraposition, etc.). But the causality cannot be seen as a classical logic relation. A basic example is “If it rains, the grass is wet.” In classical logic, the formula Rain → LawnWet means that if it rains, the grass is always wet. But this formula is too strong. Indeed, there may be exceptions to this rule (say, if the lawn is under a shed).

In the first approach, the biological events can be expressed naturally as follows:

1. If A trigger B and A is true, then B is true.

2. If A blocks B and A is true, then B is false.

Depending on the context, true can mean what is known, certain, believed, or proved. The first idea is to express these laws in classical logic by two formulas:

$\begin{array}{l}{\mathrm{f}}_1=\mathrm{trigger}\left(\mathrm{A},\mathrm{B}\right)\wedge \mathrm{A}\to \mathrm{B}\\ {\mathrm{f}}_2=\mathrm{block}\left(\mathrm{A},\mathrm{B}\right)\wedge \mathrm{A}\to \neg \mathrm{B}\end{array}$

But this formulation is problematic when there is conflict. Unfortunately, this is often ignored. For example, if we add the three pieces of information: A trigger B, A blocks B and A is true, there is a conflict (inconsistency in logic). These three information are represented by a set of three propositional formulas:

$F=\left\{A,\mathit{trigger}\left(A,B\right),\mathit{blocks}\left(A,B\right)\right\}\text{,}$

From F, implies B and ¬B. This is inconsistent. To solve such incongruencies, we can try to use methods inspired by constraint programming, such as the use of negation by failure of the Prolog programming language. It is also possible to use nonmonotonic logic.

The first method, negation by failure, poses many theoretical and technical problems beyond the simplest examples. These problems are often solved by adding properties to the formal system in keeping with the domino principle. We find here all the classic problems that arise when one wants to try to formalize and use of negation by failure in programming languages such as Prolog or Solar (Nabeshima et al., 2010).

Therefore, we will use here a classical nonmonotonic formalism: the default logic of Reiter (Reiter 1980).

3.4 Causality and nonmonotonic logics

To solve the conflict problem action/reaction simultaneously, the intuitive idea is to weaken the previous formulation as follows:

1. If A triggers B, if A is true, and it is possible that B, then B is true.

2. If A blocks B, if A is true, and it is possible that B is false, then B is false.

The problem is to formally describe what is meant by “possible”. This question began to arise in the study of artificial intelligence 30 years ago, and led to investigations of new types of reasoning. In this type of reasoning, one has to deal with incomplete, uncertain information that is subject to revision and sometimes is false. On the other hand, we must often choose between several possible contradictor conclusions.

One basic example is:

Penguins are birds.

Birds fly.

Penguins do not fly.

In classical logic, we have a contradiction if we know that Tweety flies, and the system is inconsistent. This inconsistency can be accounted for if we can handle the exception by replacing “Birds fly” with “Typically, birds fly”. The nonmonotonic logics formally describe the modes of reasoning that take into account these phenomena.

Classical logic, as first-order logic or modals logic, are monotonic: if it adds information or a formula F to a formula E, everything which was deduced from E will be deducted from E ∪ F. In other words, for monotonic logic, anything that is deduced from information will always be true if we add new information. This property of monotonicity generates inconsistent or revisable information. Indeed, in real life, it will be common to invalidate previously established conclusions when new information is added or changed. Nonmonotonic logic allows us to eliminate the monotony property of the classical logic: conclusions can be revised with the addition of new knowledge.

3.5 Default logic

In this section, we use default logic (Reiter, 1980), which is the nonmonotonic logic most frequently used. This logic can be seen as an improvement and a generalization of the negation by failure in Prolog. It is also a generalization of answer set programming (ASP) formalisms, which appear years later.

Default logic is defined by  = (D, W). The set W is a set of facts that are always true information represented by formulas of propositional logic or first-order logic. The set D is a set of defaults that are inference rules with specific content, which expresses the uncertainty. A default is an expression of the form

$d=\frac{A\left(X\right):B\left(X\right)}{C\left(X\right)}\text{,}$

where A(X), B(X), and C(X) are formulas and X is a set of variables. A(X) is the prerequisite, B(X) is the justification, and C(X) is the consequent. The set X is the set of free variables in d.

Intuitively, the default d means that if A(X) is true, and if it is possible that B(X) is true, then C(X) is true. If B(X) = C(X), the default is normal. Normal default means that normally, A implies B. In this chapter, a default is seminormal if its justification entails its conclusion. The default logic used transforms the previous rules, which are expressed as follows:

1. If A trigger B, if A is true and if B is not contradictory, then B is true.

2. If A blocks B, if A is true and if ¬B is not contradictory, then ¬B is true.

And these rules can be represented by normal defaults, without variables:

$d1=\frac{\mathit{trigger}\left(A,B\right)\wedge A:\neg B}{B}$

$d2=\frac{\mathit{blocks}\left(A,B\right)\wedge A:\neg B}{\neg \mathrm{B}}$

Therefore, a signaling pathway is represented here using a default theory  = {W, D}, where W is a set of classical logic formula and D is the set of defaults.

3.6 Extensions and choice of extensions

The goal of default logic is to find extensions of a default theory  = {W, D}. An extension E is a consistent set of formulas obtained by adding to W, under specific conditions, a maximal set of consequents of D. An extension can for example, represent a subgraph of the gene pathways constituted in network without conflict. The definition of extension is based on the utilization of W and a subset of defaults D.

Formally, E is an extension of if and only if

$E={\bigcup }_{i=0}^{\infty }{E}_i\text{,}$

With

$1)E_0=W$

$2)E_{i+1}=Th\left(E_i\right)\cup \mathrm{C}/\left\{d=\frac{A:B}{C}D,A\in E_i,\neg \mathrm{B}\notin \mathrm{E}\right\}\text{.}$

Here, Th(E_i) is the set of formulas derived from E_i in classical first-order logic.

The previous definition is difficult to use in practice. Indeed, in the latter condition, ¬B ∉ E supposes that E is known, while E is not yet calculated. In this case, an extension is a fixed point. But if all defaults are normal, the last condition can be replaced by ¬B ∉ Th(E_i). The verification of the condition is possible and extension to build. In practical terms, an extension is built starting with W and adds a maximal consistent set of consequents of D. The condition to use a normal default $d=\frac{A:B}{B}$ starts by checking if, in the current state, the prerequisite A is verified as B, and B does not lead to contradiction. In a simple manner, B does not lead to contradiction, meaning ¬B (the negation of B) is not verified. If this request is True, we add the consequent B to W, and the algorithm is restarted until all defaults have been used or rejected.

For example, if we consider  = {W, D} with

$\mathrm{W}=\left\{\mathrm{A},\mathrm{trigger}\left(\mathrm{A},\mathrm{B}\right),\mathrm{block}\left(\mathrm{A},\mathrm{B}\right)\right\}$

and

$D=\left\{d1,d2\right\}\mathrm{given}\mathrm{above}\text{,}$

it is impossible to use d1 and d2 in the same extension. Indeed, if d1 is used, B is added to the extension, and it is impossible to use d2 because ¬ ¬B = B is verified. Similarly, if d2 is used, it is impossible to use d1. However, it is possible to use a single default. Therefore, we obtain two extensions: E1, which contains B, and E2, which contains ¬B:

$\begin{array}{l}E1=\left\{A,\mathit{trigger}\left(A,B\right),B\right\}\mathrm{if}d1\mathrm{is}\mathrm{used}.\\ E2=\left\{A,\mathit{block}\left(A,B\right),\neg B\right\}\mathrm{if}d2\mathrm{is}\mathrm{used}\text{.}\end{array}$

By using default logic, the conflict is resolved, and we obtain two contradictory solutions.

But it is not possible to rank the extensions: Is B true or false? In fact, this will depend on the context. For biologists, sometimes the negative interactions are preferred to the positive ones (or vice versa). Another possibility is to use probabilistic or statistical methods to weigh each extension based on the evaluation of the knowledge. From an algorithmic viewpoint, the ranking of extensions also can be evaluated through the calculation of these extensions; and even offline ranking is preferred.

5.1 Clauses and Horn clauses

The logic plays with atoms building relation R(A1, .., An). If the atoms are signed, they are called literals: positives R(A1, .An) or negatives ¬R(A1, ..An).

In our representation, product(P53) is an atom. It is also a positive literal, meaning that the protein p53 increases in concentration. The ¬product(P53) is a negative literal, which means that it is not possible to determine if the p53 concentration increasing. In this model, activation is related to the increase in concentration. The dynamic of the system, for example, can be specified by concentration (p53,100,T), which means the concentration of p53 at the time T equals 100 a.u., and ¬concentration(P53,sup(200),T + 3) says that at the time T + 3, the concentration of p53 is not greater than 200 a.u.

Clauses are the simplest type of formula. Formally, a clause is a disjunction of literals $1\vee ..\vee ln$. If the connectors are forgetters, a clause is a set or a list of literals. For example {a, ¬b, ¬c, d} or a ¬b ¬c d represents $a\vee \neg b\vee \neg c\vee d$. A Horn clause is a clause with a maximum of one positive literal. The clauses a and ¬b ∨ ¬c ∨ d and ¬b ∨ ¬c are Horn clauses, and a ∨ b is not. For the rest, we use Horn clauses, which are interesting for two reasons.

First, using Horn clauses is a natural way to represent knowledge. In fact, the formula a ∧ b ∧ c ∧ d → d is equivalent to the Horn clause ¬a ∨ ¬b ∨ ¬c ∨ d. Similarly, the formula ¬(a ∧ b) (a and be cannot be true simultaneously) is equivalent to the negative Horn clause ¬a ∨ ¬b.

The second advantage of Horn clauses, which is fundamental in this discussion, is that their use drastically reduces the computational complexity. Indeed, any logical formula can be rewritten as a set of clauses, so complexity problems may arise in terms of clauses. In propositional calculus, the basic problem is whether a set of clauses is consistent. This is the Satisfiability problem, which is NP-complete. Otherwise, all known algorithms are exponential in the worst case. On the other hand, if all clauses are Horn causes, algorithms can be linear proportional to the size of the data. For gene pathways, the use of Horn clauses provides practically usable algorithms.

Clearly, Horn clauses cannot represent all formulas. In particular, a ∨ b is not a Horn clause. But this type of positive disjunctive information is quite rare in practice. To be more explicit, in the case of DNA DSBs, all biological reactions can be represented using Horn clauses. Even in the case of non-Horn clauses, it is possible to solve the problem by using efficient techniques, which come from constraint programming and from practical algorithms for solving NP-complete problems. These techniques may be, for example, using cardinalities, symmetries (Benhamou and Siegel, 2008) (Benhamou et al., 2010), and strong backdoors (Ostrowski et al., 2010).

In fact, the use of Horn clauses and default logic has been studied for an application with the DCNS group (DCNS is the main French group that designs, builds, and supports surface combatants, submarines, systems, and equipment). The problem was to simulate the decisions of a commander aboard a submarine in wartime. This is a problem of incomplete information because a submarine is “blind” and almost “deaf,” but it must make quick decisions, so to speak. Using Horn clauses, default logic, mutual exclusion, and simple management of the temporal aspect, it was possible to simulate several hours of fighting in seconds (Toulgoat et al., 2010a, 2010b; Toulgoat, 2011).

5.2 Language syntax

A signaling pathway is described by a set of rules. A rule can be either a hard rule, a default. Pratically a rule is a triplet (<type>, <corps>, <weight>) for which:

• < type > can take two values: hard and def. If the value is hard, the rule is a hard rule and represents a Horn clause, which is sure and nonrevisable. If the value is def, the rule represents a normal default.

• < weight > weighs the rule, which makes it possible to choose between the different extensions proposed by the algorithm.

• < corps > is a couple (L, R). The left element L is a set of literals (l1, ..ln) eventually empty. This set is identified to l1 ∧ .. ∧ ln. The right element R is either a single literal or empty. If the rule is hard, the couple (L, R) represents the formula L → R. If the rule is a default, the couple represents a normal default $d=\frac{L:R}{R}$ Increased attention is made given these two cases.

5.4 Cell signaling pathway representation

We have based our work on the bibliographic data of the response to DSBs represented on a signaling pathway (see Figure 22.2 earlier in this chapter), given by Pommier et al. (2005). The drawback of this representation is that it is very difficult to add a new interaction or protein without full reassessment. In particular, the management of conflicts (such as simultaneous trigger and block interactions) is very difficult. We worked on the translation of this interaction map in our logic language. Initial results have translated this signaling pathway, and some algorithms have been tested (Doncescu and Siegel, 2012; Doncescu et al., 2012a, 2013, 2014a, 2014b).

Today, the signaling pathway is translated by 206 rules in a very natural way, without having to tweak the predicates or the rules. The rules are expressed in the syntax given previously in this chapter. These rules can be hard rules or defaults. The syntax used is very simple, and it is possible to change the nature of these rules to test different configurations. We can calculate the extensions in a very short time. As it turns out, the use of non-Horn clauses was not necessary. This reinforces our opinion that it is possible to use a nonmonotonic logic and abduction and time on real applications.

In the case of signaling pathways, we consider a predicate to be a biological reaction or the production and activation of proteins. For example:

• product(P), binding(P, Q, R), block-binding(P, Q), stimulation(P),

• phosphorylation(P), dissociation, transcription-activating,

• increase(P), decrease(P)…

• concentration(P, > 1000), where 1000 is a threshold if it is possible to measure it.

The logical model of DNA DSB contains two types of rules: facts (hard) and defaults (def). For example:

• hard: stimulate(dsb, dna) that is an elementary fact (a ground unary clause) says that DSB stimulates ADN.

• def: stimulate(dsb, dna) → product(altered-dna). This default rule means, “(Generally when dsb (double-strand breaks) stimulates DNA, an altered DNA is produced). For example, during replication, a thymine nucleotide might be inserted in place of a guanine nucleotide. With base substitution mutations, only a single nucleotide within a gene sequence is changed, so only one codon is affected.”

• hard: product(p-atm-atm-bound) → ¬product(atm-atm) that is a negative clause. def: product(p-s15-p53-mdm2) ∧ product(p-chk1). → phosphorylation(p-chk1, →p-s15-p53-mdm2).

Using a simple logic formalism can express much of what biologists need to represent.