Farah Ben-Naoum
email: farahbennaoum@yahoo.fr

Christophe Godin
email: christophe.godin@inria.fr.

Algorithmic Height Compression of Unordered Trees

Keywords: Plants modeling, branching structures, self-nestedness, quasi-isomorphism, height redundancy

By nature, tree structures frequently present similarities between their subparts. Making use of this redundancy, different types of tree compression techniques have been designed in the literature to reduce the complexity of tree structures. A popular and efficient way to compress a tree consists of merging its isomorphic subtrees, which produces a directed acyclic graph (DAG) equivalent to the original tree. An important property of this method is that the compressed structure (i.e. the DAG), has the same height as the original tree, thus limiting partially the possibility of compression. In this paper we address the problem of further compressing this DAG in height. The difficulty is that compression must be carried out on substructures that are not exactly isomorphic as they are strictly nested within each-other. We thus introduced a notion of quasi-isomorphism between subtrees, that makes it possible to define similar patterns along any given path in a tree. We then proposed an algorithm to detect these patterns and to merge them, thus leading to compressed structures corresponding to DAGs augmented with return edges. In this way, redundant information is removed from the original tree in both width and height, thus achieving minimal structural compression. The complete compression algorithm is then illustrated on the compression of various plant-like structures.

Introduction

Many plants like trees exhibit complex branching structures. These structures contain large numbers of components (branches, leaves, flowers, etc.) whose organization in space may give a mixed feeling of both order and disorder. The impression of disorder often comes from the fact that components apparently do not follow any clear deterministic rule and that spatial distribution of organs do not show exact symmetries. However, most of the time, behind this semi-chaos, the same branching structures also show some order in their organization as many sub-structures look similar, hierarchies can be identified among branches and some symmetries in shapes, although none exact-ones, seem to exist. During decades, botanists have strived to identify rules characterizing this order despite the apparent disorder in plant architectures, introducing notions such as repetition, modularity, gradients, symmetry of branching structures, e.g. [START_REF] Troll | Die wuchsform der baeume und straeucher[END_REF]; Arber (1950); [START_REF] Halle | Tropical trees and forests. An architectural analysis[END_REF]; [START_REF] Harper | The growth and form of modular organisms[END_REF]; [START_REF] Barthelemy | Levels of organization and repetition phenomena in seed plants[END_REF]. These rules, mainly of qualitative nature, gave key insights on how to address the notion of order in plant architectures.

In the early 70's, computational formalisms started to emerge to represent formally the architecture of branching structures, e.g. [START_REF] Lindenmayer | Developmental systems without cellular interactions, their languages and grammars[END_REF]; [START_REF] Lindenmayer | Developmental systems and languages[END_REF]; [START_REF] Lindenmayer | Developmental algorithms for multicellular organisms: A survey of l-systems[END_REF] ;[START_REF] Honda | Description of the form of trees by the parameters of the tree-like body: Effects of the branching angle and the branch length on the shape of the tree-like body[END_REF]. These new conceptual tools made it possible to consider the analysis of branching systems organization from a new and quantitative perspective.

Many approaches started from there to describe models as finite automata or grammars that could reproduce by simulation the branching organization of plants, e.g. [START_REF] Borchert | Control of development in the bifurcating branch system of tabebuia rosea: a computer simulation[END_REF]; [START_REF] Reffye | La modelisation de la croissance des plantes[END_REF]; [START_REF] Prusinkiewicz | The algorithmic beauty of plants[END_REF]. Among them, L-systems emerged in the plant modeling community as the most commonly used paradigm -based on rewriting rules-to model branching system development [START_REF] Prusinkiewicz | Modeling of spatial structure and development of plants: a review[END_REF]). Most of these approaches started from the design of a formal model embedding biological assumptions, and were defined to produce algorithmically branching systems similar to those observed in real plants. By contrast, the reverse (inverse) problem, namely building algorithmically a computational finite representation (model) from given observed branching systems, was much less studied.

On fractal images this inverse problem was solved on two dimensional images by Barnsley (1988Barnsley ( , 2006) ) using models of fractal geometry. However, these models rely on iterated function systems (IFS) which correspond to purely geometrical transformations. In particular, they don't take into account topology of the studied biological structures.

To account on inference, many approaches based on L-systems were also developed and reviewed later on in [START_REF] Ben-Naoum | A survey on l-system inference[END_REF]). However, due to the complexity of the general problem, these different approaches make various simplifying assumptions. These assumptions in general are not satisfactory in the context of study of biological organisms such as plants structures.

One particularly important simplifying hypothesis consists of focusing on the result of the developmental process without considering the intermediate stages of development. This leads to a whole class of approaches in which models are constructed to capture plant branching architecture in a minimal way. A first approach was proposed by [START_REF] Viennot | Combinatorial analysis of ramified patterns and computer imagery of trees[END_REF] based on a statistical analysis of binary tree organization. Subtrees were characterized by an integer representing their amount of asymmetry (the so called Holton-Strahler -HS-number [START_REF] Deussen | Digital Design of Nature: Computer generated plants and organics[END_REF])). Then parameters were inferred from data to describe statistically the probability of finding a tree with HS number n knowing the HS number m of the parent tree. A similar statistical but more general approach was later used by [START_REF] Durand | Analysis of the plant architecture via tree-structured statistical models: the hidden markov tree models[END_REF][START_REF] Durand | Segmentation-based approaches for characterising plant architecture and assessing its plasticity at different scales[END_REF], based on Markovian processes to describe subtrees frequencies at any given node. These inference approaches are aimed to capture the statistical properties of tree organization. Viewed as compression techniques, they provide approximated strategies to compress trees, relying on different types of a priori assumptions (e.g. Markovian property). An exact and deterministic approach was recently introduced in [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF].

In this latter work, the authors addressed the problem of recognizing similar, possibly nested, patterns in plant structures, and to compress them as directed acyclic graphs (DAGs) in a reversible way. Trees were represented as unordered labeled tree structures, where no order is assumed on the children of any node of the trees. Trees whose compression are linear DAGs define the class of self-nested trees, i.e. trees that have very high compressibility. From this, a degree of self-nestedness could be defined for any tree as the normalized edit-distance of this tree to the class of self-nested trees embedding the original tree, and a polynomial-time algorithm was designed to compute this distance.

The tree compressions techniques defined in [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF] are based on the merging of isomorphic subtrees. Any two subtrees that are merged therefore result in a structure with the same height. As a result, the compressed DAG, where all the isomorphic subtrees have been merged, has the same height as the original tree. If indeed compression occurs in width, no compression occurs in height. However, some trees such as high dichotomic trees or fish bone-like trees have a repetitive structure in height and are therefore poorly compressed by this technique. In this paper, we consider the problem of maximally compressing trees both in width and height with no loss of information. This idea is illustrated in Fig. 1. In section 3, we recall the definition of tree reduction and self-nestedness introduced in [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF]. We then introduce and study in section 4 a weak extension of tree isomorphism, called quasi-isomorphism, that will make it possible to identify similar (but not identical) tree patterns at different heights of a tree. Based on these definitions and their properties, we present in section 5 an algorithm able to compress in height the reduction of any tree. This algorithm is then applied to both theoretical tree-like structures and vegetal branching systems to characterize its compression ability.

For seek of clarity all property proofs described in the main text are given in the Online Supplementary Material.

Notational conventions

An undirected graph, is a pair G = (V, E) where V denotes a finite set of vertices and E a finite set of unordered pairs of vertices called edges. A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V , such that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph). A maximal clique is a clique that cannot be extended by including one more adjacent vertex from the original set of vertices.

A directed graph, is a pair G = (V, E) where all edges correspond to ordered pairs of vertices. Let (x, y) be an edge in E, x is called a parent of y and y is a child of x. A vertex that has no child is called a leaf. We will denote, in the sequel, by child(x) the set of all the children of x, and parent(x) the set of all parents vertices of x. In a directed graph G, the Indegree of a vertex v, denoted deg -(v), is the number of its parents, and its Outdegree, denoted deg + (v), is the number of its children. The Indegree and the Outdegree of G are respectively the maximum Indegree and the maximum Outdegree of all G vertices.

