Pierre-Anthony Grenier
email: pierre-anthony.grenier@ensicaen.fr

Luc Brun
email: luc.brun@ensicaen.fr

Didier Villemin
email: didier.villemin@ensicaen.fr

A Graph Kernel incorporating molecule's stereisomerism information

The prediction of molecule's properties through Quantitative Structure Activity (resp. Property) Relationships are two active research fields named QSAR and QSPR. Within these frameworks Graph kernels allow to combine a natural encoding of a molecule by a graph with classical statistical tools such as SVM or kernel ridge regression. Unfortunately some molecules encoded by a same graph and differing only by the three dimensional orientations of their atoms in space have different properties. Such molecules are called stereoisomers. These latter properties can not be predicted by usual graph methods which do not encode stereoisomerism. In this paper we propose a new graph encoding of molecules taking explicitly into account stereoisomerism and propose a new kernel between these structures in order to predict properties related to stereoisomerism.

I. INTRODUCTION

Most of QSAR and QSPR methods are based on a basic principle of the chemoinformatics framework which states that: "two similar molecules should have similar properties". Prediction of molecular properties thus involves the design of a model encoding molecules and a similarity measure between such models. We here implicitly assume that similarity between models corresponds to a similarity between molecules. However different models may encode different amount of information about molecules hence leading to different degree of relevance of their associated similarity measures.

Molecules can be represented by their molecular formula (e.g. CH 4 ). However, as this representation does not encode the bond connections between atoms, different molecules, called structural isomers, can have a same molecular formula. An usual way to overcome this limitation consists in the use of molecular graphs. A molecular graph is a simple graph G = (V, E, µ, ν), where each node v ∈ V encodes an atom, each edge e ∈ E a bond between two atoms and the labelling functions µ and ν associate to each vertex and each edge a label encoding respectively the nature of the atom (carbon, oxygen,. . . ) and the type of the bond (single, double, triple or aromatic). Molecular graphs, allow to encode neighborhood relationships between atoms, and thus allow to differentiate structural isomers.

However, molecular graphs have also a limitation: they do not encode the spatial configuration of atoms. Indeed, some molecules, called stereoisomers, are associated to a same molecular graph but differ by the relative positioning of their atoms. Hence, molecular graphs do not allow us to distinguish Fig. 1. Two different spatial configurations of the neighbors of a carbon two stereoisomers with different properties. Most of stereoisomers are characterized by the three dimensional orientation of the direct neighbors of a single atom or two connected atoms. We can imagine for example, a carbon atom, with four neighbors, each of them located on a summit of a tetrahedron. If we permute two of the atoms, we obtain a different spatial configuration (Figure 1). An atom is called a stereocenter if a permutation of two atoms belonging to its neighborhood produces a different stereoisomer. We should stress here that, to a large extend, stereoisomerism is independent of a particular embedding of a molecule. Indeed, in Figure 1, any particular embedding keeping the same relative positioning of atoms H, Cl, Br and F according to the central carbon atom C, would correspond to a same stereoisomer. In the same way, two connected atoms form a stereocenter if a permutation of the positions of two atoms belonging to the union of their neighborhoods produces a different stereoisomer (Figure 2). According to chemical experts, within molecules currently used in chemistry, 98% of stereocenters correspond either to carbons with four neighbors, called asymmetric carbons (Figure 1) or to couples of two carbons adjacent through a double bond (Figure 2). We thus restrict the present paper to such cases. Graph kernels [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF], [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF], provide a measure of similarity between graphs. Under the assumption that a kernel k is symmetric and definite positive, the value k(G, G ′ ), where G and G ′ encode two graphs, corresponds to a scalar product between two vectors Ψ(G) and Ψ(G ′ ) in an Hilbert space. This latter property allows us to combine graph kernels with usual machine learning methods such as SVM or kernel ridge regression by using the well known kernel trick, which consists in replacing the scalar product between Ψ(G) and Ψ(G ′ ) by k(G, G ′ ) in these algorithms.

Up to now, only few methods have attempted to incorporate stereoisomerism within the graph kernel framework. Brown et al. [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] have proposed to incorporate this information through an extension of the tree-pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF]. One drawback of this method is that, patterns which encode stereo information, and patterns which do not, are combined without any weighting in the final kernel value. So for a property only related to stereoisomerism, patterns that do not encode stereo information may be assimilated to noise. Intuitively, stereoisomerism property is related to the fact that permuting two neighbors of a given atom produces a different spatial configuration. Stereoisomerism property may be easily detected if all the direct neighbors of an atom have different labels (e.g. Figure 1). However, if two neighbors of a stereocenter have a same label, the influence of a permutation should be searched beyond the direct neighborhood of this stereocenter. Based on this ascertainment, Grenier et al. [START_REF] Grenier | Treelet kernel incorporating chiral information[END_REF] have introduced the minimal subtree which characterizes a stereocenter within an acyclic molecule. They also proposed a kernel based on this minimal subtree which takes into account stereoisomerism. This kernel is however restricted to acyclic graphs.

Based on [START_REF] Grenier | Treelet kernel incorporating chiral information[END_REF], we present in Section II an encoding of molecules distinguishing stereoisomers. Section III presents the construction of a subgraph, which allows to characterize locally a stereocenter. A molecule can then be described by the set of subgraphs describing each of its stereocenters. In Section IV, we propose a new graph kernel which compares the number of occurences of these subgraphs. This kernel is valid for cyclic as well as acyclic molecules and thus, overcomes the main limitation of [START_REF] Grenier | Treelet kernel incorporating chiral information[END_REF]. We finally present in Section V results obtained using this new kernel and compare these results with state of the art methods.

II. ORDERED GRAPH AND STEREO VERTICES

The spatial configuration of the neighbors of each atom may be encoded through an ordering of its neighborhood. For example, considering the left part of Figure 1, and looking at the central carbon from the hydrogen atom (H), the sequence of remaining neighbors of the carbon: Cl, Br and F may be considered as lying on a plane and are encountered clockwise. Thus, this spatial configuration is encoded by the sequence H, Cl, Br, F and the sequence H, Br, Cl, F encodes the second configuration. The configuration around a double bond can also be encoded by ordered sequences. Considering the left part of Figure 2 and assuming a clockwise orientation with the plane embedding provided by this figure, we encounter F and Cl when turning around the carbon at the top of the molecule, and H and O for the carbon at the bottom. Thus this configuration may be encoded by both sequences F, Cl and H, O respectively for the top and bottom carbon atoms. Sequences F, Cl and O, H encode the second configuration.

In order to encode this information in a graph, we introduce the notion of ordered graph. An ordered graph G = (V, E, µ, ν, ord) is a molecular graph G m = (V, E, µ, ν) together with a function ord : V → V * which maps each vertex to an ordered list of its neighbors. Two ordered graphs G and G ′ are isomorphic (G ≃ o G ′ ) if there exists an isomorphism f between their respective molecular graphs G m and

G ′ m such that ord ′ (f (v)) = (f (v 1 ) . . . f (v n )) with ord(v) = (v 1 . . . v n ) (where N (v) = {v 1 , . . . , v n } denotes the neighborhood of v).
However, different ordered graphs may encode a same molecule. In the example of the left part of Figure 1, if we look to the central carbon from a different neighbor, we can obtain a different sequence, for example F, Br, Cl, H, that represents the same configuration but now considered from the atom F. In the same way, considering the molecule on the left part of Figure 2 still with a clockwise orientation but now from the opposite side of its plane embedding we obtain the opposite sequences Cl, F and O, H. We thus have to define an equivalence relationship between ordered graphs, such that two ordered graphs are equivalent if they represent a same configuration.

To do so, we introduce the notion of re-ordering function σ, which associates to each vertex v ∈ V of degree n a permutation σ(v) on {1, . . . , n}, which allows to re-order its neighborhood. The graph with re-ordered neighborhoods σ(G) is obtained by mapping for each vertex v its order

ord(v) = v 1 . . . .v n onto the sequence v σ(v)(1) . . . .v σ(v)(n)
where σ(v) is the permutation applied on v.

In order to define a permutation σ(v) for each vertex of a graph, we first introduce the notion of potential asymmetric carbon which corresponds to a carbon with four neighbors. Such a vertex corresponds to a stereocenter if one permutation of two of its neighbors provides a different stereoisomer (Section I). Permutations associated to a potential asymmetric carbon correspond to all even permutations of its four neighbors [START_REF] Petitjean | Chirality in metric spaces[END_REF]. We can easily check that the different orders obtained by these permutations, encode a same configuration but either seen from a different neighbor or with a same view point but with a different encoding of the cyclic order of the three remaining neighbors. For example, even permutations (1, 4)(2, 3) and (2, 3)(3, 4) applied on the order H.Cl.Br.F of the central carbon in Figure 1 produce respectively the orders F.Br.Cl.H and H.Br.F.Cl which both encode the same configuration. For a double bond between two carbons, permutations associated to each carbon of the double bound must have a same parity. In the same way, we can check that these permutations correspond to different representations of a same configuration. Finally, for any vertex which does not correspond to a potential asymmetric carbon nor to a carbon of a double bond, we do not search to characterize its spatial configuration. So these vertices are associated to all possible permutations of their neighbors.

