Julien Allali
email: allali@univ-mlv.fr

Marie-France Sagot
email: sagot@inria.fr

Novel tree edit operations for RNA secondary structure comparison

Keywords: tree comparison, edit operation, distance, RNA, secondary structure

We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two novel operations, called node fusion and edge fusion, besides the tree edit operations of deletion, insertion and relabelling classically used in the literature. This allows us to address some serious limitations of the more traditional tree edit operations when the trees represent RNAs and what is searched for is a common structural core of two RNAs. Although the algorithm complexity has an exponential term, this term depends only on the number of successive fusions that may be applied to a same node, not on the total number of fusions. The algorithm remains therefore efficient in practice and is used for illustrative purposes on ribosomal as well as on other types of RNAs.

Introduction

RNAs are one of the fundamental elements of a cell. Their role in regulation has been shown recently to be far more prominent than initially believed (20 December 2002 issue of Science, which designated small RNAs with regulatory function as the scientific breakthrough of the year). It is now known, for instance, that there is massive transcription of non-coding RNAs. Yet current mathematical and computer tools remain mostly inadequate to identify, analyse and compare RNAs.

An RNA may be seen as a string over the alphabet of nucleotides (also called bases), {A, C, G, T}. Inside a cell, RNAs do not retain a linear form but instead fold in space. The fold is given by the set of nucleotide bases that pair. The main type of pairing, called canonical, corresponds to bonds of the type A -U and G -C. Other rarer types of bonds may be observed, most frequent among them is G -U , also called the wobble pair. Figure 1 shows the sequence of a folded RNA. Each box represents a consecutive sequence of bonded pairs, corresponding to a helix in 3D space. The secondary structure of an RNA is the set of helices (or the list of paired bases) making up the RNA. Pseudo-knots, which may be described as a pair of interleaved helices, are in general excluded from the secondary structure of an RNA. RNA secondary structures can thus be represented as planar graphs. An RNA primary structure is its sequence of nucleotides while its tertiary structure corresponds to the geometric form the RNA adopts in space.

Apart from helices, the other main structural elements in an RNA are: 1. hairpin loops which are sequences of unpaired bases closing a helix; 2. internal loops which are sequences of unpaired bases linking two different helices; 3. bulges which are internal loops with unpaired bases on one side only of a helix; 4. multi-loops which are unpaired bases linking at least three helices. Stems are successions of one or more among helices, internal loops and/or bulges.

