Loïc Paulevé
email: loic.pauleve@irccyn.ec-nantes.fr

Morgan Magnin
email: morgan.magnin@irccyn.ec-nantes.fr

Olivier Roux
email: olivier.roux@irccyn.ec-nantes.fr

Refining Dynamics of Gene Regulatory Networks in a Stochastic π-Calculus Framework

In this paper, we introduce a framework allowing to model and analyse efficiently Gene Regulatory Networks (GRNs) in their temporal and stochastic aspects. The analysis of stable states and inference of René Thomas' discrete parameters derives from this logical formalism. We offer a compositional approach which comes with a natural translation to the Stochastic π-Calculus. The method we propose consists in successive refinements of generalised dynamics of GRNs. We illustrate the merits and scalability of our framework on the control of the differentiation in a GRN generalising metazoan segmentation processes, and on the analysis of stable states within a large GRN studied in the scope of breast cancer researches.

Introduction

Modelling, analysis and numerical or stochastic simulations are a usual means to predict the behaviour of complex living systems such as interacting genes.

Regulations between genes (activation or inhibition) are generally represented by Gene Regulatory Network (GRN) graphs. However, a GRN graph is not enough to describe dynamics. In continuous frameworks such as ordinary differential equations, parameters for differential equations are needed. In logical (or qualitative) frameworks such as boolean or discrete networks, dynamics are driven by René Thomas' parameters or equivalent [START_REF] Richard | Formal Methods for Modeling Biological Regulatory Networks[END_REF].

Hybrid modelling brings quantitative aspects -such as temporal or stochastic parameters -to logical modelling. In the field of formal languages, κ language [START_REF] Danos | Rule-Based Modelling of Cellular Signalling[END_REF] or Stochastic π-Calculus [START_REF] Priami | Application of a stochastic name-passing calculus to representation and simulation of molecular processes[END_REF][START_REF] Kuttler | Gene regulation in the pi calculus: Simulating cooperativity at the lambda switch[END_REF][START_REF] Blossey | A compositional approach to the stochastic dynamics of gene networks[END_REF] bring theoretical Computer Science frameworks for biological modelling. In the field of formal verifications of biological systems, frameworks like Time or Stochastic Petri Nets [START_REF] Popova-Zeugmann | Time petri nets for modelling and analysis of biochemical networks[END_REF][START_REF] Heiner | Petri Nets for Systems and Synthetic Biology[END_REF], Biocham [START_REF] Rizk | On a continuous degree of satisfaction of temporal logic formulae with applications to systems biology[END_REF], Timed Automata [START_REF] Siebert | Incorporating time delays into the logical analysis of gene regulatory networks[END_REF], Charon (Hybrid Modelling) [START_REF] Alur | Modeling and analyzing biomolecular networks[END_REF] and Linear Hybrid Modelling [START_REF] Ahmad | Hybrid modelling and dynamical analysis of gene regulatory networks with delays[END_REF] bring the first bricks for verifying and controlling dynamics of such systems.

Inference of temporal and stochastic parameters is still challenging as the domain of parameters is continuous and its volume generally grows exponentially with the number of genes. Compositional approaches, inherent to process algebras, aspire at reducing this complexity by allowing a local reasoning.

Our aim is temporal parameters synthesis for verifying formal properties on hybrid models.

Our contribution consists in the introduction of both temporal and stochastic parameters into process algebra models of GRNs through a new Stochastic π-Calculus framework: the Process Hitting framework.

Starting from a GRN without any other parameters, its largest dynamics are expressed in Process Hitting and then are refined to match the expected behaviour. Such a refinement is achieved by constructing cooperativity between genes and by creating stable states. As we will show, detecting stable states of a Process Hitting is straightforward, as well as infering the René Thomas' discrete parameters K.

Moreover, the Stochastic π-Calculus naturally brings time and stochasticity into our Process Hitting framework. We introduce a stochasticity absorption factor to highlight either the temporal or stochastic aspect of reactions. The direct translation of Process Hitting to the Stochastic π-Calculus allows simulations of such models by softwares like BioSpi [START_REF] Priami | Application of a stochastic name-passing calculus to representation and simulation of molecular processes[END_REF] or SPiM [START_REF] Phillips | Efficient, correct simulation of biological processes in the stochastic pi-calculus[END_REF].

Several points motivate the choice of the Stochastic π-Calculus framework for introducing the Process Hitting. The Stochastic π-Calculus can be considered as a "low-level" process algebra: there are very few operators compared, for instance, to the Beta Workbench [START_REF] Dematte | The Beta Workbench: a computational tool to study the dynamics of biological systems[END_REF] or Bio-PEPA [START_REF] Ciocchetta | Bio-pepa: A framework for the modelling and analysis of biological systems[END_REF]. This makes the presentation of the Process Hitting as a Stochastic π-Calculus framework more generic. Moreover, the Stochastic π-Calculus comes with a bunch of established tools as previously cited and translations into various framework have already been formalized, such as to PRISM, a probabilistic model checking tool [START_REF] Hinton | PRISM: A tool for automatic verification of probabilistic systems[END_REF][START_REF] Norman | Model checking probabilistic and stochastic extensions of the π-calculus[END_REF]. This paper is structured as follows. Section 2 introduces our framework and how it is used to build the generalised dynamics of a GRN. Section 3 presents dynamics refinement techniques and Section 4 shows how infering the René Thomas' parameters leading to such dynamics. Introduction of both temporal and stochastic parameters within Process Hitting models is addressed in Section 5. The overall approach is illustrated by two applications in Section 6. The first applies the refinement method to a toy GRN involved in biological segmentations phenomena. The temporal and stochastic parameters are then infered to bring a particular behaviour to the system. The second application shows the scalability of the Process Hitting framework by modelling a large GRN composed of 20 genes.

Notations Given a set S, n S × • • • × S, will be abbreviated as S n . If S is finite and countable, we note |S| its cardinality. Given a n-tuple C, C[x/y] refers to the n-tuple C within the element y has been substituted by x. Belonging and cartesian product for n-tuples are defined similarly to sets. [x i ; x i+n ] refers to the interval {x i , x i+1 , . . . , x i+n }. '∧' stands for the logical and connector.

Generalised Dynamics for Gene Regulatory Networks

First, we recall the basis of the René Thomas' discrete modelling framework from which we designed our refinement approach. This method is described in subsections 2.2 and 2.3. This leads to a straightforward translation into the π-Calculus which makes it possible to express generalised dynamics of GRNs.

Gene Regulatory Networks

GRNs are often described by interaction graphs where nodes are genes with activation and inhibition relations respectively represented by positive and negative edges [START_REF] Richard | Formal Methods for Modeling Biological Regulatory Networks[END_REF][START_REF] Bernot | Semantics of biological regulatory networks[END_REF].

In the discrete framework of René Thomas, each gene has at least two qualitative levels. The influence of an activating (resp. inhibiting) gene on its target depends on a threshold value: when the level of the gene is greater or equal than the threshold, the gene holds a positive (resp. negative) effect; when the level of the gene is lower than the threshold, the gene holds a negative (resp. positive) effect [START_REF] Richard | Formal Methods for Modeling Biological Regulatory Networks[END_REF].

Definition 1 (Gene Regulatory Network Graph). A Gene Regulatory

Network graph is a triple (Γ, E + , E -) where Γ is the finite set of genes and a t -→ b ∈ E + (resp. E -), t positive integer, if and only if the gene a above level t is an activator (resp. inhibitor) for b. We note a i the level i of the gene a.

Given a GRN graph (Γ, E + , E -), the maximum qualitative level for gene a ∈ Γ is noted a la where l a is the highest threshold involved in its regulations:

l a = max({t | ∃b ∈ Γ, a t - → b ∈ E + ∪ E -}) . (1)
We denote levels + (a, b) (resp. levels -(a, b)) the set of levels of a where a effectively activates (resp. inhibits) b.

Definition 2 (Effective Levels). If a t - → b ∈ E + , levels + (a, b) = [a t ; a la ] and levels -(a, b) = [a 0 ; a t-1 ]. If a t - → b ∈ E -, levels + (a, b) = [a 0 ; a t-1 ] and levels -(a, b) = [a t ; a la ]. Else levels + (a, b) = levels -(a, b) = ∅.

The Process Hitting Framework

We want to describe the action of a gene at a given level on another one. If the gene a at a given level i is an activator for b, it has a positive action on b, meaning the level of b will tend to increase. Conversely if a at a level i ′ is an inhibitor for b, it has a negative action on b and then the level of b will tend to decrease.