The set of re-ordering functions, transforming an ordered graph into another one representing a same configuration is called a valid family of re-ordering functions Σ [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF]. Two ordered graphs G and G ′ are said to be equivalent according to

Σ (G ≃ Σ G ′ ) if it exists a re-ordering function σ ∈ Σ such that σ(G) ≃ o G ′ .
This relationship defines an equivalence relationship [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF] and two different stereoisomers are encoded by non equivalent ordered graphs. We denote by IsomEqOrd(G, G ′ ) the set of equivalent ordered isomorphism between G and G ′ . Potentials asymmetric carbons, and double bonds between carbons, are not necessarily stereocenters. For example if the label of vertex Br of Figure 1 is replaced by Cl, both left and right molecules of Figure 1 would be identical. In the same way, if the label of the vertex F in Figure 2 is replaced by Cl, the left and right molecules of this figure would also become identical. For those cases, any permutation in the ordered list of the carbons would lead to an equivalent ordered graph. We thus define a stereo vertex as a vertex for which any permutation of two of its neighbors produces a non-equivalent ordered graph:

Definition 1 (Stereo vertex). Let G = (V, E, µ, ν, ord) be an ordered graph. A vertex v ∈ V is called a stereo vertex iff: ∀(i, j) ∈ {1, . . . , |N (v)|} 2 , i = j, ∄f ∈ IsomEqOrd(G, τ v i,j (G)) with f (v) = v.
(1) where τ v i,j (G) corresponds to an ordered graph deduced from G by permuting nodes of index i and j in ord(v).

III. MINIMAL STEREO SUBGRAPH

Definition 1 is based on the whole graph G to test if a vertex v is a stereo vertex. However, given a stereo vertex s, one can observe that on some configurations, the removal of some vertices far from s should not change its stereo property. In order to obtain a more local characterization of a stereo vertex, we should thus determine a vertex induced subgraph H of G, including s, big enough to characterize the stereo property of s, but sufficiently small to encode only the relevant information characterizing the stereo vertex s. Such a subgraph is called a minimal stereo subgraph of s.

We now present an heuristic, used to compute a minimal stereo subgraph of a stereo vertex. We first focus our attention on asymmetric carbons. Let H be a subgraph of G containing a stereo vertex s corresponding to an asymmetric carbon. We say that the stereo property of s is not captured by H if (Definition 1):

∃(i, j) ∈ {1, . . . , |N (s)|} 2 , i = j, ∃f ∈ IsomEqOrd(H, τ s i,j (H)) with f (s) = s (2)
To define a minimal stereo subgraph of s, we consider a finite sequence (H k s ) n k=1 of vertex induced subgraphs of G. The first element of this sequence H 1 s is the smaller vertex induced subgraph for which we can test (2) :

V (H 1 s ) = {s} ∪ N (s) where V (H 1
s ) and N (s) denote respectively the set of vertices of H 1 s and the set of neighbors of s. If the current vertex induced subgraph H k s does not characterize the stereo property of s, we know by [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF], that it exists some isomorphisms f of equivalent ordered graphs between H k s and τ s i,j (H k s ) with i = j and f (s) = s. Let us consider such an isomorphism f . By definition of equivalent ordered isomorphism, it exists σ ∈ Σ such that f is an ordered isomorphism between H k s and σ τ s i,j (H k s ) . By definition of ordered isomorphisms, and since f (s) = s, we have:

∀l ∈ {1, . . . , |N (s)|}, f (v l ) = v σ(s)•τ s i,j (l) . with ord(s) = v 1 , . . . , v n .
As σ(s) is an even permutation, σ(s) • τ s i,j is an odd one. Hence it exists l in {1, . . . , |N (s)|} such that l = σ(s)•τ s i,j (l). In other words, any equivalent ordered isomorphism corresponding to equation ( 2) maps at least one vertex in the neighborhood of s in H k s onto a different vertex in the same neighborhood. Let us denote by E k f the set of vertices of H k s connected to s by a path whose all vertices are mapped onto other vertices by f :

E k f = {v ∈ V (H k s ) | ∃c = (v 0 , . . . , v q ) ∈ H k s with v 0 = s and v q = v s.t. ∀r ∈ {1, . . . , q}, f (v r ) = v r } (3)
For any equivalent ordered isomorphism f satisfying (2), the set E k f is not empty since it contains at least 2 vertices. A vertex v belongs to E k f if neither its label nor its neighborhood in H k s allows to differentiate it from f (v). The basic idea of our algorithm consists in enforcing the constraints on each v ∈ E k f at iteration k + 1 by adding to H k s the neighborhood in G of all vertices belonging to one E k f , with f satisfying (2). The set of vertices of the vertex induced subgraph H k+1 s is thus defined by:

V (H k+1 s ) = V (H k s ) ∪ f ∈F k s N (E k f ) (4)
where F k s denotes all equivalent ordered isomorphisms satisfying (2).

Since f ∈ F k s implies that E k f is not empty, adding iteratively constraints on the existence of vertices in E k f removes f from F k s . The algorithm stops when the set F k s becomes empty. Note that such a condition must be satisfied since s is a stereocenter and hence the whole molecule does not satisfies (2).

Algorithm 1 Construction of a minimal stereo subgraph Input: a stereo vertex s and an ordered molecular graph G Output: a minimal stereo sub graph

H 1 s ← {s} ∪ N (s) (F 1 s , E 1 f ) ← getIsomorphism(H 1 s ) k ← 1 while F k s = ∅ do k ← k + 1 V (H k s ) ← V (H k-1 s ) ∪ N (E k-1 f ) (F k s , E k f ) ← getIsomorphism(H k s , F k-1 s ) end while
The main steps of our method are summed up in Algorithm 1. The function getIsomorphism uses a fast isomorphism algorithm [START_REF] Bonnici | A subgraph isomorphism algorithm and its application to biochemical data[END_REF] to compute the isomorphisms f between H k s and τ s i,j (H k s ) and the sets E k f for each (i, j) ∈ {1, . . . , |N (s)|} 2 . f contains the three carbons of these two paths and both oxygen atoms. The oxygen atoms belong to E 2 f since their neighborhoods in H 2

C does not allow to differentiate them (Fig. 3). At iteration 3, the neighborhood in G these oxygen atoms added to H 3 C , hence adding N and Br which allows to differentiate both paths and thus removes the equivalent ordered isomorphism f from F 3 C . Note that the neighborhoods of the three carbons atoms are also added but without any influence on H 3 C since these neighborhoods already belong to H 2 C . Note that smaller subgraphs than H n s which also capture the stereo property of s may be found. For example, in Fig. 3, the subgraph H Br , obtained from H 3 C by removing the bromine atom (Br) also captures the stereo property of the central carbon C since no equivalent ordered isomorphism between H Br and τ C i,j (H Br ), i, j ∈ {1, . . . , |N (C)|}, i = j may be found. In the same way, the subgraph H N obtained by removing the nitrogen atom (N) from H 3 C also captures the stereo property of the central carbon C. However these graphs capture the stereo property of the central carbon atom only thanks to the absence of atoms N in H Br and Br in H N which forbids to map their incident oxygen atoms one onto the other. Hence these graphs only encode the stereo property of the central carbon atom thanks to a lack of encoding of an information present in the graph. Moreover, there is no easy way to decide which of these graphs should represent the stereo property of the central carbon. This last point may induce a bias if one wish to compare two graphs through their sets of minimal stereo subgraphs. We hence decide to keep the subgraph H 3 C produced by our algorithm which in Fig. 3 encodes the fact that the central carbon is a stereocenter from the difference of labels between the vertex encoding nitrogen (N) and the one encoding bromine (Br).

For double bond between two carbons, v and w, we have to compute a single minimal stereo subgraph since the stereo property of each carbon of a double bond is connected to the stereo property of the other [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF]. A minimal stereo subgraph of v and w is defined the same way as for an asymmetric carbon, the only difference being in the initialisation of the sequence (H k v,w ) n k=1 . Indeed to test (2) the smaller vertex induced subgraph for a double bond between carbons is defined by the set of vertices:

V (H 1 v,w ) = {v, w} ∪ N (v) ∪ N (w)
IV. STEREO KERNEL

The method described in Section III allows to associate a minimal stereo subgraph to each stereocenter of a molecule. We can thus characterize the stereo properties of a molecule through its set of minimal stereo subgraphs. However, a same stereo subgraph may be present more than once in a given molecule. In order to compute efficiently the frequency of a given stereo subgraph within a molecule, we need to associate a unique code to each such subgraph so that the existence of an equivalent ordered isomorphism between two stereo subgraphs may be tested efficiently. We perform such a transformation from stereo subgraphs to codes thanks to [START_REF] Wipke | Stereochemically unique naming algorithm[END_REF] which associates each stereo subgraph to an unique code. Note that this code takes explicitly into account the stereoisomerism. Moreover, unlike [START_REF] Bonnici | A subgraph isomorphism algorithm and its application to biochemical data[END_REF] which allows to find efficiently all isomorphisms between two graphs, [START_REF] Wipke | Stereochemically unique naming algorithm[END_REF] associates to each molecule a unique code which allows to test the existence of an equivalent ordered isomorphism between two stereo subgraphs.

