Julien Mirval
email: julien.mirval@cozycloud.cc

Cozy Cloud

Iulian Sandu-Popa
email: iulian.sandu-popa@uvsq.fr

Practical Fully-Decentralized Secure Aggregation for Personal Data Management Systems

Keywords: Computer systems organization → Architectures;, Information systems → Data management systems Privacy, secure aggregation, decentralized, machine learning

Personal Data Management Systems (PDMS) are flourishing, boosted by legal and technical means like smart disclosure, data portability and data altruism. A PDMS allows its owner to easily collect, store and manage data, directly generated by her devices, or resulting from her interactions with companies or administrations. PDMSs unlock innovative usages by crossing multiple data sources from one or many users, thus requiring aggregation primitives. Indeed, aggregation primitives are essential to compute statistics on user data, but are also a fundamental building block for machine learning algorithms. This paper proposes a protocol allowing for secure aggregation in a massively distributed PDMS environment, which adapts to selective participation and PDMSs characteristics, and is reliable with respect to failures, with no compromise on accuracy. Preliminary experiments show the effectiveness of our protocol which can adapt to several contexts with varying PDMSs characteristics in terms of communication speed or CPU resources and can adjust the aggregation strategy to the estimated selective participation.

INTRODUCTION

The new privacy-protection regulations (e.g., GDPR) and smart disclosure initiatives in the last decade have boosted the development and adoption of Personal Data Management Systems (PDMSs) [START_REF] Anciaux | Personal data management systems: The security and functionality standpoint[END_REF]. A PDMS (e.g., Cozy Cloud, Nextcloud, Solid) is a data platform Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

allowing users to easily collect, store and manage into a single place data directly generated by user devices (e.g., quantified-self data, smart home data, photos) and data resulting from user interactions (e.g., social interaction data, health, bank, telecom). Users can then leverage the power of their PDMS to benefit from their personal data for their own good and in the interest of the community [START_REF]Proposal for a Regulation on European data governance (Data Governance Act)[END_REF].

Consequently, the PDMS paradigm leads to an important shift in the personal data ecosystem since data becomes massively distributed, at the user-side. It also holds the promise of unlocking innovative usages. An individual can now cross her data from different data silos, e.g., health records and physical activity data. Moreover, individuals can cross data within large communities of users, e.g., to compute statistics for epidemiological studies or to train a machine learning model (ML) for recommender systems or automatic classification of user data. However, these exciting perspectives should not eclipse the security issues -user data must be kept private-and the right for any PDMS user to consent, or not, in participating in each computation.

Aggregation primitives (e.g., sum or average) are obviously essential to compute basic statistics on user data but are also a fundamental building block for machine learning algorithms. Thus, to enable such new usages, we need scalable, privacy-preserving protocols implementing data aggregation primitives with selective (i.e., consenting) participants. Ideally, the proposed protocol should provide an accurate result that fully takes advantage of high-quality data available in PDMSs. Efficiency (i.e., protocol latency and total load of the system) is of prime importance and the protocol should adapt to several contexts: the PDMSs could be limited by their communication speed or by their computation power. Finally, given the scale of such decentralized aggregation, such protocols must also be robust to node failures. To summarize, our goal is to propose an aggregation protocol for basic aggregate functions that fulfills the following properties:

• fully decentralized and highly scalable, with the number of participants.

• privacy-preserving, i.e., it protects the confidentiality of user data.

• accurate, i.e., it does not require a trade-off between accuracy and privacy.

• adaptable, i.e, it can adapt to a large spectrum of computation selectivity values (reflecting the subset of contributor nodes) and system configurations (network and cryptographic latency).

• reliable, i.e., it handles node failures or voluntary disconnections.

The rest of this paper is organized as following. After discussing the related works w.r.t. the required properties in Section 2, we introduce the considered architecture and threat model in Section 3. Sections 4 and 5 focus on the proposed protocol and preliminary results. Section 6 concludes with future issues.

RELATED WORKS

Secure aggregation is an intense research area since many years and many approaches were proposed: secure multi-party computation (SMC) and (fully) homomorphic threshold encryption (HTE), (local) differential privacy and gossip-based protocols. However, the existing solutions are not adapted to the PDMS context and fail to cover all the required properties listed above.

HTE and SMC-based solutions [START_REF] Aono | Privacypreserving deep learning via additively homomorphic encryption[END_REF][START_REF] Bonawitz | Practical secure aggregation for privacy-preserving machine learning[END_REF][START_REF] Corrigan | Prio: Private, robust, and scalable computation of aggregate statistics[END_REF][START_REF] Froelicher | Drynx: Decentralized, secure, verifiable system for statistical queries and machine learning on distributed datasets[END_REF] generally target applications in which central servers orchestrate and coordinate the participating nodes (e.g. federated learning). Such solutions are not scalable with a large number of participants and a fully decentralized setting such as in the PDMS context (e.g., the server(s) load is linear [START_REF] Corrigan | Prio: Private, robust, and scalable computation of aggregate statistics[END_REF] or quadratic [START_REF] Bonawitz | Practical secure aggregation for privacy-preserving machine learning[END_REF] with the number of participants).

Local differential privacy (LDP) has gained significant momentum in the recent years addressing problems such as machine learning [START_REF] Zheng | Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible[END_REF] or basic statistics based on range queries [START_REF] Cormode | Answering Range Queries Under Local Differential Privacy[END_REF]. However, LDP requires more noise than classical DP [START_REF] Mário | Local Differential Privacy on Metric Spaces: Optimizing the Trade-Off with Utility[END_REF], either affecting accuracy or requiring a large number of participants to reduce the impact of noise, contradicting adaptability to selective participation.

Gossip-based protocols are scalable, fully decentralized, reliable and have an adjustable accuracy. Unfortunately, classical gossipbased protocols do not protect the user privacy. In [START_REF] Bellet | Personalized and private peer-to-peer machine learning[END_REF], participants collectively learn a machine learning model in a privacy preserving way by gossiping differentially private models, impacting accuracy. In [START_REF] Mo | Privacy preserving average consensus[END_REF], participants introduce noise in the first iterations and gradually remove it in subsequent iterations. This approach makes such solutions unreliable w.r.t. node failures. Finally, we are not aware of gossip protocols tolerating selective participation and trivial adaptations produce inaccurate results.

SYSTEM OVERVIEW AND THREAT MODEL

In this section, we introduce first the system architecture and the related concepts. We then present the considered threat model for the proposed secure protocol.

System Architecture

P2P network. We envision a fully distributed Peer-to-Peer (P2P) system relying only on PDMSs, thus requiring an efficient communication overlay. Distributed Hash Tables (DHT) are structured overlays which enable a logarithmic scalability with the number of nodes. Our protocol is currently built on top of the Chord DHT [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]. Each node has an Id obtained by hashing a static property of the node and stores a fingertable (FT) to route Chord messages. FT is a table with a number of entries equal to the size of the Id space in bits. If X is a node Id, the i t h entry of the FT contains the IP address of the node whose Id is closest but lower than X + 2 i . Routing is done by searching in the FT the closest entry to the target address and transmitting recursively the message until it reaches its target, with a worse case of O(loд(N )) message complexity, where N is the number of DHT nodes.

Computation model. An aggregate computation can be triggered by any node, called querier. The querier broadcasts the computation and each node consents or not to contribute, and in the positive case is called contributor. The ratio between the number of contributors and total number of nodes defines the selectivity σ , 0 < σ ≤ 1. Finally, each node (contributor or not) is a potential data processor and is then called aggregator.

Threat Model

We consider the honest-but-curious threat model, in which, an attacker can access, without altering, the data manipulated by the attacked nodes, then called leaking nodes. The rationale behind the honest-but-curious model is that a PDMS can hold the entire digital life of her owner and therefore needs to be highly protected against privacy threats. Recent works [START_REF] Anciaux | Personal Database Security and Trusted Execution Environments: A Tutorial at the Crossroads[END_REF] indicate that Trusted Execution Environments (TEEs) are prime candidates to offer this protection since they guarantee that executed code and manipulated data cannot be observed. In our context, this property allows sharing data between PDMS nodes without breaking data confidentiality.

We thus consider that each PDMS is protected by a secure hardware solution, such as Intel SGX or ARM TrustZone, providing a TEE. Such a hardware protection makes attacks difficult to produce, but since no security measure is unbreakable, we consider that some PDMS owners have succeeded in tampering their PDMS. Since attackers may collude and thus, de facto, control more than one PDMS, the worst-case attack is represented by the maximum number of colluding nodes controlled by a single "attacker", i.e., C leaking nodes.

Additionally, the TEE of each PDMS is equipped with a trustworthy certificate. Thus, any node can verify the authenticity of other participants by checking their certificate. This prevents Sybil attacks (i.e., forging nodes to master a large portion of the system).

Finally, attackers can also observe the communications between the nodes, thus requiring secure communication channels (e.g., TLS) to protect sensitive data exchanges.

Our objective is to provide a protocol that fully protects the confidentiality of the contributors' data and all the intermediary results, with high and tunable probability, the final result not being confidential. Also, we consider that being a contributor for a given computation is not a sensitive information.

PROPOSED PROTOCOL

In the protocol overview, we analyze the properties listed in Section 1 and present the main ideas and techniques behind each property and its impact on the protocol. Due to space constraints, we cannot describe in detail the proposed protocol and thus discuss some identified key elements of the protocol under the form of questions/answers, considering first the privacy aspects and then the efficiency perspective.

Protocol Overview