A path from a vertex x to a vertex y is a (possibly empty) sequence of edges {(x i , x i+1 )} i=1,M -1 such that x 1 = x, x M = y, and M correspond to |P | the length of P . For a path P we denote by V P the set of all vertices that belong to P . In an other hand, P = λ if P is an empty path. Where we denote by λ the empty path. Analogously, we say that there are no path between x and y, or there is an empty path.

A vertex x is called an ancestor of a vertex y (and y is called a descendant of x), noted x ≺ y, if there exists a path from x to y. Analogically, for the edges e = (x, y) and e = (x , y ) we can say that e ≺ e iff y ≺ x .

Given two paths

P 1 = {(x i , x i+1 )} i=1,N -1 and P 2 = {(y j , y j+1 )} j=1,M -1 :
• for x N = y 1 we define the paths union P 1 ∪ P 2 = {(x 1 , x 2 ), ..., (x N -1 , x N ), (y 1 , y 2 ), ..., (y M -1 , y M )}

• we denote V P 1 ∩ V P 2 the vertices paths intersection i.e. the subset of vertices common to both P 1 and P 2

• we say that -P 1 ⊂ P 2 if the sequence made by the subset of edges common to both P 1 and P 2 correspond to P 1 (path inclusion)

-P 1 ≺ P 2 ⇔ x N ≺ y 1 -P 1 P 2 ⇔ x N = y 1 (paths succession).
In a directed graph, we call cycle a non empty path whose extremities coincide to the same vertex. If the path is elementary, i.e. does not pass twice through the same vertex, it is called elementarycycle.

A directed acyclic graph (DAG) is a graph containing no cycle (but which may contain undirected cycles), [START_REF] Preparata | Introduction to discrete structures for computer science and engineering[END_REF]). A linear DAG is a DAG containing at least one path that goes through all its vertices.

A tree T is a connected graph containing neither directed of undirected cycle. A rooted tree is a tree such that there exists a unique vertex, called the root, which has no parent vertex. In a tree, each vertex, different from the root, has exactly one parent vertex. In the following, a rooted tree is simply called a tree.

In this paper, we consider rooted unordered trees, meaning that the order among the sibling vertices of any given vertex is not significant.

The degree deg of a tree is the maximum number of children of a vertex of T . The notation |T | represents the number of T vertices.

The height h(x) of a vertex x in a DAG is the length of the longest path from x to a leaf. The height h(D) of a DAG D is the height of its root vertex, and its width, denoted l(D), is the maximum number of vertices of the same height in all the DAG.

A subtree is a particular connected subgraph of a tree. Let x be a vertex of a tree T = (V, E), T [x] is a complete subtree if it is the maximal subtree rooted in x with:

T [x] = (V [x], E[x]
), where V [x] = {y ∈ V /x is the ancestor of y} and

E[x] = {(u, v) ∈ E/u ∈ V [x], v ∈ V [x]}.
In the sequel, we will only consider complete subtrees and use the simpler term "subtree".

Let us consider two trees,

T 1 = (V 1 , E 1 ) and T 2 = (V 2 , E 2 ). A bijection φ from V 1 to V 2 is a tree isomorphism if for each (x, y) ∈ E 1 , (φ(x), φ(y)) ∈ E 2 .
If there exists an isomorphism between T 1 and T 2 , the two structures are thus identical up to a relabeling of their components. In this case we say that T 1 is isomorphic to T 2 .

A multi-set is a set of typed elements such that the number of elements of each type is known. It is defined as a set of pairs M = {(k, n k )} k where k varies over the element types and n k is the number of occurrences of type k in the set.

Tree reduction

Definition

We consider here the principle of tree reduction as was defined by [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF]. The aim of the reduction is to transform a rooted un- To obtain a graph equivalent to the tree T , additional information is added in the DAG edges, as edges weights. For any edge (c i , c j ), its weight In the following sections we will consider DAGs corresponding to reduction graphs, i.e. DAGs whose edges are augmented by weights. D denotes the class of all DAGs.

n(c i , c j ) is

Self-nested trees

Let us define the set of self-nested trees, as the trees in which all subtrees with identical height are isomorphic. [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF] showed that self-nested-trees have the following characterizing properties:

• any two subtrees are either isomorphic or included one into another (one is a subtree of the other).

• their reduction R(T ) is a linear DAG.

The reduction of the tree in Fig. 2.b.i is the linear DAG depicted in Fig. 2.b.ii.

By contrast, the tree of Fig. 2.a.i is not self-nested as its reduction is a non linear DAG (Fig. 2.a.ii).

Based on these definitions, the degree of self-nestedness of any tree T can be quantified by computing the distance between T and the smallest selfnested tree (noted N EST ) that embeds it. This distance is null if the tree is in the class of self-nested tree and augments as the tree contains increasingly self-nested structures. [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF] showed that this distance and the corresponding N EST of a tree T can be computed in polynomial time by a DAG linearization algorithm.

An important property of both the reduction graph and the N EST of a tree is that they preserve the height of nodes in the original tree. This means that vertices in either the exact (the reduction graph) or the approximated ones (the N EST ) corresponding to vertices in the original tree have exactly the same height. In Fig. 2.b for example, the green node in the reduction graph has a height of 3 (Fig. 2.b.ii), corresponding exactly to the height of the subtrees that it refers to in the original tree rooted also in green vertices (Fig. 2.b.i). The same property is true for all the other colors. As a consequence, a tree of height N will necessarily have a compression with a number of vertices greater than N . In many cases, when N is of the same order of magnitude as the tree size |T |. This is clearly a limitation of the previous contraction procedures.

We are therefore lead to study how to compress trees in height as well as in width. For this, we need to relax the definition of isomorphism between trees to capture the notion of repetition of tree patterns independently of their height.

4. Quasi-periodic paths in a reduction graph

Intuitive idea of height reduction

Intuitively, a tree can be reduced in height if there are subtrees repeated in some way along some paths from the root to the leaves. But how to define exactly such repetitions?

Consider for instance tree of Fig. 3.a. We see that the structure including the subtrees originating at vertex B are repeated at different heights of the original tree. The series of strictly nested subtrees

A(3) ⊂ A(2) ⊂ A(1) ⊂
A(0) are similar, but not exactly isomorphic. Actually, if we discard the righthand side subtree of A(i), i = 0, .., 3 (illustrated in Fig. 3.b), on the picture, we remark that the remaining trees are indeed isomorphic. We shall say that these trees are quasi-isomorphic, i.e. isomorphic for almost all of their immediate subtrees except one, and shall show that nested quasi-isomorphic

Vertex and edge signatures

Definition 1 (Vertices signature) Let R(T ) = (V, E) a reduction graph.

We associate with V the matrix σ ∈ N |V |×|V | of vertex signature, where each element σ xy is defined as:

σ xy = n(x, y) ∀((x, y), n(x, y)) ∈ E 0 else where
In the matrix σ, the line associated with vertex x defines the signature σ x of

x. It represents the links of x with all its children vertices, and then describes the subtree T

[x]. Example 1 Let R(T 1 ) = (V, E) the reduction graph of Fig.2.b.
ii, where:

V = {A, B, C, D, E} and
E = {((A, B), 1), ((A, C), 2), ((A, D), 1), ((B, C), 1), ((B, E), 1), ((C, D), 1), ((C, E), 1), ((D, E), 1)}
The associated vertex signature matrix is given as follow:

A B C D E σ A = [ 0 1 2 1 0 ] σ B = [ 0 0 1 0 1 ] σ C = [ 0 0 0 1 1 ] σ D = [ 0 0 0 0 1 ] σ E = [ 0 0 0 0 0 ] Property 1 ∀x, y ∈ V , σ x = σ y .
Definition 2 (Atomic path) We define an atomic path in a reduction graph as a path of length 1.

x, y denotes the atomic path from a vertex x to a vertex y.

Definition 3 Given a vertices signature matrix σ, and given x, y two vertices where σ xy = 0. We define the vector σ x,y as the vector σ x with σ xy is set to 0.

The vector σ x,y describes the constitution of the subtree associated with the vertex x up to the subtree structure of its child y. This leads to the following property.

