Marius Bozga
email: bozga@imag.frmaler@imag.fr

Oded Maler

On the Representation of Probabilities over Structured Domains ?

In this paper we extend one of the main tools used in verication of discrete systems, namely Binary Decision Diagrams (BDD), to treat probabilistic transition systems. We show how probabilistic vectors and matrices can be represented canonically and succinctly using probabilistic trees and graphs, and how simulation of large-scale probabilistic systems can be performed. We consider this work as an important contribution of the veri cation community to numerous domains which need to manipulate very large matrices.

Introduction

Many problems in discrete veri cation can be reduced to the the following one:

given a non-deterministic nite-state automaton A = (Q; ) and a set P Q of states, nd the set P of all the states reachable from P. One common way to do this calculation is to let P 0 = P and P i+1 = (P i ) until P i is included in the union P 0 : : : P i?1 . Here P i is the set of states reachable from P after exactly i steps.

This method can be formulated using Boolean state-vectors and transition matrices. Each subset P of an n-element set of states can be written as an n-dimensional Boolean row vector p (a function from Q to f0; 1g) and any transition relation as an n n Boolean matrix A (a function from Q Q to f0; 1g). Thus, the calculation step P i+1 = (P i ) is equivalent to the multiplication of a vector by a matrix: p i+1 = p i A . For example, consider Figure 1 where a 5-state automaton is depicted along with its corresponding 5 5 matrix A . The reader can verify that calculating the states reachable in one step from P = f1; 2g is done via the multiplication 1; 1; 0; 0; 0] A = 0; 1; 1; 0; 1] where logical conjunction and disjunction replace multiplication and addition, respectively.

Probabilistic transition systems, such as discrete Markov chains, operate in a similar but di erent fashion. At any given stage of the system's evolution the state is given by a probability function p : Q ! 0; 1] such that P q2Q p(q) = 1.

The transition structure is probabilistic as well and is represented by a function ? This work was partially supported by the European Community Esprit-LTR Project 26270 VHS (Veri cation of Hybrid systems) and the French-Israeli collaboration project 970maefut5 (Hybrid Models of Industrial Plants). 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 Fig. 1. A non-deterministic automaton and its transition matrix.

: Q Q ! 0; 1] where (q; q 0 ) denotes the conditional probability of being in q 0 in the next-state given that the current state is q. The evolution from one probabilistic state vector to another is captured by the vector by matrix multiplication p i+1 = p i A , this time over the reals.

The state-explosion problem, also known as the curse of dimensionality, arises when the system under consideration is composed of many sub-systems. The size of the global state-space is exponential in the number of components and veri cation by explicit enumeration of states and transitions becomes impossible. Symbolic methods provide an alternative to explicit state enumeration. They are based on the following observation: the global state-space of a composed system can be encoded naturally using state-variables (a variable for the local state of each component). The evolution of each variable usually depends on a small subset of the other variables and the corresponding transition law can be written concisely as a formula in some adequate formalism (e.g. propositional logic when the variables are Boolean) and the global transition relation is a conjunction of such formulae. Similarly, sets of states can be written down as formulae. With the aid of appropriate data-structures, a symbolic version of the basic computation P i+1 = (P i ) can be performed, calculating a (hopefully concise) representation of P i+1 from a representation of P i and .

In veri cation of systems modeled as automata this technique is called symbolic model-checking McM93,BCM + 93] and it had a great success. In fact it can be seen as one of the breakthroughs in veri cation, facilitating the analysis of systems with hundreds of state variables, far beyond the capabilities of explicit enumeration on current and future computers. The most popular representation scheme used in symbolic veri cation is the binary decision diagram (BDD), which is a formalism for representing Boolean functions, admitting the following properties B86,MT98]:

1. It is canonic { given an ordering of the variables, a unique BDD corresponds to every Boolean function. 2. There are relatively-e cient algorithms for manipulating BDDs, in particular for the operations needed to compute P i+1 = (P i ).

3. It performs well in the analysis of many structured systems: the size of the BDD remains small relative to the size of the state-space. The goal of the paper is to apply this recipe to probabilistic systems, that is, to de ne a representation formalism for probabilistic vectors and transition functions such that the operation p i+1 = p i A could be performed for systems for which it is impossible to do so using currently existing methods. To this end we de ne probabilistic decision graphs (PDG)1 , a data-structure for representing probabilities over structured domains which enjoys the nice properties of BDDs.

The rest of the paper is organized as follows. In section 2 we present probabilistic decision trees and graphs and show they constitute a canonic representation for probabilities. In section 3 we rephrase the basic de nitions of Markov chains. Section 4 is devoted to the representation of probabilistic transition functions by conditional probabilistic graphs and sketch the PDG structure of some generic classes of probabilistic systems. The calculation of next-state probabilities on PDGs via the projection operation described in section 5 and some preliminary experimental results are reported in section 6. Finally we discuss the signi cance of this work and mention some of the previous relevant applications of BDD technology outside the Boolean realm.

2 Probabilistic Decision Graphs Let B = f0; 1g. We assume an underlying set Q = B n , and a probability distribution on Q, i.e. a function p : Q ! 0; 1] such that P q2Q p(q) = 1. Such a function can be extended naturally to subsets of Q by letting p(Q 0 ) = P q2Q 0 p(q) for every Q 0 Q. We will abuse strings from B n (the set of binary strings of length not greater than n) to denote certain subsets of B n . A string u = x 1 x 2 x n will stand for the singleton f(x 1 ; : : : ; x n )g while a string x 1 x 2 x i , i < n will stand for the set f(x 1 ; : : : ; x i ; x i+1 ; : : : ; x n ) : (x i+1 ; : : : ; x n ) 2 B n?i g. This can be de ned recursively by associating with u the union of the sets associated with u0 and u1. Note that the empty string " denotes the whole B n . To avoid additional symbols we use the same notation for a string and for the set it denotes. The set B n has a binary tree structure and every level B i corresponds to a partition of B n . The next de nition is the essence of this paper.

De nition 1 (Probabilistic Decision Trees). A probabilistic decision tree

(PDT) of depth n is a tuple P = (S; 0; 1; v) where S = B n , 0 and 1 are respectively the left-successor and right-successor partial functions on S, and v : S ! 0; 1] is a function satisfying v(") = 1 and for every non-leaf node s, v(s0) + v(s1) = 1.

Theorem 1 (Unique Representation). There is a one-to-one2 correspondence between probabilities on B n and PDTs.

Proof: First we assign probabilities to nodes by letting p(") = 1 and p(sx

) = p(s) v(sx) x 2 B (1)
It is not hard to see that all p values are in 0; 1] and that their sum at each level of the tree is 1. Conversely, given a probability on the leaves, it is straightforward to calculate the probability of the sets associated with the upper nodes by letting p(s) = p(s0) + p(s1) and then compute v via normalization, i.e. the inverse of (1): v(sx) = p(sx)=p(s). In the case when p(s) = 0 we can put any number in v(sx) = 0=0, and a convention such as 1=2 can be used.

PDTs are nothing but the presentation of probabilities using the so-called \chain-rule", the probabilistic analogue of Shannon factorization of Boolean functions which underlies BDDs: p(x 1 x 2 x n ) = p(x 1 ) p(x 1 x 2 jx 1 ) p(x 1 x 2 x n jx 1 x n?1 ) where p(rjs) is the conditional probability of r given s. We will replace this unfortunate (but very common) notation with p s (r) such that the above rule will be written as p(x 1 x 2 x n ) = p(x 1 ) p x1 (x 1 x 2 ) p x1 xn?1 (x 1 x n ):

Decision trees are exponential in the number of variables and, by themselves, do not solve the state explosion problems. However, when there is some structure in the objects they represent, di erent nodes may have identical sub-trees and the tree can be represented concisely by a directed acyclic graph (DAG) carrying the same information. The transformation of a tree into a DAG is a variation of the classical procedure for minimizing automata, and can be phrased as follows.

De nition 2 (Probabilistic Decision Graphs). Let P = (S; 0; 1; v) be a PDT and let be a congruence relation3 on S de ned as s s 0 if v(s) = v(s 0 ) and both s0 s 0 0 and s1 s 0 1. The associated probabilistic decision graph (PDG) is G = (S= ; 0; 1; v).

In other words, the nodes of G are the equivalence classes of . Graphically speaking, the process starts from the bottom of the tree by merging leaves sx and s 0 x 0 which have identical v's. Then the edge from s labeled by x and the edge from s 0 labeled by x 0 are redirected toward the merged node and the process continues recursively upward. Note that sx = ? for a leaf s, hence s s 0 only if both belong to the same level of the tree.

Example: Consider the following probability function over 2-(d) by merging some of their parents. 4 Like in BDDs, when there is a lot of independence between the variables, the size of the PDG is much smaller than the size of Q. In the rest of the paper we describe algorithms in terms of full trees, bearing in mind that the actual implementation reduces every tree into its corresponding minimal DAG. 3

Markov Transition Functions

Having de ned a canonical representation for probabilistic state vectors, we now move to the representation of transition matrices. In a non-probabilistic setting there is not much di erence between sets (subsets of B n ) and relations (subsets of B 2n ) and both can be represented by BDDs of the same type. For probabilistic systems, we must be more careful.

De nition 3 (Markov Transition Function

). A Markov transition function on Q is a function : Q ! (Q ! 0; 1]) such that for every q 2 Q, q : Q ! 0; 1]
is a probability function on Q.

In 20th century mathematics, such functions used to be written as jQj jQj matrices such as 1) 2(2) : : : 2(n) : : : : : : : : : : : : n(1) n(2) : : : n(n)

A = 1(1) 1(2) : : : 1(n) 2(
where each line represents a particular q . The action of on a probabilistic state-vector p can be decomposed into two stages. The rst can be viewed as applying a function ^ : (Q ! 0; 1]) ! (Q Q ! 0; 1]) where p = ^ (p) if for every q; q 0 2 Q, p(q; q 0 ) = p(q) q (q 0 ). In other words, given that the current state probability is p, ^ (p) denotes the probability of any transition to happen. Matrix-wise, when p is written as a vector p 1 ; : : : ; p n ], calculating ^ (p) amounts to multiplying every element of p by the elements of its corresponding row in to obtain A ^ (p) = p1 1(1) p1 1(2) : : : p1 1(n) p2 2(1) p2 2(2) : : : p2 2(n) : : : : : : : : : : : : pn n(1) pn n(2) : : : pn n(n) Note that unlike , ^ (p) is a probability function on Q Q.

The probability of being in the next step at a state q 0 is then the sum of the probabilities of the form p(q; q 0 ), i.e. those leading to q 0 . This can be captured by a function: w : (Q Q ! 0; 1]) ! (Q ! 0; 1]) de ned as w( ^ ) = P i ^ i . Matrixly speaking, this is equivalent to summing up every column of A ^ (p) to obtain a vector p 0 . Hence the composition w ^ : (Q ! 0; 1]) ! (Q ! 0; 1]) gives the evolution of the system as the action of a probabilistic transition matrix on a probabilistic state vector. 5 Next we de ne a data-structure for representing when Q = B n and a natural way to transform it, given a PDG-represented probability p, into a PDG of depth 2n for ^ (p). After that we de ne the basic operation on PDGs, the projection which is used in the calculation of w.

Conditional Probabilistic Decision Graphs