Scalability: The DHT achieves de facto a fully decentralized and efficient architecture for inter-nodes communication. Achieving a scalable aggregation process requires multiple aggregators, arranged in a tree structure. Building and broadcasting this aggregation tree can be very costly since the tree itself can be large. We thus employ a divide-and-conquer approach to parallelize the tree construction and diffusion and use the finger table structure to minimize communications. Finally, we reduce the knowledge (and thus the diffusion) of the tree to the minimal part strictly necessary to perform the aggregation: basically, each node of the tree only knows its parent(s) and its children.

Privacy and accuracy: We use a secret sharing scheme (without threshold) in which each contributor splits its data into s shares, making them unreadable unless someone collects all s shares. s is computed such that the probability to obtain s shares for an attacker, controlling C nodes, is inferior to a security threshold α (e.g., α = 10 -6 ). Each i t h share has the value x i = x + ϵ i such that n i=1 ϵ i = 0, where x is the private value. This way, shares from different contributors can be aggregated separately and if no share is missing (the reliability is discussed below), the final result will be equal to the exact sum of all private data. Hence, our protocol provides also, by construction, accurate results. Note that the protocol works for complex values of x, such as an array or a matrix, which is useful for advanced aggregations, e.g., training a naive Bayes ML model.

Adaptability: The number of aggregators (i.e., the tree fan-out and its height) is tuned as a function of the number of contributors, the communication costs (i.e., the latency to send a message between two nodes) and the processing costs (i.e., the asymmetric cryptographic costs to secure a communication or to sign or verify a signature, which is, by far, the most important processing costs). This allows the protocol to always offer near-optimal performance (i.e., aggregation latency) and achieve adaptability w.r.t. the computation selectivity and PDMSs characteristics. Furthermore, our protocol can also be conveniently configured to offer the desired trade-off between the latency and the total cost of the aggregation, which are conflicting optimization objectives as discussed in Section 5.

Reliability: Handling failures and disconnections is mainly implemented at two levels. First, the aggregators in the last level of the tree (just above the leaves) execute a synchronization protocol to make sure that contributors have sent all the s shares before disconnection and remove the shares for the contributors that have sent less than s shares. This ensures that the aggregation result stays accurate despite contributors failure. Second, a list of backup aggregators is created before the tree creation. Its size depends on the observed node failure/disconnection ratio. In case an aggregator fails, it is automatically replaced with a backup node during the aggregation process (the parents monitor their children). This allows the protocol to be robust to node failures and avoids losing aggregation subtree results.

Privacy Issues

What is the impact of the secret sharing on the aggregation tree? Considering s shares for each contributor and partial results leads to build s separate aggregation trees, with exactly the same structure, to avoid inferences from an attacker on any of the intermediate results. The final sum of the shares is done by the querier (tree root). A simple means to construct such trees is to consider that each node of the tree is a group of s nodes (see Figure 1 with s = 2). The protocol to build the tree is described in Section 4.3 considering that, at each step, s nodes are selected instead of one. To make this selection efficient, each node in the DHT maintains a cache with the addresses of the s -1 successor nodes that will form the aggregator group.

How is the number of shares computed? An attacker could cleverly locate her controlled nodes in the DHT to obtain the s shares of a group (typically controlling a node and its s -1 successors). We avoid this attack by reusing the concept of imposed location that we proposed in [START_REF] Loudet | SEP2P: Secure and Efficient P2P Personal Data Processing[END_REF]: the node Id in the DHT is computed by hashing the public key from the PDMS certificate (see Section 3.2). The nodes are then uniformly distributed in the DHT space and the PDMS owner (here the attacker) cannot influence this placement: the uniform distribution also applies to leaking nodes. As a consequence, s can be easily computed and is minimal when s = ⌈log(α)/log(C/N )⌉.

Do contributors/aggregators have to check the correctness of the received query?

Basically, the answer is yes. Indeed, a trivial attack would be to impersonate s aggregators (at the bottom of the tree) and ask a set of contributors for their shares, with the same protocol. If no control is done, the contributor cannot distinguish a real query from a fake query. To avoid such an attack, every aggregator must check the signature of the incoming query using the public key of the sender, having previously checked the validity of the sender's certificate. Since all the nodes are honest but curious, they must follow the protocol and thus cannot create a specific query that would lead to the disclosure of certain data.

Efficiency Issues

What is the divide-and-conquer approach to build the aggregation tree? Assuming the querier knows the height h and the fan-out f of the aggregation tree, it starts creating a tree assigning the whole DHT to its successor(s). Recursively, each aggregator in the tree (i.e., a parent node) is assigned to a DHT region that it will subdivide and delegate to other aggregators in that region. When an aggregator oversees a DHT region, it looks for f nodes that are (almost) evenly spaced across the region. The node responsible for finding peers is a parent aggregator, while the selected nodes are child aggregators. Each child then becomes the parent of the region between itself and the next sibling. This process goes on until the height h is reached. At the last tree level, the tree leaves (i.e., the contributors) are found by using a localized DHT broadcast in the respective region. Contributors willing to participate reply with their private data, after establishing a secure channel with their aggregator parent. The aggregators at level d aggregate the data they receive before sending them to the previous level of the tree down to the root (i.e., the querier) which performs the final aggregation to obtain the result. Figure 1 illustrates this process with two nodes per group (blue and red) by using letters to represent a group. The fan-out is 4 and the height is 3 (excluding the querier Q). Q selects his successor, A, who is responsible of the whole DHT and is the root of the tree. A uses its finger table to contact C, E and B. C recursively contacts D. The second level of the tree is built. Then B, E, C and D contact recursively the nodes for the second level (the figure only shows what happens with E for readability). When leaves are contacted, they send one share to each aggregators of the group (i.e., blue and red) which are summed-up separately in each aggregation tree and finally summed-up by Q. How does an aggregator contribute? If a node selected as aggregator in the tree wishes to contribute, it can simply add its data to the partial aggregate it computes before sending it to its parent. Note that it will add it without splitting the data into shares since its parent cannot guess this addition. To compute an average, we need to count the number of contributors and thus, the aggregator will add s to the count of share contributions: each aggregator accounts the number of shares it received, and the total will be finally divided by s to obtain the number of contributors. Consequently, aggregators do not appear as leaves in the aggregation tree. Note that this is not the case for backup nodes which must have the possibility to appear as leaves of the tree in case they wish to contribute.

DHT Aggregation tree Chord

How are the tree fan-out f and height h computed? At one extreme, a binary tree (f = 2) distributes the query load on a maximum number of aggregator nodes but increases the communications costs, including the creation of many secure channels to transfer the intermediate results. At the other extreme, a tree limited to a unique aggregator (f = σ × N ) minimizes the communications and thus the number of secure channels (1 per contributor). It minimizes the total system load induced by the query but concentrates most of that load on this unique aggregator (that becomes overloaded by asymmetric crypto operations for the communication decryption). An "ideal" aggregation tree would be completely balanced, with the same fan-out all along the tree. Moreover, this fan-out (and thus the height of the tree) would be cleverly chosen to optimize the query latency without impacting too much the total load. Note that this depends on the PDMS characteristics, i.e., communication speed or computation power. Finally, the tree height is simply computed based on the number of contributors (σ × N ) and the tree fan-out. σ can be estimated, for instance by contacting all nodes within a region of the DHT, and checking the ratio of nodes willing to participate. Since nodes are uniformly distributed in the DHT thanks to the hash of their public key, choosing a sample of the population should give a good estimation of σ .

PRELIMINARY RESULTS

As in most evaluations of distributed systems [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], we implemented a simulator allowing varying any parameter: number of nodes N , of colluding nodes C, security threshold α, selectivity σ , and β, a ratio defined below. Our simulator captures two metrics: (i) for the network utilization, we consider the number of exchanged messages as the most important metric (compared to, e.g., the message size); (ii) for the PDMS resource utilization, the simulator counts the asymmetric cryptographic operations which are, by far, the most expensive operations. The output of the simulator is the protocol latency and total work. They depend on β, the relative cost of one asymmetric cryptographic operation denoted crypt and the latency when sending a message between two PDMSs denoted com. Specifically, β = crypt/(crypt + com) with 0 ≤ β ≤ 1. However, note that the two extremes values of β are not realistic, i.e., β = 0 when crypt = 0 or com = +∞, β = 1 when com = 0 or crypt = +∞.

Our protocol is adaptive to σ and β, thus called Adaptive in this section. To measure the impact of these two parameters on the aggregation costs, we compare the Adaptive protocol to two other simplified versions. First, Full tree is a classical aggregation tree that does not adapt to the query selectivity, i.e., it considers σ = 1: a tree is created recursively until all nodes are included, but only those willing to contribute will send back shares. Second, Single level considers that β = 0, i.e., the communication cost is so high that we must minimize it, thus concentrating all the computation on a single group, collecting the shares from all participants, and sending the results to the querier.

We consider a network with N = 1, 000, 000 nodes, a quite large attack level (C = 10, 000) and a high security threshold (α = 10 -6 ) and compare the above protocols in relative terms, i.e., dividing the latency/total work of Full tree/Single Level by the one of Adaptive.

We first confirmed that the adaptive protocol is scalable. With increasing values of N , we obtained a logarithmic increase of the latency, thanks to the DHT and the divide-and-conquer approach. We also verified that the number of colluding nodes C has a small impact on the protocol latency, with reasonable values of C w.r.t. N

Full tree/Adaptive

Single level/Adaptive 10 -4 10 -3 10 -2 10 -1 10 0 10 0 in accordance with the considered threat model. Thus, in the rest of this section, we focus on the adaptability feature of our protocol and leave the evaluation of its reliability for future works. We vary the selectivity σ (keeping β = 0.5) and the PDMSs characteristics β (keeping σ = 0.01). The results are presented in Figures 2 and3 (log scale on Y axis for all graphs and on X axis for selectivity only).

