Julien Allali
email: allali@labri.fr

Marie-France Sagot

A multiple layer model to compare RNA secondary structures

Keywords: graph layers, graph comparison, edit distance, RNA, secondary structure

We formally introduce a new data structure, called MiGaL for "Multiple Graph Layers", that is composed of various graphs linked together by relations of abstraction/refinement. The new structure is useful for representing information that can be described at different levels of abstraction, each level corresponding to a graph. We then propose an algorithm for comparing two MiGaLs. The algorithm performs a step-by-step comparison starting with the most "abstract" level. The result of the comparison at a given step is communicated to the next step using a special colouring scheme. MiGaLs represent a very natural model for comparing RNA secondary structures that may be seen at different levels of detail, going from the sequence of nucleotides, single or paired with another to participate in a helix, to the network of multiple loops that is believed to represent the most conserved part of RNAs having similar function. We therefore show how to use MiGaLs to very efficiently compare two RNAs of any size at different levels of detail.

Introduction

We formally introduce in this paper a new data structure, called MiGaL for "Multiple Graph Layers", that is composed of various graphs linked together by relations of abstraction/refinement. The structure is useful for representing information that can be described at different levels of abstraction, each level corresponding to a graph. Similar structures have already been used for modelling a spatial environment [START_REF] Fernandez | Hierarchical graph search for mobile robot path planning[END_REF][START_REF] Fernández-Madrigal | Multihierarchical graph search[END_REF][START_REF] Galindo | Improving efficiency in mobile robot task planning through world abstraction[END_REF] or plant architectures [START_REF] Ferraro | An edit distance between quotiented trees[END_REF][START_REF] Godin | A multiscale model of plant topological structures[END_REF]. They could also be used for analysing web pages or source codes. The MiGaL structure is more general than [START_REF] Ferraro | An edit distance between quotiented trees[END_REF][START_REF] Godin | A multiscale model of plant topological structures[END_REF] as it can model graphs besides trees. It is different from [START_REF] Fernandez | Hierarchical graph search for mobile robot path planning[END_REF][START_REF] Fernández-Madrigal | Multihierarchical graph search[END_REF][START_REF] Remolina | Formalizing regions in the spatial semantic hierarchy: An AH-graphs implementation approach[END_REF][START_REF] Galindo | Improving efficiency in mobile robot task planning through world abstraction[END_REF] (neither more general, nor a special case) as we detail in Section 2.

After giving a formal presentation of the MiGaL structure, we propose an algorithm for comparing two MiGaLs. The algorithm performs a step-by-step comparison starting with the most "abstract" level. The result of the comparison at a given step is communicated to the next step using a special colouring scheme.

We then present an application of MiGaL to the analysis of RNA secondary structures. RNAs have different functions in a cell that are strongly related to the spatial fold adopted by the molecule. It is therefore meaningful to compare such folds in order to infer or understand function. For RNAs, the comparison is usually done by considering the secondary structure which, in the case of RNAs, provides a planar view of the fold. A secondary structure may be seen at different levels of detail, going from the sequence of nucleotides, single or paired with another to participate in a helix, to the network of multiple loops that is believed to correspond to the most conserved part of RNAs having similar function.

MiGaLs represent therefore a natural way of modelling such secondary structures. To perform the comparison at each different level, an edit distance algorithm is applied to trees that are rooted and ordered (reflecting the orientation of the RNA molecule). We use for this the algorithm particularly adapted to RNAs that was introduced in a recent work by Allali et al. [START_REF] Allali | A new distance for high level rna secondary structure comparison[END_REF]. In this paper, we indicate how to optimise it using the colouring scheme of the algorithm for comparing two MiGaLs introduced earlier in the paper in order to compare RNAs at different levels of detail. We show that our method leads to quite satisfying results when applied to the analysis of RNA secondary structures. Indeed, the new method addresses the scattering effect problem mentioned in the literature [START_REF] Allali | A new distance for high level rna secondary structure comparison[END_REF] (briefly, this corresponds to a wrong mapping between structurally unrelated parts) while the divide strategy used as the different levels are considered in turn allows to very efficiently compare RNAs of any size. These results are detailed and extensively discussed in the last section. They are in particular compared, in terms of both computation time and biological meaning, to the results obtained with a classical RNA secondary structure comparison algorithm due to Zhang and Shasha [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF]. Concerning the latter, our method is an improvement in the sense that it eliminates the scattering effect, therefore leading to a better matching of two input RNAs. Concerning computation time, we demonstrate that our method is efficient enough to allow the comparison of even large sized structures, something not possible with, for instance, Zhang and Shasha's algorithm or, to the best of our knowledge, with other currently available methods.

Finally, we show that the distances between pairs of RNA secondary structures calculated by the algorithm presented in this paper can be used to obtain phylogenetic trees for the RNAs that are as accurate as the trees derived by a combination of automatic inference using other methods and manual expertise.

Multiple Graph Layers

We present in this section the MiGaL data structure. After a formal definition, we provide an algorithm to compare such structures.

Definition

From now on, we adopt the following notations. Given a set S, we denote by |S| its cardinality. Let G(V, E) be a graph with vertex set

V (G) = {v 1 , . . . , v |V (G)| } and edge set E(G) = {e 1 , . . . , e |E(G)| }.
We start by defining the new data structure. It can be described as a layered sequence of graphs, with each graph linked to its neighbours by two applications, one of which corresponds to an abstraction from the previous graph, the other to a refinement leading to the next graph. The formal definition of the MultIGrAphLayers data structure is as follows.

Definition 1 (Definition of a M iGaL) A M iGaL structure M (G, R) of size |M | is defined as a layered sequence G = G 1 , . . . , G |M| of |M | graphs and a sequence R = α 1 , . . . , α |M|-1 of |M | -1 applications called refinements. Each refinement α i is an application from V (G i ) to P(V (G i+1 )), that is, each vertex in V (G i ) has a subset of V (G i+1
) as image. The inverse application of α i , denoted by β i , is a surjection called an abstraction that maps every vertex in V (G i+1 ) to a vertex of V (G i ). In addition, M (G, R) satisfies the following two conditions:

1. For each vertex v ∈ V (G i ), the subgraph induced by α i (v) is connected and not empty. 2. For each edge (u, v) ∈ E(G i ), there exists at least one vertex of α i (u) connected to a vertex of α i (v).

Figure 1 illustrates this definition. From now on, we refer to the first graph of a MiGaL as the top graph and to the last one as the bottom graph. Note that there are no restrictions on the type of graphs that define a MiGaL structure. The comparison algorithm we provide later is therefore as general as possible.

This structure is clearly useful to encode data at different levels of detail. A comparable data structure called a Hierarchical Graph (denoted by H-Graph) has been used in [START_REF] Fernandez | Hierarchical graph search for mobile robot path planning[END_REF][START_REF] Fernández-Madrigal | Multihierarchical graph search[END_REF][START_REF] Remolina | Formalizing regions in the spatial semantic hierarchy: An AH-graphs implementation approach[END_REF][START_REF] Galindo | Improving efficiency in mobile robot task planning through world abstraction[END_REF] to represent the environment (towns, buildings, rooms, . . . ) and drive robots in space. Godin et al. in [START_REF] Godin | A multiscale model of plant topological structures[END_REF][START_REF] Ferraro | An edit distance between quotiented trees[END_REF] use a similar structure, that they call quotiented trees, to model and study plants. Compared to the latter, MiGaLs can represent graphs and not just trees. Contrary to H-Graphs, MiGaLs can, in a given layer, connect vertices that are linked, through the abstraction function β, to vertices that are unconnected in an upper layer. This is illustrated in Figure 1 by the arrow in layer 3 that links two vertices which correspond in layer 2 to the (abstracted) vertices A and B that are unconnected. This property of MiGaLs is justified later in the context of RNA secondary structures where it allows to take into account so-called pseudo-knots. MiGaLs and H-Graphs differ also in that, in MiGaL, each vertex (except in the last layer) necessarily has an image by the refinement and is itself (unless it is part of the first layer), by abstraction, the image of a vertex. This is not required in H-Graphs. MiGaLs is therefore neither a generalisation nor a special case of H-Graphs. The two structures are different. Although MiGaLs, and doubtless H-Graphs, can have many applications, the MiGaL structure is particularly adapted to comparing RNAs.

Top-Down comparison algorithm

In this section, we present an algorithm to compare two MiGaLs. The algorithm performs a top-down traversal of the structure. We assume both MiGaLs have the same number of layers, and compare them layer by layer starting with the graph at the top. The result of the comparison at a given layer is transmitted to the next layer by colouring vertices and edges of the graph and using the refinement application. We then compare the two graphs of the next layer taking into account such colouring. The process continues until the last layer is reached (bottom graph).

This approach assumes the existence of an algorithm allowing to compare two graphs of a same layer. This algorithm clearly depends on the data that is modelled using a MiGaL. In what follows, we consider a black box that is able to produce an extended mapping between two graphs where by an extended mapping is meant the following: Definition 2 (Extended mapping) Given two graphs G 1 and G 2 , we define an extended mapping M between them as a set of couples of vertex sets of the two graphs:

M = {(S 1 , S 2 )|S 1 ⊂ V (G 1 ) and S 2 ⊂ V (G 2 )} such that for all (S 1 , S 2 ), (S ′ 1 , S ′ 2 ) ∈ M: • S 1 is a connected component of G 1 • S 2 is a connected component of G 2 • (S 1 , S 2 ) = (S ′ 1 , S ′ 2 ) or S 1 ∩ S ′ 1 = ∅ and S 2 ∩ S ′ 2 = ∅
We define a colour-partitioned graph G with vertex set V (G) as a graph fitted with an application C G : S ⊂ V (G) → N + which gives a colour to each vertex of S ⊂ V (G) such that subgraphs defined by vertices of the same colour are connected. For convenience, uncoloured vertices are given the colour 0. The vertices with colour 0 are therefore elements of V (G) \ S.

We now extend the definition of an extended mapping to colour-partitioned graphs as follows. Definition 3 (Colour-constrained extended mapping) Given two colour-partitioned graphs G 1 and G 2 , a colour constrained extended mapping M between them is defined as an extended mapping which further satisfies the following conditions:

• ∀(S 1 , S 2 ) ∈ M, every vertex of S 1 has the same colour c and every vertex of S 2 also has this colour c. • There is no vertex of G 1 or G 2 coloured with 0 that is involved in M. Now that we have defined a mapping on colour-partitioned graphs, we give a general algorithm for comparing two MiGaLs, M (G, R) and M ′ (G ′ , R ′ ), having the same number

Compare(M (G, R), M ′ (G ′ , R ′ )) 1. colour = 2 2.
Set all vertices of G1 and G ′ 1 to 1.

3.

for each layer i from 1 to |M |