The action is "a at level i making b at level j increase (or decrease) to level k". We say a i hits b j to make it bounce to b k and note this action a i → b j b k . In the process hitting framework, a i , b j , b k are refered as processes and a, b as sorts. Sorts can represent genes, but also logical entities, as described in further sections.

Definition 3 (Action). An action is noted a i → b j b k where a i is a process of sort a and b j = b k two processes of sort b. a i → b j is the hit part, and b j b k the bounce part. When a i = b j , such an action is refered as a self-action and a i is called a self-hitting process.

In this paper, one and only one process of each sort is present at any instant. Hence, hits between different processes of a same sort are prohibited. The set of these living processes gives the state of the Process Hitting.

Definition 4 (Process Hitting). A Process Hitting PH is a triple (Σ, L, H):

-Σ = {a, b, . . . } is the finite countable set of sorts, -L = a∈Σ L a is the set of states for PH, with L a = {a 0 . . . a la } the finite and countable set of processes of sort a ∈ Σ and l a a positive integer, a = b ⇒

a i = b j ∀(a i , b j ) ∈ L a × L b , -H = {a i → b j b k , • • • | (a, b) ∈ Σ 2 , (a i , b j , b k ) ∈ L a × L b × L b , b j = b k , a = b ⇒ a i = b j }, is the finite set of actions.
At a given state s ∈ L, an action a i → b j b k is playable if both processes a i and b j are present in s. When this action is played, the process b k replaces b j .

Definition 5 (Next States). Let (Σ, L, H) be a Process Hitting and s ∈ L be one of its states. The set of the next possible states for s are computed as follows:

next(s) = {s[b k /b j ] | ∃(a i , b j ) ∈ s 2 , ∃b k ∈ L b , a i → b j b k ∈ H} .
Definition 6 (Stable state). Let PH = (Σ, L, H) be a Process Hitting and s ∈ L be a state, s is a stable state for PH if and only if next(s) = ∅.

Graphical Representations of a Process Hitting

We set up two complementary graphical representations of a Process Hitting. The first one exhibits the actions between process levels, the second one points out the absence of hits between them. We finally define the State Graph of a Process Hitting. Figure 1 shows an instance for each of these three representations.

Given a Process Hitting (Σ, L, H), its Hypergraph represents each action a i → b j b k ∈ H by a directed hyperedge from a i to b k passing by b j . The hit part (a i to b j ) is drawn as a plain edge and the bounce part (b j to b k ) as a dotted edge.

Definition 7 (Process Hitting Hypergraph). The Hypergraph of a Process Hitting (Σ, L, H) is a couple (P, A) where P = a∈Σ L a are the vertices and A ⊆ P 3 the directed hyperedges given by

A = {(a i , b j , b k ) | a i → b j b k ∈ H}.
In the following we introduce a complementary representation we call Hitless Graph. It will allow us to obtain extra results such as the stable states of a Process Hitting (Section 3.2). The Hitless Graph of a Process Hitting (Σ, L, H) relates two processes of different sorts if and only if they hit neither each other nor themselves. Vertices of a Hitless Graph may be split into n ≤ |Σ| partitions having no element inside related to each other: a partition is, for any sort, a subset of its processes without self-actions. Such a graph is called n-partite.

Definition 8 (n-Partite Graph). A graph G = (V, E) is n-partite if and only if V = n k=1 V k , V k = ∅, ∀1 ≤ k, k ′ ≤ n, V k ∩ V k ′ = ∅ and (a i , b j ) ∈ E ⇒ ∃1 ≤ k = k ′ ≤ n, a i ∈ V k ∧ b j ∈ V k ′ .
Definition 9 (Hitless Graph). Given a Process Hitting PH = (Σ, L, H), its Hitless Graph PH = (V, E) is defined as a non-directed graph where the vertices V and edges E are computed as follows:

V = a∈Σ {a i ∈ L a | ∀a i ′ ∈ L a ∄ a i → a i a i ′ ∈ H} E = {(a i , b j ) ∈ V 2 | a = b ∧∀b j ′ ∈ L b ∄ a i → b j b j ′ ∈ H ∧ ∀a i ′ ∈ L a ∄ b j → a i a i ′ ∈ H} . Property 1. By construction of V and E, PH is a n-partite graph, n ≤ |Σ|,
where each partition is a subset of processes for one and only one sort and to each sort corresponds at most one partition.

We also define the n-cliques of a graph which are subsets of n vertices such that each element is related to each other.

Definition 10 (n-Clique). Given a graph

G = (V, E), C ⊆ V is a |C|-clique of G if and only if ∀(a i , b j ) ∈ C 2 , {a i , b j } ∈ E.
Property 2. n-cliques of a n-partite graph have one and only one vertex in each partition.

Finally, the State Graph of a Process Hitting represents the possible transitions between each couple of its states.

Definition 11 (State Graph). Given a Process Hitting

(Σ, L, H), its State Graph is a directed graph S = (L, E ⊆ L 2 ) with (s, s ′ ) ∈ E ⇔ s ′ ∈ next(s).

From Process Hitting to the π-Calculus

A main advantage of our approach is its natural translation to the π-Calculus.

In this subsection we propose a method to translate any Process Hitting into a π-Calculus expression.

We briefly present the fragment of the π-Calculus which is sufficient for translating a Process Hitting. The full syntax for π-Calculus and examples can be found in [START_REF] Blossey | A compositional approach to the stochastic dynamics of gene networks[END_REF][START_REF] Milner | A calculus of mobile processes, parts. I and II[END_REF]. π-Calculus expressions compose two kinds of objects: independently defined processes and channels shared by some processes. A process P has the capability to output (resp. input) on a channel γ and then become P ′ , noted !γ.P ′ (resp. ?γ.P ′ ). Output and input are synchronized operations, i.e. an outputting process is blocked until another process inputs on the same channel. A process can also execute an internal action (τ ), nil operation (0) or one amongst several (P ′ + P ′′ ).

Let PH = (Σ, L, H) be a Process Hitting. For each process a i of PH, a π-Calculus process A i is defined as follows. For each action a i → b j b k ∈ H where a = b, a new channel γ α is created. The π-Calculus process A i has the ability to output on this channel and the π-Calculus process B j has the ability to input on this channel so as to become B k (2). For each self-action a i → a i a j ∈ H, A i has the ability to become A j after performing an internal action τ α (3).

A i ::= α=a i → b j b k ∈H a =b !γ α .A i + α=b j → a i a k ∈H a =b ?γ α .A k (2)
+ α=a i → a i a k ∈H τ α .A k (3)

Generalised Dynamics for Gene Regulatory Networks

Our method to analyse GRNs takes benefit from the use of refinement techniques. Starting from the largest set of possible dynamics for the GRN, we gradually take into account only the specified behaviours and exclude the other ones, thus leading to a restrictive process. We call this largest set of dynamics the generalised dynamics for the GRN graph. It is described by the following rules: the level of a gene increases (resp. decreases) if and only if at least one of its activators (resp. inhibitors) is present. The absence of activators is equivalent to the presence of one inhibitor.

Let G = (Γ, E + , E -) be a GRN graph. For all (a, b) ∈ Γ 2 , we build the set of actions H b a from a to b reflecting the rules above:

-If a t - → b ∈ E + ,
all processes of sort a below the threshold t hit all processes of sort b but b 0 to make them decrease to the level below. Moreover, all processes of sort a above the threshold t hit all processes of sort b but b l b to make them increase to the level above:

H b a = {a i → b j b j-1 | 0 ≤ i < t, 1 ≤ j ≤ l b } ∪ {a i ′ → b j ′ b j ′ +1 | t ≤ i ′ ≤ l a , 0 ≤ j ′ < l b } .
-If a t -→ b ∈ E -, the actions are defined similarly to the previous case except for the bounce directions which are reversed:

H b a = {a i → b j b j+1 | 0 ≤ i < t, 0 ≤ j < l b } ∪ {a i ′ → b j ′ b j ′ -1 | t ≤ i ′ ≤ l a , 1 ≤ j ′ ≤ l b } . -If b = a and ∄c ∈ Γ, c t - → b ∈ E -∪ E +
, gene b lives in absence of activators: all processes of sort b but b 0 hit themselves to decrease to the level below.

H b b = {b i → b i b i-1 | 1 ≤ i ≤ l b } . -Obviously, if a t - → b / ∈ E -∪ E +
for any t and the previous case does not hold, we define H b a = ∅. The Process Hitting for the generalised dynamics of G is given by