Let's first focus on the Single Level protocol studied to show the impact of an extreme strategy, i.e., concentrating all the load on a single (group of) node(s). As expected, Single Level always provides a better total work than Adaptive and Full tree. However, the latency increases linearly with the number of participants leading rapidly to prohibitive costs. Practically, Single Level is competitive only if the selectivity is extremely high (i.e., tens to a few hundreds of contributors) or β = 0 (i.e., unrealistic setting).

Execution based on aggregation trees (Full tree or Adaptive) are much scalable for handling many contributors by distributing the workload. Note that for a maximal selectivity, both approaches have exactly the same latency, as their structure is identical. However, Full tree becomes more costly for both latency and total work as soon as the selectivity is below 1. Indeed, the adaptive fan-out and tree depth of Adaptive can reduce the latency up to a factor of 3 and especially the total work up to two orders of magnitude, which indicates the importance of adapting the aggregation structure to the computation and system settings.

𝛽 ratio relative total work

In the last part of our experimental evaluation, we study in more details the Adaptive protocol. In particular, we evaluate the impact of the tree fan-out on the latency and the total work of the protocol with different values of β while keeping σ = 0.01. The results are presented in Figure 4 (log scale on the X axis for both graphs). As above and to increase the readability, we represent relative values for both the latency and the total work, i.e., the ratio between the latency value (or the total work value) and its minimum observed value.

As expected, increasing the fan-out, decreases the total work, as the aggregation tree includes less nodes. This reduces the total amount of communications (and hence reduces the number of secure channels), but concentrates the cryptographic load on a few nodes, leading generally to a higher latency. However, we observed an exception to this behavior for small fan-out values. In this case, the communication overhead required to construct the tree leads to sub-optimal latency. With small values of β (i.e., the communication cost is larger than the cryptographic cost), this overhead is more prominent. On the contrary, once the fanout increases, smaller values of β result in a decreased latency, as the cryptographic operations, which are dominant, are relatively cheaper.

Our results confirm that there is a sweet spot for the fan-out depending on the PDMSs and network characteristics. The results also indicate that, depending on the application requirements, the fan-out can be adjusted to obtain a better trade-off between latency and total work. For example, training a machine learning model on user's data may be less restricted in terms of latency than a real-time traffic analysis. For instance, when β = 0.6, choosing a fan-out of 8 leads to a total work only 3% higher than the optimal value, while the latency is 32% larger than the optimal value.

CONCLUSION AND FUTURE WORKS

In this short paper, we made the first steps towards the design of an aggregation protocol providing interesting properties: highly scalable, privacy preserving, adaptable to selective participation, to several system settings, with a tree-like structure enabling robustness to failure; all this without compromise on the result quality. This protocol could be a building block to compute statistics on large communities of PDMS users or even to train ML algorithms. There is still a long way to go before providing all the required properties with efficient and secure protocols. Our next steps are to focus on the reliability aspect, selectivity estimation, and performance enhancements in the case of ML algorithms manipulating large datasets and requiring many iterations on users' data. This is an exciting research agenda with innovative usages in perspective.

Figure 1 :

 1 Figure 1: Building the aggregation tree based on DHT

Figure 2 :

 2 Figure 2: Latency and total work relatively to the Adaptive strategy varying σ

Full

Figure 3 :

 3 Figure 3: Latency and total work relatively to the Adaptive strategy varying β

Figure 4 :

 4 Figure 4: Relative latency and relative total work w.r.t. the minimum value varying the fan-out


Louis Tsakou

Julien Paganini

Jim F Kaufman
email: jim.kaufman@ed.ac.uk

Pierre Pontarotti
email: pierrepontarotti@univ-amu.fr

Origins of the RAG Transposome and the MHC

Keywords: hairpin, flanking, DDE transposon excision, Artemis, palindromic diversity, convergent evolution

How innate immunity gave rise to adaptive immunity in vertebrates remains unknown. We propose an evolutionary scenario beginning with pathogen-associated molecular pattern(s) (PAMPs) being presented by molecule(s) on one cell to specific receptor(s) on other cells, much like major histocompatibility complex (MHC) molecules and T cell receptors (TCRs). In this model, mutations in MHC-like molecule(s) that bound new PAMP(s) would not be recognized by original TCR-like molecule(s), and new MHC-like gene(s) would be lost by neutral drift. Integrating recombination activating gene (RAG) transposon(s) in a TCR-like gene would result in greater recognition diversity, with new MHC-like variants recognized and selected, along with a new RAG/TCR-like system. MHC genes would be selected to present many peptides, through multigene families, allelic polymorphism, and peptide-binding promiscuity.

Presentation of the Evolutionary Hypotheses

When the vertebrate adaptive immune system was first investigated, two aspects were particularly impressive: i) B-and T-cell repertoire diversity and the generation of this diversity by recombination, and ii) the enormous polymorphism of molecules encoded by the major histocompatibility complex (MHC), and these proteins bind numerous peptides. It has now become clear that this molecular system, largely involving immunoglobulin (Ig) domains, may have already been in place in the lineage leading to jawed vertebrates, including cartilaginous and bony fish, amphibians, reptiles, birds and mammals [START_REF] Flajnik | Origin and evolution of the adaptive immune system: genetic events and selective pressures[END_REF][START_REF] Kaufman | Unfinished Business: Evolution of the MHC and the Adaptive Immune System of Jawed Vertebrates[END_REF] The discovery of a parallel system in jawless fish, based on leucine-rich repeats (LRRs) rather than Ig domains, suggests that the vertebrate cellular system is common to both jawless and jawed vertebrates [START_REF] Pancer | The evolution of adaptive immunity[END_REF][START_REF] Boehm | Evolution of Alternative Adaptive Immune Systems in Vertebrates[END_REF][START_REF] Flajnik | A Convergent Immunological Holy Trinity of Adaptive Immunity in Lampreys: Discovery of the Variable Lymphocyte Receptors[END_REF] (see Box 1).

In this opinion piece, we propose several hypotheses that together, can explain the emergence of the recombination activating gene (RAG)-based adaptive immune system in a jawed vertebrate ancestor following the evolution of several linked biological traits. We use the evolutionary consequence of co-opting genetic traits to propose the origin of MHC polymorphism. We first discuss the concept that a complex innate immune system may have existed long before the emergence of the vertebrate ancestor. This may have included large multigene families able to recognize foreign pathogens, cell proliferation, and immune memory following pathogen contact, as well as pathogen defense via AID/APOBEC-like (activation-induced deaminase/apolipoprotein B mRNA editing enzyme, catalytic polypeptide-like) cytidine deaminase genes. We also present arguments supporting the possible presence of clonal expansion and allelic exclusion, with each clone expressing a member of the multigene family, and recognizing a pathogen-associated molecular pattern (PAMP). We then describe the RAG DDE transposon, which belongs to a functional transposon family that allows palindromic (P) diversity after excision and DNA repair, recognized to have been active in organisms --from the ancestor of the bilaterians (animals including protostomes, deuterostomes and a few other groups), to the ancestor of jawed vertebrates (Figure 1). We posit that the biochemical switch from the RAG transposon insertion and excision to the RAG sequence-specific recombination was a relatively simple functional shift. These three properties would have increased the likelihood of RAG transposon being co-opted as a major player in gene recombination, modulating the somatic diversity of antibodies (immunoglobulins) and T cell receptors (TCR).

Finally, we propose that the somatic receptor diversity orchestrated by RAG allowed the emergence of MHC peptide-binding promiscuity and polymorphism. Many excellent papers and reviews have described and proposed hypotheses on the origin and evolution of the adaptive immune system and the MHC, although here, we focus on the origin of somatic diversification and its consequence on the evolution of MHC molecules.

The origins of vertebrate adaptive immunity in metazoans

In common with vertebrate adaptive immune systems, other metazoans can harbor large multigene families able to recognize foreign pathogens. There is also evidence for cell proliferation after pathogen contact and immune memory. In addition, clonal expansion and allelic exclusion of receptors are present in some metazoans, and AID/APOBEC-like enzymes are widely present.

To discuss the former first three points, some non-vertebrate metazoan genomes display large multigene families involved in innate immunity, including those based on LRRs --such as tolllike receptors (TLRs) and other pathogen recognition receptors (PRRs) likely to recognize PAMPs, and those based on Ig-like domains --such as IgV-IgC receptors likely involved in "natural killer" activity [START_REF] Buckley | Diversity of animal immune receptors and the origins of recognition complexity in the deuterostomes[END_REF][START_REF] Litman | The origins of vertebrate adaptive immunity[END_REF]. Second, PAMP activation gives rise to cell activation in metazoans [START_REF] Boehm | Evolution of Alternative Adaptive Immune Systems in Vertebrates[END_REF], but there are reports that PAMP activation gives rise to immune cell proliferation [START_REF] Homa | Exposure to immunostimulants induces changes in activity and proliferation of coelomocytes of Eisenia andrei[END_REF][START_REF] Holm | Induced cell proliferation in putative haematopoietic tissues of the sea star, Asterias rubens (L.)[END_REF][START_REF] Salamat | Involvement of protein kinase C signalling and mitogen-activated protein kinase in the amebocyte-producing organ of Biomphalaria glabrata (Mollusca)[END_REF].

Third, numerous studies have demonstrated various forms of immune memory in many non-vertebrate metazoans (for review, see [START_REF] Milutinović | Immune memory in invertebrates[END_REF]). Although the evidence is fragmentary, the existence of even a few examples shows that these biological traits exist outside of vertebrates and may have provided the basis for the vertebrate adaptive immune system.

