Seindé Touré
email: seinde.toure@cnrs.fr

Isabelle Dusfour

Didier Stien

Véronique Eparvier
email: veronique.eparvier@cnrs.fr

Two new tetrahydrofuran derivatives from the fungus Mucor spp. SNB-VECD11D isolated from the Chrysomelidae Acalymma bivittula

Keywords: Mucor spp., fungus, insecticide, antibacterial, Aedes aegypti

Two new tetrahydrofuran derivatives, mucorinic acids A (1) and B (2) as well as the three known secondary metabolites dehydroabietic acid (3), Δ8-dihydroabietic acid (4) and 8pimarenic acid (5) were isolated from a solid culture of the fungus Mucor spp. isolated on insect Acalymma bivittula. The structure of these compounds was elucidated by analysis of NMR and MS spectroscopic data. Compounds were tested in antimicrobial and insecticidal assays. Dehydroabietic acid exhibited moderate larvicidal activity on Aedes aegypti larvae with 65% mortality at 10 ppm. Both new compounds 1 and 2 showed interesting antibacterial activity on Staphylococcus aureus and methicillin resistant S. aureus with MIC values in the 8-16 μg/ml.

The search of insecticidal and antimicrobial molecules represents a global challenge for public health. On one hand, vector-borne diseases account for over 17% of all infectious diseases. [START_REF]Vector borne diseases[END_REF] In particular, mosquito transmit a number of diseases such as malaria (Anopheles sp.), filariasis (Culex sp.), dengue and more recently Zika virus (Aedes sp.), causing millions of deaths every year. [START_REF] Rahuman | [END_REF] On the other hand, most antimicrobial drugs suffer from major drawbacks such as emergence of resistant/multiresistant strains and toxicity. Hence, it is critical to discover new, more efficient and safer insecticides and antimicrobials.

Entomopathogenic microorganisms are natural enemies of insects. They produce a large diversity of secondary metabolites during the process of infection and proliferation, including insecticides and antimicrobials. 3 As such, entomopathogens are considered as an underrated source of novel bioactive compounds of pharmaceuticals and ecological interests. 4,5 Based on this dual potential, we have undertaken to search for new insecticides and antimicrobials from a collection of 57 microorganisms isolated from the cuticle of alive, yet infected insect species. All strains were cultivated and extracted with ethyl acetate. Extracts were screened on human pathogenic microorganisms and on Aedes aegypti larvae. The fungus Mucor spp. exhibited promising larvicidal and antibacterial properties. Mucor fungus belongs to the class of Zygomycota. They were often described as plant pathogens, but can also be deadly pathogens for insects.

Results and discussion.

The fungus cultivated on potato dextrose agar and identified as Mucor spp. SNB-VECD11D proved very active on Ae. aegypti larvae (laboratory reference strain Paea) with mortality rate of 77% after 24h of exposure at a dose of 100 µg/ml. It was also active on Staphyloccocus aureus and methicillin-resistant S. aureus (MRSA) with minimal inhibitory concentrations (MIC) of 64 µg/ml and 16 µg/ml, respectively. The chemical study of Mucor spp. extract led to the isolation of two new tetrahydrofurans derivatives 1 and 2, dehydroabietic acid 6 (3), Δ8dihydroabietic acid (4) and 8-pimarenic acid (5) (Figure 1). The 1 H NMR spectrum of 1 suggested the presence of five methyl groups at δ H 1.15, 1.16, 1.29, 1.61 and 2.07, and five methines corresponding to δ H 5.68, 5.62, 5.60, 5.17 and 3.84 (Table 1). The 13 C, HSQC and HMBC NMR data allowed the identification of five quaternary carbons at δ C 173.6, 154.5, 135.7, 84.0 and 72.5. Three double bonds and a carbonyl group were detected in HSQC. These accounted for four out of the five unsaturations. The sequence of 1 H-1 H COSY correlations H-10/ H-9/H-8/H-7/H-6/H-5 and H-4/H-3/H-2 combined with the HMBC correlations H-10/C-8, C-9 ; H-8/C-7, C-9 and C-10 ; H-6/C-4 and C-5 ; H-4/C-2 and C-3 established a farnesyl-like polyene side chain from C-10 to C-2. Methyl substituents 18 and 19 were connected to C-3 and C-7, respectively. HMBC correlations of protons H-18 to C-1 placed the carboxylic group at the end of the chain (Fig. 2). The E configuration of the double bonds can be established based on NOESY correlations H-8/H-6, H-10 and H-2/H-4 (Fig. 3). The tetrahydrofuran moiety was determined based on COSY correlations between H-12 (δ H 1.84/1.94), H-13 (δ H 1.78/1.87) and H-14 (δ H 3.84) combined with HMBC correlations The molecular formula and the chemical shifts in C-11 (δ C 84.0) and C-14 (δ C 86.5) suggested these two carbons were linked by an oxygen therefore forming a tetrahydrofuran ring. This was confirmed by a NOE correlation between H-14 and H-20, also indicating that H-14 and methyl 20 are on the same side of the ring (Fig. 3). Overall compound 1 was the (2E,6E,9E)-5-(2-hydroxypropan-2-yl-2-methyltetraydrofuran-2-yl)-3,7-dimethyldeca-2,6,9-trienoic acid and was named mucorinic acid A. Isolated compounds from Mucor spp. strain were evaluated for their antimicrobial activities against several human pathogens and for their larvicidal activities against Ae. aegypti larvae.

Dehydroabietic acid (3) exhibited larvicidal activity on Ae. aegypti whereas the other four compounds exhibited moderate antimicrobial activity but no antifungal activity (Table 2). In conclusion this letter reports the first description of two new antibacterial tetrahydrofuran derivatives mucorinic acids A and B. The same fungus also produces abietane or pimarane diterpenoids 3-5. Compound 3 known as a conifer biomarker has been discovered later from fungi and cyanobacteria. 7,8 Mucor spp. SNB-VECD11D is another fungus able to produce abietanes and pimaranes.

Fig. 1 . 5 Compound 1

 151 Fig. 1. Structure of compounds 1-5

  of protons H-12 to C-11 (δ C 84.0), C-13 (δ C 39.0) and C-14 (δ C 86.5). The farnesyl side chain was linked to the tetrahydrofuran in C-11 as established by the correlation H-10/C-11. The correlation between methyl groups 16 (δ H 1.15) and 17 (δ H 1.16) with C-14 and C-15 defined a 2-hydroxypropan-2-yl subunit linked to C-14.

Fig. 2 .

 2 Fig. 2. Key 1 H-1 H COSY (bold line) and HMBC (dashed arrows) correlations of 1.

Fig. 3 .

 3 Fig. 3. Key NOESY correlations of 1.

Table 1 .

 1 NMR Spectroscopic Data (CD 3 OD) for compounds 1 and 2

		1			2
	Pos. δ C	a, c , type	δ H b (J in Hz)	δ C	a , type	δ H b (J in Hz)
	1	173.6, C		173.0, C
	2

Table 2 .

 2 Antimicrobial and larvicidal activity (at 10 ppm) of compounds 1-5 Postitive control : oxacillin for S. aureus ; fluconazole for C. albicans and T. rubrum ; vancomycine for MRSA.

		Larvicidal activity	MIC (μg/ml)
		(% mortality)
	Compound		C. albicans S. aureus MRSA T. rubrum
	1	2.0	> 256	16	16	> 256
	2	2.1	> 256	8	16	> 256
	3	65.0	> 256	128	64	64
	4	6.2	> 256	16	16	> 256
	5	10.0	> 256	16	16	> 256
	Pos. Ctrl. a		4	0.2	0.6	4
	a

Acknowledgements

A. Supporting information

Supplementary data (NMR data of compounds 1, 2, 3, 4 and 5 as well as MS data of 1 and 2) associated with this article are available online.


Hélène Fargier

Jérôme Lang

Thomas Schiex

&me Fargier

Jmhne Lang

Mixed constraint satisfaction : a framework for decision problems under incomplete knowledge

Constraint satisfaction is a powerful tool for representing and solving decision problems with complete knowledge about the world. We extend the CSP framework so as to represent decision problems under incomplete knowledge. The basis of the extension consists in a distinction between controllable and uncontrollable variables -hence the terminology "mixed CSP" -and a "solution" gives actually a conditional decision. We study the complexity of deciding the consistency of a mixed CSP. As the problem is generally intractable, we propose an algorithm for finding an approximate solution.

Introduction

Most of the time, solving a constraint satisfaction problem (CSP) means finding an assignment of the variables satisfying all the constraints, if such an assignment exists. Such a request often relies on the assumption (generally implicit) that the variables are controllable, i.e., that the agent has the power to fix their values. However, one may think to give variables a status of uncontroZZabZe: the value of an uncontrollable variable is fixed by the external world and thus it is outside the control of the agent. In the rest of the paper we will refer to controllable variables as decision variables and to uncontrollable as parameters. If all variables of a CSP are controllable, the purpose of the resolution of the CSP is to find a good decision which the agent may apply: we will refer to this kind of CSP (which is the most common in the CSP literature) as decision-oriented CSP. If all variables are uncontrollable, the constraints represent pieces of knowledge about the possible actual values of the variables. In this case, what is expected is not necessarily to find a consistent assignment, but rather to find the actual value of each variable. This means that the resolution process has to be interpreted not in terms of decision but in terms of reasoning (as this is the case in most logical approaches for knowledge representation).