PH = (Γ, a∈Γ {a 0 , . . . , a la }, (a,b)∈Γ 2 H b a ) .

Refining Dynamics of Gene Regulatory Networks

We present two methods which aim at narrowing the set of dynamics of a Process Hitting for a GRN: the first one is based on cooperativity between genes, the other one deals with the knowledge of the stable states.

Cooperative Hits

Given two genes c and f regulating a gene a, the action of c on a may depend on the level of f : there exists a cooperativity between c and f on a. In discrete frameworks, the cooperativity is often described by a boolean function between genes levels [START_REF] Richard | Formal Methods for Modeling Biological Regulatory Networks[END_REF][START_REF] Bernot | Gene regulatory networks with multiplexes[END_REF]. We show how to build cooperativity within Process Hitting. Let (Σ, L, H) be a Process Hitting and σ ⊂ Σ be a set of sorts cooperating on a given process a k to make it bounce to a k ′ . The set of all states of the cooperating sorts is denoted by S = z∈σ L z . The subset of states where the cooperativity is effective is defined by ⊤ ⊂ S.

For applying this cooperation, a new sort is added to the Process Hitting. This sort is called a cooperative sort and is refered as υ. The set of processes of sort υ is defined by L υ = {υ ς , ∀ς ∈ S}. Each process z i of sort z ∈ σ hits processes υ ς of the cooperative sort υ where z i / ∈ ς to make it bounce to υ ς[zi/zj ] , z j ∈ ς. We denote H σ the set of such actions [START_REF] Kuttler | Gene regulation in the pi calculus: Simulating cooperativity at the lambda switch[END_REF]. In this way, the process of sort υ reflects the current state of its representatives.

The cooperativity between υ processes is added into the Process Hitting by replacing hits H coop from processes of sorts present in σ to c k (5) by hits H ′ coop from processes of the cooperative sort υ selected in ⊤ (6).

H σ = {z i → υ ς υ ς[zi/zj ] | ∀z ∈ σ, ∀(z i , z j ) ∈ L 2 z , ∀υ ς ∈ L υ , z j ∈ ς} (4) H coop = {z i → a k a k ′ ∈ H | ∀z ∈ σ} (5) H ′ coop = {υ ς → a k a k ′ | ∀ς ∈ ⊤} . (6)
The resulting Process Hitting is

(Σ ∪ {υ}, L × L υ , (H \ H coop ) ∪ H σ ∪ H ′ coop ). Example 1. Let ({f, c, a}, {f 0 , f 1 } × {c 0 , c 1 } × {a 0 , a 1 }, H) be a Process Hitting where {f 1 → a 0 a 1 , c 0 → a 0 a 1 } ⊂ H.
The creation of a cooperativity between f 1 and c 0 on a 0 (σ = {f, c}, ⊤ = {f 1 c 0 }) is illustrated by Figure 2.

Stable State Pattern

Given a Process Hitting (Σ, L, H), we prove the |Σ|-cliques of its Hitless Graph are exactly its stable states. Thus, stable states may be created by removing from the Process Hitting the very hits that make such patterns appear. Proof. By definition, next(s) = ∅ if and only if there is no hit between any couple of processes present in s. This is equivalent to have s a clique of PH.

Figure 3 shows an instance of Process Hitting having one stable state.

We outline an algorithm for finding the n-cliques of a Hitless Graph PH = (V, E) where n = |Σ|.

Thanks to Prop. 1, we split V into n partitions corresponding to each process:

V = ∪ a∈Σ V a , V a ⊆ L a .
If one of this partition is empty, there can not be ncliques as it requires to have at least one vertex in each partition. We will assume V a = ∅, ∀a ∈ Σ.

For each partition a ∈ Σ and each vertex a i ∈ V a , we define

E b ai = {b j ∈ V b | (a i , b j ) ∈ E} for each other partition b ∈ Σ, b = a, the set of vertices in V b related to a i . If there exists b ∈ Σ such that E b ai = ∅,
the vertex a i is removed from candidates as it can not belong to a n-clique. Finally, we set E a ai = {a i }. Once this pruning is performed, we enumerate potential n-cliques. To reduce this enumeration, we choose the partition a sharing the least number of edges. For each vertex a i ∈ V a we test for all s ∈ b∈Σ E b ai if s is a clique of PH. For instance in Figure 3 The Hitless Graph contains only one 3-clique between a2, b1 and c0 (thick lines): this is the only stable state of this system.

From Process Hitting to René Thomas' Parameters

A René Thomas' discrete parameter gives the attractor levels for a gene when its regulators are in a given configuration. Many frameworks and tools dedicated to the study of GRNs take the full set of René Thomas' parameters as essential input [START_REF] Richard | Formal Methods for Modeling Biological Regulatory Networks[END_REF][START_REF] Siebert | Incorporating time delays into the logical analysis of gene regulatory networks[END_REF][START_REF] Ahmad | Hybrid modelling and dynamical analysis of gene regulatory networks with delays[END_REF]. In this section, we give a formal method to infer René Thomas' parameters for a GRN modelled in the Process Hitting framework. Let (Γ, E + , E -) be a GRN graph. A René Thomas' parameter K a,A,B , a ∈ Γ, A ∪ B ⊆ Γ, A ∩ B = ∅, gives the interval of attracting levels for a when genes in A are activating a and genes in B are inhibiting a. In this configuration, if the level of a is in K a,A,B , then it will never change; otherwise the level of a will tend to a level in K a,A,B .

Let (Σ, L, H) be a Process Hitting where sorts are standing either for genes or for cooperative sorts, i.e. Σ = Γ ∪ {σ 1 , . . . , σ u } with ∀1 ≤ v ≤ u, σ v ⊂ Γ . Let K a,A,B be the René Thomas' parameter to infer. For each sorts b ∈ A ∪ B, its context C b a,A,B is defined as the subset of processes L b imposed by the René Thomas' parameter: if b ∈ A (resp. B) only processes corresponding to positive (resp. negative) effective levels (Def. 2) are allowed. For each process b ∈ Γ not regulating a (i.e. b / ∈ A ∪ B), its context C b a,A,B is simply L b [START_REF] Heiner | Petri Nets for Systems and Synthetic Biology[END_REF]. The context C σ a,A,B for cooperative sorts σ ∈ {σ 1 , . . . , σ u } is the set of states of its representatives in their context [START_REF] Rizk | On a continuous degree of satisfaction of temporal logic formulae with applications to systems biology[END_REF].

∀b ∈ Γ, C b a,A,B =      levels + (b, a) if b ∈ A, levels -(b, a) if b ∈ B, L b otherwise. ( 7
) ∀σ ∈ {σ 1 , . . . , σ u }, C σ a,A,B = {σ ς | ∀ς ∈ b∈σ C b a,A,B } . (8)
We denote H a,A,B the subset of the set of actions H on a that may be performed by processes of the context of any sort [START_REF] Siebert | Incorporating time delays into the logical analysis of gene regulatory networks[END_REF]. A process of sort a is reachable if it belongs to the context of a or is the result of any action in H a,A,B . The set of such processes is noted L ? a,A,B [START_REF] Alur | Modeling and analyzing biomolecular networks[END_REF]. The set of reachable processes of sort a not hit by any other processes is noted L * a,A,B [START_REF] Ahmad | Hybrid modelling and dynamical analysis of gene regulatory networks with delays[END_REF]. Thus, as long as present processes are in the context of their sort, if a process of sort a is in L * a,A,B , it will not be bounced. In this way, L * a,A,B is called the set of focal processes of a.

H a,A,B = {b i → a j a k ∈ H | b i ∈ C b a,A,B ∧ a j ∈ C a a,A,B } (9)
L ? a,A,B = C a a,A,B ∪ {a k | ∀b i → a j a k ∈ H a,A,B } (10)
L * a,A,B = L ? a,A,B \ {a j | ∀b i → a j a k ∈ H a,A,B } . (11)
Finally, we check that the focal processes are attractors, i.e. all actions H a,A,B make processes of sort a bounce in the direction of the focal processes. If such a condition is satisfied, the focal processes correspond to the value of the requested René Thomas' parameter. We point up that all these operations are linear with the number of actions in the Process Hitting.

Condition 1 (Focal processes are attractors). ∀b