Property 2 σ x,y = σ x ,y ⇔ x is isomorphic to x up to a child node y in x and a child node y in x .

σ a 1 = σ a 2 σ xa 1 = σ x a 2 = 1 σ b 1 = σ b 2 σ xb 1 = σ x b 2 = 1        Def.3 ⇐⇒ σ x,y = σ x ,y
Then X and X are quasi-isomorphic sub-trees regarding their respective descendants Y and Y . Example 3 The edges signatures associated with the graph R(T 1 ) of Example 1 are given as follow:

σ A = 0 1 2 1 0 , σ A,B = 0 0 2 1 0 and σ AB = 1 then: σ A|B = [ 0 0 2 1 0 1 ] likewise σ A|C = [ 0 1 0 1 0 2 ] σ A|D = [ 0 1 2 0 0 1 ] σ B|C = [ 0 0 0 0 1 1 ] σ B|E = [ 0 0 1 0 0 1 ] σ C|D = [ 0 0 0 0 1 1 ] σ C|E = [ 0 0 0 1 0 1 ] σ D|E = [ 0 0 0 0 0 1 ]
The edges signatures allow us to study the quasi-isomorphism relation in a detailed and formal way on the basis of tree reduction graphs. Property 3 (Fundamental property) Let e, f be two atomic paths starting from x and let e , f be two atomic paths starting from x , then

((e ∼ = e ) ∧ (f ∼ = f )) ⇒ ((f = e) ∧ (f = e ))
In other terms, at most one pair of quasi-isomorphic atomic paths can start from a pair of vertices x and x .

Quasi-isomorphism of paths

Let's consider two paths P and Q, where P = {e 1 , ..., e n }, and

Q = {f 1 , ..., f m }. Definition 6 (quasi-isomorphic paths) We say that P is quasi-isomor- phic to Q (noted P ∼ = Q) if and only if n = m and e i ∼ = f i (1 i n).
In other words, two paths are quasi-isomorphic if and only if their atomic paths are quasi-isomorphic when compared piecewise in the paths order. Notation: A path P = { x 1 , x 2 , ..., x n-1 , x n } can be denoted as: P =

x 1 P x n or P = x 1 P 1 x k P 2 x n and so on.

If P = x 1 P 1 x i P i x i+1 P n x n and |P i | = 1 we can note P = x 1 P 1 x i x i+1 P n x n .

Quasi-periodic path

A quasi-periodic path is a path decomposable in strictly smaller sub-paths which are all quasi-isomorphic with each other, and which are not themselves strictly decomposable. x ≺ y. We say that xP y is a quasi-periodic path if there exist paths P 1 , ..., P n (P i = λ) and (n 2) for which:

• P = P 1 ∪ ... ∪ P n • P 1 ∼ = ... ∼ = P n • ∀i n, P i is not a quasi-periodic path.
P is called QP P (x, y), and the sequence P 1 , ..., P n the normal decomposition of P .

Property 4 The normal decomposition of P is unique.

Example 6 A. From the graph R(T 1 ) of Fig. 2.b, the path P = P 1 ∪ P 2 with By definition, each QP P is a set of path chunks which are:

P 1 = B, C , P 2 = C, D is a QP P . B. Moreover, in R(T 2 ) of
• embedded in the same global path,

• all quasi-isomorphic with each other,

• pairwise connected.

Therefore a QP P can be considered as a periodic path made by the repetition of quasi-isomorphic paths forming its normal decomposition. This is illustrated in Fig. 5.b that shows a QP P whose normal decomposition is made up two subsequences. One sequence is indicated by red, blue and yellow.

Let us consider quasi-periodic paths P and Q with identical extremities.

Property 5 Let xP y = QP P (x, y) and xQy = QP P (x, y) then P = Q.

The property shows that these two paths coincide.

Property 6 Every subsequence of a normal decomposition of a QP P is a normal decomposition of a smaller QP P .

Let P 1 , ..., P n be a normal decomposition of a QP P P , the path corresponding to a subsequence P i , ..., P i+k (i < n, 1 < k < n -i) of the normal decomposition of P is itself a QP P .

Maximal Quasi-periodic path

Definition 8 (Maximal quasi-periodic path M QP P ) A maximal quasi-periodic path (noted M QP P ) is a QP P maximum for path inclusion.

Let P 1 , ..., P n be the normal decomposition of a M QP P P , then there is no QP P Q (P ⊂ Q) such that P 1 , ..., P n is a part of the normal decomposition of Q.

Let us denote by M QP P (R(T )) the set of all the M QP P s of a reduction graph R(T ) = (V, E).

Property 7 The set M QP P (R(T )) can be computed in time O(|E| 2 h(R(T )) l(R(T ))).

Relative positions of maximal quasi-periodic paths in a reduction graph

Let us now study the relative positions of two M QP P s in a reduction graph. As for any two paths in a reduction graph, two M QP P s can either intersect or not, intersecting M QP P s can either be nested or not. C. In the reduction graph R(T 5 ) of Fig. 6.c:

P 1 = { A, B , B, C , C, D } ∪ { D, E , E, F , F, I } P 2 = { A, B , B, C } P 3 = { D, E , E, F }
3 M QP P s with the nesting relations: P 2 ⊂ P 1 , P 3 ⊂ P 1 .

Let us describe the general structure of a nested M QP P P 1 . Let us call P 1 1 , ..., P 1 N the normal decomposition of P 1 . The motifs P 1 n are all quasiisomorphic with each other and their union entirely covers P 1 . Therefore, to study the structure of P 1 one only needs to study the structure of one of them, say P 1 l . Now let us consider the list of M QP P s included in P 1 l . This list may be empty if P 1 is not nested and the M QP P is said to be simple.

Otherwise, P 1 l contains itself a list of M QP P s denoted P can be decomposed into a list of quasi-isomorphic motifs denoted P 1 j l m for m = 1..M , and so on (see Fig. 7). These series of decomposition forms a tree structure called the M QP P tree of P 1 . Interestingly, this tree contains many identical subtrees as indicated by the following property.

Property 8 ∀m = m , P 1 j...k l...m ∼ = P 1 j...k l...m .

Definition 9 (Maximally Nested M QP P ) A maximally nested M QP P is a M QP P that is not strictly contained within a strictly greater M QP P .

Definition 10 (Normal decomposition of a DAG) The normal decomposition of a DAG D is the set N of all its maximally nested M QP P s.

Therefore, the normal decomposition of a DAG contains only top level nested M QP P s which are either simple or decomposable in to finer M QP P s.

In general, the relative position of two M QP P s must respect constraints as indicated by the following property.

Let P = {e 1 , ..., e n } be a path. If e n = x, y we say that P terminates through x.

Property 9 Let P and P be two intersecting M QP P s:

1. If P and P starts from the same vertex then P ⊂ P or P ⊂ P .

2. If P and P are not nested then either:

(a) at least one of the M QP P s terminates through the intersection point,

Height compression of a reduction graph

Each M QP P can be decomposed in a unique manner as a sequence of quasi-isomorphic paths (normal decomposition) P 1 , ..., P n (as in Fig. 9.a.ii).

We will make use of this repeated pattern to compress these M QP P s. This will be made by allowing introduction of loops in the original DAGs, as in Fig. 9.a.iii. Let us introduce the notion of DAG with return edges.

DAGs with Return Edges

A DAG with return edges is constructed from a DAG by adding to it edges that induce oriented cycles, Fig. 9.b.

Definition 11 (DAG with return edges) Let D = (V, E) be a DAG.

We consider a set E of edges in V × V such that:

• ∀(x, y) ∈ E , y ≺ x in D.
• As for any edge of D, we associate a weight n(x, y) with each edge (x, y) ∈ E .

• In addition we associate with each edge (x, y) ∈ E one of the children z of x if any, such that n(x, y) = n(x, z), z is called the exit vertex of the cycle induced by the return edge (x, y) and denoted ex(x, y). The M QP P s correspond to maximally repeated patterns on the paths of a DAG. It is thus possible to compress the DAG in height by compressing these repeated motifs. This will lead to construct DAGs with return edges representing the compressed trees. As we will show, the loop in these graphs can only be either nested or disjoint. This leads to introduce a special kind of DAGs with return edges, namely DAGs with nested returns.