4. M = B(Gi, G ′ i ) 5.
set the color of V (Gi+1) and

V ′ (G ′ i+1 ) to 0 6.
for each couple of sets (u, v) in M

7.

for all nodes n in u 8.

set the colour of nodes in α(n) to colour

9.
for all nodes m in v 10.

set the colour of nodes in α ′ (m) to colour of layers. This number is denoted by

|M | = |M ′ |.
The algorithm assumes again that we have a black box B that computes a colour-constrained mapping between two colour-partitioned graphs.

The initialisation step colours the vertices of G 1 and G ′ 1 with 1. The algorithm is then divided into |M | steps. For each layer i from 1 to |M |, we compute the mapping M i between G i and G ′ i using B and (except for the last step) colour the vertices of G i+1 and G ′ i+1 such that vertices associated by the mapping have the same colour and vertices absent from M i are coloured with 0. The result of the algorithm is the set of all mappings between each pair of layers.

The pseudo-code of this algorithm is shown in Figure 2. Let b be the time complexity of algorithm B; the time required to compare two MiGaLs of size

n is O(n * b * |V (G n )|).
It is important to notice that the main idea of this algorithm is to compute mappings from the top to the bottom layer. Each layer is compared using the mapping of the previous one without reconsidering the choices implied by this mapping.

We now present a practical application of the MiGaL structure and of the comparison algorithm to the study of RNA secondary structures. In particular, we show how to significantly improve the runtime of algorithm B by taking advantage of the node-colouring.

RNA-MiGaL

RNAs are one of the most important molecules in a cell. They are composed by a succession of nucleotides, also called bases and denoted by A, C, G and U. Inside a cell, RNAs do not keep a linear form but instead fold in space. The fold is given by the set of interactions between nucleotides. An RNA can be described at three different levels, respectively called its primary, secondary and tertiary structures. The primary structure refers to the sequence of nucleotides. The secondary structure is composed of the list of base pairs that participate in a helix (see below). The tertiary structure corresponds to all interactions (base pairings) in the RNA, that is, to its fold in space.

The function of an RNA (be it the well known ribosomal and transfert RNAs or the more recently discovered snoRNAs, microRNAs, etc.) is strongly linked to the shape adopted by the RNA in space. It is generally accepted that two RNAs that have the same function will often have closely similar secondary structures but not necessarily similar primary structures. Considering this, it is fundamental to have efficient algorithms to compare RNAs from the point of view of their secondary structures.

Various structural elements can be distinguished in the secondary structure of an RNA (see Figure 3): helices which correspond to consecutive base pairs, hairpin-loops which are unpaired bases at the end of an helix, internal-loops defined by the unpaired bases between two helices and called bulges when one side is empty, multi-loops which are the meeting point of at least three helices and, finally, stems that are series of helices, internal-loops and bulges. Another element comsidered by some as being part of the secondary structure of an RNA, and by other authors as part of its tertiary structure, is the so-called pseudo-knot (see Figure 4). A pseudoknot is a structural element containing two stem-loop structures in which the first stem's loop forms part of the second stem. In this paper, we do not take pseudo-knots into account.

Many approaches have been used for modelling secondary structures. Mainly, three codings have been proposed to represent RNA secondary structures: rooted ordered trees [START_REF] Zuker | RNA secondary structures and their prediction[END_REF]; arc annotated sequences [START_REF] Evans | Finding common subsequence with arcs and pseudoknots[END_REF]; 2-intervals [START_REF] Vialette | Pattern matching problems over 2-interval sets[END_REF].

Since our purpose in this paper is to illustrate the interest of using a multiple layer model for RNAs, we focus on tree models. We thus represent secondary structures by rooted ordered trees. The root corresponds to the beginning and the end of the molecule. The order between the children of a node corresponds to the orientation of the sequence. In fact, we can use different tree models depending on the information we want to encode. In [START_REF] Zuker | RNA secondary structures and their prediction[END_REF], Zuker and Sankoff use trees where internal nodes code for base pairs and leaves code for free nucleotides. This tree can be compacted [START_REF] Fontana | Statistics of RNA secondary structures[END_REF] into a homeomorphically irreductible tree where internal nodes correspond to helices and leaves correspond to fragments of unpaired bases. Shapiro in [START_REF] Shapiro | An algorithm for multiple RNA secondary structures[END_REF] uses a tree where edges code for helices and nodes are labelled on {M, B, I, H, R} (multi-loop, budge, internal-loop, hairpin-loop and the root). We can also use a more abstract tree where edges code for stems and nodes for multi-loops and hairpin-loops, or just for multi-loops.

To compare rooted ordered trees, there exist essentially two methods. The first is edit distance [START_REF] Tai | The tree-to-tree correction problem[END_REF] based on three edit operations. A substitution changes the label of a node. A deletion removes a node of the tree, its children are then re-attached to the node's father preserving the relative order between nodes. An insertion is the opposite operation of a deletion. If we assign a score to each of these operations, we can define the edit distance between two trees as the minimum of the score of a series of edit operations (sum of the score of each operation) that transforms the first tree into the second one. Recently, Allali et al. [START_REF] Allali | A new distance for high level rna secondary structure comparison[END_REF] extended this distance by introducing four new operations: node fusion, edge fusion and the opposite operations of node split and edge split. These operations allow to address some of the limitations of the classical edit distance when comparing RNA secondary structures using high level trees (where nodes and edges code for secondary structure elements, not for nucleotides).

The complexity of the classical edit distance algorithm provided by Zhang and Shasha [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF] is

O(|T | * min(leaf (T ), height(T )) * |T ′ | * min(leaf (T ′ ), height(T ′ )))
where leaf (T ) is the number of leaves in the tree T and height(T ) is its height. In the worst case (fan tree), the complexity

is in O(|T | 2 * |T ′ | 2 )
. In [START_REF] Klein | Computing the edit-distance between unrooted ordered trees[END_REF], Klein gave an O(n 3 log n) algorithm to compute this distance where n is the size of the trees. The complexity of the edit distance with fusion operations [START_REF] Allali | A new distance for high level rna secondary structure comparison[END_REF] is

O((2d) l * |T | * min(leaf (T ), height(T )) * (2d ′ ) l * |T ′ | * min(leaf (T ′ ), height(T ′ )))
where d is the degree of T and l the maximum number of consecutive fusions per node.

The second method for comparing rooted ordered trees is by performing a tree alignment [START_REF] Höchsmann | Local similarity in RNA secondary structures[END_REF][START_REF] Jiang | Alignment of trees -an alternative to tree edit[END_REF]. In this case, the goal is to insert blank labelled nodes in the two trees such that they become isomorphic. The score of the alignment corresponds to the sum of the scores of the association of node labels (the blank character assumes the role of an insertion or a deletion in a sequence alignment). The optimal score, maximal or minimal depending on the scoring scheme adopted, is then sought. A tree alignment can be expressed as an edit distance computation where insertions must precede all deletions. We do not give further details here on alignments as we only use edit distance later in the paper.

We now suggest a new modelling of RNA secondary structures based on the MiGaL data structure introduced earlier in the paper. We thus call RNA-MiGaL a MiGaL structure composed by four layers, each modelled by a rooted ordered and labelled tree. In [START_REF] Giegerich | Abstract shapes of RNA[END_REF][START_REF] Reeder | Consensus shapes: an alternative to the sankoff algorithm for RNA consensus structure prediction[END_REF], Giegerich et al. introduced the concept of the abstract shapes of an RNA secondary structure that is related to our layers. Their shapes however are less detailed, the general structure of the elements only is preserved, and any information of size is discarded.

The next section is dedicated to a description of RNA-MiGaL.

The four layers definition

The four layers contained in an RNA-MiGaL correspond to the secondary structure of an RNA observed at different levels of detail. Thus, each layer is modelled by a rooted ordered labelled tree. In the bottom layer, nodes and leaves code for nucleotides while the top layer encodes the network of multi-loops of an RNA. This choice has been dictated by two assumptions. The first, already mentioned, is that structure is more important than sequence. Thus we introduce information concerning the nucleotide sequence at the bottom layer only. This is the layer that will be treated last by the comparison algorithm. The second is that the network of multi-loops can be considered as the skeleton of the secondary structure of an RNA. RNAs of the same family should thus have strongly conserved multi-loop networks. For this reason, the top layer of an RNA-MiGaL is a tree that codes for the multi-loop network. Intermediate layers correspond to the structure encoded using stems or helices. We provide below a summary of the layers and of the meaning of a node and a leaf in each layer:

• The tree of layer 1 corresponds to the multi-loop network. The nodes encode multi-loops and the edges encode stems. In the nodes, we store the number of helices connected by the multi-loop. In the edges, we store the number of nucleotides contained in the stem. • Layer 2 consists in the structure defined by the stems. The internal nodes represent multi-loops, leaves represent hairpin-loops and edges encode stems. In the edges, we store the number of base pairs and the number of unpaired bases contained in the stem.

In the internal nodes and leaves, we store the number of unpaired bases contained in the multi-loops and hairpin-loops. • The tree of layer 3 encodes secondary structure elements: nodes encode hairpin-loops, multi-loops, internal-loops and bulges and store the number of unpaired bases of the corresponding element. The edges represent helices and store the number of base pairs of the helices. • The last tree models the RNA primary structure. The internal nodes thus represent base pairs and leaves unpaired bases. Both store the names of the corresponding bases.

All the numerical values stored in the nodes and edges of the first three layers are floating numbers.

The abstractions β 0,1,2 of the MiGaL model encode the natural inclusion between structural elements. Abstraction β 2 maps the nucleotides of layer 3 to the helices and loops of layer 2. Abstraction β 1 maps helices, internal loops and bulges to the stems of layer 1, while multi-loops and hairpin-loops are mapped to their corresponding loops in layer 1. Finally, abstraction β 0 associates the multi-loops and connected stem-hairpin-loops of layer 1 to the multi-loops of layer 0, while the stems between two multi-loops in layer 1 are mapped to a same stem of layer 0.

RNA-MiGaL comparison

The problem now is to compare two secondary structures using RNA-MiGaLs. To do so, we use edit distance with fusions and the algorithm described in [START_REF] Allali | A new distance for high level rna secondary structure comparison[END_REF] to compare the pairs of trees of layers 1, 2 and 3. To take into account the colour of the nodes and edges, we just have to test if two nodes or edges have the same colour to allow them to be fusioned (in a tree) or substituted (between the trees). The trees of layer 4 are compared using the classical edit distance (no fusions). Similarly, only nodes of a same colour in layer 4 can be mapped to each other. It may be interesting in the future to have operations which allow to pair two unpaired bases, or to separate a base pair into two unpaired bases. Such operations have been defined in [START_REF] Lin | Edit distance between two RNA structures[END_REF] but Blin et al. proved in [START_REF] Blin | RNA sequences and the edit(nested,nested) problem[END_REF] that the computation of the edit distance between two trees allowing for these operations is NP-Complete. Figures 6 and7 show the result of the comparison using RNA-MiGaLs between two Group I Intron RNAs retrieved from [START_REF] Cannone | The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs[END_REF]. The left RNA is found in Acanthamoeba griffini and the right one in Chlorella sorokiniana.