Given an ordered graph G, we can thus compute its set of minimal stereo subgraphs H(G) together with its spectrum spec(G) = (S H (G)) H∈H(G) which encodes the frequency S H (G) of each H ∈ H(G). The set H(G) and the spectrum spec provide a characterisation of each stereo center of G and hence describe the stereoisomerism of G.

The comparison of the spectrum of two ordered graphs, is then used to define a kernel between two molecules taking into account the stereoisomerism:

k(G, G ′ ) = H∈H(G)∩H(G ′ ) K(S H (G), S H (G ′ )).
(

) 5
where K denotes a kernel between real values (e.g. Gaussian, intersection or polynomial). For example, if K is the intersection kernel, the kernel value k of two ordered graphs with non intersecting sets H(G) of stereo subgraphs is zero. The kernel value of two identical ordered graphs is equal to the total number of occurences of their stereo subgraphs. The choice of a particular kernel, together with its parameters is performed through cross-validation.

V. EXPERIMENTS

We have evaluated our kernel on two datasets connected with stereoisomerism properties. Both datasets correspond to regression problems, one connected to the prediction of a physical molecular property, the other one being related to a biological property. We use the standard SVM regression method [START_REF] Drucker | Support vector regression machines[END_REF] for all kernels evaluated in this section.

The first dataset [START_REF] Zhu | Matrix model to predict specific optical rotations of acyclic chiral molecules[END_REF] is composed of 90 molecules together with their optical rotations. Optical rotation of a molecule is

Method RMSE

Tree patterns Kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] 27.9 Treelet Kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] 26.2 Tree patterns Kernel incorporating stereo information [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] 25.8 Stereo Kernel 17.9

a physical property measuring the deviation angle of a planepolarized light passing through a solution of this molecule.

In practice, we only select 35 molecules, since almost all molecules have only one stereocenter, and for 55 molecules this stereocenter is unique in the dataset. Such molecules correspond thus to a property (a rotation angle) present only once in the dataset which can not be accurately predicted. The standard deviation of the optical rotation angle is equal to 38.25 for the 35 selected molecules. Due to the limited number of molecules of this dataset we evaluate the rotation angle of each molecule using a leave one out procedure. We used a grid search to choose the different parameters: C of the SVM, the type of sub kernel used in ( 5) and the parameters of [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF], [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF].

As we do not have a validation set, the selected parameters for each kernel are the ones obtain the lowest Mean Squared Error (RMSE).

Table I shows the RMSE obtained by our method and three other kernels [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF], [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF], [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF]. The Tree pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] and the treelet kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] do not incorporate any information related to stereoisomerism and obtain consequently the highest errors. The adaptation of the Tree pattern kernel to stereoisomerism [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] obtains better results than these two latter methods. However, in this experiment devoted to the prediction of a property only related to stereoisomerism, the inclusion by this kernel of information not related to stereoisomerism forbids an important decrease of the mean error. Our method represented on the last line of Table I obtains the lowest root mean squared error. We can notice that this error is significantly lower than both the error obtained by [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] (line 3) and the standard deviation of the dataset. As shown in Table II, the sizes of the minimal stereo subgraphs computed by our method on this dataset remain small but are usually larger than the size of the direct neighborhood of an asymmetric carbon (5) or a double bound [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF].

Figure 4 shows three molecules of this dataset. The closest molecule from Figure 4(a) according to the treelet kernel is shown in Figure 4(b). Indeed, the only difference between those two molecules, besides the configuration around asymmetric carbons, is an oxygen atom replaced by a nitrogen atom. Thus all treelets, apart those which include the oxygen for the first molecule and the nitrogen for the second molecule, are identical. The third molecule (Figure 4(c)), is the most similar to the first molecule according to our stereo kernel, as they have a same minimal stereo subgraph. Since the treelet kernel considers as similar, molecules with very different optical rotation, it can not accurately predict this property. Unlike the treelet kernel, the stereo kernel provides a suitable measure of similarity when considering properties involving stereoisomerism, and thus allows to obtain a better prediction of optical rotation.

The second dataset is a dataset of synthetic vitamin D derivatives, used in [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF]. This dataset is composed of 69 molecules containing cycles, with an average of 9 stereocenters per molecule. The value to predict is their biological activity. This dataset has been selected since, like in many biological properties, stereoisomerism is an important feature of molecules. However, other molecular properties, non related to stereoisomerism may also partially determine biological properties of this dataset.

After normalizing the values of the dataset, the standard deviation of biological activities is equal to 0.258. To choose the different parameters and estimate the performance of each kernel on this dataset we use a nested cross-validation. The outer cross-validation is a leave-one-out procedure, used to compute an error for each molecule of the dataset. For each fold, we use another leave-one-out procedure on the remaining molecules, to compute a validation error. Parameters which provide the lowest root mean squared error on the validation are selected. We obtain for each molecule an error, and report in Table III, the mean of this distribution of errors together with the confidence interval at 95 % of this distribution.

As in our previous experiment, greatest errors in Table III are obtained by methods [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF], [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] which do not include stereo information. The adaptation of the tree pattern kernel to stereoisomerism [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] and our method improve the results over the two previous methods hence showing the insight of adding stereoisomerism information. For this dataset, the inclusion by [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] of information not related to stereoisomerism allows to obtain slightly better results than our method alone, since the biological property to predict is not only dependent of stereosiomerism. By combining our method with the treelet kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF], we obtain results as good as those obtained by method [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF]. To combine the two kernel, we multiply each subkernel of the treelet kernel by the stereo kernel. Hence, two molecules will be similar according to this new kernel if they have a similar set of stereo subgraphs and a similar set of treelets. We can note that the mean size of molecules on this dataset is about 3 times larger than on the previous one (Table II). However, the mean size of the minimal stereo subgraphs only slightly increases from 10.4 to 13.7. This last point illustrates the fact that the size of a stereo subgraph mainly depends on the variability of vertices and edges labels around its stereocenters and not on the size of the molecule. Nevertheless, a greater number of larger molecules increases the possibility of getting larger minimal stereo subgraphs as observed in Table II.

Execution times required to compute Gram matrices of the second dataset are displayed in Table IV. We do not discuss the execution times required to compute the Gram matrices of the first dataset, since this dataset is composed of a reduced number of molecules having only one stereocenter. The execution times required by our method on this dataset would thus be low but not sufficiently significant.

The first line of Table IV shows that the Tree pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] and its adaptation to stereoisomerism [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] take about 4 minutes to compute the whole Gram matrix. This important execution time may be partially explained by the polynomial complexity of this kernel. An additional and certainly more explicative reason of this important execution time comes from the use by this kernel of implicit bags of patterns. Such bags should be computed for each evaluation of a value of the kernel. On this particular dataset, the bag of each molecule is computed implicitly 69 times. On the contrary, the treelet kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] is based on a bag extraction algorithm with a linear complexity and the bag of treelets attached to each molecule is stored explicitly. Such a bag is thus computed only once for each molecule during the computation of the Gram matrix. The execution time required to compute the Gram matrix of the treelet kernel is consequently the lowest one. Finally our stereo kernel obtains an intermediate result of 83 seconds. This latter execution time, may be explained by the fact that although our kernel uses a subgraph isomorphism algorithm, these subgraphs are in practice of small size (Table II) hence leading to small execution times. Moreover, like the treelet kernel, our kernel is based on an explicit enumeration of patterns. The bag of stereo subgraphs describing each molecule is thus computed only once for each molecule during the computation of the Gram matrix.

VI. CONCLUSION

The study and the definition of new stereoisomers constitutes an important subfield of chemistry and thus a major challenge in chemoinformatics. Indeed, stereoisomers of some common drugs may be considered as violent poisons. For example, a molecule called thalidomide was sold in the late fifties as an anti nausea for pregnant women. However, it turns out that one of the stereoisomer of this molecule could cause fetal malformation. Up to now, only few methods have proposed pattern recognition methods taking explicitly into account stereoisomerism.

We have proposed in this paper, a graph kernel based on an explicit enumeration of all the stereo subgraphs of a molecule. Each stereo subgraph is associated to a stereo vertex and encodes the part of the graph which provides the stereo property to this vertex. Based on the notion of stereo subgraph we propose to describe a molecule by its bag of stereo subgraphs. The similarity between two molecules is then encoded through a graph kernel based on the similarity of both bags. Experiments on two datasets related to stereoisomerism properties demonstrate the relevance of our approach. In a future work we plan to investigate the insight provided by the addition to our kernel of larger subgraphs encoding relationships between each stereo subgraph and the remaining parts of a molecule.

