Keywords: Réseaux de capteurs, accumulation, algorithmes d'approximation, makespan, grille

Nous présentons des algorithmes efficaces pour la collecte d'informations par une station de base au sein d'un réseau sans-fil multi sauts en présence d'interférences. Nous nous focalisons sur les réseaux en grille car ils sont un bon modèle des réseaux d'accès comme des réseaux aléatoires de capteurs. Le temps est divisé en étapes élémentaires. Au cours d'une étape, un noeud peut transmettre au plus un message à l'un de ces voisins. Chaque appareil est équipé d'un interface half duplex et ne peut donc émettre et recevoir à la même étape. Ainsi, au cours d'une étape, l'ensemble des transmissions valides induit un couplage de la grille. Le problème consiste à minimiser le nombre d'étapes nécessaires à la collecte de tous les messages par la station de base. Le meilleur algorithme connu était une 3/2 approximation. Nous donnons un algorithme très simple qui approche l'optimum à 2 près, puis nous présentons un algorithme plus évolué qui est une +1 approximation. Nos résultats sont valides lorsque les appareils ne disposent d'aucune mémoire tampon et doivent retransmettre un message à l'étape suivant sa réception.

Introduction

We address here the challenging problem of gathering information in a Base Station (denoted BS) of a wireless multi hop grid network when interferences constraints are present. This problem is also known as data collection and is particularly important in sensor networks, but also in access networks. The communication network is modeled by a graph. Here we consider grid topologies as they model well both access networks and also random networks (which approximatively behave like if the nodes were on a grid [START_REF] Klasing | From balls and bins to points and vertices[END_REF]). We suppose the time is slotted and that during one time slot, or step, each node can transmit to one of its neighbors at most one data item (referred in what follows as a message). Each vertex of the grid may have any number of messages to transmit : zero if it is not concerned (sleeping station or no sensor at this node or failed device) one or many. We also suppose that each device (sensor, station,. . . ) is equipped with an half duplex interface; so a node cannot both receive and transmit during a step. In particular, this is the case in a mono-frequency smart antennas radio system: at any step, each device can configure its antenna array to shape a beam to reach any of its neighbours, but sending a message would prevent it from receiving because, among other causes, of near-far effects. So we refer to this model as the smart-antennas model. During any step only non interfering transmissions can be done, thus the non interfering calls done during a step will form a matching (set of independent edges). Our aim is to design algorithms to do a gathering under such hypotheses, which minimize the minimum number of steps needed to send all messages to BS, a.k.a. makespan or completion time.

Related Work

A lot of authors have studied the gathering problem under various assumptions (see the surveys [BKK + 09] and [START_REF] Gargano | Time optimal gathering in sensor networks[END_REF]).

In [START_REF] Florens | Lower bounds on data collection time in sensory networks. Selected Areas in Communications[END_REF], the smart antennas model is considered with the extra constraint that non buffering is allowed in intermediary nodes. That is, when a node receives a message at some step, it must transmit it during the next step. In this setting, optimal polynomial-time algorithms are presented for path and tree topologies [START_REF] Florens | Lower bounds on data collection time in sensory networks. Selected Areas in Communications[END_REF][START_REF] Revah | Improved bounds for data-gathering time in sensor networks[END_REF]. The work of [START_REF] Florens | Lower bounds on data collection time in sensory networks. Selected Areas in Communications[END_REF] has been extended to general graphs in [START_REF] Gargano | Optimally fast data gathering in sensor networks[END_REF] and [GR] but in the uniform case where each node has exactly one message to transmit. The case of grids is considered in [START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF] where a 1.5-approximation algorithm is presented. When nodes can both emit and receive a message during the same step, the problem has also been studied. When no buffering is allowed, this problem is known as the hot-potato routing problem and is considered in [START_REF] Busch | Hard-potato routing[END_REF][START_REF] Mansour | Many-to-one packet routing on grids[END_REF].

The case of omnidirectional antennas has been extensively studied. In this model, nodes can transmit at any of their neighbours at distance d T ≥ 1 but any emission creates some interferences. More precisely, when a node v transmits, any node at distance at most d I ≥ 0 of v cannot receive a message from another node than v during the same step. The following papers consider the case d I ≥ d T . Moreover, any node has to transmit at least one message to BS and buffering is allowed. In this setting, computing the makespan is NP-hard [BGK + 06].A 4approximation algorithm and lower bounds for general graphs are also provided in [BGK + 06]. A 4-approximation algorithm has been proposed to handle the online version [START_REF] Bonifaci | An approximation algorithm for the wireless gathering problem[END_REF]. In [START_REF] Bermond | Efficient gathering in radio grids with interference[END_REF], the case of grids is considered when d T = 1: an optimal polynomial-time algorithm is provided when BS stands at the center of the grid. Gathering in grids is also considered within a continuous model in [START_REF] Gomes | Bandwidth allocation in radio grid networks[END_REF].

Our results

We deal with the gathering problem in grids. We propose a very simple algorithm that achieves makespan plus two, and a more involved +1 approximation algorithm. Our algorithms work as well when no buffering is allowed which considerably improves existing algorithms. Furthermore, following our algorithms a message arrives at most one step (or two steps) after what will happen if we have no interferences (provided that BS can receive only one message per step). So the average time is also very good. We present the results for the smart antennas model and when BS stands at some corner of the grid, but they can be easily extended to any binary distance-based interference model and to the case of any position of BS.

One helpful idea is to actually study the related one-to-many personalized broadcast problem in which the BS wants to communicate different data items to some other nodes in the network. Solving the above dissemination problem is equivalent to solve data gathering in sensor networks. Indeed, let T denote the makespan (delay), that is, the largest step used by a personalized broadcast algorithm; a gathering schedule with delay T consists in scheduling a transmission from node y to x during slot t iff the broadcasting algorithm schedules a transmission from node x to y during slot Tt + 1, for any t with 1 ≤ t ≤ T .

Preliminaries

From now on, we consider the equivalent problem of personalized broadcasting where the Base Station BS has to transmit messages to some destination nodes in the grid.

Notations

In the following, we consider a N × N grid G = (V, E) where vertices are given there natural coordinates. More precisely, the base station BS has coordinates (0, 0), and any vertex v has coordinates ( BS), where d(u, v) denotes the classical distance between nodes u and v.

x v , y v ). A vertex v is above (resp., below) w ∈ V if y v ≥ y w (resp., if y v ≤ y w ). Similarly, v is to the right (resp., to the left) of w ∈ V if x v ≥ x w (resp., if x v ≤ x w ). Finally, a vertex v is nearer to the source than w ∈ V is d(v, BS) ≤ d(w,
We consider a set of M ≥ 0 messages M that must be sent from the source BS to some destination nodes. Let dest(m) ∈ V denote the destination of m ∈ M. A message m ∈ M is lower (resp., higher) than m ′ ∈ M if dest(m) is below (resp., above) dest(m ′ ). A message m is righter (resp., lefter) than m ′ , if dest(m) is to the right (resp., to the left) of dest(m ′ ). We use d(m) to denote d(dest(m), BS), and m m ′ if dest(m) is nearer to the source than dest(m ′ ), that is, if d(m) ≤ d(m ′ ). We suppose in what follows that the messages are ordered by non increasing distance of their destination nodes, and we note

INRIA M = {m 1 , • • • , m M } where m i m j for any i ≤ j ≤ M , so d(m 1 ) ≥ d(m 2 ) ≥ • • • ≥ d(m M ).
S ⊙ S ′ denotes the sequence obtained by concatenation of two sequences S and S ′ .

Lower bound

Consider a model whitout interferences, i.e., any node can receive and transmit simultaneously, but where the source can only send one message per step. Whatever be the broascasting scheme, a message m sent at step t ≥ 1 will be received at step t ′ ≥ d(m) + t -1. A broadcasting scheme is said greedy if, given an ordered sequence S of the messages, the source sends one message per step, in the ordering S, and each message follows a shortest path toward its destination node. Note that, in the model without interferences, if the messages follow shortest paths, a vertex will never receive more than one message per step.

Definition 1 LB = max i≤M d(m i ) + i -1.
Lemma 1 In the model without interferences, when the source emits at most one message per step, a greedy algorithm following the ordered sequence of messages (m 1 , m 2 , • • • , m M ) is optimal, with makespan LB.

Proof. Clearly, sending the messages in the ordering of the sequence (m 1 , m 2 , • • • , m M ) along shortest paths will achieve such a makespan. Now, let us consider an optimal schedule of the messages (s

* 1 , • • • , s * M ) different from (m 1 , m 2 , • • • , m M ) and let i ≥ 1 be the smallest integer such that s * i = m i = s * j (j > i).
We prove that sending the messages in the ordering of the sequence (s

* 1 , • • • , s * i-1 , s * j , s * i+1 , • • • , s * j-1 , s * i , s * j+1 , • • • , s * m )
does not increase the makespan. Indeed, only the i th and j th messages differ and max{d(s

* j ) + i -1, d(s * i ) + j -1)} ≤ d(s * j ) + j -1) because d(v i , BS) = d(s * j ) ≥ d(s * i )
and j > i. By iterating this process, we get that the ordering of the sequence (m 1 , m 2 , • • • , m M ) is also optimal.

Corollary 1 In the model with interferences, no algorithms can achieve a makespan less than LB.

Personalized Broadcasting Algorithms

Horizontal-Vertical broadcasting

First, we present a very simple broadcasting scheme that we prove to be sufficient to obtain a good approximation of the optimal makespan.

Given a message whose destination node v has coordinates (x, y), the message is sent horizontally to v if it follows the shortest path from BS to v passing through (x, 0). The message is sent vertically if it follows the shortest path from BS to v passing through (0, y).

Definition 2 A Horizontal-Vertical broadcasting scheme, or HV-scheme, takes an ordering S of M as an input and proceeds as follows. A direction, horizontal or vertical, is chosen for the first message. Then, the source sends one message every step in the ordering S and alternating horizontal and vertical messages. Let us do some easy remarks about any HV-scheme. Consider two distinct messages sent by the source x time-slots apart. Since these messages follow shortest paths, while the first message has not reached its destination, both messages are separated by a distance at least x. Hence, Claim 1 In a HV-scheme, only consecutive messages may interfer.

Let us characterize forbidden and acceptable configurations in HV-scheme. Assume that two messages are sent consecutively. It is possible to guess the respective positions of their destination nodes by knowing whether both messages interfer or not. In Figure 1(a), nodes in the grey part are the nodes that are higher and lefter than y. Figure 1(a) illustrates the following Claim.

Claim 2 Let m, m ′ be 2 messages sent consecutively by a HV-scheme, with m sent vertically and m ′ sent horizontally. Messages m and m ′ interfer if and only if their destinations are distinct and m ′ is higher and lefter than m.

Before continuing, let us remark that there exist configurations for which no gathering protocol can achieve better makespan than LB + 1. Figure 1(b) represents such a configuration. Indeed, in Figure 1(b), the three destinations a, b and c have coordinates (1, 0), (1, 1) and (1, 2), and LB = 3. However, to achive such a makespan, the first message must be sent to c (because c is at distance 3 from g) and the second message must be sent to b (because the message start after the first step and must go at distance 2). To avoid collision, the only possibility is to send the first message vertically, and the second one horizontally. But then, the last message cannot reach a before step 4.