DAG with nested returns

Definition 12 (DAG with nested returns) We define a DAG with nested returns as a DAG with return edges in which any two elementary cycles B 1 and B 2 (with respective vertex sets

V 1 and V 2 ) are either nested (V 1 ∩ V 2 = V 1 or V 1 ∩ V 2 = V 2 ) or disjoint (V 1 ∩ V 2 = ∅).
We U is the maximal multiplicity of all cycles of D .

In the resulting DAG of Fig. 12.d, we observe that the obtained expanded path forms a M QP P .

Compression of a DAG as a DAG with nested returns

We have just seen that DAGs with nested returns can be unfolded into

DAGs by expending the cycles. We now consider the reciprocal question of compressing a DAG as a DAG with nested returns. To this end we will first analyze how M QP P s can be folded and then apply the resulting algorithm to a maximal set of M QP P s in the original DAG.

Compression of a M QP P

Let P be a M QP P in a DAG D and P 1 , ..., P n be its normal decomposition. The idea is to replace the sequence P 1 , ..., P n by a loop over P 1 repeated n times. In practice the original DAG must be edited in the following way.

General compression algorithm of a M QP P : Let D = (V, E, E ) be a DAG of D , and let P = P 1 ∪ ... ∪ P n the M QP P (x, y) with

P i = x i,1 P i x i,m
(1 i n, m 2), x = x 1,1 and y = x n,m , as represented in Fig. 13.a. We denote by B p the cycle obtained from the compression of P , and the resulting DAG with nested returns by D /P . Then D /P is computed in the following steps:

1. Creation of a return edge, Fig. 13.b:

• add a return edge to E from x 1,m-1 to x ,

• this edge has a weight ω = n(x i,m-1 , x i,m ),

• this edge is also augmented with the information that when the loop ends, scanning should resume on the exit vertex y of x n,m-1 , labeled by χ.

2. Redirection of entering edges of the M QP P , Fig. 13.c:

• Replace each entering edge (z, x i,j ) of the M QP P by the equivalent entering edge in the cycle B P , i.e. edge (z, x 1,j ),

• this edge has a weight n(z, x i,j ),

• its multiplicity list corresponds to the multiplicity list of the edge (z, x i,j ) augmented by the multiplicity of the loop B P for this edge, that is n -i.

3. Suppression of the M QP P repeated patterns, Fig. 13.d:

• Remove edges which belong to the paths P 2 , ..., P n ,

• the last edge of P 1 (x 1,m-1 , x 1,m ) is redirected on the exit vertex χ. It is thus replaced by the edge (x 1,m-1 , χ) whose weight is also ω,

• Edit the sets V , E and E . Note on this example that due to the M QP P compression several edges can appear between two vertices.

Gain of M QP P compression

Let us consider a M QP P P in D ∈D , with P = P 1 ∪ ... ∪ P n , and

P i = x i,1 P i x i,m (1 i n, m 2
|V P | = |V P | -|V P 1 |, |E P | = n i=2 m-1 j=1 deg + (x i,j ) -1.
Let α be the size of the computational representation of a vertex in V , and let β be the size of the computational representation of an edge in E.

Definition 15 (compression gain of a MQPP) We define the P compression gain, noted g(P ), by g(P ) = α|V P | + β|E P |.

Property 14 (compression gain of two MQPPs) Given two paths P, P ∈ M QP P (D). If P and P are either disjoint or nested, then the gain g({P, P }) = g(P ) + g(P ).

Let P and P two M QP P s in a DAG D. D /P/P denotes the DAG with nested returns obtained by successive compressions of P and P , and the gain g(D /P/P ) = g({P, P }).

Selection of a maximal set of non intersecting M QP P s with maximal compression gain

If two M QP P s are intersecting but no nested then the compression of one of them may impair or prevent the compression of the other. Therefore as the compression of the two M QP P s is mutually exclusive, the compression of the DAG will depend on the choice of the compression of either of them.

We say that the DAG compression is ambiguous.

Given a DAG D, let M be a subset of M QP P (D).

Definition 16 M is unambiguous for compression if ∀P, P ∈ M , P and P are either nested or disjoint.

In other terms, M is unambiguous for compression if all its M QP P s can be compressed independently. Therefore, if M is ambiguous for compression one needs to make choices to eliminate ambiguity in compression while maximizing the compression gain.

For this, consider the equivalence relation ∧ on M such that:

P ∧ P ⇔ P and P are neither disjoint or nested.

Let {M i } i be the set of equivalence classes of ∧ (of Fig.

G M i = (V M i , E M i ) such that each vertex of V M i represents a M QP P
of M i , and there is an edge between two vertices P and P of V M i if P and P are either disjoint or nested. With this graph definition we can characterize sets of M QP P s unambiguous for compression:

Property 15 M i is unambiguous for compression if and only if

G M i is a complete graph.
Therefore, our problem is reduced to finding in the graph G M i a clique G M i (i.e. a complete subgraph of G M i ) with maximal gain. This optimization problem is known to be NP-complete [START_REF] Feige | Approximating clique is almost np-complete[END_REF]), and several approaches have been developed to solve it [START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF]; [START_REF] Bomze | The maximum clique problem[END_REF][START_REF] Feige | Approximating maximum clique by removing subgraphs[END_REF]). Here we use the TABU algorithm [START_REF] Gendreau | Solving the maximum clique problem using a tabu search approach[END_REF]), as described in section 15 of the Online supplementary material. Given a class M i the algorithm returns a maximal subset M i unambiguous for compression with maximal gain. The unambiguous normal decomposition of D, N * , is the set of all its maximally nested M QP P s unambiguous for compression, i.e. the set

N * = N (D) ∩ M QP P (D).
Section 16 of the Online supplementary material provides examples of compressed graphs obtained from graphs of Fig. 6.

DAG compression evaluation:

Given a DAG D = (V, E). Let R be the corresponding DAG with nested returns with gain g(R).

Definition 18 (Compression factor of a DAG with nested returns)

The compression factor of a DAG with nested returns R is defined as:

f (R) = g(R) α|V | + β|E|
where α, β are the size of the computational representations of respectively a vertex in V and of an edge in E. This measure represents the relative gain in size of the compressed graph compared to the original DAG.

Algorithm for the height compression of a finite tree

Based on the definition of M QP P s and on their compressibility property, it is possible to design an optimization algorithm to maximally compress a DAG in height.

Property 16 Let D = (V, E) be a DAG, the compression in height, denoted

H(D), can be computed in time O(|E| 2 h(D) l(D)).
The main steps of the computation of H(D) are described as follows:

1. Compute the set of vertex signatures and then the set of edge signatures of D (see section 4.2).

Application to the compression of plant structures

Most plants have a modular branching structure made up of the repetition of basic modules such as leaves, stem portion between two nodes, shoots, etc. [START_REF] Bell | Plant form: An illustrated guide to flowering plants[END_REF], [START_REF] Godin | A multiscale model of plant topological structures[END_REF]). These highly repetitive structures are therefore well suited to assess our compression schemes. In this section, we will investigate how different types of plant structures can give rise to different types of compression in height.

Dichotomic Structures

Plants may build up dichotomic branching structures due to either the where α, β are the size of the computational representations of respectively a vertex and of an edge in a DAG D, and α , β are the size of the computational representations of respectively a vertex and of an edge in H(D). These notations will be used all through this section.

Structures with multi-scale periodicity