The basic idea is to extend PDTs such that nodes at certain levels of the tree are empty (with v unde ned) to denote undetermined variables. 6 To this end we will use somewhat more elaborate notations. Let X = f1 x ; 2 x ; : : : ; n x g and Y = f1 y ; 2 y ; : : : ; n y g be two copies of f1; : : :; ng. An order relation on X Y can be written as a bijection J : f1; 2; : : :; 2ng ! 5 For those familiar with BDDs, we mention that these operations resemble the nonprobabilistic ones: ^ (q; q 0 ) = p(q) ^ (q; q 0 ) and w(q 0 ) = 9q ^ (q; q 0 ) = W q ^ (q; q 0 ). 6 In fact we could have started the paper by de ning data-structures for conditional probability functions, with a partition of variables into two types. This way we could obtain probability functions as the special case where all the variables are determined, and Markov transition functions as a special case where the sizes of the two sets of variables are the same and certain restrictions are imposed on variable dependencies. However, we prefer clarity over generality.

X Y . Without loss of generality we assume that is compatible with the natural ordering of X and of Y , i.e. 1 x 2 x : : : n x . Given J, any binary string s 2 B 2n can be mapped into a pair of strings J x (s) and J y (s) from B n . For example, if J = 1 x 2 x 1 y 3 x 2 y 3 y then for a string s = x 1 x 2 y 1 x 3 y 2 y 3 , J x (s) = x 1 x 2 x 3 and J y (s) = y 1 y 2 . We also extend our string notation for sets: a string of the form x i1 x i1 x im with 0 < i 1 < i 2 < : : : < i m n will denote a subset of B n with the obvious meaning, i.e. the set of n-tuples such that the value of every i j -coordinate is x ij .

A Markov transition function over B n is a function : B n ! (B n ! 0; 1]) whose instances are written as x1 xn (y 1 y n ). For every x 1 x n , x1 xn is a probability function which can be written using the chain rule just as as any other probability:

x1 xn (y 1 y n ) = x1 xn (y 1 ) x1 xny1 (y 1 y 2 ) x1 xny1 yn?1 (y 1 y n ):

We restrict our attention to Markov chains in which every coordinate of the state-space behaves causally, i.e. it depends only on the previous values of the state variables. 7 This means that for every x 1 : : : x n and every y i , y j we have x1 xnyi (y j ) = x1 xn (y j ). Hence can be written as: (2)

We say that j y is independent of i x if for every x 1 ; : : : ; x i?1 ; x i+1 ; : : : x n , x1 xi?10xi+1 xn (y j ) = x1 xi?11xi+1 xn (y j ):

In this case we can use the notation x1 xi?1xi+1 xn (y j ). When this is not the case we say that i x in uences j y and denote it by i x + j y .

An order relation on X Y is compatible with a Markov transition function i for every i x 2 X; j y 2 Y , i x + j y implies i x j y . The default ordering 1 x : : : n x 1 y : : : n y is compatible with any and is the only one compatible with a for which every j y depends on all X.

De nition 4 (Conditional PDT and PDG). A conditional probabilistic decision tree (CPDT) of depth n is a tuple P = (S; 0; 1; J; v) where S = B 2n , 0 and 1 are as in a PDT, J is the ordering bijection and v : S ! 0; 1] is a partial function, de ned only on nodes s such that J(jsj) 2 Y , satisfying v(") = 1 and for every node s, v(s0) + v(s1) = 1 whenever it is de ned. A conditional probabilistic decision graph (CPDG) is G = (S= ; 0; 1; J; v) where is the congruence relation of De nition 2.

Theorem 2 (CPDT=Markov Transition Function).

There is a one-to-one correspondence between Markov transition functions and CPDTs.

Sketch of Proof: Similar to that of Theorem 1. We assume a xed ordering bijection J compatible with . For every Y -node sy i of the CPDT we associate v(sy i ) with the conditional probability J x (s) (y i ), for example v(x 1 x 2 y 1 x 3 y 2 ) = x1x2x3 (y 2 ). To reconstruct from a tree we go down the tree until we calculate for the lowest Y -nodes. To build a CPDT from we climb-up starting from the Y -leaves and construct the tree. We mention some classes of probabilistic transition systems such that the pattern of interaction between their components alone su ces for giving an upper-bound on the size of their CPDGs. Consider rst the degenerate case of n independent Bernoulli trials. It can be modeled as a direct product of n memory-less automata, for which the probability of the next state is independent of the current state. Thus, x1:::xn (y 1 : : : y n ) can be written as (y 1 ) (y n ) and represented by a CPDG without empty nodes, which is in fact a PDG, like in Figure 3-(a).

As a slightly less trivial example consider a direct product of n independent 2-state Markov chains. In this case each i y depends only on i x and the transition function can be represented by the CPDG of Figure 3-(b). More generally, consider a cascade A 1 ; : : : ; A n of probabilistic automata where the transition probabilities of each automaton A i depends on the states of its k predecessors (including itself) A i?k+1 ; : : : ; A i?1 ; A i . Such systems will have a CPDG of size O(n2 k ) similar to the one appearing in Figure 3-c for k = 2.

When there are no such constraints on variable dependencies, the default order needs to be used and no a-priori lower-bound better than n2 n can be stated (although some independencies might make the corresponding CPDG smaller). We repeat that even this bound is better than the 2 2n size implied by a straightforward encoding of the transition matrix. The general structure of such a CPDG is depicted in Figure 4.

Going from p and to ^ (p) is straightforward: take v(s) from the PDT for p and put it in any nodes s 0 of the CPDT of such that J x (s 0 ) = s. This way the whole tree becomes full and represents the probability ^ (p) over B 2n .

Projection

The basic operation on probabilities (and PDGs) is the probabilistic analogue of the elimination of a quanti ed variable in Boolean functions (and BDDs). This is what is needed to transform ^ (p) into (p).

De nition 5 (Projection). Let p : B n ! 0; 1] be a probability. The k-projection of p, is a function p #k : B n?1 ! 0; 1] de ned as

p #k (x 1 x k?1 x k+1 x n ) = p(x 1 x k?1 0x k+1 x n ) + p(x 1 x k?1 1x k+1 x n ) (3)
Using conditional probabilities, (3) can be rewritten as p(x 1 : : : x k?1 ) 2 4 p x1 x k?1 (0x k+1 x n ) + p x1 x k?1 (1x k+1 : : : x n ) 3 5 and further as p(x 1 x k?1 )

2 4 v(x 1 x k?1 0) p x1 x k?1 0 (x k+1 x n ) + v(x 1 x k?1 1) p x1 x k?1 1 (x k+1 x n ) 3 5
As one can see, performing a k-projection on the PDT representation of p consists of copying the rst k ? 1 levels of the tree and then plugging at each branch x 1 x k?1 a sub-tree which encodes the weighted sum of the functions p x1 x k?1 0 and p x1 x k?1 1 . This is the main computational burden in the manipulation of PDGs. The transformation of a PDT P = (S; 0; 1; v) for p with S = B n into a PDT P #k = (S #k ; 0; 1; v #k ) for p #k with S #k = B n?1 is performed as follows. For any node s 2 B k?1 we have p #k (s) = p(s). For the other nodes we have p #k (x 1 x k?1 s) = p(x 1 x k?1 0s) + p(x 1 x k?1 1s)

These values are calculated from the top down and every calculation of p #k (sx) is followed by calculating v #k (sx) as v #k (sx) = p #k (sx)=p #k (s), which in the rst k ? 1 levels reduces simply to v #k (s) = v(s). Aplying this procedure n times 8

we transform a probability on B 2n to a probability on B n and complete the computation of p 0 = p A . While working with PDGs, one can avoid part of the computation whenever there is an equivalence of the form p s0 = p s1 . In that case the weighted sum r p s0 + (1 ? r)p s1 is equal to both.

Implementation and Experimental Results

The treatment of the mathematical real numbers by computer involves an additional dimension of problematics absent from traditional applications of verication methodology. The continuum is approximated by a very large (but nite) subset of the rationals, the oating point numbers. Practitioners seem to be satis ed with this approximation. It turns out that for exploiting the advantages of PDGs we had to go further and round node values to multiples of 2 ?m (for m ranging between 3 to 10), otherwise the size of non-trivial PDGs becomes exponential after few iterations because of the low probability of two nodes having exactly the same oating-point value. With this discretization, systems with limited interaction among variables usually converge to vectors with a small PDG description. As for the semantic price of the approximation, if we re ect a bit on the empirical source of probability estimations in models, we realize that these numbers are not sacred and an initial \imprecision" of 2 ?m does not make any di erence.

We have implemented these data-structures and algorithms and tested their performance on some generic examples. The implementation is preliminary and does not yet employ all the optimizations one can nd in BDD packages. Let us rst mention the trivial cases. For n randomly-generated mutually-independent Markov chains we can treat almost any n. This is, of course, not so impressive if one realizes that each chain could be simulated separately. Yet someone unaware of BDDs will be rather surprised to see how fast you can multiply a 2 15 2 15 transition matrix void of any apparent structure or sparseness (see table 1). A slightly less trivial example is a chain of noisy communication channels where each component copies the value of its predecessor with probability 1 ? . Such a chain converges to a uniform probability vector where p(q) = 1=2 n for every state. Here again we could iterate for very large n with a linear growth in the size of the PDGs.

Next, we have tested randomly-generated cascades of communication depth 2, which using the previously mentioned discretization, usually converge to vectors with small PDGs, although exponential ones are, of course, still possible. We demonstrate the time and space behavior of the algorithm on a family consisting of a cascade of noisy AND gates such that each component becomes the conjunction of its previous value and that of its predecessors (Figure 5) with 8 Like in BDDS, this procedure can be extended naturally to a procedure that eliminates several variables in a single pass.

0:000564 0:000093 0:000412 0:000068 0:000094 0:000015 0:000068 0:000011 0:000727 0:000120 : : : 0:000653 0:000003 0:000477 0:000002 0:000108 0:000001 0:000079 0:000000 0:000842 0:000004 : : : 0:000823 0:000135 0:000153 0:000025 0:000137 0:000022 0:000025 0:000004 0:001061 0:000175 : : : 0:000953 0:000005 0:000177 0:000001 0:000158 0:000001 0:000029 0:000000 0:001229 0:000006 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

Table 1. An initial fragment of a 2 15 2 15 matrix which can be iterated until convergence within less than a second.

probability 0:9. The performance results are depicted in Figure 6 and although space behaves nicely, computation time still grows exponentially, reaching almost 4 hours for n = 54. The reason lies in the fundamental di erence between BDDs and PDGs: in the former, when an algorithms encounters a node, it does not need to remember via which branch the node is reached, and thus the hashing mechanism prevents duplicate calls. On the other hand, in PDGs, each time the projection procedure is called with a node, it has, as an additional parameter, the probability associated with its parent. Hence procedure calls with identical arguments are rather rare and the current implementation needs to do exponential work on linear-sized PDGs. We are currently investigating improvements of the implementation. We have introduced and implemented a new method for manipulating large probabilistic transition systems. We hope that this technique will improve the performance of probabilistic simulation tools. In addition, the investigation of the structure of PDGs might contribute to a better understanding of the structure of probabilistic functions. The application domains which might bene t from such a technique are numerous and include performance and reliability analysis, probabilistic veri cation, planning under uncertainty P94,BDH99], calculation of equilibria in economics, statistical mechanics and more. This work is built on what we consider to be the main insight of the BDD experience: in many situations the indices of rows and columns in matrices are the outcome of \ attenning" of much more structured domains. This attening, which is unavoidable if one wants to draw a matrix on a two-dimensional sheet of paper, hides the structure of the problem, or at least makes it very hard to retrieve.9 BDDs and PDGs suggest a way of maintaining this structural information and exploiting it in e cient computations.