Fig. 2 .

 2 Fig. 2. Two different spatial configurations of two carbons linked by a double bond.

Fig. 3 . 3 k=1- 1 s)

 331 Fig. 3. An asymmetric carbon and its associated sequence (H k C ) 3 k=1

Fig. 4 .

 4 Fig.[START_REF] Grenier | Treelet kernel incorporating chiral information[END_REF]. Three molecules of the first dataset with their optical rotations. The label of an atom is C if it is not specified.

TABLE I .

 I ROOT MEAN SQUARED ERROR (RMSE) OBTAINED BY 4 KERNELS IN PREDICTING THE OPTICAL ROTATIONS OF MOLECULES.

TABLE II

 II

	.	SIZE OF GRAPHS (|G|) AND SIZE OF MINIMAL STEREO
		SUBGRAPHS (|Hs|) IN THE TWO DATASETS
			Dataset 1	Dataset 2
			|G|	|Hs|	|G|	|Hs|
		Minimum size	14	6	68	10
		Maximum size	32	13	88	24
		Average size	21.3	10.4	76.9	13.7

TABLE III

 III

	.	PREDICTION OF THE BIOLOGICAL ACTIVITY OF
	SYNTHETIC VITAMIN D DERIVATIVES.
	Method		Mean Error	Confidence interval at 95%
	Tree patterns Kernel [1]	0.193	± 0.060
	Treelet Kernel [2]		0.207	± 0.064
	Tree patterns Kernel with stereo information [3]	0.138	± 0.043
	Stereo Kernel		0.141	± 0.047
	Stereo Kernel x Treelet Kernel	0.138	± 0.044

TABLE IV .

 IV EXECUTION TIMES REQUIRED TO COMPUTE THE 69 × 69 GRAM MATRICES OF OUR SECOND DATASET.

		Gram's matrices
	Method	computations (s)
	Tree patterns Kernel [1]	230
	Treelet Kernel [2]	7
	Stereo Kernel	86

VII. ACKNOWLEDGEMENTS

The authors wish to thank the association CRIHAN for their computing resource.


Charles-Michel Marle

A DIRECT PROOF OF MALUS' THEOREM USING THE SYMPLECTIC SRUCTURE OF THE SET OF ORIENTED STRAIGHT LINES

Keywords: 2000 Mathematics Subject Classification. -53D05, 53D12, 53B50, 7803 Geometrical Optics, Malus' Theorem, symplectic structuress, Lagrangian submanifolds

Louis Malus (X 1794) and Pierre Charles François Dupin (X 1801), in the hope that this school will in the future, as it did in the past, produce high level scientists and engineers rather than bankers and traders.

Introduction

Geometric Optics is a physical theory in which the propagation of light is described in terms of light rays. In this theory, the physical space in which we live and in which the light propagates is treated, once a unit of lenghth is chosen, as a three-dimensional Euclidean affine space E. In a transparent homogeneous medium occupying the whole physical space E, a light ray is described by an oriented straight line drawn in that space. When the transparent medium occupies only a part of E, a light ray, as long as it is contained in that medium, is described by an oriented segment of a straight line, but it will be convenient to consider the full oriented straight line which supports that segment. Reflections on smooth reflecting surfaces, or refractions through smooth surfaces separating two transparent media with different refractive indices, which transform an incident light ray into the corresponding reflected or refracted light ray, therefore appear as transformations, defined on a part of the set L of all oriented straight lines in E, with values in L.

The set L of all possible oriented straight lines drawn in the threedimensional Euclidean affine space E depends on four parameters: an oriented line L ∈ L being given, two parameters are needed to specify the unit vector -→ u parallel to and of the same orientation as L, and two more parameters, for example the coordinates of its intersection point with a transverse fixed plane, are needed to specify the position of L. We will prove below that L has the structure of a smooth four-dimensional symplectic manifold (1) .

Very often in Geometrical Optics one deals with the propagation of light rays which make a sub-family of the family of all possible light rays, smoothly depending on a number of parameters smaller than 4. For example, the family of light rays emitted by a luminous point in all possible directions, or the family of light rays emitted by a smooth luminous surface, each ray being emitted in the direction orthogonal to the surface, smoothly depend on 2 parameters. Let us state two definitions.

Definition 1.1. -The rank of a family of rays which smoothly depend on a finite number of parameters is the number of these parameters. Definition 1.2. -A rank 2 family of rays is said to be normal if at each point of the lighted part of the physical space E there exists a small piece of smooth surface orhtogonal to all the rays which meet it.

In [START_REF] Hamilton | Theory of systems of rays, Part First and Part Second[END_REF], Hamilton uses a slightly different terminology: he calls class the rank of a system of rays and orthogonal system a normal system of rays.

In an homogeneous and isotropic medium, the family of light rays emitted by a luminous point is a normal family: the spheres centered on the luminous point are indeed orthogonal to all rays. The family of rays emitted by a smooth luminous surface which, at each of its point, (1) More generally, the space of oriented straight lines in an n-dimensional Euclidean affine space is a 2(n -1)-dimensional symplectic manifold. emits a ray in the direction orthogonal to the surface, too is a normal family: it is indeed a well known geometric property of the straight lines orthogonal to a smooth surface.

Malus' theorem states that a rank 2 normal family of rays which propagates through an optical system made of any number of homogeneous and isotropic transparent media, with any number of smooth reflecting or refracting surfaces, always remains normal, in each of the media through which it propagates.

After a short presentation of its historical backgroud in Section 2, we give a direct proof of Malus' theorem which rests on symplectic geometry. We show in Section 3 that the set L of all oriented straight lines in the Euclidean affine space E is a smooth 4-dimensional manifold, naturally endowed with a symplectic 2-form ω.This symplectic form is the pull-back, by a diffeomorphism of L onto the cotangent bundle T * Σ to a two-dimensional sphere Σ, of the canonical symplectic form on that cotangent bundle. That diffeomorphism of L onto T * Σ is not uniquely determined: it depends on the choice of a reference point in E; but the symplectic form ω does not depend on that choice. In Section 4 we prove that reflection on a smooth surface is a symplectic diffeomorphism of one open subset of the symplectic manifold (L, ω) (made by light rays which hit the mirror on its reflecting side) onto another open subset of that manifold. Similarly, we prove that refraction through a smooth surface which separates two transparent media of refractive indices n 1 and n 2 is a symplectic diffeomorphism of one subset of L endowed with the symplectic form n 1 ω onto another open subset of that space endowed with the symplectic form n 2 ω. In Section 5 we prove that a rank 2 family of rays is normal if and only if it is a Lagrangian submanifold of (L, ω). We conclude in Section 6: since a symplectic diffeomorphism maps Lagrangian submanifolds onto Lagrangian submanifolds, Malus' theorem immediately follows from the results obtained in previous Sections.

For much more elaborate applications of symplectic geometry in Optics, the readers are referred to [START_REF] Arnold | Mathematical methods of classical mechanics[END_REF] (Chapter 9, Section 46, pp. 248-258 and Appendix 11, pp. 438-439) and [START_REF] Guillemin | Symplectic techniques in physics[END_REF] (Introduction, pp. 1-150).

Historical background

Étienne Louis Malus (1775-1812) is a French scientist who investigated geometric properties of families of straight oriented lines, in view of applications to light rays. He developed Huygens undulatory theory of light, discovered and investigated the phenomenon of polarization of light and the phenomenon of double refraction of light in crystals. He participated in Napoleon's disastrous expedition to Egypt (1798-1801) where he contracted diseases probably responsible for his early death. He proved [START_REF] Malus | [END_REF] that the family of rays emitted by a luminous point source (which, as we have seen above, is normal) remains normal after one reflection on a smooth surface, or one refraction through a smooth surface but he was not sure [START_REF] Malus | Traité d'optique[END_REF] whether this property remains true for several reflections or refractions (2) . His works on families of oriented straight lines were later used and enhanced by Hamilton.

For reflections, a very simple geometric proof of Malus' theorem was obtained by the French scientist Charles Dupin [START_REF] Dupin | Applications de la géométrie[END_REF]. For this reason, in French Optics manuals [START_REF] Courty | Université Pierre et Marie Curie, L3 Physique[END_REF], Malus' theorem is frequently called Malus-Dupin's theorem. According to [START_REF] Conway | Appendix Editors to Sir William Rowan Hamilton mathematical Works[END_REF], Quetelet and Gergonne gave a full proof of Malus' theorem for refractions in 1825. Independently, the great Irish mathematician William Rowan Hamilton (1805-1865) gave a proof of this theorem, both for reflections and for refractions, in his famous paper [START_REF] Hamilton | Theory of systems of rays, Part First and Part Second[END_REF]. His proof rests on the stationarity properties of the optical length of rays, with respect to infinitesimal displacements of the points of reflections or of refractions, on the reflecting or refracting surfaces.