The time complexity required to compare two trees of a same layer is O((2d) l n 4 ) for the first 3 layers and O(n 4 ) for the last layer with n being the size of the trees. Since we colour nodes while we progress in the comparison, and, once trees are coloured, substitutions and fusions can only be performed on nodes of same colour, we may wonder if it is not possible to compare separately the subtrees defined by each colour. The response is positive but it requires some attention as is shown in the following example. Figure 8 presents on the top left a colour-partitioned tree, with white corresponding to colour 0. In the box, we have split each tree into subtrees according to their colour and computed the edit distance between these trees separately. The nodes associated by the mapping are linked by dashed lines. We have then reported the result of the computations on the original trees. The problem is pointed to by the bold dashed lines in the tree at the bottom. We have two couples of nodes associated via two different computations. Inside each computation, the relative order of the nodes is respected by the edition (we work on ordered trees). However, in the final tree, the associations do not respect the order between the nodes.

We therefore have to modify the algorithm to take into account the presence of a subtree of a given colour x hanging from an edge of a subtree of colour y = x. To do so, we introduce anchors during the splitting step. When we split trees into subtrees according to their colour, we add anchors to the subtrees. These anchors represent the subtrees of another colour that hang from an edge of the subtree being considered as shown in Figure 9. The anchors have the same colour as the subtrees they stand for. We then have to modify the edit distance scoring scheme such that:

• deleting the anchor of colour c costs the deletion of the subtree corresponding to the anchor; • an anchor of colour c can only match with an anchor of the same colour.

Finally, we order the edit computations according to the dependence implied by the colouring scheme, that is, we consider the subtree from the leaves to the root. We can now rewrite the time and space complexity required to compare two trees of a given layer as the sum of the time required to compare each subtree. In the extreme, if we split the trees of size n into n subtrees of one node, then the time required to compare the trees becomes linear!

In the worst-case, the time complexity is still 0((2d) l × n 4 ) for each level but in the case of RNAs, on average, the tree at each layer contains a number of subtrees that is proportional to the size of the tree, and the observed time complexity is close to linear except for the first layer.

Experimental results

We implemented the algorithm for comparing two RNA secondary structures inside a package called MiGaL which runs on the GNU/Linux platform. It is available for download at http://igm.univ-mlv.fr/˜allali/. The code is written in C++. We provide in this section three series of tests done on a PC with a single 1.6GHz processor Intel Pentium M with 1Gb of RAM memory under Debian GNU/Linux. Three series of tests were performed. They are described in what follows.

Time to compare two RNA secondary structures

The first series of tests we ran aimed at evaluating the time required to compare two RNA secondary structures on four different data sets. Figure 10 shows the results observed with two algorithms. The first is the classical Zhang and Shasha algorithm [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF], that we denote by zs, applied to the bottom tree of rna-migal. The second, denoted by rna-migal, is our comparison algorithm with anchors optimisation. Both algorithms were applied using cost functions defined on reals (that is, on float numbers).

It is important to observe that, since the same algorithm is used to compare different trees given as input, each one having also different kinds of nodes, there may be some time lost [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF] algorithm on the tree corresponding to the bottom layer of RNA-MiGaL. The second (rna-migal) is the algorithm for comparing two MiGaLs using the anchors optimisation. The times indicated for the two algorithms are, respectively, the minimum/maximum/average times in seconds.

In the case of our method, the times shown (without and with anchors optimisation) take into account the time required for loading the RNAs and for building the corresponding MiGaL structures. The number of comparisons used to obtain these execution times appears in parenthesis in the first column.

because of genericity. Indeed, it is possible to improve the performance of the Zhang and Shasha's algorithm by using constant cost functions and a dedicated implementation. In the same way, it is possible to improve our RNA-MiGaL algorithm by using a specific source code for each layer. The first row of Figure 10 results from the 21 pairwise comparisons made on seven RNAsePs extracted from the RNAseP database [START_REF] Brown | The ribonuclease p database[END_REF]. Such RNAs are small, around 350 nucleotides. Their multi-loop networks are quite simple. The top layer tree corresponds therefore to very small trees, having from three to six nodes with a degree bounded by one (the trees are in fact paths).

As second example (second row), we considered nine Group I introns from the Comparative RNA database [START_REF] Cannone | The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs[END_REF] to which we applied all possible pairwise comparisons. The smallest Group I intron has 430 nucleotides, the longest, which contains a long unfolded part of 420 nucleotides, has 1032 nucleotides. The multi-loop networks of such RNAs lead to trees of 4-5 nodes with a degree bounded by two.

The results in the third row of Figure 10 come from the comparison of fourteen 16S-RNAs extracted also from the Comparative RNA database. Their lengths range from 1496 to 2291 nucleotides. The multi-loop networks are bigger than for the two previous examples. They correspond to trees of 19 nodes with a degree bounded by two.

Finally, the last row of Figure 10 shows the results of the comparison of six 23S-RNAs which come again from the Comparative RNA database. Their lengths go from 2928 to 3555 nucleotides. Such RNAs contain from 47 to 73 multi-loops. The top layer trees have therefore between 47 and 73 nodes with a degree bounded by 11. In this case, we were not able to use zs as the computations led to a stack overflow. Indeed, the top layer contains less than one hundred nodes which is manageable by our edit-distance-with-fusions algorithm while the bottom layer contains more than two thousand nodes which is hardly manageable by an O(n 4 ) algorithm.

As we can see, rna-migal is very performing and allows to compare large RNAs in a short time thanks to the colouring scheme and the tree splitting optimisation. In fact, the time within their respective groups, data not shown. Figure 11 shows the scoring matrix computed while Figure 12 represents the tree built using drawtree from the PHYLIP package [START_REF] Felsenstein | Phylip (phylogeny inference package) version 3.6[END_REF]. The tree indicates that plants, mammals, bacteria and archea are correctly grouped together. This test is, of course, preliminary. We are currently applying our method to infer phylogenetic trees for closely related species as such represent a better test of the accuracy of RNA-MiGaL. Indeed, in this case using the sequences often leads to wrong results.

The matrix in Figure 13 shows the scores obtained by the classical edit distance algorithm of Zhang and Shasha applied to the same eight 16S-RNAs. The scoring scheme used to compute the distances is also exactly the same as the one used to compute the matrix in Figure 11. The differences between the two sets of scores result therefore only from the constraint of locality (colour) brought from the upper layers of the MiGaL structure to the bottom one. The values z in the matrix obtained with the classical edit distance are distant from the corresponding ones, denoted by m, obtained with rna-migal by at most 10% in all cases (that is, m ≤ 1.1 * z) except five where the distance is between 10 and 15% (4 of the 5 cases), or is of 21% (last case). The resulting trees are isomorphic. The new rna-migal approach leads therefore in this case to essentially equivalent results in a much faster way.

Addressing the scattering effect problem

The last test we show gives an example where rna-migal can significantly improve the results of the comparison.

For this test, we ran zs and rna-migal on the RNAs used as illustrations in [START_REF] Allali | A new distance for high level rna secondary structure comparison[END_REF]. In this paper, the authors point out a common problem when comparing RNA secondary structures using previous methods, the so-called scattering effect. This problem corresponds to base pairs that are mapped to one another (through a substitution of their labels) although they belong to structurally unrelated regions. In Figure 14, we surrounded two such wrong substitutions. These two wrong mappings are chosen by a classical edit distance algorithm because they cost less than performing deletions. The result with rna-migal is shown in Figure 15. We surrounded the regions affected by the constraint of locality brought by the first-to-last layer comparison. We can see that the previous wrong mapping can not be made anymore because the corresponding bases do not belong to the same secondary structure elements.

Conclusion

We introduced in this paper a new data structure and an algorithm for comparing such structures. Both are generic and may be applied to very different types of problems. They are particularly interesting for comparing objects that may be described at different levels of abstraction.

RNA secondary structures are one example of such objects and we therefore showed how to optimise the generic algorithm, in particular its special colouring scheme for going from one level of abstraction to the next, to compare two RNA secondary structures. The results obtained are very satisfying. In particular, the algorithm addresses the so-called scattering effect described in the literature [START_REF] Allali | A new distance for high level rna secondary structure comparison[END_REF]. The new algorithm allows to compare large sized structures in a much faster manner while the multiple layer approach represents a biologically very natural way of modelling and analysing RNAs.

The current implementation of rna-migal does not allow to deal with pseudo-knots. We plan to introduce this possibility at the second layer from the top. Pseudo-knots correspond to edges between two secondary structure elements. Adding such nodes is possible because we allow the introduction of an edge between nodes of which the abstractions in the upper layer are unconnected. The fact that pseudo-knots are not considered yet in rna-migal is therefore a limitation of the current implementation, not of the MiGaL structure.

Algorithms working with hierarchical structures in general often consider as part of the algorithm to optimise the number of levels in the hierarchy instead of working with a fixed number as is done in rna-migal. In the case of RNAs, we are not sure optimising the number of levels would lead to a biologically realistic model. This could, however, be worth checking. The number of levels considered may also be questioned. For example, in [START_REF] Ouangraoua | Local similarity between quotiented ordered trees[END_REF], the authors used a hierarchy with two layers only, which correspond to our two last. In particular, it might be interesting to explore what happens with a model that skips the first layer.

Figure 1 .

 1 Figure 1. Example of a M iGaL structure of size three defined by three graphs and two refinements.

11 .Figure 2 .

 112 Figure 2. Algorithm for the comparison of two MiGaL structures using an external algorithm B that computes a colour-constrained mapping between two colour-partitioned graphs.

Figure 3 .

 3 Figure 3. RNA Secondary Structure: the dots represent the nucleotides (bases) of the RNA. Helices correspond to consecutive base pairs, hairpin-loops are indicated by A, internal-loops by B, bulges by C and multi-loops by D. Stems are surrounded.

Figure 4 .

 4 Figure 4. Example of pseudo-knot (picture from wikipedia)

Figure 5 .

 5 Figure 5. Classical edit distance vs edit distance with fusions on rooted ordered labelled (on nodes and edges) trees. In the first line, the tree A is edited by the edge fusion of a -3 with ba -1. Then the node 6 is split with a node split operation and node 2 is changed into 1. The second line shows how to edit A into B with the classical edit distance. First, c -3 and a -3 are deleted and ba -1 is substituted by aba -1. Then, node b -2 is inserted and 6 and 2 are substituted by 4 and 1.

