Vasilis Dakos
email: vasilis.dakos@umontpellier.fr

Blake Matthews
email: blake.matthews@eawag.ch

Andrew Hendry

Jonathan Levine

Nicolas Loeuille

Jon Norberg

Patrik Nosil

Marten Scheffer

Luc De Meester

Ecosystem tipping points in an evolving world

Keywords: resilience, evo-to-eco, contemporary evolution, catastrophic shifts, eco-evolutionary dynamics, traits

à la diffusion de documents scientifiques 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.

Tipping points in an evolving world

Tipping points mark the abrupt shift between contrasting ecosystem states (broadly termed regime shifts) when environmental conditions cross specific thresholds (Box 1). Prominent examples are the shift of shallow lakes from a clear to a turbid water state [START_REF] Scheffer | Alternative equilibria in shallow lakes[END_REF] , or the collapse of vegetation to a desert state in drylands [START_REF] Reynolds | Global Desertification: Building a Science for Dryland Development[END_REF] . Societal stakes associated with tipping points in natural ecosystems can be high and there is great emphasis on the mechanisms that trigger them [START_REF] Oliver | Biodiversity and Resilience of Ecosystem Functions[END_REF] and the possible ways to detect and avoid them [START_REF] Scheffer | Critical Transitions in Nature and Society[END_REF] . Currently, however, tipping point theory largely lacks an evolutionary perspective, and this might limit our understanding of the occurrence, timing, and abruptness of shifts between states (Box 1, Figure I). Here we argue that both trait variation and evolution are important for understanding ecosystem dynamics in the vicinity of tipping points. Developing a trait-based evolutionary perspective about tipping points in ecosystems is warranted by the growing evidence that changes in standing levels of trait variation and contemporary trait evolution are important drivers of ecological processes (e.g. [START_REF] Saccheri | Natural selection and population dynamics[END_REF][START_REF] Kinnison | Eco-evolutionary conservation biology: Contemporary evolution and the dynamics of persistence[END_REF], by influencing population dynamics (Yoshida et al. 2003), shaping the structure of species interactions in communities [START_REF] Pantel | Rapid local adaptation mediates zooplankton community assembly in experimental mesocosms[END_REF] , or affecting species composition at the metacommunity level [START_REF] Farkas | Evolution of camouflage drives rapid ecological change in an insect community[END_REF] . Such ecological effects of evolution also extend to ecosystem functioning [START_REF] Norberg | Phenotypic diversity and ecosystem functioning in changing environments: a theoretical framework[END_REF][START_REF] Matthews | Toward an integration of evolutionary biology and ecosystem science[END_REF][START_REF] Hendry | Eco-evolutionary Dynamics[END_REF] , by modifying material fluxes [START_REF] De Mazancourt | Grazing optimization and nutrient cycling: When do herbivores enhance plant production?[END_REF] , primary production [START_REF] Gravel | Experimental niche evolution alters the strength of the diversityproductivity relationship[END_REF] , nutrient recycling [START_REF] Loeuille | Consequences of plant-herbivore coevolution on the dynamics and functioning of ecosystems[END_REF] , and decomposition [START_REF] Boudsocq | Plant Preference for Ammonium versus Nitrate: A Neglected Determinant of Ecosystem Functioning?[END_REF] . Changes in life-history traits caused by environmental stress (like fishing) have been shown to destabilise dynamics of populations [START_REF] Anderson | Why fishing magnifies fluctuations in fish abundance[END_REF] or whole communities [START_REF] Kuparinen | Fishing-induced life-history changes degrade and destabilize harvested ecosystems[END_REF] , and even increase their risk of extinction [START_REF] Hutchings | Marine fish population collapses: Consequences for recovery and extinction risk[END_REF] .

Fitness-related traits (e.g. body size) can systematically change before populations collapse [START_REF] Clements | Including trait-based early warning signals helps predict population collapse[END_REF] and can be used as indicators of biological transitions [START_REF] Clements | Indicators of transitions in biological systems[END_REF][START_REF] Spanbauer | Body size distributions signal a regime shift in a lake ecosystem[END_REF] . Thus, it is reasonable to expect that changes in trait distributions might be important for understanding ecological tipping points as they might affect the variation in the sensitivity to environmental stress among species, populations, or individuals in an ecosystem [START_REF] Peterson | Ecological resilience, biodiversity, and scale[END_REF][START_REF] Elmqvist | Response diversity, ecosystem change, and resilience[END_REF] . This sensitivity underlies the response capacity of communities to stress [START_REF] Vellend | Connections between species diversity and genetic diversity[END_REF][START_REF] Enquist | Scaling from Traits to Ecosystems[END_REF] such that trait changes could affect the resilience of entire ecosystems [START_REF] Mori | Response diversity determines the resilience of ecosystems to environmental change[END_REF] and their probability of tipping to a different state. It is the effect of evolutionary trait changes on tipping points at the ecosystem level that we are focusing on in this perspective.

Ecosystem resilience can be affected by variation in traits [START_REF] Norberg | Phenotypic diversity and ecosystem functioning in changing environments: a theoretical framework[END_REF][START_REF] Matthews | Toward an integration of evolutionary biology and ecosystem science[END_REF] underlying the performance and fitness of organisms in a given environmental state (i.e. response traits), or those causing direct or indirect effects on the environmental state (i.e. effect traits) (Table 1). The distribution of such response and effect traits can vary due to phenotypic plasticity, species sorting, or evolutionary trait change, and distinguishing between these mechanisms can be important for understanding the ecological dynamics of trait change in general [START_REF] Cortez | Comparing the qualitatively different effects rapidly evolving and rapidly induced defences have on predator-prey interactions[END_REF] , and of tipping points in particular. Phenotypic plasticity, where genotypes exhibit different phenotypes in different environments, is a relevant source of trait variation, particularly when the phenotypic changes relate to the capacity of organisms to respond to stress. However evolutionary responses to stress depend on heritable trait variation in a population [START_REF] Hansen | Monitoring adaptive genetic responses to environmental change[END_REF] , which can originate from novel variants due to mutation [START_REF] Nei | The new mutation theory of phenotypic evolution[END_REF] , recombination [START_REF] Ortiz-Barrientos | Recombination Rate Evolution and the Origin of Species[END_REF] , or gene flow among populations and species [START_REF] Seehausen | Hybridization and adaptive radiation[END_REF] .

Below, we do not a priori distinguish between the genetic versus plastic sources of trait distributions (although we comment on their differences), but focus on how trait variation and trait change over time can influence ecosystem tipping points in a generic way. We do this using a graphical approach where we illustrate how trait changes might modify the collapse and recovery trajectories of ecosystems along an environmental gradient.

Trait variation could affect the probability of tipping points

Differences in the amount of trait variation within or among populations could affect their response capacity to stress. In general, we predict that high trait variation may decrease the probability of tipping points turning ecosystem responses to non-catastrophic. A decrease in the probability of tipping events occurs because standing trait variation allows for portfolio effects that introduce strong heterogeneity in population processes, interactions, and responses [START_REF] Bolnick | Why intraspecific trait variation matters in community ecology[END_REF] buffering population dynamics [START_REF] Schindler | Population diversity and the portfolio effect in an exploited species[END_REF] . Such heterogeneity can be enhanced by Jensen's inequality [START_REF] Bolnick | Why intraspecific trait variation matters in community ecology[END_REF] , where variation around the mean of a trait can affect the response of an ecological interaction or an ecological process in function of the nonlinear relationship between the trait and its effect [START_REF] Ruel | s inequality predicts effects of environmental variation[END_REF] . This effect can be clearly illustrated in a toy model describing shifts in the case of shallow lakes (Figure I in Box 1). Here, changing the amount of variation in the macrophytes' response trait to turbidity can increase or decrease the probability of a tipping point response.

Under high levels of variation the transition from the clear to the turbid water state can even become non-catastrophic with no alternative states (Figure 1).

Trait change can delay a tipping point

As introduced in the previous paragraph, trait variation simply means that some resistant phenotypes are present. However, trait variation could also facilitate trait changes. On top of that, trait changes might be fueled by de novo mutation and phenotypic plasticity. In ecosystems where stress gradients bring them closer to tipping points, trait changes could potentially delay tipping to the alternative state (Figure 2a). This resonates with the idea of evolutionary rescue [START_REF] Gomulkiewicz | When does evolution by natural selection prevent extinction?[END_REF][START_REF] Bell | Evolutionary rescue can prevent extinction following environmental change[END_REF] , the difference being that there is no rescue, but rather only a delay in the collapse of the system by shifting the threshold at which the collapse occurs at a higher stress level (Figure 2b). For instance, in the case of a shallow lake turning turbid due to eutrophication (Box 1), aquatic macrophytes might delay the transition to a higher threshold level of nutrients because of contemporary changes in traits that convey tolerance to shading (Table 1).

Trait change can lead earlier to a tipping point

Trait change may not always buffer populations from environmental changes, but could also contribute to an increased risk of ecosystem collapse (Figure 2c,d). For example, environmental stress could impose directional selection on a trait in a given species or group of species that brings the system closer to tipping to an alternative ecological state [START_REF] Dieckmann | Evolutionary Conservation Biology[END_REF][START_REF] Rankin | Can adaptation lead to extinction?[END_REF] . This is similar to evolutionary collapses or evolutionary suicide as defined in evolutionary biology [START_REF] Gyllenberg | Necessary and sufficient conditions for evolutionary suicide[END_REF][START_REF] Ferriere | Eco-evolutionary feedbacks, adaptive dynamics and evolutionary rescue theory[END_REF] , but here the collapse occurs at the scale of a whole ecosystem. Empirical examples of trait evolution leading to population collapse come mostly from fish populations under harvesting [START_REF] Rankin | Can adaptation lead to extinction?[END_REF][START_REF] Walsh | Maladaptive changes in multiple traits caused by fishing: Impediments to population recovery[END_REF] . For example, it has been shown how fishing pressure has led to the early maturation of Atlantic cod populations [START_REF] Olsen | Maturation trends indicative of rapid evolution preceded the collapse of northern cod[END_REF] that is associated with lower reproductive output and irregular recruitment dynamics that could have increased the chance of stochastic extinction and the cod collapse in the 1990s. Evolutionary suicide might lead to an ecosystem-level collapse in the case of drylands [START_REF] Kéfi | Evolution of local facilitation in arid ecosystems[END_REF] , where under increased aridity adaptive evolution can favor local facilitation among neighboring plants for resisting higher aridity. Whether evolution leads to a buffering effect depends on the seed dispersal strategy of the dominant vegetation type. In systems characterized by long-distance dispersal, evolution may actually enhance the collapse of the vegetation to a desert state due to the invasion of non-facilitating mutants. In our shallow lake example, macrophytes at intermediate turbidities might respond by growing longer stems with fewer leaves in order to reach well-lit surface waters and avoid shading. If this, however, results in less photosynthetic activity and less capacity to remove nutrients from the water column, it might reduce the capacity to outgrow the algae and maintain a clear water state.

Trait change can affect the path of recovery

Changes in trait distributions over time may also affect the recovery trajectory of an ecosystem back to its previous state and the range of hysteresis, i.e. the lag in the threshold of the environmental driver at which recovery to the pre-collapsed state occurs (see Box 1 and Box 3 (Glossary)). The most obvious example is the case where trait change delays a tipping point (Figure 3). In many cases, this delay will not necessarily result in an equally early recovery, which implies that hysteresis in the system will increase. This example illustrates that tipping points and hysteresis are the flip side of mechanisms buffering the stable states: if evolution or phenotypic plasticity buffers the system against environmental change, this can not only delay reaching a tipping point but it may also result in stronger hysteresis.

Another possibility is that evolutionary processes in the deteriorated state might cause the collapsed species to lose the genetic variation necessary for recovery to, and high fitness in, the alternate state [START_REF] Murray | Natural selection shaped the rise and fall of passenger pigeon genomic diversity[END_REF] . In a laboratory experiment, ref. [START_REF] Walsh | Maladaptive changes in multiple traits caused by fishing: Impediments to population recovery[END_REF] found that overharvested fish populations failed to recover even after reducing fishing pressure due to genetic changes in life history traits. This may result in a delay in recovery, or no recovery at all. The opposite scenario is also possible. Trait changes may accelerate recovery and reduce hysteresis (Figure 3). This may happen if, after the collapse, a highly adaptive phenotype is selected for facilitating recovery only at a small reduction of stress. For example, after the collapse of a phytoplankton population due to light stress in the laboratory, recovery took place earlier than expected due to a (probably plastic) adaptive photo-acclimation response [START_REF] Faassen | Hysteresis in an experimental phytoplankton population[END_REF] . If after the collapse a different phenotype is selected for, or if there is recovery of the lost phenotypic variation (e.g. due to immigration), it may even be possible that the recovery pattern becomes non-catastrophic.

In all cases highlighted in the previous paragraphs, it is uncertain whether the ecosystem will actually recover to the exact same state as before the collapse (Figure 3). The degree to which complete recovery happens might probably depend on the trait that changes. It is a key open question whether trait changes that impact the probability of tipping also impact recovery trajectories.

Phenotypic plasticity, evolution and tipping points

There are more possibilities for the collapse and recovery paths of the ecosystem state than the ones we highlighted here. All will depend on the mechanisms of phenotypic change and it requires both theoretical and empirical work to understand the most probable outcomes on tipping point responses that would result either from evolution, from phenotypic plasticity, or from their combined effect, including even the evolution of phenotypic plasticity. One reason why the distinction between phenotypic plasticity and evolutionary trait change is important is that the rates at which these processes operate tend to differ, with phenotypic plasticity being generally faster than evolutionary change. Conversely, phenotypic plasticity is often limited in amplitude, and evolutionary trait change might extend the range to which tipping points and hysteresis can be impacted. Importantly, trait change due to evolution also has an intrinsic impact on the population genetic structure that entails a legacy that may impact recovery (e.g. case of genetic erosion or a trait change that is adaptive in one stable state but maladaptive in the other state), whereas trait change mediated by phenotypic plasticity may impact tipping points without a legacy effect if the trait change is reversible.

Testing the effects of phenotypic change on tipping point responses

Integrating evolutionary dynamics in models of ecological tipping points

Coupling models on evolutionary dynamics with models of ecological bistability can offer a better understanding about when genetic trait change can affect tipping point responses. The adaptive dynamics framework -that assumes limited mutation and the separation of ecological and evolutionary timescales -has been used to study how evolution may incur evolutionary collapse and suicide [START_REF] Dieckmann | Evolutionary Conservation Biology[END_REF] . Under rapid environmental change, a quantitative genetics approach [START_REF] Abrams | Adaptive Dynamics' vs. 'adaptive dynamics[END_REF] is useful for studying how contemporary genetic trait change may lead to evolutionary rescue.

Both modelling frameworks can be adapted for studying how trait changes might affect well-understood models with ecological tipping points under changing environmental conditions.

For instance, we could relax the assumption on the separation of timescales and the assumption of weak selection of each framework, respectively, and apply them to models with tipping points. Or one could develop hybrid models that can account simultaneously for selection gradients, while also accounting for genetic drift and demographic stochasticity that dominate the recovery trajectory of the collapsed state. We can then combine these models with recently developed methods that measure the relative impact of evolutionary vs ecological dynamics on stability (Patel et al. 2016) to understand when and how evolutionary dynamics can affect the probability of tipping responses.

Such modelling approaches can help to (i) compare how different mechanisms of trait change (genetic vs plastic) could affect tipping point responses, (ii) identify the conditions (e.g. rate and pattern of environmental stress, rate of trait evolution, costs and trade-offs) under which trait evolution will modify collapse and recovery trajectories, or even (iii) test when trait change itself could be so abrupt (due to disruptive selection) that it could cause ecosystem tipping points. In that way we could develop novel ways for detecting tipping points based on changes in ecological and trait dynamics (Box 2), and suggest new designs for experimental testing.

Adding evolutionary contrasts to experimental tests of ecological tipping points

There are two common approaches for experimentally testing tipping point theory. The first approach starts by establishing two alternative states of the system on either side of a tipping point, and then testing how the system responds to pulse perturbations of a state variable. For example, if there is evidence for a positive feedback (Box 1) in two states with a different dominant species in each community, then the outcome of species dominance might strongly depend on the initial density of species (i.e. priority effects) [START_REF] Fukami | Productivity -biodiversity relationships depend on the history of community assembly[END_REF] . The second approach starts with the system in one state, and then applies a press perturbation of an environmental condition (e.g. increasing productivity, increasing mortality) to observe when the system transitions to a new state [START_REF] Dai | Generic Indicators for Loss of Resilience Before a Tipping Point Leading to Population Collapse[END_REF][START_REF] Veraart | Recovery rates reflect distance to a tipping point in a living system[END_REF][START_REF] Sirota | Organic-matter loading determines regime shifts and alternative states in an aquatic ecosystem[END_REF] . To test for hysteresis in the system, the environmental condition can then be reversed while tracking system recovery to the initial state [START_REF] Faassen | Hysteresis in an experimental phytoplankton population[END_REF][START_REF] Lau | Regime shifts and hysteresis in the pitcher-plant microecosystem[END_REF] .

Independently manipulating evolutionary and ecological components of a system can provide new insights into how the dynamics of trait change can affect tipping points. Several experiments have been designed to study the interplay between ecological and evolutionary dynamics [START_REF] Pantel | Rapid local adaptation mediates zooplankton community assembly in experimental mesocosms[END_REF][START_REF] Farkas | Evolution of camouflage drives rapid ecological change in an insect community[END_REF][START_REF] Becks | Reduction of adaptive genetic diversity radically alters eco-evolutionary community dynamics[END_REF]53 , and these could be usefully co-opted to experimentally test predictions from tipping point theory. A key challenge in these experiments will be to identify and be able to measure the variation of the relevant traits like the ones we highlight in Table 1. Clearly, the selection of traits to study and monitor should start by understanding the specifics of the study system and the mechanisms underlying the tipping points. Although it is challenging to quantify selection gradients in natural populations, useful estimates can be obtained from a wide range of traits (e.g. body size, condition) underlying individual performance [START_REF] Franklin | Inference of selection gradients using performance measures as fitness proxies[END_REF] . In one study of a tipping point induced in the laboratory with freshwater cyanobacteria [START_REF] Faassen | Hysteresis in an experimental phytoplankton population[END_REF] , light level was manipulated to test for hysteresis associated with transitions between a high and low biomass state. Contrary to predictions from an ecological model, the population recovered to a higher light stress faster than expected. In the experiment, the recovering cells had lower pigment concentrations, possibly reflecting adaptation to high irradiance conditions at a cost of photosynthetic efficiency at lower light irradiance. This suggests that the presence of trait variation (i.e. pigment production) in the population influenced the nature of the transition between the two states. A useful experimental test of this idea would be to manipulate standing levels of genetic variation in the stressed population and measure if tipping points change. Adding such evolutionary contrasts to ecological experiments would be a fruitful way to test how both trait variation and evolution may affect tipping points. In experimental systems it is possible to isolate the effects of density and diversity (ecological effects) from the effects of heritable trait change (evolutionary effects). Specifically, one might be able to differentiate between purely ecological effects, direct evolutionary effects linked to changes in functional effect traits, and density-mediated indirect evolutionary effects linked to changes in functional response traits [START_REF] Patel | Partitioning the effects of eco-evolutionary feedbacks on community stability[END_REF] .

Closing the loop: eco-evolutionary feedbacks and tipping point responses

Reciprocal interactions between ecological and evolutionary dynamics is an old idea (e.g. [START_REF] Pimentel | Population regultion and genetic feedback[END_REF][START_REF] Levins | Evolution in changing environments: some theoretical explorations[END_REF] ) that is increasingly being tested across a range of systems and study questions (e.g. [START_REF] Hendry | Eco-evolutionary Dynamics[END_REF][START_REF] Fussmann | Eco-evolutionary dynamics of communities and ecosystems[END_REF] ). Here, we focused on the potential implications that heritable trait changes can have for ecological tipping points. The next step is to understand how reciprocal feedbacks between ecological tipping points and evolutionary dynamics might radically alter not only the dynamics of ecosystems close to tipping but also the evolution of populations and communities of these ecosystems. Tipping points between contrasting ecosystem states create different selection regimes that can shape the evolution of focal species (like keystone, or ecosystem engineers species) and in their turn the dynamics of the ecosystem state they belong to [START_REF] Matthews | Under niche construction: an operational bridge between ecology, evolution, and ecosystem science[END_REF] . One possibility is that such selection regimes will be asymmetric, leading to evolutionary reversals, for example in body sizes in grazed populations [START_REF] Dercole | Ecological bistability and evolutionary reversals under asymmetrical competition[END_REF] , or could maintain the recurrence of harmful algal blooms in lakes [START_REF] Driscoll | Eco-evolutionary feedbacks between private and public goods: Evidence from toxic algal blooms[END_REF] .

It remains an outstanding challenge to test these ideas. It will be important to identify under which conditions (e.g. type of environmental stress, type of response/effect trait, level of genetic variation, plasticity, spatial and temporal scales) trait change would modify tipping point responses. Under high rates of environmental change, trait changes may be too slow [START_REF] Delong | How fast is fast? Eco-evolutionary dynamics and rates of change in populations and phenotypes[END_REF] to have effects on ecological dynamics. Yet, traits of organisms with short generation times or with high levels of standing genetic polymorphism would be most likely best candidate traits to change, but it is unclear how the speed of evolutionary change will be affected by the level of selective pressure prior and past a tipping point. It might be that trait changes that may impact ecosystem collapse are very different to the ones that impact recovery trajectories. Figuring out such relationships will help us study the type of eco-evolutionary feedbacks that could develop along the collapse and recovery trajectories of ecosystems with tipping points. Ultimately one might even address the question about whether ecological bistability can lead to bistability in trait values that has relevant implications in the process of speciation and species divergence.

Perhaps the biggest challenge is how to experimentally study the effects of trait change in ecosystems with tipping points. Most theoretical work on eco-evolutionary dynamics has been experimentally corroborated in laboratory experiments using organisms with short generation times [START_REF] Yoshida | Rapid evolution drives ecological dynamics in a predator -prey system[END_REF] . Similarly, ecological tipping points have been mostly studied in experimental microcosms at the population level with single species [START_REF] Dai | Generic Indicators for Loss of Resilience Before a Tipping Point Leading to Population Collapse[END_REF][START_REF] Veraart | Recovery rates reflect distance to a tipping point in a living system[END_REF] neglecting how synergistic effects across species can incur strong selection on trait changes [START_REF] Terhorst | Evolution in a Community Context: Trait Responses to Multiple Species Interactions[END_REF] . Ecosystem scale tipping points are harder to experimentally test (but see [START_REF] Carpenter | Early warnings of regime shifts: a whole-ecosystem experiment[END_REF] ) and simultaneous information on trait variation of the organisms involved is rarely available. Yet, we can identify excellent candidate traits for study.

For instance, light sensitivity of submerged macrophytes [START_REF] Van Dijk | Survival of a Potamogeton pectinatus L. population under various light conditions in a shallow eutrophic lake Lake Veluwe in The Netherlands[END_REF] is an important response trait in models of lake shifting to a turbid state [START_REF] Hilt | Response of Submerged Macrophyte Communities to External and Internal Restoration Measures in North Temperate Shallow Lakes[END_REF] , whereas the effect of macrophytes on nutrient concentrations [START_REF] Van Donk | Macrophyte-related shifts in the nitrogen and phosphorus contents of the different trophic levels in a biomanipulated shallow lake[END_REF] might be governed by rates of nutrient uptake [START_REF] Madsen | Sources of nutrients to rooted submerged macrophytes growing in a nutrient-rich stream[END_REF] . If we could start measuring such traits to get an idea of their variation, we could start unravelling how sustaining trait variation may be important not only for preventing collapse, but also for improving the success of ecological restoration. Despite the challenging task, the evolutionary perspective we advocate can improve our understanding and management of ecosystems under stress.

Table 1 Examples of ecosystem tipping points summarizing the organisms involved and the potential response and effect traits of these organisms. If these traits can experience phenotypic changes, they may affect the tipping point responses in any of the ways presented in the text . Response traits are defined as traits that respond to the environmental stressor(s) that can invoke a tipping point. Effect traits are defined as traits that may influence an ecosystem function that is linked to a tipping point. In the table we refer to the effect of such traits rather than the traits themselves. Representative references are also provided. Variation in a response trait (eg macrophyte shading tolerance) affects tipping points of shallow lake shifting to a eutrophic turbid state. a) The intersections of macrophyte and turbidity responses (M'= 0, T'= 0 nullclines) mark the equilibria of the system for two levels of trait variation in the shading tolerance of macrophytes. In the absence of variation (𝜎 ! = 0) there are two alternative equilibria (clear water and turbid water state at the crossing of solid green and brown lines). In the presence of variation (𝜎 ! = 0.75) , there is only a single equilibrium of clear water state with no tipping points (at the crossing of dashed green and solid brown lines).