For the last two points, clonal expression of receptors and allelic exclusion are common mechanisms in eukaryotes, rather than mechanisms limited to the vertebrate adaptive immune system, such as the multigene family of olfactory receptors and/or the antigenic variation of variable surface glycoproteins (VSGs) in trypanosomes [START_REF] Glover | VEX1 controls the allelic exclusion required for antigenic variation in trypanosomes[END_REF][START_REF] Monahan | Monoallelic expression of olfactory receptors[END_REF]. AID/APOBEC enzymes have several functions in vertebrates [START_REF] Conticello | The AID/APOBEC family of nucleic acid mutators[END_REF], including generating diversity of non-self recognition, producing point mutations (for instance, B-cell receptors in jawed vertebrates), and driving gene conversion mechanisms by DNA breakage, followed by repair mechanisms that increase the probability of gene conversion in cyclostomes and some invertebrates [START_REF] Arakawa | Requirement of the activation-induced deaminase (AID) gene for immunoglobulin gene conversion[END_REF][START_REF] Rogozin | Evolution and diversification of lamprey antigen receptors: evidence for involvement of an AID-APOBEC family cytosine deaminase[END_REF]. Orthologs of this family are also found with similar activities in deuterostomes, and the AID/APOBEC-like cytidine deaminase is expressed preferentially in tissues undergoing constant direct interaction with potential pathogens, can be induced upon pathogen challenge, and is involved in innate immunity acting on non-self-DNA [START_REF] Liu | Diversification of AID/APOBEC-like deaminases in metazoa: multiplicity of clades and widespread roles in immunity[END_REF][START_REF] Krishnan | Diversification of AID/APOBEC-like deaminases in metazoa: multiplicity of clades and widespread roles in immunity[END_REF].

Thus, in the pre-adaptive immune system, multigene families of PRRs and IgV-IgC receptors could have recognized PAMPs leading to cellular activation and proliferation, and immune memory. The generation of diversity for these multigene families could have been driven by members of the AID/APOBEC family [as proposed in [START_REF] Liu | Diversification of AID/APOBEC-like deaminases in metazoa: multiplicity of clades and widespread roles in immunity[END_REF]], first involved in non-self-recognition with one family member co-opted during vertebrate evolution by shifting the mutagenic activity from non-self to self. In this model, the mechanisms for clonal expression and allelic exclusion would lead to each clone expressing a single member of the multigenic family recognizing particular PAMPs.

The next step: emergence of diversified receptors

As described above, two adaptive immune systems are found in vertebrates (see Box 1). In considering the origins of the adaptive immune system of jawless vertebrates, two potentially ancestral genes are found in various metazoans and could have given rise to the diversified variable lymphocyte receptors (VLRs); namely, many proteins with LRR domains -particularly TLRs and AID/APOBEC-like enzymes. In contrast, the emergence of the adaptive immune system of jawed vertebrates is less clear, with plausible candidates for the receptors in metazoans, but rather complex in terms of the generation of diversity (see Box 2). Antibody and TCR genes of jawed vertebrates are based on Ig domains assembled from separate variable (V), diversity (D) and joining (J) gene segments during B and T lymphocyte development to give contiguous VJ and V(D)J sequences. The process is initiated by the RAG endonuclease involved in excision of DNA between the gene segments and is continued by ubiquitously-expressed DNA repair enzymes (see Box 3). The appearance of RAG has long been considered a key evolutionary step that can explain the origin of the jawed vertebrate adaptive system [START_REF] Thompson | New insights into V(D)J recombination and its role in the evolution of the immune system[END_REF][START_REF] Sakano | Sequences at the somatic recombination sites of immunoglobulin light-chain genes[END_REF].

RAG origin

The discovery of recombination signal sequences (RSSs) flanking the V, D and J gene segments, along with the mechanism of RSS cleavage --which is similar to several cut-and-paste DNA transposases (DDE transposases) [START_REF] Sakano | Sequences at the somatic recombination sites of immunoglobulin light-chain genes[END_REF][START_REF] Mcblane | Cleavage at a V(D)J recombination signal requires only RAG1 and RAG2 proteins and occurs in two steps[END_REF][START_REF] Agrawal | Transposition mediated by RAG1 and RAG2 and its implications for the evolution of the immune system[END_REF][START_REF] Hiom | DNA transposition by the RAG1 and RAG2 proteins: a possible source of oncogenic translocations[END_REF], resulted in the hypothesis (see Box 3) that a DDE transposon inserted into an Ig-like gene, eventually leading to antibody/TCR gene rearrangement [START_REF] Thompson | New insights into V(D)J recombination and its role in the evolution of the immune system[END_REF].

The experimental analyses of the RAG transposon from amphioxus (a chordate from the sister group of vertebrates, see Figure 1), devoid of any known adaptive immune system, shed light on the functional shift from a RAG transposon to the RAG sequence-specific recombination activating system. First, the excision reaction is similar for the two endonucleases: the transposase recognizes terminal inverted repeat (TIR) sequences, and the co-opted endonuclease (RAG) recognizes TIR-like sequences (i.e. the RSSs) [START_REF] Huang | Discovery of an Active RAG Transposon Illuminates the Origins of V(D)J Recombination[END_REF]. Both involve a nickhairpin mechanism characteristic of several DDE DNA transposases, including RAG/Transib (with Transib having only the RAG1 core, i.e. the endonuclease, present in several protostomes), HAT, and Mutator [START_REF] Lafaille | Junctional sequences of T cell receptor gamma delta genes: implications for gamma delta T cell lineages and for a novel intermediate of V-(D)-J joining[END_REF][START_REF] Fugmann | The origins of the Rag genes--from transposition to V(D)J recombination[END_REF][START_REF] Liu | Transposition of Mutator-like transposable elements (MULEs) resembles hAT and Transib elements and V(D)J recombination[END_REF][START_REF] Hickman | Structural insights into the mechanism of double strand break formation by Hermes, a hAT family eukaryotic DNA transposase[END_REF]. After excision, the hairpin-tipped segments are processed by the evolutionarily conserved endonuclease Artemis, performing an asymmetric opening of the hairpin, and leading to palindromic P nucleotide variation (see Box 3) [START_REF] Huang | Discovery of an Active RAG Transposon Illuminates the Origins of V(D)J Recombination[END_REF][START_REF] Colot | Extensive, nonrandom diversity of excision footprints generated by Ds-like transposon Ascot-1 suggests new parallels with V(D)J recombination[END_REF]. Other nonvertebrate species also bear a RAG transposon that is likely to work in a similar manner to that of amphioxus (Box 4 and below).

Of note, Artemis and all proteins involved in non-homologous end joining (NHEJ, a ubiquitous DNA repair pathway) are present in all metazoans [START_REF] Bonatto | In silico identification and analysis of new Artemis/Artemis-like sequences from fungal and metazoan species[END_REF], and that homologs performing a similar function are present in all eukaryotes, including PSO2 in yeast [START_REF] Tiefenbach | Pso2 (SNM1) is a DNA structure-specific endonuclease[END_REF]. Thus, co-option of RAG is not just co-option of the transposon, but co-option of a whole system of transposition which includes the cellular proteins that the transposon interacts with to perform the transposition. In this view, the RAG transposome includes the DDE transposon (transposase /TIR), the Artemis nuclease, and the cellular NHEJ enzymatic machinery.

There are differences between the RAG transposome (dependent on the RAG transposon, a piece of "selfish" DNA) and the RAG system (which has been "domesticated" for a useful function in the organism). One major difference is at the level of the flanking fragment, in which terminal deoxytransferase (TdT) adds N-nucleotides to the V, D, and J segments of the TCR and BCR genes during gene recombination, increasing junctional diversity. Preliminary work suggests that the TdT gene has a long phylogenetic history, although this remains to be fully validated; in this scenario, the domesticated RAG system would have co-opted TdT. A second major difference is at the level of the excised fragment flanked by RSSs or TIRs. The domesticated RAG actively directs cleaved signal and coding ends into the NHEJ repair pathway for signal-and coding-joint formation. In contrast, the RAG transposon strongly favors transposition, but allows some TIR-TIR joint formation [START_REF] Huang | Discovery of an Active RAG Transposon Illuminates the Origins of V(D)J Recombination[END_REF][START_REF] Carmona | New insights into the evolutionary origins of the recombination-activating gene proteins and V(D)J recombination[END_REF][START_REF] Zhang | Transposon molecular domestication and the evolution of the RAG recombinase[END_REF]. It is possible that the ancestral transposase partially prevented the interaction between the TIR and the NHEJ repair pathway, and that the RAG in jawed vertebrates lost this property, although this remains unknown. In vitro approaches to study this mechanism revealed important amino acid positions in RAG proteins involved in suppressing transposition [START_REF] Zhang | Transposon molecular domestication and the evolution of the RAG recombinase[END_REF], which would be important for avoiding harmful effects in the organism.

The biochemical functions of the DDE transposome and the vertebrate RAG system (a sequencespecific recombination activating system) are similar; hence the biochemical shift from a transposome to a sequence-specific recombination activating system seems to constitute a relatively straightforward evolutionary step [START_REF] Tsakou | DDE transposon as public goods[END_REF]. This idea is supported by the fact that many other DDE transposomes have been co-opted as sequence-specific recombination activating systems [START_REF] Tsakou | DDE transposon as public goods[END_REF], including Piggymac/TPB1/TPB2/TPB6 in ciliates [START_REF] Baudry | a domesticated piggyBac transposase involved in programmed genome rearrangements in the ciliate Paramecium tetraurelia[END_REF][START_REF] Cheng | The piggyBac transposon-derived genes TPB1 and TPB6 mediate essential transposon-like excision during the developmental rearrangement of key genes in Tetrahymena thermophila[END_REF], Kat 1 in yeast [START_REF] Rajaei | Domesticated transposase Kat1 and its fossil imprints induce sexual differentiation in yeast[END_REF], and MATalpha3 in yeast [START_REF] Barsoum | Alpha3, a transposable element that promotes host sexual reproduction[END_REF].