i → a j a k ∈ H a,A,B , ∀a f ∈ L * a,A,B , |f -k| < |f -j| . Property 3. If L * a,A,B satisfies Cond. 1, L * a,A,B is an interval. Proof. If L * a,A,B = {a f , . . . , a f ′ } is not an interval, there exists b i → a j a k ∈ H a,A,B such that f < j < f ′ . If Cond. 1 applies, we have |f -k| < |f -j| ⇒ k < j ⇒ |f ′ -k| > |f ′ -j| which contradicts Cond. 1. Theorem 2. If L * a,A,B = ∅ and Cond. 1 holds, then K a,A,B = L * a,A,B .
Proof. By construction of L * a,A,B and application of Cond. 1 and Prop. 3, it immediately appears that if L * a,A,B = ∅, it is the set of attracting levels for a.

Consequently, there might exist configurations without any correspondence with René Thomas' parameters. First, L * a,A,B = ∅ means the gene a is unstable in the fixed context, i.e. its level is changing forever. Second, Cond. 1 is violated when there exists opposite focal processes, i.e. the fate of a is not deterministic.

One of the main reasons for non-determinism of Process Hitting is the absence of cooperativity between hits to a same target which may then independently be bounced to both higher and lower processes. We leave as an open question the problem to know whether such unstable and/or non-deterministic dynamics are biologically relevant.

Temporal and Stochastic Parameters

Further dynamics refinements may be achieved by taking into account the temporal and stochastic dimensions of biological reactions. On the one hand, we may consider the probability of a reaction to occur at a given state. By introducing stochastic parameters into discrete models, we aim at computing the probability of observing an expected behaviour. On the other hand, because they are faster, some reactions always apply before others. By introducing temporal parameters into discrete models, we aim at reducing their dynamics to match such behaviours.

From Process Hitting to the Stochastic π-Calculus

The Stochastic π-Calculus [START_REF] Priami | Stochastic π-Calculus[END_REF] adds the capability to attach use rates to channels and internal actions of the π-Calculus. This gives a natural introduction for temporal and stochastic aspects in our Process Hitting framework.

A use rate controls both the duration and the probability of a reaction (communication on a channel or internal action). It is associated to a probability distribution for firing reaction along the time. The usual probability distribution is the exponential one, allowing efficient simulations through a Gillespie-like algorithm [START_REF] Phillips | Efficient, correct simulation of biological processes in the stochastic pi-calculus[END_REF][START_REF] Gillespie | Exact stochastic simulation of coupled chemical reactions[END_REF]. This is the one we consider for the rest of this paper.

The probability along time t of firing a reaction with use rate r is given by F (t) = 1e -rt . The average duration of this reaction is r -1 with a variance of r -2 . When x reactions are possible having use rates of r 1 , . . . , r x respectively, the probability that the y th reaction is fired is given by ry r1+•••+rx . The translation of Process Hitting (Σ, L, H) into the Stochastic π-Calculus is the same as the one presented in Section 2.4. Additionally, to each channel γ α , or internal action τ α , a use rate r α is attached.

Stochasticity Absorption

Use rates are both temporal and stochastic parameters. Nonetheless, these two aspects are closely tied: the lower a use rate is, the higher the variance around its mean duration is. We introduce a stochasticity absorption factor to control this variance to favour either the stochastic or the temporal behaviour of an action.

We propose to replace the exponential distribution of a reaction with a rate r by the distribution of the sum of sa random variables each having an exponential distribution of parameter r.sa. The resulting probability distribution is also known as the Erlang distribution. The average duration is unchanged: (r.sa) -1 sa = r -1 , but the variance is divided by sa: (r.sa) -2 sa = r -2 sa -1 . sa stands for the stochasticity absorption factor. Based on the previously presented translation from the Process Hitting to the Stochastic π-Calculus, we supply a simple method to achieve this stochasticity absorption factor which do not require to adapt simulation algorithms based on the memoryless property of the exponential law [START_REF] Priami | Stochastic π-calculus with general distributions[END_REF].

Basically, to each channel γ α , or internal action τ α , a use rate r α and a stochasticity absorption factor sa α is attached. To each component α of the sum defined by the π-Calculus process A i in the expressions (2),(3), a counter c α is attached, initially, c α = 1. This counter is given as a parameter for A i . As long as this counter is not equal to sa α , A i is restarted and the counter is incremented by one. When the counter reaches the stochasticity absorption factor value, the next process replaces A i , having all its counters reset to 1. Let (Σ, L, H) be a Process Hitting, for each process a i of PH, a π-Calculus process A i is defined as follows.

A i (c) ::= α=a i → b j b k ∈H a =b !γ α .A i (c) + α=b j → a i a k ∈H a =b [c α < sa α ]?γ α .A i (c[c α + 1]) + [c α = sa α ]?γ α .A k ( 1) + α=a i → a i a k ∈H [c α < sa α ]τ α .A i (c[c α + 1]) + [c α = sa α ]τ α .A k ( 1)
where ĉ = c 1 , . . . , c n with n = |{b j → a i a k ∈ H}|. ĉ[c α + 1] = c 1 , . . . , c α + 1, . . . , c n . A k ( 1) is an abbreviation for the recursive call to A k with all parameters set to 1. [cond]π.P stands for an action π enabled only when cond is satisfied.

Applications

Metazoan Segmentation

In this section, we illustrate our method and its benefits on a case study in which our aim is to control the final state of the corresponding GRN. The GRN we chose has been established in silico by François et al. [23] but in a differential equations framework. It aims at generalizing a common motif present in biological segmentation networks such as the Drosophila.

The GRN (Figure 4(a)) is composed of three genes. A wavefront gene f activates the gap-gene a whose products are responsible or stripes. Gene f also activates a gene c whose products repress the gene a. The auto-inhibition of c generalizes a chain of repressors on a. The apparition of stripes has to be regular. We attach to each gene two processes representing their qualitative levels (missing or present) -for instance c 0 (absence) and c 1 (presence) are processes for c. When f switches off, c goes to process c 0 and a has two fates, ending either at process a 0 or a 1 . We are interested in controlling the final process for a.

The Process Hitting for generalised dynamics of the GRN (Section 2) is computed first. Figure 4(b) shows its hypergraph. The specification of dynamics implies two cooperative hits in the Process Hitting: first, c 0 needs products of f to bounce to process c 1 ; second, expression of a only increases if both f activates it (i.e. process f 1 is present) and c does not inhibit it (i.e. c 0 is present). Consequently, we create a cooperative sort fc reflecting the state of f and c (Section 3.1) and replace the independent hits from c 0 and f 1 to c 0 and a 0 by hits from fc 10 . The resulting Process Hitting is represented in Figure 5(a).

By looking at the Hitless Graph of the Process Hitting (Figure 5(b)), only one stable state is present: f 0 c 0 fc 00 a 0 . The stability of the state f 0 c 0 fc 00 a 1 is controlled by the absence of inhibition by f 0 on a 1 . By removing the action f 0 → a 1 a 0 from the Process Hitting, we make the state f 0 c 0 fc 00 a 1 stable. The full set of corresponding René Thomas' parameters for the genes a and c is inferred by applying the method depicted in Section 4. We get:

K a,∅,{a,c,f } = 0 K a,{a,c},{f } = 1 K c,∅,{c,f } = 0 K a,{a},{c,f } = 0 K a,{a,f },{c} = 0 K c,{c},{f } = 0 K a,{c},{a,f } = 0 K a,{c,f },{a} = 1 K c,{f },{c} = 0 K a,{f },{a,c} = 0 K a,{a,c,f },∅ = 1 K c,{c,f },∅ = 1 .
We are interested in controlling the final process of sort a -either a 0 or a 1 -when f goes down to f 0 . Looking at the Process Hitting hypergraph on Figure 5(a) and considering f 0 is present, we deduce that the more c 1 is present, the more a 1 may be hit by c 1 to bounce to a 0 ; similarly, the more fc 10 is present, the more a 0 may be hit by it to bounce to a 1 . We tune actions only triggered by f 0 : we reduce the presence of c 1 by increasing the rate of the action f 0 → c 1 c 0 and extend the presence of fc 10 by reducing the rate of f 0 → fc 10 fc 00 . This leads to an increase of the probability for a to bounce to process a 1 .

Finally, to obtain regular stripes, we set a high stochasticity absorption factor to actions responsible of the bounces of processes of sort c and a when f 1 is present. Figure 6 plots the evolution of the genes a,c and f during a simulation under SPiM [24] of the Process Hitting illustrated by Figure 5(a) with initial state f 1 c 0 fc 10 a 0 and a fast rate for the action f 0 → c 1 c 0 compared to the rate of c 1 → a 1 a 0 . The rate values have been arbitrarily choosen and respect the infered relations between them. Appendix B.1 details the Process Hitting used for the simulation.