We will refer to this kind of CSP as reasoning-oriented CSP. Examples of reasoningoriented CSPs in the literature are far less numerous. For instance, CSP used for scene interpretation clearly belong in this class.

The fundamental difference between these two kinds of CSPs thus lies in the interpretation of the data (variables and constraints) and in the output of the resolution pro-homas Sehiex INRA 3 1320 Castanet Cedex (France) cess; interpreting the number of solutions is particularly worth of interest: if a decision-oriented CSP has several soZutions, this is rather good news since the agent will be (in principle) happy with any of them; on the contrary, if a reasoning-orientedCSP has several solutions, which means that the knowledge is incomplete, giving only one solution means arbitrary selecting one possible situation, which is not necessarily the real one -giving all solutions could be more adequate. Now, if a decision-oriented CSP has no solution, the problem is over-specified; inconsistency for reasoning-oriented CSP has to be interpreted in a different way, since the variables do have a value in the actual world and therefore at least one of the constraints is not sound. Now, beyond pure decision or reasoning-oriented problems, there are practical problems where a decision has to be taken, while the actual world is not completely known (which is the basic assumption in applications of decision theory). For instance, in scheduling, the decision (sequencing the tasks) may depend on ill-known parameters such as the reliability of some machines. Our motivation is to show that the CSP framework, which has been successfully developed and applied in the past years, can be extended in such a way that it can represent and solve problems of decision making under incomplete knowledge. These problems will be represented by so-called mixed CSPs involving both controllable and uncontrollable variables.

The definition of a solution of a mixed CSP depends crucially on the assumptions concerning the agent's awareness of the parameter values (the state of the world) at the time the decision must be made (deadline for acting) -where a decision is an assignment of decision variables.

We will consider these two epistemological assumptions:

(full observability): the actual world will be completely revealed to the agent before the deadline is reached (possibly, just before), so that it is useful to compute "off-line" a ready-to-use conditional decision, mapping possible cases to decisions, that the agent will be able to instantiate in real time, as soon as the actual world is known. NO (no observability): the agent will never learn anything new about the actual state of the world before the deadline; all it will ever know is already encoded in the initial specification of the problem. In this case, it is useless to provide a conditional decision, and a suitable solution of the problem consists in pure, unconditional decision to be taken in any outside the scope of the paper, we assume that K is consispossible case.

tent. The intermediate case where some partial knowledge about the state of the world may be learned (for instance through information-gathering actions) is not considered in this paper. The two extreme assumptions we consider lead to two definitions of a solution of a mixed CSP and two different notions of consistency, that we study in Section 2. In Section 3 we propose an anytime algorithm for solving mixed CSP under assumption (FO). Possible extensions and applications are mentioned in conclusion.

A mixed CSP defines a collection Candidates(P), of classical, decision-oriented CSPs, one for each possible world w -it will be called the set of candidate problems induced by P. Briefly (we omit technical details for space considerations), the candidate problem induced by a world w is a CSP over X whose constraints are the original pure decision constraints plus those obtained by reducing each mixed constraint C to a pure decision constraint by letting its parameters take their value as specified in wl.

Mixed constraint satisfaction Definitions

A classical constraint satisfaction problem is a triple P = (X, D, C), where X is a set of variables, each of which takes its possible values in a domain Di (supposed here finite, we note D = x iDi), and C is a a set of constraints, each of which restricting the possible values of some variables. Sol(P) denotes the set of all assignments satisfying all constraints of P.

Roughly speaking, a mixed CSP is a CSP equipped with a partition between (controllable) decision variables and (uncontrollable) parameters.

Definition 1 (mixed CSP) A mixed CSP is defined by a 6-uple P = (A, L, X, D, ic,C) where:

-A== {A,,... , X,) is a set of parameters; -L=L1x

.

+ e x L,, where Li is the domain of Xi; -x = (Xl,... , xn) is a set of decision variables; -D=D1 x . . . x Dn, where Di is the domain of xi; -K is a set of constraints involving only parameters; -C is a set of constraints, each of them involving at least one decision variable.

A complete assignment of the parameters will be called a world and will be denoted by w. A complete assignment of the decision variables will be called a decision and will be generally denoted by d. The complete assignment of both parameters and decision variables resulting from the concatenation of w and d will be denoted by (w, d).

The important distinction between the constraints of K and those of C is due to their very different interpretations: the constraints of K involve only parameters and thus represent the knowledge we have about the real world. Now, C contains decision constraints, which restrict the allowed values of decision variables, possibly conditioned by some parameters -if so they will be called mixed (or equivalently parameterized) constraints. If A = 0 (resp. X = m), P is a classical decision-oriented (resp. reasoning-oriented) CSP.