Figure 6 .

 6 Figure 6. Result of the comparison of two Group I Introns. On the left, the result of the comparison of the trees of layer 1; on the right, the result of the comparison of the trees of layer 2.

Figure 7 .

 7 Figure 7. Result of the comparison of two Group I Introns. On the top, the comparison of the trees of layer 3; on the bottom, the result of the comparison of the trees of layer 4.

Figure 8 .

 8 Figure 8. Potential problem when splitting a tree according to colour to optimise an edit computation.

Figure 9 .

 9 Figure 9. Splitting the left tree into subtrees according to the colours of the nodes and the addition of anchors (represented by triangles).

Figure 14 .

 14 Figure 14. Result of the comparison of two RNAseP (of Streptococcus gordonii (left) and Thermotoga maritima) extracted from [3] using the classical edit distance of Zhang and Shasha. An example of scattering effect corresponds to the surrounded substitutions.

Figure 15 .

 15 Figure 15. Result of the comparison of the RNAs of Figure 14 using rna-migal. The effect of the constraints of locality brought by the first-to-last layer comparisons are shown by the surrounded regions.

  Figure 10. Computation time for comparing different kinds of RNA secondary structures using two algorithms. The first algorithm (zs) is the classical edit distance between two RNAs using Zhang and Shasha's

	RNAs	Size	zs	rna-migal
	RNAseP (21)	345.4	0.48 / 1.26 / 0.78	0.05 / 0.12 / 0.07
	GroupI (36)	541.7	0.68 / 4.65 / 1.62	0.1 / 0.67 / 0.22
	16S (91)	1744.8	36.25 / 128.1 / 62.93	0.34 / 0.94 / 0.51
	23S (15)	2721.52	-6.23 / 321.63 / 107.85

Copyright c 2006 John Wiley & Sons, Ltd. Softw. Pract. Exper. 2006; 1:1-1 Prepared using speauth.cls

Acknowledgements

We would like to thank Claude Thermes and Yves d'Aubenton-Carafa for their help all along the development of MiGaL.

required by rna-migal to compare two RNAs is roughly the same as the time required to compare the first layers of the MiGaL structures. The time complexity of the edit-distancewith-fusions algorithm depends strongly on the degree of the input trees. This explains why it takes so long to compare the 23S-RNAs in relation to the other RNAs: the huge central multi-loop with many branching helices leads to a high node degree in the top layer tree.

Using MiGaL to build phylogenetic trees

The second test we performed consisted in comparing eight of the 14 16S-RNAs from the Comparative RNA database and in using the scores of the edit computations on the bottom layers of the MiGaL structures to build a phylogenetic tree using the neighbour joining algorithm implementation of quicktree [START_REF] Howe | Quicktree: building huge neighbour-joining trees of protein sequences[END_REF]. For the purposes of the illustration, two RNAs only were chosen for each of the four main evolutionary groups present in the data, archea, bacteria, mammals and plants. The remaining 6 RNAs were well classified by the method Result of the application of quicktree [START_REF] Howe | Quicktree: building huge neighbour-joining trees of protein sequences[END_REF] to compute the tree corresponding to the matrix given in Figure 11 (neighbour-joining method). Trees were drawn with the drawtree PHYLIP program [START_REF] Felsenstein | Phylip (phylogeny inference package) version 3.6[END_REF], the left one is without edge length.


Alexandre Audinot

Diane Dewez

Gwendal Fouché

Rebecca Fribourg

Thomas Howard

Flavien Lécuyer

Tiffany Luong

Victor Mercado

Adrien Reuzeau

Thomas Rinnert

Guillaume Vailland

Ferran Argelaguet

3Dexterity: Finding your place in a 3-armed world

à 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.

INTRODUCTION

In the presented virtual reality experience, users (having two arms) inhabit a world in which humans have evolved to have three arms (see Figure 1). As such, users will encounter difficulties to interact with their environment due to the differences between their own body (only two arms) and the "standard" three-armed body that makes up the norm in this fictional world. In this experience, the world and tools are designed for people with three arms which puts users in an uncomfortable context. The experience is divided in three phases. In the first phase of the experience, users will have to approach the world and attempt to achieve tasks designed for tri-manual control using only their two arms. The goal is to show frustration, inconvenience as well as giving users a feeling of inadequacy and social exclusion. Furthermore, it reflects everyday challenges that face people with physical disabilities in daily tasks and tools designed for people with a wider range of physical capabilities. In the second phase, users are given a third arm prosthesis intended to compensate for their handicap, thus recovering some level of autonomy in interaction with their environment. However, the prosthesis is both imperfect and complex to master, highlighting real-world issues with current prosthetic solutions for people with disabilities. In the third phase, users can perform the same interactions as in the first phase but using the prosthesis to achieve them.

CONTROLLING A THIRD ARM

In this demonstration, users will need to control a third arm prosthesis. In the literature, there exist a number of works that have already explored and evaluated the control of additional arms. For example, in a virtual reality context, Laha et al. [START_REF] Laha | Evaluating control schemes for the third arm of an avatar[END_REF] proposed and evaluated three different methods to control a third arm (bimanual, unimanual, and head-control). Another interesting example is the work from Steptoe et al. [START_REF] Steptoe | Human tails: Ownership and control of extended humanoid avatars[END_REF] which studied embodiment within an avatar having a tail (hip control). Finally, in a real-world context, Saraiji et al. [START_REF] Saraiji | Metaarms: Body remapping using feet-controlled artificial arms[END_REF] proposed a robotic system composed of two robotic arms attached to users' back and controlled thanks to the feet and the knees. Parietti et al. [START_REF] Parietti | Supernumerary robotic limbs for aircraft fuselage assembly: body stabilization and guidance by bracing[END_REF] propose a similar robotic system with a different approach to control, where the robot autonomously adjusts its state based on interaction positions and forces and a model of the task. From the different examples in the literature, direct control of additional limbs through coupling with a user's head, limbs, hips or individual muscle's state appears to be the most used method. In this experience we propose two different control mechanisms: a novel command-based control and a continuous control.

Command-based Control

In the discrete control mode, users' gaze is used to define interaction targets for the third arm. Then, users can issue voice commands to trigger specific actions with the gaze-designated target. Initially, the third arm prosthesis is in an "inactive"/"idle" state. By saying "activate", users switch on the prosthesis, putting it into an "activewaiting" state where targets can be designated using the gaze and actions can be triggered. Users then have the choice between several actions: "go" (extends the arm towards the target), "back" (retracts the arm), "push" (pushes against the target), "grasp" (grasps the target) and "release" (releases a grasped object). Once an action is triggered, the prosthesis switches into an "active-doing" state where no further action can be triggered. Upon action completion, the prosthesis returns into the "active-waiting" state. The key advantages of this control mode lie in the fact that both users' hands are free for simultaneous interaction with the environment. However, this control scheme can become limited for complex movements and interactions not initially planned.

Continuous Control

Users can switch to a continuous control mode for the arm by using a dedicated voice command. In this mode, users hold down the trigger in their left or right hand to designate that hand as a guide for the prosthesis. This allows users to "drag" the third arm prosthesis to a desired position or through a desired sequence of movements. This control mode provides an intuitive way to move the prosthesis while also providing great freedom of movement and interactions. However, one of users' hands is always occupied by the prosthesis' control during the movement phase, hindering some movement combinations.

DEMO APPARATUS

The experience uses a HTC Vive Pro Eye virtual reality headset, which integrates Tobii eye tracking technology to enable tracking of users' gaze. We use the headset's built-in microphone to register voice control commands. Voice input is parsed locally on the PC running the demo using the Windows Speech Recognition platform, with parsed words being compared to a previously defined dictionary of command words. An experimenter equips users with a chest-strap holding the haptic feedback device while users are being equipped with the virtual prosthetic device in the doctor's office scene. Vibrotactile feedback indicating prosthesis movement and collisions with the environment is provided to the chest via a pair of Actronika HFBA 9532 voice-coil actuators driven by a Tactronik standard board connected to the PC running the demo via USB.

SCENARIO AND INTERACTIONS

As a two-armed human, users face difficulties in simple daily tasks, with interfaces designed for tri-manual interactions. The first scene takes place in a subway station. Users intend to take the subway to get to a doctor's appointment. There, they will receive a third arm prosthesis and learn how to use it before returning home, now capable of using devices designed for three-handed people.

Before receiving a prosthesis 4.1.1 First task: Reloading the transport card

Users need to reload their transport card at the ticket machine before entering the subway (see Figure 2 left). The particularity of this task is that the ticket machine is designed in such a way that users have to hold both their transportation card and their credit card up against the respective card readers, all the while pressing another button to make the adequate selections. Once the selection is made, the presence of the credit card against the reader triggers the payment and order confirmation. If the order is not confirmed in time, it is canceled and users must repeat the process. As a three-armed user, each hand can perform a sub-task (holding one of the cards against a reader, pressing the button) simultaneously so as to easily achieve the task. Since the ticket machine interface expects such users, the countdown before cancellation is quite short. Therefore, the task is achievable as a two-armed user but proves very difficult. Failures cause frustration to users, amplified by background sounds of discontent from other people waiting in line to use the machine. Once the card is recharged, users can move to the train access gates.

Second task: Crossing the gate

For the next task, users must cross the gate, once again designed for tri-manual operation (see Figure 2 right). The transportation card must be maintained on the card reader, unlocking both doors that can then be individually pushed. Two-armed users will only be able to push one door, creating an opening too narrow for them to go through. Consequently, this task is impossible to achieve. Users can call for help or use the button with a handicap logo in order to have a security officer activate the automatic opening, stressing users' lack of autonomy (see Figure 3). If users are too slow, the train can leave before they cross the doors, causing additional frustration. Once users enter the train, they are fast-forwarded to the medical office.

Getting the third arm prosthesis

In a medical office, users are introduced to the third arm prosthesis and are taught on how to use it. After a talk with a virtual doctor, a black transition is displayed when users are equipped with the prosthesis. At that moment, the experimenter equips users with the haptic device, while sound effects are played to simulate an operation. The prosthesis controls are then explained through a speech tutorial provided by the virtual doctor, followed by a minigame. In the mini-game, users have to reproduce a sequence of notes on three drums placed in front of them (see Figure 4).

After receiving the prosthesis

Now that users have a third arm, they once again face the same tasks as before in the subway station, and see the differences with their first attempt.To reload their transport card, users now simply have to use their prosthesis to hold one of the cards against the associated reader, freeing up one hand to easily go through the rest of the process. Proceeding to the subway gate, they no longer need to ask for help to get through the doors as the prosthesis can be used to push against one of the doors once unlocked. Passing through the doors ends the experiment, with a message telling the user to remove the headset.

CONCLUSION