The vertical evolution of the RAG transposon and the origin of RAG

From the concepts presented above, any DDE transposon capable of creating a hairpin in the region flanking the excised fragment could have been co-opted as RAG, since such DDE transposons are able to generate P nucleotides involved in the generation of diversity [START_REF] Lu | Extent to which hairpin opening by the Artemis:DNA-Pkcs complex can contribute to junctional diversity in V(D)J recombination[END_REF]. One might wonder what the advantage of the RAG transposon might be, compared to these other

transposons. The answer could come from the different evolutionary behaviors of these transposons.

Phylogenetic analysis has been performed on hairpin-forming DDE transposons: HAT [START_REF] Arensburger | Phylogenetic and functional characterization of the hAT transposon superfamily[END_REF],

Mutator [START_REF] Dupeyron | Evolution of Mutator transposable elements across eukaryotic diversity[END_REF], Transib [START_REF] Hencken | Functional characterization of an active Rag-like transposase[END_REF] and other DDE transposons [START_REF] Wallau | Horizontal transposon transfer in eukarya: detection, bias, and perspectives[END_REF][START_REF] Dotto | HTT-DB: new features and updates[END_REF][START_REF] Joly-Lopez | Phylogenetic and Genomic Analyses Resolve the Origin of Important Plant Genes Derived from Transposable Elements[END_REF][START_REF] Bouallègue | Molecular Evolution of piggyBac Superfamily: from Selfishness to Domestication[END_REF][START_REF] Peccoud | Massive horizontal transfer of transposable elements in insects[END_REF]. Such phylogenetic studies show that these DDE transposons have apparently evolved in a horizontal manner, which contrasts with the RAG transposon, which evolved in a vertical manner. In contrast, the phylogenetic analysis of RAG transposon and vertebrate RAG sequences, as well as sequences belonging to the RAG family with unknown status and fossilized RAG transposons, shows a sequence tree topology following the species phylogenetic tree [START_REF] Morales Poole | The RAG transposon is active through the deuterostome evolution and domesticated in jawed vertebrates[END_REF][START_REF] Martin | Evidence for an ancient bilaterian origin of the RAG-like transposon. Mobile Elements[END_REF]. The phylogenetic reconstruction also indicates that the RAG structure appeared at least at the origin of the bilaterians. Therefore, the RAG transposon appears to have been active since its birth in the bilaterians' ancestor and co-opted as a specific endonuclease in the jawed vertebrate ancestor. The presence of the RAG transposon that was inherited in the genome from one generation to the next may have increased the likelihood that it would be co-opted compared to other transposons that evolve(d) by horizontal transmission between individuals.

Horizontal transfer of DDE transposons may allow these transposable elements to enter naïve genomes which they invade by making copies of themselves and then escape before they become fully silenced by the Piwi-piRNA pathway --a host mechanism against transposable elements [START_REF] Aravin | The Piwi-piRNA pathway provides an adaptive defense in the transposon arms race[END_REF][START_REF] Lerat | TEtools facilitates big data expression analysis of transposable elements and reveals an antagonism between their activity and that of piRNA genes[END_REF]. The RAG transposon is able to transpose within a genome [START_REF] Huang | Discovery of an Active RAG Transposon Illuminates the Origins of V(D)J Recombination[END_REF][START_REF] Morales Poole | The RAG transposon is active through the deuterostome evolution and domesticated in jawed vertebrates[END_REF], but to our knowledge, not between genomes of divergent species. Therefore, on the one hand, the RAG transposon seems to have lost the ability to transpose between species, and on the other hand, it seems to have evolved a mechanism to escape the Piwi-piRNA system of the host.

In this context, it should be noted that only one of the two subunits encoded by the RAG transposon comes from a transposon, while the other seems to have a host origin. The RAG1 subunit corresponds to the DDE transposase, highly related to Transib, while the RAG2 in the RAG transposon derived from a host genome [START_REF] Kapitonov | RAG1 core and V(D)J recombination signal sequences were derived from Transib transposons[END_REF][START_REF] Kapitonov | Evolution of the RAG1-RAG2 locus: both proteins came from the same transposon[END_REF]. Several sequence similarity analyses propose that a RAG-like open reading frame flanked by RSS-like TIRs captured a RAG2-like open reading frame from an ancestral protostome to give rise to the original RAG transposon [START_REF] Litman | The origins of vertebrate adaptive immunity[END_REF][START_REF] Carmona | New insights into the evolutionary origins of the recombination-activating gene proteins and V(D)J recombination[END_REF][START_REF] Callebaut | The V(D)J recombination activating protein RAG2 consists of a six-bladed propeller and a PHD fingerlike domain, as revealed by sequence analysis[END_REF]. Thus, the transposon domesticated a part of the host genome, perhaps to evade the Piwi-piRNA of the host and avoid inactivation. However, it is also possible that the transposon was retained for an unknown reason, perhaps including another function for the host.

Consequently, we propose the following conjectural scenario to enhance the published model [START_REF] Fugmann | The origins of the Rag genes--from transposition to V(D)J recombination[END_REF]: i) some time ago, there was an insertion of a complete RAG transposon (or possibly the corresponding miniature inverted-repeat transposable element (MITE, i.e. the TIR of the RAG transposon) that separated an IgV domain (already involved in immune recognition) into V and J segments; ii) after insertion of the complete transposon, the transposase was lost, leaving the native TIRs between the V and J segments intact, while a transposase from another RAG transposon was used, and which in turn, lost its TIR; iii) The TIR-like sequence could be recognized by the RAG transposase and excised along with the internal sequence, leaving hairpin-tipped ends on the flanking segments. These segments could then be processed via Artemis, opening the hairpins asymmetrically, followed by the DNA repair system leading to palindromic (P) diversity. The ability to generate diversity would have then increased with the duplication of the VJ unit (V-TIR-TIR-J) and the co-option of a TdT gene. The system later became more complex, as described by others [START_REF] Hsu | The origin of V(D)J diversification[END_REF].

Of note, the transposon and its corresponding MITE would have had hundreds of millions of years to be inserted anywhere in the genome of many protostome lineages. Some of these events were likely to have been negatively selected, some neutral, and it is possible that the insertion into a genetic system was positively selected that was already engaged in non-self-recognition. We estimate the probability of a RAG transposon insertion in an ancestral V domain to give rise to a bona fide V-J module in some metazoans to be 99% (see table S1 in supplementary material).

A third step: antibody/TCR receptor somatic diversity could drive the appearance of MHC promiscuity and polymorphisms

The classical class I/II genes of the MHC are highly polymorphic, encoding proteins that bind processed peptides within the cell, move to the cell surface, and then interact with TCRs expressed on the surface of T-cells. Each MHC allelic form can bind many peptides, both self and non-self, with a specific amino acid motif. Most developing T-cells bearing TCRs that react with self-MHC molecules bound to self-peptides, are eliminated during maturation in the thymus.

During infection, both self and non-self-peptides are presented by MHC proteins, with non-selfpeptides recognized by TCRs on T-cells, which activate the immune system to respond in a variety of ways. These MHC genes evolved in the ancestor of jawed vertebrates in roughly the same time window as the RAG/V(D)J generation of somatic diversity [START_REF] Flajnik | Origin and evolution of the adaptive immune system: genetic events and selective pressures[END_REF][START_REF] Danchin | The major histocompatibility complex origin[END_REF]. Various hypotheses have been proposed for the origin of MHC genes (see Box 4). In this speculative review, we also propose a scenario whereby MHC genes evolved from PRRs from the innate immune system.

The first part of our hypothesis is that the ancestral MHC-like molecule could have bound some In the second part of this hypothesis, the integration of the RAG transposon into ancestral BCR/TCR-like genes may have led to a significantly increased possibility of recognition; we will focus here only on TCRs, as they interact with the MHC. As a result of the increased possibilities of recognition by the TCRs, mutations in the ancestral MHC-like molecule leading to the binding of new PAMPs could have been recognized by the TCRs, and therefore been selected.

Presumably, this expanded ability of this ancient MHC/TCR system to recognize new PAMPs would have eventually allowed peptides to be bound, presented, and recognized during an immune response.