Among previous extensions of BDD technology to represent functions from B n to N (motivated chie y by arithmetical circuits), R and other domains we mention the structure called Multi-terminal BDDs (MTBDD) in CFM + 93] and Algebraic Decision Diagrams (ADD) in BFG + 93]. This is a straightforward extension of BDDs with leaves having values in non-Boolean domains. Algorithms for performing matrix multiplications and other operations on these representations have been proposed and applied, for example, to probabilistic veri cation BCG + 97]. The main drawback of MTBDDs/ADDs is that they yield a succint representation only if the corresponding vectors and matrices have a lot of identical entries, e.g. sparse matrices having many zeros. In contrast many generic examples of functions with no interaction between the variables will lead to exponential MTBDDs: for example it is not hard to create probabilities on B n with all variables mutually-independent, and yet no two elements will have the same probability. In fact, the ability to represent functions concisely as decision graphs without putting any information on the non-leaf nodes is a special property of Boolean algebra.

The above observation has led some researchers in the hardware veri cation community VPL96,TP97] to consider extending BDD with values on their edges (which is practically the same as putting values on the nodes, as we do here). This structure is called Edge-valued BDD (EVBDD) and it has been used to encode the so-called Pseudo-Boolean functions which are essentially functions from f0; 1g n to N. EVBDDs contain both additive and multiplicative constants and in some cases overcome the limitations of MTBDDs. However, since the class of functions treated by EVBDDs is much less constrained than the class of probabilistic functions, normalization and matrix multiplication are much more complicated than the ones reported in this paper.

Finally, let us mention another formalism, related to PDGs, the Bayesian Networks which are used extensively in AI P88,J96]. Like PDGs, Bayesian networks consist of a graphical representation of variables and their probabilistic dependencies. The comparison between the two formalisms is outside the scope of this paper, but it seems that PDGs can be viewed as a constrained and wellbehaving sub-class of networks, with a special emphasis on the dynamic aspects (next-state probabilities) which makes them, perhaps, more suitable for treating large-scale Markov decision processes.

  Figure 2-(a) shows the probabilities of all subsets in B 3 . The PDT in Figure 2-(b) is obtained via the normalization v(sx) = p(sx)=p(s). The reduction modulo into a PDG starts in Figure 2-(c) by merging identical leaves and terminates in Figure 2-(d) by merging some of their parents. 4 Like in BDDs, when there is

Fig. 2 .

 2 Fig. 2. Transforming a probability function (a) into a PDT (b) and successively via (c) into a PDG (d).

  x1 xn (y 1 y n ) = x1 xn (y 1 ) x1 xn (y 2 ) x1 xn (y n ):

Fig. 3 .

 3 Fig. 3. Schematic CPDGs for Markov transition function which consist of: (a) Independent Bernoulli trials (b) Independent Markov chains (c) A cascade with k = 2. The dark nodes indicate Y -nodes.

Fig. 4 .

 4 Fig. 4. A schematic CPDG for an arbitrary (but causal) Markov transition function.

Fig. 5 .

 5 Fig. 5. A chain of noisy AND gates.

Fig. 6 .

 6 Fig. 6. The PDG size and time until convergence as a function of the number of variables, for discretizations of 1=1024 and 1=512.

We say \graphs" instead of \diagrams" to avoid yet another xDD acronym.

In our de nition there is an implicit ordering on the \variables".

Congruence with respect to the 0 and 1 operations.

Unlike BDDs we do not go further and eliminate nodes whose left and right successors are identical: we restrict ourselves to balanced DAGs where all paths from the root to the leaves are of the same length, otherwise we cannot satisfy the requirement that the sum of the leaves at every level is 1.

Note that one can write Markov transition functions over Q which do not admit such a causal decomposition, and this observation might be a source of interesting investigations in the theory of stochastic processes. In fact, the above implies that every m-state Markov chain which admits a causal decomposition can be represented in space O(m log m) instead of O(m 2 ).

Just compare the non-intuitive de nition of the Kronecker product (also known as Tensor product) of two matrices with the straightforward Cartesian product of automata.

Acknowledgements: We are grateful to Moshe Tennenholz for raising the possibility of applying some veri cation techniques to AI problems of planning under uncertainty. His visit in Grenoble, in fact, triggered this work. We thank Amir Pnueli for many fruitful discussions at various stages of this work, and in particular for the observations concerning causal Markov chains and weighted sum of identical sub-trees. Eugene Asarin reminded us of certain facts concerning the convergence of probabilistic matrix multiplications.


Francisco Ramos-Martín
email: francisco.ramos@u-picardie.fr.

Claudia Herrera-León

Viviane Antonietti

Pascal Sonnet

Catherine Sarazin

Nicola D'amelio
email: nicola.damelio@u-picardie.fr.

The potential of antifungal peptide Sesquin as natural food preservative

Keywords: food biopreservation, antimicrobial peptide, antifungal, NMR, molecular dynamics, biomembranes

Highlights

• Sesquin shows antimicrobial activity against fungi and bacteria involved in food spoilage.

• Based on NMR and MD data we have found that Sesquin interacts with biomimetic bacterial and fungal membranes.

• Sesquin specifically interacts with phosphatidylethanolamine and ergosterol altering membrane organization.

• A mechanism of action at atomic level is proposed explaining additional biological activities.

• MD data show that its activity is preserved at high pressure or with electric field pulses, commonly used as food preservation techniques .

Introduction

Food preservation is hampered by the action of a variety of bacteria and fungi. Different preservation techniques have been developed, including fermentation, addition of salts or sugars, picking, drying, cooling, addition of preservatives, heating, modified packaging atmosphere, high pressure or even high electric fields [START_REF] Dijksterhuis | 2 Fungal Spoilage of Crops and Food[END_REF][START_REF] Pitt | Fresh and Perishable Foods[END_REF][START_REF] Pitt | Spoilage of Stored, Processed and Preserved Foods, in: Fungi and Food Spoilage[END_REF][START_REF] Heinz | Food preservation by high pressure[END_REF][START_REF] Li | Effect of Low-Temperature-High-Pressure Treatment on the Reduction of in Milk[END_REF][START_REF] Yang | Inactivation of foodborne pathogens in raw milk using high hydrostatic pressure[END_REF][START_REF] Domitrovic | High hydrostatic pressure activates gene expression through Msn2/4 stress transcription factors which are involved in the acquired tolerance by mild pressure precondition in Saccharomyces cerevisiae[END_REF][START_REF] Grahl | Killing of microorganisms by pulsed electric fields[END_REF][START_REF] Reina | Inactivation of Listeria monocytogenes in milk by pulsed electric field[END_REF][START_REF] Yeom | Processing of yogurt-based products with pulsed electric fields: Microbial, sensory and physical evaluations[END_REF][START_REF] Bhat | Current and future prospects for the use of pulsed electric field in the meat industry[END_REF][START_REF] Chen | Adaptation response of Pseudomonas fragi on refrigerated solid matrix to a moderate electric field[END_REF][START_REF] Jha | Advances of electro-freezing in food processing[END_REF][START_REF] Kang | Supercooling preservation technology in food and biological samples: a review focused on electric and magnetic field applications[END_REF][START_REF] Wang | Enhancing Food Processing by Pulsed and High Voltage Electric Fields: Principles and Applications[END_REF]. Although these techniques have significantly improved the preservation of food, they have also stimulated the rise of resistant microorganisms able to survive under these extreme conditions. Among them, Botrytis cinerea and Fusarium oxysporum are among the most critical microorganisms because of their ability to affect common products such as wheat and grapes. Botrytis cinerea is a necrotrophic fungus, which causes widespread infection of grapes, tomatoes, strawberries, and other fruits [START_REF] Pitt | Fresh and Perishable Foods[END_REF]. It is also the most destructive pathogen on green and leafy vegetables. Its virulence, which involves pathogens and hosts inflammatory response [START_REF] Choquer | Botrytis cinerea virulence factors: new insights into a necrotrophic and polyphageous pathogen[END_REF], is amplified by its extreme tolerance to low temperatures [START_REF] Hoogerwerf | High-oxygen and high-carbon dioxide containing atmospheres inhibit growth of food associated moulds[END_REF]. Since Botrytis infects every plant part at any growth stage, the advantage of the use of fungicides is very limited [START_REF] Griffiths | Lipid composition of Botrytis cinerea and inhibition of its radiolabelling by the fungicide iprodione[END_REF]. Fusarium oxysporum is an opportunistic pathogen producing Fusarium wilt disease [START_REF] Srinivas | Fusarium oxysporum f. sp. lycopersici causal agent of vascular wilt disease of tomato: Biology to diversity-A review[END_REF] and able to infect citrus fruit [START_REF] Snowdon | Post-Harvest Diseases and Disorders of Fruits and Vegetables: Volume 1: General Introduction and Fruits[END_REF] but also vegetables such as potatoes, onions and garlic, among many others [START_REF] Pitt | Fresh and Perishable Foods[END_REF]. Most importantly, Fusarium sp. is the principal pathogenic fungal genus causing spoilage of maize, and producing mycotoxins harmful to humans and domestic animals [START_REF] Desjardins | Fusarium Mycotoxins: Chemistry, Genetics and Biology[END_REF][START_REF] Pitt | Spoilage of Stored, Processed and Preserved Foods, in: Fungi and Food Spoilage[END_REF].

In the attempt to develop new antifungals active against Botrytis cinerea and Fusarium oxysporum, we focused on Sesquin, an antifungal peptide homologous to Defensin that was isolated from Vigna sesquipedalis [START_REF] Wong | Sesquin, a potent defensin-like antimicrobial peptide from ground beans with inhibitory activities toward tumor cells and HIV-1 reverse transcriptase[END_REF]. The use of antimicrobial peptides (AMPs) as antimicrobials is a promising strategy not only to treat health diseases but also to prevent the deleterious effects of pesticides in the environment [START_REF] Tago | Pesticides and health: a review of evidence on health effects, valuation of risks, and benefit-cost analysis[END_REF]. In fact, they are already in use in the food industry because of their ability to control the growth of undesirable microorganisms while maintaining the qualities and nutritional properties of products [START_REF] Wang | Antimicrobial peptides: Promising alternatives in the post feeding antibiotic era[END_REF]. Not only Sesquin attacks Botrytis cinerea, Fusarium oxysporum and Mycosphaerella arachidicola but also several bacteria (Escherichia coli, Proteus vulgaris, Mycobacterium phlei and Bacillus megaterium), cancer cells (MCF-7 breast cancer model and leukemia M1 cells) and viruses (human immunodeficiency virus-type 1 reverse transcriptase). Despite the exceptional variety of targeted organisms, the mode of action of Sesquin has not been deeply investigated [START_REF] Nikoletta | Antifungal proteins: More than antimicrobials?[END_REF].