This paper presents an original scenario for a 3DUI contest that plunges users into an uncomfortable experience in a world which is not adapted to their morphology. Virtual agents in the simulation all have an additional third arm, which users are missing. This makes interactions difficult for users, maximizing frustration, providing a sense of difference and generating empathy for people with physical disabilities. In the end, users are given a prosthesis controlled by voice or arm movements. The prosthesis' imperfection and control complexity add to the awareness or real-world issues of such aids.

Figure 1 :

 1 Figure 1: Left: Virtual environment representing a subway gate and populated with persons having three arms. Right: First-person perspective on user's only two arms.

Figure 2 :

 2 Figure 2: The main tasks to perform in the virtual environment. Left: Reloading the transport card on a dedicated machine. Right: Crossing the gate by opening its doors in order to enter the subway carriage.

Figure 3 :

 3 Figure 3: The call for help. Left: User's hand reaching for the help button. Right: Security officer coming to activate the automatic opening.

Figure 4 :

 4 Figure 4: The doctor's office. Left: Doctor welcoming the user. Right: The bongos used as a tutorial for controlling the third arm.


M Auffan

C Santaella

L Brousset

M Tella

C E Morel

P Ortet

M Barakat

C Chaneac

J Issartel

B Angeletti

C Levard

J-L Hazemann

M Wiesner

J Rose

A Thiéry

J.-Y Bottero

The shape and speciation of Ag nanoparticles drive their impacts on organisms in a lotic ecosystem

Silver nanomaterials with different shapes (spheres, plates, wires, rods, cubes) are valued by industries and scientists for their shape-dependent properties which make them useful for diverse applications. In a safer-bydesign perspective, controlling the shape of Ag nanomaterials could be an option to increase their potential applications while lowering either their hazard or their exposure potentials. Nine indoor aquatic mesocosms reproducing a lotic ecosystem were contaminated with chronic low-level additions of Ag nanospheres (Sp-Ag) and nanoplates (Pl-Ag) during a month. A shape-dependent impact in such environmentally relevant exposure conditions was observed. Pl-Ag induced a moderate oxidative stress in adult Gammarus fossarum (after molt) and an hormesis effect in the planktonic microbial communities, while Sp-Ag had no effect. In an environmental risk perspective, our results highlight which ecological niches of a lotic ecosystems would be more impacted by Pl-Ag : (i) >72% of the total Ag was found fully sulfidized in surficial sediment and had only moderate impact on benthic macro-organisms, (ii) only 11 to 15% of the Ag remained in the water column after 1 month, but Ag was under a more reactive speciation that impacts significantly the planktonic community.

Introduction

Controlling the size, shape, and structure of metal-based nanomaterials (NM) is technologically important due to the strong correlation between the intrinsic properties of NMs and their potential applications 1,2 .

For instance, silver nanomaterials (nanospheres, triangular nanoplates, nanowires, nanorods, or nanocubes) are valued by industries and scientists for their size-and shape-dependent properties which make them useful for diverse applications as optics, catalysis, sensors, antimicrobial agents, etc. 3,4 . Silver nanospheres are commonly used in antibacterial and antifungal applications, silver nanoplates in analytical chemistry as optical sensors, and silver nanowires as promising conductive films for flexible touch screens 5- 7 . One reason for the particularities of these applications stems from the relationship between nanoparticle shapes and the associated crystallographic faces exhibited that may allow for the tuning of surface reactivity and bulk properties. For instance, silver nanocubes have the {100} crystal faces as basal plane, whereas truncated triangular nanoplates and near-spherical nanoparticles predominantly exhibit the most-stable {111} crystal face. Also, for a given mass, a spherical geometry minimizes surface area. As a result, the rate of the reaction (in catalytic oxidation) of nanocubes is >14 times higher than nanoplates and 4 times higher than nanospheres 8 . Despite the challenge of controlling the shape of NMs during synthesis, several questions have been raised regarding the potential shape-dependence of hazard and exposure posed by NMs. George et al. (2012) studied the impacts of Ag nanospheres, nanoplates, and nanowires toward a fish gill cell line and zebrafish embryos (doses tested 0.39-25 mg.L -1 ). For both organisms, Ag nanoplates were significantly more toxic due to a high level of crystal defects (stacking faults and point defects) on the nanoplate surfaces 9 . Pal et al. (2007) also observed that truncated triangular silver nanoplates displayed the strongest biocidal action (doses tested 0.01-10 mg.L -1 ) toward Escherichia coli 10 . This was attributed to the high atom density {111} facet of the basal plane. Tak et al. (2015) assessed the penetration rates and depths through different layers of skin (in vitro and in vivo) of Ag nanospheres, nanorods and nanoplates 11 . Ag nanorods had the highest penetration and accumulated in the dermal layer, while triangular nanoplates had a slower penetration capability. Even if the mechanisms beyond these differences were not fully understood, such a shape-dependence allowed determining the therapeutic potential of Ag NMs versus their systemic toxicity 11 .

From a safer-by-design perspective, the risk related to nanomaterials for both human and the environment may be mitigated by lowering either the hazard or the exposure potential 12 . Controlling the shape of Ag NMs could be an option to fine-tune their efficacy in specific applications while reducing their potential harmful effects once release in the Environment. To our knowledge, such a shape-effect has never been assessed towards freshwater ecosystems under realistic exposure scenario.

Herein, we designed indoor aquatic mesocosm experiments to compare the environmental behavior, fate, and impact of Ag NMs with different shapes (plate and sphere) and consequently contrasted surface reactivities. Such mesocosm testing provides meaningful data to inform about environmental risk toward ecosystems [13][14][15][16] . A mesocosm is define here as an enclosed and, essentially self-sufficient (but not necessarily isolated) experimental environment or ecosystem with a number of interdependent system parameters 17 . Mesocosm experiments allow answering two research questions. First, do the shapedependent biological effects of Ag NMs previously observed in vitro on cell lines and in vivo toward mice also observed toward freshwater ecosystems under a realistic exposure scenario (chronic low-level additions of Ag, mid-term exposure)? Second, how the impacts towards benthic and planktonic ecological niches of a lotic ecosystem differ following exposure to these Ag NMs and their degradation byproducts? Nine indoor aquatic mesocosms reproducing a lotic ecosystem were dosed with chronic low-level additions of Ag nanospheres (Sp-Ag) and triangular nanoplates (Pl-Ag) during one month (final concentration of 42 and 47 µg.L -1 respectively). The biological impacts were assessed on the freshwater benthic detritivore Gammarus fossarum (Crustacea Amphipoda) through the analysis of oxidative stress biomarkers, and on microbial communities by pyrosequencing of the 16S rRNA gene. The (bio)distribution and (bio)transformation were assessed by inductively coupled mass spectrometry and X-ray absorption spectroscopy. G. fossarum is a detritivore crustacean with a key role in stream ecosystems (e.g. involved in leaf litter breakdown process, predated by other macroinvertebrates, fishes and amphibians) 18 and has been extensively used as a pertinent model organism for the ecotoxicity evaluation of a contaminants.

Herein, the final concentration of exposure to Pl-Ag and Sp-Ag is in the lower ranger of the LC50 previously determined for gammarids (between 5 to 1000 µg Ag.L -1 ) 19 .

Materials and methods

Spherical and triangular plate Ag nanoparticles suspensions

Polyvinylpyrrolidone coated spherical (Sp-Ag) and triangular plates (Pl-Ag) silver NMs suspensions were purchased from Nanocomposix ® . The commercialized stock suspensions were stored at 4°C for less than one month at 21.23 mg.L -1 (Sp-Ag) and 20.77 mg.L -1 (Pl-Ag). The amount of dissolved Ag in the stock suspensions were measured by ICP-MS (NexIon 300X®, Perkin Elmer) after ultracentrifugation (at 396 750xg for 1 h) at ~3.7% (Sp-Ag) and ~0.2% (Pl-Ag). The suspensions were then dialyzed (10 KDa) in milliQ® water to homogenize these amounts to 0.3 ± 0.1% (percentage of dissolved Ag vs total Ag). After dialysis the conductivity of the suspensions were 53 µS.cm -1 for Pl-Ag and 2.2 µS.cm -1 for Sp-Ag.

Observations of particles have been carried on a FEI Tecnai Spirit G2 TEM (Transmission Electron

Microscope) working with an acceleration voltage of 120 kV. For the analysis, one drop of particle suspension is deposited on a carbon film coated cupper grid. The average diameter of Sp-Ag was 20±1 nm, while Pl-Ag had a mean diameter of 26±7 nm and mean height of 8±1 nm (Fig. 1). Based on the TEM sizes and shapes, the specific surface area (SSA) were estimated at 25±3 m 2 .g -1 (Sp-Ag) and 29±13 m 2 .g -1 (Pl-Ag).

The metallic Ag(0) composition of the Sp-Ag and Pl-Ag was confirmed by Ag K-edge X-ray Absorption Near-Edge Structure (XANES) (Figure S1). Both suspensions have a zeta potential between -20 and -15 mV from pH 3 to 9 due to the PVP coating and average hydrodynamic diameter of 21±3 nm (Sp-Ag) and 24±3 nm (Pl-Ag) measured by dynamic light scattering (DLS) and electrophoretic mobility (Zeta nanosizer, Marlvern®, UK) (Figure S1).

Mesocosm set-up and monitoring

Nine indoor mesocosms (glass tanks of 750×200×600 mm) were set up to mimic a natural river. Natural sediments and organisms were collected from a non-contaminated river in southern France (43.81138 N, 5.34399 E, altitude 294 m a.s.l.). Each mesocosm consisted of a layer of artificial sediment (89% SiO2, 10% kaolinite, 1% CaCO3) covered with 240 g of water-saturated natural sediment (sieved <200 µm) containing primary producers (e.g., algae, bacteria), and 46 L of Volvic ® water. The depth of the sediments was ~5 cm and the height of the water column was ~50 cm. The pH and conductivity values of the Volvic ® water were close to those of natural river water. The natural water parameters registered the day of field sampling were 11.4° C, 95.6 % O2 i.e. 10.12 mg.L -1 , 435 µS.cm -1 , and pH 8.11. See Auffan et al. (2014) for more details on the mesocosm set-up and monitoring 16 .

The mesocosms were operated over an initial equilibration period of nine weeks at which point they were considered to be at steady state as measured by stable values of the physico-chemical parameters (pH, oxidation-reduction potential (ORP), dissolved O2, temperature, conductivity, and turbidity) in the mesocosms and the development of the primary producers. After the equilibration period, 100 adult amphipods G. fossarum (Koch, 1836) were introduced in each mesocosm. Only adults were brought in the mesocosms but birth occurred during the experiments. Two days after the organism introduction, three mesocosms were dosed with Sp-Ag, three with Pl-Ag, and three were kept as controls.