As a third part of this hypothesis, we posit that the ancient MHC molecule was selected to bind many peptides to allow the recognition of numerous pathogens, possibly via the appearance of allelic polymorphisms and peptide-binding promiscuity (as well as from the generation of multigene families). Both allelic polymorphisms and promiscuity are properties of MHC molecules encoded by a single gene, and both extend the number of peptides that can be bound, and thus, the number of pathogens that can be recognized [START_REF] Spurgin | How pathogens drive genetic diversity: MHC, mechanisms and misunderstandings[END_REF][START_REF] Radwan | Advances in the evolutionary understanding of MHC polymorphism[END_REF][START_REF] Kaufman | Generalists and Specialists: A New View of How MHC Class I Molecules Fight Infectious Pathogens[END_REF]. If a particular MHC molecule only bound a limited number of peptides, then a new pathogen would not be recognized by the MHC/TCR system unless a mutation occurred in MHC genes; thus, such a mutation would be selected to deal with the new pathogen. However, the mutation might prevent the new molecule from binding previously-bound peptides, so that the host would be vulnerable to the original pathogen still in the environment. In order to deal with both old and newly-arising pathogens, pathogen-mediated selection leads to allelic polymorphism [START_REF] Spurgin | How pathogens drive genetic diversity: MHC, mechanisms and misunderstandings[END_REF][START_REF] Radwan | Advances in the evolutionary understanding of MHC polymorphism[END_REF][START_REF] Kaufman | Generalists and Specialists: A New View of How MHC Class I Molecules Fight Infectious Pathogens[END_REF]. Another way to increase recognition of new pathogens would be to increase the range of peptides bound, and such promiscuity can be an important feature of MHC molecules [START_REF] Kaufman | Generalists and Specialists: A New View of How MHC Class I Molecules Fight Infectious Pathogens[END_REF][START_REF] Chappell | Expression levels of MHC class I molecules are inversely correlated with promiscuity of peptide binding[END_REF][START_REF] Manczinger | Pathogen diversity drives the evolution of generalist MHC-II alleles in human populations[END_REF]. A third way to increase recognition of new pathogens would be to increase the number of MHC genes, but the need to avoid recognition of self-peptides might limit the size of the MHC multigene family (although there are theoretical arguments to the contrary) [START_REF] Vidović | Unresponsiveness to a foreign antigen can be caused by self-tolerance[END_REF][START_REF] Nowak | The optimal number of major histocompatibility complex molecules in an individual[END_REF][START_REF] Borghans | Thymic selection does not limit the individual MHC diversity[END_REF]. whether there is a functional equivalent of MHC molecules in jawless fish remains unclear.

Box 2 Evolution of two systems of adaptive immunity in vertebrates

An important question concerns the origin of the complexity of cells involved in adaptive immunity. Both molecular systems with somatic diversification (VLR/AID and VDJ/RAG) could have been in place along with a pre-adaptive immune system [START_REF] Kaufman | Unfinished Business: Evolution of the MHC and the Adaptive Immune System of Jawed Vertebrates[END_REF][START_REF] Boehm | Evolution of Alternative Adaptive Immune Systems in Vertebrates[END_REF][START_REF] Flajnik | A Convergent Immunological Holy Trinity of Adaptive Immunity in Lampreys: Discovery of the Variable Lymphocyte Receptors[END_REF]. Then, the two molecular systems might have evolved in an independent manner in the two vertebrate lineages, jawless fish and jawed vertebrates. The mechanism of diversity generation is similar in both vertebrate lineages, starting with a DNA double-strand break (DSB) in the region involved in DNA recognition, followed by gene repair from either non-homologous end-joining (NHEJ) mechanisms or gene conversion [START_REF] Arakawa | Requirement of the activation-induced deaminase (AID) gene for immunoglobulin gene conversion[END_REF][START_REF] Rogozin | Evolution and diversification of lamprey antigen receptors: evidence for involvement of an AID-APOBEC family cytosine deaminase[END_REF]. The DSB in cyclostomes (and some jawed vertebrates) is due to an enzyme from the AID/APOBEC family and repair by gene conversion events, while the DSB in most jawed vertebrates is due to the RAG sequence-specific endonuclease, followed by DNA repair through a NHEJ mechanism.

It is important to note that the function of possible T-and B-cell lineages prior to the time adaptive immunity arose is entirely unclear. Innate lymphoid cells (ILCs) found in mammals are potential candidates for the functions of non-adaptive T cells before adaptive immunity (although they could also be a novelty of placental mammals), but system replacement might be more likely After cleavage, the hairpin-tipped coding segments are cut by the Artemis endonuclease, joined imprecisely by the repair cell machinery to form a coding joint (CJ). The imprecise joins are due to the palindromic (P) diversity (due to Artemis), nucleotide deletion diversity, and nucleotide (N) diversity (due to the terminal deoxynucleotidyl transferase, TdT), while the cleaved RSSs (and eliminated DNA segments) are joined precisely to form a signal joint (SJ). End-processing and joining are carried out by the NHEJ DNA repair pathway [for complete review, see [START_REF] Teng | Regulation and Evolution of the RAG Recombinase[END_REF]].

The discovery of RSSs, along with the mechanism of RSS cleavage (similar to several cut-andpaste DNA transposases (DDE transposases)) [START_REF] Sakano | Sequences at the somatic recombination sites of immunoglobulin light-chain genes[END_REF][START_REF] Mcblane | Cleavage at a V(D)J recombination signal requires only RAG1 and RAG2 proteins and occurs in two steps[END_REF] led to the hypothesis that a DDE transposon invaded an Ig-like gene, eventually resulting in antibody/TCR gene rearrangement [START_REF] Thompson | New insights into V(D)J recombination and its role in the evolution of the immune system[END_REF]. This hypothesis was strengthened by the demonstration that RAG is capable of DNA transposition [START_REF] Agrawal | Transposition mediated by RAG1 and RAG2 and its implications for the evolution of the immune system[END_REF][START_REF] Hiom | DNA transposition by the RAG1 and RAG2 proteins: a possible source of oncogenic translocations[END_REF]. The discovery of the Transib transposon in non-vertebrates (corresponding to the RAG1 core sequence and whose TIRs are similar to the RSSs) supports this hypothesis [START_REF] Kapitonov | RAG1 core and V(D)J recombination signal sequences were derived from Transib transposons[END_REF]. The finding being potentially ancestral to T cells [START_REF] Du Pasquier | The phylogenetic origin of antigen-specific receptors[END_REF]. NK cells can recognize stressed cells without direct pathogen recognition. A specific scenario was recently suggested in which an NK cell receptor recognized an MHC-like molecule with a closed groove, which evolved into an MHC-like

molecule with an open groove to detect proteins bearing leucine as a starting amino acid, and which appear in stressed cells [START_REF] Kaufman | Unfinished Business: Evolution of the MHC and the Adaptive Immune System of Jawed Vertebrates[END_REF].

A linked issue is whether primordial MHC genes and molecules were organized as in the class I or class II systems. A scenario based on structure is that the original MHC molecule was a homodimer of class II β-like chains, with gene duplication and divergence giving rise to heterodimers of class II α-like and β-like chains, followed by an inversion leading to a class I heavy-like chain and a β 2 -microglobulin chain with a transmembrane region, and a subsequent mutation to give rise to a class I-like molecule [START_REF] Kaufman | Unfinished Business: Evolution of the MHC and the Adaptive Immune System of Jawed Vertebrates[END_REF][START_REF] Kaufman | The class II molecules of the human and murine major histocompatibility complex[END_REF]. A scenario based on function suggested the transfer of a peptide-binding region from a chaperone in front of an IgC-like region to produce a class I-like heavy chain first [START_REF] Ruff | MHC signaling during social communication[END_REF]. Recent evidence for highly promiscuous peptide binding and C-terminal protrusions of peptides from the groove of chicken class I molecules renders the differences between class I and II molecules less clear [START_REF] Kaufman | Generalists and Specialists: A New View of How MHC Class I Molecules Fight Infectious Pathogens[END_REF][START_REF] Chappell | Expression levels of MHC class I molecules are inversely correlated with promiscuity of peptide binding[END_REF][START_REF] Xiao | An Invariant Arginine in Common with MHC Class II Allows Extension at the C-Terminal End of Peptides Bound to Chicken MHC Class I[END_REF].

  PAMPs, presenting them to ancestral TCR-like molecules. The ancestral MHC-like molecule may have been limited to just a few pathogens, and each ancestral TCR-like molecule may have only recognized a particular class of PAMP bound to the ancestral MHC-like molecule. Thus, if a mutation of the ancestral MHC-like molecule allowed binding of a new PAMP, this combination might not be recognized by the ancestral BCR/TCR-like molecules (even if they were encoded by a multigene family); therefore, the new MHC-like molecule might not be selected and the mutant gene could be lost by genetic drift. In fact, if the new MHC-like molecule lost binding to the original PAMPs, it might be negatively selected.

Figure 1 .

 1 Figure 1. Phylogenetic distribution: RAG in jawed vertebrates and the RAG-like transposon.Shown on the consensus bilaterian tree, are the presence of RAG-like transposons[START_REF] Huang | Discovery of an Active RAG Transposon Illuminates the Origins of V(D)J Recombination[END_REF][START_REF] Fugmann | The origins of the Rag genes--from transposition to V(D)J recombination[END_REF][START_REF] Martin | Evidence for an ancient bilaterian origin of the RAG-like transposon. Mobile Elements[END_REF][START_REF] Kapitonov | RAG1 core and V(D)J recombination signal sequences were derived from Transib transposons[END_REF][START_REF] Kapitonov | Evolution of the RAG1-RAG2 locus: both proteins came from the same transposon[END_REF], and the RAG among clades, sequenced from databases. The comparative activity of RAG in V(D)J recombination among jawed vertebrates, and the activity of RAG-like transposons is adapted[START_REF] Huang | Discovery of an Active RAG Transposon Illuminates the Origins of V(D)J Recombination[END_REF][START_REF] Janeway | Immunobiology: the immune system in health and disease[END_REF], showing that this biochemical switch would constitute an unconstrained evolutionary step.