Charles François Dupin (1784-1873) is a French mathematician and naval engineer. Several mathematical objects in differential geometry bear his name: Dupin cyclids (remarkable surfaces he discovered when he was a young student at the French École Polytechnique), Dupin indicatrix (which describes the local shape of a surface). It is said in Wikipedia [START_REF] Wikipedia | [END_REF] that he inspired to the poet and novelist Edgar Allan Poe (1809-1849) the figure of Auguste Dupin appearing in the three detective stories: The murders in the rue Morgue, The Mystery of Marie Roget and The Purloined Letter.

3. The symplectic structure of the set of oriented straight lines Proposition 3.1. -The set L of all possible oriented straight lines in the affine 3-dimensional Euclidean space E has a natural structure of smooth 4-dimensional manifold, is endowed with a symplectic form ω and is diffeomorphic, by a symplectic diffeomorphism, to the cotangent bundle T * Σ to a 2-dimensional sphere Σ .

Proof. -Let indeed Σ be a sphere of any fixed radius R (for example R = 1) centered on a point C ∈ E and O be another fixed point in E. Of course we can take O = C, but for clarity it is better to separate these two points. An oriented straight line L determines a unique point m ∈ Σ such that the vector -→ u = --→ Cm is parallel to and of the same direction as L, -a unique linear form η on the tangent space T m Σ at m to the sphere Σ, given by

η( -→ w ) = -→ OP • -→ w for all -→ w ∈ T m Σ ,
where P is any point of the line L, and where -→ OP • -→ w denotes the scalar product of the vectors -→ OP and -→ w . The pair (m, η) is an element of the cotangent bundle T * Σ. In fact m being determined by η, we can say that η is an element of T * Σ.

Conversely, an element η ∈ T * Σ, i.e. a linear form η on the tangent space to Σ at some point m ∈ Σ, determines an oriented straight line L, parallel to and of the same direction as -→ u = --→ Cm. This line is the set of points P ∈ E such that -→ OP • -→ w = η( -→ w ) for all -→ w ∈ T m Σ .

There exists ([10] p. 59, [START_REF] Laurent-Gengoux | Poisson structures[END_REF] p. 176) on the cotangent bundle T * Σ a unique differential one-form λ Σ , called the Liouville form, whose exterior differential dλ Σ is a symplectic form on T * Σ. The above described 1-1 correspondence between the set L of all oriented straight lines and the cotangent bundle T * Σ allows us to transport on L the differentiable manifold structure, the Liouville one form λ Σ and the symplectic form dλ Σ . So we get on L a differential one-form λ O and a symplectic form ω = dλ O . Therefore (L, ω) is a symplectic manifold.

The diffeomorphism so obtained, the one-form λ O and its exterior differential ω = dλ O do not depend on the choice of the centre C of the sphere Σ (with the obvious convention that two spheres of the same radius centered on two different points C and C ′ are identified by means of the translation which sends C on C ′ ). However, this diffeomorphism depends on the choice of the point O, and so does the one-form λ O : when, to a given straight line L, the choice of O associates the pair (m, η) ∈ T * Σ, the choice of another point O ′ associates the pair m, η

+ df O ′ O (m) , where f O ′ O : Σ → R is the smooth function defined on Σ f O ′ O (n) = --→ O ′ O • -→ Cn , n ∈ Σ . Therefore, if the choice of O determines on L the one-form λ O , the choice of O ′ determines the one-form λ O ′ = λ O + d(f O ′ O • π Σ )
where π Σ : T * Σ → Σ is the canonical projection. The symplectic form ω on the set of all oriented straight lines L does not depend on the choice of O, nor on the choice of C, since we have

ω = dλ O = dλ O ′ because d • d = 0 . Proposition 3.2. -Let ( -→ e 1 , -→ e 2 , -
→ e 3 ) be an orthonormal basis of the Euclidean vector space -→ E associated to the affine Euclidean space E. Any oriented straight line L ∈ L can be determined by its unit directing vector -→ u and by a point P ∈ L (determined up to addition of a vector collinear with -→ u ). Expressed in terms of the coordinates (p 1 , p 2 , p 3 ) of P in the affine frame (O, -→ e 1 , -→ e 2 , -→ e 3 ) and of the components (u 1 , u 2 , u 3 ) of -→ u , the symplectic form ω is given by

ω = 3 i=1 dp i ∧ du i .
Proof. -Using the definition of the Liouville one-form on T * Σ, we see that

λ 0 = 3 i=1 p i du i .
Therefore

ω = dλ O = 3 i=1 dp i ∧ du i . Remark 3.3.
-The three components u 1 , u 2 , u 3 of -→ u are not independent, since they must satisfy 3 i=1 (u i ) 2 = 1. The point P ∈ L used to detemine the oriented straight line L is not uniquely determined, since by adding to P any vector collinear with -→ u we get another point in L. However, these facts do not affect the validity of the expression of ω given above.

Remark 3.4. -The symplectic form ω can be expressed very concisely by using an obvious vector notation combining the wedge and scalar products: Proof. -Any oriented straight line L 1 which hits the mirror M is determined by

ω(P, - → u ) = d -→ P ∧ d -→ u .
the unit vector -→ u 1 parallel to and of the same direction as L 1 , -the incidence point P ∈ M of the light ray on the mirror. We will write -→ P for the vector -→ OP , the fixed point O being arbitrarily chosen.

The reflected ray L 2 is determined by the unit vector -→ u 2 , given in terms of -→ u 1 by the formula

-→ u 2 = -→ u 1 + 2( -→ u 1 • -→ n ) -→ n ,
where -→ n is a unit vector orthogonal to the mirror M at the incidence point P , with anyone of the two possible orientations; -the same point P ∈ M on the mirror. According to the expression of the symplectic form ω given in the last Remark, we have to check that d

-→ P ∧ d -→ u 2 = d -→ P ∧ d -→ u 1 . We have d -→ P ∧ d( -→ u 2 --→ u 1 ) = 2d -→ P ∧ d ( -→ u 1 • -→ n ) -→ n = -2d ( -→ u 1 • -→ n )( -→ n • d -→ P ) = 0 , because -→ n • d -→ P = 0, the differential d -→
P lying tangent to the mirror M, while the vector -→ n is orthogonal to the mirror. Proposition 4.2. -Let R be a smooth refracting surface, which separates two transparent media with refractive indexes n 1 and n 2 . Let Refrac R be the map which associates, to each light ray L 1 which hits the refracting surface R on the side of refracting index n 1 , the corresponding refracted ray L 2 = Refrac R (L 1 ) determined by Snell's law of refraction. The map Refrac R is a symplectic diffeomorphism defined on an open subset of (L, n 1 ω), (the set of oriented straight lines which hit R on the n 1 side and, if n 1 > n 2 , are not totally reflected) with values in an open subset of (L, n 2 ω).

Proof. -Any oriented straight line L 1 which hits the refracting surface R is determined by the unit vector -→ u 1 parallel to and of the same direction as L 1 , -the incidence point P ∈ R of the light ray on the refracting surface.

We will write -→ P for the vector -→ OP , the fixed point O being arbitrarily chosen.

The refracted ray L 2 is determined by the unit vector -→ u 2 , related to -→ u 1 by the formula

n 2 -→ u 2 -( -→ u 2 • -→ n ) -→ n = n 1 -→ u 1 -( -→ u 1 • -→ n ) -→ n ,
where -→ n is a unit vector orthogonal to the refractig surface R at the incidence point P , with anyone of the two possible orientations; -the same point P ∈ R on the refracting surface.

We have to check that n

2 d -→ P ∧ d -→ u 2 = n 1 d -→ P ∧ d -→ u 1 . We have d -→ P ∧ (n 2 d -→ u 2 -n 1 d -→ u 1 ) = d -→ P ∧ d n 2 ( -→ u 2 • -→ n ) -→ n -n 1 ( -→ u 1 • -→ n ) -→ n = -d n 2 ( -→ u 2 • -→ n ) -n 1 ( -→ u 1 • -→ n ) ( -→ n • d -→ P ) = 0 , because -→ n • d -→ P = 0, the differential d -→
P lying tangent to the refracting surface R, while the vector -→ n is orthogonal to R. For each value of (k 1 , k 2 ), the ray L(k 1 , k 2 ) can be determined by

-a point P (k 1 , k 2 ) of the ray L(k 1 , k 2 ), -the unit director vector -→ u (k 1 , k 2 ) of the ray L(k 1 , k 2 ) Although P (k 1 , k 2 )
is not uniquely determined, we can arrange things so that the map

(k 1 , k 2 ) → P (k 1 , k 2 ), -→ u (k 1 , k 2 ) is smooth. By assump- tion it is everywhere of rank 2.
The reciprocal image of the symplectic form ω of L by the map

(k 1 , k 2 ) → P (k 1 , k 2 ), - → u (k 1 , k 2 ) is ∂ -→ P (k 1 , k 2 ) ∂k 1 • ∂ -→ u (k 1 , k 2 ) ∂k 2 - ∂ -→ P (k 1 , k 2 ) ∂k 2 • ∂ -→ u (k 1 , k 2 ) ∂k 1 dk 1 ∧ dk 2 ,
where, as before, we have written