b) Changing the level of trait variation in the response trait (eg shading tolerance) will affect the response of a shallow lake to environmental stress (turbidity). Under increasing trait variation hysteresis decreases, bistability disappears, and the tipping point turns into a gradual and noncatastrophic response. Extending similar models like the above along these directions will enable us to better understand the role of trait change and variation on ecological tipping points. Model details and parameters can be found in the Supplementary Information. Potential consequences of trait change on the recovery trajectories of an ecosystem after collapse (green dotted lines). Starting from a high value of environmental stress E, if stress is progressively reduced, the ecosystem recovers to the pre-collapse state at the tipping point following the black solid line (no phenotypic change trajectory). In the presence of phenotypic changes, recovery may be delayed or occur earlier (green dotted lines). This implies that phenotypic changes affect the range of hysteresis and the ease of recovery. In both cases, it is unclear whether the ecosystem shifts back to exactly the same state as before the collapse. It may even be possible that the collapse has allowed the emergence of a different (new) phenotype that could turn the recovery path non-catastrophic (smooth). [Solid lines represent the two alternative states of the reference model with no phenotypic change, dashed lines mark the unstable boundary between the two states, circles denote tipping points.]

Box 1: What is a tipping point?

Tipping points mark the shift between contrasting system states that occur when external conditions reach thresholds that trigger an accelerating transition to a contrasting new state [START_REF] Nes | What Do You Mean, 'Tipping Point'?[END_REF] .