From the obtained simulation trace, we observe that f 0 hits c 1 before c 1 had time to hit a 1 : the final state is then f 0 c 0 fc 00 a 1 .

Thanks to the Process Hitting framework, it has been easy to build a qualitative model of the biological system by refining the generalised dynamics of the GRN. Using a simple reasoning on the Process Hitting structure, relation between regulation delays to favour a final state have been infered. These results are coherent with those obtained using differential equations as done in [23].

ERBB Receptor-Regulated G1/S Transition

The aim of this section is to demonstrate the scalability of the refining approach on Process Hittings modelling large GRNs. The selected GRN relates regulations between 20 genes. This GRN models the ERBB receptor-regulated G1/S transition involved in the breast cancer. It has been extracted from published data by Sahin et al. [25] and is reproduced in Figure 7. This network acts as an activation cascade for the gene pRB which controls the G1/S transition involved in cell divisions. The gene EGF then acts as an input of this cascade: when expressed, pRB will be potentially activated. Based on the literature, Sahin et al. have also established a set of logical rules controlling the activation of the various genes present in the network.

Starting from the GRN, its generalised dynamics expressed in Process Hitting is first computed. Then, cooperations between the different sorts are built from the logical rules. The Process Hitting obtained contains 670 actions and stands for 2 64 (≈ 2.10 19 ) states that has hopefully not be built. This model is fully detailled in Appendix B.2.

The computation of all the stable states present in the dynamics is done using the algorithm sketched by Section 3.2. It results in 5 stables states (also detailled in the appendix) that are computed in less than one second.

It is worth noticing that no assumption is made on the initial state of the system. All the stable states of the model are computed. This is a major difference with the approach presented in [25] where only dynamics starting from a fixed state can be studied.

Conclusion

We introduced the Process Hitting framework for modelling qualitative dynamics of GRNs with temporal and stochastic features. Temporal and stochastic param-

EGF ERBB2 ERBB1 ERBB3 ERBB1 2 ERBB1 3 ERBB2 3 IGF1R MEK1 AKT1 ERalpha MYC CycD1 p27 p21 CycE1 CDK6 CDK2 CDK4
pRB Fig. 7. ERBB receptor-regulated G1/S transition GRN reproduced from eters determine probabilities, durations and temporal variance of reactions in the model. We exhibited a direct translation from Process Hitting to the Stochastic π-Calculus. Detection of stable states and inference of René Thomas' parameters for dynamics derive from this framework. The methods we offered work by successive refinements of generalised dynamics for GRNs, by specifying both the cooperativity between genes and the expected stable states. We illustrated this method by inferring temporal parameters for the dynamics of a GRN generalizing metazoan segmentation processes (with the aim of controlling its final state). The scalability of the presented approach has been experimented on a Process Hitting modelling a GRN composed of 20 genes and computing its stable states.