RNA secondary structure comparison is one of the main basic computational problems raised by the study of RNAs. It is the problem we address in this paper. The motivations are many. RNA structure comparison has been used in at least one approach to RNA structure prediction that takes as initial data a set of unaligned sequences supposed to have a common structural core [START_REF] Bouthinon | A new method to predict the consensus secondary structure of a set of unaligned RNA sequences[END_REF]. For each sequence, a set of structural predictions are made (for instance, all suboptimal structures predicted by an algorithm like Zucker's MFOLD [START_REF] Zuker | Mfold web server for nucleic acid folding and hybridization prediction[END_REF], or all suboptimal sets of compatible helices or stems). The common structure is then found by comparing all the structures obtained from the initial set of sequences, and identifying a substructure common to all, or to some of the sequences. RNA structure comparison is also an essential element in the discovery of RNA structural motifs, or profiles, or of more general models that may then be used to search for other RNAs of the same type in newly sequenced genomes. For instance, general models for tRNAs and introns of group I have been derived by hand [3] [5]. It is an open question whether models at least as accurate as these, or perhaps even more accurate, could have been derived in an automatic way. The identification of smaller structural motifs is an equally important topic that requires comparing structures.

As we saw, the comparison of RNA structures may concern known RNA structures (that is, structures that were experimentally determined) or predicted structures. The objective in both cases is the same: to find the common parts of such structures.

In [START_REF] Shapiro | An algorithm for multiple rna secondary structures[END_REF], Shapiro suggested to mathematically model RNA secondary structures without pseudoknots by means of trees. The trees are rooted and ordered, which means that the order among the children of a node matters. This order corresponds to the 5'-3' orientation of an RNA sequence. One way to compare two RNA secondary structures is then to apply a number of tree edit operations in one or both of the trees representing the RNAs until isomorphic trees are obtained. The tree edit operations considered are derived from the operations classically applied to sequences: substitution, deletion and insertion. In 1989, Zhang and Shasha proposed [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF] a dynamic programming algorithm for comparing two trees. Shapiro and Zhang then showed [START_REF] Shapiro | Comparing multiple RNA secondary structures using tree comparisons[END_REF] how to use tree editing to compare RNAs. The latter also proposed various tree models that could be used for representing RNA secondary structures. Each suggested tree offers a more or less detailed view of an RNA structure. Figure 2 (b) to (e) presents a few examples of such possible views for the RNA given in Figure 2 (a). In Figure 2, the nodes of the tree in (b) represent either unpaired bases (leaves) or paired bases (internal nodes). Each node is labelled with, respectively, a base or a pair of bases. A node of the tree in (c) represents a set of successive unpaired bases or of stacked paired ones. The label of a node is an integer indicating, respectively, the number of unpaired bases or the height of the stack of paired ones. The nodes of the tree in (d) represent elements of secondary structure: hairpin loop (H), bulge (B), internal loop (I) or multi-loop (M). The edges correspond to helices. Finally, the tree in (e) contains only the information concerning the skeleton of multi-loops of an RNA. The last representation, though giving a highly simplified view of an RNA, is important nevertheless as it is generally accepted that it is this skeleton which is usually the most constrained part of an RNA. The last two models may be enriched with information concerning, for instance, the number of (unpaired) bases in a loop (hairpin, internal, multi) or bulge, and the number of paired bases in a helix. The first label the nodes of the tree, the second its edges. Other types of information may be added (such as overall composition of the elements of secondary structure). In fact, one could consider working with various representations simultaneously or in an interlocked, multilevel fashion. This goes beyond the scope of this paper which is concerned with comparing RNA secondary structures using one among the many tree representations possible. We shall however comment further this multi-level approach later on.

Concerning the objectives of this paper, they are twofold. The first is to give some indications on why the classical edit operations that have been considered so far in the literature for comparing trees present some limitations when the trees stand for RNA structures. Three cases of such limitations will be illustrated through examples in Section 3. In Section 4, we then introduce two novel operations, so-called node-fusion and edge-fusion, that enable us to address some of these limitations and then give a dynamic programming algorithm for comparing two RNA structures with these two additional operations. Implementation issues and initial results are presented in Section 5. Before that, we start by introducing some notation and by recalling in the next section the basics about classical tree edit operations and tree mapping.

C G C G C G G C C G C G C G G C A U A U A U G C C G U A U A G C A U U A C G AUAUUA U U U C G A A U G G C C A A G A C G A A U A C A U A C A A U G C C G A U A U G C C U U U G G C U A A A U G U A A A U U U C C A A R U U U A G G G A A C A C A A A A U U G G C U U U -1 6 4 3 3 3 1 4 2 3 3 2 7 3 1 5 M I B H H R R M H H (b) (a) (c) (e) (d)

Tree editing and mapping

Let T be an ordered rooted tree, that is, a tree where the order among the children of a node matters. We define three kinds of operations on T : deletion, insertion and relabelling (corresponding to a substitution in sequence comparison). The operations are shown in Figure 3. The deletion (3 (b)) of a node u removes u from the tree. The children of u become the children of u's father. An insertion (3 (c)) is the symmetric of a deletion. Given a node u, we remove a consecutive (in relation to the order among the children) set u 1 , . . . , u p of its children, create a new node v, make v a child of u by attaching it at the place where the set was, and, finally, make the set u 1 , . . . , u p (in the same order) the children of v. The relabelling of a node (3 (d)) consists simply in changing its label.

Given two trees T and T ′ , we define S = {s 1 . . . s e } to be a series of edit operations such that if we apply successively the operations in S to the tree T , we obtain T ′ (i.e., T and T ′ become isomorphic). A series of operations like S realizes the editing of T into T ′ and is denoted by T S → T ′ . We define a function cost from the set of possible edit operations (deletion, insertion, relabelling) to the integers (or the reals) such that cost s is the score of the edit operation s. If S is a series of edit operations, we define by extension that cost S is s∈S cost s . We can define the edit distance between two trees as the series of operations that performs the editing of T into T ′ and such that its cost is minimal: Let an insertion or a deletion cost one and the relabelling of a node cost zero if the label is the same and one otherwise. For the two trees of the figure on the left, the series relabel(A → F ).delete(B).insert(G) realizes the editing of the left tree into the right one and costs 3. Another possibility is the series delete(B).relabel(A → G).insert(F ) which also costs 3. The distance between these two trees is 3. Given a series of operations S, let us consider the nodes of T that are not deleted (in the initial tree or after some relabelling). Such nodes are associated with nodes of T ′ . The mapping M S relative to S is the set of couples (u, u ′ ) with u ∈ T and u ′ ∈ T ′ such that u is associated with u ′ by S.

distance(T, T ′ ) = {min(cost S )|T S → T ′ }. A B C D E F G H D E F G H A B C I A B C E F G H B C D E F G H K (c) (d) (b) (a)
The operations described above are the "classical tree edit operations" that have been commonly used in the literature for RNA secondary structure comparisons. We now present a few results obtained using such classical operations that will allow us to illustrate a few limitations they may present when used for comparing RNA structures.

Limitations of classical tree edit operations for RNA comparison

As suggested in [START_REF] Shapiro | Comparing multiple RNA secondary structures using tree comparisons[END_REF], the tree edit operations recalled in the previous section can be used on any type of tree coding of an RNA secondary structure.

Figure 4 shows two RNAsePs extracted from the database [START_REF] Brown | The ribonuclease p database[END_REF] (they are found, respectively, in Thermotoga maritima and Streptococcus gordonii). For the example we discuss now, we code the RNAs using the tree representation indicated in Figure 2 (b) where a node represents a base pair and a leaf an unpaired base. After applying a few edit operations to the trees, we obtain the result indicated in Figure 2, with deleted/inserted bases in grey. We have surrounded a few regions that match in the two trees. Bases in the box at the bottom of the RNA on the left are thus associated with bases in the rightmost box of the RNA on the right. Such matches illustrate one of the main problems with the classical tree edit operations: bases in one RNA may be mapped to identically labelled bases in the other RNA to minimise the total cost, while such bases should not be associated in terms of the elements of secondary structure to which they belong. In fact, such elements are often distant from one another along the common RNA structure. We call this problem the "scattering effect". It is related to the definition of tree edit operations. In the case of this example and of the representation adopted, the problem might have been avoided if structural information had been used. Indeed, the problem appears also because the structural location of an unpaired base is not taken into account. It is therefore possible to match, for instance, an unpaired base from a hairpin loop with an unpaired base from a multi-loop. Using another type of representation, as we shall do, would, however, not be enough to solve all problems as we see next.

Indeed, to compare the same two RNAs, we can also use a more abstract tree representation such as the one given in Figure 2 (d). In this case, the internal nodes represent a multi-loop, internal-loop or bulge, the leaves code for hairpin loops and edges for helices. The result of the edition of T into T ′ for some cost function is presented in Figure 5 (we shall come back later to the cost functions used in the case of such more abstract RNA representations; for the sake of this example, we may assume an arbitrary one is used).

The problem we wish to illustrate in this case is shown by the boxes in the figure . Consider the boxes at the bottom. In the left RNA, we have a helix made up of 13 base pairs. In the right RNA, the helix is formed by 7 base pairs followed by an internal loop and another helix of size 5. By definition (see Section 2), the algorithm can only associate one element in the first tree to one element in the second tree. In this case, we would like to associate the helix of the left tree to the two helices of the second tree since it seems clear that the internal loop represents either an inserted element in the second RNA, or the unbonding of one base pair. This, however, is not possible with classical edit operations.

A third type of problem one can meet when using only the three classical edit operations to compare trees standing for RNAs is similar to the previous one but concerns this time a node instead of edges in the same tree representation. Often, an RNA may present a very small helix between two elements (multi-loop, internal-loop, bulge or hairpin-loop) while such helix is absent in the other RNA. In this case, we would therefore have liked to be able to associate one node in a tree representing an RNA with two or more nodes in the tree for the other RNA. Once again, this is not possible with any of the classical tree edit operations. An illustration of this problem is shown in Figure 11 (see Section 5).

We shall use RNA representations that take the elements of the structure of an RNA into account to avoid some of this scattering effect. Furthermore, in addition to considering information of a structural nature, labels are attached, in general to both nodes and edges of the tree representing an RNA. Such labels are numerical values (integers or reals). They represent in most cases the size of the corresponding element, but may also further indicate its composition etc. Such additional information is then incorporated into the cost functions for all three edit operations.

It remains now to deal with the last two problems that are a consequence of the one-toone associations between nodes and edges enforced by the classical tree edit operations. To that purpose, we introduce two novel tree edit operations, called the edge fusion and the node fusion. 4 Introducing novel tree edit operations

Edge fusion and node fusion

In order to address some of the limitations of the classical tree edit operations that were illustrated in the previous section, we need to introduce two novel operations. These are the edge fusion and the node fusion. They may be applied to any of the tree representations given in Figure 2(c) to (e).

An example of edge fusion is shown in Figure 6. Let e u be an edge leading to a node u, c i a child of u and e ci the edge between u and c i . The edge fusion of e u and e ci consists in replacing e ci and e u with a new single edge e. The edge e links the father of u to c i . Its label then becomes a function of the (numerical) labels of e u , u and e ci . For instance, if such labels indicated the size of each element (e.g. for a helix, the number of its stacked pairs, and for a loop, the min, max or the average of its unpaired bases on each side of the loop), the label of e could be the sum of the sizes of e u , u and e ci . Observe that merging two edges implies deleting all subtrees rooted at the children c j of u for j different from i. The cost of such deletions is added to the cost of the edge fusion.

Fig. 6. On the left, an example of edge fusion. On the right, an example of node fusion. Fig. 9. Illustration of the gain that must be obtained using a fusion instead of a deletion/relabelling. a fusion will be performed only if it improves the score by 0.1. In practice, we use values of t between 0 and 0.2.

We have applied the new algorithm on the two RNAs shown in Figure 5 (these are eukaryotic nuclear P RNAs from Saccharomyces uvarum and Saccharomyces kluveri) and coded using the same type of representation as in Figure 2 (d). We have limited the number of consecutive fusions to one (l = 1). The computation of the edit distance between the two trees taking node and edge fusions into account besides deletions, insertions and relabelling has taken less than a second. The total cost allowing for fusions is 6.18 with t = 0.05 against 7.42 without fusions. As indicated in Figure 10, the last two problems discussed in Section 3 disappear thanks to some edge fusions (represented by the boxes).

An example of node fusions required when comparing two "real" RNAs is given in Figure 11. The RNAs are coded using the same type of representation as in Figure 2 (d). The figure shows part of the mapping obtained between the small sub-units of two ribosomal RNAs retrieved from [START_REF] Winkelmans | The european database on small subunit ribosomal rna[END_REF] (from Bacillaria paxillifer and Calicophoron calicophorum). The node fusion has been circled.

Further work and conclusion

We have proposed an algorithm that addresses two main limitations of the classical tree edit operations for comparing RNA secondary structures. Its complexity is high in theory if many fusions are applied in succession to any given (the same) node, but the total number of fusions that may be performed is not limited. In practice, the algorithm is fast enough for most situations one can meet in practice.

To provide a more complete solution to the problem of the scattering effect, we propose the following scheme. Given an RNA, we build four tree representations for it instead of just one. Each tree corresponds to a different level of abstraction of the secondary structure of the RNA. The higher level represents the multi-loop skeleton while the lower level represents the sequence of paired and unpaired bases. For each tree except the one at the lowest level, there is a one-tomany relation between nodes, that is, a node of the tree at a given level is related with at least one node in the tree at the levels below. Two elements at the lowest level of abstraction, that is, two bases or base pairs can be matched only if they are part of a same structural element, the correspondence between such elements having being identified at a previous step by using the algorithm for comparing two structural tree representations introduced in this paper. Such approach thus allows us to address the problem of the scattering effect in an efficient way. A full description and practical consequences of such 4-level comparison method will be the subject of another paper.

Fig. 1 .

 1 Fig. 1. Primary and secondary structures of a transfer RNA.

Fig. 2 .

 2 Fig. 2. Example of different tree representations of a same RNA.

Fig. 3 .

 3 Fig. 3. Edit operations: (a) the original tree T , (b) deletion of node labelled D, (c) insertion of the node labelled I and (d) relabelling of a node in T (the label A of the root is changed into K).

Fig. 4 .

 4 Fig. 4. Result of the matching of the two RNAs in Figure 4 using the model (b) given in Figure 2.

Fig. 5 .

 5 Fig. 5. Result of the matching of the two RNAs using the model (d) given in Figure 2.

Fig. 10 .

 10 Fig. 10. Result of the editing between the two RNAs shown in the Figure 4 allowing for node and edge fusions. The boxes represent edge fusions.

Fig. 11 .

 11 Fig. 11. Part of a mapping between two rRNA small sub-units. The node fusion is circled.

An example of node fusion is given in Figure 6. Let u be a node and c i one of its children. Performing a node fusion of u and c i consists in making u the father of all children of c i and in relabelling u with a value that is a function of the values of the labels of u, c i and of the edge between them.

Observe that a node fusion may be simulated using the classical edit operations by a deletion followed by a relabelling. However, the difference between a node fusion and a deletion/relabelling is in the cost associated with both operations. We shall come back to this point later.

Obviously, like insertions or deletions, edge fusions and node fusions have of course symmetric conuterparts, which are the edge split and the node split.

We now present an algorithm to compute the tree edit distance between two trees using the classical tree edit operations plus the two operations just introduced.

Algorithm

The method we introduce is a dynamic programming algorithm based on the one proposed by Zhang and Shasha. Their algorithm is divided in two parts: they first compute the edit distance between two trees (this part is denoted by T Dist) and then the distance between two forests (this part is denoted by F Dist). In order to take our two new operations into account, we need to compute a few more things in the T Dist part. Indeed, we must add the possibility for each tree to have a node fusion (inversely, node split) between the root and one of its children, or to have an edge fusion (inversely edge split) between the root and one of its children. These additional operations are indicated in the right box of Figure 7.

We present now a formal description of the algorithm. Let T be an ordered rooted tree with |T | nodes. We denote by t i the i th node in a postfix order. For each node t i , l(i) is the index of the leftmost child of the subtree rooted at t i . Let T (i . . . j) denote the forest composed by the nodes t i . . . t j (T ≡ T (0 . . . |T |)). To simplify notation, from now on, when there is no ambiguity, i will refer to the node t i . In this case, distance(i 1 . . . i 2 , j 1 . . . j 2 ) will be equivalent to distance(T (i 1 . . . i 2 ), T ′ (j 1 . . . j 2 )).

The algorithm of Zhang and Sasha is fully described by the following recurrence formula:

Part (1) of the formula corresponds to Figure 7 while part (2) corresponds to Figure 8. In practice, the algorithm stores in a matrix the score between each subtree of T and T ′ . The space complexity is therefore O(|T | * |T ′ |). To reach this complexity, the computation must be done in a certain order (see [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF] for further details). The time complexity of the algorithm is

where leaf (T ) and height(T ) represent, respectively, the number of leaves and the height of a tree T .

Follows now the formula to compute the edit score allowing for both node and edge fusions.

Given two nodes u and v such that v is a child of u, node f usion(u, v) is the fusion of node v with u and edge f usion(u, v) is the edge fusion between the edges leading to, respectively, nodes u and v. The symmetric operations are denoted by, respectively, node split(u, v) and edge split(u, v).

The distance computation takes two new parameters path and path ′ . These are sets of pairs (e or u, v) which indicate, for node i k (resp. j k ), the series of fusions that were done. Thus a pair (e, v) indicates that an edge fusion has been perfomed between i k and v, while for (u, v) a node v has been merged with node i k . The notation path.(e, v) indicates that the operation (e, v) has been performed in relation to node i k and the information is thus concatenated to the set path of pairs currently linked with i k .

Observe that the computation of the forest distance does not change in relation to the original algorithm. We therefore need a matrix to store all edit scores between (i, path) and (j, path ′ ).

Let d be the maximum degree of the two trees. Then each node has O((2d) l ) different ways of participating in l consecutive fusions (that is, in fusions with successive nodes along a same branch). If we limit the number of consecutive fusions to l, the total memory complexity of our algorithm is O(n(2d) l ). By using the same arguments as in [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF], we prove that the time complexity of the new algorithm to be O((2d

This complexity suggests that the fusion operations may be used only for reasonable trees (typically, less than 100 nodes) and small values of l (typically, less then 4). It is however important to observe that the overall number of fusions one may perform can be much greater than l without affecting the worst-case complexity of the algorithm. Indeed, any number of fusions can be made while still retaining the bound of O((2d

) so long as one does not realize more than l consecutive fusions for each node.

In general also, most interesting tree representations of an RNA are of small enough size as will be shown next, together with some initial results obtained in practice.

Implementation and results

The algorithm presented in the previous section has been coded using C++. An online version is available at http://www-igm.univ-mlv.fr/~allali/migal/.

We recall that RNAs are relatively small molecules with sizes limited to a few kilobases. For instance, the small ribosomal subunit of Sulfolobus acidocaldarius (D14876) is made up of 1147 bases. Using the representation shown in Figure 2 (b), the tree obtained contains 440 internal nodes and 567 leaves, that is 1007 nodes overall. Using the representation 2 (d), the tree is composed of 78 nodes. Finally, the tree obtained using the representation given in Figure 2 (e) contains only 48 nodes. We therefore see that even for large RNAs, any of the known abstract tree-representations (that is, representations which take the elements of the secondary structure of an RNA into account) that we can use leads to a tree of manageable size for our algorithm. In fact, for small values of l (2 or 3), the tree comparison takes reasonable time (a few minutes) and memory (less than 1Gb).

As we already mentioned, a fusion (resp. split) can be viewed as an alternative to a deletion (resp. insertion) followed by a relabelling. Therefore, the cost function for a fusion must be chosen carefully.

Let us assume that the cost function returns a real value between zero and one. If we want to compute the cost of a fusion between two nodes u and v, the aim is to give to such fusion a cost slightly greater than the cost of deleting v and relabelling u; that is, we wish to have cost node f usion (u, v) = min(del(v) + t, 1). The parameter t is a tuning parameter for the fusion. Suppose that the new node w resulting from the fusion of u and v matches with another node z. The cost of this match is cost match (w, z). If we do not allow for node fusions, the algorithm will first match u with z, then will delete v. If we compare the two possibilities, on one hand we have a total cost of cost node f usion (u, v) + cost match (w, z) for the fusion, that is del(v) + t + cost match (w, z), on the other hand a cost of del(v) + cost match (u, z). Thus t represents the gain that must be obtained by cost match (w, z) with regard to cost match (u, z), that is by a match without fusion. This is illustrated in Figure 9.

The tuning parameter t is thus an important parameter that allows us to control fusions. Always considering a cost function that produces real values between 0 and 1, if t is equal to 0.1,


Laura Bonato

Matthieu Virot

Thomas Dumas

Adel Mesbah

Pierre Lecante

Damien Prieur

Xavier Le Goff

Christoph Hennig

Nicolas Dacheux

Philippe Moisy

Sergey I Nikitenko

Deciphering the Crystal Structure of a Scarce 1D Polymeric Thorium Peroxo Sulfate

Keywords: thorium, peroxide, sulfate, spectroscopic techniques, structure elucidation

The preparation and structural characterization of an original Th peroxo sulfate dihydrate crystallizing at room temperature in the form of stable 1D polymeric microfibres is described. A combination of laboratory and synchrotron techniques allowed to solve the structure of Th(O2)(SO4)(H2O)2 compound which crystallizes in a new structure type in the space group Pna21 of the orthorhombic crystal system. Particularly, peroxide ligand coordinates Th cations in an unusual μ3-η 2 :η 2: η 2 bridging mode forming an infinite 1D chain decorated with sulfato ligands exhibiting simultaneously monodentate and bidentate coordination modes.

Tetravalent actinides exhibit an extremely complex and varied chemical behaviour. [START_REF]The Chemistry of the Actinide and Transactinide Elements[END_REF] The chemistry of Pu(IV) has often been studied by using Th(IV) as a surrogate despite the differences in the sizes of their respective solvated ions which can be a source of significant discrepancies. On the other hand, the greater variability of the coordination number of Th(IV) compared to Pu(IV) is only very rarely addressed and remains an important challenge. [2] The case of mixed complexes, composed of two types of polyvalent ligands such as peroxo and sulfate, is particularly interesting. The only resolved Th peroxo structure available in the literature is the tri-nuclear cluster [Th(O2)(terpy)(NO3)2]3 (terpy= 2,2',6',2''-terpyridine) found to be assembled with bridging side-on/side-on μ-η 2 :η 2 peroxide anions coordinating Th atoms. [3] Nevertheless, structural characterization of thorium peroxides has puzzled the coordination chemists community and the few publications that has been reported so far often deals with highly insoluble and ill-defined compounds integrating inorganic anions from the solution in the solid species. [4] Th peroxides have been described since 1885 and have been widely used for separation purposes. [5] Particularly, thorium peroxides of variable compositions have been reported to form in sulfuric acid medium. [4a, 4d, 5a, 6] The older literature reports that weakly acid conditions lead to a precipitate crystallizing in the hexagonal system [5a, 6] while higher acidic conditions (> 0.3 M) are proposed to form a trihydrate Th(O2)(SO4)(H2O)3. A coordination number of 6 was proposed for this compound and the few structural interpretations have suggested an orthorhombic system comprising a bridging O-O peroxide ligand and a bidentate chelating sulfato group. [4a, 4d, 6] The current paper describes the unprecedented structure of a mixed Th(IV) complex coordinated with peroxo and sulfate ligands.

The addition of hydrogen peroxide to a thorium sulfate solution (0.05 M) at room temperature was found to yield a white powder composed of 1D fibre-like crystals of ca. 0.1 µm diameter and a length of 4 µm (Figure 1, inset). Powder X-ray diffraction pattern of the as-synthesized material (obtained on a conventional laboratory diffractometer with Cu-Kα radiation) exhibits intense and narrow diffraction peaks which are characteristic of a highly crystalline material. Throughout the experiments, the material was observed to be very stable thus facilitating further characterizations. No correspondence with ICSD or literature was found for this product. The quality of the XRD pattern was insufficient for structure determination (e.g. Rietveld analysis) and the various attempts devoted to the preparation of a single crystal failed (crystals not big enough). Interesting structural features were nevertheless evidenced by Fourier transform infra-red (FTIR) and Raman spectroscopies. The observed vibration wavenumbers and corresponding assignments are reported in Both vibrational spectroscopies show the characteristic signatures of coordinated peroxide and sulfate ligands in addition to both interstitial and/or coordinated water (Figure S1, SI).

Particularly, the band positioned at 859 cm -1 on the Raman spectrum (Figure 2) and the very weak one observed at 818 cm -1 on FTIR spectrum (Figure S1, SI) are assigned to the ʋ(O-O) symmetric stretching vibration mode of peroxide ligand in accordance with the bridging µ-η 2 :η 2 coordination mode already observed for cerium(IV), uranium(VI) and plutonium(IV) compounds. [2a, 7] The shift of the Raman band to lower wavenumber in comparison to free H2O2 (around 880 cm -1 ) can be attributed to the coordinating Th(IV) cation. [7d, 8] Raman bands positioned at 1128 and 1088 cm -1 (ʋ3); 979 cm -1 (ʋ1); 644 and 601 cm -1 (ʋ4); and 496 cm -1 (ʋ2) can be assigned to sulfate ligand in agreement with the literature [7g, 9] and FTIR data (Figure S1, SI). [4d, 7e, 7g, 9a, 9c, 10] Thermogravimetric analysis (TGA) illustrated in Figure S2 (SI) shows a two-step weight loss process of ca. 14.6% (between 20°C 480°C) and 18.6% (between 630°C and 1000°C). These two weight losses are correlated to the endothermic peaks observed at ca. 130°C and 775°C from differential thermal analysis (DTA). The absence of weight variation below 100°C suggests the absence of interstitial water. The initial weight loss up to 210°C can be attributed to the release of peroxide and coordinated water molecules. A slow and continuous loss observed up to 480°C can be attributed to remaining peroxides as confirmed by a weak exothermic peak at 465°C. The presence of a plateau between 480°C and 630°C indicates the formation of a stable intermediate compound suggested to be a thorium oxo sulfate of formula ThO(SO4). [START_REF] Raman | [END_REF] Sulfate decomposition then occurs between 630°C and 1000°C. Mass spectrometry (MS) coupled with TGA (Figure S3, SI) confirmed these interpretations with the release of H2O (up to 210°C), O2 (up to 480°C and at 695°C) and SO2 (at 695°C) as summarized in Table 1. The following chemical formula can then be proposed: Th(O2)(SO4)(H2O)2.

The solid blue curve presented in Figure 3 shows the Fourier transform (FT) of the extended X-ray absorption fine structure (EXAFS) obtained at the Th LIII-edge for the synthesized compound (k 3 -weighted EXAFS spectra is shown in Figure S4, SI). The main peak at R-φ= 1.9 Å superimposed with a satellite peak at R-φ= 2.3 Å corresponds to the first oxygen coordination sphere. This large peak expresses an intricate oxygen shell agreeing with the presence of peroxide, water, and sulfate ligands coordinated to the central Th atom. Two peaks noticed at R-φ= 2.8 Å and R-φ= 3.2 Å are attributed to sulfur atoms respectively evidencing both bidentate and monodentate coordination modes for sulfates. Such coordination has been already observed and discriminated on U(IV) and Th(IV) sulfato complexes giving similar FT profiles with corrected Th-S distances of 3.08 ± 0.02 and 3.67 ± 0.02 Å for U(IV) and 3.14 ± 0.02 and 3.81 ± 0.02 Å for Th(IV), respectively. [12] Radial Distribution Function (RDF) analysis from in-lab measurements provided more structural informations (Figure S5 and V= 717.31(5) Å 3 . The asymmetric unit is composed by one Th atom surrounded by one sulfur atom and eight oxygen atoms. Four of the eight oxygen belong to the sulfate group (labelled OS), two O-atoms belong to the peroxo group (labelled OP) and the remaining two belongs to the water molecules (labelled OW). A general view of the structure down the c axis is presented in Figure 4; metrical data are gathered in Table 2 (structural and refinement parameters are given in Table S2, SI). In this structure, each Th atom is coordinated to eleven oxygen atoms consisting of three OS, six OP and two OW. The formed polyhedra are connected together by edge or face sharing through the peroxo groups to form infinite polymeric chains oriented along the c axis (Figure 5). The 3D cohesion is ensured by hydrogen bonds between water molecules and one oxygen from the sulfate groups. It is worth noting that the sulfate groups provide a kind of intra-chain coordination around the Th atoms.

The presence of coordinated water, peroxo, monodentate and bidentate sulfate ligands, as viewed in Figure 5, agrees with the above structural hypotheses. Peroxo groups are found to be coordinated in a fairly scarce bridging µ3-η 2 :η 2 :η 2 mode recently reported in the crystal structure of lanthanide complexes [Ln4(O2)2Cl8(Py)10],Py (Ln= Sm, Eu, Gd; py= pyridine), heterobimetallic Zn4Ln7 (Ln= Gd, Dy) nano-sized clusters and [Tb3(O2)(pic)9] 2-(pic= picolinate) compound. [13] The O-O bond length of the peroxide ligands in Th(O2)(SO4)(H2O)2 equals ca. 1.486(7) Å which is slightly lower than those reported for µ3 bridged Ln-peroxo compounds(1.52 Å to 1.55 Å). [13b] However, it is closer to those reported for the only two peroxide structures resolved for tetravalent actinides where the peroxide ligand exhibit µ2-η 2 :η 2 coordination (O-O length is 1.496( 6) Å in the Pu(IV) peroxy-carbonate compound Na8Pu2(O2)2(CO3)6,12H2O and 1.516-1.515 Å in [Th(O2)(terpy)(NO3)2]3 cluster). [3, 7c] Such difference can be attributed to the ionic radius of the tetravalent actinides vs. trivalent lanthanides and their related charge density. The Th-OP length in Th(O2)(SO4)(H2O)2 ranges from 2.351(7) Å to 2.573( 6) Å which agrees with the literature data observed for Th (2.369(2) Å) and Pu peroxide clusters (2.33(1)-2.36(1) Å) [3, 7c] but also with µ3 peroxo complexes (Ln-OP ranges from 2.311(3) to 2.408(2) Å for Ln= Sm, Eu, Gd; from 2.289 to 2.501 Å for Ln= Dy; and from 2.35 to 2.36 Å for Ln= Tb). [13] The linking sulfate in Th(O2)(SO4)(H2O)2 is coordinated to one Th atom in bidentate coordination mode with a Th-S distance of 3.126(5) Å and to a neighbouring Th atom in monodentate coordination mode with a Th-S distance of 3.251(5) Å. Compared to other Th sulfate compounds, Th(O2)(SO4)(H2O)2 shows a smaller difference between Th-S distances for both coordination modes. Simultaneous bidentate and monodentate coordination for sulfato ligands has been reported by Hennig et al. for U(IV) (distances of 3.08 ± 0.02 and 3.67 ± 0.02 Å, respectively) and Th(IV) (3.14 ± 0.02 and 3.81 ± 0.02 Å, respectively) sulfato complexes. [12] Arutyunyan and Porai-Koshits reported both coordination modes in K4[Th(SO4)4(H2O)2] with distances of 3.119 Å and 3.715 Å, [14] respectively. Habash and Smith reported distances of 3.173 Å and 3.741 Å, respectively, in Cs2Th(SO4)3(H2O)2 compound. [15] The shorter Th-S distance in Th(O2)(SO4)(H2O)2 is related to the intra-chain coordination which brings monodentate sulfate closer to Th centers. The resulting Th-O-S angle for monodentate coordination is about 107.30° against 137.19° measured for instance in K4[Th(SO4)4(H2O)2]. [14] The flexibility of the Th-O-S angle in monodentate coordination allows a wide variation of Th-S distances.

The validity of the structural model is supported by simulating the experimental EXAFS signal (Figure 3 and Table 3). Scattering paths in a R-range from 0 to 4.3 Å were included and coordination numbers were maintained strictly identical to those derived from XRD. Interatomic distances and Debye-Waller factors (DWF) were adjusted using a global floating parameter for each shell. The corresponding fit (red circles in Figure 3) is in very good agreement with the experimental EXAFS spectrum (R-factor <5%) thus strengthening the validity of the proposed crystal structure. In detail, the 11 oxygen atoms observed in the first shell It is noteworthy that Th atoms located in the third coordination shell (two at 3.997 Å and two at 4.270 Å) are barely observed in both the experimental and simulated EXAFS spectra (Figure 3). Such counter-intuitive effect, already observed during the characterization of ThSiO4 nanoparticles, has been ascribed to destructive interferences generated by the contribution of different Th-Th distances. [16] This effect is illustrated in Figure S7 (SI) where the phases of the Th-Th scattering paths obtained from the synchrotron resolved structure are found to be opposite on the EXAFS signal. This phenomenon prevents a correct extraction of structure parameters from the Th scattering contribution. The experimental observation of Th-Th distances could be overcome by using X-ray scattering where all the individual contributions of atom pairs are summed for a global scattering signal, with strong emphasis on pairs involving Th (Figure S5, SI). The good global agreement between both experimental and simulated RDF also confirms its validity. Since the strong amorphous background clearly observed on non-corrected XRD data (Figure S6, SI) also fully contributes to the RDF, this agreement is also a proof that the studied compound includes only one structural phase, however with different degrees of crystallization. The synthesis and structural characterization of this unprecedented Th peroxo sulfate polymerizing within the form of stable 1D fibre-like crystals, clarify old discussions and contributes in filling the knowledge gap available on tetravalent actinide peroxo compounds. Particularly, the crystal structure of Th(O2)(SO4)(H2O)2 puzzled actinide scientists for more than a century and its characterization can be considered as milestone achievement that opens new investigation routes for the synthesis and understanding of other actinide peroxides. The observed rare 11-fold coordination of Th cations in this structure reveals a striking difference with the known actinide coordination geometries. ((Insert TOC Graphic here))

Paths

((Insert TOC Graphic here))

Figure 1

 1 Figure 1: Powder XRD diagram (background corrected) of the synthesized Th(O2)(SO4)(H2O)2 compound. Inset: SEM picture of the 1D fibre-like crystals. EDX analyses indicate the following chemical composition (at.%): C: 2.9 ± 0.6 (from SEM carbon tapes), O: 63.4 ± 2.9, S: 14.0 ± 1.2 and Th: 19.5 ± 1.4.

Figure 2 :

 2 Figure 2: Normalized Raman spectrum measured on the Th peroxo sulfate attesting the coordination of peroxo and sulfato ligands (= 532 nm, 39 mW).

Figure 3 :

 3 Figure 3: FT of the experimental k 3 -weighted EXAFS spectrum (solid blue curve) compared to the fitted FT derived from the structure resolved by powder synchrotron analysis (red circles). k-range fit obtained in the 2 Å - 1 < k < 13 Å -1 range. Scattering paths for the various shells are marked with dashed lines. OS, Om, and Ol respectively stand for averaged short, medium and long distance ranges for the O shell.

Figure 5 :

 5 Figure 5: Arrangement of the asymmetric unit Th(O2)(SO4)(H2O)2 forming polymeric chains along the c axis and evidencing the presence of bridging µ3-η 2 :η 2 :η 2 peroxo ligands, coordinated water molecules, and simultaneous monodentate and bidentate sulfato ligands.

Figure 4 :

 4 Figure 4: Arrangement of the asymmetric unit Th(O2)(SO4)(H2O)2 along the [001] direction

Table S1 in

 S1 Supporting Information (SI).

	[a]	Laura Bonato, Dr. Matthieu Virot, Dr. Adel Mesbah, Dr. Xavier Le
		Goff, Pr. Nicolas Dacheux and Dr. Sergey I. Nikitenko
		ICSM, CEA, CNRS, ENSCM, Univ Montpellier, Site de Marcoule,
		Bat 426, 30207 Bagnols sur Ceze, France
		E-mail: matthieu.virot@cea.fr
	[b]	Dr. Thomas Dumas, Dr. Philippe Moisy
		French Nuclear and Alternative Energies Commission (CEA)
		Nuclear Energy Division, Department of Mining and Fuel Recycling
		Processes (DMRC), Site de Marcoule
		BP17171, 30207 Bagnols sur Cèze, France
	[c]	Dr. Pierre Lecante
		Groupe SINanO, CEMES-CNRS, 29 rue Jeanne Marvig,
		31055 Toulouse Cedex 4, France
	[d]	Dr. Damien Prieur, Dr. Christoph Hennig
		Helmholtz-Zentrum Dresden -Rossendorf, Institute of Resource
		Ecology, Bautzner Landstraße 400,
		01328 Dresden, Germany
		Supporting Information (SI) for this article is given via a link at the
		end of the document.

Table 1 .

 1 Assignment of the mass losses observed during the TGA-DTA-MS experiments performed with the thorium peroxo sulfate compound.*%wt is the theoretical value calculated from released molecules.

Table 2 .

 2 Selected interatomic distances in Th(O2)(SO4)(H2O)2. OP, OS, and OW respectively stand for oxygen from peroxo group, sulfate group and water.

	Atom -Atom	Distance (Å)	Atom -Atom	Distance (Å)
	Th1 -OP1	2.569(5)	Th1 -OW1	2.51(3)
	Th1 -OP1	2.573(6)	Th1 -OW2	2.49(4)
	Th1 -OP1	2.378(6)	Th1 S1	3.251(5)
	Th1 -OP2	2.546(6)	Th1 S1	3.126(5)
	Th1 -OP2	2.478(7)	S1 -OS1	1.506(4)
	Th1 -OP2	2.351(7)	S1 -OS2	1.516(15)
	Th1 -OS2	2.42(5)	S1 -OS3	1.51(3)
	Th1 -OS3	2.50(3)	S1 -OS4	1.507(19)
	Th1 -OS4	2.50(3)	OX1 -OX2	1.486(7)

Table 3 .

 3 EXAFS structural parameters calculated according to the synchrotron resolved structure. R-factor 4.5%, *fixed value, # averaged value, S0 2 = 1.0, CN: coordination number, σ²: Debye-Waller factor, ΔE0= 4.8 eV. OS, Om, and Ol respectively stand for averaged short, medium and long distance ranges for the O shell.

Page No. -Page No. Deciphering the Crystal Structure of a Scarce 1D Polymeric Thorium Peroxo Sulfate

  Entry for theTable of Contents (Please choose one layout) Laura Bonato, Matthieu Virot,* Thomas Dumas, Adel Mesbah, Pierre Lecante, Damien Prieur, Xavier Le Goff, Christoph Hennig, Nicolas Dacheux, Philippe Moisy, and Sergey I. Nikitenko, Corresponding Author(s)*

	Layout 1:
	COMMUNICATION
	The structural characterization of an
	original Th peroxo sulfate dihydrate
	crystallizing at room temperature in
	the form of stable 1D polymeric
	microfibers is described.
	Th(O2)(SO4)(H2O)2 crystallizes in the
	Pna21 space group of the
	orthorhombic system. Peroxide
	ligands coordinate Th cations with a
	scarce μ3-η 2 :η 2 :η 2 bridging mode
	forming infinite 1D chains decorated
	with simultaneous monodentate and
	bidentate sulfato ligands.
	Layout 2:
		CN*	σ² (Ų)	R (Å)
	Os	2	0.010 (3)	2.29 (2) #
	Om	6	0.010 (3)	2.41 (2) #
	Ol	3	0.010 (3)	2.55 (2) #
	Sbid	1	0.003 (2)	3.13 (3)
	Smono	1	0.003 (2)	3.23 (3)
	Th1	2	0.014 (5)	3.91 (10)
	Th2	2	0.014 (5)	4.17 (10)

Acknowledgements

The authors gratefully acknowledge Mohamed Ruwaid Rafiuddin for useful discussion.

Experimental Section

Caution! 232 Th is an α-emitting radionuclide and standard precautions should be followed for handling these radioactive materials.

Synthesis. An aqueous solution of Th at 0.0135 M was prepared by dissolving 77 mg of Th(NO3)4.5H2O in 9 mL of 0.05 M sulfuric acid. 1 mL of 2.7 M H2O2 diluted in 0.05 M sulfuric acid was rapidly added to the Th solution. A white precipitate is formed one hour after the addition of the hydrogen peroxide. After centrifugation and washing with water, this precipitate is dried at room temperature under Ar before characterizations.

Extended X-Ray Absorption Fine Structure (EXAFS) analysis. The powdered compound was finely ground and mechanically mixed with boron nitride. EXAFS measurements were performed at the HZDRoperated Rossendorf beamline (European Synchrotron Radiation Facility, Grenoble, France) using a Si(111) double-crystal monochromator. Experimental spectra were recorded at Th LIII edge in fluorescence mode using a 13-element Ge detector at room temperature and pressure. EXAFS data were analysed using Athena and Artemis softwares from the IFEFFIT package. [17] X-ray structural analysis. Th(O2)(SO4)(H2O)2, 396 g.mol -1 ; white precipitate; orthorhombic system; Pna21 space group; V= 717.31(5) Å 3 ; ρcalcd= 3.631; Z= 4; a= 10.2600(5) Å, b= 16.3746(7) Å and c= 4.2696(1) Å. Synchrotron powder X-ray diffraction data were recorded at the Rossendorf beamline -BM20 (ESRF) using a Pilatus 3 X 2M detector (sample-detector: 39.9 cm; λ= 0.77490 Å; Si(111) double-crystal monochromator). The first 30 peaks of the pattern were indexed using the X-Cell algorithm incorporated in the Reflex program of materials studio. [18] The best solution was proposed in the orthorhombic crystal system in the space group Pna21 with unit cell parameters of a= 10.2725 Å, b= 16.3908 Å and c= 4.2761 Å. The Le Bail treatment of the powder pattern led to a satisfactory refinement with Rp= 0.014 and Rwp= 0.023. The obtained profile parameters were introduced in the Fox program to solve the crystal structure in the direct space methods where the sulfate groups were introduced as a rigid body. [19] After few cycles, the proposed solution was successfully refined without hydrogen atoms by the Rietveld method using the Fullprof suite program. [20] A full description of the characterization techniques and procedures is available in the Supporting Information. Further details on the crystal structure investigation(s) may be obtained from the Fachinformationszentrum Karlsruhe, 76344 Eggenstein-Leopoldshafen, Germany (fax: (+49)7247-808-666; e-mail: crysdata@fiz-karlsruhe.de), on quoting the depository number CSD 1904119.