Details on the parameters monitored are provided in Figure S2. Briefly, temperature (15.3±0.6ºC), dissolved oxygen (10.6±0.6 mg.L -1 ), pH (8.0±0.1), and electrical conductivity corrected at 25°C (276±17 µS.cm -1 ) were constant over time. The water column was oxidative (218±53 mV), while reductive conditions prevailed in sediments (-187±117 mV) (Figure S2). The concentration of phosphates and carbonates were 3.8×10 -6 mol.L -1 and 0.2×10 -3 mol.L -1 respectively in controls after 4 weeks. The primary producers were counted weekly in both water column and sediments. The concentrations of picoplankton and algae were respectively between 10 4 -10 7 cells.mL -1 and 10 2 -10 4 cells.mL -1 in the water column and between 10 7 -10 8 cells.mL -1 and 10 6 -10 7 cell.mL -1 in surficial sediments (Figure S3). The concentration of colloidal particles (<0.7µm) in the water column was constant over time around 10 6 particle.mL -1 as measured using the optical counter Flowcell® FC200S+HR (OCCHIO).

Aquatic mesocosms dosing

Starting at Day 0 (2 days after introduction of the organisms), the water column of respective mesocosms was dosed 3 times per week (on Monday, Wednesday, and Friday) with Pl-Ag or Sp-Ag during 28 days. The total and dissolved [Ag] were measured in dialyzed stock suspensions prior to each dosing. Since SSAs of Sp-Ag and Pl-Ag were not statistically different, mesocosms were dosed with similar mass-and surface area-based concentrations. The final [Ag] obtained after 4 weeks were 46.8 µg.L -1 i.e. 1.4(±0.6)×10 -3 m 2 .L -1

for Pl-Ag and 42.1 µg.L -1 i.e. 1.1(±0.1)×10 -3 m 2 .L -1 for Sp-Ag.

Distribution in the mesocosms

The Ag content was measured by ICP-MS (NexIon 300X®, Perkin Elmer) in sediment, water column, and organisms (adults and juveniles G. fossarum). Surficial sediments (depth of sampling estimated at about 0.9±0.4 cm) 15 , water column (at ~10 cm from the air/water interface), and adult G. fossarum were sampled at Day 7, 14, 21, and 28. At Day 28, cores of sediment were sampled as well as juvenile G. fossarum. Each sampling of water, sediment and organism was performed in triplicate (sampling randomly distributed in one tank) and pooled for chemical analysis. The data presented are the average and standard deviation obtained within 3 replicated mesocosms.

Dialysis bags (10 kDa) filled with milliQ water were also placed in the water tank before NMs input, and 5 mL were once a week extracted from the bags for dissolved Ag analysis.

All samples were acid digested before ICP-MS analysis using adapted protocols 20 . The measurement quality was controlled using certified reference materials (HISS-1 marine sediment reference, CRM-NRC) and homemade references. All Ag concentrations expressed in mg.kg -1 correspond to dry weight.

Structural analysis

Silver K-edge (25.514 KeV) XANES spectra were acquired at the European Synchrotron Radiation Facility (ESRF, France) on the FAME beamline (BM30b) with Si(220) monochromator crystals 21,22 . Prior analysis, sediment and organisms were freeze-dried and pressed into pellets. Spectral acquisition was performed at liquid helium temperature to avoid sample evolution under the beam. Measurements were carried out in fluorescence mode using a Canberra Ge solid-state detector. Each spectrum was at least the sum of three scans. Data reduction was performed using the Ifeffit software package 23 . Sp-Ag, Pl-Ag, Ag2S, Ag-GSH were used as reference compounds.

Lipid peroxidation and total antioxidant capacity measurements

Between 6 to 8 adult G. fossarum, pooled from the three mesocosms of each condition, were sampled at days 14, 21 and 28. Immediately after sampling, organisms were gently dried on towel paper and frozen in liquid nitrogen. Samples were stored at -80°C until the start of the assays. Gammarids were individually crushed using a MM 400 homogenizer (Retsch®, Germany) in 350 µL of extraction buffer (5 mM KH2PO4, pH 7.4 with 0.9 % NaCl and 0.1% glucose). Homogenized samples were then used for lipid peroxidation (TBARS) and total antioxidant capacity (TAOC) quantifications according to protocols already published 15 .

All assay kits for the TAOC and TBARS measurements were provided by Cayman Chemical® (US). TAOC and TBARS contents were normalized to protein content following the Bradford method with serum albumin standard 24 .

As normality was not observed in all of the TBARS and TAOC data sets, differences between the mean TBARS and TAOC levels of controls and exposed organisms at a given exposure time were assessed using a non-parametric Kruskal-Wallis test, followed by a Dunn's post hoc test. Statistical analysis was performed using XLStat (Addinsoft, 2010). A 5% significance (p<0.05) was used in all tests.

Microbiota analysis

Water column and sediment from the nine mesocosms were sampled at days 0 and 28. Total DNA was extracted using FastDNA SPIN Kits for Soil and FastPrep-24 Instrument (MP Biomedicals®, France), according to the manufacturer's instructions. Variable regions 1 to 3 (V1-V3) of bacterial 16S rRNA gene were amplified with the specific primers 27Fmod (5′-AGRGTTTGATCMTGGCTCAG-3′) and 530R (CCGCNGCNGCTGGCAC) and barcode 25 . Polymerase chain reaction (PCR) reactions were carried out using HotStarTaq Plus Master Mix Kit (Qiagen, US). PCR products tagged with unique barcode from each sample were equally mixed and purified using Agencourt Ampure beads (Agencourt Bioscience®, US) and sequenced by MR DNA (www.mrdnalab.com, MR DNA, US) utilizing Roche 454 FLX Titanium instruments and reagents.

Sequence data resulting from the sequencing process were processed using a proprietary analysis pipeline (www.mrdnalab.com) 26,27 . Sequences were trimmed of barcodes and primers, and then short sequences (<200 bp), sequences with ambiguous base calls, and sequences with homopolymer runs exceeding 6 bp were removed. The 16S rRNA amplicon sequence data were analyzed using QIIME2 (qiime2:2019.10.0) 28 . Sequences were demultiplexed, truncated at 370 nucleotides based on sequence quality profile (>25), denoised and chimeras were removed using DADA2 29 . Sequences were aligned using MAFFT 30 , and were used to construct a phylogeny using FastTree 31 . Taxonomy was assigned using a Naïve Bayes classifier trained on the GreenGenes database (version 13_8) using trimmed sequences pre-clustered at 97% of similarity. 15729 features were generated from 383931 reads from 36 samples. Alpha diversity measures (observed OTUs, Chao1, Simpson, Fisher's index, and Shannon's diversity) and 𝛽 diversity measures (Bray-Curtis dissimilarity) were generated in MicrobiomeAnalyst 32 using a subsample feature table rarefied to 2 833 reads for the analysis of the whole dataset including sediments and water columns and to 11 522 reads when focusing on the water column samples. For β diversity and univariate analysis, data were transformed with Relative log expression (RLE) 33 and filtered (minimum count 10 for a feature, 20% of prevalence, filtering of features closed to constant using 10% based inter-quartile range).

Venn diagrams were constructed in MetaCoMET (Metagenomics Core Microbiome Exploration Tool).

Statistical analyses (Kruskall-Wallis, ANOVA, PERMANOVA, PERMDIST) were performed in R (www.rproject.org), MicrobiomeAnalyst, or XSTAT (2019.3.2). Db-RDA was run in Vegan. For multiple testing, p<0.05 was considered to be statistically significant. p-values were corrected to Q-values using the Benjamini-Hochberg False Discovery Rate (FDR). We selected a nonstringent Q-value set at 0.20 to avoid missing any important leads (www.biostathandbook.com). All statistical analyses were performed on 3 replicates of the same treatment, except for the microbial community in the water column dosed with Pl-Ag, for which a bloom of diatoms developed in one replicate as of Day-0. This replicate was excluded from the analysis (cf. result section).

Results and Discussion

Relevance assessment of mesocosms mimicking a lotic ecosystem

To assess the similarities among mesocosms before any contamination, and their ability to mimic a lotic ecosystem, we explored the composition and the diversity of the benthic and water communities in the mesocosms under baseline conditions at Day 0.

The diversity within a community (𝛼 diversity) 34 was described using the number of observed and predicted (Chao1) OTUs that characterize the richness of microbiomes, and the Shannon and Simpson's indexes that report on the richness and evenness (equitability among microbiota communities from different treatments). Based on Simpson index, a high diversity was observed in surficial sediments (from 0.985 to 0.993) and in water columns (from 0.792 to 0.938) of mesocosms at Day 0 (Figure S4, Table S1). The percentage of total species represented in a sample (Good's coverage) ranged from 98.63 to 99.89% in sediments and 98.80 to 99.58% in water column, highlighting that the majority of the bacterial communities was captured. Within both benthic and aquatic communities, high values of Shannon index were associated to high values of observed OTUs and Chao1, indicating that the communities were rich and even (not dominated by few abundant taxa). The diversity indexes within a compartment (surficial sediments or water column) did not differ between mesocosms (Kruskall-Wallis test, p<0.05). As expected in a natural lotic ecosystem 35 , the diversity was significantly higher in the benthic compartment than in the water column (Kruskall-Wallis test, p<0.017).

To assess dissimilarities among communities, Bray-Curtis distance (BC) summarizing compositional differences was used. The principal coordinate analysis (PCoA, Figure S5) based on BC visualizes the distribution of the microbiomes from surficial sediments and water columns at Day 0. A PERMANOVA based on BC demonstrated that the communities in sediments and water columns were significantly different (p<0.001, R 2 =0.409) evidencing naturally spatial niche partitioning. The bacterial community composition in surficial sediments did not differ at Day 0 among the 9 mesocosms (PERMANOVA, R 2 =0.242, p=0.582). In the water column, excluding one mesocosm where a diatomaceous Brown Algae biofilm had bloomed (Figure S6), the composition did not differ among mesocosms (PERMANOVA, p=0.762, R 2 =0.240).

The bacterial compositions of surficial sediments and water columns at Day 0 are illustrated at the class level in Figure S7. In the sediments, 17 phyla-subphyla were identified, of which BetaProteobacteria (24.8%), Alphaproteobacteria (22.8%), Actinobacteria (18.4%), Bacteroidetes (7.8%), Acidobacteria (6.6%), Cyanobacteria (6.3%), Gamaproteobacteria (4.8%), Nitrospirae (2.5%), DeltaProteobacteria (1.8%), Planctomycetes (1.6%) and Chloroflexi (1.1%). In the water column, Betaproteobacteria (35.1%), Bacteroidetes (7.5%), Alphaproteobacteria (29.3%), Actinobacteria (12.9%), Cyanobacteria (4.5%), Acidobacteria (2.8%), Gammaproteobacteria (2.8%), and Planctomycetes, Nitrospirae, Cholroflexi (1.5, 1.2 and 1.1 %, respectively) dominated the taxonomic diversity at the phylum/class levels. Similar community composition of surficial sediments and water was already observed in a survey of microbial diversity based on 16S rRNA gene sequence libraries from lotic, stream and river ecosystems 36 . Altogether, these features highlight that the mesocosms at Day 0 did not differ substantially in bacterial composition and were representative of a lotic system.