Figure 2 .Box 1 .

 21 Figure 2. Antibody/TCR receptor somatic diversity might drive the appearance of MHC promiscuity and polymorphisms. We propose a hypothetical model whereby the ancestral MHC-like molecule bound certain PAMPs, presenting them to ancestral TCR-like molecules. The ancestral MHC-like molecule may have been limited to just a few pathogens, and each ancestral TCR-like molecule might have only recognized a particular class of PAMP bound to the ancestral MHC-like molecule. A mutation in the ancestral MHC-like molecule may have allowed binding of a new PAMP, but this new combination could not be recognized by the ancestral TCR-like molecule. As a result, the new MHC-like molecule would be lost by genetic drift. The integration of the RAG transposon into an ancestral TCR-like gene may have led to a significantly increased probability of recognition by these original, non-diverse TCRs. Thus, mutations in the ancestral MHC-like molecule may have led to a conformational ability to bind new PAMPs; consequently, mutated MHC molecules could have then been recognized by diverse TCRs thereafter, becoming evolutionarily selected via three mechanisms, peptide-binding promiscuity, allelic polymorphism, and expansion into multigene families. The expanded ability of this ancient MHC/TCR system to recognize new PAMPs would presumably allow peptides to be bound, presented, and recognized during an immune response.

[ 48 ]Box 3 .

 483 . If the first adaptive immune system was based on VLR, then, in jawed vertebrates, a shift might have occurred from IgV-IgC innate immunity, to IgV-IgC adaptive immunity, followed by the loss of VLR-based adaptive immunity. If the first adaptive immune system was based on IgV-IgC, then, in cyclostomes, the reverse may have occurred. In fact, such replacements have been noted for natural killer (NK) cell receptors [2]: at least three families of NK cell receptors exist with analogous functions: lectin-like receptors (overwhelmingly in rodents and to a lesser extent in certain other mammals), Ig-like receptors of the KIR family (one or another of the KIR sub-families, as in humans and other mammals) and a completely different family of Ig-like receptors in bony fish. Emergence of Rearranging B-and T-cell receptors and Brief History of the Origin of RAG The antibody and TCR genes of jawed vertebrates are assembled from variable (V), diversity (D), and joining (J) gene segments during B-and T-lymphocyte development to give contiguous VJ and V(D)J sequences. The process to excise the DNA between the gene segments is initiated by the RAG endonuclease. The RAG endonuclease specifically recognizes recombination signal sequences (RSSs) that flank each gene segment. RSSs are composed of conserved heptamer and nonamer sequences separated by a less conserved spacer sequence of either 12 or 23 bp (12RSS and 23RSS). RAG-mediated DNA cleavage occurs preferentially in a complex containing a 12RSS and a 23RSS, involving a nick-hairpin mechanism.

Acknowledgements

This work was supported by the French Government under the «Investissements d'avenir» (Investments for the Future) program managed by the Agence Nationale de la Recherche (ANR, fr: National Agency for Research), (reference: Méditerranée Infection 10-IAHU-03) to P. P., and by an Investigator Award from the Wellcome Trust to J. K. (110106/Z/15/Z).

Concluding Remarks

We propose a model whereby the ancestral MHC-like molecule harbored an innate immune function, but when ancestral TCR-like molecules began to diversify due to RAG domestication, thus increasing their recognition potential, ancient MHC molecules might have increased their peptide-binding capacity through increased promiscuity. However, the peptide-binding capacity may have still been low, compared to the recognition capacity of the TCR; therefore, allelic polymorphism may have evolved via pathogen-mediated selection. As this hypothesis begins with the recognition of PAMPs, for which LRR-containing molecules such as TLRs are major players, a similar scenario might be envisaged for the VLR system, based on LRRs. Thus far, no equivalent of an MHC molecule in cyclostomes has been reported (Box 1), but some analogous molecule might be expected based on this model (see outstanding questions).

Transposable elements are usually considered to be egotistical pieces of DNA, although there is much research on their potential utility for host organisms. The case of the RAG transposon is particularly spectacular: a small piece of DNA that has completely changed immunity in jawed vertebrates and indeed, also the research of many, if not most, immunologists (including the authors of this opinion article). It will be exciting to discover which other accidents of evolution have led to such enormous consequences. of complete RAG transposons (formed by RAG1-like and RAG2-like sequences) in the genome of the protochordate amphioxus (Branchiostoma belcheri) [START_REF] Huang | Discovery of an Active RAG Transposon Illuminates the Origins of V(D)J Recombination[END_REF] and the hemichordate Ptychodera flava [START_REF] Morales Poole | The RAG transposon is active through the deuterostome evolution and domesticated in jawed vertebrates[END_REF], as well as fossilized transposons in several deuterostomes [START_REF] Fugmann | The origins of the Rag genes--from transposition to V(D)J recombination[END_REF][START_REF] Morales Poole | The RAG transposon is active through the deuterostome evolution and domesticated in jawed vertebrates[END_REF][START_REF] Kapitonov | Evolution of the RAG1-RAG2 locus: both proteins came from the same transposon[END_REF] and protostomes [START_REF] Martin | Evidence for an ancient bilaterian origin of the RAG-like transposon. Mobile Elements[END_REF], indicates that the RAG transposon was present at least as far back as the bilaterian ancestor, remained active in several lineages, and was co-opted as part of V(D)J recombination machinery in jawed vertebrates [START_REF] Morales Poole | The RAG transposon is active through the deuterostome evolution and domesticated in jawed vertebrates[END_REF][START_REF] Martin | Evidence for an ancient bilaterian origin of the RAG-like transposon. Mobile Elements[END_REF].

Box 4 The function and origin of MHC molecules

The high polymorphism of classical MHC genes is generally accepted to be a consequence of a molecular arms race between host and pathogens. However, the MHC can also be involved in inbreeding avoidance behavior, and kin-specific cooperation. Since kin selection and inbreeding avoidance are universal phenomena [START_REF] Cardarelli | Two Proteins Form a Heteromeric Bacterial Self-Recognition Complex in Which Variable Subdomains Determine Allele-Restricted Binding[END_REF][START_REF] Tomaso | Allorecognition and Stem Cell Parasitism: A Tale of Competition, Selfish Genes and Greenbeards in a Basal Chordate[END_REF][START_REF] Espinosa | Evidence of Taxa-, Clone-, and Kindiscrimination in Protists: Ecological and Evolutionary Implications[END_REF][START_REF] Fujii | Non-self-and self-recognition models in plant self-incompatibility[END_REF][START_REF] Gruenheit | A polychromatic 'greenbeard' locus determines patterns of cooperation in a social amoeba[END_REF][START_REF] Harada | Mechanism of self-sterility in a hermaphroditic chordate[END_REF][START_REF] Heller | Greenbeard Genes Involved in Long-Distance Kind Discrimination in a Microbial Eukaryote[END_REF][START_REF] Kües | From two to many: Multiple mating types in Basidiomycetes[END_REF][START_REF] Paoletti | Vegetative incompatibility in fungi: From recognition to cell death, whatever does the trick[END_REF][START_REF] Rosengarten | Model systems of invertebrate allorecognition[END_REF][START_REF] Saak | The Self-Identity Protein IdsD Is Communicated between Cells in Swarming Proteus mirabilis Colonies[END_REF][START_REF] Wall | Kin Recognition in Bacteria[END_REF], some authors have proposed that the immune function of the MHC is a derived function [START_REF] Boehm | Quality control in self/nonself discrimination[END_REF][START_REF] Ruff | MHC signaling during social communication[END_REF]. However, even in the best-studied systems for mate choice, evidence that MHC molecules participate in this process, and the putative mechanisms, remain unclear [START_REF] Radwan | Advances in the evolutionary understanding of MHC polymorphism[END_REF][START_REF] Leinders-Zufall | Structural requirements for the activation of vomeronasal sensory neurons by MHC peptides[END_REF].

Various hypotheses have been proposed for the origin of MHC genes. One suggestion was that chaperone genes gave rise to the peptide-binding domains characteristic of MHC molecules [START_REF] Flajnik | Which came first, MHC class I or class II?[END_REF].

Although subsequent structural analysis of HSP70 rules out the specific example suggested by these authors [START_REF] Kaufman | Unfinished Business: Evolution of the MHC and the Adaptive Immune System of Jawed Vertebrates[END_REF], it remains possible that a different ancient chaperone could be the ancestor. Another candidate is IRE1, which is involved as a sensor in the unfolded protein response, and has a structure and peptide-binding properties like MHC molecules [START_REF] Credle | On the mechanism of sensing unfolded protein in the endoplasmic reticulum[END_REF][START_REF] Karagöz | An unfolded protein-induced conformational switch activates mammalian IRE1[END_REF]. A recent suggestion was that the primordial MHC-like molecule evolved from a heavy chain-only antibody molecule that cycled between endosomal compartments and the surface [START_REF] Dijkstra | Ancient features of the MHC class II presentation pathway, and a model for the possible origin of MHC molecules[END_REF]. Another hypothesis was that NK cell receptor-ligand interactions allowed TCR-MHC interactions to evolve, with NK cells Glossary AID/APOBEC deaminases (AADs): family of enzymes that convert cytidine to uridine in single-stranded nucleic acids; involved in numerous mutagenic processes, including those underpinning vertebrate innate and adaptive immunity.

Allelic exclusion:

process by which only one allele of a gene is expressed while the other allele is silenced.

Bilaterian: metazoan animals with a bilaterally symmetric body plan, including the protostomes and deuterostomes.

Cyclostome: jawless fish (also known as agnathan); the sister group of jawed vertebrates Deuterostome: clade of animals including jawed vertebrates, jawless fish, cephalochordates (such as amphioxus), urochordates, hemichordates and echinoderms (such as sea urchins); the sister group of protostomes within bilaterians. Recombination activating genes (RAGs) are two host genes located next to each other that encode RAG1 and RAG2 proteins; these, as a complex, initiate the rearrangement of gene segments encoding antibody and TCR molecules.