Definition 2 A solution of the reasoning-oriented CSP (A, L, K> is a possible world. The set of all possible worlds for P is denoted by Pass(P).

Now, a decision d is said to cover a world w iff it satisfies the candidate problem induced by w; this means that if the real world appears to be w, then d will be a suitable decision. Among the possible worlds, those which are covered by at least one decision, i.e., whose induced candidate problem is consistent, are called good worldsand the others are called bad worlds.

Definition 3 A decision d is said to cover a world w iff (w, d) is a solution of (AUX, L x D, C). The set of all worlds (possible or not) covered by d is denoted by Covers?(d).

Definition 4 Good(P) = Pass(P) n (&=oCoversp(d)) Bad(P) = Pass(P) \ Good(p)

Equivalently,

Good(p) = &D{W E Poss(P)((w,d) satisfies C}.

Example: let P be the following mixed CSP:

-X = {x1,

Conditional and unconditional decisions

The case of full observability In the case of full observability, solving a mixed CSP consists in giving a conditional strategy (from a planning point of view,-a conditional plan) associating, to each possible world, a decision that satisfies the corresponding candidate problem: once the actual If 1c: were inconsistent, we would get Pass(P) = 0. But this means that at least one of the constraints of K: is not sound. A non-trivial handling of this inconsistency being 'Note that among the CSPs of Candidates(P), some may be inconsistent, which means that the actual problem may be inconsistent.

values of the parameters are known, we have an appropriate decision.

More reasonably, we may consider conditional decisions defined on a subset of Pass(P) (ideally on Good(P)).

Definition 5 (conditional decisions) A conditional decision s for P is a map from a subset W, of Pass(P) to D such that VW E W,, s(w) covers w. Zf W, = Good(p), s is optimal. If W, = Good(P) = Pass(P) (implying Bad(P) = 0), s is complete.

Obviously, a complete conditional decision is also optimal, but the converse is generally not true: while a mixed CSP always has optimal conditional decisions, it does not always have a complete conditional decision.

Definition 6 (consistency) A mixed CSP is consistent ifit has a complete conditional decision.

Clearly, P is consistent H Bad(P) = o ti Good(P) = Pass(P). The consistency of P means that all candidate problems are consistent. When it is not the case, a weaker request consists in giving an optimal conditional decision, which covers all situations which are possible to cover. Example (continued): the following s is an optimal conditional decision for P2:

I XI L I X2 -+ II a I b I c I d I -.
,a b :

The case of no observability The previous approach assumes that the actual world will be known before the decision has to be taken (FO). Clearly, under the other extreme assumption (NO), it is useless to look for a conditional decision: consequently, in this case one has to look for a pure (unconditional) decision. Intuitively, this pure decision should cover "as many worlds as possible"; if there is no other decision covering more worlds covered by d (w.r.t. set inclusion), d is undominated; if furthermore d covers all good (resp. possible) worlds, it is universal (resp. strong universal).

Definition 7 A decision d E D is a undominated for P iff there is no d' E D such that Coversp(d') strictly contains Coversp(d); it is an universal decision for P if Coversp (d) = Good(P) and a strong universal decision for P if Coversp(d) = Pass(P).

While a mixed CSP always has an undominated decision (and generally has several incomparable ones), it is not always the case that it has a universal decision (and a fortiori a strong universal decision). Note that a pure decision is an extreme case of a conditional decision, where all considered worlds are mapped to the same decision. Here is a summary of the relations between different notions of decisions: 2The table has to be read this way: a world w is defined by the values assigned to both parameters X1 and X2 and corresponds thus to a row and a column, at the intersection of which is the decision s(w) when defined i.e., when w E W(s). Here, W(s) contains all good worlds, so s is optimal. Clearly, P is strongly consistent if and only if it is both consistent and uniformly consistent. The converses are generally not true. Note that universal (resp. strong universal) consistency implies that any undominated decision is a universal decision (resp. a strong universal decision). Example (continued): P has no universal decision. Consider the mixed CSP P' obtained from P by replacing Ca : z1 + 22 5 4 by Ci : 2x1 + 22 5 4. Then, Go&(?') = {a, b} x {a, b, d} and d = (1,2,3) is a universal decision (but not a strong universal decision).

Complexity

Interestingly, the problems of deciding consistency and strong consistency fall in complexity classes which are above /VP in the polynomial hierarchy.

We recall [START_REF] Stockmeyer | The polynomial-time hierarchy[END_REF] that a decision problem is in Sketch of proof: the problem is in l-I: since its complementary problem can be solved by the following algorithm: guess a world w, check that it is possible and that the corresponding candidate problem is inconsistent (co-NP-complete oracle). The completeness can be proven by reducing 2-QBF restricted to 3-CNF to the MIXED-SAT problem (see [START_REF] Fargier | Constraint satisfaction and decision under uncertainty[END_REF]).

NPNP = Cc iff
Note that MIXED-SAT remains IIF-complete even when we restrict ourself to binary mixed CSP with an empty K. This results furthermore offers a "canonical" lI,P-complete problem to the CSP community. The problem of deciding strong consistency is easily shown to be in Cc, but completeness is still to be proven in the general case. 3and remains so when F is restricted to 3-CNF [START_REF] Stockmeyer | The polynomial-time hierarchy[END_REF].

Constraint Satisfaction

In practice, the complexity of MIXED-SAT may be reasonable if we consider that K should usually drastically reduce the number of possible worlds. Lastly, when K = 0 (or equivalently Pass(P) = L), parameters are independent (since their possible values are not constrained).

This assumption has a drastic effect on the complexity of strong consistency:

Proposition 2 Under the parameter independence assumption, deciding strong consistency in a binary mixed CSP is NP-complete.

Sketch of proof: membership in NP is straightforward (the decision d is a polynomial length certificate which is checkable in polynomial time since Pass(P) = L). The completeness comes from the fact that the consistency of any binary CSP can be reduced to the strong consistency of the same CSP, considered as a mixed CSP with an empty parameter set A.

Searching for a conditional decision

The high complexity of finding a solution of a mixed CSP leads us to look for an algorithm which gives an optimal conditional solution if we let it run until it stops naturally, or otherwise gives an approximate (non optimal) conditional decision (the longer we let it run, the closer it gets to optimality). Intuitively, the algorithm incrementally builds a list of decisions which eventually covers a superset of all good worlds. Repeatedly, we pick a new decision d (to be added to the list) that covers at least one possible world among those which are not yet covered, we compute the set R of worlds (possible or not) that this decision covers and we subtract this set from the set of worlds which haven't yet been covered. In order to easily compute worlds covered by d, we assume that any constraint of C involves at most one parameter. Therefore, Coversp (d) forms a Cartesian product of subsets of the parameter domains and can be computed in polynomial time in binary mixed CSP. The successive subtractions of these Cartesian products is performed using a technique recently proposed in (Freuder and Hubbe, 1995) , called subdomain subproblem extraction. We recah this technique before we describe our algorithm.

Sub-domain extraction

We define an environment E as a set of worlds of the form El x . . . x Z,, with V'k, lk E Lk. An example of environment is (Xi E {a, c), X2 E {b, c, d}), also written {a, c} x {b, c, d) or [ tc>] when there is no ambiguity on the order of parameters. The set of all possible environments is obviously a lattice (equipped with the inclusion order), whose top is the set of all possible parameter assignments (in the example, [ $$]) and whose bottom is the empty set.

Given two environments E and R, sub-domain subprob-Zem extraction technique (Freuder and Hubbe, 1995)

end {else} end {else} Until Env = 0 (or interruption by the user) End {LD covers Good(P)} Several steps of the algorithm deserve some comments:

(1) The test of consistency of (A, L, K u E) may seem superfluous -since its role is only to distinguish bad environments from impossible environments, and in any case no new decision will be added-but is necessary* if we care about about the consistency of P (since Lemma 4 will not hold any longer if this test is removed). (l)+(2) The two sequences of CSP (A, L,K u E) and (A U X, L x D, K U C U E), repeatedly solved by the algorithm, define dynamic CSP (Dechter et al., 1988) and their resolution may be improved by any techniques developed to solve such problems.

(3) Once a new R is built, it is subtracted from all the awaiting environments to avoid some redundant computations. This furthermore guarantees that the computation will stop when the current list LD defines a solution.

(3) The update of the list of environments Env, may be performed lazily to avoid memory consumption.

Lastly, the algorithm considers an environment as impossible only when all of its worlds are impossible; consequently, there will be environments in LD and Bad containing impossible worlds. This is not a problem, since (i) these 4However, this test can be performed during the resolution (2) of (A U X, L x D, K U C U E) by the backtrack-based algorithm simply by imposing that the parameters be instantiated first. As soon as a consistent labeling of the A is found, any vertical ordering heuristics may apply. impossible worlds will never be observed; the important point is that any possible, coverable world is covered by a decision, and any possible, bad world is in the Bad list; and (ii) any environment added to the Bad list contains at least a possible world, which ensures that at the end of the algorithm, P is consistent @Bad = 0. ). This search of a decision for a given world could be made more efficient via the use of a discrimination tree for example. The worlds marked with a "*" are actually impossible but the list LD assigns them a decision, or labels them bad.

Correctness of the algorithm

It is based on the following properties; the proofs (omitted for length considerations) appear in [START_REF] Fargier | Constraint satisfaction and decision under uncertainty[END_REF]. to prove the termination, we prove that LJE~Q~E decreases strictly at each iteration (using Proposition 3). The second part of the theorem relies on the following invariant, verified at any iteration: VW E Poss( P), 3( E, d) E LD such that w E E or 3!E E Env such that w E E or 3!E E Bad such that w E E, The invariant is proved by induction on the algorithm (we omit the proof for length considerations). Applying the invariant to the end of the last iteration gives VW E Pass(P), either 3( E, d) in LD such that w E E, or 3E E Bad such that w E E. Together with Propositions 4 and 5, this achieves proving the theorem.

Since the set of possible worlds covered by LD grows monotonically as the algorithm runs (and so is Bad) it is possible to use the algorithm as an "anytime" algorithm. Actually, LD tends to a cover of Good(Q) and Bad tends to a subset of Bad(Q) .

Proposition 7 If the algorithm runs until it stops, Q is consistent ifl Bad # 0.

The proof follows easily from Propositions 6 and 4. Qbviously, if Bad = 0 and 1 LDI = 1 then Q is strongly consistent. The converse is not true; more generally, the list LD may not be minima15.

Partial CSP (Freuder, 1989) also handles simultaneously a family of CSPs (representing the possible relaxations of an overconstrained CSP) but the original motivation of this framework is not to handle decision under incomplete knowledge, and therefore lacks the distinction between controllable and uncontrollable variables. In (Helzerman and Harper, 1994) an efficient algorithm is proposed for enforcing arc-consistency simultaneously in a family of CSPs sharing some variables and constraints; such a family is related to our set of candidates, but again, this approach does not enable decision under incomplete knowledge. Now, in the field of knowledge representation (Boutilier, 1994) proposed a logical, qualitative basis for decision theory, distinguishing like us between controllable and uncontrollable propositions, but without the notion of conditional decision. Poole's independent choice logic (Poole, 1995) also distinguishes between the nature's choice space and the agent's choice space, in order to build strategies which are similar to our conditional decisions; it also includes the representation of probabilities, utilities and knowledge-gathering actions. In this paper we proposed an anytime algorithm for computing conditional decisions under the full observability assumption. Further work will consist first in implementing and testing our algorithm; for this we think of exploiting 5For instance, it may be the case that the last decision added to the list covers all possible worlds but that many decisions have been added to the list before. Of course, one could think of checking afterwards whether some decisions are redundant, but this could be very costly.

results from the area of dynamic constraint satisfaction (Dechter et al., 1988), where several techniques are proposed in order to solve a sequence of CSP that differs only in some constraints more efficiently than by naively solving each CSP one after the other. Furthermore, the computation of a compact representation of conditional decisions could also probably be performed using Finite Automata (as (Vempaty, 1992) for sets of solutions) or Binary Decision Diagrams [START_REF] Bryant | Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams[END_REF]. It is clear that, at this level of complexity, algorithmic issues may be crucial.

Since our contribution consists in extending the CSP framework in order to deal with decision problems under incomplete knowledge (namely by distinguishing between controllable and uncontrollable variables), it can be considered as a first step to embed decision theory into constraint satisfaction; other important steps in this direction would consist in considering probabilities, utilities and sequences of decisions. A first step towards handling probabilistic knowledge in constraint satisfaction has been proposed in (Fargier et al., 1995), where the uncertainty on the values of parameters is encoded by a given probability distribution instead of a set of constraints. Utility functions would enable us to represent flexible goals and it should not be hard to embed them in our framework; in the constraints of C, an extra field is added to each tuple, namely the utility of the corresponding assignment, as in (Schiex et al., 1995, Bistarelli et al., 1995). Extending our framework to sequences of decisions is significantly harder. The partition of the variables is not sufficient: not only decisions are influenced by parameters, but the value of some parameters may also be influenced by earlier decisions; for this we may structure decision variables and parameters in a directed network, in the same spirit as influence diagrams [START_REF] Howard | Influence Diagrams, Influence Diagrams[END_REF]6 , a link from Xi to xj meaning that the allowed values of the decision variable xj depend on X;, and a link from xi to Xj meaning that the decision of assigning a value to xj has or may have some effects on Xj .

An interesting potential application of mixed constraint satisfaction and its possible extensions is planning under uncertainty. Clearly, this topic needs the notion of controllability, and would gain a lot in being encoded in an extension of the CSP framework -since it could benefit from the numerous advances on the resolution of CSPs. The similarity between our conditional decisions and conditional plans is clear, at least for a single action. For handling sequences of actions, mixed CSPs have to be extended as evoked in the previous paragraph.