The Process Hitting brings a formal framework for progressively adding knowledge of the dynamics of a GRN by refining an abstracted behaviour. The compositionality of the framework and the presence of particular structure patterns lead to scalable methods for dynamics analyses (stable states, René Thomas' parameters, etc.). Mainly, thanks to these Process Hitting patterns, it becomes possible to perform a local analysis, which has the major advantage to prevent us from exploring the full state and parameter space.

In future works, we aim at identifying more Process Hitting patterns leading to the emergence of particular behaviours (e.g. oscillations) and especially hybrid patterns coupling both discrete structure and continuous temporal and stochastic parameters. The verification of Process Hittings could be performed by using a translation into Petri Nets or into PRISM. Translating Process Hittings into more sophisticated process aglebras (Beta Workbench, Bio-PEPA, etc.) may also be of interest. Finally, techniques have to be developed to infer automatically temporal and stochastic parameters of Process Hittings modelling GRNs. A Process Hitting Related Tools

This appendix briefly presents currently available implementations of tools manipulating Process Hittings. They are available at the following URL: http://www.irccyn.ec-nantes.fr/ ~pauleve/processhitting-refining.tar. gz . Implemented in the OCAML language, these tools have a command-line user interline.

A.1 Process Hitting Specification

A basic language has been setup to specify Process Hitting using a text file. Main features are presented here, more details can be found in the provided archive. Full examples of Process Hitting specifications are given in Appendix B.

Sort definition A sort is declared by giving the process with the highest rank (i.e. a la for the sort a, with the notations used in Section 2). Hereafter is an instance of the use of the GRN macro for the GRN having activating edges a

Fig. 1 .

 1 Fig. 1. Graphical representations for the Process Hitting PH = ({a, b}, {a0, a1} × {b0, b1, b2}, H) with H = {b0 → a0 a1, a1 → b0 b1, a1 → b1 b2}.

Fig. 2 .

 2 Fig.2. Construction of a cooperative hit between f1 and c0 on a0 (thick lines): σ = {f, c}, ⊤ = {f1c0}, υ = fc. fc01 stands for the process corresponding to the state f0c1 of the cooperating processes σ.

  (b), a 1 is removed from the Hitless Graph (E b a1 = ∅), the partition associated to c is chosen (involved into only 4 edges), two states are tested: a 0 b 0 c 1 and a 2 b 1 c 0 and the latter reveals to be the only 3-clique.

Fig. 3 .

 3 Fig.3. A Process Hitting represented by its Hypergraph (a) and its Hitless Graph (b). The Hitless Graph contains only one 3-clique between a2, b1 and c0 (thick lines): this is the only stable state of this system.

Fig. 4 .Fig. 5 .

 45 Fig.[START_REF] Kuttler | Gene regulation in the pi calculus: Simulating cooperativity at the lambda switch[END_REF]. The starting Gene Regulatory Network graph (a), arrow-ended edges represent the positive regulations, and bar-ended edges the negative ones. All regulation thresholds are 1. The Process Hitting (b) for its generalized dynamics. Cooperativity between f1 and c0 on a0 and c0 will be applied in the same way as in example. 1.

Fig. 6 .

 6 Fig. 6. Simulation of the Process Hitting for segmentation: evolution of the expressions of the gap-gene a (top), the autonomous clock c (middle) and the wavefront f .

  24. Phillips, A.: SPiM -Stochastic Pi Machine. (SPiM) http://research.microsoft. com/en-us/projects/spim. 25. Sahin, O., Frohlich, H., Lobke, C., Korf, U., Burmester, S., Majety, M., Mattern, J., Schupp, I., Chaouiya, C., Thieffry, D., Poustka, A., Wiemann, S., Beissbarth, T., Arlt, D.: Modeling ERBB receptor-regulated G1/S transition to find novel targets for de novo trastuzumab resistance. BMC Systems Biology 3(1) (2009)

  Action specification An action a i → b j b k is added by the following instruction:a i -> b j k @ rate ~absorptionGeneralised dynamics of GRNsThe GRN macro computes the generalised dynamics of the specified GRN according to Section 2.5. An activating (resp. inhibiting) edge a X -→ b from gene a to gene b active with a threshold X is noted as a X -> + b (resp. a X -> -b).

1 -→ b and a 2 -→ a, and inhibiting edge b 1 -

 121 → b. GRN([a 1 -> + b; b 1 -> -a; a 2 -> + a ])Refinement: cooperations The COOPERATIVITY([a1;...;an] -> b j k, [s1;...;sp]) macro creates a cooperative sort σ = {a 1 , . . . , a n } for the bounce b j b k . This cooperation is effective for every state s 1 , . . . , s p .The following instruction creates a cooperativity between sorts a and b to bounce process c 0 to c 1 only if a 1 b 0 or a 0 b 1 are present.

  COOPERATIVITY([a;b] -> c 0 1, [[1;0];[0;1]])

Supplementary Material

The Process Hitting compiler to SPiM, a stable states computer and presented models are available at the following URL: http://www.irccyn.ec-nantes.fr/ ~pauleve/processhitting-refining.tar. gz .

Refinement: action removing An action a i → b j b k can be deleted by using the macro RM: RM({a i -> b j k})

A.2 Compiler to SPiM

This tool translates a Process Hitting specification into a SPiM model according to Section 5.2.

phc -spim <model.ph> <output.spi>

A.3 Stable States Listing

The stable states of a Process Hitting are determined used an implementation of the algorithm sketched in Section 3.2. This algorithm computes the n-cliques of the hitless graph for the given Process Hitting, where n is the number of sorts. The efficiency of this computation heavily relies on the order of sorts when building cliques. Currently, basic heuristics are used to select the order of the sorts. More sophisticated analyses may conduct to dramatically improve the efficiency of this algorithm.

This tool is compiled into the executable ph-stable-states and takes as argument the filename of the Process Hitting specification : ph-stable-states <model.ph>

B Process Hitting Examples

This appendix details the Process Hittings used in Section 6. They are specified in the language presented in the previous appendix.

B.1 Metazoan Segmentation

The following Process Hitting models the metazoan segmentation presented in Section. 6.1. Actions are specified separately and rates have been assigned to values matching the relations infered in the application case study. The directive sample and initial state instructions are of use for SPiM only. A result of the execution of this Process Hitting translated into SPiM is given by Figure 6.

process a 1 process c 1 process f 1 process fc 3 (* cooperative sort {f , c } *) c 1 -> fc 0 1 @5 . c 1 -> fc 2 3 @5 . c 0 -> fc 1 0 @10 . c 0 -> fc 3 2 @5 . f 1 -> fc 0 2 @10 . f 1 -> fc 1 3 @10 . f 0 -> fc 2 0 @0 .1 f 0 -> fc 3 1 @0 .1 (* actions on c *) fc 2 -> c 0 1 @0 .5~50 (* only if ( f1 , c0 ) *) c 1 -> c 1 0 @0 .5~50 (* actions on a *) fc 2 -> a 0 1 @1 .~50 (* only if ( f1 , c0 ) *) c 1 -> a 1 0 @1 .~50 (* actions on f *) f 1 -> f 1 0 @0 .034~100 (* auto -off *) f 0 -> c 1 0 @0 .1 i n i t i a l s t a t e f 1 , c 0 , a 0

B.2 ERBB Receptor-Regulated G1/S Transition

The following Process Hitting results from the case study presented in Section 6.2. It starts by specifying the GRN depicted by Figure 7 to compute its generalised dynamics. The logical rules setup by Sahin et al. [25] are then applied by using sorts cooperativity.

This Process Hitting contains 670 actions and 2 64 (≈ 2.10 19 ) states. Only 5 stable states exist and are determined in less than a second using the tool presented in the previous appendix.

Below is the list of stable states present in the Process Hitting. For each stable state, only genes at level 1 are written.

-AKT1, CDK2, CDK4, CDK6, CycD1, CycE1, EGF, ERBB1, ERBB1 2, ERBB1 3, ERBB2, ERBB2 3, ERBB3, ERalpha, MEK1, MYC, pRB.

-AKT1, CDK2, CDK4, CDK6, CycD1, CycE1, ERalpha, IGF1R, MEK1, MYC, pRB.

-AKT1, CDK2, CycE1, EGF, ERBB1, ERBB1 2, ERBB1 3, ERBB2, ERBB2 3, ERBB3, ERal- pha, MEK1, MYC.

-AKT1, CDK2, CycE1, ERalpha, IGF1R, MEK1, MYC.

-∅ (all genes have level 0). process AKT1 1 process CDK2 1 process CDK4 1 process CDK6 1 process CycD1 1 process CycE1 1 process EGF 1 process ERalpha 1 process ERBB1 1 process ERBB1_2 1 process ERBB1_3 1 process ERBB2 1 process ERBB2_3 1 process ERBB3 1 process IGF1R 1 process MEK1 1 process MYC 1 process p21 1 process p27 1 process pRB 1


B Amann

I Fundulaki

M Scholl

C Beeri

A-M Vercoustre

Mapping XML Fragments to Community Web Ontologies

Introduction

The C-Web (Community Web) 1 project [START_REF] Amann | Integrating ontologies and thesauri for RDF schema creation and metadata querying[END_REF] aims at supporting the sharing, integration and retrieval of information in a specific domain of interest for a group of people who desire to access and exchange knowledge and information in this domain. A C-Web portal (or mediator) provides the infrastructure for (1) publishing information sources and (2) formulating structured queries by taking into consideration the conceptual representation of a specific domain in form of an ontology.

Query mediation has been extensively studied in the literature for different kinds of mediation models and for various source capabilities. Tsimmis [START_REF] Papakonstantinou | Object Exchange Across Heterogeneous Information Sources[END_REF], YAT [START_REF] Christophides | On Wrapping Query Languages and Efficient XML Integration[END_REF], Infomaster [START_REF] Genesereth | Infomaster: An Information Integration System[END_REF], Information Manifold [START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF], Tukwila [START_REF] Pottinger | A Scalable Algorithm for Answering Queries using Views[END_REF][START_REF] Ives | An adaptive query execution system for data integration[END_REF] and PICSEL [START_REF] Goasdoué | The use of CARIN Language and Algorithms for Information Integration: The PICSEL System[END_REF] are among the most prominent examples of mediation systems. In C-Web, query mediation is closely related to the last three of them which follow the local as view approach. These systems describe the source contents in terms of the mediator schema and the resulting query rewriting algorithms are based on efficient implementations for evaluating query subsumption and satisfiability. Similar to the above systems, in C-Web users formulate queries in terms of the ontology and the mediator translates these queries according to the source descriptions and the source query facilities.

In this paper we are interested in the publication and querying of XPath [START_REF]XML Path Language (XPath) Version 1.0. W3C Recommendation[END_REF] enabled XML resources. More precisely, we want to take advantage of the structure of XML documents (generally described by a DTD) for mapping pieces of information contained in XML fragments [START_REF]XML Fragment Interchange. W3C Candidate Recommendation[END_REF] to domain specific ontologies. The objective here is to be able to forward user queries to diverse XML repositories while hiding their DTD heterogeneity to the end-user. Our contribution is two-fold : [START_REF] Abiteboul | Data On the Web: From Relations to Semistructured Data and XML[END_REF] we propose a simple mapping language describing sources by a set of rules relating XPath location paths to the concepts and roles of an ontology and (2) a query rewriting algorithm for translating user queries into queries expressed in an XML query language [START_REF] Chamberlin | XQuery: A Query Language for XML[END_REF][START_REF] Chamberlin | Quilt: An XML Query Language for Heterogeneous Data Sources[END_REF][START_REF] Robie | XML Query Language (XQL)[END_REF] that are send for evaluation to XML sources.

XPath [START_REF]XML Path Language (XPath) Version 1.0. W3C Recommendation[END_REF][START_REF] Wadler | A formal semantics of patterns in XSLT[END_REF] is a tree pattern language which allows to characterise XML fragments according to their position in the document tree, their type and their contents. Whereas XPath does not have the full expressive power of XML query languages, the choice of using XPath as part of a mapping language for XML documents is interesting for several reasons. First, XPath is already part of several XML-related languages [START_REF] Abiteboul | Data On the Web: From Relations to Semistructured Data and XML[END_REF] for the transformation (XSLT [START_REF]XSL Transformation (XSLT) Version 1.0. W3C Recommendation[END_REF]), linkage (XLink [START_REF]XML Linking Language (XLink) Version 1[END_REF]) and querying (XQL [START_REF] Robie | XML Query Language (XQL)[END_REF], XQuery [START_REF] Chamberlin | XQuery: A Query Language for XML[END_REF] and Quilt [START_REF] Chamberlin | Quilt: An XML Query Language for Heterogeneous Data Sources[END_REF]) of XML documents. This implies that XPath is used by an important number of XML developers who do not have to learn a new language for writing mapping rules and that it is implemented in a variety of tools and can be integrated very easily in a standard Web server 2 .

In this paper we illustrate our approach considering the integration of cultural information sources accessible from Web servers. We show how such Web resources can be described according to an ontology (Section 2) by creating mapping rules between XML fragments (identified by XPath expressions) and ontology concepts and roles (Section 3).

Finally we illustrate in Section 5 how these mappings can be used for the rewriting of a restricted class of OQL queries presented in Section 4.

Ontologies and Schema Paths

Ontologies : An ontology is a quintuple O = (C, R, source, target, isa), where : (i) C is a set of concepts, (ii) R is a set of binary roles between concepts in C, (iii) functions source and target map roles to their domain and target concepts, respectively, and (iv) isa is an inheritance relationship on C with the usual properties (hierarchy on C).

An ontology usually reflects a common understanding of a certain domain. In our case we are interested with domain-specific information stored in one or several XML databases and we define the semantics of an ontology by the databases that conform to it : a database for an ontology O contains a set of objects (instances) for each concept in C which are related by instances of roles in R. The isa component of O is interpreted with a subset semantics, and we say that two concepts c and c ′ are isa-related if c = c ′ or c isa c ′ or c ′ isa c holds.

An example of an ontology for cultural artifacts is shown in Figure 1. Ten concepts and nine roles describe actors (persons) performing activities for producing artifacts. For example, concept Person collects all persons, is a subconcept of Actor and inherits role performed relating actors to activities. It is possible to follow schema paths between concepts in the ontology graph. For example, the artifacts produced by an actor are obtained by traversing role performed (activities performed by actors), and then role has produced (artifacts produced by these activities). Observe also, that this traversal defines the subset of all artifacts produced by some actor. We distinguish between role paths defining derived roles and concept paths defining virtual concepts. Role paths and derived roles : A role path of length n (n ≥ 1) is a sequence r = r 1 . . . r n , where r i are roles, such that for all 1 ≤ i < n, target(r i ) and source(r i+1 ) are isa-related. The source and target of a role path are defined by the source and the target of its extremities : source(r) = source(r 1 ) and target(r) = target(r n ). Clearly, the composition of a role path r and a role path r ′ , denoted r • r ′ , is well-defined provided that target(r) and source(r ′ ) are isa-related. Role performed is a role path of length 1 with source Actor and target Activity. A role path r of length > 1 defines a derived role, rol(r) from instances of its source concept to instances of its target concept. For example, role path technique.used material of length 2 defines a derived role, rol(technique.used material) between concept Man Made Object and concept Material. A sequence r 1 .r 2 can be viewed as a derived role whose every instance connects an instance o of source(r 1 ) with an instance o ′ of target(r 2 ), through an intermediary o ′′ that must be an instance of both target(r 1 ) and source(r 2 ). Instance o ′′ can only exist if target(r 1 ), source(r 2 ) are isa-related, and o ′′ must be an instance of both concepts target(r 1 ) and source(r 2 ).

Concept paths and virtual concepts :

A concept path p is either of the form c, or a sequence c.r, where c is a concept and r is a role path, such that source(r) and c are isa-related. The length of p is 0 in the first case, and the length of the role path r in the second case. The source and target of c are c. The source and target of p = c.r are defined as: source(p) = c and target(p) = target(r). The composition of a concept path p and a role path r, denoted p • r, is well-defined provided that target(p) and source(r) are isa-related. A concept path p = c.r can be viewed as defining a virtual concept denoted by con(p), standing for "the instances of target(p) that can be reached from source(p) by following the roles in p, in order". For example, concept path Person.performed.has produced denotes the artifacts (instances of concept Man Made Object) produced by some person. We also consider that the suffixes of a concept path p define superconcepts of the virtual concept defined by p : a suffix of a concept path p is obtained by removing a prefix, and adding an appropriate concept in the beginning. For example, if p = c 1 .r 1 .r 2 .r 3 , then source(r 3 ).r 3 and source(r 2 ).r 2 .r 3 are its suffixes. It is evident that the extent of p is a subset of the extent of any of its proper suffixes. Thus, we also relate a concept path and its suffixes (as virtual concepts) by isa.

Given an ontology, a set of role paths R, and a set of concept paths C defined on this ontology, we can define a view ontology, O V = (C V , R V , source V , target V , isa V ) where C V is the set of virtual concepts defined by each concept path in C along with its superconcepts (as previously defined), R V is the set of derived roles defined by each role path in R, and isa V is the isa relationship between virtual concepts.

A Mapping Language for XML

In the following we present a language for establishing mappings between XML fragments and ontology concepts and roles. Suppose that http://www.art.com is a web server of XML documents about artists and art in general. The corresponding DTD is shown in Figure 2. The mapping rules in Figure 3 map XPath location paths to schema paths in the ontology of Figure 1 : For example, rule R 1 states that all fragments of element type ARTIST which are descendants of the root of document http://www.art.com (see [START_REF]XML Path Language (XPath) Version 1.0. W3C Recommendation[END_REF][START_REF] Wadler | A formal semantics of patterns in XSLT[END_REF] for the definition of XPath patterns/location paths) are instances of concept Person. In the same way, rule R 8 states that all elements of element type ARTIFACT, descendants of the root of document http://www.art.com, are instances of concept Man Made Object. Rule R 3 creates instances of the derived role, rol(perf ormed.has produced) connecting each element x of type ARTIST obtained by rule R 1 , to all elements of type ARTIFACT that can be obtained from x by applying XPath /ARTIFACT. Mapping Rules : A mapping rule is an expression of the form R : u/q [as v] ← p, where 1) R is the rule's label, 2) u, the rule's root, 3) q is an XPath location path, 4) [as v] is an optional binding of variable v and 5) p is a schema path. More precisely, the root (u) is either a variable, or a URL and p is a role path if u is a variable and a concept path otherwise. Rule R is called a relative mapping rule if its root is a variable, and an absolute mapping rule otherwise. Let lp(R), cp(R) denote R's location path q and schema path p, respectively.

<!ELEMENT ARTIST (NAME,NATIONALITY,ARTIFACT * )> <!ELEMENT NAME (#PCDATA)> <!ELEMENT ARTIFACT (TITLE,PROCEDURE,LOCATION)> <!ELEMENT NATIONALITY (#PCDATA)> <!ELEMENT TITLE (#PCDATA)> <!ELEMENT MATERIAL (#PCDATA)> <!ELEMENT LOCATION (#PCDATA)> <!ELEMENT STYLE (#PCDATA)> <!ELEMENT PROCEDURE (MATERIAL,STYLE)>
R1: http://
A rule r : u/q as v ← p, is interpreted as follows : (1) apply location path q to all instances (x 1 ) of variable u; (2) the obtained fragments (x 2 ) are added to the set of instances of variable v; (3) if u is a variable, add (x 1 , x 2 ) to the set of instances of the derived role p; (4) if u is a URL, add x 2 to the set of instances of virtual concept p. Observe that we allow multiple bindings for the same variable. Such bindings reduce the number of mapping rules, while making the structure easier to understand. In the opposite way, it is possible to map the same location path to different variables in order to distinguish between two interpretations of the same set of fragments. Observe that rule R 3 binds the same variable (u 2 ) as rule R 8 which allows the application of rules R 4 and R 5 on the instances "found" by both rules to obtain the artifacts' title and technique.

Given a set of mapping rules, we define reachability for rules and variables, as follows: Each rule whose root is a URL, or a reachable variable is reachable, and each variable bound in a reachable rule is reachable. A mapping M over an ontology O is a set of mapping rules such that 1) labels are unique (that is, no two rules have the same label), 2) all rules are reachable (hence so are all variables) and 3) the concepts and roles used in its rules occur in O. Note that the binding-use relationships between variables in a mapping may be cyclic. The simplest case of a cycle is a rule whose left-hand-side contains v/A as v (provided that v can be reached from a URL by some other rules). A mapping is cyclic if it contains a binding-use cycle. Concatenation of mapping rules : Two rules R 1 : a/q 1 as v 1 ← p 1 , R 2 : v 1 /q 2 [as v 2 ] ← p 2 , can be concatenated, if the composition of their schema paths, p 1 • p 2 is well defined 3 . Note the constraint that the root of R 2 is bound in R 1 and that concatenation is possible only if p 2 is a role path. The concatenation is the rule R 1 .R 2 : a/q 1 /q 2 [as v 2 ] ← p 1 • p 2 . Given a mapping M , its closure, denoted by M * , is the set of all rules that can be obtained from M by repeated concatenation. Its expansion, denoted M , is the set of absolute rules in M * ( M ⊆ M * ). Given an ontology O, a mapping M over O defines a view ontology, O M = (C M , R M , source M , target M , isa M ) where C M is the set of virtual concepts defined by the concept paths of absolute rules in M and R M is the set of derived roles defined by the relative rules in M * .