+2 approximation

Recall that (m 1 , • • • , m M ) denotes the ordered sequence of the messages in the non increasing ordering of the distance to their destinations. In this section, we give the Algorithm T woApprox, depicted in Figure 2, that computes an ordered sequence S = (s 1 , • • • , s m ) of the messages satisfying the two following properties:

INRIA Input: M = {m 1 , • • • , m M }, the set of messages ordered in non increasing distance order Output: (s 1 , • • • , s M ) an ordered sequence of M satisfying (i) and (ii) begin Case M = 0 return ∅ Case M = 1 return (m 1 ) Case M ≥ 2 Let O ⊙ p = T woApprox({m 1 , • • • , m M-2 })
Let q be the lowest message in {m M-1 , m M } and let r be the other one if p is higher than q return O ⊙ (p, q, r) (i) HV-scheme(S) broadcasts the messages without collisions, sending the last message vertically, and

else return O ⊙ (m M-1 , p, m M ) end.
(ii) s i ∈ {m i-2 , m i-1 , m i , m i+1 , m i+2 } for any i ≤ M , and s M ∈ {m M-1 , m M }
Theorem 1 Algorithm T woApprox computes an ordering S of the messages, such that HV-scheme(S) satisfies properties (i) and (ii) and so achieves makespan at most LB + 2.

Proof. To prove the correctness of Algorithm T woApprox, we proceed by induction on M . If M ≤ 2, the result holds obviously. Let us assume that the ordering of the sequence computed by T woApprox({m 1 , • • • , m M-2 }) satisfies properties (i) and (ii). Let p be the last message of this sequence. By the induction hypothesis, p ∈ {m M-3 , m M-2 } is sent vertically. Let t be the message before p in this sequence. By Claim 2, p must be higher or lefter than t. The sequence is denoted by

O ⊙ p = O ′ ⊙ (t, p).
Let q be the lowest message in {m M-1 , m M } and let r be the other one. We consider two cases depending on the positions of p, q and r. a) Case p is higher than q. It is sufficient to send q horizontally at step M -1, and r vertically at step M . This case is depicted in Figure 3(a). Indeed, by Claim 1 only p and q, or q and r may interfer. By Claim 2, there are no interferences. It is easy to check that O ⊙ (p, q, r) satisfies (i) and (ii).

b) Case q and r are higher than p. Since q, r p, they are higher and lefter than p. This case is depicted in Figure 3(b). In this case, instead of sending p at step M -2, the source sends m M-1 vertically at step M -2, then p horizontally at step M -1, and then m M vertically at step M . The transformation is depicted in Figure 3(c). Clearly, O ⊙ (m M-1 , p, m M ) satisfies (i) and (ii). By Claim 1 only t and m M-1 , or m M-1 and p, or p and m M may interfer. Since m M-1 is higher and lefter than p that is higher or lefter than t, by Claim 2, m M-1 interfers neither with t nor with p. Similarly, m M is higher and lefter than p and these messages do not interfer.

+1 approximation

In this section, we give the Algorithm OneApprox, depicted in Figure 4, that computes an ordered sequence S = (s 1 , • • • , s m ) of the messages satisfying the following properties:

(i) HV-scheme(S) broadcasts the messages without collisions, sending the last message vertically, and

(iii) s i ∈ {m i-1 , m i , m i+1 } for any i ≤ M (in particular, either s M = m M , or s M = m M-1 and s M-1 = m M ).
Theorem 2 Algorithm OneApprox computes an ordering S of the messages, such that HV-scheme(S) achieves makespan at most LB + 1.

Proof. We prove that Algorithm OneApprox computes an ordered sequence of messages satisfying the properties (i) and (iii). We proceed by induction on M . An ordered sequence S = (s 1 , • • • , s M ) of M satisfying (i) and (iii) is said valid. Sequence S is said i-almost valid if it satisfies all the desired properties, but s i interfers with s i+1 , for a unique i ≤ M . If M ≤ 2, the result holds obviously. Let us assume that the sequence OneApprox({m 1 , • • • , m M-2 }) satisfies (i) and (iii). Let p be the last message of this sequence. By the induction hypothesis, p ∈ {m M-3 , m M-2 } is sent vertically. The sequence is denoted by

(s 1 , • • • , s M-2 ). INRIA Input: M = {m 1 , • • • , m M }
, the set of messages ordered in non increasing distance order Output:

(s 1 , • • • , s M ) an ordered sequence of M such that m i ∈ {s i-1 , s i , s i+1 } for any i ≤ M begin Case M = 0 return ∅ Case M = 1 return (m 1 ) Case M ≥ 2 Let O ⊙ p = OneApprox({m 1 , • • • , m M-2 })
Let q be the lowest message in {m M-1 , m M } and let r be the other one if p is higher than q return O ⊙ (p, q, r)

else if p = m M-2 return O ⊙ (m M-1 , p, m M ) else /* This last case may occur only if M > 3 */ Let (s 1 , • • • , s M-4 ) ⊙ (m M-2 , m M-3 ) = OneApprox({m 1 , • • • , m M-2 }) return M akeV alid((s 1 , • • • , s M-4 ) ⊙ (m M-3 , m M-1 , m M-2 , m M ), 2) end.
-2j = 0 */ return O else if s M-2j = m M-2j /* In particular, this case occurs if M -2j = 1 */ return (s 1 , • • • , s M-2j-2 ) ⊙ (s M-2j-1 , s M-2j+1 , s M-2j , s M-2j+2 ) ⊙ (s M-2j+3 , • • • , s M ) else return /* This last case may occur only if M -2j ≥ 2 */ /* Note that, in this case, s M-2j = m M-2j-1 and s M-2j-1 = m M-2j */ M akeV alid((s 1 , • • • , s M-2j-2 ) ⊙ (s M-2j , s M-2j+1 , s M-2j-1 , s M-2j+2 ) ⊙ (s M-2j+3 , • • • , s M ), j + 1) end.
For any i < M -2, O i denotes (s 1 , • • • , s M-2-i ), i.e., (s 1 , • • • , s M-2 ) = O i ⊙ (s i+1 , • • • , s M-2 ).
Recall that by induction hypothesis, p = s M-2 ∈ {m M-3 , m M-2 } and has been sent vertically. Let q be the lowest message in {m M-1 , m M } and let r be the other one. We consider the 3 cases of Algorithm OneApprox (when M ≥ 2). a) Case p is higher than q. We proceed like in case (a) of the proof of Theorem 1. In this way it is easy to check that O 1 ⊙ (p, q, r) is valid.

b) Case q and r are higher than p, and p = m M-2 . We proceed like in case (b) of the proof of Theorem 1. The transformation is depicted in Figure 3(c). The sequence

O 1 ⊙ (m M-1 , p, m M ) is valid.
c) Case q and r are higher than p, and p = m M-2 (i.e., s M-3 = m M-2 and p = s M-2 = m M-3 ). Moreover, p is sent vertically. This case is depicted in Figure 6 (with M = 8).

By Claim 2 and because s M-3 s M-2 = p, s M-3 is lower than s M-2 = p. Indeed, these messages do not interfer in the ordered sequence computed by Algorithm OneApprox. Then, it is possible to send messages m M-3 , m M-1 , m M-2 and m M , alternatively horizontal and vertical (starting horizontally) without any interference between these four messages. Therefore, the scheduling

O M-4 ⊙ (m M-3 , m M-1 , m M-2 , m M ) is either valid or (M -4)-almost valid.
We prove that Subprocedure M akeV alid

(O M-4 ⊙(m M-3 , m M-1 , m M-2 , m M ), 2)
computes an ordered sequence of M that is valid. We need the following technical definition. Let us do the following easy remarks.

Definition 3 Let i ∈ {2, • • • , ⌊M/2⌋}. An ordered sequence S = (s 1 , • • • , s M ) is (i -1)-good if it is (M -2i)-
1. In a (i -1)-good sequence S, if s M-2i does not interfer with s M-2i+1 then S is valid.

2. In particular, if 2i = M , a (i -1)-good sequence is valid.

Note that the sequence O

M-4 ⊙ (m M-3 , m M-1 , m M-2 , m M ) is 1- good.
Let i, 1 < i ≤ ⌊M/2⌋ and let S be a (i -1)-good sequence. By reverse induction on i, we prove that M akeV alid(S, i) will compute a valid sequence.

We recall that

S = (s 1 , • • • , s M-2i-2 )⊙(s M-2i-1 , s M-2i , s M-2i+1 , s M-2i+2 )⊙(s M-2i+3 , • • • , s M ) = (s 1 , • • • , s M-2i-2 )⊙(s M-2i-1 , s M-2i , m M-2i+1 , m M-2i+3 )⊙(s M-2i+3 , • • • , s M )
First, if 2i = M , then s M-2i does not interfer with s M-2i+1 (because s M-2i is not defined). M akeV alid(S, i) returns S which is valid by Remark 2.

If 2i = M -1 and s 1 and s 2 do not interfer, M akeV alid(S, i) returns S that is valid by Remark 1. Otherwise, if 2i = M -1 and s 1 and s 2 interfer, ). This implies that s 1 = m 1 . In this case, M akeV alid(S, i) returns (m 2 , m 1 , m 4 ) ⊙ (s 4 , • • • , s 2i+1 ). Moreover, by parity and because s 2i+1 is sent vertically, m 2 is sent horizontally. By Claim 2 and because m 1 m 2 m 4 , m 1 must be lower than m 2 that is lower than m 4 . By Claim 1, the only possible interferences may occur between m 1 and m 2 , or m 2 and m 4 . The respective positions of the destination nodes of m 1 , m 2 , m 4 imply that this sequence is valid. Now, assume 2i < M -1, and assume that, if S is i-good, M akeV alid(S, i+ 1) will compute a valid sequence. Assume that S is (i -1)-good. If s M-2i and s M-2i+1 do not interfer, then M akeV alid(S, i) returns S that is valid by Remark 1. Let us consider the case when s M-2i and s M-2i+1 interfer. By parity, s M-2i is sent vertically and s M-2i+1 horizontally. By Claim 2, s M-2i+1 is higher and lefter than s M-2i . Moreover, since s M-2i+1 and s M-2i+2 do not interfer, then s M-2i+2 must be higher or lefter than s M-2i+1 . Similarly, s M-2i-1 must be either lower or righter than s M-2i .

There are two cases to be considered according to the value of s M-2i . Recall that, because

s M-2i+1 = m M-2i+1 , s M-2i ∈ {m M-2i , m M-2i-1 }. c.1 If s M-2i = m M-2i .
Because of their respective positions, it is possible to send messages s M-2i-1 , s M-2i+1 , s M-2i and then s M-2i+2 , alternatively horizontal and vertical (starting horizontally) without any interference between these 4 messages. In this case, M akeV alid(S, i) returns the sequence (s

1 , • • • , s M-2i-2 ) ⊙ (s M-2i-1 , s M-2i+1 , s M-2i , s M-2i+2 ) ⊙ (s M-2i+3 , • • • , s M )
. By previous remark, this sequence does not create any interference. Moreover, only s M-2i+1 = m M-2i+1 and s M-2i = m M-2i have been switched. Therefore, it is easy to check that it is valid.