Mathematically, these transitions correspond to saddle-node or fold bifurcation points [START_REF] Strogatz | Nonlinear Dynamics and Chaos with Applications to Physics[END_REF] . They are also called catastrophic because they mark an unexpected and radical change in the equilibrium state of a system. Tipping points can occur at population level (e.g. due to Allee effects [START_REF] Dai | Generic Indicators for Loss of Resilience Before a Tipping Point Leading to Population Collapse[END_REF] ) and community level (e.g. due to priority effects and competition [START_REF] Petraitis | Experimental confirmation of multiple community states in a marine ecosystem[END_REF] ), but it is at the ecosystem scale that tipping points are most prominently studied because they can incur longterm disruption to vital ecosystem services [START_REF] Barnosky | Approaching a state shift in Earth's biosphere[END_REF] . For example, clear lakes turn turbid dominated by algal blooms [START_REF] Scheffer | Alternative equilibria in shallow lakes[END_REF] , coral reefs get overgrown by macroalgae [START_REF] Knowlton | Thresholds and Multiple Stable States in Coral Reef Community Dynamics[END_REF] , fisheries collapse due to overexploitation [START_REF] Beddington | Harvesting natural populations in a randomly fluctuating environment[END_REF] , and tropical forests shift to savanna-type ecosystems under high fire intensity [START_REF] Staver | The Global Extent and Determinants of Savanna and Forest as Alternative Biome States[END_REF] .