Benthic compartment: high exposure to Ag NMs but low impact

Silver accumulation in sediments and uptake by benthic organisms

Surficial sediments were sampled 7, 14, 21, and 28 days after the first injection of Pl-Ag and Sp-Ag. An increase of the Ag concentration was measured over time from 1.3±0.9 mg.kg -1 at Day 0 to 8.3±1.9 mg.kg - 1 at Day 28 (Fig. 2A and Fig. 2B). No significant difference in concentrations between Pl-Ag and Sp-Ag were observed. Comparing the span of predicted environmental concentrations (PEC) given in the literature (between 10 to 100 µg.kg -1 ) for sediments 37 , the amount of silver measured over a month in the sediment of mesocosms is two orders of magnitude higher. The analysis of cores of sediments sampled at Day 28 has shown that Ag mostly accumulated in the first 3 mm of sediments (Fig. 2A). This time-dependent increase of [Ag] in the sediment is attributed to the aggregation and settling of the Ag nanoparticles 38 . The size of the aggregates was evaluated in batch using Volvic ® water (Figure S8). For both Pl-Ag and Sp-Ag, two populations of hydrodynamic diameters (dh) were obtained after 2.5 hours centered on 40 nm and 1 500 nm for Sp-Ag, and on 60 nm and 1 500 nm for Pl-Ag. While not measured in the water column of the mesocosms, these values highlight the strong and similar aggregation expected at such pH and ionic strength. This is in agreement with George et al. (2012) 9 . showing similar aggregation for Pl-Ag and Sp-Ag in culture media.

G. fossarum were exposed to the silver reservoir localized in the surficial sediments which represents 85±19 % (Pl-Ag) and 72±34 % (Sp-Ag) of the total Ag injected. The quantity of Ag taken up or adsorbed on the cuticles of adults G. fossarum (Fig. 2C) was not shape-dependent. It increased from ~8.9±2.8 mg.kg -1 (days 7 and 14) to ~14.5±7.4 mg.kg -1 (day 21) and significantly decreased to 1.3±0.1 mg.kg -1 (day 28).

Concomitantly to this decrease, a significant number of juveniles G. fossarum was observed (Figure S9) with Ag concentration of 12.8±0.1 mg.kg -1 for Pl-Ag and 51.2±18.4 mg.kg -1 for Sp-Ag (Fig. 2C).

As all arthropods, female G. fossarum are known to shed their chitinous exoskeleton to develop, grow, and spawn 39 . The exuviation and the shedding of the chitinous cuticle and peritrophic membrane has been shown as one crucial mechanism governing the release of NMs taken up in the digestive track or adsorbed at the surface of arthropods 40 . We hypothesize that during the last week of exposure in the mesocosms, adults G. fossarum molt, juveniles hatched, and this exuviation induced a decrease of the Ag concentration measured in adults. Hence, the [Ag] taken up was dependent on the lifecycle stages of the organisms but not on the shape or even the thickness of the NMs (~20 nm for the Sp-Ag and ~8 nm for the Pl-Ag).

Ag sulfidation in the benthic compartment

It is well-known that metallic Ag is not thermodynamically stable under environmental conditions and will oxidize and/or react with (in)organic ligands as sulfide 41 , chloride 42 , and organic matter 43 . The speciation of the Ag accumulated in the surficial sediments and interacting with G. fossarum was assessed by XANES at the Ag K-edge (Fig. 3). Metallic Ag nanoparticles have a distinct XANES signatures with high amplitude of the first oscillations. Consequently, even if present in minor amounts, Ag(0) could be detected. Linear combination fitting (LCF) was performed to estimate the amount of Ag(0), Ag(I) and the nature of the first atomic shell. Herein, GSH was considered as a proxy for organic thiol-containing ligands having a strong affinity for silver (e.g. 𝑙𝑜𝑔𝐾 !"#$%&'()*( = 11.9), while Ag2S was considered as a relevant highly insoluble inorganic mineral (𝑙𝑜𝑔𝐾 &+ = -50.2) 44,45 . It is interesting to note that XANES spectra of Ag in sediment exposed to Sp-Ag and Pl-Ag superimposed, as do the XANES spectra of Ag in G. fossarum exposed to Sp-Ag and Pl-Ag (Fig. 3). The LCFs results highlight that no Ag K-edge XANES signal were attributed to Ag(0) but rather to sulfidized silver species either as inorganic bearing phase (54±8% and 22±3% respectively in sediment and G. fossarum) or organic Ag-thiol complex (46±7% and 78±12% respectively in sediment and G. fossarum). Based on the low signal/noise ratio and the fit residue, other Ag species could be present in these samples but not identified by LCFs. The XANES analysis confirmed that in freshwater organisms and sediments, silver strongly bound to both organic and inorganic sulfur likely through oxidative dissolution and precipitations 44 .

Low impact on benthic organisms

The impact of Sp-Ag and Pl-Ag was assessed on G. fossarum and benthic microbial community. Regarding adults G. fossarum, no significant difference in the number of adults or juvenile organisms were observed between Control and Ag NMs dosed-mesocosms after 28 days (Figure S8). This confirms the absence of acute toxicity in these experimental conditions. TAOC and TBARS levels were measured before (days 14 and 21) and after (day 28) the molting of G. fossarum (Fig. 4). No variation in TAOC was observed during the entire experiment among all treatments. However, lipid peroxidation was significantly higher (p=0.029) in gammarids exposed to Pl-Ag after 28 days of exposure (TBARS, 2.3±0.4 µmol.g -1 ), compared to the respective time-matched controls (TBARS, 1.8±0.3 µmol.g -1 ) (Fig. 4, and Fig. S13). A slightly lower variability in TBARS was observed in 21 and 28 days controls, and may participate to the significance of the statistical analysis observed at day 28. However, no difference between all time-matched controlled (14, 21 and 28 days) was observed (Kruskall-Wallis test), which corroborate the hypothesis of the Pl-Ag effect in G.

fossarum. The TBARS increased concomitantly when the Ag taken up by the organisms was mainly bound to thiol-containing ligands (100% of sulfidation and Ag2S/Ag-GSH of 0.3 in G. fossarum, Fig. 3).

Interestingly, a higher number of molting events was observed after 21 days. Gammarus pulex, a closerelated species to G. fossarum, is known to be more sensitive to cadmium after molting 46 . This suggests that after the exuviation occurring between day 21 and 28, G. fossarum could be more sensitive to Ag NMs.

The higher sensitivity to Pl-Ag compared to Sp-Ag is discussed in the next section.

After 28 days, the richness (observed and predicted OTUs) and richness-evenness (Shannon and Simpson indexes) of the bacterial communities in the sediments were not significantly altered compared to Day 0 and did not differ (Kruskall Wallis, all p>0.05) showing that neither time nor exposure to Pl-Ag and Sp-Ag modified the diversity in surficial sediments. At Day 28, time was the sole driver of the community composition (PERMANOVA, p<0.001, R 2 =0.105). Treatment and time-treatment interactions had no significant effect (p>0.05) on the composition of microbiomes on the surficial sediments, showing that after 28 days of chronic exposure to Sp-Ag and Pl-Ag, the structure of the benthic bacterial communities remained similar to controls. These results are consistent with the sulfidation of Ag in surficial sediment (100% of sulfidation and Ag2S/Ag-GSH of ~1.2). Indeed, several studies have shown that Ag sulfidation reduced the impact of Ag NMs on living organisms as zebrafish, killifish, nematode worms, microbial communities etc. 20,[47][48][49] . This was due to the lower solubility of sulfidized Ag relative to metallic Ag and consequently the lowest release of ecotoxic dissolved silver species following sulfidation. Planktonic compartment: low exposure to Ag NMs but significant impacts on microbial community Silver behavior and speciation in the water column.

During 4 weeks, the total and dissolved (<10 KDa) amount of silver were measured in the water column (Fig. 5). Each sampling, except between Day 0 and Day 3, were performed few minutes before the following dosing. Thus, these concentrations correspond the amount of silver remaining in the water column after all bio-physical-chemical transformations occurred (e.g. aggregation, uptake, …). In all cases, no significant difference in the means of total [Ag] or dissolved [Ag] in the water column was observed following Sp-Ag and Pl-Ag contaminations. The total [Ag] increased from 1.4±0.2 µg.L -1 at Day 3 (for both Pl-Ag and Sp-Ag) to 6.5±1.5 µg.L -1 for Pl-Ag and 5.2±0.5 µg.L -1 for Sp-Ag at Day 28. Comparing the span of PEC given in the literature (between 10 -5 to 10 -1 µg.L -1 ) for surface waters 37 to the amount of silver measured over a month in the water column of the mesocosms, provides an indication of the environmental relevance of these experiments. The linear decrease (R=0.99) observed between Day 0 and Day 3 shows the fast removal of silver from the water column between two dosing's. We estimated that after 5h and 72h, respectively 54% and 80% of the silver was removed. This was similar to the kinetics of removal already measured for (un)coated CeO2 NMs despite their different physical-chemical mechanisms of solubility (reductive dissolution for CeO2 vs. oxidative dissolution for metallic Ag) 14 . At the end of the experiment, a mass balance calculation shows that less than 15% of silver remained in the water column.

Mathematical integration of the dissolved [Ag] in the water column over time allowed to calculate a theoretical total exposure concentration over one month to dissolved Ag of 0.12±0.05 µg.L -1 .month -1 for Pl-Ag and 0.17±0.08 µg.L -1 .month -1 for Sp-Ag. Specifically, the mesocosms were observed to evolve over two distinct periods of time independently of the Ag NMs shape (Fig. 5) : dissolved [Ag] increased during the first week to ~0.10 µg.L -1 and then decreased and stabilized around ~0.025 µg.L -1 . We hypothesized that these two periods were attributed to (i) the oxidative dissolution of Ag(0) and (ii) the precipitation of the silver species in solution. Based on the solubility products (e.g. Ksp Ag20 = 4×10 -11 versus Ksp Ag2S = 5.92×10 -51 ), speciation determine by XANES, and the cationic/anionic composition of the water column, silver sulfidation is the most favorable transformation leading to this precipitation [START_REF] Pourbaix | Atlas of electrochemical equilibria in aqueous solutions[END_REF] .

Significant impacts on planktonic microbial community.

The impact of Pl-Ag and Sp-Ag on the bacterial microbiomes diversity and composition in the water column was assessed by sequencing of 16S rRNA gene amplicons. After 28 days, all indicators of diversity did not differ among treatments (Kruskal-Wallis test, p>0.05) (Figure S10, Table S2). As compared to Day 0, observed OTUs and Chao1 at D28 were significantly lower in the Pl-Ag dosed mesocosms (p<0.05), but not the Shannon and Simpson indexes (p>0.05), showing that the water columns differed in terms of richness but not in terms of effective diversities. The Sp-Ag treatment did not significantly affect the diversity in the water column over the 28 days of exposure.

Ordination based on the BC distance matrix (PCoA, Fig. 6) shows the distribution of the microbiomes in the water column of the mesocosms at days 0 and 28, for the different treatments. A PERMANOVA showed that among the explicative variables, the treatment-time interaction (R 2 = 0.510, p<0.007) and the time (PERMANOVA, R 2 = 0.245, p<0.001) were the main drivers of the community composition. Between days 0 and 28, all controls shifted and clustered downwards and to the right, while the Ag NMs-dosed communities (Pl-Ag and Sp-Ag) shifted upwards and to the right. Note that the mesocosm in which a diatomaceous Brown Algae biofilm had bloomed and differed from the other mesocosms as of Day-0, was excluded from the dataset. At D28 in the water column, a PERMANOVA on BC distance matrix showed a significant clustering based on treatment (p<0.037, R 2 =0.467). Univariate analysis showed differences at OTU and all taxonomic levels, illustrated at the class-level (Fig. 7). No significant difference in composition was detected between the water column composition of Sp-Ag dosed-and Control-mesocosms (FDR>0.20). However, the composition of the bacterial communities from the water column was significantly altered by Pl-Ag at the phylum level, with a 5-fold increase in the relative abundance of Bacteroidetes (p=0.0029, FDR=0.011) and a 3-fold decrease in Proteobacteria (p=0.069, FDR<0.139). At the order level, a 15-fold increase was observed in Saprospirales (p<0.0009, FDR=0.017) in Pl-Ag-dosed vs Controls. At the genus level, a 23-fold increase in a genus related to Sediminibacterium in the Pl-Ag vs Control (p<0.0008; FDR<0.017). Sediminibacterium genus has been described in sediment biofilms and in the water column of streams [START_REF] Besemer | [END_REF] .

Can the shift of microbiomes exposed to Ag NMs be understood in terms of toxicity?

To understand whether this change in abundance is a marker of toxicity, ecological patterns were sought out focusing on the dynamic core microbiome 52 . The consistently detected or persistent core microbiome was defined by taxa that were present within a user-specified fraction (0.8) of the samples to be counted as belonging to that group. Persistent core microbiomes are postulated to be responsible for microbially driven ecosystem processes, as illustrated in the ocean water column 53 . Spatial or temporal samplings allow for identification of spatially-(i.e. over different replicates of a same treatment) or temporally-dynamic persistent core microbiomes. At Day 0, 14 OTUs were consistently shared as a spatial persistent core microbiome among the water columns of the mesocosms. These persistent spatially core microbiome taxa represented on average 56%, 47% and 46% of the total community abundance for Control, Pl-Ag and Sp-Ag-dosed mesocosms respectively (Figure S11). At Day 28, the number of consistent OTUs among mesocosms decreased to 6 persistent taxa showing a shrink in the core microbiome as a result of time and Ag NMs treatment i.e. a system divergence. The abundance of core microbiome taxa after 28 days decreased to 35% and 21% of the total abundance for Control and Sp-Ag-dosed mesocosms, but increased to 54% for Pl-Ag exposed mesocosms (Figure S12).

Within each treatment, we compared the temporally dynamic core microbiome based on persistence.

Between days 0 and 28, the persistent core microbiome was richer in the mesocosms exposed to Pl-Ag with 15 OTUs than 8 OTUs for Sp-Ag and 7 taxa for Controls. In all cases, the response of the bacterial community to time and Ag NMs treatments went through an increase in the total core microbiome abundance vs. the total bacterial community and a modulation of the taxa abundance within the core community (Figure S11). Together, these patterns suggest rather a stimulation of microbial communities due to Pl-Ag than a toxic effect.

Environmental implications

Our results point out shape-dependent impacts towards organisms and communities living in a lotic ecosystem. Despite similar behavior (dissolution, aggregation, Fig. 2, Fig. 5), Sp-Ag impacted neither the benthic macro-organisms nor the microbial communities, while Pl-Ag induced a moderate oxidative stress in adult G. fossarum (Fig. 4) and destabilized the planktonic microbial communities (Fig. 6, Fig. 7).

Interestingly, the shift of microbiota in the water column in response to Pl-Ag points to an hormesis effect instead of a toxic event towards the community. Such a stimulation was already observed in term of growth of Cupriavidus necator at low Ag NMs concentrations 54 , as well as in Pseudomonas aeruginosa exposed to 20 mg.L -1 Ag NMs 55 . A shape-dependent biological responses to Ag NMs was already observed in vitro toward fish gill cells, red blood cells, zebrafish embryos 9 , and E. coli 10 . The high levels of defects at the surface of Pl-Ag 9 associated with the high reactivity of the edges and corners of triangular-shaped NPs might be responsible for the alteration of biomolecules or cellular structures via direct contact and generation of free oxygen radicals. This could explain the presence of oxidative damage and the shift in the microbial communities observed with Pl-Ag herein.

From an environmental risk perspective, our results highlight which ecological niches of a lotic ecosystems would be more impacted by Pl-Ag. Indeed, despite the highest exposure to Ag NMs in the benthic compartment (surficial sediment), the biological impacts were lower than in the planktonic compartment. These results confirm what has been recently stated by the scientific community, i.e. that the speciation and transformation of NMs rather than their concentrations drive the biological responses. Indeed, the surficial sediment contained >72% of the total Ag injected after 1 month, however the Ag is fully sulfidized and consequently less available to significantly impact the macro-and micro-organisms (only moderate effect were observed on G. fossarum). However, even if only 11 to 15% of the Ag remained in the water column after 1 month, Ag is present as a more reactive species (likely less oxidized surface of NMs and dissolved species) and more significantly impacts the pelagic community. 3), but focus on the environmental footprint (2) of Ag NMs based on their shape. The results presented herein could inform decision-making for the implementation of Ag NMs by maximizing the ratio of NMs functional performance (e.g. antibacterial, optical, electric properties) to environmental risks (shape-dependent effects).

