Pierrick Labbé
email: pierrick.labbe@ed.ac.ukrhh

Nicolas Sidos

Michel Raymond

Thomas Lenormand

RESISTANCE GENE REPLACEMENT IN THE MOSQUITO CULEX PIPIENS: FITNESS ESTIMATION FROM LONG TERM CLINE SERIES

Keywords: overproduced esterases, selection, trade-off, adaptation

How adaptation appears and is later refined by natural selection has been the object of intense theoretical work. However the testing of these theories is limited by our ability to estimate the strength of natural selection in nature. Using a long-term cline series, we estimate the selection coefficients acting on different alleles at the same locus in order to analyse the allele replacement observed in the insecticide resistance gene Ester in the mosquito Culex pipiens in the Montpellier area, southern France. Our method allows us to accurately account for the resistance allele replacement observed in this area since 1986. A first resistance allele appeared early, which was replaced by a second resistance allele providing the same advantage but at a lower cost, itself being replaced by a third resistance allele with both higher advantage and cost. It shows that amelioration of the adaptation (here resistance to insecticide) through allele replacement was successively achieved by selection of first a generalist allele (i.e. with a low fitness variance across environments) and later of a specialist allele (i.e. with a large fitness variance across environments). More generally, we discuss how precise estimates of the strength of selection obtained from field data help understand the process of amelioration of adaptation.

"Without extensive knowledge of natural selection in the wild, we have no idea how relevant experiment or theory are to the evolution of natural populations" [START_REF] Endler | Natural selection in the wild[END_REF].

Twenty years after ENDLER's famous monograph, many advances have been made in the theory of adaptation. Some predictions made by this theory have been tested in the lab, but little insight has been gained into the process in nature. The main advance has been the shift from a strict micromutationnal view to one when mutations of larger effect also played a role.