Tree Queries

The user views the C-web portal as a single database of fragments without knowledge of the source on which each fragment is located. We might then consider each fragment as an object whose identity is the location path of the fragment. A mapping M , allows us to organise the fragments into collections of instances of concepts in O M , and also to view certain XML paths as representing roles of O M . It follows that one can in principle query this database of fragments using a query language, such as OQL. The answer of a query is defined using the semantics of queries on object bases. However, even though the answer is well-defined, an efficient evaluation requires that we use effectively the mapping M to translate the query into one or more queries on the sources. Our ability to do so may depend on the form of the query. We introduce a tree query language, as a restricted version of OQL, and discuss how mapping rules can be used in the evaluation of queries in this language.

Tree queries are based on select-from-where clauses on schema paths. Figure 4 shows two tree queries Q and Q1 where Q is the general form of a tree query and Q1 is an example of such a query that looks for "the titles and location of all man made objects where clay was used in the applied technique".

Q: select x i , x j , ... Q1: select b,d from e 1 x 1 , from Man Made Object a, e 2 x 2 ,
a.has title b, ... , a.technique.used material c, e i x i , a.located at d e i x i , where c = "clay" ... where c 0 and c 1 and ... Tree query Q is defined as follows. The x i 's are variables. Each e i in the from clause is either (1) a concept path c i /c i .q i defining a (virtual) concept or (2) a variable x i followed by a derived role q i . In the first case, c i and c i .q i , and in the second case, q i , are called the binding path of x i , denoted bp(x i ). < is a partial order on the variables, such that if x j .q i x i occurs in the from clause, then x j < x i (x j is called the parent of x i ). The where clause is a conjunction of simple predicates, of the form c k ≡ x i θd in which θ ∈ {=, <, >, ≤, ≥} and d is an atomic value. It is not possible to express joins by equalities between variables. Schema paths appear exclusively in the from clause, a syntax that simplifies the presentation of our rewriting algorithm 4 . The language has no quantifiers, aggregates, or subqueries but a variable x j , present in the from clause but not in the select or where clauses, is implicitly existentially quantified.