Tipping points are typically observed in systems where strong positive feedbacks drive the establishment of alternative stable states [START_REF] Nes | What Do You Mean, 'Tipping Point'?[END_REF] . In the case of shallow lakes, dominance of aquatic macrophytes prevents the growth of algae by removing nutrients (phosphorus) from the water column that leads to the establishment of a stable clear water state (Fig I). When phosphorus loading exceeds a critical threshold macrophytes cannot successfully retain phosphorus, algae start to grow and lake turbidity increases. Rising turbidity kicks a vicious cycle: it hinders the growth of macrophytes but facilitates algae concentration in a self-enforced positive feedback loop (less macrophytes => more algae => more turbidity => less macrophytes and so on) that leads to the collapse of macrophytes and the establishment of a contrasting turbid lake state.

The same positive feedback loop can lead to the recovery of macrophytes, but this time at a lower critical level of phosphorus loading, where algae growth is limited to such an extent that turbidity decreases sufficiently for macrophyte to grow again, capture the phosphorus and reinforce a positive feedback loop leading back to the clear water state. Between these two tipping points, the system is bistable meaning that it can be found in one of the two alternative stable states. This difference in conditions that mark the forward and backward shift is called hysteresis. The stronger the hysteresis, the more difficult it is to recover an ecosystem back to its previous state. Ecological tipping points are difficult to detect. However, theory suggests that subtle changes in the dynamics of an ecosystem state can provide early-warning information on the underlying stability and risk of a tipping response [START_REF] Scheffer | Early-warning signals for critical transitions[END_REF] . This risk is typically quantified by indicators of resilience based on critical-slowing-down [START_REF] Dakos | Resilience indicators: prospects and limitations for early warnings of regime shifts[END_REF] , and include an increase in recovery time back to equilibrium after a perturbation, a rise in variance as the state of the ecosystem fluctuates more widely around its equilibrium, and an increase in autocorrelation because the state of the ecosystem resembles more and more its previous state close to a tipping point. These indicators have been empirically tested in laboratory experiments [START_REF] Dai | Generic Indicators for Loss of Resilience Before a Tipping Point Leading to Population Collapse[END_REF][START_REF] Veraart | Recovery rates reflect distance to a tipping point in a living system[END_REF] and in the field [START_REF] Carpenter | Early warnings of regime shifts: a whole-ecosystem experiment[END_REF][START_REF] Van Belzen | Vegetation recovery in tidal marshes reveals critical slowing down under increased inundation[END_REF] focusing on the dynamics of the ecosystem state (species cover, biomass or abundance), while neglecting any trait changes. Accounting for trait change creates new challenges but also opportunities in the detection of tipping points. On one hand, although slowing down indicators should be expected -at least based on ecological dynamics -at the edge of tipping points [START_REF] Ferriere | Eco-evolutionary feedbacks, adaptive dynamics and evolutionary rescue theory[END_REF] , it is unclear whether trait changes would either weaken or nullify these signals. On the other hand, changes in traits themselves could be used as proxies for upcoming transitions [START_REF] Clements | Indicators of transitions in biological systems[END_REF] . Early studies on fishing-induced evolutionary changes suggested that variation in maturation schedules of cod could have been used to detect its collapse [START_REF] Olsen | Maturation trends indicative of rapid evolution preceded the collapse of northern cod[END_REF] , or that shifts in the mean age-at-maturation of overfished populations could be indicator of their loss of stability (in terms of population variability) [START_REF] Anderson | Why fishing magnifies fluctuations in fish abundance[END_REF] . Recent work demonstrates how indicators based on both abundance and trait dynamics could complement each other to improve tipping point detection [START_REF] Clements | Indicators of transitions in biological systems[END_REF][START_REF] Spanbauer | Body size distributions signal a regime shift in a lake ecosystem[END_REF] . For instance, measuring changes in mean and variance in body size in combination with resilience indicators based on species abundance improved the warning of collapse in an experimental system with protists populations [START_REF] Clements | Including trait-based early warning signals helps predict population collapse[END_REF] . Theoretical work demonstrates that the promising possibility to use such fitness-related trait changes as indicators will depend on the rate of environmental change, the level of genetic variation, and the strength of plasticity [START_REF] Baruah | When do shifts in trait dynamics precede population declines?[END_REF] . Other work found no strong earlywarnings in populations experiencing rapid environmental change leading them to extinction [START_REF] Osmond | An evolutionary tipping point in a changing environment[END_REF] .

These works suggest that the dynamics of phenotypic changes will most likely be contextdependent. The next step is to test these predictions in more complex models of ecosystemwide tipping points. Future work would need to assess whether changes in response and effect traits could be used as signals of impending transitions. The reported traits in Table 2 map potential traits that could be monitored to provide a proxy for the risk of a transition. Changes in traits like growth forms (density of leaves, length of stems) of macrophytes could be used as Their intersections mark the two alternative stable states (clear and turbid state) and the unstable saddle depending on the value of background turbidity To (Fig. 1a). We hypothesize that the half-saturation h T that affects the strength of nonlinear response of macrophytes to turbidity is defined by a response trait z (e.g. capacity to grow under low light conditionsshading). DIfferent values of z will thus change the response of macrophytes to turbidity by changes in h T (Supplementary Figure 1a). We assumed that trait z follows a beta distribution (closed limits) that we can parameterize in order to define a given mean μ (=0) and variance σ 2 . We further assumed that the half-saturation h T depends on the trait z following

ℎ ! = ℎ !" 𝑒 !"
, where h To is a background value (= 2) and c a factor (=0.5) (Supplementary Figure 1b).

Using this relationship and integrating for different limits of trait z and levels of variance of the Beta distribution, we can calculate the macrophyte equilibrium in the presence of standing phenotypic variation in z as:

𝑀 ! = ℎ ! 𝑧 ! ℎ ! 𝑧 ! + 𝑇 ! 𝑝 𝑧 𝑑𝑧 ! !!
where p(z) is defined by the Beta distribution as explained above within a range of z (= [-2,2]).

We repeat this for a range of turbidity T values (= [0-8]) to estimate the nullcline of

Figure 2 Figure 3

 23 Figure 2

Figure I Box 2 :

 I2 Figure I

  proxies of shading tolerance to indicate loss of resilience in shallow lakes. Alternatively, changes in the defense traits of vegetation to herbivores could be signals of vulnerability to overexploitation in dryland landscapes. Overall, the goal is to understand what pattern of trait changes to expect depending on the type of mechanism and stress involved.

Box 3 :

 3 GlossaryAlternative stable states: contrasting states that a system may converge to under the same external conditions Bistability: the presence of two alternative stable states under the same conditions Catastrophic bifurcation: a substantial change in the qualitative state of a system at a threshold in a parameter or condition Contemporary (or rapid) evolution: evolutionary changes that occurs sufficiently rapid that it can have an impact on ecological dynamics at the same time-scale as other ecological factors Eco-evolutionary dynamics: dynamics in which ecological processes influence evolutionary processes and evolutionary processes influence ecological processes Effect trait: a measurable feature of an organism that underlies an organism's direct effect on an ecosystem functionGenetic drift: changes in allele frequencies due to random sampling during reproductionHysteresis: the lack of reversibility after a catastrophic bifurcation, meaning that when conditions change in the opposite direction the system stays in the alternative state unless it reaches another bifurcation point (different than the one that caused the first shift)Phenotypic plasticity: non-heritable changes in the phenotype of an organismResponse trait: a measurable feature of an organism that underlies an organism's response to environmental change Tipping point: the point where following a perturbation a self-propagated change can eventually cause a system to shift to a qualitatively different state Trait variation: variability of any morphological, physiological, or behavioral feature

Acknowledgements

We thank two anonymous reviewers, Christopher Clements and Gaurav Baruah for their comments. VD and BM are grateful to Eawag and the Adaptation to a Changing Environment Program at ETH Zurich for financing a workshop on eco-evolutionary dynamics of tipping points help in Kastanienbaum in 2016. BM acknowledges a SNF 31003A_175614 grant.

Competing interests

We declare no competing interests.

Author contributions

Trait evolution: genetic change in phenotype of a given trait 460