DDE transposon (aka class

RAG DDE transposon:

RAG-like sequence found in non-vertebrates, functioning as transposon.

Somatic diversification: the process of mutation in somatic cells, e.g. genomic rearrangement

Terminal deoxytransferase (TdT): enzyme that randomly adds nucleotides to untemplated broken ends of DNA, particularly during somatic diversification of antibody and TCR genes

Toll-like receptor (TLR): one class of PRRs involved in initiating innate immune responses

Transib: DDE transposon from protostomes whose transposase gene is closest to RAG1, and whose TIR is similar to the RAG transposon, and the V(D)J RSSs .

Highlights

RAG evolved from a DDE transposon present in the ancestor of bilaterian animals; it evolved in a vertical manner and was domesticated as RAG in a jawed vertebrate ancestor. This RAG-like transposon belonged to a transposon family with an ability to create palindromic (P) diversity.

A proposed model is that the jawed vertebrate ancestor possessed a complex and powerful innate immune system, where the pre-MHC molecule was able to bind and present certain PAMP molecules to a monomorphic non-rearranging TCR-like molecule.

The integration of the RAG transposon in recognition module of the TCR-like gene may have led to a significant increase in recognition possibilities, presumably allowing new MHC-like variants to be selected.

Hypothetically, the increase in recognition possibilities may have also led to the appearance of MHC polymorphisms and an increase in peptide-binding repertoires (promiscuity). Table S1. Estimated Probability of the RAG transposon insertion in an ancestral V domain.

RAG transposon co-option events

The average transposition for a given DDE transposon per genome is approximately 10 -4 /year [START_REF] Adrion | Genome-Wide Estimates of Transposable Element Insertion and Deletion Rates in Drosophila Melanogaster[END_REF].

The generation time is approximately 1 year in average for Deuterostomia (calculated on the average generation age of the deuterostomian) and might be estimated as 10, including (TIR-------TIR) (MIR), and potentially more, if we look at the Ptychodera genome [START_REF] Morales Poole | The RAG transposon is active through the deuterostome evolution and domesticated in jawed vertebrates[END_REF].

The time of evolution in the deuterostomia lineage of the RAG transposon before its co-option as RAG V(D)J recombinase was approximately 200 million years (the difference between the time the RAG transposon appeared in the ancestor of deuterostomes, and the time of its co-option in the jawed vertebrate ancestor) [START_REF] Morales Poole | The RAG transposon is active through the deuterostome evolution and domesticated in jawed vertebrates[END_REF]. The number of possible positions per gene V is approximately 250, to have a J sequence of at least 50 nucleotides [START_REF] Janeway | Immunobiology: the immune system in health and disease[END_REF]. We could estimate that 100 copies of V genes were present.

Thus, the number of possible transposition events on a V gene might be:

10 -4 x 2(10) 8 x 10 x 250 x 100 = 5 x10 9 .

The size of a deuterostomian genome is on average 5(10) 8 . The probability of observing at least one event in 5(10) 9 repetitions is the complement of not observing any, and as the events are independent (and follow the same distribution), the probability of not observing a single event in 5(10) 9 trials, is the probability of not observing it:

1 -(499999999/500000000) > 5(10) 9 = 1%.

Thus, the probability that the event happened might then be: 99%. Supplementary Material Table S1


Maud Pélissier

Jennifer Krzonowski

Emmanuel Ferragne

Effect of saliency and L1-L2 similarity on the processing of English past tense by French learners: an ERP study

Keywords: ERPs, L2 processing, syntax, L1-L2 similarity, saliency

This study explored the effect of saliency and L1-L2 similarity on the processing of second language morphosyntax. ERP responses to violations of past tense morphology were obtained from adult intermediate French learners of English. Results show that participants processed L2-specific violations as salient events and not as morphosyntactic incongruities.

Introduction

The way the syntax of our first language (L1) interacts with the syntax of a language we are trying to learn (L2) remains a much debated issue in the field of SLA. Some of the possible facilitating factors include the presence of similar structures in the L1 and the saliency of the morphosyntactic structure under scrutiny in the L2 [START_REF] Macwhinney | Extending the Competition Model[END_REF]. In this study, we focused on a structure that contrasts these two factors: ERP responses to morphosyntactic violations of the past tense in polar questions in French learners of English with the auxiliaries DID and HAD. Polar questions using HAD followed by a past participle work in a way that is similar to French, where the past tense is marked both on the auxiliary and the main verb. On the contrary, questions with DID are specific to English in that the past tense is marked only on the auxiliary. However, violations of past-tense inflection are phonologically more salient with DID, where a past morpheme is added to the main verb, than with HAD.

Methods

Participants

Materials and Procedure

The material consisted of 192 simple polar questions, half of them containing the auxiliary DID (DID Condition) and half HAD (HAD condition). Half of the sentences in each condition were made incorrect by varying the presence of the past morpheme. 120 sentences containing other agreement violations and 120 sentences containing a semantic violation were added as fillers.

Participants were asked to focus on the meaning of the sentence and evaluate its semantic acceptability while EEG data were recorded. A fixation cross appeared first for 500 ms and remained on the screen during the auditory presentation of the stimulus and for 1000 ms afterwards. A screen then prompted the participant to evaluate the semantic acceptability of the sentence by pressing a coloured button. As soon as the participant answered or after 2000 ms, the fixation cross appeared again and the next stimulus was presented.

Participants also completed a timed Grammaticality Judgment Task (GJT) with similar stimuli and additional fillers.

EEG data acquisition and analysis

EEGs were recorded with a Biosemi ActiveTwo system with 32 active electrodes, referenced on-line to the two mastoids and re-referenced off-line to the average of the two mastoids. Data were filtered on-line between 0.1 and 100 Hz. Electrode impedance was maintained below 20 Ohms and the signal was sampled at a rate of 512 Hz. Epochs from -200 ms to 1000 ms around the critical point (beginning of the critical past morpheme) were extracted from continuous data. After baseline correction (-200-0 ms) and low-pass filtering at 30 Hz, trials for which peak-to-peak amplitude exceeded 70 μV on the EOG channel or 100 μV on the other channels were automatically rejected. Electrodes were divided into central and lateral sites, the latter also divided into anterior/posterior region and left/right hemisphere. The following temporal windows were selected: 600-900 ms for the P600 and 300-500 ms for the LAN or N400.

Results

Behavioural measures: the GJT

A sensitivity index (d') was computed for each participant and each auxiliary. Analyses showed that the participants' d' was marginally better in the Had condition (F(1,25)=3.48, p=.07) but their response time was shorter with DID (F(1,25)=7.98, p<.01) : on average, it took them 562 ms to re-Effect of saliency and L1-L2 similarity on processing of past tense 3 spond to sentences containing DID and 634 ms for sentences containing HAD.

EEG results

A repeated-measures ANOVA with mean amplitude in the P600 window as dependent variable and Condition (Correct / Incorrect), Auxiliary (DID / HAD), Hemisphere (Left / Right) and Region (Anterior / Posterior) as within-subject variables showed an effect of the interaction between Condition and Auxiliary (F(1,28)=9.15, p<.01). Post-hoc analyses revealed that the effect of Condition in this time window was limited to sentences with DID (p<.001). A similar ANOVA was conducted on the mean amplitude in the 300-500 ms window and an effect of the Condition × Auxiliary interaction (F(1,28)=25.68, p<.001) was found. Post-hoc analyses revealed that with DID, the amplitude was greater in the Incorrect than in the Correct condition (p<.001) but that with HAD, the amplitude was more negative in the Incorrect than in the Correct Condition (p<.001).

Discussion

Violations in the DID condition thus elicited a P600 as well as a positive peak in the 300-500ms window, resembling a P3 component. These viola-tions involve the presence of the past morpheme in a context where it should be absent. They are therefore more phonetically salient than violations with HAD, which are due to the absence of this same morpheme. These results are therefore consistent with the hypothesis that the P600 reflects, as the P3 does, the subjective salience of the stimulus [START_REF] Sassenhagen | The P600as-P3 hypothesis revisited: Single-trial analyses reveal that the late EEG positivity following linguistically deviant material is reaction time aligned[END_REF]. Besides, polar questions with DID represent a complex L2-specific structure, since they involve the movement of the inflectional morpheme from the main verb (where it would be in a declarative sentence) to the auxiliary. This represents an additional processing cost; yet participants were faster to decide for these sentences. This apparent discrepancy, as well as the presence of the P3, suggests that the P600 effect observed here in the DID condition is not a reflection of a better perception of the morphosyntactic error at hand but of an explicit reaction to the superior saliency of this violation.

Violations in the HAD condition elicited a negativity in the 300-500ms window that was not limited to anterior sites, thus more reminiscent of an N400 than a LAN. N400 effects have been found to be elicited by morphosyntactic violations even in native speakers [START_REF] Tanner | ERPs reveal individual differences in morphosyntactic processing[END_REF], possibly because those speakers rely more on lexico-semantic information to process their native language. It thus seems that these violations with HAD were not perceived as subjectively salient events but as lexical violations.

These results suggest that when the processed structure does not exist in the L1, other cues such as the phonological salience of the violation are used to process morphosyntactic violations. These findings also have theoretical relevance since they strongly support the P600-as-P3 hypothesis.

Figure 1 .

 1 Figure 1. Difference wave (Incorrect -Correct) for each Auxiliary at Pz.

intermediate French learners of English (5 male, aged 18.5 ± 1) took part in the experiment. They were first year University students of English having spent less than a month in an English-speaking country.

Acknowledgements

This research was supported by an IUF grant awarded to Dr. Emmanuel Ferragne.