A molecular picture of its interaction with fungal and bacterial membranes could explain why Sesquin displays wider spectrum activity than sequence-related peptides [START_REF] Wong | Gymnin, a potent defensin-like antifungal peptide from the Yunnan bean (Gymnocladus chinensis Baill)[END_REF][START_REF] Ngai | Coccinin, an antifungal peptide with antiproliferative and HIV-1 reverse transcriptase inhibitory activities from large scarlet runner beans[END_REF]. Studies on membranes mimicking eukaryotic cells are also useful to predict possible undesirable cytotoxic effects for applications of Sesquin as a food preservative. As a food preservative, Sesquin does not appear to be cytotoxic. Unlike other PE-specific AMPs like cyclotides, maximin H and lantibiotics [START_REF] Grage | Orientation and Location of the Cyclotide Kalata B1 in Lipid Bilayers Revealed by Solid-State NMR[END_REF][START_REF] Vestergaard | Structure and Dynamics of Cinnamycin-Lipid Complexes: Mechanisms of Selectivity for Phosphatidylethanolamine Lipids[END_REF][START_REF] Sarah R Dennison | The role of C-terminal amidation in the membrane interactions of the anionic antimicrobial peptide, maximin H5[END_REF], Sesquin does not interact with phosphatidylcholine, making its mechanism of action unique and reducing its toxicity as compared with other PEtargeting peptides. In fact, contrarily to those peptides [START_REF] Phoenix | The increasing role of phosphatidylethanolamine as a lipid receptor in the action of host defence peptides[END_REF], Sesquin is not reported to be hemolytic probably due to the fact that PE is minimally exposed in healthy RBC (less than 1% [START_REF] Larson | Phosphatidylethanolamine is progressively exposed on RBCs during storage[END_REF]).

In this paper, we investigate a possible use of Sesquin as a food preservative by observing its effects on biomembranes of different compositions and in different conditions.

By liquid and solid-state NMR and molecular dynamic simulations we describe the interaction of Sesquin with membranes mimicking fungi, bacteria and eukaryotic cells. A specific interaction with phosphatidylethanolamine might explain why, while unaffecting mammalian mimetic membranes, Sesquin displays such a wide spectrum activity. In particular, we show how a direct interaction with ergosterol could account for its strong antifungal activity. Finally, we investigate the compatibility of Sesquin with modern food preservation techniques such as high pressure, or the presence of electric field pulses.

Materials and Methods

Sequence alignment by ADAPTABLE web server

The families of peptides active against both Botrytis cinerea and Fusarium sp. were created by the family generator page of ADAPTABLE web server [START_REF] Ramos-Martín | ADAPTABLE: a comprehensive web platform of antimicrobial peptides tailored to the user's research[END_REF] using the following parameters: "Target Organism = fusarium, cinerea"; "Substitution matrix = Blosum45"; "Minimum % of similarity = 60; "Experimentally validated = yes".

The family of peptides sequence-related to Sesquin (KTCENLADTY) was created by the family generator page of ADAPTABLE web server using "Create the family of a specific peptide" option with the following parameters: "Substitution matrix = Blosum45"; "Minimum % of similarity =70".

As ADAPTABLE continuously updates with new entries, sequence-related families might change slightly with the time [START_REF] Ramos-Martín | ADAPTABLE: a comprehensive web platform of antimicrobial peptides tailored to the user's research[END_REF].

Synthesis of Sesquin

Fmoc(9-fluorophenylmethoxy)-amino acids and Fmoc-Tyr(tBu)-AC TentaGel® resin (0.22 mmol/g, particle size: 90 µm) were purchased from Iris Biotech (Germany). The other chemical compounds were purchased from VWR Chemicals, Iris Biotech or Acros and used without further purification. The peptides were synthesized on a CEM Liberty 1 Microwave Peptide Synthesizer, using standard automated continuous-flow microwave solid-phase peptide synthesis methods. Five-fold molar excess of the above amino acids was used in a typical coupling reaction. Fmoc-deprotection was accomplished by treatment with 20% (v/v) piperidine in N-methyl-2-pyrrolidone (NMP) at 75 °C. The coupling reaction was achieved by treatment with 2-(1H-benzotriazol-1-yl)-1,1,3,3-tetramethyluronium hexafluorophosphate (HBTU) and N,N-diisopropylethylamine (DIEA) in NMP using a standard microwave protocol (75 °C). The peptide was cleaved and side-chain deprotected by treatment of the peptide resin with a mixture of 1.85 ml of trifluoroacetic acid (TFA), 50 µL of triisopropylsilane, 50 µL H2O and 50 mg of DL-dithiothreitol, in respective percent proportions, 92.5/2.5/2.5/2.5, during 4 hours at room temperature. The solid support was removed by filtration, the filtrate concentrated under reduced pressure, and the peptide precipitated from diethyl ether. The precipitate was washed several times with diethyl ether and dried under reduced pressure.

The peptides were purified on an RP-HPLC C18 column (Phenomenex® C18, Jupiter 4µ Proteo, 90 Å, 250x21.20 mm) using a mixture of aqueous 0.1% (v/v) TFA (A) and 0.1% (v/v) TFA in acetonitrile (B) as the mobile phase (flow rate of 3 ml/min) and employing UV detection at 210 and 254 nm.

The peptide KTCENLADTY was obtained according to the precedent synthesis and purification procedures starting from the Fmoc-Tyr(tBu)-AC TentaGel® resin (454.5 mg, 0.100 mmol). Peptide was obtained, as a white powder, with a total yield of 45.3%, after purification by reverse-phase HPLC (97% analytical purity, Fig. S1).

Molecular Dynamics Simulations

Systems for simulations were prepared using CHARMM-GUI [START_REF] Jo | CHARMM-GUI Membrane Builder for mixed bilayers and its application to yeast membranes[END_REF][START_REF] Lee | CHARMM-GUI Input Generator for NAMD, GROMACS, AMBER, OpenMM, and CHARMM/OpenMM Simulations Using the CHARMM36 Additive Force Field[END_REF][START_REF] Wu | CHARMM-GUI Membrane Builder toward realistic biological membrane simulations[END_REF]. A total of 128 lipid molecules were placed in each lipid bilayer (i.e., 64 lipids in each leaflet) and peptide molecules were placed over the upper leaflet at a non-interacting distance (>10 Å). Lysine residues were protonated. Initial peptide structure was obtained from the SATPdb database [START_REF] Singh | SATPdb: a database of structurally annotated therapeutic peptides[END_REF] (id: 24206). In the case of calculations with 8 peptides, they were placed next to each other but not in contact. A water layer of 50-Å thickness was added above and below the lipid bilayer which resulted in about 15000 water molecules (30000 in the case of CL) with small variations depending on the nature of the membrane. Systems were neutralized with Na⁺ or Cl⁻ counterions. MD simulations were performed using GROMACS software [START_REF] Abraham | GROMACS: High performance molecular simulations through multi-level parallelism from laptops to supercomputers[END_REF] and CHARMM36m force field [START_REF] Klauda | Update of the CHARMM all-atom additive force field for lipids: validation on six lipid types[END_REF][START_REF] Huang | CHARMM36m: an improved force field for folded and intrinsically disordered proteins[END_REF] under semi-isotropic (for bilayers) and isotropic (for micelles) NPT conditions [START_REF] Jo | Automated builder and database of protein/membrane complexes for molecular dynamics simulations[END_REF][START_REF] Cheng | CHARMM-GUI micelle builder for pure/mixed micelle and protein/micelle complex systems[END_REF]. The TIP3P model [START_REF] Berendsen | Interaction Models for Water in Relation to Protein Hydration[END_REF] was used to describe water molecules. Each system was energy-minimized with a steepest-descent algorithm for 5000 steps. Systems were equilibrated with the Berendsen barostat [START_REF] Berendsen | Molecular dynamics with coupling to an external bath[END_REF] and Parrinello-Rahman barostat [START_REF] Parrinello | Polymorphic transitions in single crystals: A new molecular dynamics method[END_REF][START_REF] Nosé | Constant pressure molecular dynamics for molecular systems[END_REF] was used to maintain pressure (1 bar) semi-isotropically with a time constant of 5 ps and a compressibility of 4.5 × 10 -5 bar -1 . Nose-Hoover thermostat [START_REF] Nosé | A unified formulation of the constant temperature molecular dynamics methods[END_REF][START_REF] Hoover | Canonical dynamics: Equilibrium phase-space distributions[END_REF] was chosen to maintain the systems at 310 K or 278 K with a time constant of 1 ps. High pressure simulations were performed at 1000 bar pressure level as reported in other works [START_REF] Ding | Effects of High Pressure on Phospholipid Bilayers[END_REF]. Simulations under electric fields were run setting a static field with E0= 0.1 V/nm in the Z-direction [START_REF] Lindahl | GROMACS 2019 Manual[END_REF]. All bonds were constrained using the LINear Constraint Solver (LINCS) algorithm, which allowed an integration step of 2 fs. PBC (Periodic Boundary Conditions) was employed for all simulations, and the particle mesh Ewald (PME) method [START_REF] Essmann | A smooth particle mesh Ewald method[END_REF] was used for long-range electrostatic interactions. After the standard CHARMM-GUI minimization and equilibration steps [START_REF] Jo | Automated builder and database of protein/membrane complexes for molecular dynamics simulations[END_REF], the production run was performed for 500 ns and the whole process (minimization, equilibration and production run) was repeated once in the absence of peptide and twice in its presence.

Convergence was assessed using RMSD and polar contacts analysis.