-→ P (k 1 , k 2 ) for -→ OP (k 1 , k 2 )
, the origin O being any fixed point in E.

Using the symmetry property of the second derivatives

∂ 2 -→ P (k 1 , k 2 ) ∂k 1 ∂k 2 = ∂ 2 -→ P (k 1 , k 2 )
∂k 2 ∂k 1 we see that the reciprocal image of ω can be written

∂ ∂k 2 -→ u • ∂ -→ P ∂k 1 - ∂ ∂k 1 -→ u • ∂ -→ P ∂k 2 dk 1 ∧ dk 2 .
where we have written -→ u and -→ P for -→ u (k 1 , k 2 ) and -→ P (k 1 , k 2 ). Our rank 2 family of rays is a Lagrangian submanifold of (L, ω) if and only if the reciprocal image of ω vanishes, i.e., if and only if

∂ ∂k 2 -→ u • ∂ -→ P ∂k 1 = ∂ ∂k 1 -→ u • ∂ -→ P ∂k 2 ,
or if and only if there exists locally a smooth function

(k 1 , k 2 ) → F (k 1 , k 2 ) such that -→ u • ∂ -→ P ∂k 1 = ∂F ∂k 1 , -→ u • ∂ -→ P ∂k 2 = ∂F ∂k 2 . ( * )
Let us now look at the necessary and sufficient conditions under which there exists locally, near a given ray of the family, a smooth surface orthogonal to all the neighbouring rays of the family. This surface is the image of a map

(k 1 , k 2 ) → P (k 1 , k 2 ) + λ(k 1 , k 2 ) -→ u (k 1 , k 2 ) , where (k 1 , k 2 ) → λ(k 1 , k 2 ) is a smooth function.
This surface is orhtogonal to the rays if and only if the function λ is such that

-→ u (k 1 , k 2 ) • d -→ P (k 1 , k 2 ) + λ(k 1 , k 2 ) -→ u (k 1 , k 2 ) = 0 . The equalities -→ u (k 1 , k 2 ) • d -→ u (k 1 , k 2 ) = 0 and -→ u (k 1 , k 2 ) • -→ u (k 1 , k 2 ) = 1 allow us to write this condition as -→ u (k 1 , k 2 ) • d -→ P (k 1 , k 2 ) + dλ(k 1 , k 2 ) = 0 . ( * * )
We see that when there exists a smooth function F which satifies ( * ), all functions λ = -F + Constant satisfy ( * * ), and conversely when there exists a smooth function λ which satisfies ( * * ), all functions F = -λ + Constant satisfy ( * ). A rank 2 family of rays is therefore normal il and only if it is a Lagrangian submanifold of L.

Malus' Theorem