c.2 If s M-2i = m M-2i-1 . In this case, note that s M-2i-1 = m M-2i .
Because of their respective positions, it is possible to send messages, s M-2i , s M-2i+1 , s M-2i-1 and then s M-2i+2 alternatively horizontal and vertical (starting horizontally) without any interference between these 4 messages. Hence, the only possible interference in the following sequence is between s M-2i-2 and to s M-2i :

S ′ = (s 1 , • • • , s M-2i-2 )⊙(s M-2i , s M-2i+1 , s M-2i-1 , s M-2i+2 )⊙(s M-2i+3 , • • • , s M ).
It is easy to check that S ′ is i-good. Besides, M akeV alid(S, i) returns M akeV alid(S ′ , i + 1) that is valid by the induction assumption. Now, we prove that Algorithm OneApprox performs in linear time, with respect to the number of messages.

Theorem 3 The time complexity of Algorithm OneApprox is O(M ).

Proof. We note c(i) the time-complexity of OneApprox({m

1 , • • • , m i }). We prove by induction on i that c(i) = O(i). Let S = (s 1 , • • • , s M )

Distributed Algorithm

We present a distributed algorithm for the gathering in a grid. This algorithm is based on the Algorithm T woApprox, for personalized broadcasting presented in section 3.2.

Distributed Model

The network is assumed to be synchronous. Each node has only a local view of the network. However, it has access to the following global information: its position (x, y) in the grid, the position of BS (for sake of simplicity, we assume INRIA that BS has coordinates (0, 0)), and the size N × N of the grid (an upper bound on N is sufficient). Finally, any node v has m(v) ≥ 0 messages that it must send to BS. At every step, a node can send or (exclusive) receive a control message, or signaling, of size O(log N ) to (from) one of its neighbours. In the following, for any i ≤ 2N , Diag(i) denotes the set of vertices at distance i from BS. We refer to Diag(i) as the diagonal i. The central node c(2a) (resp., c(2a + 1)) of Diag(2a) (resp., Diag(2a + 1)) is the node with coordinates (a, a) (resp., (a + 1, a)). Finally, let AntiDiag be the set that consists of the vertices c(i) for all i ≤ 2N . The algorithm consists of four phases that we describe now.

Basic Description of Distributed Algorithm

Our algorithm aims at giving to any message m its position in the ordering S computed by Algorithm T woApprox (in terms of personalized broadcasting) and the makespan. This is performed in Y = O(N 2 ) steps (Y will be specified below) using O(N 2 ) signalings. Then, with this information, any message can compute its starting time, given that the first message will be sent at step Y + 1. Let us give a rough description of the four phases of the distributed algorithm. First two phases consist in giving to any message m its position in the non increasing order of their distance to BS such that nodes in the same diagonal are ordered up to down (the ordering of messages hosted at a same node is arbitrary). Moreover, each message m 2a+1 with a ≥ 0, resp., m 2a+2 , (actually, the node hosting this message) will learn the position(s) of messages m 2a+2 , m 2a+3 , m 2a+4 , resp., m 2a+1 , m 2a+3 , m 2a+4 . Then the third phase starts. With the information previously learnt, according to Algorithm T woApprox, message m 1 can decide the ordering in S of the first three messages: s 1 , s 2 , s 3 . Two of these three positions are occupied by m 1 and m 2 . The remaining place is occupied by m 3 or m 4 (This comes from the definition of the T woApprox algorithm). Then, at some step, the message s 2a+3 is fixed. With this information, we prove that message m 2a+3 can extend the ordering to s 2a+4 and s 2a+5 using the T woAlgo algorithm. At the end of this phase, any node knows its position in S and BS knows the makespan. During the last phase, BS broadcasts the makespan to any node. With this information, each node can compute its starting time for the gathering process.

Formal Description of Distributed Algorithm

Phase 1. The first phase is divided into two processes that are executed "almost" simultaneously.

The first one is executed in parallel by all diagonals. For any i ≤ 2N , it aims at collecting some information in c(i), the central node of Diag(i). When this process ends up at step i + 5, c(i) has learnt the number of messages l i standing in Diag(i) in nodes with greater ordinate than c(i),

the number of messages r i standing in Diag(i) in nodes with smaller ordinate than c(i),

the position(s) of the three messages with greatest ordinate in Diag(i).

Moreover, at the end of the phase, any node v with coordinates (x, y) in Diag(i) has learnt the position of the (at most 3) node(s) of Diag(i) hosting the closest 3 messages that are higher (if y ≥ x) or lower (if y ≤ x) than v.

To do so, two signalings D1 i and D1 ′ i , initiated by nodes (i, 0) and (0, i) respectively, are propagated toward c(i). From (i, 0) (resp., from (0, i)), D1 i (resp., D1 ′ i ) is transmitted to node (i, 1) and then to (i -1, 1) (resp., to (1, i) and then to (1, i -1)), and so on until reaching c(i). To avoid interferences, D1 i and D1 ′ i are initiated at step 1 by (i, 0) and (0, i) if i is odd. If i is even, D1 i is initiated at step 5 by (i, 0), and D1 ′ i is initiated at step 6 by (0, i). It is easy to see how information can be aggregated as D1 i and D1 ′ i go along, in order to obtain the desired information. Moreover, signalings D1 i (resp. D1 ′ i ) have size O(log N ) since they contain: the number of messages they met, the position(s) of the first three messages they met, and the position(s) of the last three messages they met. At step 7, a signaling A1 is initiated in BS and is propagated along AntiDiag towards (N -1, N -1). When c(i) receives A1 at step i + 6, it learns the total number of messages hosting by nodes in j<i Diag(j) and the position(s) of the three messages in j<i Diag(j) that are further to BS and with greatest ordinate. Then, using the information propagated by messages D1 i and D1 ′ i , c(i) updates message A1 and sends it to c(i + 1) during the next step.

The signaling A1 arrives to (N -1, N -1) at step 2N + 5 which concludes this phase.

Phase 2. The second phase is divided into three successive processes.

At step 2N + 6, a signaling A2 is initiated in (N -1, N -1) and is propagated along AntiDiag towards (0, 0). When c(i) receives A2 at step 4N + 6i, it learns the total number of messages M and the position(s) of the three messages in j>i Diag(j) that are closest to BS and with smallest ordinate.

Note that after step 4N + 6i, c(i) knows the interval of the positions occupied by messages in Diag(i), i.e., from M -j≤i Diag(j) + 1 = j>i Diag(j) + 1 to j>i Diag(j) + l i + r i + m(c(i)). The goal of next processes is that: any message m knows its position in the non increasing order of their distance to BS, i.e., its position in the ordered sequence M, and any message m 2a (resp., m 2a+1 ) knows the position(s) of messages m 2a+1 , m 2a+2 , m 2a+3 (resp., m 2a , m 2a+2 , m 2a+3 ).

At step 4N + 6i + 3 if i is odd and 4N + 6i + 5 if i is even, a signaling D2 i is initiated in c(i) and is propagated toward (i, 0). D2 i transmits: the next position (in M) to be attribuated to the messages in Diag(i) with smaller ordinates than c(i), i.e., from j>i Diag(j) + l i + m(c(i)) to j>i Diag(j) + l i + r i + m(c(i)) (in such a way that any message lower than c(i) in Diag(i) leanrs its number in the ordering when it meets the signaling D2 i ), the position(s) of the last three messages met by this signaling, and the position(s) of the three messages in j<i Diag(j) furthest to BS and with greatest ordinates.

INRIA

At step 4N +6-i+2 if i is odd and 4N +6-i+6 if i is even, a signaling D2 ′ i is initiated in c(i) and is propagated toward (0, i). D2 ′ i transmits: the next position (in the ordering) to be attribuated to the messages in Diag(i) with greater ordinates than c(i), i.e., from j>i Diag(j) to j>i Diag(j)+l i (in such a way that any message higher than c(i) in Diag(i) leanrs its number in the ordering when it meets the signaling D2 ′ i ), the position(s) of the last three messages met by this signaling, and the position(s) of the three messages in j<i Diag(j) furthest to BS and with greatest ordinates.

This phase ends at slot 4N + 12.

Phase 3. During this phase, any message learns its position in the final ordering S.

We define the start of this phase at slot 4N + 13 after finishing phase 2. At the beginning of this phase, message m 2a+1 (a ≥ 0) knows its position in the ordered sequence and the position(s) of m 2a+2 , m 2a+3 , and m 2a+4 .

The procedure starts as follows. Node m 1 knows m 2 , m 3 , m 4 . Using T woApprox algorithm with input (m 1 , m 2 , m 3 , m 4 ), it computes the ordering of the first three positions of S. According to the algorithm the possible configurations for the first three messages in S are (m 1 , m 2 , m 3 ), (m 1 , m 3 , m 2 ), (m 1 , m 2 , m 4 ), (m 2 , m 1 , m 3 ), (m 2 , m 3 , m 1 ), (m 2 , m 1 , m 4 ). Note that, although the algorithm returns also a message for the fourth position, it is not definitive because it could be modified when the next pair of messages (m 5 , m 6 ) is included. The first message s 1 is decided arbitrarily to be vertical.

Then, m 1 computes the current makespan, i.e., max j∈{1,2,3} d(BS, s j )+m j -1 and propagates the information to m 2 and m 3 . That is, m 1 sends them the ordering of the first three messages (s 1 , s 2 , s 3 ) of S (again, {s 1 , s 2 , s 3 } ⊂ {m 1 , • • • , m 4 }) and the current makespan. The corresponding signaling is sent at step 4N + 13 to m 3 and at step 4N + 15 to m 2 . The signaling reachs m 3 at step 4N + 12 + t where t is the distance between m 1 and m 3 .

The process continues iteratively until m 2a+3 receives a signaling from m 2a+1 at step 4N + 12 + t, for t = 0≤k≤p dist(m 2k+1 , m 2k+3 ). This signaling contains the positions of messages s 2a+1 , s 2a+2 , s 2a+3 , and the current makespan, i.e., the makespan restricted to messages s 1 to s 2a+3 . At this step, m 2a+3 must decide which messages will occupy positions s 2a+4 and s 2a+5 in S. This decision is taken according to Algorithm T woApprox. Note that, Algorithm T woApprox requires as input the next pair of messages m 2a+5 , m 2a+6 and the message m * ∈ {m 1 , • • • , m 2a+4 } whose position in S has not been decided yet. By property of Algorithm T woApprox, m * ∈ {m 2a+3 , m 2a+4 } Thus, m 2a+3 is able to decide which messages will occupy positions s 2a+4 and s 2a+5 in S, and then it can update the current makespan. Finally, at step 4N +12+t+1 (resp., at step 4N +12+t+3), message m 2a+3 sends a signaling to m 2a+5 (resp., to m 2a+4 ). This signaling contains the current makespan, s 2a+3 , s 2a+4 and s 2a+5 . The signaling is received by m 2a+5 at step 4N + 12 + t + t ′ where t ′ is the distance between m 2a+3 and m 2a+5 . The end of this phase is upper bounded by step 4N + 12 + 2N 2 . Phase 4. At the end of previous phase, BS learns the makespan of a HVscheme realizing the computed ordering and starts broadcasting it to any node at step 4N + 13 + 2N 2 . This is done thanks to a signaling through AntiDiag, and signalings from c(i) to (i, 0) and (0, i) (i ≤ 2N ) in a similar way as Phase 2. This process ends at step 6N + 19 + 2N 2 .