Fish bone-like structures present a typical example of structure of multiscale periodicity. They can be noticed, for example, in axial trees whose growth is monopodial (i.e. trees having a growing main stem that keeps on growing while producing lateral branches). Such a structure is thus composed of a principal axis on which several elements are repeated (branches, leaves, fruits,...). The Date Palm illustrates the wide variety of plants or plant parts showing a fish bone-like structure (Fig.17 where 2n is the number of leaves on each lateral branch, and m the number of all lateral branches. More generally, a fish bone-like structure can be compressed in height both on the lateral branches (j 1 , ..., j m ) and on the main axis (i 1 , ...i n ), Note the two cycles of H(D) express respectively the repetition of motifs on lateral branches and the repetition of motifs on the main axis.

Structures with nested periodicity

The structures introduced above correspond to structures with a multiscale periodicity, which is characterized by two levels of repeated patterns. In more complex multi-scale structures there may be several types of repeated

f (H(D)) = 1 - 7α +11β α(k(n+m)+3)+2β(k(n+m)+2) .
Note that the nested returns in H(D) express the nested periodicity, where the outer loop corresponds to the repeated sequence (leaves, fruits), and the inner loops represent respectively the leaves and the fruits repetitions.

Self-similar structures

Self-similarity is a conspicuous feature of many plants [START_REF] Prusinkiewicz | Selfsimilarity in plants : integrating mathematical and biological perspectives[END_REF]), that can be exploited to compress the plant structures. Fern provides a typical example of such a self-similar structure (Fig. 18.b.i). A model of this fern can be constructed in L-system [START_REF] Prusinkiewicz | The artificial life of plants[END_REF] For n = 30 the reduction factor is close to 93% showing the remarkable height compressibility of self-similar structures.

A general model of self-similar branching structures has been proposed

by [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF] One can notice that the monopodial template plants (T 0 , T 1 and T 2 )

are weakly height compressible structures, whereas the sympodial tree T 3 is remarkably height compressible. However as soon as noise is introduced in this tree, its height compressibility becomes weaker.

Overall, the height compressibility of the four families is low for small noise factor (probability 0.6). Nevertheless for increasing noise (probability < 0.6) height compressibility increases as the tree tends to become a linear structure.

Conclusion

This paper has considered the problem of height reduction from tree structures. This study was designed to complement the work previously done in the context of lossless compression of unordered trees [START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF]), where the trees were compressed in width and not in height. Using the property that some tree structures exhibit height regularities, we proposed to represent differently these special structures, characterized by a height repeated pattern. These repetitions are associated with quasiisomorphic sub-trees which are regularly organized along one main branch.

Starting from a reduction graph of a given tree, the height reduction consists of searching of all collections of regularly height repeated patterns. Each repeated pattern is replaced by a unique instance of this pattern augmented with a loop in the compressed tree which is called a Reduction Graph with Nested Returns. The efficiency of the compression algorithm is quantified by a compression factor reflecting the ratio between the size of the DAG with nested returns and the size of the initial DAG.

The method was then illustrated on different type of plant structures and showed that in many cases height compression can add a significant compression factor to the width compression, in particular on self-similar plants.

Figure 1 :

 1 Figure 1: Basic example of width and height tree reduction

  ordered tree T into a directed acyclic graph noted D = (V, E). Each vertex of the D corresponds to an equivalence class of T subtrees. All subtrees belonging to the same class are isomorphic. All DAG vertices (classes) connected by edges are ordered by the ancestor partial order relation, noted , between the subtrees which they represent. In other words, let A and B two DAG vertices where A B, then the tree of class B is isomorphic to a subtree of

Figure 2 :

 2 Figure 2: a.i. a tree T , and ii. the associated reduction graph R(T ), b.i. the tree T 1 , and ii. its reduction graph R(T 1 )

  defined by the number of occurrences of the subtree of class c j in this of class c i . The obtained graph is called the reduction graph of T , and noted by R(T ) = (V, E), where E is a multi-set whose elements have the form ((c i , c j ), n(c i , c j )). The construction of the reduction graph of a tree can be carried out in time O(|T | 2 deg(T ) log deg(T ))[START_REF] Godin | Quantifying the degree of self-nestedness of trees: Application to the structural analysis of plants[END_REF]).

Fig. 2 .

 2 Fig.2.a shows an example of a tree and its reduction graph.

Figure 3

 3 Figure 3: a. a height regular tree T , b. the repeated pattern of T , c. Intuitive elimination of T pattern repetitions, d. the DAG R(T ), e. the subDAG representing the regular repeated pattern, f. The intuitive height reduced DAG of R(T )

Property 2

 2 Fig.4.a and 4.c, and associated with the vertices x and x in the corresponding reduction graphs of Fig.4.b and 4.d. Note that the subtrees rooted in Y and Y are distinct. We obtain:

Figure 4

 4 Figure 4: a. and c. quasi-isomorphic trees T [X] and T [X ], b. and d. the corresponding reduction graphs R(T [X]) and R(T [X ]). Black vertices display their differences

  4.3. Quasi-isomorphism of paths 4.3.1. Quasi-isomorphism of atomic paths Definition 5 (Quasi-isomorphic atomic paths) In a reduction graph, given two distinct atomic paths x, y , x , y . We say that x, y and x , y are quasi-isomorphic, noted x, y ∼ = x , y , if and only if σ x|y = σ x |y . Example 4 A. From Example 2: σ x,y = σ x ,y σ xy = σ x y = 1 Def.4 ⇐⇒ σ x|y = σ x |y Def.5 ⇐⇒ x, y ∼ = x , y B. Given the set of edges signature computed in Example 3. There exist in this set, two equal edges signatures: σ B|C = σ C|D , which induce that B, C ∼ = C, D . This appears clearly in Fig.2.b.i in which the subtree associated with B except its child C, and the subtree associated with C except its child D are isomorphic.

  Example 5 A. In the DAG R(T 1 ) (Fig.2.b) they are two quasi-isomorphic paths: P = B, C and P = C, D from σ B|C = σ C|D . B. In the DAG R(T 2 ) (Fig.5.a) they are two quasi-isomorphic paths: P ∼ = P with P = { B, E , E, I }, P = { C, F , F, H } from σ B|E = σ C|F = [000100000001], and σ E|I = σ F |H = [000000100001].

Figure 5

 5 Figure 5: a.i. A tree T 2 , ii. its reduction R(T 2 ).We surround by dashed lines the two QIP s P = { B, E , E, I } and P = { C, F , F, H }, b. Illustration of QP P in a pattern of a DAG where the same color is used for all quasi-isomorphic atomic paths

  Fig.5.a.ii, although the paths P and P are two quasi-isomorphic paths, they do not form a QP P since they are not consecutive.

Figure 6

 6 Figure 6: a. Tree T 3 and its reduction R(T 3 ) with two intersecting M QP P s. b. Tree T 4 and its reduction R(T 4 ) with two disjoint M QP P s. c. Tree T 5 and its reduction R(T 5 ) with a set of nested M QP P s

Figure 7 :

 7 Figure 7: Indexing the component of a nested M QP P . Each motif is composed of a series of M QP P s and each M QP P is composed of a series of motifs.

Figure 8 :

 8 Figure 8: a. Patterns of relative positions of two intersecting M QP P s, b. Patterns of impossible situations of two intersecting M QP P s. See text for detail explanation

Figure 9 :

 9 Figure 9: a.i. A height repeated branch, ii. the corresponding M QP P = P 1 ∪ ... ∪ P n in the associated DAG , iii. the equivalent height reduced DAG including a return edge and a returns number (n -1), b.i. a DAG, ii. the original DAG augmented with return edges (dashed edges), the result is a DAG with return edges

  The triplet D = (V, E, E ) verifying these conditions is called DAG with return edges, where E is the set of return edges of D . D ↑ denotes the class of all DAGs with return edges. Property 10 Let B = (e 1 , ..., e n ) an elementary cycle in a DAG with return edges D = (V, E, E ). There is a unique return edge e k ∈ E in B denoted re(B). We called the path {e k+1 , ..., e n , e 1 , ..., e k-1 } the principal path of B denoted pp(B), and the vertex ex(e k ) = z the exit vertex of the cycle B, denoted ex(B).Furthermore, we say that x ∈ pp(B), for each vertex x in pp(B). In the DAG with return edges of Fig.10.e, for the elementary cycle B 2 = ((x, y), (y, z), (z, w), (w, x)): re(B) = (w, x), pp(B) = {(x, y), (y, z), (z, w)} and ex(B) = e.

  denote the class of all DAGs with nested returns by D . Note that D ⊂D ↑ . Example 9 Fig.11.a shows examples of patterns of vertices of DAGs ∈D and in Fig.11.b DAGs / ∈D .