Non-deterministic effects of actions may be encoded by using extra parameters.

Lastly, many recent approaches to planning make use of decision theory; clearly, extending mixed CSP with a larger part of decision theory goes in this direction; our long-term goal is thus to provide a constraint satisfaction based framework to decision-theoretic planning.

  {A,, A,}; Ll = La = {a, b, c, d} -K: contains only one constraint: Co: XI # X2 -C contains three constraints Cl, C2, C3: Cl c2 c3 f'o4') = {(a, b), (a, 4 (~4, @+4 (W, @A Cc, 4 (c, b), (c, d), @,a), (d, b), (d, c)}. tit WI = (d, b) and w = (d, c); the decisions covering w1 are (3,1,2) and (3,1,3). It can be checked that no decision covers ~2, and that all other possible worlds are good: Bad(P) = (~2). Lastly, let dl = (1,3,3), then Coversp(dl) = {a, b} x {a, c}.

  uniformly consistent ifs it has a universal decision, and strongly consistent iffit has a strong universal decision.

  it can be solved in polynomial time on a non- deterministic Turin 5 machine using N P-oracles; a decision problem is in co-C, = II: iff its complementary problem is in Cc. The role of the "canonical" complete problem (which is played by SAT for NP) is played by 2-QBF for Cr; 2-QBF is the problem of deciding whether the following quantified boolean formula is true: XVb'F(Z, c). The complementary problem 2-QBF (vz %F(a', 6)) is complete3 for II<. Strong consistency (resp. consistency) looks similar to 2-QBF (resp. to 2-QBF) since it involves the same alternation of quantifiers. roposition 1 The problem MIXED-SAT of deciding consistency of a binary mixed CSP is II:-complete.

  decomposes E into a set of disjoint sub-environments Dec( E, R) such that all worlds of E belong either to R or to one of the sub-environments of the decomposition. The decomposition is unique if an ordering on the variables is fixed. WhenEnR = 0 we let Dec(E, R) = (E); and when E C R,Dec(E, R) = 0. Thus, this decomposition is actually a subtraction since we end up with a list of disjoint environments which cover exactly the worlds of E \ R. W; {list of decisions with the env. covered} Env:= {& x .a. x Lp}; {list of env. not yet covered by LD} Bad:= 0; {list of non coverable env.} Repeat E := an environment from Env; {possible heuristics} If (A, L, K: U E) is consistent (1) {E contains possible worlds} then If (A U X, L x D, K U C U E) is inconsistent (2) {E contains only non-coverable worlds} then Bad :=Bad UE else s := a solution of (A U X, L x D, K: U C U E); d := projection of s on the decision variables; {d covers at least one possible world of E} R := Caversp (d) {unary constraints on par-am.} Add (R, d) to LD; Env:= UFEEnVDeC(F, R)

  ",I; d3 = (1,3,3); R = {a, b} x {a, c); Dec([El, [~f3=Dec([~l, [::1)=0; ~4,d,l7 rzl) =c& ~4[abCcdl' [::I> = Uabccdlh Env= tr,",1, Lbccdlh LD=N:I> c41> 2% &gJ (1>2,3)), ([::I7 (19 39 3))) E = [ ,",I; K: U C U E inconsistent (but K U E consistent). Bad = tr,",1> E = [=bCcd]; & = (2,2,3); R = (a, c} x (a, b, d); ~4[,Ll7 Lx& = Klh Env = Klh LD = {<[:I, (3,1,2)), (l:;d]' (L2,3)), ([::I, (L3, W, ([::g' (29 27 3))) E = [:I; K: U E inconsistent. Env = 0. STOP Finally, the last value of LD is {([if], (3,1,2)), ([Qabbd], (1,2,3)), ([:!I, (L3,3)L ([~~.Jl' C&T WI, and Bad = {[,",Ih This allows us to build a conditional decision where each world w is mapped to the decision S(W) = dj associated to the first item (E, dj) such that E contains w (shown on the table below

Proposition 4

 4 At any point of the algorithm, if E E Bad then E n Pass(P) C Bad(Q) and E n Pass(P) # 0. Proposition 5 Atanypointofthe algorithm, if(E, d) E LD then VW E E, (w, d) satisfies C. Proposition 6 (Correctness of the algorithm) Zf run quietly, the algorithm stops, the jnal value of LD dejnes an optimal conditional decision for Q and the jinal value of Bad contains Bad(Q), Sketch of proof:

Constraint Satisfaction

Constraint Satisfaction

Constraint Satisfaction


Maria Vittoria Cubellis
email: cubellis@unina.it

Marc Baaden
email: baaden@smplinux.de

Giuseppina Andreotti

Taming molecular flexibility to tackle rare diseases

Keywords: molecular dynamics, disease, diagnostic use, protein stability AGAL, lysosomal alpha-galactosidase, DGJ, 1-deoxy-galactonojirimycin, RMSD, Root mean square deviation, RMSF, root mean square fluctuation Highlights

come

Taming molecular flexibility to tackle rare diseases.

Introduction

For most diseases different types of mutations exist and each type requires a specific therapeutic approach. Some mutations lower the free energy difference between the folded and the unfolded protein, shifting the equilibrium towards the latter one. Unstable proteins, although retaining the functional chemical groups needed for the biological activity, are sensitive to proteolysis and are cleared by the protein quality control systems in the cell. Hence, for these mutations, which represent a good share of all the ones associated with human diseases [START_REF] Yue | Loss of protein structure stability as a major causative factor in monogenic disease[END_REF], the reduction of the protein concentration in the cell is the primary effect and the reduction of total activity is only a secondary effect. Small chemicals, which are known as pharmacological chaperones, bind preferentially to the folded state, thereby at least partially restoring the equilibrium between folded and unfolded states, and rescue these mutants [START_REF] Aymami | Pharmacological chaperones for enzyme enhancement therapy in genetic diseases[END_REF]. They cannot be used for all the genotypes of a given disease, but in general are limited to those which retain residual activity. Nonetheless pharmacological chaperones offer advantages, low cost, oral administration and increased bioavailability. Beside pharmacological chaperones, other small molecules are being evaluated for therapy. They are not specific for a given mutated protein, but alter protein homeostasis [START_REF] Ryno | Targeting unfolded protein response signaling pathways to ameliorate protein misfolding diseases[END_REF].

Computational modeling, for instance molecular dynamics simulations, can be used to predict residual activity in the cell. This knowledge is important both for diagnosis and for therapy, because residual activity, the severity of the disease, and responsiveness to small molecule drugs are correlated.

Fabry disease represents a good example to show how conformational flexibility predictions can be used for designing original treatments for rare diseases. Among the many computational techniques that exist to predict protein flexibility such as normal mode analysis and distance geometry approaches, we will focus on molecular dynamics (MD). Fabry disease is X-linked and relatively frequent, 1-9 in 100000 (OMIM: 30150). Different mutations of the gene encoding lysosomal alpha-galactosidase A (AGAL) result in a wide phenotypic spectrum, with respect to age at onset, rate of disease progression, severity of clinical manifestations. Patients with the late onset or atypical form of Fabry disease retain some AGAL activity and are asymptomatic until adult age when they develop cardiac and kidney problems [START_REF] Germain | Fabry disease[END_REF].

The treatment of Fabry disease with a pharmacological chaperone 1-deoxy-galactonojirimycin (DGJ) was first proposed by Fan et al in 1999 [START_REF] Fan | Accelerated transport and maturation of lysosomal alphagalactosidase A in Fabry lymphoblasts by an enzyme inhibitor[END_REF]. The introduction in clinical practice of galactose to enhance AGAL activity in patients was reported by Frustaci et al. in 2001 [6]. Since then, responsiveness to pharmacological chaperones has been assessed for a huge number of AGAL mutations, covering both early and late onset forms of Fabry disease (for a review please consult Fabry_CEP [START_REF] Cammisa | Fabry_CEP: a tool to identify Fabry mutations responsive to pharmacological chaperones[END_REF] and references therein). A relatively large proportion of mutants, in particular among mutations associated with the late onset form of Fabry disease, recover activity when treated with DGJ. In a few cases it was possible to prove that DGJ acts by enhancing thermodynamic stability of the mutants [8] [9].

In this paper we correlate the flexibility of the sites where AGAL mutations occur with the residual activity in the cells. This result is useful for the evaluation of severity and the choice of a personalized therapy. The direct measure of residual activity in the cells for each case would be impractical because more than 520 missense/nonsense mutations have been described in the databank HGMD® professional [START_REF]HGMD[END_REF] for Fabry disease and most of them are private, that means that they are seen in a single family.

2

Materials and methods

Molecular dynamics simulations

We used the structure of AGAL solved in the presence (3GXT) or in the absence (3GXN) of DGJ at pH 4.5 as input. We run a 50 nanosecond MD simulation with the amber03 force field (a variant of the AMBER-99 one [START_REF] Wang | How well does a restrained electrostatic potential (RESP) model perform in calculating conformational energies of organic and biological molecules?[END_REF]) at the same pH at which crystals were grown. We used the Yasara program under default conditions combined with fully automatic optimized assignment of topology and parameters for the ligand using the AutoSMILES procedure [START_REF] Krieger | Making optimal use of empirical energy functions: force-field parameterization in crystal space[END_REF][START_REF] Krieger | Increasing the precision of comparative models with YASARA NOVA--a self-parameterizing force field[END_REF]. All systems were solvated with explicit TIP3P water molecules and Na+ and Cl-counterions were added as background salt and to preserve overall electrical neutrality. Each system was energy minimized by using the steepest descent method to relax any steric conflicts before beginning the simulations. Simulations were carried out with periodic boundary conditions. Long-range electrostatic interactions were calculated by using PME with a direct-space cut-off of 7.86 Å. All simulations were performed by using an NVT ensemble at 298 K. A 2 fs/1 fs double-integration time step was used. Root mean square deviation (RMSD) between structures following least-squares fitting to the reference energy-minimized input structure, was calculated with Gromacs [START_REF] Van Der | GROMACS: fast, flexible, and free[END_REF]. The RMSD value increases steadily in the first 25 nanoseconds. After the stabilization of the system, Root mean square fluctuations (RMSF) of alpha carbons of each residue were calculated with Gromacs [START_REF] Van Der | GROMACS: fast, flexible, and free[END_REF].

Miscellaneous

Graph plotting was carried out with Kaleidagraph (Synergy Software, PA).

We assigned secondary structure with SEGNO [START_REF] Cubellis | Secondary structure assignment that accurately reflects physical and evolutionary characteristics[END_REF]. Active site residues were identified with DrosteP [START_REF] Cammisa | Identification and analysis of conserved pockets on protein surfaces[END_REF]. The figure showing the AGAL structure colored by RMSF was produced with CHIMERA [START_REF] Pettersen | UCSF Chimera--a visualization system for exploratory research and analysis[END_REF].

Results and discussion

Correlation between alpha-galactosidase flexibility and residual activity of missense mutants in the cell

An attempt to systematically classify the phenotype of Fabry disease based on structural features of AGAL was made by Saito [START_REF] Saito | Prediction of the clinical phenotype of Fabry disease based on protein sequential and structural information[END_REF]. In this previous work, mutations were divided into two categories defined as classic or atypical based on clinical signs. We believe that this classification is too simplistic because for most mutations few affected people are known and symptoms are variable even among patients with the same mutation [START_REF] Rigoldi | Intrafamilial phenotypic variability in four families with Anderson-Fabry disease[END_REF]. In general, residual enzyme activity is associated with a less severe phenotype [START_REF] Branton | Natural history of Fabry renal disease: influence of alpha-galactosidase A activity and genetic mutations on clinical course[END_REF][START_REF] Ries | Genotype-phenotype correlation in Fabry disease[END_REF]. We decided to use a different approach and move from binary categories to real values, taking advantage of the fact that enzymatic activity of mutants has been measured in cells derived from patients or in cells transiently transfected with plasmid carrying a specific AGAL mutation.

We collected data from several laboratories [START_REF] Andreotti | Therapy of Fabry disease with pharmacological chaperones: from in silico predictions to in vitro tests[END_REF] [23] [24-28] and examined 244 mutations altogether. The effect of mutations depends critically on the positions of the affected residue in the protein structure and secondarily on the type of substitution, conservative ones being more tolerated. In a few cases, lack of activity can be explained straightforwardly because the mutation affects the active site or disulphide bridges. We define active site residues as those that line the most conserved pocket in the protein structure: by this definition the active site residues in AGAL are W47, D92, D93, Y134, L168, D170, Y207, R227, E203, L206, D231, S297. When these amino acids are mutated, activity is null or proximal to zero. Disulphide bridges are essential to maintain the 3D-structure of the protein and it is not surprising that when a cysteine involved in a bridge (C52, C94; C56, C63; C142, C172; C202, C223; C378, C383) is mutated, fold, and consequently activity, is lost. It is worth observing that not all the cysteine residues in AGAL form disulphide bridges, the exception being C90 and C174.

When the active site is not severely compromised, the activity in the cells depends on two factors, the specific activity (U/mg) and the amount of the mature protein, which in turn depends on stability. Only in a very few cases it was possible to purify mutants and measure specific activity or stability independently, but in these cases it was shown that most missense mutations observed in Fabry patients do not affect the maximal velocity (kcat) or the affinity for substrate (KM) [START_REF] Ishii | Mutant alpha-galactosidase A enzymes identified in Fabry disease patients with residual enzyme activity: biochemical characterization and restoration of normal intracellular processing by 1-deoxygalactonojirimycin[END_REF]. In order to analyze all mutations and try to correlate their effect in the cell with the position in the protein structure, we calculated an average residual activity per site. For example, we assign a value of 10.75% to Q327 because Q327K and Q327E have 0 or 21.5% residual activity, respectively. We divided the data in two sets. The first one includes 66 sites with zero average residual activity, the second one 92 sites with non null average residual activity. This distinction is motivated by the observation that the residual activity and stability in the cell correlates only for mutants that are not completely inactive.

We carried out MD simulations using the structure of AGAL solved in the absence (3GXN) or in the presence (3GXT) of DGJ at pH 4.5 [START_REF] Lieberman | Effects of pH and iminosugar pharmacological chaperones on lysosomal glycosidase structure and stability[END_REF] as input. We run a 50 nanosecond simulation at the same pH at which crystals were grown and calculated root mean square fluctuation (RMSF) values as a measure of flexibility per residue. In Fig. 1, the structure of AGAL solved in the presence of DGJ (3GXT) was colored by RMSF with colors ranging from blue (low flexibility) to white (medium flexibility) to red (high flexibility). AGAL is a homo-dimer and each subunit is made up by two domains, a TIM barrel where the active site is located and an antiparallel beta domain. Inspection of Fig. 1 suggests that flexibility is minimal in the regions not exposed to solvent buried between subunits, between domains or inside the TIM barrel.

Indeed accessibility (percent of residue surface exposed to solvent) and flexibility follow the same trend but direct correlation between the two properties is relatively low, approximately 70%.

In Fig. 2 we show RMSF for the molecular dynamics run reported on the structure without the drug (blue line) or with the drug (black line).

There is little difference between the two. Notably the region where the highest difference is observed, spans aa 173-177. This observation is interesting because Asp 170 makes a salt bridge with the heterocyclic nitrogen in the drug molecule [START_REF] Lieberman | Effects of pH and iminosugar pharmacological chaperones on lysosomal glycosidase structure and stability[END_REF].

The beta strand of the TIM barrel at the tip of which are located the active site residues, form the rigid core of the protein. The active site residues are rigid both in 3GXN and 3GXT. Circles represent sites where mutations are associated with null residual activity (first set). As can be observed, these sites are mostly found in regions corresponding to minima of flexibility or correspond to cysteines involved in disulphide bond formation (filled red circles in Fig. 2).

We correlated the residual AGAL activity measured in cells with the RMSF per residue obtained from running MD simulations on the substrate-bound 3GXT structure.

As shown in Fig. 3 the correlation is medium (Pearson correlation coefficient R 0.50 ; p<0.0001), but the trend is clear. When looking at this figure it should be born in mind that the experimental data come from several labs [22] [23-28], who applied different methods and no attempt was made to exclude a priori those mutants that are known to have reduced kcat or higher KM. Mutations occurring at flexible sites tend to be less severe. It is interesting to analyze the outliers, i.e. flexible residues that once mutated, have lower activity than expected (red in Fig. 3). Most of the outliers are residues for which abnormal kinetic parameters were determined (E59K or R112H) [START_REF] Ishii | Mutant alpha-galactosidase A enzymes identified in Fabry disease patients with residual enzyme activity: biochemical characterization and restoration of normal intracellular processing by 1-deoxygalactonojirimycin[END_REF],

residues lining the active site pocket (Y207) [START_REF] Andreotti | Prediction of the responsiveness to pharmacological chaperones: lysosomal human alpha-galactosidase, a case of study[END_REF] or intrinsically flexible glycine residues (G35, G183, G258, G260, G261, G325, G360, G395) which can adopt unusual dihedral angles. Due to the correlation between flexibility and accessibility, it is not surprising that mutations occurring at exposed sites tend to retain residual activity. However it is not possible to find a molecular-level explanation to justify the numerous exceptions observed among buried as well as exposed sites (data not shown).

We gathered data on the activity of AGAL mutants in cells treated with DGJ [START_REF] Andreotti | Therapy of Fabry disease with pharmacological chaperones: from in silico predictions to in vitro tests[END_REF][START_REF] Lukas | Functional characterisation of alpha-galactosidase a mutations as a basis for a new classification system in fabry disease[END_REF][START_REF] Park | Effects of a chemical chaperone on genetic mutations in alpha-galactosidase A in Korean patients with Fabry disease[END_REF][START_REF] Shimotori | Novel mutations of the GLA gene in Japanese patients with Fabry disease and their functional characterization by active site specific chaperone[END_REF][START_REF] Shin | Prediction of response of mutated alpha-galactosidase A to a pharmacological chaperone[END_REF][START_REF] Spada | High incidence of later-onset fabry disease revealed by newborn screening[END_REF][START_REF] Wu | A pharmacogenetic approach to identify mutant forms of alphagalactosidase A that respond to a pharmacological chaperone for Fabry disease[END_REF]. Mutations occurring at the first group of sites, i.e. those with null residual activity, show little, if any, response to the drug, although exceptions are observed. For all mutations occurring at the second group of sites, i.e. those retaining residual activity, exposure to the drug is beneficial. However, the increase of activity is highly variable and does not correlate with RMSF (data not shown).

The approach presented here, validated through an extensive dataset for Fabry disease, is easy to generalize for any disease-related protein with available structural data. MD simulations as those used in the present study can nowadays almost be setup automatically and improved computing resources allow a swift execution of such runs. It remains to be assessed whether simpler and computationally even less demanding approaches may lead to correlations of comparable quality.

Concluding remarks

Fabry disease offers an exquisite example to prove the usefulness of chemico-physical methods for medicine. With regard to diagnosis, we correlated protein flexibility, predicted from MD simulations on the AGAL protein structure, with the residual activity of the pathological mutants measured in cells. Residual activity in turn correlates with the severity of the disease [START_REF] Branton | Natural history of Fabry renal disease: influence of alpha-galactosidase A activity and genetic mutations on clinical course[END_REF][START_REF] Ries | Genotype-phenotype correlation in Fabry disease[END_REF]. With our approach, we tried to overcome and enrich the binary "disease versus non-disease" classification of mutations. Our analysis reflects the spectrum of Fabry disease severity and helps identifying those patients who are eligible for pharmacological therapy. People affected by mutations that occur at very flexible sites should possess a relatively high residual activity and are likely to develop a mild and late form of the disease, people affected by mutations occurring at sites of intermediate flexibility should possess some residual activity and are likely to develop a mild form of the disease that is responsive to pharmacological chaperones [START_REF] Lukas | Functional characterisation of alpha-galactosidase a mutations as a basis for a new classification system in fabry disease[END_REF]. People, in particular males, affected by mutations that occur at rigid sites, or affecting the active site or glycines with positive dihedral angles should have null residual activity and, consequently, severe and early onset Fabry disease. Nonetheless even in the less favorable case, some mutations might recover activity upon treatment with pharmacological chaperones [23] [24-28]. The need of a graduated prediction of disease mutations will be more and more urgent when exome sequencing becomes largely employed. The case offered by Fabry disease with more than 400 missense mutations and large phenotypical differences will become common among genetic diseases. It will not be sufficient to classify a mutation as pathological one, but it will be necessary to predict whether the symptoms associated to a given genotype are severe, and which type of therapy is most appropriate.

Figure 1 .

 1 Figure 1. Crystal structure of AGAL (3GXT) in complex with DGJ (yellow). The structure was

Figure 2 .

 2 Figure 2. RMSF for the molecular dynamics run reported on the structure without the drug (blue line) or with the drug (black line). Circles represent sites where mutations are associated with null

Figure 3 .

 3 Figure 3. Correlation of residual AGAL activity measured in cells with the RMSF per residue

Fig1 2

 2 Fig1 2-column fitting image

Acknowledgements

The financial support of Telethon -Italy (Grant no. GGP12108), by the Università Federico II, programma Breve Mobilità and "Programma F.A.R.O. IV tornata" (to MVC) is gratefully acknowledged. This work was supported by the "Initiative d'Excellence" program from the French State (Grant "DYNAMO", ANR-11-LABX-0011-01).

We are grateful to Dr Sophie Sacquin-Mora for fruitful discussion and advice and to Mr Emilio Castelluccio for technical assistance. This work is dedicated to our friend and colleague Dr Maria Malanga.

Fig3 single column fitting image

Competing interests

Maria Vittoria Cubellis was a consultant for Shire HGT in 2012.


Nicolas Le Sommer
email: nicolas.le-sommer@univ-ubs.fr

Lionel Touseau
email: lionel.touseau@st-cyr.terre-net.defense.gouv.fr

LoRaOpp: A Protocol for Opportunistic Networking and Computing in LoRa Networks

Keywords: IoT, Opportunistic Networking, LoRa

LoRa is one of the major communication technologies for Low Power Wide Area Networks, and a convenient technology for the Internet of Things. LoRa is usually associated with LoRaWAN, which is a protocol relying on a star network topology, in which end-nodes are connected through one-hop wireless links to one or several gateways. Despites the long range characteristics of the LoRa physical layer, physical obstacles, interferences and mobility can sometimes prevent end-nodes to communicate with gateways through single-hop links.

This paper presents a new opportunistic protocol for LoRa, called LoRaOpp, that supports multi-hop communications between pairs of nodes and between nodes and gateways, even without end-to-end paths between them. This paper also presents experimental results obtained for LoRaOpp in real conditions and in emulation.

I. INTRODUCTION

Over the last years, Low-Power Wide Area Networks (LPWANs) have received much attention from the research community and the industry for IoT applications dedicated to various domains, such as smart cities, smart agriculture and smart industry. Among existing communication technologies for LPWANs, LoRa is one of the most promising standards. It is robust to interferences, it utilizes unlicensed spectrum sub-GHz ISM bands, and it provides symmetric modulation for uplink and downlink, thus facilitating device-to-device communications and the construction of ad hoc networks. Some experiments showed that the LoRa communication range can be longer than 10 km in advantageous outdoor conditions (i.e., without physical obstacles between end-nodes and gateways), but also that it can be drastically reduced when devices are deployed in environments with natural or artificial obstacles (e.g. mountains, buildings, undergrounds). The simple star network topology considered with LoRaWAN, in which nodes and gateways must be in the radio range of each other to communicate, can be limiting in certain challenging environments. Several works have investigated these last years solutions relying on multi-hop transmissions [START_REF] Cotrim | LoRaWAN Mesh Networks: A Review and Classification of Multihop Communication[END_REF] in order to extend the network coverage in such environments, without having to deploy additional gateway devices. Many of these works rely on assumptions that make them appropriate only for specific use cases. For instance, they often assume that the periods of activity and of communication of nodes are synchronized in order to create end-to-end paths between nodes and gateways. A few number of these works [START_REF] Bor | LoRa for the Internet of Things[END_REF], [START_REF] Florita | Opportunistic lora-based gateways for delay-tolerant sensor data collection in urban settings[END_REF], [START_REF] Tanjung | OODC: An Opportunistic and On-Demand Forwarding Mechanism for LPWA Networks[END_REF] implement opportunistic networking techniques to support the temporal, and sometimes the spatial, disruptions that can occur in the communication paths due to the mobility or to the sleep phases of the nodes acting as relays. But here again they rely on strong assumptions such as the fact that nodes must always be up to receive beacons from the gateways in order to send them their data [START_REF] Florita | Opportunistic lora-based gateways for delay-tolerant sensor data collection in urban settings[END_REF].

In this paper, we propose a new multi-hop routing protocol for LoRa, called LoRaOpp. This protocol implements opportunistic networking techniques in order to allow devices to exchange data even if there is no end-to-end path between them at anytime. It combines several mechanisms to efficiently forward packets in the network while limiting the number of packets that are disseminated in this one. Some of these mechanisms have been studied in past research works dealing with disruption-tolerant and opportunistic networking [START_REF] Mota | Protocols, Mobility Models and Tools in Opportunistic Networks: A Survey[END_REF] (e.g. source routing, "spray and focus" approach [START_REF] Spyropoulos | Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility[END_REF], limitation of the number of hops and of the lifetime of packets), but they have not been considered so far in works implementing opportunistic networking techniques in LoRa-based protocols [START_REF] Bor | LoRa for the Internet of Things[END_REF], [START_REF] Florita | Opportunistic lora-based gateways for delay-tolerant sensor data collection in urban settings[END_REF], [START_REF] Almeida | A Multi-Technology Opportunistic Platform for Environmental Data Gathering on Smart Cities[END_REF], [START_REF] Tanjung | OODC: An Opportunistic and On-Demand Forwarding Mechanism for LPWA Networks[END_REF]. With this protocol we want to evaluate the communication performances that can be obtained, notably in terms of delivery time and ratio, on various network setups without requiring a synchronization of the activity and communication periods of nodes, and while complying with sub-Ghz regulation -1 % duty cycle must be observed.

The rest of this paper is organized as follows. Section II presents research works investigating LoRa opportunistic communications. Section III details the main features of LoRaOpp. The experimental results we obtained for this protocol, both in real conditions and in emulation, are presented in section IV. Section V concludes this paper by summarizing our contribution and by mentioning the future improvements we would like to make for LoRaOpp.

II. RELATED WORK

Works [START_REF] Dias | Lorawan multi-hop uplink extension[END_REF], [START_REF] Chall | LoRaWAN Network: Radio Propagation Models and Performance Evaluation in Various Environments in Lebanon[END_REF], [START_REF] Zhou | LoRa-Hybrid: A LoRaWAN Based Multihop Solution for Regional Microgrid[END_REF], [START_REF] Farooq | Introducing Scalability in LoRa-Based Networks through Multi-Hop Communication Setups[END_REF], [START_REF] Liao | Multi-Hop LoRa Networks Enabled by Concurrent Transmission[END_REF], [START_REF] Abrardo | A Multi-Hop LoRa Linear Sensor Network for the Monitoring of Underground Environments: The Case of the Medieval Aqueducts in Siena, Italy[END_REF] have investigated and proposed solutions to support multi-hop communications in LoRa networks, mainly with the aim of creating and maintaining end-to-end paths between the nodes and the gateways. These solutions rely on strong assumptions, such as the synchronization of the activity and communication periods of nodes and on relay devices that are always up and powered. To overcome these constraints and to support the volatility and the mobility of nodes and gateways, which induce disruptions in communication paths, a small number of works have considered opportunistic communication techniques [START_REF] Almeida | A Multi-Technology Opportunistic Platform for Environmental Data Gathering on Smart Cities[END_REF], [START_REF] Florita | Opportunistic lora-based gateways for delay-tolerant sensor data collection in urban settings[END_REF], [START_REF] Tanjung | OODC: An Opportunistic and On-Demand Forwarding Mechanism for LPWA Networks[END_REF] to forward packets in intermittently-connected networks.

In [START_REF] Almeida | A Multi-Technology Opportunistic Platform for Environmental Data Gathering on Smart Cities[END_REF], Almedia et al. proposed a platform for data gathering in smart cities using both mobile and static devices equipped with Wi-Fi and LoRa interfaces. Three types of devices are considered in this work: 1) the Data Collecting Units (DCU), which are static or mobile devices equipped with sensors, 2) the sink stations, which are fixed devices that are connected to a server accessible from the Internet, 3) and mobile nodes that serve as relays to opportunistically deliver data from the DCU to the sink stations. This platform does not rely on LoRaWAN, but on an alternative LoRa MAC protocol designed to exploit the multiple sink stations that are present in the network. In [START_REF] Florita | Opportunistic lora-based gateways for delay-tolerant sensor data collection in urban settings[END_REF], Florita et al. also investigated data gathering in smart cities with an opportunistic communication system. This system is composed of two types of devices: fixed sensor nodes and mobile gateways, which are used to collect data from sensors. Gateways have two types of wireless communication interfaces: a LoRa interface to communicate with the sensor nodes, and a Wi-Fi interface to upload collected data to a server connected to the Internet. Unlike the system proposed in [START_REF] Almeida | A Multi-Technology Opportunistic Platform for Environmental Data Gathering on Smart Cities[END_REF], which uses either Wi-Fi or LoRa communications to exchange data between DCU and mobile devices, this one only supports LoRa communications between sensor nodes and mobile gateways for energy saving purposes. These gateways are embedded in vehicles moving around the city, allowing a node to send its data when the gateway is in its communication range. This communication system includes a new MAC layer protocol for the communications between a sensor node and a gateway, enabling a pull-based transfer of data. In [START_REF] Almeida | A Multi-Technology Opportunistic Platform for Environmental Data Gathering on Smart Cities[END_REF] and [START_REF] Florita | Opportunistic lora-based gateways for delay-tolerant sensor data collection in urban settings[END_REF], opportunistic communications are only considered between nodes and mobile devices, while they could also be applied between fixed nodes as proposed in [START_REF] Tanjung | OODC: An Opportunistic and On-Demand Forwarding Mechanism for LPWA Networks[END_REF]. Opportunistic networking and network coding techniques are combined in [START_REF] Tanjung | OODC: An Opportunistic and On-Demand Forwarding Mechanism for LPWA Networks[END_REF] in order to avoid a bottleneck that could be created by individual emissions of packets. In order to reduce unnecessary transmission between nodes and relays, an on demand feedback mechanism is implemented in a LoRaWAN forwarder. Relays only forward packets that are missing in feedback messages. Disruption-tolerant and opportunistic networking techniques studied in past research works [START_REF] Mota | Protocols, Mobility Models and Tools in Opportunistic Networks: A Survey[END_REF] have not been considered so far in previous works, while they could help addressing packets forwarding issues in intermittentlyconnected LoRa networks. Moreover, these works do not investigate the impact of the variation of the number of nodes and gateways on the communication performances, knowing that duty-cycling constraints must be observed for LoRa on sub-GHz ISM bands.

III. THE LORAOPP PROTOCOL

LoRaOpp is an opportunistic communication protocol designed to ensure data transmission in intermittently-connected LoRa networks, such as the network illustrated in Figure 1. Lo-RaOpp supports multi-hop data exchange between the nodes themselves and between the nodes and the gateways. LoRaOpp combines several methods and techniques in order to limit the number of packets that are forwarded in the network while providing efficient delivery times and ratios, such as source routing, transmission feedback techniques and the "spray and focus" method [START_REF] Spyropoulos | Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility[END_REF]. It also implements several strategies to select the data transmission paths. The remainder of this section outlines how the protocol LoRaOpp works and presents its main features.

A. Devices discovery

Three types of devices are currently considered in Lo-RaOpp, namely end-nodes, peer-nodes, and gateways. Both nodes and gateways are involved in the packet forwarding process. Transmission strategies of data packets and of presence advertisement packets depend on the type of the device. In use cases envisioned for LoRaOpp, end-nodes can measure and process physical quantities before transferring them to a server through gateways. They can access gateways directly or via intermediate nodes. Conversely, remote servers can send data to end-nodes through gateways and intermediate nodes. Like end-nodes, peer-nodes can transfer the physical quantities they have measured and processed to a server through gateways, can receive packets from this server, and on top of that, they can communicate with each other. They allow to build more complex network topologies than the star network topology considered by LoRaWAN. If the next intermediate device towards the destination is not reachable at the forwarding time, gateways and nodes temporarily store the packets that must be forwarded, and wait for a next contact opportunity to forward them.

Gateways announce their presence to the nodes by broadcasting dedicated packets at several hops in the network. Before exchanging data with their direct neighbors, endnodes advertise their presence at one hop. End-nodes will be discovered by gateways after sending them a packet. Gateways can deduce from these packets the distance between them and the nodes expressed in number of hops and time. As far as peer-nodes are concerned, they broadcast their advertisements at several hops in order to be discovered by the nodes with which they are expected to exchange data and to form a distributed IoT system. Developers of such IoT systems can specify the maximum number of hops that must be considered for the discovery of the nodes composing their systems and for transmission of data packets.

B. Forwarding algorithm

The general principle of the LoRaOpp's forwarding algorithm executed by the nodes is presented in Algorithm 1. It combines several transmission strategies depending on the type of the devices and on the type of packets that are emitted or received by the node. It is executed when the node starts for the first time, and whenever it wakes up.

A LoRa node will only receive the packets transmitted by the neighbor node having the strongest transmission signal when several of its neighbor nodes emit their packets simultaneously. Consequently, packets sent by some nodes can be lost if they are not retransmitted. To avoid these unsuccessful transmissions, and knowing that LoRa node transceivers operate on half-duplex communications, LoRaOpp implements both a collision detection mechanism based on a channel listening, and a retransmission process based on a transmission feedback (i.e. on an acknowledgment listing the packets that have been received). Emissions of packets are constrained by the duty cycling that must be observed on ISM frequency bands lower than 1 GHz.

LoRaOpp makes it possible to specify both the wake-up periods and the running times of the nodes. These parameters are taken into account in the transmission process, and have therefore an impact on the energy consumption of the nodes and on the packet transmission rate. They allow to mimic the behavior of class A, B or C nodes defined in the LoRaWan protocol.

Algorithm 1 Algorithm applied on node startup or wake-up.

C. LoRaOpp packets processing

Six types of packets are currently considered in LoRaOpp, which can respectively be used by nodes and gateways to advertise their presence in the network (hello packets) or their (temporary) leaving from this one (bye packets), to send data (data packets), to acknowledge the reception of data packets (ack packets), and to notify their direct neighbor when they start and stop data transmissions (start_transfer and end_transfer packets). Packets are implemented as payload of the physical layer.

Method process(pkt) used in Algorithm 1 behaves as described below. It's algorithm is not detailed due to the lack of space. The packets that are received by the nodes are processed according to their type. Hello carry information required by devices to keep their routing table up to date. Entries of routing tables are composed of the ID, the type of the target device, the path to reach this device, the number of hops to the target device, the expected transmission delay to send data to this one, and the last update time of the entry. Packets that can be forwarded in the network (i.e. Packets whose number of hops is greater than 1 and whose lifetime has not expired) are put into the cache of the devices in order to be forwarded by these ones when they will be able to.

When nodes gracefully leave the network, temporarily or definitively, they broadcast bye packets. Bye packets are processed similarly to the hello packets, except that they are used to remove information about the leaving devices from the routing tables. When a device is about to forward the packets stored in its cache, it sends a packet of type start_transfer to advertise its direct neighbors of the amount of data it will send, thus allowing them to define adaptive listening windows to receive all packets, or only a part of them if they must be put in sleep mode before receiving all packets. If all the data have not been received, the emission of the ack packet is postponed. When a device receives an end_transfer packet, it sends back an ack packet to acknowledge the data packets it received, thus allowing both the initial emitter and the intermediate forwarders to remove these packets from their cache. Each time a device receives a data packet, it checks if this packet is still valid and has not already been received and relayed. If not, it checks if it is the final recipient of this packet. If so, it forwards the packet to the application for processing purposes. Otherwise, it decreases the number of hops before storing the packet into its local cache, and marks this one as to be forwarded and acknowledged for the next emission phase. When end-nodes want to send data packets to a remote application server, they look up their routing table to find the best route to reach a gateway, and send the packet to this one specifying the route to follow. Peer-nodes proceed in a similar way when they want to send data packets to a remote application server or to another peer-node.

IV. EXPERIMENTS AND RESULTS

An outdoor experiment and several experiments in emulation were conducted in order to evaluate the performances of LoRaOpp and its scalability. The performance criteria we have sought to evaluate during these experiments are the delivery ratios and the delivery times of data packets. The delivery ratio is the number of packets received by their recipient(s) out of the number of packets that have been sent. The delivery time is the time between the moment a packet is received by its destination and the moment when the packet is sent by the source. The LoRaOpp's parameters and the number of nodes and of gateways used in these experiments are listed in Table I. In all these experiments only one copy of each packet is initially sent by the source node, and no additional copies are created in the network by the intermediate nodes. The selection of the paths that must be followed by data packets is based on the number of hops between the source and the destination. The paths with less hops are selected. A 1 % duty cycle is observed to comply with sub-Ghz regulation (for all packet transmissions, including hello and bye packets).

A. Outdoor experiments

The outdoor experiment was conducted on a large sports complex in the city of Vannes, France. The network was composed of 7 Heltech ESP32 devices equipped with a SX1276 LoRa node chip (868 Mhz), and was deployed following the topology shown in Figure 1. Three of the seven devices act as end-nodes, three as peer nodes, and one device as a gateway. The wake up and running periods of nodes are defined respectively between 5 and 15 minutes, and between 1 and 4 minutes. The experiment lasted for 2 hours. At each wake up periods, the nodes generate a data packet that is intended for a gateway, and whose payload is a string of 32 bytes including a JSON object that carries a temperature measurement.

The averages and the medians of the delivery delays and ratios of data packets that were measured during the experiment, are presented in Table II. All the data packets sent by the nodes were received by the gateway. They were delivered with an average delay and a median delay of 334 and 285 milliseconds respectively. The median and the average values of the hops that were necessary to deliver these packets are 2 and 2.5. Thus, the average of transmission delay per hop is around 133 milliseconds, knowing that the optimal transmission delay for a data packet with a payload of 32 bytes with a spreading factor of 7, a coding rate of 4/5, a signal bandwidth of 125 kHz and a frequency band of 868 MHz is 95 milliseconds. The best value obtained in this experiment for the one-hop transmission delay is consistent with this theoretical value. The best values obtained for several hops are also consistent with the theoretical values related to the implementation of LoRaOpp, and which follow the formula t h data = h * (t ack + t data ), where h is the number of hops between the source and the destination, and t ack and t data are respectively the transmission delays for the acknowledgment and the data packets at one hop. In these favorable transmissions, the period of emission and reception of devices are in phase, allowing to build an end-to-end path between the source and the destination.

B. Performance evaluation in emulation conditions

In order to evaluate LoRaOpp in larger networks, we have conducted experiments in emulation. The code running on emulated nodes is the same as the code running on actual nodes. The behavior of the LoRa physical layer is reproduced as accurately as possible using a software stack. For comparison purposes, we first evaluated LoRaOpp in emulation with a network topology comparable to that considered in the outdoor experiment, and on 4 additional randomized network topologies also composed of 6 nodes and 1 gateway. Each setup was run 10 times, with randomly varying node runtime periods and wake up intervals. The results obtained in emulation for a network topology similar to the one considered in the outdoor experiment, are very close to those obtained in this experiment. The results obtained for the other randomized network topologies, gave us slightly better results. The delivery ratios also reached 100%. The average of the number of hops needed to deliver data packets dropped from 2.5 to 2.2 in emulation, and the average and the median of the delivery times dropped respectively from 33.42 and 28.49 seconds in actual conditions to 21.20 and 14.06 seconds in emulation. These better results can be explained by the fact that in some topologies nodes are closer to the gateway, what causes packets to be forwarded faster.

Three additional configurations, with specifically different node/gateway distributions, namely 25 for 2, 50 for 5, and 100 nodes for 10 gateways, have been considered in order to assess the efficiency of the LoRaOpp protocol in the gateway and path selection process. These configurations were each run on 5 randomized network topologies. Each setup was run 10 times, with randomly varying node runtime periods and wake up intervals. The results of these 150 additional runs were evaluated on the same criteria as the actual experiment. As works presented in [START_REF] Almeida | A Multi-Technology Opportunistic Platform for Environmental Data Gathering on Smart Cities[END_REF], [START_REF] Florita | Opportunistic lora-based gateways for delay-tolerant sensor data collection in urban settings[END_REF], [START_REF] Tanjung | OODC: An Opportunistic and On-Demand Forwarding Mechanism for LPWA Networks[END_REF] are not publicly available, and thus cannot be tested in real and emulation conditions, we executed, for comparison purposes, on the same setups the Epidemic Routing (ER) protocol [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF], which is an opportunistic protocol known to provide the best results in terms of delivery times and ratios, but as being a bad one in terms of network load as packets are forwarded by, and replicated on, all the nodes of the network.

The results are presented in Figure 2. They show that the performances provided by the LoRaOpp and the ER protocols are slightly impacted by the increase of the number of nodes in the network, and by the resulting larger number of packets that are exchanged. Few variations in the packet delivery times and rates can indeed be observed.

On one hand, the shorter delivery times for an increasing number of nodes can be explained by the fact that, for very similar contact durations, there is more contact opportunities as each node has more neighbors (respectively an average of 1, 2, 4 and 9 neighbors for the nodes/gateways configurations 6/1, 25/2, 50/5 and 100/10). Therefore it is easier to find a route to reach the destination. The increase in the number of gateways and therefore of possible destinations also contributes to this performance improvement.

On the other hand, we can notice that the packet delivery rate decreases inversely with the number of nodes. For example for LoRaOpp, 100% of packets are delivered for network topologies composed of 6 nodes and 1 gateway, while the average delivery ratio drops to 93% for 100 nodes and 10 gateways. The increase in the number of possible destinations, through the increase in the number of gateways, however slightly improves the delivery rate, as observed when comparing the results for 100 nodes and for 50 nodes. Less hops are indeed required to deliver a packet for 100 nodes and 10 gateways than for 50 nodes and 5 gateways.

To confirm this hypothesis, we conducted other experiments to study how LoRaOpp behaves when the number of destinations varies while the number of nodes remains the same. In these experiments we considered 1, 2, 5 and 10 gateways as destinations in a network composed of 100 nodes. The results are presented in Figure 3. They show that the LoRaOpp protocol can benefit from the presence of several gateways in the network to improve packet delivery. They also show that the more gateways there are, the less nodes are solicited to forward packets. As a consequence, more packets can overall be delivered because the retransmission load is more evenly distributed across the network, and therefore the duty cycle limit is reached less quickly on each node.

In addition, Figure 2 highlights that even though ER shows better performances than LoRaOpp, it however causes a significantly higher network traffic as presented in Table III. ER generates 2.02, 6.31, 20.04 and 72.84 times more packets than LoRaOpp does in the considered configurations. The better performances achieved with ER can be explained by the fact that ER allows all nodes to forward packets in the network, while LoRaOpp only uses the nodes considered to be the best relays. ER thus makes it possible to use nodes that are less relevant for routing, but which are able to forward packets because they have not reached their transmission time limit set by the duty cycle.

In consideration with the previous observations, it seems interesting to take into account the ability of nodes to retransmit data when defining forwarding paths (i.e., when selecting the nodes that will be used as relays). Paths should therefore be also selected according to their transmission rate, and not solely on the basis of the number of hops and/or the forwarding delays recorded between the source and the destination.

V. CONCLUSION AND FUTURE WORK

In this paper we proposed an opportunistic multi-hop routing protocol for LoRa-based intermittently-connected networks, called LoRaOpp. This protocol is versatile enough to be used in the most diverse situations. It does not require a specific network topology. Different types of nodes and gateways can form the network. It supports multi-hop data exchange between the nodes themselves and between the nodes and the gateways, and it implements several techniques and methods to limit the number of packets that are forwarded in the network. The experiments conducted both in real conditions and in emulation have shown that the LoRaOpp protocol performs well in different setups, and that it allows to forward packets at several hops, even if the period of activity of devices are not synchronized, and therefore even if there is no end-to-end paths between devices at a given time.

In future work, we would like to improve the performances of LoRaOpp and to introduce LoRa nodes running on the 2.4 GHz band. LoRaOpp multi-hop routing would be even more relevant with such nodes, since the communication range is shorter than with sub-GHz frequencies, while an higher throughput and no duty cycle constraints would make data exchange between nodes more efficient.

  1: rt: the node running time 2: pkt: the packet that has been recevied 3: next_snd_time: the next time the node can send a packet considering 4: of the application that data packets will be forwarded for the reception of an acknowledge packet 26: pkt←rcv_pkt(min(next_sleep-current_time, MAX_ACK_RCV_DELAY)) until next_sleep_time ≥ current_time()

Fig. 1 .

 1 Fig. 1. Network topology adopted for outdoor experiments.

  (a) Number of hops for packet delivery. (b) Packet delivery ratios.(c) packet delivery times.

Fig. 2 .

 2 Fig. 2. Performance results of the LoRaOpp protocol vs the Epidemic Routing protocol for 6 nodes/1 gateway, 25 nodes/2 gateways, 50 nodes/5 gateways, 100 nodes/10 gateways.

Fig. 3 .

 3 Fig. 3. Performance results of LoRaOpp for 100 nodes and 1, 2, 5 and 10 gateways.

TABLE I EXPERIMENT

 I PARAMETERS.