Since reflections and refractions are symplectic diffeomorphisms, and since by composing several symplectic diffeomorphisms we get again a symplectic diffeomorphism, the travel of light rays through an optical device with any number of reflecting or refracting smooth surfaces is a symplectic diffeomorphism. The image of a Lagrangian submanifold by a symplectic diffeomorphism is automatically a Lagrangian submanifold. We therefore can state as a theorem the following result, very remarkable by the fact that no assumption other than their smoothness is made about the shapes of the reflecting or refracting surfacesse surfaces. It is only assumed that these surfaces are smooth and that the reflections or refractions obey the well-known laws of Optics. Theorem 6.1 (Malus' Theorem). -A two parameter normal family of light rays remains normal after any number of reflections on smooth reflecting surfaces or refractions across smooth surfaces which separate transparent media with different refractive indexes.

Acknowledgements

I address my warmest thanks to Géry de Saxcé for offering me to present a talk at the 58-th Souriau Colloquium, and for all the efforts he made and is still making for the success and the perennity of these colloquia.

I am indebted to Dominique Flament, who recently gave me the opportunity to present at his seminar Histoires de Géométries the works of William Rowan Hamilton on Geometrical Optics. It was in preparing my talk for this seminar that I learnt about Malus' theorem and tried to find a direct proof founded in symplectic geometry.

4 .

 4 Reflection and refraction are symplectic diffeomorphisms Proposition 4.1. -Let M be a smooth reflecting surface. Let Reflec M be the map which associates to each light ray L 1 which hits M on its reflecting side, the reflected light ray L 2 = Reflec M (L 1 ). The map Reflec M is a symplectic diffeomorphism defined on the open subset of the symplectic manifold (L, ω) made by light rays which hit Mon its reflecting side, onto the open subset made by the same straight lines with the opposite orientation.

5 .

 5 Normal families are Lagrangian submanifolds Proposition 5.1. -A rank 2 family of oriented straight lines is normal (in the sense of Definition 1.2) if and only if it is a Lagrangian submanifold ([10] p. 92, or [11] p. 123) of the symplectic manifold (L, ω) of all oriented straight lines. Proof. -Let us consider a rank 2 family of oriented straight lines. Locally, in a neighbourhood of each of its straight lines, the family can be determined by a smooth map (k 1 , k 2 ) → L(k 1 , k 2 ), defined on an open substet of R 2 , with values in the manifold L of oriented straight lines.

[START_REF] Conway | Appendix Editors to Sir William Rowan Hamilton mathematical Works[END_REF] This is an illustration of the famous Arnold theorem: when a theorem or a mathematical concept bears the name of a scientist, it is not due to that scientist. Arnold added: of course, that theorem applies to itself!


Sophie Derrot
email: sophie.derrot@bnf.fr

Clément Oury
email: clement.oury@bnf.fr

Keywords:

Even though the ebooks market has developed more slowly in France than in other countries, especially in northern America and northern Europe, the number of titles proposed is now increasing. The ebook production and distribution chain has been clarified, while major standard ebooks formats (EPUB, PDF) and metadata schemes (ONIX) have emerged. A growing number of French citizens are currently using ebooks to access knowledge, culture and entertainment. Being able to collect this new kind of resource in order to preserve it in the long term has thus become a major challenge for the national library of France.

In order to tackle this issue and to set up a complete ebook deposit workflow, the Bibliothèque nationale de France (National Library of France or BnF) benefits from its experience in managing digital documents (for its digital library, Gallica) and from its tradition of legal deposit. It also seeks to capitalise on the long-standing relationships it has built with the publishers and the ebooks distributor. However, the Library needs to deal with the dual nature of ebooks, which are on one hand digital documents, collected in the name of the internet legal deposit, and on the other hand a new form of a kind of document that has been acquired by the library for centuries. This paper aims to present the questions that the BnF needed to answer when faced with the need of collecting ebooks, and the solution it is currently adopting. Technical implementation has just begun and the outcomes -a complete entry, cataloguing, access and preservation workflow -are expected at the end of 2014 or the beginning of 2015.

A favourable context

The late emergence of an ebook market in France At the very beginning of 2000, French media announced the birth a totally new kind of publication: the electronic book or ebook. Devices called "Softbook", "Cybook" or even "Rocket e-Book" were supposed to change the publishing industry and promote a brand new way of reading: the screen was expected to replace paper. French companies were in many cases leading this so-called revolution. However, of the numerous devices that were launched at the beginning of the 21th century, very few survived. Too complex, too expensive, they came in fact too early and were not able to create a market beyond a very narrow circle of early adopters. The economic failure of the first generation of ebook devices had a strong impact on the future development of ebook market in France: the good old trustworthy book was therefore, for at least a decade, considered by most French readers and many publishers far more reliable than its electronic cousin. Progressively, technological innovation (such as the use of e-ink) and the increasing popularity of new kinds of devices, such as tablets, led to an evolution of this situation of distrust. The French market changed. New purely online publishers appeared. The bestestablished publishers started delivering their books directly in both forms. They launched the digitization of their older collections, often fostered by financial support from the State. Standardization became a driver of technological innovation: the jungle of formats was progressively cleared in favour of a few reference formats: PDF for computers and tablets, EPUB and its proprietary equivalents (such as KF8 and iBooks) for ebook readers. On the back-office side, standardization of exchange of metadata is under way, thanks to the wide adoption of the ONIX format [START_REF] Illien | The state of e-legal deposit in France: looking back at five years of putting new legislation into practice and envisioning the future[END_REF] . Finally, standardization is also taking place from the point of view of the ebook production and selling channel. Schematically, three main stakeholders have emerged.

Current ebook production and distribution chain

At the beginning of the chain, the publisher is in charge of producing the book: intellectual production (relationships with authors) and "material" production of the book in its paper or electronic form (this part may also be outsourced to a contractor). At the other end of the chain, the digital bookseller is in charge of promoting and selling the ebook to readers. In the middle, the role of the e-distributor is to make a bridge between these two stakeholders: it receives the ebook from the publisher, checks its format, verifies and enhances the quality of its metadata, and sends it to the bookseller. The e-distributor is also frequently in charge of managing the financial flows between the different links of the chain. This summary does not encompass all the complexities and subtleties of the actual production system, and this distribution of roles is always subject to change. However, the respective responsibilities of each actor are today better defined than in previous years.

Compared to its international equivalents, especially in northern America and northern Europe, the ebook market in France is not yet mature. The imbalance between the availability of books in printed and in electronic form is lessening, but there is still a strong difference in terms of demand. However, several figures are showing a positive trend: in March 2014, a poll indicated that 15 % of French citizens were reading ebooks, compared to 5 % two years before [START_REF] Oury | When press is not printed: the challenge of collecting digital newspapers at the Bibliothèque nationale de France[END_REF] . Thus, a growing number of French citizens is using ebooks to access knowledge, [START_REF] Illien | The state of e-legal deposit in France: looking back at five years of putting new legislation into practice and envisioning the future[END_REF] ONIX for Books, an XML standard designed to support computer-to-computer communication of bibliographic information. See http://www.editeur.org/83/Overview/ 2 Regular polls about ebooks usage and practices are funded by three of the main professional stakeholders in the books chain: the SOFIA, the SNE, and the SGDL. See culture and entertainment. Being able to collect this new kind of resource in order to preserve it in the long run has thus become a major issue for the national library of France.

Management of digital material at the BnF: from digitization to digital legal deposit

Management of digital documents is not a new task at the BnF. The library has been involved in the field of digitization since 1992 through its digital library, Gallica. Gallica has now reached nearly 2 million documents: books and periodicals, newspapers, engravings, manuscripts, objects, sound recordings, audiovisual material. The BnF is also in charge of receiving digital documents through legal deposit. Legal deposit is a long-standing mission of the Library. It was first established for printed books in 1537, by the Renaissance king François Ier, a lover of art and literature. Over the centuries, the legislation has evolved to cover different publication types and forms, thus adjusting to all major technological and social changes. This is particularly true during the 20th and 21st centuries, when the development of many media innovations created new forms of publication, which have gradually been included in the scope of legal deposit legislation. The BnF received its first digital resources when audio and video material, subject to legal deposit respectively since 1938 and 1975, become distributed in digital form (on CDs and then on DVDs). In 1992, an extension of the law covered the case of software and databases. Finally, on 1st August 2006, the most recent evolution included all publications of the French Internet in the scope of the legal deposit -this law is now part of the "Heritage code" [1].

Internet legal deposit covers all kinds of resources distributed online: from news websites to public parts of social networks, from institutional portals to blogs. Indeed, legal deposit refuses to select the documents to be preserved according to their intellectual or artistic value. However, this new extension brings two fundamental changes to the principles of legal deposit. First, the term "deposit" itself is not really relevant anymore. The BnF (along with the National Audiovisual Institute, or INA, for websites related to TV and radio) is in charge of collecting documents by automated means. Harvesting software, known as a "robot", is used to retrieve content online. Second, comprehensiveness, which is the traditional objective of legal deposit, is not an achievable goal anymore, as the library is faced with the huge and ever-changing space of the internet. Instead of comprehensiveness, the BnF follows an objective of representativeness: it seeks to constitute a collection that mirrors what is available online at a given date. A combination of broad crawls of the .fr domain and focused crawls of websites selected by BnF librarians or partner organizations has been put in place in order to achieve this goal [START_REF] Aparsen | Report on DRM Preservation[END_REF] .

As most ebooks are promoted and sold online, they are supposed to enter BnF holdings through the legal deposit of the internet [START_REF] Derrot | Preservation is Knowledge: A community-driven preservation approach[END_REF] . So, from a legal point of view, ebooks have clearly the same status as any other publications hosted online. However, from an ontological point of view, they are digital equivalents of a kind of documents acquired by the library for centuries. This dual nature of ebooks -electronic and books -explains why the BnF decided to dedicate them a specific entry and treatment channel, different from the one of web http://www.sne.fr/img/pdf/SDL/2012/Barometre_SofiaSneSgdl_Les%20usagesdulivrenumerique_mars2012.pdf and http://www.sne.fr/img/pdf/Evenements/Assises/Assises-21mars2014/Barometre-SNE-Sofia-SGDL-desusages-du-livre-numerique-21-03-2014.pdf. [START_REF] Aparsen | Report on DRM Preservation[END_REF] See Sylvie Bonnel and Clément Oury, "La sélection de sites web pour une bibliothèque encyclopédique", to be published in the proceedings of the IFLA 2014 Conference in Lyon. [START_REF] Derrot | Preservation is Knowledge: A community-driven preservation approach[END_REF] Ebooks that are delivered to the public on physical media (e.g. CD, USB key…) already enter BnF collections through audiovisual legal deposit. But this currently represents a very small part of the ebooks market.

archives. Thus, the library built upon its triple experience of receiving printed books, of producing digitized books, and of collecting online publications in order to design a complete ebooks deposit workflow.

First experiments in the collection of digital publications

The first experiments towards the collection of digital publications at the BnF started around 2000, even before the law was changed. These investigations were performed within the digital library department, which was also in charge of managing Gallica. The two ways of getting digital content were investigated by BnF librarians: automated harvesting of internet content and direct deposit by newspapers or ebooks publishers. However, the first approach (online harvesting) was quickly considered a priority and most effort was put into setting up a complete web archiving workflow. Several reasons explain this choice. First, websites were seen as the most at-risk document; the web was a very young publishing space and it appeared critical to preserve its earliest forms. They were also practical reasons. On one hand, thanks to international cooperation, tools for web archiving were already available; on the other hand, few ebooks were available, the ebook distribution chain itself was not mature and deposit solutions were not considered stable enough. There were finally legal constraints. In France, laws voted by the Parliament are enforced by a decree. The decree on digital legal deposit was only published in December 2011. So, between 2006 and 2011, there was a legal possibility to harvest freely available content (such as the huge majority of websites), but no means to ask publishers to deposit content distributed under payment, such as ebooks. This explains why the BnF did not start designing its ebook deposit workflow before 2012.

The BnF approach to the legal deposit of ebooks

Cooperation as a key

Cooperation with publishers was immediately identified as a critical element in order to build an efficient and durable system. The BnF benefited from its long-standing relationship with the Syndicat National de l'Édition (SNE), the main union of French publishers. In September 2012, during a meeting between representatives of SNE, BnF and the French ministry of Culture, it was decided to set up two joint working groups:

-a legal working group, whose mandate is to identify if the current decree on internet legal deposit takes sufficiently into account the specificities of ebooks; -a technical or functional working group, which is in charge of designing the principles of a deposit system.

The functional working group started in March 2013. Its first decisions were related to the way of retrieving content: a system of direct deposit was preferred to web harvesting. The BnF could have chosen to crawl ebook hosting platforms, as it currently does for news websites [2]. However, in several cases, ebooks distributed online are not directly hosted on the website of the online bookstore. The bookstore is only the place where financial transaction occurs; the document itself, or a link to download it, is then sent to the purchaser by another means (e.g. by email). In that case, web harvesting would not have been efficient. Moreover, harvesting ebook hosting platforms would have made it impossible to benefit from the relationships established between the library's teams in charge of the deposit of printed documents and the publishers. Here therefore, the principles in use for printed books legal deposit prevailed over the logic of internet harvesting: in "traditional" legal deposit, booksellers are not in charge of sending documents to the library; neither should they be for digital legal deposit.

The functional joint working group thus preferred leaving the publisher in charge of the deposit. However, for practical reasons, it was proposed that a publisher could give a mandate to its e-distributor to actually perform the deposit. For the BnF, working with distributors appeared very quickly as the best solution as:

• there are few distributors compared to hundreds of publishers; • the BnF benefits from a first set of quality controls performed by distributors, both for the ebooks and their metadata; • distributors receive ebooks without DRM; they are therefore able to send them to the library without DRM (see below).

Analyzing existing (internal and external) transmission channels

The discussions of the joint working group were complemented by several enquiries performed by a dedicated team at BnF, grouping together experts from the legal deposit and IT departments.

This group interviewed the main French distributors, as they were supposed to become the first ones to perform actual deposits. It studied the data and metadata formats they were using, how they were transmitting content, and what they could send to the Library. At the same time, the group also performed an analysis of the BnF internal entry chains for digital documents (documents from BnF holdings digitized by private contractors; audio and video documents, master versions of books sent by publishers to BnF for visually impaired people5 , etc.). The goal of this enquiry was to identify what tools, what entry tracks already developed for similar kind of documents could be re-used for an ebooks deposit workflow. These studies led to the design of a first draft of a deposit workflow in the summer of 2013. More detailed analyses followed during the second semester of the year; their conclusions will be presented below. Concrete developments started in the first months of 2014.

Implementation: a work in progress

Defining the scope As already stated, the landscape of commercialized ebook formats, which was quite dense a few years ago, has tended to become simplified, to the advantage of standardized formats (EPUB) or closed-source formats of the market leaders. Even if it does not solve every issue, this simplification is welcome from a legal deposit point of view, as the 2006 law theoretically extends the perimeter of the objects concerned to all produced and commercialized formats.

The efforts are concentrated on files which can be easily defined as "books" as they share the characteristics of printed books. Therefore, ebooks in formats such as TXT or DOC were excluded from the beginning, as they are more often production formats than publication formats; they are not found in commercial markets and distributors do not work with them.

At the other end of the ebook chain of production, physical reading devices and their software are not concerned either by this deposit track. As discussed below, DRM and closed-source formats too have to be excluded from the process. Once these exclusions have been made, what is left? During the initial discussions, publishers and distributors made clear that the most frequently produced and sold formats were EPUB 2 and PDF; MOBI and EPUB 3 were currently in the minority. PDF and EPUB (versions 2 and 3, fixed-layout and reflowable) are therefore the main target.

First step: receiving ebooks with metadata

Distributors should depose their files on a dedicated FTP platform in the form of a ZIP file, containing both data files (EPUB or PDF) and metadata files (one or more ONIX files). These files come with their MD5 checksum, for the BnF to check their integrity throughout the process. Once these ZIP files are deposed, a first set of checks will be performed by the library, such as virus checks, verification that the files declared are really in the delivered package, etc. They are then opened and their content is more carefully processed. Before admission into the library's collections, a waiting period is defined to allow each distributor to send any bibliographical and/or technical updates to the file and/or its metadata. Once the delay for potential updates has passed and if the package that has been delivered passes the checks, the ebooks receive a legal deposit number and the distributor is informed that the document has been deposited. One application supervises the whole process, from the reception of the documents to access and expert cataloguing. This ensures information exchanges between the different applications involved and give the process its consistency.

Metadata flow: automation and conversion are the keys

The guiding principle when putting in place the legal deposit of ebooks was automation, including the re-exploitation of metadata created by publishers and distributors for their own needs. The most used format for carrying this metadata in the book trade are ONIX files, which are generally created by distributors from information provided by publishers and are then sent to online booksellers along with ebook files. The advantages of ONIX files attached to ebooks by the distributors are their richness and precision: this information has to be exact because of its commercial purpose. On the other hand, quite a few of the data are useless from a librarian point of view (for example, prices for every country where the ebook is commercialized) and some important bibliographic metadata is often lacking (the ISBN of the printed version is not always provided). To make existing ONIX files as useful as possible for the library, an ONIX model including the BnF specifications was defined by librarians and proposed to publishers and distributors.

As soon as a book has passed all the checks in the delivery zone, its metadata is processed by the entry application. Among other things, this application converts information within the ONIX file from XML to Intermarc, the specific format for bibliographic metadata used by the BnF. Information given by the distributors should be published within the BnF catalogue and be distributed under an Open License. This bibliographic record is quite rich, as information from the ONIX file is fairly detailed (title, author, publisher, but also abstract, author's biographical note, keywords, etc.). In a second phase of the project, the automatic creation of links will allow a relation to be established between for example the records for two formats of the same work (printed and EPUB, EPUB and PDF) thanks to the ISBN which publishers will hopefully provide within the ONIX file. Using the same principle, ISNI identifiers could be used to link ebook bibliographical records to authority records.

All these steps are designed to be automated. For some deposited ebooks, bibliographical records will partially be reworked by cataloguers and will gain more precision. Records from the BnF catalogue are already largely reused by other libraries: ebooks metadata is rather eagerly awaited, as there is currently no specific database for such bibliographical metadata as for printed books. Even publishers are interested in getting this enriched metadata back, to improve their own bibliographical databases.

Data flow: preservation at the heart of the system

Contrary to the metadata files, the ebooks files will not be converted in any way and the original file will be the one that is preserved. Legal deposit is indeed attached to the format of the document and this format has to be kept in its original form.

As already shown, ebook files pass a first set of tests at moment they are deposited on the FTP platform to check their integrity and format. A validation tool developed by the International Digital Publication Forum (IDPF), EPUBCheck, will be used for EPUB files, but the choice has still to be made for PDF. The purpose of these tests is to check if the files are in fact able to be managed by the library: DRM and closed-source formats will not be accepted by the system, both for preservation and access reasons.

The main reason that ebooks with DRM will be excluded is to permit manipulation of the files during the deposit process. Frequent copies -often blocked by DRM -are de facto necessary for deposit, access and preservation processes 6 : setting up a legal deposit system of this kind of protected material didn't seem feasible. Publishers and distributors agreed to this pragmatic position. Closed source formats will not be deposited for the same reasons: preservation systems will probably be unable to deal with them, especially in the long term, 6 About issues of preserving digital resources with DRMs, see [3]. and access solutions would be difficult to implement. In spite of the ambiguity of this position -in contradiction with the traditional objective of comprehensiveness of legal deposit -, it seemed more reasonable to proceed in this way in order to ensure long-term access and preservation -which are also part of the objectives of legal deposit.

Once the ebook files enter the BnF collections, they will be prepared for ingest by the library's digital repository, SPAR (Scalable Preservation and Access Repository) 7 . A dedicated preingest module will be developed for the "Negotiated legal deposit track". The legal deposit is considered to be "negotiated" as the form of the delivery is negotiated between the distributor and the library, so that for example not all formats will be accepted. This module will get the package ready for ingest, by joining together the ebook file (EPUB or PDF), the original ONIX file, possibly a picture file of the book cover, and finally the METS manifest 8 . The role of the SPAR system in the legal deposit workflow is critical. On one hand, the preingest module will provide fundamental information to the General Catalogue, such as the ARK number of the ebook file, i.e. its persistent identifier. On the other hand, SPAR will deliver the deposited ebooks to the access platform and application.

Within SPAR itself, two channels will be set up, according to the ebook format and its components:

• Ebooks whose format is considered "managed" after all quality checks and characterization will be ingested in the first channel. • Files that are valid from a format specification point of view but which present some preservation threats will be ingested in the second channel. For example, EPUB files containing Flash or Javascript elements are not considered "managed" as BnF does not have sufficient confidence in its capability to preserve them in the long term.

7 About SPAR, see [4]. 8 METS (Metadata Encoding and Transmission Standard) is an XML format. METS files are wrappers that contain all metadata elements necessary to describe a digital document and preserve it in the long run. Therefore, the documents won't be available for access before they are ready to be preserved long-term. It is only when the digital repository has treated them that an availability flag will be sent to the catalogue and to the access application.

Access to legal deposit materials is legally restricted to research areas of the library and only authorised persons have the possibility to consult them. The restriction applies to both printed and digital material, including web archives and in the future deposited ebooks. A specific application of the digital library, "Gallica intra muros", provides access to restricted digital material (i.e. under copyright) and is not available outside the library reading rooms.

As security is a central concern of both the library and its partners, this aspect of Gallica intra muros has been reinforced. The chosen solution is a "virtual browser" which gives access to material without any possibility for the user to download or modify them. Both PDF and EPUB will be available in the same application, among the other copyrighted digital collections of the library.

The evolution of formats and reading tools will be a crucial point in the coming years. A strong dialogue with partners will be necessary to follow their practices. In addition, the participation of the BnF in international bodies such as IDPF could be a good solution to keep up to date with evolutions in access, as the library already does for preservation matters.

The role of humans: still an open question

It is not currently possible to know what level of human work will be involved in this workflow: will a human quality control be performed on some ebooks before they enter BnF collections? What percentage of books will be catalogued by librarians, if any? What level of quality will be acceptable for catalogue records?

In any case, management of digital along with printed books will represent a dramatic change for the professionals of the legal deposit department. In order to assist them in this evolution, the department launched a series of training sessions called "digital workshops". All members of the legal deposit department are requested to attend these, which deal with questions such as "what is an ebook?" "How does one produce/buy/read/preserve such documents?". This first round of training is intended to give everyone a common basic level of knowledge and awareness regarding e-publications. A second step would be to train them to actually receive, verify and catalogue ebooks -but this will come later, when the critical questions related to the level of human implication in the ebooks workflow have been decided.

Conclusion: lessons learnt and next steps

Developments have already begun and the whole chain should be ready at the end of 2014 or the beginning of 2015. First experiments with volunteer distributors will be carried out at the end of the year. The involvement of publishers and distributors is the first strength of this project. This brings the possibility for the library has to work with a new kind of professionals. Some publishers or distributors belong to the traditional chain of book production and already have the habit of working with the BnF. However other partners are quite new and specific to the ebook market; they are often pure players and sometimes have new practices and new points of view. The reflection on the legal deposit of ebooks has to take into consideration this diversity in the ebook chain of production and commercialisation.

The second strength of the workflow is its capacity to build on many other projects already running within the library. Almost every application needed already exists in one form or another. The teams concerned work together and the reflection on ebooks benefits from a large panel of expertise -from the ebook market and formats to cataloguing, metadata and preservation . This will greatly facilitate the setting up of the legal deposit of ebooks.

Figure 1 .

 1 Figure 1. Same information, multiple uses.

Figure 2 .

 2 Figure 2. The data flow

According to the law, whenever an association of visually impaired people requires it, the BnF is entitled to ask from the publishers the master digital version of a printed book (ideally a XML version) and to transfer it to the association. The association is then entitled to transform the book in an accessible digital version.

Acknowledgments

The authors thank Peter Stirling for his perfect English and his Scottish accent.