All MD trajectories were analyzed using GROMACS tools [START_REF] Smith | Simulation Best Practices for Lipid Membranes [Article v1.0[END_REF][START_REF] Lemkul | From Proteins to Perturbed Hamiltonians: A Suite of Tutorials for the GROMACS-2018 Molecular Simulation Package[END_REF] and Fatslim [START_REF] Buchoux | FATSLiM: a fast and robust software to analyze MD simulations of membranes[END_REF].

MOLMOL [START_REF] Koradi | MOLMOL: a program for display and analysis of macromolecular structures[END_REF] and VMD [START_REF] Humphrey | VMD: Visual molecular dynamics[END_REF] were used for visualization. Graphs and images were produced with GNUplot [START_REF] Janert | Gnuplot in Action: Understanding Data with Graphs[END_REF] and PyMol [START_REF] Delano | Pymol: An open-source molecular graphics tool[END_REF].

Sample preparation, NMR experiments and analysis

Backbone and sequential resonance assignments were achieved by 1 H, 13 C-HSQC, 1 H, 1 H-TOCSY (mixing of 60 ms), and 1 H, 1 H-NOESY (mixing of 200 ms) recorded on a 500 MHz Bruker spectrometer equipped with a 5 mm BBI probe. Deuterated sodium 3-(trimethylsilyl)propionate-d4 (TSP-d4) at a concentration of 100 µM was used as internal reference for chemical shift. Reference random coil values in our experimental conditions (T = 278 K, pH 6.6 and ionic strength 0.01 M) were calculated by POTENCI web server (https://st-protein02.chem.au.dk/potenci/) [START_REF] Nielsen | POTENCI: prediction of temperature, neighbor and pH-corrected chemical shifts for intrinsically disordered proteins[END_REF].

A 0.8 mM sample of Sesquin (90% 10 mM phosphate buffer / 10% D2O, pH 6.6) was titrated with a 1 M stock solution of DPC:d38 to a final DPC concentration of 60 mM. Titration was followed by 1D 1 H-NMR at 278 K. For the assignment of the interacting form of the peptide 2D 1 H, 1 H-NOESY and 1 H, 13 C-HSQC were recorded at total DPC concentrations of 60 mM.

Bicelles were prepared as follows. A mixture of 33.3 % DMPC and 66.7 % DHPC in chloroform was used to obtain isotropic bicelles at a molar (q) ratio of 0.5. The solvent was evaporated under a nitrogen flow and the samples were then lyophilized and resuspended in a 10 mM phosphate buffer (pH 6.6) to reach a final concentration of 1 M (stock solution). DMPG, DMPS and DMPE containing bicelles were prepared as described above, except part of DMPC was replaced by DMPG (25%), DMPS (25%), DMPE (10%) or ergosterol (5%) reproducing previous experiments [START_REF] Marcotte | Bicelles as model membranes for solid-and solution-state NMR studies of membrane peptides and proteins, Concepts in Magnetic Resonance Part A[END_REF][START_REF] Ghimire | A comparative study of the effect of cholesterol on bicelle model membranes using X-band and Q-band EPR spectroscopy[END_REF][START_REF] Sasaki | Cholesterol Doping Induced Enhanced Stability of Bicelles[END_REF][START_REF] Diller | Bicelles: A natural "molecular goniometer" for structural, dynamical and topological studies of molecules in membranes[END_REF]. A 0.8 mM sample of Sesquin (90% 10 mM phosphate buffer / 10% D2O, pH 6.6) was titrated with bicelles up to a final lipid concentration of 70 mM and monitored at 278 K by a 1D 1 H-NMR spectrum recorded after each addition.

Multilamellar vesicles (MLVs) containing deuterated palmitoyl chains were prepared according to the conventional protocol [START_REF] Monnier | Exploring the Dual Interaction of Natural Rhamnolipids with Plant and Fungal Biomimetic Plasma Membranes through Biophysical Studies[END_REF][START_REF] Furlan | Red wine tannins fluidify and precipitate lipid liposomes and bicelles. A role for lipids in wine tasting?[END_REF][START_REF] Furlan | Flavanol/lipid interaction: a novel molecular perspective in the description of wine astringency & bitterness and antioxidant action[END_REF][START_REF] Grélard | Hepatitis B subvirus particles display both a fluid bilayer membrane and a strong resistance to freeze drying: a study by solid-state NMR, light scattering, and cryo-electron microscopy/tomography[END_REF][START_REF] Hall | Identification of Specific Lysines and Arginines That Mediate Angiomotin Membrane Association[END_REF] using the following proportions: 50%:50% POPC/POPC:d31, 50%:50% POPG/POPG:d31, 50%:50% POPS/POPS:d31; 70%:30% POPE:d31/POPG , 50%:50% CL/POPC:d31 , 70%:30% POPE:d31/POPC, 70%:25%:5% POPE:d31/POPC/Ergosterol, 67%:27%:6% POPE:d31/POPG/CL, 50%:50% POPC:d31/SoyPI. Lipids were solubilized in chloroform and solutions were mixed in order to obtain the right proportions in a total lipid amount of 60 mM. The resulting solution was evaporated under nitrogen gas flow. The sample was hydrated with ultrapure water, well-vortexed to promote total hydration and lyophilized overnight to remove the traces of solvents. The resulting powder containing lipids was hydrated by 80 µl of ultra pure water (for non charged lipids) or 10 mM phosphate buffer pH 6.6 100 mM NaCl (for charged lipids), vortexed and homogenized using four free-thaw cycles involving one step of freezing (-80°C, 15 min) followed by thawing (40°C, 15 min) and shaking. Finally, the MLV samples were placed in a 7-mm ssNMR rotor to perform the experiments. 2.4 mM of peptide were added for interaction studies. ssNMR experiments were recorded at 310 K, 298 K and 283 K on a Bruker Avance Biospin 300 WB (7.05T) equipped with a CP-MAS 7-mm probe. Static 2 H NMR was carried out applying a phase cycled quadrupolar echo pulse sequence (90°x-τ-90°y-τ-acq) [START_REF] Davis | Quadrupolar echo deuteron magnetic resonance spectroscopy in ordered hydrocarbon chains[END_REF]. The parameters used are: spectral width of 150 kHz, π/2 pulse of 5.25 μs, an interpulse delay of 40 μs, a recycled delay of 1.5 s, and a number of acquisitions ranging from 8 k to 14 k depending on samples. For all spectra, an exponential line broadening of 100 Hz was applied before Fourier-transform from the top of the echo signal.

RESULTS AND DISCUSSION

Property alignment highlights motifs potentially involved in Sesquin wide-spectrum activity

There exist more than 6000 antifungal peptides, out of which about 200 display significant activity towards both Botrytis cinerea and Fusarium sp. (e.g. IC50<10uM). Sequence alignment by ADAPTABLE web server [START_REF] Ramos-Martín | ADAPTABLE: a comprehensive web platform of antimicrobial peptides tailored to the user's research[END_REF] grouped peptides active against these fungi in sequence-related families (SR families). Out of these, we selected the family generated by Sesquin shown in Figure 1A, for its simplicity (only 10 amino acid long) and its interesting properties. Sesquin is in fact not only antifungal but also antibacterial, anticancer and antiviral. The alignment reveals that a few motifs are particularly conserved: the initial K, the CEN triad and the D residue (Figure 1B). Using Sesquin as a bait to find similar sequences, independently of the activity resulted in the creation of the SR family with members which might also be active against Botrytis cinerea and Fusarium sp., even though they might not have been tested yet (Figure 1C). This latter alignment reveals that Sesquin is similar to a significant number of antimicrobial or anticancer peptides, in part belonging to the Defensin family, where it is often found at the N-terminus of much longer sequences. Their activities are mostly antifungal, antiviral and antibacterial but also anticancer and antiparasitic. It should be noted that Sesquin is an atypical antimicrobial peptide as it has a negative overall charge and is too short to form stable alpha-helices, although a hypothetical helix would have amphipathic character (Figure 1D).

Sesquin is substantially unstructured in solution NMR

In order to get insight into the mechanism of action of Sesquin, we analyzed the structure of the peptide in solution by NMR spectroscopy. Antifungal peptides commonly adopt a random coil or alpha helical conformation, while they rarely assume extended strand and beta-turn conformations [START_REF] Soltani | In silico analysis of antifungal peptides[END_REF]. 2D-NOESY, 2D-TOCSY and 1 H- 13 C HSQC experiments were acquired for complete 1 H, 13 C resonance assignment of backbone amide protons and nonexchangeable CH moieties (Table S1). The analysis of the NOESY spectrum did not reveal the presence of NOE effect between protons distant in the primary structure, suggesting that the peptide is completely unstructured in solution. Accordingly, the 1 H amide region of the NMR spectrum improves in quality at low temperature, as expected by a slowing down of exchange phenomena with the solvent. A further confirmation comes from the Chemical Shift Index (CSI) [START_REF] Wishart | The chemical shift index: a fast and simple method for the assignment of protein secondary structure through NMR spectroscopy[END_REF][START_REF] Wishart | The 13 C Chemical-Shift Index: A simple method for the identification of protein secondary structure using 13 C chemical-shift data[END_REF][START_REF] Wishart | Interpreting protein chemical shift data[END_REF] (Figure 1E) showing very limited deviations from random coil values of Hα, Cα and Cβ atoms, which are lower than the threshold (0.1 ppm for 1 H and 0.7 ppm for 13 C) [START_REF] Wang | Probability-based protein secondary structure identification using combined NMR chemical-shift data[END_REF].

Figure 1. (A) Sequence-related family generated by ADAPTABLE using Sesquin as a bait among peptides with IC50<10μM against both Botrytis cinerea and Fusarium sp. (B) Relative importance of each aminoacid in terms of conservation. (C) Sequence-related family generated by Sesquin used as a bait among the full ADAPTABLE database, independently of their activity. (D) Helical wheel plot (generated by NetWheels [77]). (E) Chemical shift deviations from random coil values of HN, Hα, Cα and Cβ atoms. (F) Amide region of 1 H NMR spectrum for the reduced (blue) and oxidized (red) forms of Sesquin.

We also investigated the influence of the cysteine residue on the structure of the peptide and the possible formation of disulphide-linked dimers. The NMR spectrum of Sesquin does change after a few days in solution and changes are reverted by the addition of reducing agents such as dithiothreitol (DTT) or tris(2-carboxyethyl)phosphine (TCEP). The chemical shift of beta carbon of cysteine changes from 41.2 ppm to 28.2 ppm, definitively confirming the formation of disulfide bonds [START_REF] Sharma | Rajarathnam, 13C NMR chemical shifts can predict disulfide bond formation[END_REF]. As shown in Figure 1F, oxidation perturbs the chemical shift of the amide region in a very specific region of the molecule that involves the cysteine and its neighbouring aminoacids. No other important changes are observed, indicating that the dimer remains substantially unstructured.

The chemical shift of amide protons reveals a peculiar electronic distribution in Sesquin

The values of chemical shifts indicate that amide protons in Sesquin appear progressively shielded from residue T2 to Y10 (K1 is not detected). With the exception of L6, also the deviations from random coil values (Figure 1E) confirm this peculiar trend. This indicates that the electronic density at the level of amide protons increases from the first to the last residue, possibly leaving on the former a substantial positive charge. Such a peculiar charge distribution might have a role in the interaction with its target (see section 3.7).

Interaction with model membranes

Studies with DPC micelles suggests poor affinity for PC head groups

The interaction of Sesquin with dodecylphosphocholine (DPC) micelles was followed by NMR, to ascertain its tendency to assume secondary structure in their hydrophobic cores.

Micelles allow the study in solution and provide a very rough model of the apolar environment within biological membranes. Contrary to other peptides [START_REF] Liu | A potential food biopreservative, CecXJ-37N, noncovalently intercalates into the nucleotides of bacterial genomic DNA beyond membrane attack[END_REF][START_REF] Ramos-Martín | Antimicrobial Peptide K11 Selectively Recognizes Bacterial Biomimetic Membranes and Acts by Twisting Their Bilayers[END_REF] and despite the complementary charges of the exposed choline groups, Sesquin does not seem to interact with DPC micelles (Figure S2), suggesting its poor affinity for the hydrophobic environment found in bilayers and the absence of a specific recognition of PC headgroups. Isotropic bicelles and liposomes are more realistic models, allowing to evaluate the interactions with a wider variety of phospholipids, able to better reproduce the membranes of different organisms [START_REF] Marcotte | Bicelles as model membranes for solid-and solution-state NMR studies of membrane peptides and proteins, Concepts in Magnetic Resonance Part A[END_REF][START_REF] Porcelli | On the role of NMR spectroscopy for characterization of antimicrobial peptides[END_REF].

Studies with isotropic bicelles suggests an interaction with PE head groups

With respect to micelles, isotropic bicelles allow a certain degree of control on its lipid composition, providing a better model for biological membranes still amenable to studies by solution state NMR [START_REF] Marcotte | Bicelles as model membranes for solid-and solution-state NMR studies of membrane peptides and proteins, Concepts in Magnetic Resonance Part A[END_REF][START_REF] Porcelli | On the role of NMR spectroscopy for characterization of antimicrobial peptides[END_REF]. Also in this case, Sesquin showed a relative insensitivity to the presence of bicelles of various compositions (Figure S3A). Weakening of peaks in the HSQC spectra (Figure S3B) is partly attributable to partial oxidation of the sample during the experiments or artifacts due to the presence of bicelles, whose lipids are much more concentrated than the peptide (we used a peptide: lipid ratio of 1:25 and the result did not change even with a ratio of 1:80). On the other hand, peaks relative to the N terminus (Hα/Cα of residues T2, C3, E4) tend to disappear and the effect is more evident in the presence of DMPE, suggesting a preference for phosphatidylethanolamine (Figure S3B, bottom). The presence of a conserved Cys residue could indicate a possible role of disulphide bonds in the mechanism of action. However, the oxidised form of Sesquin remains quite insensitive to the presence of bicelles, possibly displaying a weak interaction with DMPC/DHPC bicelles (Figure S3B, top).

Studies with MLVs show Sesquin preference for fungal and bacterial lipids

Multilamellar vesicles (MLVs) or liposomes provide more realistic models of biological membranes in that they allow phospholipid mixtures incompatible with bicelles or micelles.

Thanks to their properties, we have been able to study their interaction with Sesquin at variable temperatures (in a range from 283 K to 310 K) and using a wide range of lipid compositions mimicking membranes of different organisms.

Static 2 H NMR of liposomes provides valuable information on the internal dynamics of the bilayer when the acyl chains of phospholipids are deuterated. For a matter of simplicity in spectra interpretation, we performed our measurements on phospholipids deuterated only in the palmitoyl chain. Each 2 H atom presents a quadrupolar splitting whose magnitude scales with its dynamics, due to averaging of orientations with respect to the external magnetic field [START_REF] Davis | The description of membrane lipid conformation, order and dynamics by 2H-NMR[END_REF][START_REF] Molugu | Concepts and Methods of Solid-State NMR Spectroscopy Applied to Biomembranes[END_REF][START_REF] Salnikov | Membrane order perturbation in the presence of antimicrobial peptides by (2)H solid-state NMR spectroscopy[END_REF]. As a consequence, 2 H atoms in very mobile molecular fragments, as methyl groups, display small quadrupolar splitting and appear at the center of the spectrum. Conversely, 2 H atoms located in the rigid part of the acyl chain, as well as those found close to the ester bond (the plateau region including carbon atoms 2-6), display almost full couplings and appear at the edges of the spectrum. Insertion of molecules in the bilayer is usually accompanied by a change in the degrees of freedom of acyl chains and can be used as an indirect experiment to probe the depth of the interaction [START_REF] Harmouche | Lipid-Mediated Interactions between the Antimicrobial Peptides Magainin 2 and PGLa in Bilayers[END_REF][START_REF] Matsuzaki | Orientational and aggregational states of magainin 2 in phospholipid bilayers[END_REF]. The peptide may have a rigidifying or fluidifying effect, monitored as an increase or a decrease in the width of the 2 H spectrum, respectively [START_REF] Salnikov | Membrane order perturbation in the presence of antimicrobial peptides by (2)H solid-state NMR spectroscopy[END_REF][START_REF] Aisenbrey | The Mechanisms of Action of Cationic Antimicrobial Peptides Refined by Novel Concepts from Biophysical Investigations[END_REF][START_REF] Dufourc | Delta-haemolysin from Staphylococcus aureus and model membranes. A solid-state 2H-NMR and 31P-NMR study[END_REF][START_REF] Dufourc | Molecular details of melittin-induced lysis of phospholipid membranes as revealed by deuterium and phosphorus NMR[END_REF][START_REF] Jean-François | Aggregation of cateslytin beta-sheets on negatively charged lipids promotes rigid membrane domains. A new mode of action for antimicrobial peptides?[END_REF][START_REF] Zhang | Mechanism of penetration of Antp(43-58) into membrane bilayers[END_REF]. Among the large variety of liposome types tested (Figure 2), a clear fluidifying effect is observed with PE (Figure 2B) over PC (Figure 2A). Note that PE solutions must contain at least a small percentage of PC (see Material and methods section) for the correct assembly of liposomes [START_REF] Sendecki | Supported Lipid Bilayers with Phosphatidylethanolamine as the Major Component[END_REF][START_REF] Lewis | The physicochemical properties of cardiolipin bilayers and cardiolipincontaining lipid membranes[END_REF][START_REF] Tari | Structure and function relationship of phosphatidylglycerol in the stabilization of phosphatidylethanolamine bilayer[END_REF][START_REF] Szoka | Comparative properties and methods of preparation of lipid vesicles (liposomes)[END_REF][START_REF] Papahadjopoulos | Phospholipid model membranes. I. Structural characteristics of hydrated liquid crystals[END_REF][START_REF] Litman | Lipid model membranes. Characterization of mixed phospholipid vesicles[END_REF][START_REF] Tinker | On the identification of lamellar and hexagonal phases in negatively stained phospholipid-water systems[END_REF][START_REF] Junger | Liquid crystalline phases of hydrated phosphatidylethanolamine[END_REF]. The effect is conserved in the presence of ergosterol, which was added to PE liposomes to better model fungal membranes [START_REF] Perczyk | The role of phospholipid composition and ergosterol presence in the adaptation of fungal membranes to harsh environmental conditions-membrane modeling study[END_REF][START_REF] Thevissen | Interactions of antifungal plant defensins with fungal membrane components[END_REF][START_REF] Lösel | Lipids in the Structure and Function of Fungal Membranes[END_REF][START_REF] Makovitzki | Ultrashort antibacterial and antifungal lipopeptides[END_REF][START_REF] Weete | Lipid Biochemistry of Fungi and Other Organisms[END_REF]. The presence of ergosterol slightly reduces the fluidification induced by Sesquin (Figure 2C), proportionally to its concentration (Figure S4). Analyzing liposomes with different phospholipid compositions, we observed small effects for PI (Figure 2F) and CL (figure 2G), typically found in fungal [START_REF] Makovitzki | Ultrashort antibacterial and antifungal lipopeptides[END_REF][START_REF] Shrestha | Membrane lipid-modulated mechanism of action and non-cytotoxicity of novel fungicide aminoglycoside FG08[END_REF][START_REF] Avrahami | A new group of antifungal and antibacterial lipopeptides derived from nonmembrane active peptides conjugated to palmitic acid[END_REF] and bacterial membranes (but also mitochondrial) [START_REF] Watson | Biological membranes[END_REF][START_REF] Galanth | Mechanism of antibacterial action of dermaseptin B2: interplay between helix-hinge-helix structure and membrane curvature strain[END_REF][START_REF] Romantsov | Cardiolipin and the osmotic stress responses of bacteria[END_REF][START_REF] Lopes | Improved model systems for bacterial membranes from differing species: the importance of varying composition in PE/PG/cardiolipin ternary mixtures[END_REF], respectively, while not for pure PG and PS (Figures 2D,E). This is an interesting observation as Sesquin targets several bacteria, although with lower activities than fungi [START_REF] Wong | Sesquin, a potent defensin-like antimicrobial peptide from ground beans with inhibitory activities toward tumor cells and HIV-1 reverse transcriptase[END_REF].

Bacterial membranes are typically composed of a mixture of PE, PG and CL [START_REF] Watson | Biological membranes[END_REF][START_REF] Galanth | Mechanism of antibacterial action of dermaseptin B2: interplay between helix-hinge-helix structure and membrane curvature strain[END_REF][START_REF] Romantsov | Cardiolipin and the osmotic stress responses of bacteria[END_REF][START_REF] Lopes | Improved model systems for bacterial membranes from differing species: the importance of varying composition in PE/PG/cardiolipin ternary mixtures[END_REF].

Our experiments with mixed lipid compositions show that Sesquin has an important fluidification effect on such type of liposomes (Figure 2I) but is not able to perturb the internal dynamics of PE/PG bilayers (Figure 2H), probably because of the richer network of interactions that the peptide would need to break for its insertion [START_REF] Galanth | Mechanism of antibacterial action of dermaseptin B2: interplay between helix-hinge-helix structure and membrane curvature strain[END_REF][START_REF] Murzyn | Phosphatidylethanolamine-phosphatidylglycerol bilayer as a model of the inner bacterial membrane[END_REF]. The addition of CL in PE/PG bilayer rigidifies the membrane significantly as demonstrated by the increase in the overall width of the spectrum (compare Figure 2H and figure 2I) while breaking some of these interactions [START_REF] Lewis | The physicochemical properties of cardiolipin bilayers and cardiolipin-containing lipid membranes[END_REF]. As a consequence, the peptide might penetrate more easily causing a change in fluidity even more apparent.

Molecular dynamics studies on phospholipid bilayers confirm a specific recognition of PE

Molecular dynamics (MD) simulations were performed to study Sesquin interaction with various bilayers. While other techniques and sampling algorithms are better suited for the detection of processes needing a longer time scale to occur [START_REF] Yang | Melittin-Induced Permeabilization, Re-sealing, and Repermeabilization of E. coli Membranes[END_REF][START_REF] Avci | Membrane Active Peptides and Their Biophysical Characterization[END_REF][START_REF] Orsi | Dual-resolution molecular dynamics simulation of antimicrobials in biomembranes[END_REF][START_REF] Kästner | Umbrella sampling: Umbrella sampling[END_REF][START_REF] Barducci | Metadynamics: Metadynamics[END_REF][START_REF] Marrink | Computational Modeling of Realistic Cell Membranes[END_REF][START_REF] Mori | Molecular dynamics simulations of biological membranes and membrane proteins using enhanced conformational sampling algorithms[END_REF], MD still allows us to better understand the mechanism of action of this peptide at the first stages of the interaction and to study a wider range of membrane lipid compositions otherwise harder to achieve experimentally. MD also permits a direct comparison with NMR data, providing a molecular picture for their interpretation.

Snapshots of characteristic peptide-membrane interactions are shown in Figure 3. In our simulations, Sesquin does not show an affinity for POPC membranes (Figure 3), although the two-fold positive N-terminus might be electrostatically attracted to the negatively charged phosphate groups of POPC. Likewise, another electrostatic interaction could potentially be established between the choline group and the side chains of E4 and D8, which are deprotonated at physiological pH. The absence of interaction is probably due to the steric hindrance of the choline headgroup, which does not allow distances sufficiently short for a significant Coulombic attraction. This result is consistent with the absence of relevant interaction with the PC headgroup observed by liquid and solid-state NMR (Figures S2, S3 and2).

In POPE membranes (Figure 3), this steric hindrance is removed (the three methyls of choline are replaced by three hydrogen atoms) and the interactions hypothesized above are allowed to take place: we observe the formation of a salt bridge between the amine groups of K1 with the negatively charged oxygen atoms of the membrane phosphates and between the carboxylates of E4, D8 and of the C-terminus with the positively charged amine group of POPE. In order to have a more quantitative analysis of such interactions, we calculated the radial distribution function [START_REF] Berendsen | Interaction Models for Water in Relation to Protein Hydration[END_REF] of each N, O atom of the membrane with respect to each N, O atom of the peptide and we extracted the maximum of these curves within the H-bond/saltbridge distances. The obtained values for each couple of polar atoms (Figures S5-S7) give an estimate of the frequency of such interactions along MD trajectories and, consequently, of their probabilities. Results in Figure S5 show very clearly that Sesquin approaches the membranes with its N-terminus but, with the exception of POPE, it is not able to establish a stable interaction involving its complete sequence. The frequency of the interaction is very poor in POPC (even the most frequent, between the N-terminus of Sesquin and one oxygen of its phosphate, occurs rarely) while it becomes important in POPE. In this case, the most frequent interaction is between the lysine side chain of Sesquin and one oxygen of its phosphate. Most importantly, Figures 3 andS5-S9 show that Sesquin interacts entirely with membranes (and not only with its N-terminus) uniquely when POPE is present because only POPE (and POPS) provide an accessible positively charged group that can interact with its negatively charged groups (E4, D8 and the C-terminus). In the case of POPS (Figure S5), the carboxylate of serine headgroup probably reduces the accessibility of Sesquin and/or weakens the electrostatic interaction with the amine of POPS. Accordingly, most of the interactions established by negatively charged carboxylates of Sesquin with POPE are lost with PS.

Figure 3. MD snapshots showing Sesquin at characteristic distance from several membranes with variable phospholipid compositions. Color code: phosphorus atom: yellow. POPC black (body) and light gray (choline group); POPE dark green (body), turquoise (headgroup), light green (amine of the headgroup); POPS brown (body), gold (headgroup), light yellow (amine of the headgroup) and orange (carboxyl of the headgroup); POPI blue (body), light blue (headgroup), cyan (hydroxyls of the headgroup); POPG dark violet (body), violet (headgroup), light violet (hydroxyls of the headgroup); CL dark red (body) and light red (headgroup

blue (N-terminus) to red (C-terminus). Side chains are shown as sticks with the following color code: positively charged (blue), negatively charged (red), non-polar (light gray), polar (yellow).

A remarkable affinity for PE containing membranes is confirmed by a deep insertion of the peptide, highlighted by a significant amount of apolar contacts (Figure S8). This phenomenon is observed not only in pure PE membranes but also with bacterial biomimetic membranes containing PE and in most PE based membranes with different sterols (Figures S9 andS10).

In the case of POPI, the network of interactions shown in Figure S6 is very simple as compared to other cases. Despite the steric hindrance of the inositol ring, the interaction between the N-terminus of Sesquin and one oxygen of POPI phosphate is frequent (Figure S6). No other significant interactions are observed while NMR data suggest a slight fluidification of POPI containing MLVs (Figure 2F).

In the case of POPG, the oxydrils in the headgroup do not seem to be involved in specific H-bonds and Sesquin interacts sporadically with only its N-terminus (Figure S5), without being able to penetrate the bilayer (Figure S8), as experimentally confirmed (Figure 2). The situation is different with CL, despite the similarity of the functional groups in the two lipids. In this case, the oxygen atoms of the phosphate groups (OP13, OP14, OP33 and OP34) are accessible and readily available for interaction and Sesquin can bind them in bidentate fashion by using both its N-terminal and K1 side chain amines (Figure S6). Even if the interaction remains superficial (Figure S9), the geometry of CL makes Sesquin closer to the acyl chains of the bilayer.

The antifungal activity of Sesquin seems to involve a specific recognition of both PE and ergosterol

If our data have revealed an enhanced preference of Sesquin for PE phospholipid, it should be noted that PE is present in many different organisms and this specificity can explain Sesquin activity towards a wide range of organisms (not only fungi but also bacteria, virus [START_REF] Phoenix | The increasing role of phosphatidylethanolamine as a lipid receptor in the action of host defence peptides[END_REF][START_REF] Lorizate | Comparative lipidomics analysis of HIV-1 particles and their producer cell membrane in different cell lines[END_REF][START_REF] Brügger | The HIV lipidome: a raft with an unusual composition[END_REF][START_REF] Henriques | Phosphatidylethanolamine binding is a conserved feature of cyclotide-membrane interactions[END_REF][START_REF] Henriques | Decoding the Membrane Activity of the Cyclotide Kalata B1[END_REF] and cancer cells [START_REF] Phoenix | The increasing role of phosphatidylethanolamine as a lipid receptor in the action of host defence peptides[END_REF][START_REF] Stafford | Increased exposure of phosphatidylethanolamine on the surface of tumor vascular endothelium[END_REF][START_REF] Musters | Sarcolemmal phosphatidylethanolamine reorganization during simulated ischaemia and reperfusion[END_REF][START_REF] Zhou | Identification of plasma lipid biomarkers for prostate cancer by lipidomics and bioinformatics[END_REF][START_REF] Emoto | Exposure of phosphatidylethanolamine on the surface of apoptotic cells[END_REF]). We therefore decided to investigate the effect of other lipids in POPE bilayers (Figure 3) and reproduce the composition of fungal (POPE/ERGO) [START_REF] Perczyk | The role of phospholipid composition and ergosterol presence in the adaptation of fungal membranes to harsh environmental conditions-membrane modeling study[END_REF] and bacterial (POPE/POPG or POPE/POPG/CL) membranes. The effect of sterols found in plants (SITO or STIGMA) [START_REF] Valitova | Plant Sterols: Diversity, Biosynthesis, and Physiological Functions[END_REF] or vertebrates (CHO) was also studied to evaluate potential additional specificities.

In all cases, Sesquin interacts extensively, making a wide network of interactions with the membranes (Figure S6 andS7). The detailed behavior of Sesquin varies significantly from case to case. In bilayers representing bacterial membranes, a preference for PE over PG can be observed (Figure S6). When CL is present, the affinity increases significantly but interactions with CL predominate over PE.

An interesting aspect emerging from simulations is the formation of alpha helical structures in some POPE containing membranes. In most simulations, Sesquin is unstructured and quickly loses the initial alpha helical conformation predicted by the SATPdb database [START_REF] Singh | SATPdb: a database of structurally annotated therapeutic peptides[END_REF].

However, such helical structure reforms in POPE, ergosterol-containing POPE (typical of fungi) and sitosterol membranes (Figure S11 andS12). In other words, the amphipathic character of Sesquin created by the helical conformation (Figure 1D) is probably necessary for its action and could explain why Sesquin is a more potent antifungal than antibacterial. Figure 3 clearly shows that when a helix is formed, Sesquin can penetrate much deeper and establish polar contacts from the interior (the positive side chain of K1 with the phosphate oxygen atoms and the negative side chains of E4 and D8 with the amine groups of PE), thus destabilizing the membrane order. If the helix is not formed, the peptide still interacts but remains outside the bilayer. Once in the membrane it may act as other common AMPs [START_REF] Grage | Membrane Thinning and Thickening Induced by Membrane-Active Amphipathic Peptides[END_REF].

As its short length does not allow encompassing the full membrane for the formation of a channel, Sesquin may be viewed as a PE specific AMP acting on membrane by carpet model [START_REF] Nikoletta | Antifungal proteins: More than antimicrobials?[END_REF].

Even if outside the scope of this work, it is interesting to point out that the selectivity for PE is able to explain its anticancer activity, due to the fact that apoptotic cancer cells and mitochondria of carcinogenic cells [START_REF] Horton | Mitochondria-penetrating peptides[END_REF] tend to expose PE on their outer leaflet [START_REF] Phoenix | The increasing role of phosphatidylethanolamine as a lipid receptor in the action of host defence peptides[END_REF][START_REF] Stafford | Increased exposure of phosphatidylethanolamine on the surface of tumor vascular endothelium[END_REF][START_REF] Musters | Sarcolemmal phosphatidylethanolamine reorganization during simulated ischaemia and reperfusion[END_REF][START_REF] Zhou | Identification of plasma lipid biomarkers for prostate cancer by lipidomics and bioinformatics[END_REF][START_REF] Emoto | Exposure of phosphatidylethanolamine on the surface of apoptotic cells[END_REF].

In a similar way, Sesquin could disrupt the envelope of HIV explaining its antiviral activity [START_REF] Phoenix | The increasing role of phosphatidylethanolamine as a lipid receptor in the action of host defence peptides[END_REF][START_REF] Lorizate | Comparative lipidomics analysis of HIV-1 particles and their producer cell membrane in different cell lines[END_REF][START_REF] Brügger | The HIV lipidome: a raft with an unusual composition[END_REF][START_REF] Henriques | Phosphatidylethanolamine binding is a conserved feature of cyclotide-membrane interactions[END_REF][START_REF] Henriques | Decoding the Membrane Activity of the Cyclotide Kalata B1[END_REF], although this has been ascribed to a direct interaction with the HIV reverse transcriptase.

Focusing on its antifungal properties, we need to take into account the activity in the presence of ergosterol, the most common fungal sterol [START_REF] Perczyk | The role of phospholipid composition and ergosterol presence in the adaptation of fungal membranes to harsh environmental conditions-membrane modeling study[END_REF]. Despite their relatively similar structure, we found an apparent preference of Sesquin for ergosterol. Such an affinity is highlighted by the presence of both polar and apolar contacts (Figures S7 andS10), but also a perturbation of the area per lipid (Figure S13 andS14) and the order parameter of the POPE palmitoyl side chains S(CD). The latter expresses the order of CH moieties in phospholipid acyl chains. It can be measured as a reduction of the quadrupolar splitting in NMR 2 H spectra [START_REF] Davis | The description of membrane lipid conformation, order and dynamics by 2H-NMR[END_REF][START_REF] Salnikov | Membrane order perturbation in the presence of antimicrobial peptides by (2)H solid-state NMR spectroscopy[END_REF][START_REF] Douliez | Fully deuterated magnetically oriented system based on fatty acid direct hexagonal phases[END_REF] or calculated in MD simulations (Figure S15).

In particular, Sesquin can form polar contacts between the T2 or C3 side chains and the hydroxyl of ergosterol (Figure S7) that were not found with other sterols. As mentioned above, Sesquin folds into a helix only in the presence of sitosterol and ergosterol (Figure S12), but penetrates more deeply in the latter case (Figure S10) for which direct peptide-sterol contacts are observed, thus explaining the different effects on the order parameter (Figure S15). In the case of cholesterol and stigmasterol, Sesquin never penetrates deeply, probably due to the increased rigidity conferred by these sterols [START_REF] Salnikov | Membrane order perturbation in the presence of antimicrobial peptides by (2)H solid-state NMR spectroscopy[END_REF][START_REF] Brown | Sphingolipid organization in biomembranes: what physical studies of model membranes reveal[END_REF] (higher values of the order parameter in Figure S15). The preference for ergosterol over other sterols might be due to the slightly different geometry of its condensed ring body, caused by the introduction of a double bond between carbons 7 and 8 making the overall shape more planar than the other sterols (see the comparison with cholesterol in Figure S16).

A linear gradient of charge to approach the membrane and an amphipathic helix for its disruption

As discussed in section 3.3, NMR data indicate a progressive decrease in electronic density towards Sesquin N-terminus. In simulations, we observe that the peptide approaches the membrane as an arrow (see Figure 4) inserting in the membrane either the side chain or the terminal amine of K1. Subsequently, the peptide folds into alpha helical conformation which allows the establishment of salt bridges with the amine of PE headgroups. By clinging to such a group with the carboxylates of E4 and D8 (which reside on the same side of the helix), hydrophobic side chains on the opposite side "fall" into the hydrophobic core. Subsequently, other interactions can be formed including a further salt bridge between the amine of PE and the carboxy terminus. T9 is on the same side of the helix as T2 but does not seem to participate in the recognition.

A possible cooperative effect was explored by performing the simulations with 8 peptides per system. Although Sesquin tends to form aggregates by approaching the hydrophobic surface in helical conformation, each peptide seems to act independently in the first stages of the interaction with the membrane. The overall effect on the membrane can be better evaluated by calculating the area per lipid (Figures S13 andS14). In the case of PEcontaining membranes the ensemble of the peptides exert a significant pressure on the surface, invaginating the bilayers as demonstrated by the increase and decrease of the area per lipid of the outer and inner leaflet, respectively.

A potential food preservative

For its unique properties as antifungal and antibacterial and the lack of hemolytic or cytotoxic activities [START_REF] Wong | Sesquin, a potent defensin-like antimicrobial peptide from ground beans with inhibitory activities toward tumor cells and HIV-1 reverse transcriptase[END_REF], we have investigated the effect of some of the most used food preservation techniques on the molecular properties of Sesquin. In particular we have focused on temperature and pressure changes but also on the usage of electrical pulses. MD simulations have shown to be suitable to study novel food processing technologies such as high pressure and electric fields in combination with antimicrobial peptides [START_REF] Ding | Effects of High Pressure on Phospholipid Bilayers[END_REF][START_REF] Chen | Molecular Dynamics Simulation for Mechanism Elucidation of Food Processing and Safety: State of the Art[END_REF][START_REF] Sun | Molecular dynamics simulations of phase transition of lamellar lipid membrane in water under an electric field[END_REF][START_REF] Wang | The penetration of a charged peptide across a membrane under an external electric field: a coarse-grained molecular dynamics simulation[END_REF][START_REF] Machado | Tuning the transdermal transport by application of external continuous electric field: a coarse-grained molecular dynamics study[END_REF][START_REF] Kong | Investigation of the morphological transition of a phospholipid bilayer membrane in an external electric field via molecular dynamics simulation[END_REF].

When lowering the temperature to 278 K, some membranes undergo phase transitions, namely POPE (Tm=298 K) and POPS (Tm=287 K). Others approach the phase transition: POPC (Tm=271 K) and POPG (Tm=271 K) [START_REF] Silvius | Thermotropic phase transitions of pure lipids in model membranes and their modifications by membrane proteins[END_REF]. With the exception of CL (Tm=345 K), all other systems are significantly more rigid [START_REF] Kranenburg | Phase behavior of model lipid bilayers[END_REF]. In this conditions, two effects play a role in the mode of interaction: (i) due to the decreased kinetic energy available at lower temperature, Sesquin tends to reside longer on membrane surfaces, establishing similar polar contacts as those described at 310K (Figures S17-S19); (ii) due to the increased rigidification of the membrane, Sesquin tends to penetrate less in the bilayers (Figures S19-S21). The first effect determines invagination of the membrane with one or multiple peptides (see the effect on the area per lipid, Figures S22 andS23) while the second effect significantly reduces the amount of apolar contacts with the acyl chains of phospholipids (Figures S19-S21). Overall, Sesquin penetrates only in pure PE, PE/ergosterol and in pure CL membranes where the acyl chains are directly accessible for the absence of a large headgroup.

While our simulations at 310 K did not reveal a specificity for POPI, at 278 K a clear reduction of the order parameter is observed only for this type of membranes (see Figure S24), demonstrating that Sesquin does not need to insert deeply in the POPI bilayer to fluidify it.

Pressure has been used as a way to preserve food [START_REF] Yang | Inactivation of foodborne pathogens in raw milk using high hydrostatic pressure[END_REF][START_REF] Ritz | Physiological damages of Listeria monocytogenes treated by high hydrostatic pressure[END_REF]. Some of the advantages of this approach are the short process times [START_REF] Heinz | Food preservation by high pressure[END_REF], energy saving, and a good conservation of organoleptic properties [START_REF] Dijksterhuis | Activation of ascospores by novel food preservation techniques[END_REF]. High pressure has also been tested to prevent prions contamination [START_REF] Knorr | High pressure application for food biopolymers[END_REF][START_REF] Norton | Recent Advances in the Use of High Pressure as an Effective Processing Technique in the Food Industry[END_REF]. On the other hand, some organisms including fungi [START_REF] Dijksterhuis | Activation of ascospores by novel food preservation techniques[END_REF][START_REF]Fungi in Extreme Environments[END_REF] are tolerant to high pressures [START_REF] Gaspar | Hydrostatic pressure induces the fusion-active state of enveloped viruses[END_REF][START_REF] Sharma | Sensitivity of Escherichia albertii, a Potential Food-Borne Pathogen, to Food Preservation Treatments[END_REF][START_REF] Karatzas | Characterization of a Listeria monocytogenes Scott A isolate with high tolerance towards high hydrostatic pressure[END_REF], or express resistance genes to tolerate such conditions [START_REF] Domitrovic | High hydrostatic pressure activates gene expression through Msn2/4 stress transcription factors which are involved in the acquired tolerance by mild pressure precondition in Saccharomyces cerevisiae[END_REF][START_REF] Teixeira | A genome-wide perspective on the response and tolerance to food-relevant stresses in Saccharomyces cerevisiae[END_REF]. Combination with other agents, as AMPs, could help to overcome these issues.

Under high pressure conditions and in the absence of Sesquin, we observe a significant decrease of area per lipid (data not shown) and an increase in the order parameter of acyl chains (Figure S25), in some cases due to the induction of phase transitions. Electron density profiles comparing the different membranes under atmospheric and high pressures (1000 bar) were also evaluated (see Figure S26). For most of the membranes (except for those undergoing phase transitions like POPE and POPS) it can be seen that densities are slightly lower at the two peaks corresponding to the lipid head groups while higher at the central region. This would indicate a reduction in the volume in the center of the bilayer, while it is harder to compress further the more dense regions close to the head groups. Such effects were previously described in the literature for POPC and DOPC [START_REF] Ding | Effects of High Pressure on Phospholipid Bilayers[END_REF]. Pure POPE and POPS membranes undergo a phase transition at these high pressure conditions, leading to more remarkable changes in the profiles (Figure S26).

When a high pressure is applied in the presence of Sesquin, behaviors similar to those described at low temperature are observed but in this case the rigidification of the membrane can be dramatic, independently of the phase transition temperature. As a consequence, larger perturbations of the area per lipid are observed for PE, PE/ergosterol, PI and PS (compare Figures S27 andS28 with Figure S29) while the peptide penetrates poorly in all bilayers (Figures S30-S32) with the notable exception of PE and PE/ergosterol bilayers. This confirms the selective preference of Sesquin for fungal-like membranes and its possible use under high pressure conditions, allowing a synergistic effect aiming at destroying recalcitrant bacterial or fungal cells.

An emerging technique for food preservation is electric field processing. It has been successfully used with liquid or semi solid food such as milk, youghourts, soups and liquid eggs. In the last years it has been extended to solid meals [START_REF] Bhat | Current and future prospects for the use of pulsed electric field in the meat industry[END_REF]. Additionally, this technique has shown its capacity to preserve nutritional properties such as the vitamins content [START_REF] Yeom | Processing of yogurt-based products with pulsed electric fields: Microbial, sensory and physical evaluations[END_REF][START_REF] Jha | Advances of electro-freezing in food processing[END_REF][START_REF] Wang | Enhancing Food Processing by Pulsed and High Voltage Electric Fields: Principles and Applications[END_REF][START_REF]Pulsed electric field processing: An emerging technology for food preservation[END_REF][START_REF] Grahl | Killing of microorganisms by pulsed electric fields[END_REF][START_REF] Reina | Inactivation of Listeria monocytogenes in milk by pulsed electric field[END_REF][START_REF] Chen | Adaptation response of Pseudomonas fragi on refrigerated solid matrix to a moderate electric field[END_REF][START_REF] Kang | Supercooling preservation technology in food and biological samples: a review focused on electric and magnetic field applications[END_REF]. At variance with the previously described preservation methods, electric fields fluidify membranes (Figure S33) rather than making them more stiff, thus favouring the penetration of Sesquin. The choice of the electric field strength was dictated by the need to weaken the studied bilayer without disrupting it by its sole action. The analysis of polar and apolar contacts clearly show that electric fields amplify the antimicrobial effect of Sesquin (Figures S34-S38). In these conditions, Sesquin clearly lowers the order parameters of palmitoyl acyl chains (Figure S39) in PE and PE/Ergosterol bilayers due to its penetration in their inner cores. In parallel, the antibacterial properties are amplified with the establishment of polar and apolar contacts with all phospholipids present in bacterial membranes (PE,PG and CL) and their mixtures. It is worth pointing out that POPC bilayers (here representing mammalian membranes) remain poorly perturbed by the presence of the peptide even in such conditions. The use of Sesquin could allow lowering the power of electric fields commonly used for food preservation with benefits for food integrity, organoleptic properties and lower energy consumption.

Conclusions

While we chemically synthesized Sesquin for our mechanistic study, applications should take into account strategies to make the production costs feasible such as its synthesis via fermentation. Once the ecological impact on fields is ascertained, applications in cropprotection could also be postulated by bioengineering of symbiotic bacteria although this is beyond the scope of the present workUnlike most antimicrobial peptides, Sesquin is a negatively charged molecule. Such a feature is the key for its specificity towards phosphatidylethanolamine headgroup, which contains a positively charged amine group. The overall negative charge of Sesquin is limited to -1 at physiological pH which could be a compromise between attraction to the PE amine groups and the overall negative charge, typically found in fungal membranes. In Sesquin, the electronic density on each amide proton gradually diminishes from the C-terminus to the N-terminus where two positive charges are present on the backbone and sidechain amine groups. The N-terminus is able to interact with negatively charged phosphate oxygen atoms in the interior of the bilayer, acting as an arrow.

After an initial electrostatic attraction, the negatively charged residues E4 and D8 form salt bridges with the amine moieties of PE, whose flexibility and poor hindrance facilitate the folding of Sesquin in an amphipathic alpha helix. In the final step, the apolar side of the helix drops into the interior of the target bilayer and Sesquin remains anchored to the phosphate groups, while occupying the layer underneath. In the case of phosphatidylcholine membranes, the presence of methyl groups in the amine of choline might account for the impossibility to form salt bridges with E4 and D8 while their increased steric hindrance might prevent the insertion of the helix.

Our data clearly show a remarkable selectivity of Sesquin for ergosterol containing membranes, thus explaining its main antifungal activity and making it a good candidate for food preservation. Its activity does not seem to be hampered by the use of common preservation techniques, possibly allowing its use for a synergistic antimicrobial action.

Figure 2 .

 2 Figure 2. Static 2 H NMR spectra of various MLV liposomes in the absence (blue) and the presence (red) of Sesquin.

  ); CHO purple (body) and light purple (hydroxyl); ERGO dark orange (body) and light orange (hydroxyl); SITO deep-dark green (body) and pea-green (hydroxyl); STIGMA electric blue (body) and light electric blue (hydroxyl). For clarity, only functional groups of headgroups are represented as spheres in the upper leaflet. Sesquin is shown as "tube" representation, colored from

Figure 4 .

 4 Figure 4. Schematic representation of the mode of action of Sesquin peptide approaching targeted membranes. (A) Sesquin approaches the target membrane by forming a salt bridge

Acknowledgements

We would like to thank Habiba Hasnaoui for assistance in the sample preparation and NMR assignment. We also thank the Matrics platform at the University "Picardie Jules Verne" and the "Méso-centre de Calcul Scientifique Intensif" at the University of Lille for providing computing resources.

Funding

Francisco Ramos-Martín ' s PhD scholarship was co-funded by Conseil régional des Hauts-de-France and by European Fund for Economic and Regional Development (FEDER); Claudia Herrera-León's PhD scholarship was funded by the National Council for Science and Technology (CONACYT).

Abbreviations

Competing interests

The authors declare that they have no competing interests.

CRediT authorship contribution statement

Competing interests

The authors declare that they have no competing interests.

Appendix A. Supplementary data

The following are the Supplementary data to this article: …