Figure 10 :

 10 Figure 10: a. Cycle B 1 in a pattern of a DAG with returns D, b. The multiplicities of the set of entering edges in B 1 (Edges in bold ), c. Cycle B 2 in the same graph D , d. The multiplicities of the set of entering edges in B 2 , e. the DAG D with the nested cycles B 1 and B 2 , f. the merged sets of multiplicities of entering edges in cycles B 1 and B 2

Figure 11 :

 11 Figure 11: a. Patterns of valid DAGs in D , b. Patterns of DAGs not in D , (Dashed edges represent return edges)

Figure 13

 13 Figure 13: a. Formal pattern of a M QP P P = P 1 ∪ ... ∪ P n , b. creation of the return edge of P , c. redirection of an entering edge of P into its pattern in P 1 , d. Suppression of the repeated patterns P 2 , ..., P n

  ). Let us denote |V P | and |E P | the number of vertices and respectively the number of edges removed from P compression. Formally

  15.a). In a class M i M QP P 's are pairwise intersecting with M QP P 's of the same class. Note that classes themselves are disjoint. Our problem is thus to select a subset of M QP P s in M i such that this subset is unambiguous for compression, and the total gain of these M QP P 's is maximal, Fig 15.b.

Figure 15

 15 Figure 15: a. Pattern of a DAG with M 1 , M 2 , M 3 the equivalence classes of ∧ , i.e.maximal M QP P sets ambiguous for compression (paths of the same color belongs to the same set M i ), b. the corresponding unambiguous subsets M 1 , M 2 , M 3

  For a DAG D, let M = ∪ i M i and M = ∪ i M i , and let us denote by M QP P (D) the maximal set of M QP P s of D unambiguous for compression, with: M QP P (D) = M QP P (D) \ (M \ M ) Where \ denotes the sets difference. Let N (D) be the normal decomposition of a DAG D, M QP P (D) allows us to eliminate the compression ambiguity on the full DAG D. Definition 17 (Unambiguous normal decomposition of a DAG)

2 .

 2 Given the set of edge signatures compute the set M QP P (D) (see section 4.3). 3. From M QP P (D) determine the sets M then M , and deduce M QP P (D) (see section 5.3.3). 4. Iterative computation of H(D): (a) Initialization: Let H = (V, E, E ) be the DAG with nested returns for which the vertex and the edge set are equal to the vertex and the edge set of D, and the set of return edges is an empty set. (b) Repeat i. compute N * (H) = {P 1 , ..., P n } the unambiguous normal decomposition of H ii. H = H /P 1 /.../Pn until N * (H) = ∅, 5. Return the DAG with nested returns H(D) = H of compression factor f (H(D)) = g(H(D)) α|V |+β|E| . Finally, if R(T ) denotes the reduction of the tree T in width, if H(D) denotes the compression of a DAG D in height then the compression R (T ) of the tree T in width and height can be computed in time O(|T | 2 deg(T ) h(T )) such as: R (T ) = H • R(T ).

  subdivision of their apices or to sympodial branching (the main apex stop to grow and two lateral apices resume the growth). Many plants show such a type of organization including one of the initial form of the earth's plant life, that is the Cooksonia Caledonica plant (Boyce (2008)) (Fig.16.a.i), and the Horneophyton lignieri[START_REF] Eggert | The sporangium of horneophyton lignieri (rhyniophytina)[END_REF]) (Fig.16.a.ii).

Figure 16 :

 16 Figure 16: a. Examples of vegetal dichotomic structures: i. The Cooksonia Caledonica shape (Tandart et al. (2014)), ii. Horneophyton tree (Tandart et al. (2014)), b.i. a binary tree graph T , ii. the DAG D of its width reduction, iii. its height reduction graph H(D)

  .a.i). It can be abstracted as the graph T represented in Fig.17

  .a.ii, where the main axis represents the trunk of the palm tree and the lateral branches represents the composed leaves. This structure can be compressed in width leading to the graph D of Fig.17

  .a.iii that can itself be further compressed in height as H(D) (Fig.17

  .a.iv) with height compression factor of

Figure 17 :

 17 Figure 17: a.i. A model of the date palm (Phoenix Dactylifera) (Rhouma (1994)) and its lateral leaf modeled using the L-studio/Vlab (Prusinkiewicz et al. (2000); Abelson and DiSessa (1981)), ii. graphical representation T of the date palm. iii. the corresponding DAG D, iv. its height reduced graph H(D), b.i. Pattern of a fish bone-like structure T , ii. its width reduction DAG D, iii. its height reduced DAG H(D)

Fig. 17

 17 Fig.17.b.i. The width reduction of T produces the DAG D (Fig.17.b.ii). Then the height reduction H(D) of D (Fig.17.b.iii) is computed in time O((n + m) 3 ) with a height compression factor f (H(D)) = 1 -

Figure 18

 18 Figure 18: a.i. Callistemon branch (Rosser (2014); Nicholson (2014)), ii. Pattern of the corresponding DAG D, iii. its height reduced DAG H(D). Vertex in green represents a tree leaf, and pink vertex a fruit, b.i. A real fern of Filicopsida Class in the Pteridophyta division (Smith et al. (2006); Esculier and Ferreol (2014)), ii. Fractal fern illustrated using the OpenAlea Lab environment (Pradal et al. (2007)), iii. the associated DAG D, iv. its height reduced DAG H(D)

  )using a unique production rule (see section 17 of the Online supplementary material)-as represented in Fig.18.b.ii. The width reduction of a fern model of height n produces the DAG of Fig.18.b.iii, and the height reduction of D produces H(D) (Fig.18.b.iv) in time O(n 3 ), with a height reduction factor f (H(D)) = 1 -3α +3β α(n+1)+βn .

  , called self-nested trees. To study and assess the quality of width compression algorithm the authors defined a database of self-nested branching structures made up by four families of purely selfnested trees (Fig.19.a and .b) together with versions of this trees altered with different levels of noise, Fig.19.c. In each family M i (i = 0..3), starting from a self-nested template plant T i , several noisy versions were created by varying the lateral branching probability (Fig.19.c). Width and height compression were then applied on each tree T i and all there noisy versions. Fig.20.a illustrates the width reduction graphs of some specimens of the M 3 family, and for which the height compression provides the graphs of Fig.20.b. For the four families, the obtained height compression factors depending on the branching probability (for α and β fixed to one unit) is shown in Fig.21.

Figure 19 :

 19 Figure 19: a. (i) The differentiation graph of a non-branching plant structure. (ii) The resulting axis structure, where component colors correspond to the differentiation graph states in which these components were created. The numbers attached to each loop indicate the number of steps a meristem stays in the corresponding state. (iii) Differentiation graphs used for the definition of the theoretical plants T i (i = 0..3). Solid arrows correspond to possible transitions of the apical meristem states. Dashed arrows correspond to possible transitions from the apical meristem state to the axillary meristem states. b. the self-nested template plants T i (i = 0..3), c. the noisy versions of the template plant T 1 with probability 0.8, 0.6, 0.4 and 0.0

Acknowledgments

The authors are grateful to the University Djillali Liabes of Sidi-Bel-Abbes (Algeria) and to the INRIA-CIRAD-INRA Virtual Plants projectteam of Montpellier (France) who funded this research. Bibliography Abelson, H., DiSessa, A., nov 1981. Turtle geometry: The computer as a medium for exploring mathematics. MIT Press, Cambridge, MA 39 (11). Arber, A., 1950. Natural philosophy of plant form. University Press, Cambridge, 210-217. Barnsley, M. F., 1988. Fractals Everywhere. Academic Press, Dublin. (2nd Edition, Morgan Kaufmann 1993; 3rd Edition, Dover Publications, 2012). Barnsley, M. F., 2006. SuperFractals. Cambridge University Press.

From Fig. 10.b, µ B 1 for (a, x) is 4, while it is 6 for edge (b, y).

The intuitive idea is to define on each edge entering a loop the number of times this loop must be scanned, and these is the multiplicity of the loop for this edge, In the DAG with nested returns of Fig. 10.e there is two elementary cycles

Our aim is to show that DAGs with nested returns are in general compressed versions of DAGs, where the cycles can be unfolded to construct • unfolding its return edge by the repetition of the principal path of B 1 µ max times. Let P 1 , ..., P µmax+1 be the obtained repeated patterns with P 1 = pp(B 1 ).