Supplementary Information -Shallow lake eutrophication model

We used a minimal model that describes the dynamics of transition from a clear water state dominated by macrophytes to a turbid water state where macrophytes are practically absent [START_REF] Scheffer | Alternative equilibria in shallow lakes[END_REF] .

Such transition occurs at a crossing of a fold bifurcation (tipping point) due to changes in nutrient loading (eutrophication). Below we explain how we analysed the model to highlight the presence of alternative states as function of environmental stress (Box 1), and the effects of standing phenotypic variation (Figure 1).

The model describes the interactions between macrophyte coverage and turbidity of a shallow lake with the following two ordinary differential equations: Solving for steady state the nullclines of the system are: macrophytes M for this range of turbidity T, and we find the new equilibria states from the cross sections with the turbidity nullcline (Fig. 1a).

We repeat this procedure to estimate all equilibria as a function of environmental conditions


Vasilis Dakos

Population dynamics: Nature's dynamical complexity

Population dynamics: Nature´s dynamical compexity

Vasilis Dakos ISEM, CNRS, University of Montpellier, EPHE, IRD, 34090 Montpellier, France vasilis.dakos@umontpellier.fr A large-scale, cross-taxa analysis reveals high nonlinearity and limited long-term predictability in the dynamics of animal populations Dynamics of animal populations fluctuate in a variety of ways. They may periodically oscillate, wax and wane irregularly, boom-and-bust, or alternate between periods with different types of fluctuations. All these complex patterns are driven by a combination of biotic and abiotic factors, either stochastic or deterministic [START_REF] Bjørnstad | Noisy clockwork: time series analysis of population fluctuations in animals[END_REF] . As a consequence it is notoriously hard to understand and predict population dynamics. Writing in this issue of Nature Ecology and Evolution, Clark and Luis 2 analyse the temporal dynamics of a large collection of animal populations to demonstrate that, in more than half of the cases, their dynamics are nonlinear and difficult to predict.

Understanding nonlinearity and predictability has always been a fascinating subject for ecologists, especially as it relates to identifying chaotic dynamics in nature [START_REF] Hastings | Chaos in ecology -Is mother nature a strange attractor?[END_REF] . Nonlinearity emerges when interactions among system components are not directly proportional. This could mean threshold or saturating relationships, or multiplicative interactions that combined give rise to complex dynamics. Simple population models [START_REF]Simple mathematical models with very complicated dynamics[END_REF] and lab experiments with insect populations [START_REF] Desharnais | Chaos and population control of insect outbreaks[END_REF] showed how chaotic dynamics could arise due to such nonlinear intrinsic processes like overcompensatory density dependence where population growth is strongly affected by population abundance. Chaotic dynamics are characterised by high sensitivity to initial conditions, which means that even a slight difference at the start of two trajectories will exponentially diverge in time. This implies that chaotic, and in general nonlinear, systems are inherently hard to predict far ahead into the future--just like it is hard to forecast the weather several days in advance.

But just how nonlinear and unpredictable are natural populations? Clark and Luis attempt to answer this question.

To do so, they first collected 747 datasets of population abundance timeseries across 228 different taxa including mammals, bony fish, birds, and insects. Second, they analysed the dynamical complexity of each timeseries using nonlinear forecasting [START_REF] Sugihara | Nonlinear forecasting as a way of distinguishing chaos from measurement error in time series[END_REF] . Nonlinear forecasting is a set of nonparametric time series modelling techniques that is based on Takens' embedology theorem [START_REF] Takens | Detecting strange attractors in turbulence[END_REF] . The idea is that instead of parameterising a specific model, the timeseries is used to build a map by plotting (embedding) the time points of a timeseries in a phase space made up of time delayed coordinates (Fig. 1). Takens' theorem states that the embedded timeseries should produce a geometric object that resembles the characteristics of the "true" system, which in their study is every population and its supposed interactions with all other populations and abiotic factors. Such mapping becomes more reliable if a timeseries is sufficiently long, so Clark and Luis only used records of more than 30 observations to perform the nonlinear forecasting. They then used these embedded maps to estimate how accurately they can forecast population densities taken out-of-sample for each timeseries. In this way, they quantified for each population timeseries three properties [START_REF] Sugihara | Nonlinear forecasting as a way of distinguishing chaos from measurement error in time series[END_REF] : dimensionality, predictability, and nonlinearity.

Their results are revealing. In three out of the four taxonomic classes, they found strong prevalence of nonlinear dynamics. Only bird populations were characterised as the least nonlinear (35% of bird populations), while insects were the most nonlinear group (74% of insect populations). They also found that nonlinearity was negatively correlated with predictability, which means that less predictable populations were probably more affected by stochastic processes. Nonetheless, when they tried to forecast more than a single time step into the future, predictability declined exponentially in all cases.

To a large extent, these results are in line with previous studies that have identified nonlinear dynamics using similar methods [START_REF] Takens | Detecting strange attractors in turbulence[END_REF] , and they seem to confirm our intuition that most systems are in a non-equilibrium state that is hard to predict. But which, when, and how? What can we conclude when looking at these "macro-ecological" patterns to infer what drives nonlinear dynamics? Clark and Luis take a step towards that direction by linking the three elements of dynamic complexity to species lifehistory traits, phylogeny, and trophic level as well as other elements of the observed records.

They found no significant phylogenetic relationships, but they did consistently find a positive relationship between nonlinearity and predictability for animals that had fast life-history traits (reflected by their short body size, early age at first reproduction and short longevity). Although the relationships are rather weak and the authors themselves conclude that "no matter the species or ecosystem studied, the underlying systems may be hard to predict", they do point in the right direction for exploring the possibilities and limitations of building a more predictive ecology [START_REF] Petchey | The ecological forecast horizon, and examples of its uses and determinants[END_REF] .

Most of our understanding in this direction has focused on improving mathematical population models (like the Ricker model), or better fitting statistical parametric models (like autoregressive models 10 ) to map dynamics and understand processes. Nonlinear nonparametric forecasting represents an alternative equation-free approach [START_REF] Ye | Equation-free mechanistic ecosystem forecasting using empirical dynamic modeling[END_REF] . Without relying on specific equations, it can produce predictions simply based on the observed dynamics of the system. Its forecasting skill at times outperforms other approaches [START_REF] Ye | Equation-free mechanistic ecosystem forecasting using empirical dynamic modeling[END_REF] , but it comes at the expense of lacking a mechanistic background. By applying nonlinear forecasting to such a large dataset, Clark and Luis have only scratched the surface to start understanding the extent to which such equation-free approaches could help build better models at least for predicting animal populations. This work does not, of course, solve the old spell of the "equilibrium world" that haunts ecologists in their quest to understand and predict nature, in which ecological systems are assumed to have regular dynamics around a stable steady state. But it does make us think of the potential to test the limits of predictability of our ecological systems as more and better resolved data are becoming available and novel standardised methodologies are being developed. The opportunities of such advancements for conservation management especially under current trends of global change should not be missed.

Fig 1. Estimating dynamical complexity of population trajectories