Defining Y = 6N + 19 + 2N 2 , each node knows the step when it has to send the message given that the starting step is Y + 1. Moreover, the message s j is sent horinzontally or vertically according to the parity of j.

Conclusion and Further Works

In this paper, we have presented algorithms for the minimum makespan personalized broadcasting in grid networks. In these settings, the problem is strictly equivalent to the data gathering problem. One can note that our network model assumes that an optimal MAC layer is available. It would be interesting to investigate on the behavior of the problems under weaker assumptions. Another direction to investigate is the online version of the problems. It is worth pointing out that, in this case, personalized broadcasting and gathering are no longer equivalent.

  Configuration when the trivial lower bound cannot be achieved.

Figure 1 :

 1 Figure 1: Two particular configurations

Figure

  Figure 2: Algorithm T woApprox

Figure 4 :

 4 Figure 4: Algorithm OneApprox

Figure

  Figure 5: MakeValid

  almost valid, and s M-2i+1 = m M-2i+1 , s M-2i+2 = m M-2i+3 and s M = m M .

Figure 6 :

 6 Figure 6: Case with recursive modifications of the scheduling

  be the ordered sequence computed by OneApprox(M). The pivot s M-2P of this sequence is the message such that s M-2P = m M-2P , and minimizing P . More precisely, we prove that c(M) = O(c(M -2P ) + O(P )). If M ≤ 1, the result is trivial. Let us assume M ≥ 2. By induction, the computation of OneApprox({m 1 , • • • , m M-2 }) takes time O(c(M -2 -2P ′ ) + O(P ′ )) where P ′ is the pivot of the obtained sequence. There are three possible cases corresponding to the three cases of the algorithm (when M ≥ 2). a. Clearly, in this case, c(M ) = c(M -2) + O(1). Moreover, either P = P ′ + 1 (if r = m M-1 ) or P = 0 (if r = m M ). In both cases, we get c(M ) = O(c(M -2P ) + O(2P )). b. c(M ) = c(M -2) + O(1) and P = P ′ + 1, thus c(M ) = O(c(M -2P ) + O(2P )). c. Let c ′ (M ) be the complexity of M akevalid((s 1 , • • • , s M ), 2). In this case, c(M ) = c(M -2) + c ′ (M ) and P = 0 (because in the computed sequence, s M = m M ). Finally, when executed M akevalid((s 1 , • • • , s M ), 2), the same subprocedure M akeV alid is recursivelly executed until s M-2j and s M-2j+1 do not interfer, or s M-2j = m M-2j . Therefore, it is executed at most P ′ times and each execution takes O(1). Hence, c(M ) = O(M -2P ′ ) + O(P ′ ) = O(M ).

RR n 6851

This work has been partially funded by European project IST/FET AEOLUS. * Funded by Conicyt(Chile)/INRIA.


A Forler

C Remoué

A Venon

A Rousselet

G Lucas

A O Kwarteng

R Rover

M Le Guilloux

Guilloux M Le

S Vazquez

G Alins

T Kirisits

Stéphane Bazot

A 1 Cornille

Affiliations

Ecological and evolutionary drivers of phenotypic and genetic variation in the European crabapple ( Malus sylvestris (L.) Mill.), a wild relative of the cultivated apple

Keywords: population structure, isolation-by-distance, isolation-by-ecology, local adaptation, climate change, apple tree, crop wild relatives

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Knowledge of the spatial phenotypic and genetic variation among populations is essential for understanding the ecological (biotic and abiotic) and evolutionary (gene flow, selection, drift, mutation) processes involved in population divergence and adaptation [START_REF] Savolainen | Ecological genomics of local adaptation[END_REF][START_REF] Sork | Genomic Studies of Local Adaptation in Natural Plant Populations[END_REF]. The global biodiversity crisis, and its consequences on ecosystem health and services, makes investigating these questions, and identifying the taxa most vulnerable to anthropogenic change, all the more relevant [START_REF] Hoffmann | Opportunities and challenges in assessing climate change vulnerability through genomics[END_REF].

Plant species distributed across climatic gradients typically experience spatial variation in selection, genetic drift and gene flow, processes that drive genetic and phenotypic divergence among populations [START_REF] Svenning | The Influence of Paleoclimate on Present-Day Patterns in Biodiversity and Ecosystems[END_REF]. Climate influence demography such as population expansion and contraction, the extent of gene flow among populations, and ultimately the extent of genetic divergence among populations [START_REF] Edwards | The Evolution of Comparative Phylogeography: Putting the Geography (and More) into Comparative Population Genomics[END_REF]. For instance, changes in the climate since the last glacial maximum (LGM) 20,000 years ago have driven the genetic composition of the European crabapple and many other tree species [START_REF] Comes | The effect of Quaternary climatic changes on plant distribution and evolution[END_REF][START_REF] Kremer | Is there a correlation between chloroplastic and nuclear divergence, or what are the roles of history and selection on genetic diversity in European oaks? Range wide distribution of chloroplast DNA diversity and pollen deposits in European white oaks: inferences about colonisation routes and management of oak genetic resources[END_REF][START_REF] Pyhäjärvi | Colonization routes of Pinus sylvestris inferred from distribution of mitochondrial DNA variation[END_REF]Cornille et al., 2013a;[START_REF] Gugger | Influence of late Quaternary climate change on present patterns of genetic variation in valley oak, Quercus lobata Née[END_REF][START_REF] Riordan | Association of genetic and phenotypic variability with geography and climate in three southern California oaks[END_REF][START_REF] Lander | Weak founder effects but significant spatial genetic imprint of recent contraction and expansion of European beech populations[END_REF][START_REF] Yamada | Refugia during the last glacial period and the origin of the disjunct distribution of an insular plant[END_REF][START_REF] Parisod | Plant speciation in the face of recurrent climate changes in the Alps[END_REF]. Climate can also shape phenotypic variation among populations. Populations occurring under the same climate may share physiological tolerances to climatic conditions, including plant carbon uptake via photosynthesis. Carbon uptake traits condition plant size and growth, reproduction and survival under different climatic conditions [START_REF] Nicotra | Plant phenotypic plasticity in a changing climate[END_REF][START_REF] Hartmann | Plant carbon allocation in a changing worldchallenges and progress: introduction to a Virtual Issue on carbon allocation[END_REF]. In some cases, local climate can impose divergent selection on carbon uptake traits and lead to long-term reduction in gene flow among populations and local adaptation [START_REF] Keller | Climate-driven local adaptation of ecophysiology and phenology in balsam poplar, Populus balsamifera L. (Salicaceae)[END_REF][START_REF] Franks | Evolutionary and plastic responses to climate change in terrestrial plant populations[END_REF][START_REF] Aitken | Time to get moving: assisted gene flow of forest trees[END_REF][START_REF] Ramírez-Valiente | Population-Level Differentiation in Growth Rates and Leaf Traits in Seedlings of the Neotropical Live Oak Quercus oleoides Grown under Natural and Manipulated Precipitation Regimes[END_REF][START_REF] Alexandre | How does contemporary selection shape oak phenotypes?[END_REF]. Whether the phenotypic variation observed in species distributed across large climatic ranges results from their demographic or adaptive history remains an intense topic of investigation [START_REF] Li | Joint analysis of demography and selection in population genetics: where do we stand and where could we go?[END_REF][START_REF] Tiffin | Advances and limits of using population genetics to understand local adaptation[END_REF]. Furthermore, investigating this question can help predict how plants may respond to climate change and how species adapt to their environment.

There are multiple ways to investigate whether the genetic and phenotypic variation among populations distributed across climatic gradients results from selection, genetic drift and/or gene flow.

A first step could be to use a common garden experiment to investigate the genetic basis of phenotypic variation among populations. Indeed, different populations occurring across a climatic gradient may display clinal variation, i.e., differences in a trait that may be the result of plasticity or local genetic adaptation [START_REF] Savolainen | Ecological genomics of local adaptation[END_REF][START_REF] De Villemereuil | Common garden experiments in the genomic era: new perspectives and opportunities[END_REF]. Measuring candidate traits for adaptation to climate, e.g., phenology [START_REF] Brachi | Investigation of the geographical scale of adaptive phenological variation and its underlying genetics in Arabidopsis thaliana[END_REF] or traits related to plant carbon uptake [START_REF] Savolainen | Ecological genomics of local adaptation[END_REF][START_REF] De Villemereuil | Common garden experiments in the genomic era: new perspectives and opportunities[END_REF] in individuals from different populations under the same environmental conditions can help elucidate the genetic basis of phenotypic variation across populations without the confounding effects of the environment. Ideally, common garden should include the main genetic groups across the species' distribution [START_REF] De Villemereuil | Common garden experiments to study local adaptation need to account for population structure[END_REF]. The association of neutral genotypic variation with ecological variation can also be used as evidence of adaptive divergence among populations [START_REF] Shafer | Widespread evidence for incipient ecological speciation: a metaanalysis of isolation-by-ecology[END_REF][START_REF] Wang | Isolation by environment[END_REF]. The correlation between neutral genetic differentiation and environmental or phenotypic divergence among populations, independent of geographic distance, referred to as isolation-by-ecology (IBE), is an extension of the isolation-by-distance (IBD hereafter) model [START_REF] Wright | Isolation by distance[END_REF], and has increasingly used as an indicator of adaptive divergence between populations. In the IBE model, natural selection, which results from several factors including climate, can indirectly increase neutral genetic and phenotypic differentiation between populations by promoting general barriers to gene flow [START_REF] Nosil | Divergent selection and heterogeneous genomic divergence[END_REF]Orsini et al., 2013, p. 201;[START_REF] Shafer | Widespread evidence for incipient ecological speciation: a metaanalysis of isolation-by-ecology[END_REF][START_REF] Wang | Isolation by environment[END_REF]. The IBE pattern is agnostic with respect to the underlying processes that generated it [START_REF] Wang | Isolation by environment[END_REF]; this pattern can be generated by different processes including natural selection against immigrants, sexual selection against immigrants, reduced hybrid fitness and biased dispersal. Although it can be difficult to map one or more processes to this pattern, testing for the IBE pattern is valuable for better understanding the ways in which natural selection shapes neutral genetic and phenotypic variation. Evidence from common garden experiments and IBE patterns can therefore contribute to understanding how genotypes, phenotypes and the environment interact to ultimately influence population divergence and potentially local adaptation.