Query Rewriting and Evaluation

We present here a query rewriting algorithm that transforms a tree query Q according to a given acyclic mapping M into a query expressed in an XML query language. The algorithm consists of two phases, namely the binding and the rewriting phases. In the first phase we try to find all rules whose schema paths "map" to query paths and in the second phase we rewrite the initial query into a set of XPath expressions. Binding Variables to Rules : Take, for example, query Q1 and the mapping shown in Figure 3. Intuitively, rules R 1 .R 3 and R 8 might be used to find man made objects for variable a. The former finds all man made objects that have been produced by a person and the latter can be used to find man made objects in general. Rule R 4 can then be used to find the titles for those man made objects and values for variable b. In the same way, rule R 5 .R 6 finds the material used to produce these objects and obtains instances for variable c.

Formally, a variable to rule binding, or shortly variable binding, for a query Q is a mapping β on a subset of variables in Q, denoted dom(β). More precisely, if dom(β) is not empty, then β associates each variable in dom(β) with a rule in closure M * , such that the following holds:

1. if x is the root of query Q, then β(x) is an absolute mapping rule such that the query binding path bp(x) of variable x denotes a superconcept of the virtual concept, con(cp(β(x))) in O M , which is the case when bp(x) is equal to or a suffix of cp(β(x)) or a superconcept of the target of β(x);

2. else the declaration of x in Q has the form x ′ .q x, i.e. x is the child of variable x ′ and the binding path of x is q.

Answers for x can be obtained from answers for x ′ , by following the binding path q of x if (1) the root variable of rule β(x) is bound in rule β(x ′ ), (2) the role denoted by the derived role of the rule β(x), rol(cp(β(x))), is equal to the role denoted by the binding path of x and (3) the composition of the schema paths of the rules β(x ′ ) and β(x) is well-defined, i.e. the concatenation of the two rules is well-defined.

For example, for query Q1 above, the query root variable a is bound in the query to the (real) concept Man Made Object. In this case the concept path of bp(a) is a suffix of cp(R 1 .R 3 )=Person.performed.has produced and is equal to the concept path of cp(R 8 ). Now, the binding path bp(b) of variable b in Q1 is has title, so we need a rule whose schema path leads from Man Made Object to the virtual concept Man Made Object.has title; Rule R 4 is such a rule. Similar reasoning applies to the binding for variables c, d. Binding Algorithm : A variable binding is full if it is defined on all variables of Q, and partial otherwise. Given a query, we need to find all full variable bindings according to some mapping M . Indeed, each such binding provides, as shown below, a subset of the answer. By taking the union of all these answers, we have a maximal answer, with respect to the given sources and the given mapping. We assume, w.l.g, that variables are arranged in pre-order: x 1 , . . . , x n . This ensures that when we try to extend a binding to a variable, it is defined on its parent. A binding is represented as a vector of associations of variables to rules or concatenation of rules, in that order, namely {x 1 → r 1 , . . . x n → r n }.

We sketch here the binding algorithm for acyclic mapping rules. We assume that since the closure M * is finite, it has been calculated in advance. In the first step of this algorithm, we extend the empty binding to the root variable x 1 . For each absolute rule r in M * such that cp(r) is a subconcept of the binding concept path bp(x 1 ), we create a binding {x 1 → r}. Then, we iterate through the sequence of variables, from the left. Assume we have constructed a set of partial bindings that are defined on all variables up to and including x i , we show how to extend it to x i+1 . Let x j (j < i + 1) be x i+1 's parent. Necessarily, each binding β we have constructed is defined on x j and associates a rule r ′ = β(x j ) with x j . Suppose that variable v is bound in r ′ . Then, for each relative rule r of M * whose root is v, if the schema paths of r ′ and r can be composed, we extend β by x i+1 → r. Note that the edge from x j to x i+1 is 'traversed in this step, and only in this step.' After all bindings that are defined up to and including x i+1 are computed, all previous partial bindings can be dropped.

When M is cyclic, M * may be infinite. In a longer version of this paper we show how to compute a useful finite representation of M * that can be used to compute a finite representation of the set of bindings.

We illustrate variable binding for the mapping shown in Figure 3 and for query Q1 above. In the first step, we need to extend the empty binding with a binding for the root variable a, associated with virtual concept Man Made Object. An obvious one is a → R 8 , but since Person.performed.has produced defines a subconcept, the binding a → R 1 .R 3 is another solution and we obtain two (partial) bindings β 1 and β 2 defined on a. It is easy to see that each of them can be extended afterwards by b → R 4 , c → R 5 .R 6 , d → R 9 to a complete binding. Query Rewriting : Let B be a set of full variable bindings calculated by the foregoing algorithm for some query Q and mapping M . Then for each of the variable bindings in B, we create a query QS where we replace the schema path for a query variable with the XPath location path of the rule associated to it. For example, for query Q1, the algorithm returns bindings β 1 and β 2 . For binding This query can be easily expressed in any XML query language using XPath for binding variables such as Quilt [START_REF] Chamberlin | Quilt: An XML Query Language for Heterogeneous Data Sources[END_REF], XQL [START_REF] Robie | XML Query Language (XQL)[END_REF] and XQuery [START_REF] Chamberlin | XQuery: A Query Language for XML[END_REF]. However, XPath is a restricted language. For example, an XPath query can only return one kind of node (and for each node its XML subtree). Thus, the query QS1 cannot be expressed as a single XPath expression since it returns a set of pairs (b, d). But, we can express in XPath a request for the node of a, including in it the conditions that the paths in the XML document leading to b, c, d exist, and that the value of node for c is equal to "clay". When a subtree that corresponds to a is returned, we can locally project it on the nodes for b, d.

β 1 = {a → R 1 .R 3 , b → R 4 , c → R 5 .R 6 , d → R 9 } ,
An algorithm that decomposes a query QS into a partially ordered set of XPath expressions to be evaluated by the sources, where the partial order implies information passing, followed by an XML query to be evaluated by the mediator on the results of these subqueries is presented in a full version of this paper.

Figure 1 :

 1 Figure 1: An Ontology for Cultural Artifacts

Figure 2 :

 2 Figure 2: A simple XML DTD for Artists and Art in general

Figure 3 :

 3 Figure 3: Set of Mapping Rules

Figure 4 :

 4 Figure 4: Tree Queries

  www.art.com//ARTIST as u1

		← Person
	R2: u1/NAME	← has name
	R3: u1/ARTIFACT as u2	← performed.has produced
	R4: u2/TITLE	← has title
	R5: u2/PROCEDURE as u3	← technique
	R6: u3/MATERIAL	← used material
	R7: u1/NATIONALITY	← born.took place at
	R8: http://www.art.com//ARTIFACT as u2 ← Man Made Object
	R9: u2/LOCATION	← located at

  the obtained query is : QS1: select b, d from http://www.art.com//ARTIST/ARTIFACT a, a/TITLE b, a/PROCEDURE/MATERIAL c, a/LOCATION d where c = "clay"

http://cweb.inria.fr

See for example fragserver, http://www.xml.com/pub/r/676.

We do not define any restriction on the concatenation of location paths (rule left-hand-sides).

It is easy to show that a query with schema paths in the select and the where clause can be rewritten into an equivalent query in which they appear only in the from clause.