Several experimental studies support this view (see review in [START_REF] Orr | The genetic theory of adaptation: a brief history[END_REF]. When adaptation to a new habitat is like a sequential approach towards a phenotypic optimum, mutations of large effect will tend to occur early and be followed by mutations of smaller effects 'refining' the adaptation [START_REF] Hartl | Compensatory Nearly Neutral Mutations: Selection without Adaptation[END_REF][START_REF] Barton | Evolutionary biology: The geometry of adaptation[END_REF][START_REF] Orr | The Population Genetics of Adaptation: The Distribution of Factors Fixed during Adaptive Evolution[END_REF][START_REF] Orr | The evolutionary genetics of adaptation: a simulation study[END_REF][START_REF] Barton | Understanding quantitative genetic variation[END_REF].

Adaptation to a new environment involves two types of traits; i) traits that change to match the new environmental challenge, and ii) traits that are not involved in this environmental change and have to remain unchanged. "Amelioration" of adaptation (sensu [START_REF] Cohan | Amelioration of the deleterious pleiotropic effects of an adaptive mutation in Bacillus subtilis[END_REF] occurs therefore in two directions: improving traits from set 1, and correcting the correlated (or 'pleiotropic') changes that may have occurred on traits from set 2 because of changes that occurred on traits in set 1. We will designate below these two modes of amelioration as being 'direct' or 'compensatory', respectively. Most new adaptive mutations affect these two sets of traits together, by producing traits that better match the environment but also modifying some traits that should not change, generating conflicting selection pressures and impeding the rate of adaptation [START_REF] Caspari | Pleiotropic gene action[END_REF][START_REF] Wright | Evolution and the genetics of populations[END_REF][START_REF] Carrière | Life-history cost associated with the evolution of insecticide resistance[END_REF]. It is, however, difficult to disentangle these different selection pressures in nature. Moreover, this process of amelioration can take several routes at the genetic level: it can either involve several loci (e.g. a modifier gene with a compensatory effect) or only a single locus repeatedly (allele replacement) [START_REF] Cohan | Amelioration of the deleterious pleiotropic effects of an adaptive mutation in Bacillus subtilis[END_REF].

Additionally, although less commonly appreciated, more complex molecular processes such as gene duplication may also be involved on a short time-scale [START_REF] Labbé | Independent duplications of the acetylcholinesterase gene conferring insecticide resistance in the mosquito Culex pipiens[END_REF]. While several examples of these processes have been described in laboratory studies (e.g. LENSKI 1988a;LENSKI 1988b;[START_REF] Cohan | Amelioration of the deleterious pleiotropic effects of an adaptive mutation in Bacillus subtilis[END_REF], it is difficult to study them in nature without precise methods to estimate selection coefficients and without the knowledge of the genetic bases of the adaptation.

In this paper, we developed an approach allowing us to precisely measure selection coefficients in order to study this process of amelioration in nature. We used a well-known case study, the evolution of organophosphate insecticide (OP) resistance in the mosquito Culex pipiens (vector of West Niles encephalitis, filariasis, etc.). In particular, we focused on the allele replacement that occurred at the Ester locus in the Montpellier area (Southern France) during the 1990's and 2000's [START_REF] Guillemaud | Evolution of resistance in Culex pipiens: allele replacement and changing environment[END_REF][START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF]. The Ester superlocus codes for detoxifying carboxylester hydrolases (or esterases). The overproduction of these esterases is one of the major resistance mechanisms to OP in C. pipiens (see for review [START_REF] Raymond | Insecticide resistance in the mosquito Culex pipiens: what have we learned about adaptation?[END_REF]. Several resistance alleles, each corresponding to a distinct overproduced esterase, have been described. They are selected for in insecticide treated areas (i.e. a selective advantage as they survive better in this environment), but they are costly (i.e. confer a fitness disadvantage such as lower mating success, lower survival, etc. in absence of treatment) and thus selected against in non-treated areas [START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF]. No estimates of the relative fitness of these three resistance alleles are available so far.

We are still largely ignorant as to the precise mechanisms of amelioration operating in this example and would like to know if these allele replacements involved alleles increasing their advantage in treated area (s), decreasing their cost (c) or both. It is important to stress at this point that whether an allele replace another does not simply follow from s and c values, but also depends in a non-trivial way on gene flow and habitat spatial structure [START_REF] Nagylaki | Patterns of Multiallelic Polymorphism Maintained by Migration and Selection[END_REF]. Although observing gene replacement allows qualitative inferences about the relative fitness of the competing alleles, only quantifying differences in fitness and their components (s and c) will enable us to discriminate between distinct scenarios of amelioration (direct or compensatory) and measure the net fitness change occurring during the process of amelioration.

The problem is that identifying such a subtle process requires precise methods to disentangle the relative values of s and c among adaptive alleles: while it is relatively easy to measure large fitness differences among two alleles (e.g. between susceptible and resistance alleles), it is more difficult when the differences are slight (e.g. between two resistance alleles) and a greater number of alleles are involved. In laboratory and model organism (especially microbes) studies it is possible to measure selection coefficient with a precision of less than 1% (e.g. [START_REF] De Gelder | Combining mathematical models and statistical methods to understand and predict the dynamics of antibiotic-sensitive mutants in a population of resistant bacteria during experimental evolution[END_REF][START_REF] De Visser | Clonal interference and the periodic selection of new beneficial mutations in Escherichia coli[END_REF]. However, despite a long history of estimating the strength of natural selection in nature (see [START_REF] Manly | The statistics of natural selection on animal populations[END_REF][START_REF] Endler | Natural selection in the wild[END_REF]HOEKSTRA et al. 2001, for review), this precision has never been reached with field data. The study of spatial and temporal frequency variation of adapted alleles has been one of the most accurate methods of estimating natural selection (e.g. [START_REF] Haldane | The theory of a cline[END_REF][START_REF] Kettlewell | The study of a cline[END_REF][START_REF] May | Gene frequency clines in the presence of selection opposed by gene flow[END_REF][START_REF] Mallet | Inference from Clines Stabilized by Frequency-Dependent Selection[END_REF][START_REF] Mallet | Estimates of Selection and Gene Flow from Measures of Cline Width and Linkage Disequilibrium in Heliconius Hybrid Zones[END_REF][START_REF] Mani | Theoretical-Models of Melanism in Biston betularia -a Review[END_REF][START_REF] Mani | Peppered moth revisited: analysis of recent decreases in melanic frequency and predictions for the future[END_REF][START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF][START_REF] Cook | The rise and fall of the Carbonaria form of the peppered moth[END_REF][START_REF] Hoekstra | Ecological genetics of adaptive color polymorphism in pocket mice: geographic variation in selected and neutral genes[END_REF]. However, at least two issues are crucial to obtaining accurate estimates with this method. The first issue is disentangling the effects of migration and selection on frequency variation (e.g. [START_REF] Brakefield | The Reliability of Estimates of Migration in the Peppered Moth Biston betularia and Some Implications for Selection-Migration Models[END_REF]. This problem can be overcome by estimating migration directly (e.g. using mark-recapture, [START_REF] Brakefield | The Reliability of Estimates of Migration in the Peppered Moth Biston betularia and Some Implications for Selection-Migration Models[END_REF]LIEBERT 1990, or neutral genetic markers, HOEKSTRA et al. 2004), or by estimating migration from patterns of linkage disequilibria among locally adapted alleles [START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF], an approach similar to that used to study hybrid zones [START_REF] Barton | Analysis of Hybrid Zones[END_REF][START_REF] Mallet | Inference from Clines Stabilized by Frequency-Dependent Selection[END_REF]. The second difficulty is that inference of selection depends on the validity of the underlying migration-selection model. In most cases it is necessary to assume that the observed spatial frequency pattern is at migration -selection equilibrium, precluding the study of transient allele replacement.

In this paper, we developed a powerful approach that does not assume migrationselection equilibrium, and which comes close to the precision obtained under laboratory conditions. We used this approach to estimate the selection coefficients of the Ester alleles in C. pipiens from the pattern of resistant allele replacement at this locus in Montpellier area. We used the 15-year Ester allele frequency series to estimate the magnitude of the two fitness components, cost (c) and selective advantage (s), conferred by each resistance Ester allele, by combining the information of both spatial and temporal frequency variation. We also investigated the effect of dominance among the different alleles on the quality of our estimates. In addition we looked for evidence that the selection regime had changed or that compensatory modifiers had spread in these populations. Finally, we discuss what this case study tells us about the processes of amelioration in natural populations.

MATERIAL AND METHODS

In the Montpellier area, the mosquito Culex pipiens is treated with OP insecticides on a coastal belt delimiting two areas (Figure 1): a treated area close to the Mediterranean Sea, where resistant alleles tend to be frequent due to their selective advantage (s), and a nontreated area more inland where resistant alleles are less frequent due to their cost (c). The frequency of resistant alleles thus display a clinal shape along a transect from the sea (treated) to the inland (untreated). At equilibrium between migration and selection, the rate of decline in the frequency of resistance is proportional to the intensity of migration (σ), and depends on the magnitude of selection in the two areas.

In this study, we thus present a model using spatial information from clines to estimate selective advantages and costs, but also temporal information from long term survey (~15 years) to estimate the selection coefficients of each allele in each environment. With this approach, we focused on the long term trend of allele replacement. For a proper comparison among years, we used data from only one season (summer), ignoring within years variations that are not directly relevant to the long term trend. Importantly, this approach does not make any equilibrium assumption: the initial situation is fitted by a description of the clines of the first year in the series (1986), and all the clines in the following years depend on these initial frequencies, migration rate and selection coefficients of the different alleles (See Supplementary materials for a review of previous models).

Data collection:

The dataset is a compilation of published Ester starch-gel electrophoresis phenotype frequencies from samples collected in the Montpellier area from 1986 to 2002 [START_REF] Guillemaud | Evolution of resistance in Culex pipiens: allele replacement and changing environment[END_REF][START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF]

Insecticide treatment:

The size of the treated area is pivotal to estimating the selection parameters from cline analysis [START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF]. In order to obtain good estimation of this size, we used data of total insecticide quantities per district provided by the local insecticide treatment agency (EID, Entente Interdépartementale de Démoustication) from 1990 to 2002. In previous years (1986 to 1989), treatment applications (i.e. treated area size and quantities used) did not change significantly [START_REF] Eid | Entente Interdépartementale de Démoustication[END_REF][START_REF] Guillemaud | Evolution of resistance in Culex pipiens: allele replacement and changing environment[END_REF]. We used GIS data to estimate the quantities of insecticide applied in the Montpellier area. The total area analyzed was 40 km wide (20 km each side of the sampling transect) and 35 km long, perpendicularly to the coast. We divided this area in 2 km wide stripes, parallel to the coast. The OP quantity used in each stripe, q j , expressed in liter.km -2 (L/km 2 ), was computed as

∑ ∑ = i ij i i i ij j A q A A q (1),
where A ij is the area of each district i within the stripe j, A i and q i the total area and the quantity of insecticide used in this district i, respectively. We determined the width of the treated area as the distance from the sea where the quantities of insecticides treatments used drops for most years to 0 L/km².

Migration-Selection Model:

In order to estimate the relative costs and selective advantages of each the three alleles at the Ester locus we used a deterministic stepping stone-like model to follow frequency changes. The order of life cycle was assumed to be reproductionselection-migration. We assumed 13 generations per year according to LENORMAND et al.

(1999) and a constant population density across treated and non-treated areas (we will discuss this last hypothesis below). Algorithms of migration and selection were checked using analytical results for one locus provided by equations 32-33 in NAGYLAKI (1975).

Reproduction. Each generation was computed from the previous one assuming Hardy-Weinberg proportions in each deme independently (each deme being considered as an infinite population), as it has been shown that data are congruent with this assumption (LABBÉ et al.

2005).

Selection. The fitnesses of the Ester alleles were computed as follow: let s i and c i be the fitness advantage conferred by resistance alleles in treated area and the fitness cost of the allele i, respectively; let h s ij be the dominance of the benefit for resistance and h c ij the dominance of the cost of the allele i over the allele j. The fitness w ij of the diploid genotype (ij) was computed as

w ij = 1 + γ [s i + h s ij (s j -s i )] -[c i + h c ij (c j -c i )]
(2), with γ = 1 in the treated area and γ = 0 in the non-treated area and where the fitness of a susceptible homozygote w 00 = 1 (i.e.

s 0 = c 0 = 0). For γ = 1, [s i + h s ij (s j -s i )]
represents the overall advantage of the resistance genotype in the treated area. [c i + h c ij (c j -c i )] represents its cost in both the treated and the untreated area. h s ij ranges from 0 (total dominance of i over j)

to 1 (total dominance of j over i), with 0.5 representing codominance. h c ij ranges from 0 to a value >1 (overdominance), providing that c j >c i . As there are three resistance alleles at Ester locus, 18 parameters were used to describe selection at this locus: the costs, c 1 , c 2 , c 4 , the advantage of resistance s 1 , s 2 , s 4 (for Ester 1 , Ester 2 and Ester 4 , respectively) and the 6 dominance parameters for the cost and the advantage of resistance of the four alleles (Ester 0 , Ester 1 , Ester 2 and Ester 4 ).

To consider indirect selection due to genetic association of Ester alleles with the other C. pipiens main OP resistance locus, ace-1, we used fitness parameters estimated for ace-1 in previous study (s R = 0.33 and c R = 0.11, LENORMAND et al. 1999, ignoring possible fitness differences between ace-1 resistance alleles) and assumed codominance at this locus. We also assumed multiplicative fitness between the ace-1 and Ester loci and used the recombination rate between the two loci (r = 14.5%) estimated from laboratory crosses (LENORMAND et al.

1998).

The frequency of genotype k in deme l after selection g' kl was computed from its frequency before selection g kl as:

g' kl = g kl w kl / W l (3),
where w kl is the fitness of genotype k in deme l and W l the mean fitness in deme l. We first computed selection coefficients by assuming that all alleles were codominant (i.e h s ij = h c ij = 0.5 for all alleles): this is the COD model. We then relaxed this hypothesis by allowing dominance parameters to differ from 0.5: this is the NOCOD model.

Migration. One-dimensional clines were simulated by a series of demes connected by migration (one deme every 2 kms, 35 demes in total). The migration distribution was reflected at one edge of the stepping-stone, to simulate a semi-infinite environment and take into account the presence of the sea [START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF]. We used an approximately gaussian dispersal kernel with a parent-offspring distance standard deviation σ = 6.6 km.generation -1/2 ; this value has been estimated by [START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF] using the spatial pattern of linkage disequilibrium between resistance locus. This method does not require assuming migration-selection equilibrium at the selected loci as far as the linkage disequilibrium equilibrates faster than frequency changes. This latter situation will be easily met if the resistance alleles are not too far from an equilibrium or if their frequency change slowly, provided that the loci are not too tightly linked (this in the well-studied quasi linkage equilibrium situation, BARTON and GALE 1993;NAGYLAKI 1993). This situation is very likely to be met in our case as the recombination rate between resistance loci is quite large (r ~ 15%)

and the important frequency changes at these loci occurs at the scale of hundreds of generations.

Initial conditions. Only phenotype data are available due to the dominance of overproduced esterases in the identification method (starch-gel electrophoresis, see Parameters estimations). Thus, to obtain initial conditions, we estimated (simultaneously with the selection coefficients) the distribution of the frequency of each allele in 1986 (first year of sampling available) using a descriptive model as in previous studies [START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF][START_REF] Lenormand | Analysis of clines with variable selection and variable migration[END_REF]. In 1986, only Ester 1 and Ester 4 alleles were present, as

Ester 2 was detected for the first time in 1990 in the Montpellier area (one heterozygote individual found among all populations sampled, [START_REF] Rivet | French mosquito populations invaded by A2-B2 esterases causing insecticide resistance[END_REF]. Frequency clines for the two first resistance alleles i (i = 1 or 4 for Ester 1 and Ester 4 , respectively) were simultaneously fitted to a scaled negative exponential

p i = k i exp[-(a i x 2 + b i x)] (4),
where x is the distance from the coast, and k i , b i and a i are the estimated parameters. k i is the frequency of resistance allele i for x = 0 (i.e. at the coast). As the Ester 2 allele was not yet present in 1986, we introduced it t* generations after 1986, at a frequency of 0.001 in all demes. t* was estimated together with the other parameters. As all the parameters (initials conditions, selection coefficients and t*) are fitted simultaneously, the model is not particularly susceptible to the initial conditions and choosing another year to start the estimation would not change them significantly (of course, the longest the period considered, the better the estimation).

Parameters estimations:

The method of estimation is a standard maximum likelihood approach. Deterministic recursions described above generate the predicted clines of each allele at any point in time for a given set of parameter values. It is then straightforward to compute the probability of observing a sample at any location in any year given this prediction. Assuming that the different samples are independent, the likelihood of a full 15 year scenario can then readily be obtained. The only difficulty, however, is the computer time needed to maximize this likelihood given that a single 15 years prediction requires simulating ~200 generations in a relatively large stepping stone. Recursions and likelihood maximisation algorithms were written and compiled using Delphi TM v. 7 (Borland Software Corporation).

The Ester phenotype of each mosquito was obtained using starch-gel electrophoresis.

This technique does not allow complete identification of genotype [START_REF] Guillemaud | Evolution of resistance in Culex pipiens: allele replacement and changing environment[END_REF][START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF][START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF]

( ) ij j ij i f n L ln ∑ ∑ = (5).
It was maximized for parameters joint estimation, using a simulated annealing method (using a Metropolis algorithm, see LENORMAND AND [START_REF] Lenormand | Analysis of clines with variable selection and variable migration[END_REF].

Model comparison and tests:

For the complete COD model (model COD-A), a total of 13 parameters needed to be estimated: (i) s 1 , s 2 , s 4 , the selective advantages of Ester 1 , Ester 2 and Ester 4 respectively, (ii) c 1 , c 2 , c 4 , the selective costs of Ester 1 , Ester 2 and Ester 4 respectively, Model COD-A was then simplified using likelihood ratio tests corrected for overdispersion (F-test, LEBRETON et al. 1992;[START_REF] Anderson | AIC model selection in overdispersed capture-recapture data[END_REF]) to find the best adequate model. We first determined whether the selective advantages s i and s j of alleles i and j were significantly different by setting s 1 = s 2, s 1 = s 4, s 2 = s 4 in models COD-B 1 , COD-B 2 and COD-B 3 , respectively, all other parameters being freely estimated. Similarly, we then determined whether costs c i and c j of alleles i and j were significantly different. We computed the models COD-C 1 , COD-C 2 and COD-C 3 by setting c 1 = c 2, c 1 = c 4, c 2 = c 4 , respectively, with all other parameters being freely estimated. Models combining more complex hypotheses (i.e.

(iii) k 1, k 4 , a 1 , a 4 ,
constraining both s and c values to be identical among some alleles) were then computed as models COD-D, with all other parameters again being freely estimated.

Over-dispersion was computed from model COD-A as the ratio of residual deviance (the deviance equals -2 x ln[likelihood]) over residual degrees of freedom. We computed the percentage of total deviance explained by a model (%TD) as

%TD = (D max -D model ) / (D max -D min ) (6),
where the maximal deviance (D max ) is obtained by fitting a minimal model in which the frequency of each allele in each population is set to its average along the transect and over years, and the minimal deviance (D min ) obtained by fitting a maximal model in which the frequency of each allele in each population is set to its observed frequency. Models were compared using F-tests in order to correct for overdispersion. All deviances were also corrected for overdispersion to estimate the support limits of each parameter p. These were computed by maximising or minimizing the value of p, for upper limit (p max ) and lower limit (p min ), respectively. All other parameters were allowed to change, ensuring us to find the actual p max and p min in the range of the multidimensional parameter landscape where likelihood is not significantly different from the maximum likelihood of the model, using the same simulated annealing method.

We used the same process when relaxing the overdominance hypothesis (NOCOD models) and simply tested whether each dominance parameter was significantly different from 0.5 (codominance) or not, all other parameters being again freely estimated.

RESULTS

Insecticide treatment:

The treatment practices for the period 1990-2002 are presented in Supplemental Figure 1 (Supplementary Materials). Over the 12 years analyzed, the treated area size is roughly constant and runs 16 km inland from the sea, although treatment extension and intensity was higher in the first years analysed (Supplemental Figure 1). The total amount of insecticides used is variable over the years, from 124.3 to 733.1 L.km -2 (Supplemental Figure 2, Supplementary Materials). The treated area is not evenly treated:

immediately close to the sea, treatments are less intense, due to less suitable breeding sites for C. pipiens. This mosquito needs freshwater to reproduce and brackish lagoons near the sea largely reduce the area with potential breeding sites. However, for simplicity we considered the treated area as an approximately uniformly treated surface in the model, as we have no clue about how the dose of insecticide relates to fitness in the field. 2A. This model explains 70.3% of the total deviance with low overdispersion (~1.52).

Model comparison and tests:

Relaxing the codominance hypothesis introduces 12 additional parameters of dominance associated to s and c, h s ij and h c ij . Among these only one, h s 20 , the advantage dominance of Ester 2 over Ester 0 , is significantly different from 0.5 (codominance) (h s 20 = 0.076, Table 2B). Under this hypothesis, the simplest model (NOCOD-D) is built with four parameters describing selective advantage and cost: s 1 = s 4 , s 2 , c 1 = c 4 and c 2 , the differences in cost and advantage dominances, h c and h s , alone explaining the allele replacement. The best value of each of these and corresponding supporting limits are indicated in Table 2B. This model explains 72.9% of the total deviance with low overdispersion (~1.43).

The last parameter, the time to Ester 2 appearance t*, is estimated to 45 and 48 generations (with and without the codominance hypothesis respectively), which corresponds to ~1989 with support limits being 30-60 generations, i.e. [1988][1989][1990].

The predicted cline of each allele (spatial frequencies variation) is presented in Figure 2, for each year for which samples are available, under the NOCOD-A model. The computed variation over the period 1986-2002 (temporal frequencies variation) of the maximal frequency of each allele is presented in Figure 3 (NOCOD-A model). It shows the replacement of Ester 1 by Ester 4 that occurred during the 1990s. It also predicts the replacement of Ester 4 by Ester 2 over the period 2002-2024 (Figure 3), providing that treatment practices will not change during this period.

To assess whether there was a consistent variation of selection coefficients over time, we used two estimators of the goodness of fit, overdispersion and percentage of deviance explained by the model, for each sampling year. The variability over the 1986-2002 period of these two measures is presented in Supplemental Figure 3. Each sampled year independently is well fitted with more than 50% and up to 82% of the total deviance explained and an overdispersion inferior to 2 for each of them.

DISCUSSION

Natural selection is notoriously difficult to measure in the wild, and this imposes an important limit on our ability to study evolution and to test in natura theories of adaptation.

However, the study of cline series is a particularly informative situation since temporal and spatial frequency variation can be combined to estimate selection. We illustrate this approach with the evolution of insecticide resistance in the mosquito Culex pipiens: the resistance allele replacement observed at the Ester locus in the Montpellier area since 1986 allows us to analyse the process of amelioration with a degree of precision more typical of laboratory than field studies (down to a precision of ~2% for some selection coefficients). In addition, this is the first time, to our knowledge, that estimation of the relative fitness of more than two alleles at a single locus has been performed using field data (our model is nevertheless in accordance with previous average measures of fitness on this system, see Comparison with previous estimations, Supplementary Materials). This approach enabled us to study in more detail the process of allele replacement in the field and to determine whether it was driven by direct or compensatory amelioration. It also enables us to quantify the amount of fitness variation occurring at the different stages of the process.

Selection coefficients:

The selection coefficient estimations provided for the various resistance alleles (Table 1) accurately explain the allele replacements observed in Montpellier area (70% of the total deviance is explained). With the susceptible allele fitness being w 0 =1, the overall resistance allele fitness orders are Ester 2 (w 2 = 1.250) > Ester 4 (w 4 = 1.154) >

Ester 1 (w 1 = 1.112) in the treated area and Ester 4 (w 2 = 0.964) > Ester 1 (w 4 = 0.922) > Ester 2

(w 1 = 0.880) in the non-treated area (COD-A model, Table 2). The fitnesses differences detected between resistant alleles can thus be relatively small compared to the differences between susceptible and resistant (e.g. in treated area Ester 4 fitness is w 4 = 1.038 relative to

Ester 1 , i.e. if w 1 = 1, although Ester 2 differences with Ester 4 and Ester 1 are still quite large, e.g. in treated area w 2 = 1.124 relative to Ester 1 ).

During the 1990s, Ester 4 replaced Ester 1 (Figure 3, [START_REF] Guillemaud | Evolution of resistance in Culex pipiens: allele replacement and changing environment[END_REF][START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF]. We show here that Ester 1 's selective advantage is not significantly different from that of Ester 4 (relative to s 1 , s 4 = 0, SL = -0.026 -0.019), but that its cost is higher under the codominance hypothesis (relative to c 1 , c 4 = -0.045, SL = -0.055 --0.035). Thus, the lower cost of Ester 4 could be pivotal in explaining the replacement of Ester 1 by Ester 4 . However, if dominances are different from 0.5, the estimated costs of Ester 1 and Ester 4 are not distinguishable (relative to c 1 , c 4 = -0.002, SL = -0.032 -0.059). In this case, the allele replacement is due to the cost being more dominant for Ester 1 than Ester 4 (the cost of (Ester 1 /Ester 0 ) heterozygotes is closer to that of (Ester 1 /Ester 1 ) than (Ester 0 /Ester 0 ) homozygotes, whereas the cost of (Ester 4 /Ester 0 ) heterozygotes is closer to that of (Ester 0 /Ester 0 ) than (Ester 4 / Ester 4 ) homozygotes). However dominances remain difficult to precisely estimate using these data (Table 2B). Fitting dominances only marginally increases the overall goodness of fit, explaining no more than 3% more of the deviance than the codominance model. Finally, laboratory data provide support for Ester 1 having a higher cost than Ester 4 (see Comparison with laboratory experiments, Supplementary Materials), suggesting a compensatory amelioration in this first allele replacement.

Ester 2 was first detected in Southern France near Marseille (~150 km from Montpellier) in 1986, but it was first detected at a very low frequency in the Montpellier area in 1990 [START_REF] Rivet | French mosquito populations invaded by A2-B2 esterases causing insecticide resistance[END_REF]. Our study estimates its first occurrence near Montpellier during the year 1989, which indicates a quite fast spread of this allele in the south of France (c.a. 50 km per year in approximately 3 years). This alone suggests a strong fitness advantage for this resistance allele. It remained at low frequency (coastal frequency < 0.1) until 1999 [START_REF] Gazave | Dissecting the cost of insecticide resistance genes during the overwintering period of the mosquito Culex pipiens[END_REF][START_REF] Guillemaud | Evolution of resistance in Culex pipiens: allele replacement and changing environment[END_REF][START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF] and then progressively increased in frequency (coastal frequency ~ 0.2 in 2002), leading to a decrease in the frequency of Ester 1 and the stabilization of the frequency of Ester 4 [START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF]. As shown in this study, this seems to be explained by a strong selective advantage leading to a higher fitness of Ester 2 in the treated area compared to the previous alleles (relative to s 1 , s 2 = 0.158, SL = 0.072 -0.282; relative to s 4 , s 2 = 0.158, SL = 0.077 -0.288), despite a higher cost (relative to c 1 , c 2 = 0.188, SL = 0.118 -0.329; relative to c 4 , c 2 = 0.155, SL = 0.082 -0.302; see Table 2). Thus, the increased advantage of Ester 2 in the treated area compensates for its increased cost in the non-treated area, indicating that this second allele replacement is most probably due to a direct amelioration (see also Comparison with laboratory experiments, Supplementary Materials). Finally, our estimations (Figure 3) indicate that without any modification in the insecticide treatment practices, Ester 2 would eventually replace both alleles in about 20 years, the approximate time from the appearance of Ester 4 until now.

Limit of the approach:

In this study, we used two main assumptions by neglecting the intra annual variation and the density variation between treated and non-treated areas (other parameters, including the initial conditions, are fitted in the model or were obtained independently; see Migration-Selection Model, Material and Methods). For practical reasons of computational time, intra annual variations of selection coefficients were not taken into account in our model. Because we ignored them, we cannot determine if the different resistance alleles are selected differently in different season (e.g. if differences in the fitness cost are due to difference in mortality during female overwintering or to differences of larval development time during summer; [START_REF] Gazave | Dissecting the cost of insecticide resistance genes during the overwintering period of the mosquito Culex pipiens[END_REF][START_REF] Lenormand | Tracking the evolution of insecticide resistance in the mosquito Culex pipiens[END_REF][START_REF] Lenormand | Analysis of clines with variable selection and variable migration[END_REF]. Thus, the estimates we give have to be understood as annual averages. However, the cline observed in summer is relatively independent of what happened during the rest of the year, so that the hypothesis of a temporary migration-selection equilibrium reached each year at the end of summer is reasonably accurate (see Comparison with previous estimations in Supplementary Material), although the allele replacement modifies this equilibrium from one year to another. Density differences between treated and non-treated areas may bias our estimates of selection by causing an asymmetrical gene flow between the two habitats [START_REF] Nagylaki | CLINES WITH ASYMMETRIC MIGRATION[END_REF]. This is true in particular for the relative selection coefficients between susceptible and resistance alleles. Like for selection, the density pattern may also vary seasonally or among years. Thus, the estimates we give have to be understood as if density was constant. For instance, if density is lower in the treated area (which is not necessarily the case, [START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF], larger s would be required to maintain the same clines. However, it is important to underline that because the different resistance alleles experience the same density variation across treated and non treated area and because they have very similar spatial distribution (see Figure 2), this bias is minimal as far as resistance alleles are compared to one another, as it is the case in our study (i.e. the values of s and c relative to the susceptible allele might be biased, but the differences between s 1 , s 2 and s 4 on one hand, or between c 1 , c 2 and c 4 on the other hand, cannot be strongly affected by density effects). The same arguments hold for demographic, topological or treatment intensity variations that could occur perpendicular to our transect (although we are unaware of such variation over few tens of km East or West of our transect). Globally, our model explains more than 70% of the total deviance (TD) observed in the evolution of Ester resistance genes in Montpellier area (with a low global overdispersion, ~1.43). There is no indication of a trend towards increase or decrease of %TD or overdispersion during allele replacement (Supplemental Figure 3), as would be the case if selection changes with time. This would be the case, for example, if a modifier gene appeared at another locus during the course of the replacement, as was seen in Lucilia cuprina (for a review see [START_REF] Mckenzie | Ecological and evolutionnary aspects of insecticide resistance[END_REF]. Such a modifier could increase the fitness of resistant Ester alleles by reducing their deleterious sideeffects. Although our power to detect a compensatory modifier was limited, especially if it had a weak effect, a modifier gene is not necessary to explain the trends observed in natural populations through this long-term study. Currently, a second replacement is occurring: Ester 2 is replacing Ester 4 despite a higher fitness cost, due to a higher selective advantage in the treated area (direct amelioration). Thus, contrary to the first replacement during which a more 'generalist' allele was selected, the second replacement involves an allele which is more 'specialist' to treated areas, leading to the reinforcement of local adaptation. There are two ways by which evolution may proceed ultimately if the insecticide treatments are maintained. The first option would involve further evolution towards specialist alleles that confer high resistance but with strong pleiotropic effects, such as Ester 2 . This type of situation occurs when there is a strong trade-off between conflicting selection pressures in the different habitats. In such a situation a stable polymorphism is likely to be maintained and may lead to the evolution of distinct niches. The second option would involve further evolution towards generalist alleles that confer resistance with little pleiotropic effects, such as Ester 4 . This type of situation occurs when there is a weaker trade-off between the conflicting selection pressures in the different habitats. In this scenario the polymorphism is likely to be lost rapidly, with the fixation of a 'cost-free' resistance allele, which corresponds to an extension of the niche. It is interesting to note that in our case both options have occurred successively in combination with a changing environment. The evolution at the Ester locus is certainly influenced by treatment practices, and it is possible that if insecticide treatment intensity decreases Ester 4 may be favoured again due to its lower cost, with the stronger resistance of Ester 2 then being less advantageous. This emphasizes the role of local treatment practices, which have been shown to be crucial in the competition of Ester alleles on a worldwide scale [START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF].

The theory of adaptation: From a more general point of view, the evolution of insecticide resistance at the Ester gene represents a first step to study theories of adaptation [START_REF] Orr | The genetic theory of adaptation: a brief history[END_REF] in nature. Although amelioration has been reported from field studies (e.g. MCKENZIE 1993), our study allows quantitative estimation of the selection coefficient involved with a clear knowledge of the history and genetic bases of the adaptive changes. Viewed at first as a slow process of accumulation of small mutations toward a fitness optimum [START_REF] Fisher | The possible modification of the response of the wild type to recurrent mutations[END_REF][START_REF] Hartl | Compensatory Nearly Neutral Mutations: Selection without Adaptation[END_REF], the process of adaptation is now thought to imply larger fitness effect mutations, occurring early in the process, and smaller mutations occurring subsequently to refine the adaptation [START_REF] Cohan | Amelioration of the deleterious pleiotropic effects of an adaptive mutation in Bacillus subtilis[END_REF][START_REF] Barton | Evolutionary biology: The geometry of adaptation[END_REF][START_REF] Orr | The Population Genetics of Adaptation: The Distribution of Factors Fixed during Adaptive Evolution[END_REF][START_REF] Orr | The evolutionary genetics of adaptation: a simulation study[END_REF][START_REF] Barton | Understanding quantitative genetic variation[END_REF][START_REF] Orr | The genetic theory of adaptation: a brief history[END_REF]. This theory has been supported by laboratory studies (e.g. [START_REF] Cohan | Amelioration of the deleterious pleiotropic effects of an adaptive mutation in Bacillus subtilis[END_REF][START_REF] Oxman | Defined order of evolutionary adaptations: experimental evidence[END_REF], but ours gives new support from field data: the first mutation, Ester 1 , was indeed a mutation of large fitness effect (relatively to ancestral susceptible alleles), the second, Ester 4 , had a smaller fitness effect and refined the adaptation by lowering the cost, and the third, Ester 2 , had again a large effect on fitness (Table 2). Albeit representing few steps, this field study is consistent with the theory formalized by ORR (1998). Interestingly, this study also provides some insights about the fact that adaptation is local, and thus that several strategies are possible in the course of adaptation to a heterogeneous environment. It is difficult to predict whether local adaptation will reinforce itself and lead to the evolution of specialist strategies or whether a generalist strategy that can exploit all habitats will emerge. The course of events obviously depends on the selective properties of the new resistance alleles that occur (and the underlying trade-off). Our study illustrates this point precisely: Ester 4 was more generalist than Ester 1 (low c), but it is now being replaced by Ester 2 a more specialist allele (high s, high c). The theory of adaptation tends to focus primarily on evolution in a single population. It will benefit from taking into account the spatial and temporal variability of the environment. 1 The residual deviance of each model is scaled to the overdispersion of model A.

2 df is the number of degrees of freedom.

3 %TD is the part of the total deviance explained by each model. Samples are indicated with black circles. The dashed line represents approximately the border between treated and untreated areas [START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF]. C. pipiens is present in the whole area. Recently, a third allele, Ester 2 , invaded the Montpellier area (crosses) [START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF].

We used the estimation of coastal frequencies of the different alleles provided by [START_REF] Labbé | On the worldwide spread of an insecticide resistance gene: a role for local selection[END_REF]. Lines represent the fitted values according to the NOCOD-A model (see Material and Methods). The susceptible allele is not represented as its frequency is equal to 1-Σ(resistant allele frequencies).

  . We used samples from years 1986 (9 populations, N = 354), 1987 (3 populations, N = 193), 1991 (9 populations, N = 217), 1993 (2 populations, N = 110), 1995 (8 populations, N = 1203), 1996 (9 populations, N = 512), 1999 (9 populations, N = 582), 2001 (9 populations, N = 736) and 2002 (9 populations, N = 521) to perform our analysis, considering only samples collected during the summer. A total of 4428 individuals were analyzed.

Parameters estimations :

 estimations The first six parameters of our models are those describing the initial clines (1986): the initial maximum frequencies (k 1 and k 4 ) and the rates of decline (a 1 , a 4 , b 1 and b 4 ) of each allele present (Ester 1 and Ester 4 ). This initial cline is best described by an exp(-x 2 ) shape, where x is the distance from the coast (k 1 = 0.461, k 4 = 0.233, a 1 = 0.095, a 4= 0.071, b 1 = b 4 = 0).Under the codominance hypothesis, the simplest model (COD-D) is built with four other parameters describing selective advantage and cost: s 1 = s 4 , s 2 , c 1 = c 2 and c 4 . The best value of each of these and corresponding support limits are indicated in Table

  We are very grateful to T.Guillemaud, D. Allen, M. Weill and anonymous reviewers for very helpful comments on the manuscript, A. Berthomieu, C. Berticat, M. Marquine, S. Unal and C. Bernard for technical assistance and V. Durand for literature search. This work was funded in part by ANR MOREVOL. Contribution 2008.xxx of the Institut des Sciences de l'Evolution de Montpellier (UMR CNRS-UM2 5554).

  The models are described in the text. They correspond to different simplifications of the complete model (COD-A and NOCOD-A, respectively with and without codominance hypothesis), indicated in the "Simplification" column. F-test statistic values and P-values indicate whether the deviance of the model considered is significantly different from that of the complete model A ( n.s. P-value > 0.05, * P-value < 0.05, ** P-value < 0.01, *** P-value < 0.001). Each dominance parameter was set to 0.5 (COD) or freely estimated (NOCOD).

FIGURE 2 .

 2 FIGURE 2. Cline fitting of the best model. The expected patterns of frequency variation along

FIGURE 3 .

 3 FIGURE 3. Interannual variation of Ester alleles frequencies. The frequencies presented here are the maximum frequencies, i.e. at the coast. The first allele to appear was Ester 1 (with white diamonds), then replaced by Ester 4 (black triangles)[START_REF] Guillemaud | Evolution of resistance in Culex pipiens: allele replacement and changing environment[END_REF].

  FIGURE 2.

  because the presence of a susceptible allele cannot reliably be detected in an individual with an overproduced resistance allele. The Ester i /Ester 0 or Ester i / Ester i , and phenotype [ij] correspond to genotype Ester i / Ester j , see[START_REF] Lenormand | Evaluating gene flow using selected markers: a case study[END_REF]. The loglikelihood of a sample was computed from the phenotypic multinomial distribution. Let n ij

	phenotype was thus considered to be a seven-state random variable ([0], [1], [2], [4], [12],
	[14], [24], where phenotype [i] corresponds to genotypes

and f ij be the observed number and expected frequency of individuals having phenotype i in population j, respectively. The log-likelihood L of observing all the data is proportional to

  b 1 and b 4 , the parameters of the initial frequency clines in 1986 of Ester 1 and Ester 4 respectively, and (iv) t*, the date of apparition of Ester 2 . When the codominance Ester 1 , Ester 2 and Ester 4 respectively).

	hypothesis is relaxed (NOCOD model), 12 additional parameters are needed: (vi) h s	10 , h s	20 ,
	h s	40 , h s	21 , h s	41 and h s	24 , for the dominance of the resistance fitness benefit and (vii) h s	10 , h s	20 ,
	h s	40 , h s	21 , h s	41 and h s	24 , for the dominance of the cost (where 0, 1, 2 and 4 represent Ester 0 ,

  Ester 4 (i.e. c 4 < c 2 = c 1 ). Relaxing the codominance hypothesis modifies the results, such that neither the selective advantages nor the costs of Ester 1 and Ester 4 are significantly different (i.e. s 1 = s 4 and c 1 = c 4 , model NOCOD-D).

Model selection was performed using likelihood ratio tests corrected for overdispersion

(F-test, LEBRETON et al. 1992;[START_REF] Anderson | AIC model selection in overdispersed capture-recapture data[END_REF]

to determine whether the selection coefficients were different among alleles. Results of each comparison are detailed in Table 1. Under the codominance hypothesis, in the simplest adequate model (model COD-D) the selective advantages of Ester 1 and Ester 4 and the costs of Ester 1 and Ester 2 are not significantly different (i.e. s 1 = s 4 and c 1 = c 2 , resp.), but the cost is lower for

The process of amelioration:

  This work enables us to understand the causes of the resistance allele replacement observed at the Ester locus in the Montpellier area. Our model and previous laboratory experiments (see Supplementary Materials) suggest that Ester 1 has most probably been replaced by Ester 4 because Ester 4 is less costly (compensatory amelioration).

TABLE 1 Model selection.

 1

	Model	Simplification	Dev 1	Df 2	%TD 3	F-test	P-value
	COD-A	complete model	6215.98	7	0.705	-	-
	COD-B1	s 1 = s 2	6230.86	6	0.694	14.88	0.000	***
	COD-B2	s 1 = s 4	6216.38	6	0.704	0.40	0.526	n.s.
	COD-B3	s 2 = s 4	6238.40	6	0.689	22.43	0.000	***
	COD-C1	c 1 = c 2	6217.86	6	0.703	1.88	0.171	n.s.
	COD-C2	c 1 = c 4	6233.88	6	0.692	17.90	0.000	***
	COD-C3	c 2 = c 4	6222.20	6	0.700	6.22	0.013	*
	COD-D	s 1 = s 4 and c 1 = c 2	6218.48	5	0.703	1.25	0.288	n.s.
	NOCOD-A	complete model	6179.95	19	0.730	-	-
	NOCOD-B1	s 1 = s 2	6193.16	18	0.720	13.20	0.000	***
	NOCOD-B2	s 1 = s 4	6179.95	18	0.730	0.00	1.000	n.s.
	NOCOD-B3	s 2 = s 4	6187.23	18	0.725	7.28	0.007	**
	NOCOD-C1	c 1 = c 2	6183.88	18	0.727	3.93	0.048	*
	NOCOD-C2	c 1 = c 4	6180.00	18	0.730	0.05	0.830	n.s.
	NOCOD-C3	c 2 = c 4	6184.57	18	0.726	4.62	0.032	*
	NOCOD-D	s 1 = s 4 and c 1 = c 4	6179.96	17	0.730	0.00	0.997

n.s.

TABLE 2 Best fitted parameters

 2 being freely estimated (NOCOD-A model). In the last case, the estimated value of the dominance parameters, for selection, h s ij , or for cost, h c ij , are also indicated (values significantly different from 0.5, i.e codominance, are bolded). Sample site locations in the northwest southeast transect in the Montpellier area.

	A-
	Parameter Best value	Support limits
	s 1	0.19	0.15 -0.24
	s 2	0.37	0.28 -0.53
	s 4	0.19	0.16 -0.21
	c 1	0.078	0.058 -0.10
	c 2	0.12	0.050 -0.28
	c 4	0.036	0.027 -0.045
	t*	45	30 -60
	B-
	Parameter Best value	Support limits
	s 1	0.17	0.13 -0.21
	s 2	0.51	0.35 -0.72
	s 4	0.18	0.15 -0.24
	c 1	0.057	0.040 -0.079
	c 2	0.20	0.084 -0.52
	c 4	0.059	0.027 -0.11
	t*	48	30 -60
	h s	10	0.19	0.00 -0.57
	h s	40	0.29	0.00 -0.59
	h s	20	0.076	0.00 -0.29
	h s	14	1.00	0.00 -1.00
	h s	12	1.00	0.44 -1.00
	h s	24	0.54	0.095 -1.00
	h c	10	0.65	0.44 -1.02
	h c	40	0.21	0.00 -0.52
	h c	20	0.36	0.00 -0.86
	h c	14	2.86	0.00 -3.00
	h c	12	0.00	0.00 -0.88
	h c	24	0.64	0.00 -1.92

For each parameter, the best value fitted is indicated, associated to the corresponding support limits (see text), A) for codominance hypothesis (COD-A model) and B) dominance parameters


domain: math shs

text:
Simon Modeste¹
email: simon.modeste@umontpellier.fr

Maryna Rafalska²
email: m.v.rafalska@npu.edu.ua

Algorithmics in secondary school: A comparative study between Ukraine And France

Keywords: Algorithm, algorithmics, didactic transposition, curricula comparison, France, Ukraine

This article is focused on the teaching and learning of Algorithmics, a discipline at the intersection of Informatics and Mathematics. We focus on the didactic transposition of Algorithmics in secondary school in France and Ukraine. Based on epistemological and didactical frameworks, we identify the general characteristics of the approaches in the two countries, taking into account the organization of the content and the national contexts (in the course of Mathematics in France and in the course of Informatics in Ukraine). Our results give perspectives on understanding the place that Algorithmics can hold in the teaching and learning of Mathematics and Informatics.

Introduction

Mathematics and Informatics 1 , as disciplines, have strong links. On one hand, Mathematics gives theoretical basis and instruments to Informatics, and on the other hand, Informatics enriches Mathematics with new objects and problems, and brought some changes in the mathematical activity. Many disciplines (Discrete Mathematics, Algorithmics, etc.) developed at their interface. Nowadays, there is an international movement towards including Informatics and these subjects in secondary education. Algorithmics is more and more present in secondary school in many countries. It can be involved in programs of Mathematics (as in France) or Informatics (as in Ukraine). This situation questions the goals of teaching and learning Algorithmics in secondary school, the contents of the curricula as well as the approaches and activities proposed to pupils. To contribute to the study of these issues, we propose a comparative study regarding the concept of algorithm and the contents of Algorithmics in secondary school in France and Ukraine.

Algorithm is a central notion in Mathematics and Informatics. Algorithm in "classic" Mathematics is generally used with the meaning of a general effective procedure for solving problems. Since the origins of Mathematics, algorithms have been designed and used for solving problems (arithmetic operations with decimal numbers, solving equations, etc.). The use of computers and programming languages brought a new point of view on the notion of algorithm referring to the formalization of procedures, the automation of computations and the problem of data treatment. In this context, the notions of finiteness, iteration and recurrence play an important role (Chabert, 1999, pp. 6-7).

As a reference, we retained the following definition of an algorithm given by Modeste (2012, p. 25) and based on the academic literature on the subject: "a procedure for solving a problem which, in a finite number of constructive, effective, not ambiguous steps, gives a result for any instance of the 1 We will use the term "Informatics", a more faithful translation from the French and Ukrainian than Computer Science.

Thematic Working Group 11

Proceedings of CERME10 problem". We will delimit the discipline Algorithmics as the field that deals with algorithms, the problems they can solve, their design, their use, their analysis and their comparison.

Research questions, theoretical framework and methodology

To formalize our problematic, we have formulated the following research questions:

 What is the place of Algorithmics in secondary school in France and Ukraine?

 In what way the learning contents related to Algorithmics are organized?  What types of activities in Algorithmics are proposed to pupils in both countries?  What common points and differences appear? How can they be interpreted? Our study is based on the concept of didactic transposition [START_REF] Chevallard | La transposition didactiquedu savoir savant au savoir enseigné[END_REF] developed in the Anthropological Theory of the Didactic [START_REF] Bosch | Introduction to the Anthropological Theory of the Didactic (ATD)[END_REF]. The didactic transposition describes the processes of transformation between academic knowledge, the knowledge to be taught and the taught knowledge. It takes a step back from the curriculum and the content actually taught, to understand the role and the influence of the different institutions involved in these processes.

In order to analyse the content devoted to Algorithmics in the curricula, to measure their distance to the academic knowledge, and to develop our comparative study, we lean on an epistemological framework, in accordance with a classical methodology in Didactics of Sciences and Mathematics [START_REF] Artigue | Épistémologie et didactique[END_REF]. Concerning the concept of algorithm and Algorithmics we used the epistemological framework developed by [START_REF] Modeste | Enseigner l'algorithme pour quoi ? Quelles nouvelles questions pour les mathématiques ? Quels apports pour l'apprentissage de la preuve[END_REF][START_REF] Modeste | The appearance of algorithms in curricula, a new opportunity to deal with proof[END_REF]. The epistemological model distinguishes five fundamental aspects of the concept of algorithm: problem aspect (the fact that an algorithm is a tool to solve all instances of a problem, the notions of input and output); effectiveness aspect (all elements referring to the fact that an algorithm solves problems effectively: the notion of operator; the finiteness of instructions and executions, etc.); complexity aspect (all elements referring to the notion of complexity of algorithms and problems); proof aspect (referring to the links between algorithm and proof); theoretical models aspect (referring to the theoretical works in Logic and Informatics concerning the concept of algorithm). Among these aspects, problem and effectiveness refer to algorithm as a tool, whereas proof, complexity and theoretical models refer to algorithm as an object. This tool-object dialectic of the concept of algorithm will be useful to understand the points of view in different institutions.

In this study, we analysed the official instructions, the official resources for teachers and particular textbooks (we focused on the knowledge to be taught, but our analysis of textbooks also informs about the taught knowledge). For this purpose (addressing the didactic transposition in a given institution), it is not sufficient to study the discourse about algorithms: it is essential to examine the algorithms selected by the institution, their representations and the activities involving these algorithms: this can reveal differences (and even contradictions) with the general discourse. To do this, for each resource, we answered to the following questions:

 What kind of definition of algorithm is proposed?  What algorithms (or types of algorithms) have been selected?  What representations of algorithm are used?  What tasks (or types of tasks) in Algorithmics are proposed? Answering these questions brings elements that permit to address our principal question:

 What aspects of algorithm are presented (according to the five fundamental aspects)? Do this aspect relate to algorithm as a tool or as an object?

Our corpus of resources is described in Table 1. In the following, we present the results of our analyses and the answers to the research questions. As we cannot provide all details in this paper, we present only the main results of the comparison. Before that, it is necessary to give an overview of the situation in France and Ukraine, regarding the teaching of Algorithmics. [START_REF] Bosch | Introduction to the Anthropological Theory of the Didactic (ATD)[END_REF], 2015, Ryvkind J.Ya. et al., 2014, 2015) for grades 6 and 7, part 'Algorithmics'.

Presentation of the contexts and evolutions of curricula in Ukraine and France

Situation in Ukraine (organization, history and recent evolutions)

The Ukrainian school system consists of primary school (grades 1-4, age of pupils -6-9 years), middle school (grades 5-9, 10-15 years) and high school (grades 10-11, 16-17 years). In high school pupils make a choice between general or professional-oriented paths. Informatics has been taught since 1985 in secondary school in USSR. From the beginning, Algorithmics was a part of it. At that time, the course was mainly dedicated to writing algorithms in pseudo-code and executing them manually. Only two programming languages were used: Rapira (especially elaborated in USSR for teaching) and Basic. The major part of the first manual of Informatics in USSR is devoted to solving algorithmic problems. An algorithm is defined as "a clear and precise instruction destined to an operator to carry out a sequence of actions in order to reach a goal or solve a problem". In this manual, the notion of operator plays a central role. It is also underlined that an operator executes an algorithm formally, i.e. it can carry out operations one by one in defined order without understanding the goal. A scheme for solving a problem with a computer is presented: in brief, it consists of modelling the problem, constructing an algorithm, writing it in a programming language, executing it, and analysing the results. Many tasks require constructing algorithms for solving mathematical and physical problems with a computer, such as Horners' method or the approximation of the area under the graph of a positive function.

Since 1985, Informatics has always been a mandatory subject in high school. In the programs published in 2008, Informatics can be taught at the following levels: standard (for general and humanitarian paths), academic (for science path), professional and advanced (for informatics and mathematics paths). The difference is the number of hours of Informatics per week (between 1 and 5) and the contents. As a part of the subject, Algorithmics is studied at every level with a total amount of hours that varies a lot: Standard (5), Academic (28), Professional (175), Advanced (191).

In 2013, Informatics also became a mandatory subject in primary (from grade 2) and middle school. Thus, at the moment, Algorithmics is also present in middle school (from grade 6).

Situation in France (organization, history and recent evolutions)

The secondary French school system consists of middle school (collège, grades 6-9, 11-15 years) and high school (lycée, grades 10-12, 16-18 years). In high school, professional, technical and general orientations are proposed, and the general orientation is divided into humanities, economic and scientific paths2 . In this study, we will concentrate on the general orientation. Recently, many reforms happened in the French curricula, the last one was in 2016 and concerned middle school. Starting from 2016, Informatics will also be taught in middle school (principally in grades 7-9) in the mathematics and technology classes. Few years before that (from 2009 for grade 10 to 2012 for grade 12), some contents of Algorithmics were introduced in the curricula of Mathematics in high school [START_REF] Modeste | The appearance of algorithms in curricula, a new opportunity to deal with proof[END_REF].

Comparison at high school level (grades 10-12, ages 15-18)

Algorithmics in high school in Ukraine

Through all grades and levels, a common approach to Algorithmics can be identified. It includes the presentation of the steps for solving problems using a computer and the role of algorithms in this process, distinguishing algorithms from programs, with an emphasis on the notion of operator. The activities involve various representations of algorithms (common language, flowchart and program).

In the analysed textbooks the term algorithm is defined as a finite sequence of instructions that determines what operations and in which order to carry out for obtaining a goal. In this definition, as well as in the description of the properties of an algorithm (discreteness, certitude, feasibility, finiteness, effectiveness) given explicitly at all levels, we can identify the aspect effectiveness. The problem aspect is expressed in the property of "generality" of an algorithm, which says that an algorithm applies to a set of similar problems, which have the same question and solving procedure and differs only by the values of initial data. At the same time, the specific term "instance algorithm" is used in the textbooks to define an algorithm that solves only one case of a problem. Most part of the proposed instance algorithms are: algorithms of daily life (e.g., preparing meal), algorithms from others disciplines (e.g., geometrical constructions), algorithms implementing a strategy (e.g., the wolf, goat, and cabbage problem). The expected competence is to represent the solution of a problem in an algorithmic way (as a sequence of instructions) rather than to solve it.

At standard level, many tasks concern the construction of algorithms for a given operator. The activity is centred on identifying the system of commands of an operator and writing an algorithm using only these commands. Although, most of the problems are quite easy and the goal of the tasks is to find the best strategy and present it in the required form. This concerns principally instance algorithms and refers to the effectiveness aspect. Generic algorithms (algorithms with many instances) mostly relate to solving mathematical problems (solving equations, evaluating the area of a polygons.) and computations (evaluation of simple expression). Pupils construct algorithms, describe them in the requested form (principally flowcharts) and execute them manually.

At academic level, Algorithmics is based on Delphi, an object-oriented programming language: pupils get accustomed to Algorithmics by learning the instructions of Delphi. 65% of the tasks are about writing programs, executing and modifying them, 19% of tasks are devoted to object-oriented programming. Algorithms are mostly verified by testing the programs. Generic algorithms are more present than instance algorithms. Most of them concern computations (e.g., evaluation of simple expressions) (33 %) and solving mathematical problems (e.g., solving equations, primality test) (31%). A bit less tasks concern the computation of sequences, products, sums (11%) and data treatment (e.g., sorting, searching in an array) (17 %). The textbook includes many tasks where an algorithm is only used for formulating a procedure before programming it. One can also found tasks where algorithms plays the role of tool for problem solving (e.g., finding the divisors of an integer).

In this case, the focus is more on the construction of algorithms than on writing and debugging programs. Although we found many generic algorithms, only the effectiveness and problem aspects are strongly present. The complexity aspect is only evoked concerning the binary search algorithm.

At professional and advanced levels, an algorithm is presented not only as tool but also as an object. At professional level we found many "rich" algorithms, such as recursive algorithms, algorithms on graphs, algorithms of treatment of stacks and lists, etc. Expected competences for pupils are not only to understand some algorithms and write programs, but also to analyse algorithms' efficiency and compare them. The complexity aspect is also evoked. At advanced level the theoretical models aspect is present (e.g., NP-complete problems). Expected competences concern the abilities to choose an algorithm appropriate to a problem, to compare algorithms according to their complexity, to analyse and compare algorithms. Algorithm is present as an object.

Algorithmics in high school in France

Programs of Mathematics for high school, for all levels, contain the same Algorithmics part, with a list of expectations for the end of high school: pupils must be able to "describe algorithms in natural and symbolic languages", to "carry out some of them using a spreadsheet or a small program written in a calculator or a software" and "interpret more complex algorithms". It is mentioned that "algorithmics has a natural place in all the mathematical subjects". Pupils must learn elementary instructions, conditional instructions and loops. At each level, few specific algorithms are mandatory, e.g. plotting a curve (grade 10); solving equations of the type f(x)=0; simulating random experiments (grade 12, scientific path). Most of the algorithms in the programs deal with sequences, numerical methods and simulations in probability and statistics. Algebra and geometry are just mentioned as fields for algorithmic activities. Discrete Mathematics have a very little presence. The priority seems to be given to the implementation of algorithms in a programming language.

The accompanying resource for grade 10that seems to have driven the approach to Algorithmics in high school [START_REF] Modeste | Enseigner l'algorithme pour quoi ? Quelles nouvelles questions pour les mathématiques ? Quels apports pour l'apprentissage de la preuve[END_REF] does not define the term algorithm, and does not even distinguish it from the term program. The activities are focused on language and rigorous expression of operations, and often aim at writing programs. It results in a confusion between program and algorithm that indicates a focus on the effectiveness aspect. A specific language to describe algorithms is implicitly developed, mixing pseudo-code and technical programming constraintsthat we called paper-program [START_REF] Modeste | Enseigner l'algorithme pour quoi ? Quelles nouvelles questions pour les mathématiques ? Quels apports pour l'apprentissage de la preuve[END_REF]. Many instance algorithms are present, which confirms a confusion between writing algorithms and describing step-by-step operations.

In the studied textbooks for all levels, we can see the strong influence of this accompanying resource. Most algorithms are described as "paper-programs" before being implemented (generally as immediate translation). Many exercises deal with interpreting, writing or translating algorithms in a given language. Algorithm is only shown as a tool, even the problem aspect has little presence. In the program for the ISN option, the approach differs. The program explicitly defines the notion of algorithm and mentions that it must be distinguished from the notion of program. Algorithmics is presented as a branch of Informatics and algorithms are not restricted to programming. The concept of algorithm appears as a tool and as an object (complexity and proof aspects are present).

Comparison in high school

In Ukraine as in France, the effectiveness aspect is central. In all levels, algorithm is used as a tool, but the problem aspect is more developed in Ukraine. Algorithm is treated as an object only at professional and advanced levels in Ukraine, and in the ISN option in France. We could have expected them to appear in the French scientific paths but it is not the case. In Ukraine, the approach to Algorithmics seems to be guided by the development of algorithmic thinking whereas in France the focus is on the programming and language skills. It appears clearly in the texbooks: in Ukraine, the concept of algorithm is defined and a list of its properties is given, whereas, in France, an algorithm is defined by the language that describe it. Although in France, Algorithmics is taught in the Mathematics class, the focus on programming seems to be stronger than in Ukraine for standard level, where programming is not required and the focus is on elementary algorithmic thinking. In Ukraine, two features can be highlighted, probably inherited from historical context of teaching of Informatics in USSR: significant role of the scheme of problem solving (presumably influenced by the problem-solving theories) and the emphasis put on the notion of operator. In France, in Mathematics, algorithms are used to solve mathematical problems and are considered as a mean to deal with the mathematical concepts. The important presence of programs for simulations in probability or for embodying properties of mathematical objects attests to this point of view. The approach developed in ISN, in France, is close to the approach proposed at professional and advanced levels in Ukraine. They involve advanced concepts and aim at developing advanced algorithmic thinking, but we suspect a difference between the programs and the taught knowledge.

Comparison at middle school level (grades 6-9, ages 11-15)

Algorithmics in middle school in Ukraine

In the programs for grades 6 and 7, the part devoted to Algorithmics is similar to the program for standard level of high school. Although the program declares programming as one of the pupils' activities, it does not specify any programming language to use. In the textbooks for grades 6 and 7, an algorithm is defined as a finite sequence of instructions to be carried out for solving a problem.

As we can see, in the given definition the effectiveness and problem aspects are on the first plan. At the same time, the fact that an algorithm solves all instances of a problem is not presented. The main part of proposed problems concerns the construction of instance algorithms for different operators.

Both textbooks propose to program in Scratch. Pupils' activity is focused on developing programs and projects, using this programming environment. In grades 8 and 9, the Algorithmics part of the program is devoted to object-oriented programming. In grade 8, the notion of variable and different types of data are introduced. In grade 9, search algorithms in arrays are studied. The expected competences of pupils refer mostly to writing, modifying and debugging programs. The aspects related to algorithm as an object are not present.

Algorithmics in middle school in France

In 2016, Informatics appeared in middle school. Algorithmics contents essentially appeared in the Mathematics course, in the cycle 4 (grades 7-9), in the theme "Algorithmics and Programming". Textbooks for this reform were not available at the time of the study, so we only analysed the programs. One general competence guides the program: "write, elaborate and execute a simple program". Then, more specific competences are listed (decomposing a problem into sub-problems, designing a program to solve a problem; writing programs driven by events; and writing parallel programs) and contents are specified: notions of algorithm and program; variables in Informatics; event-driven action, sequence of instructions, loops, conditional instructions; exchanged messages between objects. These contents are strongly oriented towards programming and, even if it is not declared, the software Scratch must be used to teach these notions. The chosen approach implies developing projects and games (in order to develop pupils' reasoning) and does not focus only on mathematical concepts. Effectiveness aspect of algorithm is present and problem aspect is more notable than in the high school curricula. Contrary to the approach proposed in Mathematics in high school, Algorithmics is introduced by programming (independently from mathematical contents).

Comparison in middle school

In France and in Ukraine, in middle school, algorithm is presented as a tool. The effectiveness aspect is dominant. Although the problem aspect is mentioned, the role of algorithms for problem solving and the place for generic algorithms are not clear. At this level, the complexity and proof aspects are not proposed. Contrary to the curricula for high school, there are more similarities between the two curricula for middle school. Particularly, the notions of algorithm and program are distinguished; the introduction to Algorithmics includes event-driven programming in Scratch, and objects and variables are introduced later. The approach is based on solving concrete problems and developing projects in Informatics and in other disciplines. This could be explained by the influence of an international movement towards the teaching of Informatics in primary and middle school. Nevertheless, there are also important differences. In France, the most part of the proposed projects are in Mathematics (maybe because it will be taught by Mathematics teachers, not well trained yet in Informatics), and there is a strong focus on programming (in a different way from high school). In Ukraine, the notion of operator is still highlighted, representations of algorithms with schemes and flowcharts are requested and many examples of algorithms are taken from everyday life. This is directly inherited from the didactic transposition proposed in the 1980's and today in high school.

Conclusions and perspectives

On the one hand, this comparative analysis of the didactic transposition of the concept of algorithm and Algorithmics in secondary school in France and Ukraine brings out differences that reveal the impact of institutions, traditions and historical contexts on the curricula. The comparison of two contexts where Algorithmics is not a part of the same course (Mathematics versus Informatics) shows the influence of these disciplines on the contents, on the points of view on Algorithmics and on the algorithmic activity. On the other hand, in the two countries, we see general orientations in middle school that seem to be part of an international movement towards the teaching and learning of Informatics. This study contributes to understand and improve curricula, by taking into account the points of view of Mathematics and Informatics on Algorithmics. It gives perspectives to study the development of algorithmic thinking, and the teaching and learning of Algorithmics' concepts.

Table 1 : Analysed resources.

 1

  Gueudet, Bueno-Ravel, Modeste and Trouche (to appear) give more details about the evolution of French mathematics curricula, including Algorithmics. Informatics appeared for the first time in the French curricula in the 1980's[START_REF] Baron | L'informatique et son enseignement dans l'enseignement scolaire général français: Enjeux de pouvoirs et de savoirs[END_REF], with an introduction to Programming and Algorithmics in high school. It disappeared in the 1990's, replaced by the use of computer tools and new technologies. Recently, Informatics came back in secondary school. In 2012, an optional course was created in grade 12 in the scientific path (ISN: "Informatics and digital sciences", 2h/week), and in 2015, an optional course appeared in grade 10 ("Informatics and Digital Creation", 1h30/week).

Proceedings of CERME10

For details about French system: http://eduscol.education.fr/cid66998/eduscol-the-portal-for-educationplayers.html Thematic Working Group 11 Proceedings of CERME10