Fruit trees are a major component of terrestrial ecosystems [START_REF] Petit | Some evolutionary consequences of being a tree[END_REF] and are grown in managed plantations and orchards to provide a variety of economically important products [START_REF] Boyd | The Consequence of Tree Pests and Diseases for Ecosystem Services[END_REF]. Recent breeding efforts have involved the repeated use of a limited number of cultivars sources of genetic material leading to a reduction in genetic diversity and the loss of valuable alleles at genes that are not directly targeted by human selection [START_REF] Myles | Genetic structure and domestication history of the grape[END_REF][START_REF] Warschefsky | Population genomic analysis of mango (Mangifera indica) suggests a complex history of domestication[END_REF][START_REF] Migicovsky | Genomic consequences of apple improvement[END_REF]. Wild relatives of crop fruit trees (or "CWR" for crop wild relative) harbor phenotypic and genetic diversity that are potentially highly valuable for future breeding programs in the context of climate change [START_REF] Zhang | Back into the wild-Apply untapped genetic diversity of wild relatives for crop improvement[END_REF][START_REF] Hoban | Sampling Wild Species to Conserve Genetic Diversity[END_REF][START_REF] Hübner | Tapping Diversity From the Wild: From Sampling to Implementation[END_REF]. However, rare of the studies which thoroughly investigate the phenotypic variation of CWR of fruit trees in relation to response to climate; most studies so far have focused on forest trees [START_REF] Kremer | Oaks: an evolutionary success story[END_REF]. Key traits to study in this context are related to plant carbon uptake. Indeed, climate impacts plant carbon uptake [START_REF] Aubin | Traits to stay, traits to move: a review of functional traits to assess sensitivity and adaptive capacity of temperate and boreal trees to climate change[END_REF], which latter known to impact fruit quality characteristics and production [START_REF] Demestihas | Ecosystem services in orchards. A review[END_REF]. These questions are urgent as native CWRs can be threatened by crop-to-wild gene flow from nearby domesticated trees [START_REF] Delplancke | Gene flow among wild and domesticated almond species: insights from chloroplast and nuclear markers[END_REF][START_REF] Cornille | Anthropogenic and natural drivers of gene flow in a temperate wild fruit tree: A basis for conservation and breeding programs in apples[END_REF][START_REF] Diez | Olive domestication and diversification in the Mediterranean Basin[END_REF][START_REF] Feurtey | Crop-to-wild gene flow and its fitness consequences for a wild fruit tree: Towards a comprehensive conservation strategy of the wild apple in Europe[END_REF][START_REF] Flowers | Cross-species hybridization and the origin of North African date palms[END_REF][START_REF] Liu | The complex evolutionary history of apricots: species divergence, gene flow and multiple domestication events[END_REF].

Therefore, the study of the genetic and phenotypic variation among populations of CWR fruit tree species is timely to guide future breeding programs; in addition, it may contribute to our understanding of the evolutionary and ecological drivers of population divergence, including climate.

The European crabapple, Malus sylvestris (L.) Mill, is a CWR and a major contributor to the cultivated apple genome [START_REF] Cornille | New insight into the history of domesticated apple: secondary contribution of the European wild apple to the genome of cultivated varieties[END_REF][START_REF] Cornille | The domestication and evolutionary ecology of apples[END_REF][START_REF] Cornille | A Multifaceted Overview of Apple Tree Domestication[END_REF][START_REF] Peace | Apple whole genome sequences: recent advances and new prospects[END_REF]. Substantial crop-to-wild gene flow has been observed across M. sylvestris populations in Europe (up to 23.1% of natural populations are introgressed by M. domestica [START_REF] Cornille | Anthropogenic and natural drivers of gene flow in a temperate wild fruit tree: A basis for conservation and breeding programs in apples[END_REF]). Crop-wild hybrids sampled in a forest in France and grown in controlled conditions showed superior fitness compared to wild seedlings [START_REF] Feurtey | Crop-to-wild gene flow and its fitness consequences for a wild fruit tree: Towards a comprehensive conservation strategy of the wild apple in Europe[END_REF]. Population genetics analyses also identified five pure (i.e., not introgressed by M. domestica) populations in Scandinavia, western France, eastern France, Eastern Europe and Italy [START_REF] Cornille | Anthropogenic and natural drivers of gene flow in a temperate wild fruit tree: A basis for conservation and breeding programs in apples[END_REF]. These five populations resulted from past contractions and expansions associated with the LGM (Cornille et al., 2013a[START_REF] Cornille | Anthropogenic and natural drivers of gene flow in a temperate wild fruit tree: A basis for conservation and breeding programs in apples[END_REF]. It remains unclear, however, whether these five populations, distributed across a large area with different climatic conditions, present phenotypic variation that could be the result of local adaptation to past and/or present climates.

We investigated the spatial phenotypic and genetic variation among populations of a major wild contributor to the cultivated apple, M. sylvestris, to test for adaptive divergence. Variation in plant growth and traits related to carbon uptake was measured in 584 M. sylvestris seedlings grown under controlled conditions and genotyped for 13 microsatellite markers. We first assessed the genetic status of each seedling (pure vs. crop-wild hybrid). Then, we compared growth traits and traits related to plant carbon uptake among seedlings belonging to different European genetic groups. We also formally tested the impact of geography (IBD) and ecology (IBE tested with phenotypic traits and climate) on genetic variation observed from 13 microsatellite markers. We investigated the following questions: 1) Does growth rate and carbon uptake trait vary between populations of the European crabapple? Are those traits heritable, and thus can population history predict seedling phenotype?; 2) Is there any association between phenotypic variation and genetic variation, taking into account geographic distance?; and 3) Is climate associated with neutral genetic diversity of the European crabapple, which could suggest local adaptation (i.e., ecological/adaptive divergence)?

Materials and Methods

Plant material, experimental design and trait measurements

A total of 584 seeds were collected from 90 M. sylvestris mother trees (three to 15 seeds per mother tree, Table S1) from six different geographical regions in Europe: Austria (N = 89, two sites), Denmark (N = 91, three sites), Spain (N = 39, one site), France (N = 220, eight sites), Italy (N = 32, one site), Romania (N = 117, seven sites) (Table S1).

In mid-April 2019, the 584 seeds were washed, sterilized (in 0.5% chlorine for 20 min), and vernalized for three months at 4°C in the dark in a mix of damp sand and vermiculite. Then, seeds were sowed in jiffy pellets and each pellet was randomly placed in a 20-hole array. Seeds were grown in controlled conditions for two months (from mid-July to mid-September 2019: 22 ±1•C, 60 ±5 % relative humidity, a 16:8 (L:D) photoperiod and a light level of 40-60 µmol m -2 .s -1 ). Each 20-hole array was rotated daily in the growth chamber to avoid any micro-environmental variation in plant response, and plants were watered weekly.

During the course of the two-month experiment, the number of leaves and the height of each seedling were recorded. Some accessions, due to the low germination rate, could not be recorded (i.e., height and number of leaves could not be recorded for 19 seedlings out of 584, N = 565, Table 1). Seedlings were measured every two or three days, starting from day 7-11 after the start of the experiment.

The last week of the experiment, the superficial flavonol and chlorophyll content and the nitrogen balance index (NBI) were measured in three leaves per seedling. Superficial chlorophyll content is the concentration of chlorophyll in the leaf epidermis (µg/cm²), and superficial flavonol content is an index of the flavonoid concentration (µg/cm²) in this upper layer and is related to phenol accumulation and UV protection. Leaf chlorophyll and flavonol content and NBI are parameters correlated with plant carbon uptake via photosynthesis. Flavonol is a phenolic compound that is also known to contribute to plant resistance, acclimation and adaptation to environmental constraints through various mechanisms, including its antioxidant activity. These traits were measured using a portable Dualex device (Force-A, Orsay, France), which uses a combination of fluorescence signals at various excitation bands to quantify pigments and chemical compounds. As carbon uptake related traits must be measured in the same day, a subsample of 257 seedlings out of the 565 seedlings (Table 1, numbers in brackets) was measured because of time limitation in a day. Seedlings measured for carbon uptake related traits were selected based on two criteria: having at least one seedling per mother tree and three seedlings per geographic site.

DNA extraction, microsatellite genotyping and genetic ancestry of the seedlings

At the end of the experiment, leaves of each seedling were sampled for microsatellite genotyping.

Genomic DNA was extracted with the NucleoSpin plant DNA extraction kit II (Macherey & Nagel, Düren, Germany) according to the manufacturer's instructions. Microsatellites were amplified by multiplex PCR with the Multiplex PCR Kit (QIAGEN, Inc.). We used 13 microsatellite markers, Ch01f02, Ch01f03, Ch01h01, Ch01h10, Ch02c06, Ch02c09, Ch02c11, Ch02d08, Ch03d07, Ch04c07, Ch05f06, GD12 and Hi02c07 in four multiplexes (MP01 to MP04; [START_REF] Cornille | New insight into the history of domesticated apple: secondary contribution of the European wild apple to the genome of cultivated varieties[END_REF]).

PCR was performed in a final reaction volume of 15 ml (7.5 ml of QIAGEN Multiplex Master Mix, 10-20 mM of each primer with the forward primer labelled with a fluorescent dye, and 10 ng of template DNA). We used a touch-down PCR program (initial annealing temperature of 60°C, decreasing by 1°C per cycle down to 55°C). Genotyping was performed at the GENTYANE platform (INRAE Clermont-Ferrand) on an ABI PRISM X3730XL, with 2 ml of GS500LIZ size standard (Applied Biosystems).

Alleles were scored with the GENEMAPPER 4.0 software (Applied Biosystems). We retained only multilocus genotypes presenting less than 10% missing data.

Clones or closely related individuals can bias inferences of population structure. We estimated the kinship coefficient between pairs of individuals (Fij) with SPAGeDI 1.5d [START_REF] Loiselle | Spatial genetic structure of a tropical understory shrub, Psychotria officinalis (Rubiaceae)[END_REF][START_REF] Hardy | SPAGeDI: a versatile computer program to analyse spatial genetic structure at the individual or population levels[END_REF], and removed highly genetically related individuals with Fij > 0.5.

The individual-based Bayesian clustering method implemented in STRUCTURE 2.3.3 [START_REF] Pritchard | Inference of population structure using multilocus genotype data[END_REF] was used to estimate the admixture between M. domestica and M. sylvestris, and the population genetic structure of M. sylvestris. STRUCTURE uses Markov Chain Monte Carlo (MCMC) simulations to infer the proportion of ancestry of genotypes from K distinct clusters. The underlying algorithm attempts to minimize deviations from Hardy-Weinberg and linkage disequilibria. K ranged from 1 to 10. Ten independent runs were carried out for each K and 500,000 MCMC iterations after a burn-in of 50,000 steps were used. CLUMPAK (Greedy algorithm) [START_REF] Kopelman | Clumpak: a program for identifying clustering modes and packaging population structure inferences across K[END_REF] was used to identify distinct modes in the 10 replicated runs for each K. STRUCTURE analyses were run for the full dataset (N = 584), plus 40 M. domestica genotypes included as a reference for the cultivated apple gene pool (Cornille et al., 2013b). The R package pophelper v2.3.0 was used [START_REF] Francis | POPHELPER: An R package and web app to analyse and visualise population structure[END_REF] to visualize bar plots. The amount of additional information explained by increasing K was determined using the ΔK statistic [START_REF] Evanno | Detecting the number of clusters of individuals using the software STRUCTURE: a simulation study[END_REF], as implemented in Structure Harvester [START_REF] Earl | STRUCTURE HARVESTER: a website and program for visualizing STRUCTURE output and implementing the Evanno method[END_REF].