Fig. 1

 1 Fig. 1 Size and shape of the Pl-Ag and Sp-Ag nanoparticles in their stock suspensions. TEM images and average particles sizes ± standard deviation.

Fig. 2

 2 Fig. 2 Distribution of Ag in the sediment. (A) Total [Ag] measured in 1 mm-section of cores of sediment sampled after 4 weeks. (B) Total [Ag] measured in the surficial sediments on 0.9 ± 0.4 mm depth sampled at 7, 14, 21 and 28 days. (C) Total [Ag] taken up or adsorbed on adults G. fossarum sampled at 7, 14, 21 and 28 days and juveniles at 28 days. For each time point and replicate, between 3 to 10 adults and 240 to 320 juveniles were pooled prior measurement. (A, B, C) Data represent average ± standard deviation of 3 replicated mesocosms corrected from background concentration determined in control mesocosms. * indicates a significant difference between Pl-Ag and Sp-Ag (p < 0.05).

Fig. 3

 3 Fig. 3 Ag K-edge XANES spectra of Ag in the surficial sediments and taken up or adsorbed at the surface of adults G. fossarum after 28 days of exposure to Sp-Ag and Pl-Ag. LCF : linear combination fits using Pl-Ag, Sp-Ag, Ag-GSH, and Ag2S reference compounds. R-factor refers to fit quality. Interestingly, at Day 28, the Ag2S/Ag-GSH ratio is lower in G. fossarum (~0.3) than in sediments (~1.2). This change in sulfidized species distribution could be related to pH or Eh variations, to different amount of sulfide vs. thiol-containing ligands in the sediments vs. in G. fossarum, but also to different bio-availabilities among Ag-S species.

Fig. 4

 4 Fig. 4 Lipid peroxidation (TBARS) and total antioxidant capacity (TOAC) in G. fossarum. Value are means ± sd. * indicates a significant difference with the respective control group (p < 0.05).

Fig. 5

 5 Fig. 5 Distribution of Ag in the water column. (top) Total [Ag] injected in the mesocosms (dotted lines) and dosed in the water column (symbols). The water was sampled at 10 cm from the air/water interface. (bottom) Dissolved [Ag] (<10 kDa). Data represent average ± standard deviation (𝑛 = 3) corrected from background concentration determined in control mesocosms. No significant difference between Pl-Ag and Sp-Ag was observed (p < 0.05).

Fig. 6

 6 Fig. 6 Principal coordinate analysis based on Bray Curtis dissimilarity of microbiomes in the water column (WC). Microbiomes are visualized at Day 0 (D0) and Day 28 (D28), respectively for Control mesocosms (coral and gold dots), Pl-Ag exposed mesocosms (green and cyan dots) and Sp-Ag treated mesocosms (blue and pink dots).

Fig. 7

 7 Fig. 7 Mean abundances at the class-level of the water bacterial community after 28 days in the mesocosms exposed to Pl-Ag, Sp-Ag and Controls.

From a safer

  by design perspective, Falinski et al. (2018) proposed a framework for sustainable NMs selection and design based on (1) performance, (2) hazard, and (3) economic considerations 56 . The current paper did not intend to inform about (1) and (

  CEREGE, CNRS, Aix Marseille Univ, IRD, INRAE, Coll France, Aix-en-Provence, France b. CEINT Center, Duke University, Durham, NC 27708, USA c. Aix Marseille Univ, CEA, CNRS, LEMIRE, 13108 Saint-Paul-lez-Durance, France d. Aix-Marseille Univ, Univ Avignon, CNRS, IRD, IMBE, Marseille, France e. CIRAD, US Analyse, F-34398 Montpellier, France, Analyse, Univ Montpellier, CIRAD, Montpellier, France f. Sorbonne Université, CNRS, Collège de France, LCMCP, France g. CNRS, Institut Néel, Université Grenoble Alpes, Grenoble, France Electronic Supplementary Information (ESI) available: [supplementary physico-chemical characterization of NMs and microbiota analysis]. See DOI: 10.1039/x0xx00000x

a.

Acknowledgements

The authors thank the CNRS for funding the IRP iNOVE, and the French ANR for funding the ANR-10-NANO-0006/MESONNET project. The authors acknowledge financial support provided by the FP7 project NANoREG (A common European approach to the regulatory testing of Manufactured Nanomaterials; European Commission, Grant Agreement Number 310584). This work has received funding from Excellence Initiative of Aix -Marseille University -A*MIDEX, a French "Investissements d'Avenir" program, through its associated Labex SERENADE project. This work is also a contribution to the OSU-Institut Pythéas.

Conflicts of interest

There are no conflicts to declare.