(a). Hypothetical timeseries of population abundances of three species (x,y,z) belonging to a trophic chain. (b) Plotting in phase-space the ambundances of each species measured at the same point in time (black dot highlighted in purple, A:{x(t), y(t), z(t)}) produces a "map" with a particular structure that is unique signature of the 3-species system. (c) Based on Takens' theorem [START_REF] Takens | Detecting strange attractors in turbulence[END_REF] , using the single timeseries of species x (blue line in panel a) and "embedding" it in phase-space using lagged coordinates (black dot highlighted in red x(t) vs x(t+τ) vs x(t+2τ), where τ is the time delay) reveals another "map" that resembles the ¨true¨ map of the original 3-species system in panel b. Based on such reconstructed maps one can forecast the future evolution of the system state and infer the dimensionality (i.e. the number of dimensions of the embedded phase space), predictability (i.e. the forecasting skill), and nonlinearity (i.e. the weighing of a nonlinear model used for producing the highest forecasting skill) of an ecological system.

  ): {x(t), x(t+tau), x(t+2tau)} A(t): {x(t), y(t), z(t)

Competing Interests:

The author declares no competing interests.


Pierre Peterlongo
email: pierre.peterlongo@univ-mlv.fr

Julien Allali

Marie-France Sagot

The Gapped-Factor Tree

Keywords: suffix tree, k-factor factor tree, string index, gapped-factor, gapped-factor tree

We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The data structure presented is based on the suffix tree and indexes all the gapped-factors of a text with a fixed size of gap, and only those. The construction of this data structure is done online in O(n × |Σ|) time and space, with n the length of the text and |Σ| the size of the alphabet. Such a data structure may play an important role in some pattern matching and motif inference problems, for instance in text filtration.

Introduction

The indexation and extraction of repeated short words (called k-factors 4 for words of length k) has become a widely used technique in many text algorithmic problems. One can mention their use in, for instance, fasta [START_REF] Lipman | Rapid and sensitive protein similarity searches[END_REF] and blast [START_REF] Altschul | Basic local alignment search tool[END_REF][START_REF] Altschul | Lipman: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs[END_REF]. Indeed, many algorithms for efficiently computing string matches [START_REF] Gravano | Srivastava: Approximate string joins in a database (almost) for free[END_REF][START_REF] Navarro | Indexing text with approximate q-grams[END_REF][START_REF] Sutinen | On using q-gram locations in approximate string matching[END_REF] or alignments [START_REF] Brudno | LAGAN and Multi-LAGAN: Efficient tools for large-scale multiple alignment of genomic DNA[END_REF][START_REF] Brudno | Fast and sensitive multiple alignment of large genomic sequences[END_REF][START_REF] Edgar | MUSCLE: Multiple sequence alignment with high accuracy and high throughput[END_REF][START_REF] Höhl | Efficient multiple genome alignment[END_REF][START_REF] Li | PatternHunter II: Highly sensitive and fast homology search[END_REF][START_REF] Ma | PatternHunter: Faster and more sensitive homology search[END_REF][START_REF] Michael | Siteblast rapid and sensitive local alignment of genomic sequences employing motif anchors[END_REF] use k-factors. In particular, filtration algorithms that have been created for quickly discarding large portions of the input before applying a more expensive algorithm on the remaining data are often based on the identification of such short repeated words [6-8, 15, 25, 26, 28].

Among the exact filtration algorithms (exact in the sense that they discard only portions of the text that can not be part of the final solution sought), some consider k-factors composed of non consecutive letters [START_REF] Burkhardt | Better filtering with gapped q-grams[END_REF][START_REF] Burkhardt | One-gapped q-gram filters for Levenshtein distance[END_REF][START_REF] Kucherov | Multiseed lossless filtration[END_REF][START_REF] Pevzner | Multiple filtration and approximate pattern matching[END_REF], or sets of k-factors [START_REF] Burkhardt | q-gram based database searching using a suffix array (QUASAR)[END_REF][START_REF] Peterlongo | Lossless filter for finding long multiple approximate repetitions using a new data structure, the bi-factor array[END_REF][START_REF] Rasmussen | Efficient q-gram filters for finding all εmatches over a given length[END_REF]. Both present advantages for filtering purposes in comparison with single k-factors with no letters skipped as shown in [START_REF] Burkhardt | Better filtering with gapped q-grams[END_REF][START_REF] Kärkkäinen | Computing the threshold for q-gram filters[END_REF][START_REF] Kucherov | Multiseed lossless filtration[END_REF].

In order to efficiently use such k-factors, one needs data structures to index them. Depending on the kind of k-factor adopted, different types of data structures may be considered. For instance, sets of k-factors may be indexed in a hash table or using a labelling technique as proposed in [START_REF] Iliopoulos | A first approach to finding common motifs with gaps[END_REF]. In this paper, we introduce a data structure designed for the indexation of sub-words composed of a k-factor, a gap of length d not taken into account during the indexation and a k ′ -factor. Such a sub-word is called a gapped-factor as it contains a unique gap.

The new data structure is an adaptation of the suffix tree [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF]. More precisely, the construction we describe in this paper is an adaptation of the construction of a k-factor tree [START_REF] Allali | The at most k-deep factor tree[END_REF], which itself is an extension of the Ukkonen construction of a suffix tree [START_REF] Ukkonen | On-line construction of suffix-trees[END_REF]. A k-factor tree is a tree indexing all k-factors of a text.

As indicated in Section 5, the new data structure, called a gapped-factor tree, allows to extract in linear time all the repeated gapped-factors of a text or of a set of texts. Furthermore, it offers the possibility to obtain in time O(k + k ′ ) the list of all the positions of a gapped-factor.

The paper is organised as follows. In Section 2, we provide the context and some definitions about text and trees. In Section 3, we formally introduce gapped-factors and the gapped-factor tree. In Section 4, we present the algorithm to construct a gapped-factor tree for indexing the gapped-factors of a text after recalling the Ukkonen construction of a suffix tree and the Allali construction of a k-factor tree. We end by indicating two basic uses of gapped-factor trees.

Preliminaries

A text, also called a string, is a sequence of zero or more symbols from an alphabet Σ.

A text t of length n is denoted by t[0, n-1] = t 0 t 1 . . . t n-1 , where t i ∈ Σ for 0 ≤ i < n.
The length of t is denoted by |t|. A string w is a factor of t if t = uwv for u, v ∈ Σ * ; in this case, the string w occurs at position |u| in the string t. A k-factor denotes a factor of length k.

If t = uv for u, v ∈ Σ * then v is called a suffix of t. A suffix starting at position i in t is denoted by t i... .
A tree is a data structure composed of nodes connected together by edges. Except for a special node called the root, each node has exactly one father. Nodes with no children are called the leaves while all other nodes are called the internal nodes of the tree. An internal node having at least two children is called a branching node.

We call the depth of a node N the sum of the lengths of the edges that need to be traversed from the root of the tree to reach N . By definition, the depth of the root is thus 0.

Nodes and edges may be labelled. For instance, in Figure 1, edges are labelled with letters from a given alphabet. Let N be a node of a tree, we denote by path(N ) the text corresponding to the concatenation of the letters from a given alphabet labelling the edges from the root to N .

For instance, if N 0 denotes the leftmost leaf of the tree presented in Figure 1, path(N 0 ) = AA.

The suffix trie of a text t is a tree with edges labelled with elements of Σ. For each factor of t, there exists a node N such that path(N ) is equal to that factor. If t has an ending symbol, all nodes N for which the path from the root spells a suffix of t are leaves.

The implicit suffix tree of t is a tree with edges labelled by non-empty elements of Σ * . The suffix tree is a compressed version of the suffix trie. Each internal node N of the suffix trie that has only one child is deleted and its two adjacent edges are replaced by an edge that goes from the father of N to its child. The label of the new edge is equal to the concatenation of the label of the edge going from the father of N to N and of the label of the edge from N to its child. This tree is called implicit because not all suffixes of t lead to a leaf. The true suffix tree is obtained when a special ending symbol $ not in Σ is added at the end of t. A suffix tree indexes all the |t| suffixes of a text t.

Gapped-factor tree

A gapped-factor tree indexes gapped-factors that are defined as follows:

Definition 1 (Gapped-factor). A gapped-factor is a concatenation of a factor of length k, a gap of length d and another factor of length k ′ . A gapped-factor occurring at position i in a text

t is t[i, i+k -1].t[i+k +d, i+k +d+k ′ -1]. Such a gapped-factor is called a (k-d-k ′ )-gapped-factor.
An example of a (2-1-3)-gapped-factor is given in Figure 2. We propose a new data structure, called a gapped-factor tree, to index all the (kd-k ′ )-gapped-factors of a text or of a set of texts. This is a modification of the suffix tree [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF] data structure. The gapped-factor tree takes into account the gap of length d of the gapped-factors it indexes. This means that the tree contains a region up to which the k-factors are indexed as in a classical suffix tree, while below this region the second factors (of length k ′ ) of the (k-d-k ′ )-gapped-factors starting with the same k-factor start from the same node. This region is called the invisible region.

An intuitive idea of such a data structure is given in Figure 3.

00000000000000000 00000000000000000 00000000000000000 00000000000000000 11111111111111111 11111111111111111 11111111111111111 11111111111111111 0000000000000 1111111111111 0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 A T A C A C A A A C C A A C A d k k' A C A C A A C A C A k k' Figure 3
. An intuitive view of a gapped-factor tree. Even if this is not the way the gappedfactor tree is constructed, a gapped-factor tree can be seen as a truncated suffix tree where a part has been removed, provoking merges in the lower part of the tree.

Definition 2 (Path in a Gapped-Factor Tree). Let w be a

(k-d-k ′ )-gapped-factor starting at position i < |t| -k -d -k ′ that is indexed in such a tree. Let N be the node at depth z ≤ k + k ′ corresponding to this (k-d-k ′ )-gapped-factor. Then: path(N ) = t[i, i + z -1] if z ≤ k t[i, i + k -1].t[i + k + d, i + d + z -1] otherwise
An example of gapped-factor tree and of a path in such a tree is presented in Figure 4. In the next section, we present the algorithm which performs the online construction of a gapped-suffix tree.

A A G A C G G A A A G A A A A A C G A A C G C A G G A
The algorithm for constructing a gapped-factor tree is an extension of the algorithm for constructing a k-factor tree [START_REF] Allali | The at most k-deep factor tree[END_REF], which is itself an extension of the suffix tree construction algorithm due to Ukkonen [START_REF] Ukkonen | On-line construction of suffix-trees[END_REF]. Therefore, in the following, we start by presenting the construction of a suffix tree, then the one of a k-factor tree, and finally we describe the construction of a gapped-factor tree.

Ukkonen construction of the suffix tree

To present the Ukkonen algorithm, we follow the description given in [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences[END_REF]. This algorithm constructs a full suffix tree of a text t in O(|t|) time and space. An example of a suffix tree is given in the Figure 5. The algorithm is divided into |t| phases. The i th phase (for 0 ≤ i < |t|) consists in the insertion of all the i + 1 suffixes of t[0, i] into the tree. The naive approach divides each phase i into i + 1 steps, one step j (0 ≤ j < i) consisting in the insertion of the suffix t[j, i] into the tree. This naive version of the construction algorithm is presented in Algorithm 9. Clearly this algorithm is in O(|t| 3 ).

A $ G G A $ G $ A G $ $ G A G $ G A G G A G

Algorithm 9 Naive suffix tree construction algorithm

Require: A text t Ensure: The suffix tree ST (t) of t 1: for i from 0 to |t| -1 do 2: for j from 0 to i do 3: Add(ST (t),t[j, i]) 4: end for 5: end for The Ukkonen algorithm uses three tricks in order to reduce the time complexity to O(|t|).

Before we present those three tricks, we describe the encoding of a suffix tree. The suffix tree created by this algorithm does not store the text: each node N contains a couple of integers (s, e) corresponding to the starting and ending positions of the factor in the text that led to the creation of the node itself. In the following, we denote by N s,e such a node. Thus, by definition, in the suffix tree of a text t, path(N s,e ) is equal to t[s, e].

The Ukkonen algorithm uses suffix links. A suffix link is an oriented link between two branching nodes of a suffix tree. Given a node N s,e , its suffix link is denoted by S l (N s,e ) and the node pointed by S l (N s,e ) is denoted by S n (N s,e ). In this case, path (S n (N s,e )) = path(N s,e ) 1, |path(N s,e )| . For instance, if path(N s,e ) = AGGT , then, path(S n (N s,e )) = GGT .

In Figure 5, the suffix links are represented by dashed lines. We present the three ideas leading to a linear time complexity for constructing a suffix tree for the text t.

1. Let us assume that the suffix tree is constructed for t[0, i-1]. During the i th phase, all the leaves have to be lengthened by one in order to take the character t i into account. In other terms, the ending integer e of each leaf has to be incremented by one. Since by definition, all leaves have the same ending integer, the latter can be coded by a global variable that is incremented by one at each phase of the Ukkonen algorithm. This global variable is equal to i during phase i. Thus, the extension of the leaves is implicit and done in constant time. 2. (a) Fast Insertion: during the i th phase, let N s,e be the last branching node reached during the insertion of t[j, i]. By construction this node contains a suffix link. In this case, t[j, i] = path(N s,e ).w.σ where w ∈ Σ * and σ ∈ Σ. In order to insert t[j + 1, i], w (which is necessarily already in the tree) is read from S n (N s,e ) and σ is added if needed.

To avoid having to read all the letters of w from S n (N s,e ), the following trick is used. At each branching node met during the reading of w, an edge is chosen depending on the current letter in w. Once the edge is identified, the node pointed by this edge is reached and we advance in the reading of w by the number of letters in the edge. The process is repeated while w is not totally read. Thus the complexity of the reading of w is related to the number of nodes traversed and not to |w|. If σ is added, a branching node is created. The suffix link of such a node points to the last branching node met during the next insertion (it can be a created one).

The pseudo-code of this algorithm is given in appendix in Figure 10. (b) During phase i, all the suffixes of t[0, i] have to be inserted. Yet if during the insertion of t[j, i], this word is already in the tree, then, by definition, all the words {t[k, i], k ∈ [j, i]} are already in the tree as well. In this case, the i th phase stops here. Similarly, the (i + 1) th phase can start inserting t[j, i + 1]: with the implicit extension of the leaves, the factors {t[k, i + 1], k ∈ [1, j -1]} are already in the tree.

A pseudo-code of this construction algorithm is given in appendix in Algorithm A. Each phase of the algorithm is not done in constant time. However the amortised construction time is linear with respect to the input text length. The demonstration of this complexity is given in [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences[END_REF]. It consists in bounding the overall number of nodes traversed during all insertions.

Construction algorithm of a k-factor tree

The k-factor tree, also called truncated suffix tree, has been presented in [START_REF] Na | Truncated suffix trees and their application to data compression[END_REF] and [START_REF] Allali | The at most k-deep factor tree[END_REF]. A k-factor tree is a suffix tree cut such that each word spelt from the root to a leaf has a length bounded by k. An example of k-factor tree is given in Figure 6. This structure finds applications in various areas such as data compression [START_REF] Na | Truncated suffix trees and their application to data compression[END_REF][START_REF] Na | Data compression with truncated suffix trees[END_REF] where the indexation is made over a sliding window, or string matching and computational biology [START_REF] Marsan | Extracting structured motifs using a suffix tree -algorithms and application to promoter consensus identification[END_REF][START_REF] Pisanti | RISOTTO: Fast extraction of motifs with mismatches[END_REF][START_REF] Thébault | Combining constraint processing and pattern matching to describe and locate structured motifs in genomic sequences[END_REF] where the length of the motifs searched for in the text is bounded.

The linear time construction algorithm we describe here is based on the Ukkonen suffix tree construction algorithm. For further details on implementation and proof of validity, the reader is referred to [START_REF] Allali | The at most k-deep factor tree[END_REF].

This algorithm is divided in two parts:

1. Build the suffix tree for t[0, k

-2]. 2. Add in |t| -k + 1 phases the suffixes of t[i -k, i] for i from k -1 to |t| -1.
The first part is achieved using the Ukkonen algorithm. During this part, the leaves created are added to a queue called queue ℓeaf .

In the second part, we have to modify the Ukkonen algorithm so that:

for each phase i, we start by inserting t[j, i] with j not smaller than ik + 1; -implicit leaf extensions are stopped when the length k is reached for the path of a leaf.

To do this last point, we use the queue queue ℓeaf .

During the whole construction, each leaf created is added at the end of queue ℓeaf . In the second part, for each phase i, there are two possibilities: either queue ℓeaf is empty or not.

Suppose queue ℓeaf contains at least one leaf. Let L s,e denote a leaf starting position s and ending position e. We then have queue ℓeaf = L 1 s 1 ,e . . . L p s p ,e . We start by fixing the end position of L 1 s 1 ,e to i, that is L 1 s 1 ,e becomes L 1 s 1 ,i . Indeed, we know that path(L 1 s 1 ,i ) has a length of k. Suppose we are in phase i = k -1. Then queue ℓeaf contains at least one leaf which corresponds to the one created during the insertion of t[0] in the tree (first insertion of the first phase). This leaf is L 1 0,e . In phase i = k, the leaf is now L 1 0,k-1 , so its length is equal to k. If there is another leaf in the queue, it corresponds to L 1 1,e and it is clear that its length will be equal to k at the next phase. And so on, as the leaves L s,e are created with s incremented by one between two leaves.

Once the leaf at the beginning of queue ℓeaf is fixed, we apply again the Ukkonen algorithm from the last leaf in queue ℓeaf (the last created which can be the one we have just fixed). At the end of phase (i.e. no leaf created during the last insertion), we remove the leaf at the head of queue ℓeaf .

We describe now the case when there is no leaf in the queue. Suppose there were a leaf in the queue at the previous phase i -1. By fixing the end value of this leaf, we have fixed the leaf corresponding to t[ik, i -1]. Then we started by inserting t[ik + 1, i -1] in the tree. This insertion did not create a leaf (queue ℓeaf is empty in phase i) and lead to a position p in the tree that corresponds to the spelling of t[ik + 1, i -1]. In the current phase i, since queue ℓeaf is empty, we have to start by inserting t[ik + 1, i] in the tree. This can be done in constant time by trying to insert t[i] from the position p. If this insertion creates a leaf, its end value is directly set to i (not added in queue ℓeaf ) and it is used to try to insert t[ik + 1, i]. If no leaf is created, then we continue by trying to insert t[ik + 1, i] from the leaf reached (we know that the insertion of t[ik, i] leads to a leaf since the path length of the leaves is bounded by k). If the insertion of t[ik + 1, i] does not create a leaf, we use the position reached in the tree to start the next phase.

A pseudo-code of this algorithm is given in appendix in Algorithm A.

The time and space complexities of the algorithm are linear in the size of the input text (see [START_REF] Allali | The at most k-deep factor tree[END_REF] for details).

A G G A G A $ G G A $ G A $ G G k=3 Figure 6
. Example of a k-factor tree for the text AGGAG$ with k = 3

Gapped-factor tree construction

We now present the construction algorithm of a gapped-factor tree (gft for short).

Once again, the construction algorithm is done online. As shown in Figure 4, a gft is composed of three different regions: the upper part of depth k, the invisible region corresponding to the gap of length d, and the lower part of depth k ′ :

1. During the construction of the gft, the first region is treated exactly as for a kfactor tree. The queue containing the leaves in extension is denoted by queue leaf up . 2. When a leaf reaches the depth k, it enters in the invisible region for d phases. To simulate this behaviour, a queue is created that contains the leaves in extension in the invisible region. This queue is denoted by queue invisible . Leaves entering queue invisible stay inside for d phases. During those phases, leaves inside the queue are ignored. After d phases, a leaf in the queue is virtually reaching the depth k + d. It is then removed from the queue. 3. The construction algorithm of the lower part of the tree is again very similar to the one of a k-factor tree. All the tricks applied for the suffix tree construction are still available. Once more a queue is used to store the leaves in extension in the lower part of the tree. This queue is denoted by queue leaf low . The ending integer of the leaves in extension in the queue is the global variable i. The leaves stay in the queue during k ′ phases before they become leaves that stay fixed, and contain the positions of the gapped-factors corresponding to the path leading to them from the root. However, for the construction of the lower part, the use made of suffix links is slightly different than in the upper part of the tree. This is due to the following particularity of the gapped-factor tree: a node in the lower part of the tree may have up to |Σ| suffix links. Indeed, one node in this tree may correspond to several paths. According to the first letter in the invisible region leading to a node, the suffix link to follow will not be the same. Figure 7 illustrates this observation.

The algorithm 15 given in appendix gives an overview of the whole gapped-factor tree construction algorithm. The node pointed by an arrow has two suffix links (in dotted line). One is labelled with an A and the other is labelled with a B. The correct suffix link to follow depends on the path that leads to the node. If the node is reached reading ABA.w (w ∈ Σ * ), the correct suffix link to follow is the one labelled with an A; it goes to a node reachable reading the text BA.w. Any other suffix link leaving the node would be labelled differently and would reach a node corresponding to the text B.σ.w, with σ ∈ Σ and σ = A.

Complexity of the Gft construction

The algorithm for constructing a gft uses all the tricks employed by Ukkonen and Allali to lead to a linear time and memory complexity. However, the multiple suffix links add a multiplicative term in |Σ| to both complexities. Thus the total time and memory complexity for the construction of a gapped-factor tree for a text t is in O(|t| × |Σ|). One can notice that once the gapped-factor is constructed, the (multiple) suffix links are not useful anymore and can be removed. In this case, the memory complexity falls back to O(|t|).

Generalisation to more than one text As for the suffix tree or the k-factor tree, the gft can be extended to a generalised gapped-factor tree and accept a set of m > 1 texts t 0 , t 1 , . . . , t m-1 .

In this case, each text i ∈ [0, m -1] ends with a special character $ i and the leaves are labelled not only with the positions of a gapped-factor but also with the sequence number in [0, m-1] where the factors occur. The complexity for constructing a generalised gapped-factor tree is in

O m-1 i=0 |t i | × |Σ| .

Basic uses of a gapped-factor tree

To find all the positions where a (k-d-k ′ )-gapped-factor occurs in a text given a (k-d-k ′ )-gapped-factor tree for the text one needs to find the leaf corresponding to the given gapped-factor. This is done straightforwardly by traversing the gappedfactor tree from the root to the node as in a suffix tree. The list attached to the leaf corresponds to the positions of the occurrences of the gapped-factors. This algorithm takes a time proportional to the number of nodes traversed, which is in the worst case k + k ′ . Thus retrieving the positions of a given (k-d-k ′ )-gappedfactor is done in O(k + k ′ ).

The gft data structure allows also to easily find all the repeated gapped-factors of a text or of a set of texts. If we are interested in finding all gapped-factors occurring at least r times in a text, for r a positive integer, we just have to visit the leaves. For each leaf, if the number of elements of the list attached to it is greater or equal to r, the corresponding gapped-factor is considered as repeated.

As the number of elements of each list may be stored in the leaves, this extraction is done in time proportional to the number of leaves. If n denotes the length of the indexed text, the number of leaves is no greater than n. The extraction is therefore done in time O(n).

In the generalised case, one may want to extract all gapped-factors occurring in at least r different texts. In this case, to each leaf is attached the number of different texts in which the corresponding gapped-factor occurs. Thus extracting all gappedfactors occurring in at least r different texts is done by checking each leaf in constant time leading to a complexity in O(

m i=1 |t i |).

Conclusion

We presented a new data structure used for indexing factors containing a gap (called the gapped-factors). This data structure is based on the suffix tree structure. Furthermore, we indicated an online construction algorithm of this data structure for a text t on an alphabet Σ in O(|t| × |Σ|) time and space. This algorithm is based on the Ukkonen algorithm for constructing a suffix tree. remove the leaf at the head of queue leaf and set its end value to i 16: end for 17: return R Algorithm 12 Function Phase (Suffix tree and k-factor tree construction) Require: R, t, k, i, queue leaf , lastLeaf Ensure: One phase of the construction of the suffix tree and of the k-factor tree. The underlined parts stand only for the k-factor tree construction. 1: endP hase ← f alse 2: repeat 3: f orward ← length(F ather(lastLeaf ), lastLeaf ) -1 4: if S l (F ather(lastLeaf )) is undefined and F ather(lastLeaf )! = R then 5:

A Pseudo-codes

f orward ← f orward + length(F ather(F ather(lastLeaf )), F ather(lastLeaf )) 6:

if F ather(F ather(lastLeaf )) is R then 7:

AddString(R,t,if orward + 1,i) 8: else 9:

AddString(S l (F ather(F ather(lastLeaf ))),t,if orward,i)

Figure 1 .

 1 Figure1. Example of a tree labelled with letters from a given alphabet. Reading all paths from the root to the leaves, leads to the strings AA, AC, CA and CT .

Figure 2 .

 2 Figure 2. Example of a (2-1-3)-gapped-factor. The first factor length is k = 2, the gap is of length d = 1 and the second factor has a length k ′ = 3. It occurs at position 1 in the text. With these parameters, the content of the gapped-factor occurring at position 1 is GGGAG composed by GG and GAG.

Figure 4 .

 4 Figure 4. Example of gapped-factor tree. The input sequence is AGGAGAGACAA. The dashed lines correspond to the invisible region of the tree. In this case, the gapped factors indexed are (2-1-3)-gapped-factors. The information attached to one of the leaves corresponds to the starting positions of a gapped-factor in the text.

Figure 5 .

 5 Figure 5. Example of a suffix tree for the text AGGAG$. The dashed lines represent the suffix links.

Figure 7 .

 7 Figure 7. Example of multiple suffix links. The node pointed by an arrow has two suffix links (in dotted line). One is labelled with an A and the other is labelled with a B. The correct suffix link to follow depends on the path that leads to the node. If the node is reached reading ABA.w (w ∈ Σ * ), the correct suffix link to follow is the one labelled with an A; it goes to a node reachable reading the text BA.w. Any other suffix link leaving the node would be labelled differently and would reach a node corresponding to the text B.σ.w, with σ ∈ Σ and σ = A.

  Algorithm 10 Fast InsertionRequire: N ,t,start,end Ensure: Insert a string t start...end from a node N assuming that the tree is already constructed for t start...end-1 from N 1: endJump ← f alse 2: while (not endJump) and ((endstart) = 0) do 3: set child to the child of N that starts with the lettert start 4: if (endstart) ≥ length(N , child) then if (endstart) = 0and N has not a child for letter t end then 12: add a child to N with edge label start equal to end 13: end if 14: e ←the label of the edge between N and child 15: if e end-start+1 = s end then 16: split e at position endstart 17: add a leaf with start position equal to end to the new node 18: end if Algorithm 11 Factor Tree Require: R, t , k , queue leaf Ensure: The k-factor tree of t 1: do the first k -1 phases using Suffix Tree algorithm, filling queue leaf with each new leaf created 2: for i from k to |t| do 3: if queue leaf is not empty then 4: set lastLeaf to the leaf at the end of queue leaf Phase (R, t , k, i, queue leaf , lastLeaf ) 15:

	5:	start ← start + length(N , child)
	6:	N ← child
	7: else
	8:	endJump ← true
	9: end if
	10: end while
	11: 5: else
	6:	add t i from last position reached during the last insertion
	7:	if a leaf is created then
	8:	add this leaf at the end of queue leaf
	9:	set lastLeaf to this leaf
	10:	else
	11:	set lastLeaf to the leaf reached
	12:	end if
	13:	end if
	14:

  Ensure: The suffix tree of t 1: Add to R a leaf L with edge label t 0 2: lastLeaf ← L 3: for i from 1 to |t| -1 do 4: Phase (R, t , k, i, lastLeaf ) 5: end for 6: return R

	10:	end if
	11:	else
	12:	if F ather(lastLeaf ) is R then
	13:	AddString(R,t,i -f orward + 1,i)
	14:	else
	15:	AddString(S l (F ather(lastLeaf )),t,i -f orward,i)
	16:	end if
	17:	end if
	18:	if a node was created during the previous step then
	19:	set the suffix link of this node to the last node reached during the insertion
	20:	end if
	21:	if a leaf was created in the call to AddString then
	22:	set lastLeaf to this leaf
	23:	add this leaf at the end of queue leaf
	24:	end if
	25:	if no node was created during the call to AddString then
	26:	endP hase ← true
	27:	end if
	28: until not endP hase
	Algorithm 13 Suffix Tree
	Require: t

Proceedings of the Prague Stringology Conference '06

⋆ Supported by the ACI Nouvelles Interfaces des Mathématiques π-vert project of the French Ministry of Research, the ARC BIN project from the INRIA, and the ANR project REGLIS. 4 for designing k-factors is q-grams