However, ΔK provides statistical support for the strongest but not the finest population structure [START_REF] Puechmaille | The program structure does not reliably recover the correct population structure when sampling is uneven: subsampling and new estimators alleviate the problem[END_REF]. Natural populations can display a hierarchical genetic structure with fine-scale population structure. Visual inspection of the barplots was used to identify the K value for which all clusters have well assigned individuals, and where additional clusters at higher K values do not have well assigned individuals (indicating that we have reached the highest K value for which no new genuine clusters could be delimited). The K value we therefore considered corresponded to the finest one, which can be higher than the K value of the strongest population structure identified by ΔK.

Using the best K value inferred with STRUCTURE, we defined Pdom, the membership proportion of a seedling to the M. domestica gene pool; membership coefficients were used to define the genetic ancestry of each seedling: 1) seedlings with Pdom > 0.9, whose mother tree was likely misidentified in the field (referred to as "dom" hereafter); 2) seedlings with Pdom > 0.1, i.e., crop-wild hybrids (referred to as "cw" hereafter); then 3) seedlings with a membership coefficient > 0.9 to a given wild apple cluster were considered to be « pure » wild seedlings (referred to as "pure" hereafter); and 4) seedlings with a membership coefficient < 0.9 to a given wild apple gene pool were considered to be wild-wild hybrids ("ww", hereafter). In addition, "pure" seedlings were assigned to different populations (i.e., groups of seedlings with membership coefficient > 0.9 to a given wild gene pool). Two effects were then tested using statistical models below: the genetic status effect (i.e., dom, cw, ww, pure), and the wild apple population effect (i.e., corresponding to the "pure" populations detected with STRUCTURE).

Fitness proxy estimates

The fitness of each seedling was therefore estimated from growth and carbon related trait proxies.

The absolute growth rate (AGR [START_REF] Radford | Growth Analysis Formulae -Their Use and Abuse1[END_REF]), relative growth rate (RGR [START_REF] Briggs | A quantitative analyses of plant growth: part II[END_REF]), and whole AGR were estimated as follows (the traits considered were the height and the number of leaves of the seedling):

𝐴𝐺𝑅(𝑐𝑚/𝑑𝑎𝑦) = (𝑡𝑟𝑎𝑖𝑡 𝑡+1 -𝑡𝑟𝑎𝑖𝑡 𝑡 ) (𝑑𝑎𝑡𝑒 𝑡+1 -𝑑𝑎𝑡𝑒 𝑡 ) (1) 𝑅𝐺𝑅(𝑐𝑚/𝑑𝑎𝑦/𝑑𝑎𝑦) = 𝐴𝐺𝑅 𝑑𝑎𝑡𝑒 𝑡 (2) 𝑊ℎ𝑜𝑙𝑒𝐴𝐺𝑅(𝑐𝑚/𝑑𝑎𝑦) = 𝑡𝑟𝑎𝑖𝑡 𝑒𝑛𝑑 -𝑡𝑟𝑎𝑖𝑡 𝑏𝑒𝑔𝑖𝑛𝑛𝑖𝑛𝑔 𝑑𝑎𝑡𝑒 𝑒𝑛𝑑 -𝑑𝑎𝑡𝑒 𝑏𝑒𝑔𝑖𝑛𝑛𝑖𝑛𝑔 (3)
Note that for the whole AGR, the beginning of the experiment corresponded to days 7 and 11 for leaf and height measurements, respectively, while the last measurement was done at day 60. The internode ratio, which represents the ratio between the number of leaves and the height of the seedling at day 60, was also considered a fitness trait, as this value plays an important role in apple tree architecture [START_REF] Ripetti | Shaping the shoot: the relative contribution of cell number and cell shape to variations in internode length between parent and hybrid apple trees[END_REF].

Seven fitness proxies were therefore calculated for the full dataset (565 seedlings, Table 1): height_AGR, height_RGR, whole_height_AGR, leaf_AGR, leaf_RGR, whole_leaf_AGR and internode.

In addition, chlorophyll (Chl) and flavonol (Flav) content, and NBI, were measured in the subsample (257 seedlings, Table 1). A preliminary exploration of correlation and variation among phenotypic traits was carried out using a principal component analysis (PCA) with the FactoMineR R package [START_REF] Lê | FactoMineR: An R Package for Multivariate Analysis[END_REF].

Statistical analyses of fitness variation

A previous study demonstrated that crop-to-wild gene flow has an impact on early-stage growth rate [START_REF] Feurtey | Crop-to-wild gene flow and its fitness consequences for a wild fruit tree: Towards a comprehensive conservation strategy of the wild apple in Europe[END_REF]. The effect of the genetic status of seedlings (i.e., dom, cw, ww, pure, Table 1) on fitness variation among seedlings was therefore tested. A linear mixed model was fitted to the data as follows:

Fitnessijkl ~ μ + wild population of origini + genetic ancestry statusj + wild population of origini*genetic ancestry statusj + motherk+ eijkl (4), where μ is the overall mean, "wild population of origin" is the fixed effect of the population of origin of the seedling inferred with STRUCTURE, "status" is the fixed effect of the genetic status of the seedling (i.e., "pure", "dom", "ww", "cw"), the interaction between the two fixed effects, and "mother" is a normally distributed random effect with its own mean and variance parameters, and e is the residual. The mother tree of each seedling was used as a random factor to avoid pseudo-replication due to the presence of multiple half-siblings (i.e., from the same mother tree). We ran the model (4), but replaced the "status" effect by the "Pdom" fixed effect. We gradually removed interactions and effects depending on their significance. In addition, we evaluated the differences in the effect on trait variation using a contrast analysis. We fitted the data to the model using the lm4e R package [START_REF] Bates | Fitting linear mixed-effects models using lme4[END_REF].

For fitness proxies defined from the number of leaves (leaf_AGR, leaf_RGR and whole_leaf_AGR), a log link function was used and the residual distribution was fitted to a negative binomial distribution (function glm.nb in R package lme4). For fitness proxies defined from the height of the seedling (height_AGR, height_RGR, whole_height_AGR), and for chlorophyll and flavonol content, and NBI, a similar linear mixed model was run, but with a residual term that was assumed to be normally distributed.

Heritability estimates

Heritability estimates were computed using only pure and wild-wild M. sylvestris seedlings detected as above. We fitted each fitness proxy with a linear mixed model as follows:

Yijk = μ + Fi + Cj + eijk (5),
where Yijk is the fitness proxy (growth rate or carbon uptake related trait) of the k th seedling belonging to family i, member of the j th genetic cluster, μ the overall fixed mean of the population, Fi the random effect of the i th family, Cj the fixed effect of the j th genetic cluster and eijk the random error term. The model was fitted using REML (restricted maximum likelihood). Calculations were performed by the lme-function of the R-library nlme [START_REF] Pinheiro | nlme: Linear and Nonlinear Mixed Effects Models[END_REF]. The output of lme provides estimates for the variance components, the corresponding standard deviations (sd), and the best unbiased linear predictors (BLUP) for random effects. Genetic parameters were then calculated as follows:

-

𝑉𝑃

Test for isolation-by-ecology

Only pure and wild-wild hybrid M. sylvestris seedlings were selected for IBE analysis (N = 449, 21 sites, Table 1). The IBE pattern, i.e., the contribution of climate and phenotypic distances to the genetic structure taking into account geographical distance, was evaluated using a distance-based redundancy analysis (db-RDA). db-RDA can be used when the response variable is a distance matrix, here a genetic distance matrix (FST) across 21 sampled sites, and the explanatory variables are in vector form.

Explanatory variables were as follows : (i) the geographical distance between sampled sites which underlies an IBD process, represented by vectors with positive eigenvalues of a principal coordinate of neighbor matrix (PCNM) [START_REF] Borcard | All-scale spatial analysis of ecological data by means of principal coordinates of neighbour matrices[END_REF], which was applied to the geographical pairwise distance matrix between sampled sites computed with SPAGeDI 1.5d [START_REF] Hardy | SPAGeDI: a versatile computer program to analyse spatial genetic structure at the individual or population levels[END_REF]; 19 bioclimatic variables downloaded from the Worldclim2 database (30s resolution, https://www.worldclim.org/data/worldclim21.html) representing annual and seasonal trends and extremes averaged (ii) over the years 1970-2000 and averaged (iii) for the Pleistocene period (20K years ago) [START_REF] Gamisch | Oscillayers: A dataset for the study of climatic oscillations over Plio-Pleistocene time-scales at high spatial-temporal resolution[END_REF], which were used to test for an isolation-by-climate pattern (IBC, hereafter); and (iv) growth rate (N = 551, Table 1) and carbon uptake related traits (N = 239, Table 1) averaged per site, as well as chlorophyll and flavonoid content, which were used to test for an isolation-by-adaptation pattern, referred as to IBA hereafter.

To identify the variables that explained the genetic structure of M. sylvestris, a db-RDA using the "capscale" function [START_REF] Oksanen | Vegan: Community ecology package[END_REF] was run on a full model which included all investigated variables (i.e., PCNM components, growth rates, carbon uptake related traits, 19 bioclimatic variables).

The best variables were selected for an optimum model with the function "step" based on the Akaike Information Criterion (AIC). Because db-RDA does not provide information on the relative contribution of each variable of the model, a variance partitioning analysis was run using the "varpart" function from the R-package "vegan" [START_REF] Peres-Neto | Variation partitioning of species data matrices: estimation and comparison of fractions[END_REF].

Results

Genetic ancestry of seedlings

No clones or closely related individuals were detected (Figure S1) and therefore all 584 seedlings were included in the STRUCTURE analyses.

STRUCTURE revealed a clear spatial population genetic structure of M. sylvestris in Europe as well as crop-wild admixture (Figures 1 andS2). For K = 2, the analysis recovered a group that included M. domestica and the western M. sylvestris samples (green) and another group that consisted of the Eastern European samples (red). For K = 3, the western group was split into two groups, one comprising M.

domestica and Spanish and Italian M. sylvestris seedlings (black), and another comprising the remaining western samples (green); the Central European group was also recovered. For K = 4, the Eastern European samples were split into two groups: an Austrian group and a Romanian group. For K = 5, there was a clear east/west substructure in France. For K = 6, a sixth cluster comprising the Danish individuals was found. For K = 7, the Italian population split into two groups. For K = 8, the population from one site in eastern France (Lor) was identified as a new cluster. When K > 9, STRUCTURE did not reveal any further substructures, with only additional cluster with highly admixed individuals (Figure S2). Therefore, although the ΔK indicated that the most likely K value was five (Figure S3), K = 8 was the finest population structure and was therefore retained in subsequent analyses.

For K = 8, we found that the M. domestica reference varieties were admixed with the Italian and Western European M. sylvestris. Conversely, we detected 68 M. sylvestris seedlings with Pdom > 0.1 (considered as crop-wild hybrids), corresponding to 11.6% of the seedlings (N = 584, Figures 1, S4 and S5, Table 1). We also found 21 seedlings with a membership coefficient to the M. domestica gene pool > 0.9, corresponding to 4% of the seedlings. Nearly all Spanish seedlings were assigned to the M. domestica gene pool with membership coefficients > 0.1 (i.e., 26 crop-wild hybrids and 13 individuals assigned to the M. domestica gene pool) and showed admixture only with the wild Italian purple gene pool (Figure S4). 33 individuals could not be assigned to any cluster (i.e., individuals with a membership coefficient < 0.5 to any cluster).

We therefore identified 68 "cw", 21 "dom", 167 "ww" and 282 "pure" seedlings (Table 1, N = 551).

After removing cw hybrids (N = 68), seedlings sampled from misidentified mother trees (N = 21), the M. domestica reference samples (N = 40) and individuals with a membership coefficient < 0.5 to any cluster, seven wild apple populations (i.e., groups of seedlings with a membership coefficient > 0.5 to a wild apple cluster) were defined: French Western ("FR-W", N = 77), French Eastern ("FR-E", N = 50), French Lorraine ("FR-Lor", N = 28), Danish (DA, N = 78), Italian ("IT", N = 27), Austrian ("AUT", N = 81) and Romanian ("RO", N = 108) (Figure S6). Each M. sylvestris population showed a high level of genetic variation (Table S2). The Romanian population was the most genetically differentiated population and was close to the Austrian population; the Danish and French Western populations were genetically similar (Figure S7).

No effect of seedling status on phenotypic variation

Variation and correlations among traits are presented in Figures S8 to S11. Heritability estimates were moderate to high for all traits except growth rate based on leaf number (Table S3). However, these estimates need to be taken with caution given the limited sample size, as reflected by the large standard deviations.

We did not find any significant effect of seedling status (i.e., pure, ww, cw, dom) (Figure 5, Table S4, Figure S12) or Pdom (Table S5, Figure S13) on phenotypic traits (i.e., leaf and height AGR, leaf and height RGR, whole leaf and height AGR). We therefore removed the seedling status and Pdom effects from the model 4, as well as dom and cw individuals. We therefore only considered wild apple seedlings (i.e., pure and ww, N = 449), and focused on the 'wild population of origin 'effect (Table S6).

Significant variation in growth rates and chlorophyll content among populations

Mean height variation along the course of the experiment among seedlings from different populations is shown in Figure 2. There was significant variation among seedlings from different populations in certain growth-related traits (Table 2). On average, seedlings belonging to the Austrian population were taller (+11 cm, P = 0.047) whereas Romanian (-14.9 cm, P = 0.008) and Italian (-18.7 cm, P = 0.044) seedlings were shorter (Figure 2) than seedlings from other populations. Seedlings from other populations did not show a significant difference in height. In addition, the number of leaves and height traits were negatively correlated, r = -0.3, P < 0.001). The Austrian population presented the lowest number of leaves (average = 5, sd = 4) whereas seedlings belonging to the Romanian population had the highest number of leaves (average = 8, sd = 7, Figure S15). The Romanian population also had the largest internode (+ 0.02 leaf/cm, P = 0.024).