domain: sdv math spi info.info-au

text:
S Nilusmas

M Mercat

T Perrot

Suzanne Touzeau

V Calcagno

C Djian-Caporalino

P Castagnone

Ludovic Mailleret

C Djian Caporalino

P Castagnone-Sereno

A multi

Keywords: epidemiology, nematode, resistance

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Root-knot nematodes are present in most soils worldwide. They can infect more than 5500 plant species [START_REF] Goodey | The nematode parasites of plants catalogued under their hosts[END_REF] and cause considerable damage to crops. Controlling these parasites has long relied on chemical treatments. Since 2006, many of these treatments have been removed from the market because of their environmental and sanitary impact [START_REF] Abad | Plant nematode Interaction: a sophisticated dialogue[END_REF]. This is for instance the case of methyl bromide, a preplant soil-fumigant that was banned by the European Union (MBTOC 2006;EC Directive 1107[START_REF]EC Directive[END_REF]. The fight against nematodes of genus Meloidogyne now consists in using plant cultivars bearing resistance genes. Avirulent nematodes are not able to infect such resistant plants. However, the risks of resistance being overcome by virulent nematode populations that were demonstrated in the laboratory [START_REF] Djian-Caporalino | The reproductive potential of the root-knot nematode Meloidogyne incognita is affected by selection for virulence against major resistance genes from tomato and pepper[END_REF] are more and more observed in cropping conditions [START_REF] Djian-Caporalino | Evaluation expérimentale de stratégies de déploiement de gènes de résistance pour la gestion durable des nématodes à galles[END_REF]. Resistance breaking may lead to a significant reduction of durability of resistance-based cultivars and thus compromise yield. Even though virulent nematodes are able to infect resistant and susceptible plants, they develop more slowly on the susceptible plants as the acquisition of virulence comes at the price of a fitness cost, represented by a decrease in fertility [START_REF] Djian-Caporalino | The reproductive potential of the root-knot nematode Meloidogyne incognita is affected by selection for virulence against major resistance genes from tomato and pepper[END_REF].

Setting up rotation strategies of resistant and susceptible crops should allow to increase the durability of resistance genes and limit the spread of virulent nematodes. Our aim is to explore the efficiency of such rotation strategies by a modelling approach. In this paper, we first present an epidemic model describing the infection dynamics of susceptible or resistant plants by avirulent and virulent nematodes. We then adjust it to the available experimental data. We finally use this model to determine optimal crop rotation strategies.

MATERIALS AND METHODS

Our model is based on a description of plant root infection by nematodes: the free living parasites have limited mobility in the soil; they spread and reproduce in the local plant root system. Given that the problem under consideration is essentially seasonal, we used a semi-discrete plant epidemic model to describe the within-season plant root infection dynamics, coupled to the season-to-season survival of nematodes [START_REF] Mailleret | From elaborate to compact seasonal plant epidemic models and back: is competitive exclusion in the details?[END_REF][START_REF] Fabre | Durable strategies to deploy plant resistance in agricultural landscapes[END_REF][START_REF] Fabre | Epidemiological and evolutionary management of plant resistance: optimizing the deployment of cultivar mixtures in time and space in agricultural landscapes[END_REF]. The within-season dynamics of the nematode infection of plant roots is described by a system of ordinary differential equations. When a healthy plant root H comes into contact with a free living nematode P, it becomes latently infected E as the nematode settles in the plant root. After a period 1/λ, it becomes infectious I, producing nematodes P at rate r. The infection of roots by nematodes negatively impacts root growth [START_REF] Leskovar | Root growth and root-shoot interaction in transplants and direct seeded pepper plants[END_REF], which is taken into account through function f. This function discounts the basal growth rate gx by a decreasing exponential function of the infection prevalence π=I/(H X +E+I) multiplied by a scaling factor k: f(H,E,I)=gxe -kπ .

Within-season infection dynamics

During a cropping season of length τ, either susceptible (X=S) or resistant (X=R) plants are grown. Two kinds of nematodes compete for healthy roots H X : avirulent nematodes Pa which can infect susceptible plants (ε a S =1) but are unable to infect resistant plants (ε a R = 0); and virulent nematodes Pv which can infect both susceptible and resistant plants (ε v =0.8), but reproduce less efficiently on susceptible plants because of the fitness cost w associated with the virulence. We assumed that a proportion δ of newborn avirulent nematodes mutate into virulent nematodes and considered the reverse mutation as negligible [START_REF] Castagnone-Sereno | Stable virulence against the tomato resistance gene parthenogenetic root-knot nematode Meloidogyne incognita[END_REF]. The within-season model equations read as follows (see also Fig. 1):

Ṗa =-βP a H X -ΩP a + r (1 ─ δ ) I a Ṗv =-βP v H X -ΩP v + r δ I a +r (1-w) I v Ḣ X =f ( H X , I , E)-ε a X β P a H X -ε v β P v H X Ėa =ε a βP a H X -λE a Ėv =ε v βP v H X -λE v İ a =λE a -αI a İ v =λE v -αI v
Parameter definitions, values and units are given in Table 1. The simulation of these equations were conducted with R (function ODE in package deSolve) using the Runge Kutta 4 method.

Winter survival of nematodes

Nematode densities Pa and Pv at the beginning of a given cropping season are computed as the product of nematode densities at the end of the previous cropping season multiplied by the winter survival probability φ. Other variables are reset to zero, except the number of healthy roots H at crop plantation, which is set to the initial root biomass of newly planted individuals H0.

Model adjustment

All parameters could be estimated from the literature or expert knowledge but three: the conversion factor of units of root in feeding sites (x), the infection rate (β), and impact of infection prevalence on root growth rate (k ).

We thus obtained their value by adjusting the model to experimental data on the within cropping season dynamics of susceptible tomato plants and avirulent nematodes, reported by [START_REF] Ehwaeti | Dynamics of damage to tomato by Meloidogyne incognita[END_REF]. They measured the final density of nematodes in the ground after one cropping season (Pdata) for different values of their initial density (i=1,...5), as well as the relative loss of biomass (Bdata) after 42 days (j=1) and at the end of the season, i.e. after 135 days (j=2). Each set of data is reported as the mean over five replicates, for five values of initial nematode density (Fig. 2). We computed the density of nematodes after 135 days (Pmodel) for each initial density. We assumed that we could equate the relative loss of total biomass (the data) with the relative loss of root biomass (our model), the total root biomass being the sum of healthy (H), latent (E) and infectious (I) roots. So we could also compute this variable (Bmodel) for each initial nematode density (i=1,… 5) and at both dates (j=1,2). We measured the distance between our model output and the observed data using a weighted least square metric calculated in the following way:

RSS= ∑ i =1 5 ( P model (i)-P data (i) Mean(P data ) ) 2 + ∑ j=1 2 ∑ i=1 5 ( B model (i, j)-B data (i , j) Mean(B data ( j)) )
2

The division by averages allowed accounting for heterogeneous data between nematode density and relative loss of biomass. Model adjustment was done with the optim function in R, using Nelder-Mead's method. The parameter values obtained are given in Table 1. β Infection rate 4.9 10 -3 UR -1 x day -1 (3.92 10 -3 , 5.88 10 -3 )

[*]

x Conversion factor between root mass and density of feeding sites 3.7 10 -5 UR x mg of roots

Optimal crop rotation strategies

We considered all periodic rotation strategies between resistant and susceptible crops, beginning with resistant crops, and alternating m and p seasons of resistant and susceptible plants, respectively. We denoted by mR+pS these periodic strategies. For instance, a 2R+1S (i.e. m=2 and p=1) strategy on a 10-season temporal horizon is RRSRRSRRSR. We also considered the two pure resistant-only and susceptible-only strategies that correspond to planting only one crop type along the seasons.

We quantified the performance of each strategy using an epidemiological criterion called the Area Under the Disease Progress Curve (AUDPC; [START_REF] Jeger | Analysis of disease progress as a basis for evaluating disease management practices[END_REF]) defined for one season as: ∫ 0 τ (I a (t)+ I v (t)) dt . More precisely, we used the average AUDPC calculated as the mean of the AUDPC over the n cropping seasons.

The larger the criterion, the more severe the plant infestation by nematodes. We thus defined the optimal strategy as the one minimizing the above criterion. We have shown that minimizing AUDPC amounts to maximize yield. Indeed, we found that AUDPC was negatively correlated with crop yield (not shown). We computed these optimal strategies for all temporal horizons between n=2 and n=40 cropping seasons.

To study the robustness of the strategies with respect to parameter values, we also varied the most uncertain or variable parameters according to the ranges given in Table 1. We calculated the AUDPC of all pure and periodic rotation strategies and for all 2880 parameter combinations. We then deduced the optimal strategy for each temporal horizon and each parameter set. We computed the median and the 5-95% inter-percentile over all parameter combinations for the optimal and pure strategies.

RESULTS AND DISCUSSION

Model adjustment

The loss of biomass 42 days after planting was well fitted by the model (see Figure 2), but the model overestimated the loss of biomass after 135 days. The fit of nematode populations 135 days after planting was also satisfying.

Optimal crop rotation strategies

The median and inter-percentile AUDPC for the susceptible-only strategies were constant for temporal horizons over 5 seasons (see Figure 3). In contrast, the AUDPC for the resistant-only strategies increased with the temporal horizon, which is characteristic of resistance breakdown by nematode populations.

As we could expect, the resistant-only and optimal strategies had lower AUDPC and hence performed better than the susceptible-only strategies. Up to 5 years the two former strategies had very similar performances, but for larger time horizons optimal strategies resulted in significant improvements: for instance, the average AUDPC was around 0.8 UR x days while resistant-only was around 1.2 UR x days for a 10-year temporal horizon. Hence, on very short time horizons, a resistant-only strategy remained efficient, while for longer temporal horizons, periodic rotations were preferable. The AUDPC gain obtained when shifting from a resistant-only to an optimal strategy could be almost as large as the one obtained by shifting from a susceptible-only to a resistant-only strategy.

Figure 3. Graphical representation of the susceptible-only, resistant-only and optimal periodic rotation strategies according to the temporal horizon, for the parameter combinations defined in Table 1. The shaded areas represent the 5-95% interpercentiles, i.e. envelopes containing 90 % of the values over the 2880 parameter sets. The solid curves represent the median.

For temporal horizons greater than 5 seasons, optimal strategies generally alternated a single season of resistant (R) plants with a few seasons of susceptible plants (see Table 2). A single R season appeared to be the best trade-off to reduce the avirulent nematode population and limit the increase of virulent nematodes. With our parameter ranges, optimal performance was overall achieved by planting relatively few resistant plants. A low ratio of resistant plants limits the selection pressure in favour of virulent nematodes, but also increases crop losses as avirulent nematodes thrive on susceptible plants. On the contrary, larger resistant plant ratios decrease the durability of the gene, by selecting for virulent nematodes, which eventually cancel the benefits provided by the resistance. The resistant plant ratio had an impact on the performance and dynamics. We compared an optimal 1R+5S and a non optimal 1R+2S strategy on a 20-season temporal horizon (see Figure 4). After the first 3 seasons, which were the same for both strategies, the end-of-season value of the total biomass tended to stabilise around 0.2 UR for the non optimal strategy, whereas it varied between 0.1 and 0.6 UR for the optimal strategy (see Figure 4(a)).

The nematode population also had a fairly regular seasonal pattern for the non optimal strategy: its density varied between 2 and 7 UN (see Figure 4(b)) and mostly consisted of virulent nematodes (see Figure 4(c)). In contrast, the optimal strategy exhibited an irregular pattern: at the end of each R season, nematode density tended to 0. It then increased, but the proportion of virulent nematodes gradually decreased to 0 over the subsequent 4 S seasons (see Figure 4(c)). Indeed, virulent nematodes are selected for in resistant crops, but selected against in susceptible crops, as they are less competitive than avirulent nematodes. The 1R+5S optimal strategy ensured that virulent nematodes were rare in the soil when introducing resistant plants, in order to take full benefit from the resistance. In contrast, the 1R+2S non optimal strategy did not achieve the same result because 2 S seasons were not enough for the virulent nematodes to become rare. Consequently, during R seasons, production (biomass) increased for the optimal strategy, but not for the non optimal strategy. Corresponding AUDPC are 1.14 UR x days for the optimal strategy and 1.44 UR x days for the non optimal strategy.

CONCLUSION

This study proposed a model which describes plant root infection dynamics by nematodes. Parameter adjustment of our model on experimental data allowed to reproduce rather faithfully infected plant growth by nematodes during a cropping season. We looked for optimal periodic crop rotations, by minimizing a proxy of nematode damage to crops. The deployment of resistant and susceptible plants should allow to maintain crop yield while controlling resistance breaking by virulent nematodes. We found that rather few resistant plants are necessary to achieve this goal. To take the study one step further, we could carry out sensitivity analyses to identify parameters which have most influence on the the optimal strategy. We could also test these strategies experimentally to validate their efficiency.

Figure 1 .

 1 Figure 1. Compartmental diagram representing the within-season infection of susceptible (superscript X=S) or resistant (superscript X=R) healthy plant roots (H X ) by virulent (subscript v) and avirulent (subscript a) nematodes (P), before becoming latently infected (E=Ea+Ev) and then infectious (I=Ia+Iv) plant roots. Parameters are described in the text.

Figure 2 .

 2 Figure 2. Adjustment of the model to experimental data. (a) Final density of nematodes and (b) relative biomass loss after 42 (in red) and 135 days (in blue), as functions of the initial density of nematodes (logarithmic scale).

Figure 4 .

 4 Figure 4. Graphical representation of two periodic rotation strategies over a 20-season time horizon: the 1R+5S optimal strategy (in blue) alternating 1 and 5 seasons of resistant (R in red) and susceptible (S in green) plants, respectively; the 1R+2S non optimal strategy (in black). Winter seasons are illustrated as shaded areas.Corresponding AUDPC are 1.14 UR x days for the optimal strategy and 1.44 UR x days for the non optimal strategy.

Table 1 .

 1 List of model parameters: parameter values either derive from the literature [reference given] or were estimated [*]; values in brackets are given for the 6 parameters (in bold) that were varied.

	Parameter	Description	Value (and range)	Reference
	r	Nematode reproduction rate	25 UN x UR -1 x day -1	[1]
	g	Plant root growth rate	105 mg of roots x day -1	[2]
	H0	cropping season Initial root biomass at the beginning of each	1500 mg of roots	[2]
	Ω	Mortality rate of nematodes in the soil	0.04 day -1	[3]
	w	Cost of virulence	0.4 (0.3, 0.35, 0.4, 0.45)	[3]
	εv	Success of infection by virulent nematodes.	0.8 a UR x b UN -1	[3]
	λ	Transition rate from E to I	0.05 day -1	[4,5]
	α	Mortality rate of infected feeding sites	0.125 day -1	[4,5]
	δ	nematodes Mutation rate of avirulent to virulent	10 -3 (10 -3 , 10 -4 , 10 -5 , 10 -6 )	[6]
	τ	Duration of each cropping season	135 days	__
	ε a X	nematodes. Success of infection by avirulent	0 if X=R, or 1 if X=S UR x UN -1	__
	φ	Winter survival probability	0.8 (0.5, 0.6, 0.7, 0.8)	[7]
	P0	Initial nematode density in the soil	0.8 (0.016, 0.03, 0.8, 4, 20) UN	[8]

Table 2 .

 2 Optimal periodic rotation strategies with their associated AUDPC , for various temporal horizons. An mR+pS strategy alternates m and p seasons of resistant and susceptible plants, respectively.

	Temporal horizon	Optimal strategy	AUDPC
	(seasons)		(UR x days)
	5	1R+3S	0.78
	10	1R+3S	1.10
	20	1R+5S	1.14
	30	1R+4S	1.21
	40	1R+4S	1.21

ACKNOWLEDGEMENTS

The authors are grateful to the Inria Sophia Antipolis -Méditerranée "NEF" computation cluster for providing resources and support.