Chlorophyll content differed among populations with seedlings from the Italian population producing on average more chlorophyll (+4.14 µg/cm², P = 0.039, Figure S16) than seedlings from other populations. Flavonol content and NBI did not differ significantly among populations.

Significant IBD and IBC

Correlation plots between bioclimatic variables are provided in Figures S17 andS18; however, all variables were included in the analysis as db-RDA can cope with correlated variables. The optimal model was chosen according to its best AIC value. The optimal model explained up to 25.9% of the genetic structure (Adj-R² = 69.9%, P = 0.001) and contained seven variables (four geographic and three bioclimatic variables) (Table 3): the geographical distance is represented by the 1st, 2nd, 3rd and 6th axis of the PCNM analysis and three past climatic variables (Bio3: isothermality; Bio6: minimum temperature of coldest month; Bio 9: mean temperature of driest quarter). In total, IBD explained 47% of the variance of the wild apple tree population genetic structure, whereas IBC explained 22% (Figure 3). Taking geographical distance into account, we did not find a pattern of IBA i.e., covariation between phenotype and genetic divergences.

Discussion

This study is the first to take into account the population genetic structure as well as the phenotypic variation of a contributor to the cultivated apple genome [START_REF] Cornille | New insight into the history of domesticated apple: secondary contribution of the European wild apple to the genome of cultivated varieties[END_REF], to investigate ecological divergence. Bayesian clustering revealed seven M. sylvestris populations across Europe with a substantial number of seedlings (11.6%, mainly from Western Europe) introgressed by M. domestica, although this figure is less substantial than previously reported (Cornille et al., 2013b[START_REF] Cornille | Anthropogenic and natural drivers of gene flow in a temperate wild fruit tree: A basis for conservation and breeding programs in apples[END_REF][START_REF] Feurtey | Crop-to-wild gene flow and its fitness consequences for a wild fruit tree: Towards a comprehensive conservation strategy of the wild apple in Europe[END_REF]. Although the crop-wild hybrid status of seedlings did not impact phenotypic variation, we observed phenotypic variation among crabapple populations when grown in controlled conditions.

Phenotypic variation was found for growth and chlorophyll content among populations of the European crabapple from different climates in Europe. Based on the IBA pattern, this phenotypic variation was not adaptive. However, the IBC pattern revealed that climate was a driver of genetic differentiation between populations. Given that the IBC pattern was still found after accounting for IBD, this implies that there are sufficient levels of local adaptation to LGM climate to reduce gene flow among populations. The European crabapple may therefore be locally adapted to the past climate conditions of the LGM. The lack of signal of adaptive phenotypic divergence suggests that traits other than the ones we investigated in this study may be under divergent selection. The results of this study pinpoints adaptive divergence related to climate in a wild contributor to a fruit tree crop genome, which is a starting point for future breeding programs and mitigating the impact of climate change of CWR of an emblematic temperate fruit tree.

Ongoing crop-to-wild gene flow in the European crabapple

We revealed substantial gene flow from M. domestica to the European crabapple, with 11.8% of seedlings, mostly from Western Europe, introgressed by M. domestica. Introgression rates were lower compared to previous studies (i.e, 37% in Cornille et al. (2013b) and 23.1% in [START_REF] Cornille | Anthropogenic and natural drivers of gene flow in a temperate wild fruit tree: A basis for conservation and breeding programs in apples[END_REF]).

However, these studies genotyped more mother trees (i.e., N = 756 and N = 1,889, respectively), which could explain the difference in estimates of crop-to-wild gene flow. The results described here highlight the fact that crop-to-wild gene flow is still ongoing in the European crabapple. The Spanish seedlings sampled here were the progeny of trees growing in a location that is known to have high levels of M.

domestica introgression (pers. comment. G. Alins). It is even possible that the mother trees of these seedlings were M. domestica and not M. sylvestris. The inclusion of reference cultivated apple samples mainly from Western Europe may decrease the probability of detecting crop-to-wild introgression events in wild populations from Eastern and Northern Europe. The lower crop-to-wild introgression rates in wild seedlings from Eastern Europe can also be explained by their physical distance from cultivated apple orchards. Indeed, distance can be a natural barrier to hybridization between M.

domestica and its wild relative [START_REF] Larsen | A high-throughput method for genotyping S-RNase alleles in apple[END_REF], which we confirmed in this study. The position of a M. sylvestris individual in a forest may also impact its level of introgression. Indeed, M. sylvestris trees are often found in forest gaps and at the forest edge, corresponding to their ecophysiological preferences (i.e., preference for light and low competition). The effect of the location of the trees in the forest on the level of crop-to-wild introgression needs to be studied further.

The consequences of crop-wild introgression on phenotypic variation between crop and wild individuals have been studied more in annual crops (e.g., maize, wheat, lettuce, rice) [START_REF] Ellstrand | Introgression of Crop Alleles into Wild or Weedy Populations[END_REF] than in perennial fruit trees. One study has shown that crop-wild hybrid seedlings of the European crabapple have higher growth rates and showed earlier germination than wild apple seedlings [START_REF] Feurtey | Crop-to-wild gene flow and its fitness consequences for a wild fruit tree: Towards a comprehensive conservation strategy of the wild apple in Europe[END_REF]. We did not detect any effect of the status of a seedling (pure, wild, crop-wild, dom) or the level of introgression (Pdom) on growth and carbon uptake related fitness proxies. This could be due to the low number of samples from the cw and dom categories. Note that we did not test the variation in germination rate among seedlings as germination can be strongly impacted by stratification conditions.

No adaptive phenotypic variation among populations, but signs of local adaptation to past climate in the European crabapple

Under controlled conditions, seedlings from the different populations were found to have significantly different growth and morphology, but IBA analyses indicated that this variation was likely not adaptive.

Seedlings belonging to the Austrian population were the tallest, had the highest absolute growth rate and the lowest number of leaves; by contrast, Romanian seedlings were the shortest, had the lowest absolute growth rate and the highest number of leaves. Italian seedlings had the highest chlorophyll content. The seedlings belonging to the Austrian population may be fitter in the climate conditions simulated in this experiment. We tested whether this phenotypic variation was adaptive. However, taking geographic distance into account, we did not find any significant covariation between genetic and phenotypic variation. This suggests a lack of divergent selection on traits related to carbon uptake or growth that are often associated with plant responses to climate [START_REF] Bussotti | Functional traits and adaptive capacity of European forests to climate change[END_REF]. Therefore, the phenotypic variation we observed among populations under controlled conditions may be the result of genetic drift alone; alternatively, the traits we selected (thought to be related to responses to climate)

are not good candidates for investigating divergent selection. Leaf mass per area (LMA) and foliar nitrogen content demonstrated can be future targeted parameter to assess the responses of apple seedling to environmental stress [START_REF] Bussotti | Functional traits and adaptive capacity of European forests to climate change[END_REF]. Another explanation could be that we did not phenotype enough seedlings from each genetic group. Indeed, we observed a high variation in each phenotypic trait and in their heritability estimates, suggesting that the traits we studied may be relevant but that a larger number of seedlings should be phenotyped and analyzed (e.g., (Klein et al., 1973)). However, some studies have found that even with large sample sizes, the standard error of heritability estimates can still be large and vary greatly between experimental designs [START_REF] Visscher | A General Unified Framework to Assess the Sampling Variance of Heritability Estimates Using Pedigree or Marker-Based Relationships[END_REF]. The fairly high heritability estimates for most of the traits considered here could be seen as consistent with rather weak within population selection, enabling the maintenance of ample additive genetic variation [START_REF] Wheelwright | The effect of trait type and strength of selection on heritability and evolvability in an island bird population[END_REF]. Furthermore, high variation in seedling traits combined with high heritability estimates could suggest that there is large room of genetic material for adaptation to work on. In addition, the population of origin of the seedlings did not explain all phenotypic variation. Even though we found an effect of the population of origin on phenotypic traits, its contribution was relatively low (e.g., model 4, R 2 for height = 0.119, and R 2 for height AGR= 0.047). Environment (e.g., climate) and interaction between genotype and environment could also impact fitness.

As M. sylvestris is distributed across gradient, we further investigated the role of climate in shaping the genetic variation among populations of the European crabapple, without considering phenotypic trait variation. We tested for an IBE pattern, where the pattern of neutral genetic variation covaries with ecological variables (here climate). There was no combined effect of geographic and climatic distance (IBD ∩ IBC), which allowed us to assess the contribution of these processes separately [START_REF] Wang | Isolation by environment[END_REF]. We showed that IBD and IBC played a significant role (R 2 adj = 47% and R 2 adj = 22%, respectively) on the genetic differentiation of European crabapple populations. Weak but significant IBD has been previously identified in wild apple relatives of the cultivated apple (i.e., M. sylvestris, M. orientalis and M. sieversii) suggesting they have high dispersal capacities (Cornille et al., 2013b[START_REF] Cornille | Anthropogenic and natural drivers of gene flow in a temperate wild fruit tree: A basis for conservation and breeding programs in apples[END_REF]. Weak IBD is explained by self-incompatibility systems that prevent self-fertilization [START_REF] Brown | Genetics of apple[END_REF], pollen dispersal by bees and flies (Syrphidae) and endozoochorous seed dispersal by large mammals such as ungulates, wild pigs, brown bears or humans (Larsen et al., 2006). We show that in addition to IBD, IBC persisted after taking geographic distance into account. Climate can impose divergent selection pressures on different locations and thus reduce gene flow between populations, so that IBC contributes to genetic differentiation. The main variables explaining genetic differentiation in the European crabapple were related to temperature during the LGM. This suggests that the European crabapple may be locally adapted to its past temperature but not to its current climate. Local adaptation to current climate is well studied in wind-dispersed trees [START_REF] Savolainen | Ecological genomics of local adaptation[END_REF][START_REF] Kremer | Oaks: an evolutionary success story[END_REF]Pyhäjärvi et al. 2020). However, to our knowledge no study has shown local adaptation to past climate conditions in a tree species.

Additional factors other than climate can also shape adaptive divergence between populations.

Malus sylvestris is a pioneer species that needs high levels of light and is not very competitive. Local adaptation to biotic factors such as the presence of other species is possible. Competition for light with other species such as the European beech (Fagus sylvatica) could be a source of divergence between populations. Local adaptation of fruit trees to biotic factors, including parasites [START_REF] Olvera-Vazquez | Experimental test for local adaptation of the rosy apple aphid (Dysaphis plantaginea) to its host (Malus domestica) and to its climate in Europe. PCI Ecology Pre-registration version[END_REF], deserves further investigations. Besides selection, the potential role of phenotypic plasticity in enabling growth and optimal fitness in changing environments also needs to be carefully evaluated (Benito Garzón et al., 2011).

Further investigations needed on local adaptation and plasticity in response to climate in the

European crabapple

Our study raises concerns regarding the future of wild apple populations and their current vulnerability to current climate change. However, the adaptation of tree species to climate remains complex [START_REF] Bussotti | Functional traits and adaptive capacity of European forests to climate change[END_REF]. For instance, in Eucalyptus camaldulensis, variation in leaf traits and performance proxies was unrelated to the climate of genotype provenance [START_REF] Asao | Leaf trait variation is similar among genotypes of Eucalyptus camaldulensis from differing climates and arises in plastic responses to the seasons rather than water availability[END_REF], whereas variation in several photosynthetic traits was clearly related to the climate of genotype provenance across Australia [START_REF] Dillon | Photosynthetic variation and responsiveness to CO2 in a widespread riparian tree[END_REF]. In contrast, collective differences in leaf morphology and photosynthetic physiology, in several Populus species may be adaptive for differences in growth season length, temperature and insolation [START_REF] Keller | Climate-driven local adaptation of ecophysiology and phenology in balsam poplar, Populus balsamifera L. (Salicaceae)[END_REF][START_REF] Kaluthota | Higher photosynthetic capacity from higher latitude: foliar characteristics and gas exchange of southern, central and northern populations of Populus angustifolia[END_REF]. Further investigations on local adaptation and plasticity to climate or biotic factors in the European crabapple are therefore needed. Genomic data will be particularly useful for determining the relative influence of adaptive and neutral processes on climate-or biotic-driven divergence by screening genomes from different populations in Europe.

Comparing the fitness of seedlings from different populations in reciprocal transplants will also be important to further test for local adaptation. Our study therefore raises questions regarding the processes of local adaptation of fruit trees, and is a starting point for apple breeding programs. Npure: number of seedlings assigned to a wild gene pool with a membership coefficient > 0.9 ; Nww, number of wild-wild hybrids (i.e., seedlings with a membership coefficient > 0.1 to a wild gene pool other than its own wild gene pool and a membership coefficient < 0.1 to the M. domestica gene pool); Ncw: number of crop-wild hybrids (i.e., seedling assigned to the M. domestica gene pool with a membership coefficient > 0.1). Nno cluster : seedlings that could not be assigned to any defined gene pool; Total measured for phenotypic traits : number of individuals measured for each phenotypic trait and included in the statistical analyses, the number in brackets represents the initial sample size before data were filtered for statistical analyses. Wild population name: populations defined with STRUCTURE at K=8 excluding crop-wild hybrids and seedlings from misidentified mother trees (i.e., including only wild pure and wild-wild hybrids).

  the additive genetic variance: 𝑉𝐴 = 4𝜎 𝐹 2 𝑤ith 𝜎 𝐹 2 representing the between-family variance the corresponding coefficient of variation: 𝐶𝑉𝐴 = ξ𝑉𝐴 𝜇 the phenotypic variation: 𝑉𝑃 = 𝜎 𝐹 2 + 𝜎 𝐸 2 , with 𝜎 𝐸 2 representing the residual variance the corresponding coefficient of variation: 𝐶𝑉𝑃 = ξ𝑉𝑃 𝜇 -Narrow-sense heritability: ℎ 2 = 𝑉𝐴 𝑉𝑃 -Dickerson's approximation for its standard deviation: 𝑠𝑑(ℎ 2 ) ≈ 4𝑠𝑑(𝜎 𝐹 2 )

Figure 1 .

 1 Figures and Tables Figure 1. Bayesian clustering of the Malus sylvestris seedlings sampled in this study (N = 584) and the reference samples of Malus domestica (N = 40) inferred with STRUCTURE for K = 8, and its associated map of mean membership per sampled site. Each individual is represented by a vertical bar partitioned into clusters. Visualization was improved by sorting genotypes by country; countries are separated by a white line. The reference M. domestica reference samples are shown on the far left of the map in the Atlantic. Circle size is proportional to the number of individuals within the cluster (scale shown on the top right-hand corner).

Figure 2 .

 2 Figure 2. Mean height of apple seedlings measured over the time of the experiment in controlled conditions (including pure and wild-wild hybrid seedlings, N = 449, and seedlings assigned to the M. domestica gene pool, N = 21, as detected with STRUCTURE for K=8). The 40 reference M. domestica individuals were not measured under controlled conditions thus are not shown here. Vertical lines represent the standard deviation. Populations: AUT (N = 81), DA (N = 78), DOM (N = 21, includes 13 Spanish genotypes and seedlings from other countries), FR-E (N = 50), FR-Lor (N = 28), FR-W (N = 77), IT (N = 27), RO (N = 108).

Figure 3 .

 3 Figure 3. Variance partitioning analysis of the db-RDA results obtained for Malus sylvestris (Nsites = 21, 13 microsatellite markers). Variation of the site pairwise genetic differentiation (FST) is explained by the variables generating isolation-by-distance (geographical distance) and isolation-byclimate (with three bioclimatic variables during the last glacial maximum: Bio3, isothermality; Bio6, minimum temperature of coldest month; Bio 9: mean temperature of driest quarter).

Table 1 . Number of M. sylvestris seedlings used in this study for population genetic analyses inferred with STRUCTURE for K = 8 with 13 microsatellite markers and phenotyping (growth and carbon-uptake related traits).

 1

							Total
							measured	Wild
	Clusters	Npure	Nww	Ncw	Ndom	Nno cluster	for	population
							phenotypic	name
							traits
	Q1 (light green)	32	46	7	0	10	92	FR-W
	Q2 (yellow)	0	52	5	0	4	57	FR-E
	Q3 (lor)	28	1	0	0		28	FR-Lor
	Q4 (blue)	61	21	1	0	6	85	DA
	Q5 (purple)	23	4	3	0	4	34	IT
	Q6 (dark green)	66	17	1	0	1	83	AUT
	Q7 (red)	77	34	5	0	0	113	RO
	Q8 (black -M. domestica)	40	0	46	21	8	73	-
	Total	287	175	68	21	33	551 (584)
	Total measured for height and number of leaves	282	167	63	21	32	533 (565)

Table 2 . Final model depicting effects of the Malus sylvestris population to which each seedling belonged (i.e., cluster inferred with STRUCTURE at K=8) on phenotypic traits (i.e., height, number of leaves, internode, chlorophyll and flavonol content, NBI) measured in 533 individuals.

 2 Variables in green are significant (P < 0.05).

	Explanatory variable		Cluster		Mother		Model		Mother
	Fitness	Χ 2	P-value	df	REML	Standard Deviation	AIC	R²	Corrected R²	R²
	Height_AGR 17.863 0.007***	6	1,229	0.204	1248	0.047	0.091	0.044
	Height_RGR	12.846	0.045*	6	-2,264	0.006	-2245	0,041	0.147	0.106
	Leaf_AGR	-	-	-	-	-	-	-	-	-
	Leaf_RGR	-	-	-	-	-	-	-	-	-
	Height whole AGR	22.243	1.00e-03***	6	630	0.175	650	0.074	0.192	0.118
	Leaf whole AGR	36.326	2.38e-06***	6	-1,277	0.009	-1,258	0.09	0.118	0.028

***: P-value <0.001; **: 0.01< P-value <0.001; *: 0.05< P-value <0.01; AIC: Akaike Indice Criterion.

Acknowledgements

We thank the Laboratoire d'Excellence BASC (Biodiversité, Agroécosystèmes, Société, Climat), the Institut Diversité Écologie et Évolution du Vivant (IDEEV), the European LEADER program and ATIP-Avenir CNRS Inserm for funding. We are grateful to the INRAE MIGALE bioinformatics platform (http://migale.jouy.inra.fr) for providing help and support, in particular Véronique Martin, Eric Montaubon and Valentin Loux. We also thank Adrien Falce, Olivier Langella and Benoit Johannet for help and support on the INRAE Génétique Quantitative et Evolution-Le Moulon lab cluster and the Plateforme de Génotypage GENTYANE INRAE UMR 1095. We thank Einar Flensted-Jensen, Michel

Bonnessee, Alberto Dominici, Jean-Luc Ricaud, Eric Wolff, Alain Guinet, Line Caminade, for providing seeds, Richard Le Menn, Bernard Gambier. USDA is an equal opportunity provider, employer, and lender. Mention of trade names or commercial products is solely for the purpose of providing specific information and does not imply recommendation or endorsement by the U.S. Department of Agriculture. AR and TU were partly funded through project PN2019-2022/19270201 -BIODIVERS 3.

Authors contributions

AC, GV, AR, SB, TU conceived and designed the experiments; AC, GV, AT, TU, TK obtained the funding; AC, GV, AT, TU, KAO, SV, RR, XC, TK, CR sampled the material; XC, CR, AV, AR, GL, KAO, RR, MLG, HB, VC, HC, SV, MF performed the molecular biology analyses; AC, AF, KomAvi and XC analyzed the data. The manuscript was written by AC, KomAvi and AF, with essential input from other co-authors.