Benoit Gaüzère

Pierre-Anthony Grenier

Luc Brun

Didier Villemin

Treelet kernel incorporating cyclic, stereo and inter pattern information in Chemoinformatics

come   L'archive ouverte pluridisciplinaire

Introduction

Chemoinformatics is a science field lying at the edge of chemical and computer science which aims to study, analyze, store and predict chemical data through informational techniques. Two problematics addressed by chemoinformatics correspond to Quantitative Structure-Activity Relationship (QSAR) and Quantitative Structure-Property Relationship (QSPR) problems. QSAR and QSPR are based on the similarity principle [START_REF] Johnson | Concepts and Applications of Molecular Similarity[END_REF] which states that two structurally similar molecules should have similar activities and properties.

A molecule is usually encoded by its molecular graph. A molecular graph is defined as a labeled graph G = (V, E, µ, ν), where the unlabeled graph (V, E) encodes the structure of the molecule while µ maps each vertex to an atom's label corresponding to atom's chemical element. Labeling function ν characterizes each edge by a type of bond between two atoms (single, double, triple or aromatic). Considering this molecular representation and the similarity principle, QSAR/QSPR problems rely on defining a similarity measure between molecular graphs.

A first family of methods introduced within QSAR/QSPR field is based on the correlation between a set of molecular descriptors and a given molecular property (e.g. molecule's boiling point). Descriptor sets are encoded by vectors and may be computed from structural information [START_REF] Cherqaoui | Use of a neural network to determine the normal boiling points of acyclic ethers, peroxides, acetals and their sulfur analogues[END_REF], physical properties or biological activities. These vectors may be used within any statistical machine learning algorithm in order to predict molecule's properties. Such a scheme allows to benefit from the large set of tools available within the statistical machine learning framework. However, the definition of a fixed size vector from a molecule, i.e. a molecular graph, induces a loss of information. Moreover, for each application, the definition of a vectorial description of each molecule is based on chemical expert's heuristics. A slightly different approach is based on graph embedding. Within this framework, a vectorial description of a graph is automatically built from its encoding using, for example, the spectral analysis of graphs [START_REF] Caelli | An eigenspace projection clustering method for inexact graph matching[END_REF]. In this last case, the embedding is deduced from the analysis of the eigenvectors and eigenvalues of the adjacency matrix.

A second family of methods, based on graph theory [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF], may be decomposed in two subfamilies. The first subfamily [START_REF] Poezevara | Discovering emerging graph patterns from chemicals[END_REF], related to the data mining field, aims to discover subgraphs having a large difference of frequencies between sets of positive and negative examples. We can note that this first subfamily is mainly restricted to classification problems. The second subfamily [START_REF] Riesen | Graph classification based on vector space embedding[END_REF], bases molecular graph similarity measures on graph edit distance. However, since graph edit distance does not define an euclidean distance [START_REF] Dattorro | Convex optimization & Euclidean distance geometry[END_REF], similarity measures based on graph edit distance do not correspond to a direct explicit nor implicit embedding. An embedding may nevertheless be obtained by regularizing the edit distance or by using distances to a set of prototype graphs [START_REF] Riesen | Graph classification based on vector space embedding[END_REF]. Graph edit distance can also be directly combined with a restricted set of machine learning methods such as k-nearest neighbors or k-medians algorithms.

Graph kernels can be understood as symmetric graph similarity measures. Using a positive definite kernel k, the value k(G, G ′ ), where G and G ′ encode two graphs, corresponds to a scalar product between two vectors ψ(G) and ψ(G ′ ) in a Hilbert space. Therefore, such a similarity measure may be used in conjunction with machine learning methods which may access to input data only through scalar products (such as SVM). Graph kernel framework provides thus a natural connection between structural pattern recognition and graph theory on one hand and statistical pattern recognition on the other hand.

A large family of graph kernels used in chemoinformatics is based on the definition of a bag of patterns for each graph and deduces graph similarity from similarity between bags. Some bags of patterns are defined by linear patterns. For example, marginalized kernel [START_REF] Kashima | Kernels for graphs[END_REF] defines a graph kernel based on a comparison between sets of random walks extracted from each graph. Tree pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] defines a graph kernel using a set of tree patterns instead of walks. This last kernel allows to encode more structural information than kernels based on linear patterns such as random walks.

A common drawback of kernels based on random walks and tree patterns is that the global similarity between two graphs is based on an implicit enumeration of their common patterns. An implicit enumeration does not allow to analyze the relevance of each pattern according to a given dataset and a particular property. Weisfeiler-Lehman kernel [START_REF] Shervashidze | Fast subtree kernels on graphs[END_REF] corresponds to a kernel based on a subset of tree patterns, computable in linear time, which provides an explicit distribution of each pattern within a graph. However, authors do not propose a method to weight each pattern. Treelet kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] defines a graph kernel based on a explicit set of patterns, called treelets, defined as all labeled subtrees having at most 6 nodes. This kernel can be used with a treelet selection step which aims to select relevant treelets according to a given property.

Kernels based on bags of patterns compute a similarity between two molecular graphs by comparing the number of occurrences of a given set of patterns in each graph. This approach only compares strictly isomorphic patterns. However, similarity principle established between molecular graphs can be transposed to patterns, i.e. similar patterns may have a similar influence on molecular properties. Considering this hypothesis, the shingled Weisfeiler-Lehman subtree kernel [START_REF] Shervaszide | Scalable graph kernels[END_REF] consists in including the comparison of similar tree patterns into kernel computation. However, this kernel is limited to the comparison of structurally isomorphic patterns and the set of patterns is restricted to balanced trees.

However, kernels based on linear or tree patterns do not encode any cyclic information. Molecular cycles correspond to an important molecular characteristic since they reduce the atom's degrees of freedom and hence influence molecular properties. Based on this last point, cyclic systems are used by chemical experts in order to classify molecules into several distinct molecular families, each family having similar chemical and biological properties. Cyclic pattern kernel [START_REF] Horváth | Cyclic pattern kernels for predictive graph mining[END_REF] aims to encode cyclic similarity between molecular graphs. This kernel is defined as a sum of two subkernels, a first one encoding acyclic similarity and a second one encoding cyclic similarity. However, the cyclic information captured by this kernel is restricted to the number of common cycles of two graphs and hence does not encode adjacency relationships between molecular cycles.

Finally, most of existing graph kernels do not take into account stereoisomerism. Stereoisomerism is a molecular property which distinguishes two molecules, called stereoisomers, encoded by a same molecular graph but which differs by the relative positioning of their atoms. Stereoisomers can have different properties which can not be accurately predicted by usual graph kernels which consider these molecules as identical. The adaptation of the tree pattern kernel [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] in order to encode stereo information constitutes a noticeable exception. However, this method does not provide a clear separation between patterns encoding stereoisomerism and patterns which do not.

This article is an extension of two previous papers [START_REF] Gaüzére | Relevant cycle hypergraph representation for molecules[END_REF][START_REF] Grenier | Treelet kernel incorporating chiral information[END_REF] which extend treelet kernel by explicitly taking into account cyclic and chiral information of molecules. In this article, we propose a unified presentation of treelet kernel in-cluding a detailed description of the extensions proposed in [START_REF] Gaüzére | Relevant cycle hypergraph representation for molecules[END_REF][START_REF] Grenier | Treelet kernel incorporating chiral information[END_REF]. In addition, we propose an original extension of treelet kernel which includes the contribution of similar patterns. Moreover, we propose to explain in detail a pattern weighting scheme based on multiple kernel learning and more complete experiments. Our paper is organized as follows: First, the treelet kernel construction scheme is described in section 2 together with a weighting scheme based on multiple kernel learning [START_REF] Gönen | Multiple kernel learning algorithms[END_REF] which allows to compute an optimal weight for each pattern according to a given property. Second, section 3 aims to define a kernel which includes the comparison of similar patterns. Then, section 4 aims to include stereo information into graph kernel. Finally, we propose to encode cyclic information in two different ways. The first one consists in encoding the cyclic system of a molecule by its relevant cycle graph (section 5.2) which allows to encode relationships between cycles of a molecule. The second representation, called relevant cycle hypergraph (section 5.3), allows to encode relationships between cyclic and acyclic parts into an unique molecular representation. Treelet kernel has been adapted to the comparison of these two new molecular representations. Finally, all proposed extensions are evaluated in section 6 on several chemical data sets.

Treelet kernel

The treelet kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] is a graph kernel defined as a convolution kernel [START_REF] Haussler | Convolution kernels on discrete structures[END_REF] between bags of patterns extracted from two graphs. The set of extracted patterns, called treelets, is composed of all labeled trees with a number of nodes lower than or equals to 6. The set of treelet's structures, i.e. the set of all unlabeled trees associated to treelets, is displayed in figure 1. This set of patterns allows us to define an ad hoc enumeration algorithm which encodes most of the relevant structural information encoded in a molecular graph. Indeed, graph fragment approach experiments [START_REF] Wale | Comparison of descriptor spaces for chemical compound retrieval and classification[END_REF] have observed that no significant gain is obtained with structures having more than 6 nodes. In order to compute treelet kernel, we have to enumerate the set of treelets of each graph. The first step of this enumeration consists in enumerating the set of treelet's structures (figure 1) of a graph. This structure identification step consists in two sub steps: First, linear patterns are enumerated by a depth first traversal performed from each node. In order to enumerate all paths having at most 6 nodes, depth first traversal is stopped after encountering 5 edges. Then, non linear treelets are enumerated using a neighborhood analysis of n-star nodes which are defined as nodes having a degree equals to n (G 6 , G 8 and G 13 treelet's structures in figure 1). Considering these first structures, others treelet's structures are enumerated using the neighborhood of nodes adjacent to n-stars. Therefore, structures G 7 , G 9 , G 10 and G 12 are enumerated from G 6 . Similarly, G 11 is retrieved from G 8 . This structure identification step allows to associate an index to each enumerated subgraph. This index identifies the structure of each treelet in a canonical way.

✁ ✂ ✄ ✂☎ ☎ ✆ ✝ ✞ ✟ ✠ ✡ ✂✁ ✂✂ ✂✄
Once this first step is performed, a key encoding the labels of each treelet is computed in order to distinguish treelets having a same structure index but different labels. Considering linear treelets, this key is defined as a sequence of labels encountered during a traversal of the associated path. Since there is two possible path traversals, this sequence is defined as the lowest one according to lexicographic order. For each non linear treelet structure, our key's construction scheme requires to root each treelet. To this end we use the Morgan numbering [START_REF] Morgan | The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service[END_REF] which maps each node to an integer depending on node's degrees. Considering this numbering, each tree is rooted on the node having the highest Morgan number. Then each set of child nodes is ordered using a subkey defined from its Morgan numbering and the concatenation of the child's label, the label of the edge connecting it to its father and the key of the subtree rooted on this child. Given this ordered rooted tree, the key is defined as a sequence of labels encountered during a depth first traversal. This traversal provides thus a sequence of nodes and edges labels which is unique for two isomorphic treelets. Conversely, we have shown [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] that two treelets with a same index (i.e. a same structure) and a same key are isomorphic. Therefore, the concatenation of treelet's structure index and treelet's key defines a unique code for each treelet which allows to perform an explicit enumeration of all treelets included within a graph. Based on this enumeration, we define a function f t : G → R + which encodes the number of occurrences of treelet t ∈ T in a graph:

∀ t ∈ T , f t (G) = |(t G)| (1)
where T denotes the set of treelets and the subgraph isomorphism relationship. Then, similarity between treelet distributions is computed using a sum of subkernels between treelet's frequencies:

k T (G, G ′ ) = t∈T (G)∩T (G ′ ) k(f t (G), f t (G ′ )) not. = t∈T (G)∩T (G ′ ) k t (G, G ′ ) ( 2
)
where T (G) encodes the set of treelets extracted from

G, k t (G, G ′ ) = k(f t (G), f t (G ′ ))
and k(., .) corresponds to any positive definite kernel between real numbers such as linear kernel, gaussian kernel or intersection kernel. Each subkernel k t encodes thus a similarity between frequencies of a given treelet t in each graph. Note that, unlike tree pattern or random walks kernels, this kernel explicitly enumerates subtrees by computing the number of occurrences of each pattern. This explicit enumeration allows us to apply a treelet weighting step, as defined in section 2.1.

Pattern weighting

Chemical experts aim to identify particular subgraphs which may be responsible for a particular molecular activity. The presence or absence of one of these particular subgraphs, called pharmacophores, is an important characteristic to determine if a molecule is toxic or not. Considering graph kernels based on bags on patterns, each pattern may be seen as a potential pharmacophore. It may thus be interesting to weight each pattern according to its influence on a given property. A relevant pattern may thus be associated to an important weight whereas patterns which do not encode any information may be removed from kernel computation. Considering a kernel based on a bag of patterns P and defined as a sum of subkernels, each subkernel encodes graph similarity according to a given pattern p ∈ P. Pattern weighting relies on computing a weight for each term of the sum. A weighted kernel is defined as:

k weight (x, x ′ ) = p∈P d(p) * k p (x, x ′ ) ( 3
)
where d : P → R + encodes the influence of each pattern into kernel computation. An high d(p) encodes an high influence and corresponds to an high contribution of pattern p. Conversely, a weight d(p) close to or equal to 0 relies to remove the contribution of pattern p from kernel computation. Tree pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] includes a pattern weighting function. This weighting is an a priori parameter which allows to favor structurally complex tree patterns or linear patterns depending on parameter value. Treelet kernel can be combined with iterative pattern selection method [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] which allows to select or not a given pattern into kernel computation. Conversely to a priori pattern weighting method proposed by tree pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF], this last method computes a weighting function according to a particular property. However, this pattern selection step is only binary, computationally costly and non optimal.

Multiple kernel learning

Considering a pattern weighting problem as defined by equation 3, Multiple Kernel Learning (MKL) methods aim to compute an optimal weighting function d according to a given dataset and a property to predict. Considering a finite set of M patterns, weighting function d is encoded by a vector d ∈ R M + where each coordinate d m encodes a weight associated to a pattern. The weighted kernel is then defined as:

k MKL (x, x ′ ) = M m=1 d m * k m (x, x ′ ) ( 4
)
where k m corresponds to a subkernel encoding a graph similarity measure according to a particular pattern. Multiple kernel learning methods consist in computing an optimal vector d according to a prediction task. Simple MKL [START_REF] Rakotomamonjy | SimpleMKL[END_REF] consists in optimizing a SVM problem by computing an optimal weighting for each sub kernel. Considering a kernel as defined in equation 4, Simple MKL consists in solving:

minimize d J(d) such that d m > 0, ∀i ∈ {1, . . . , M } M m=1 d m = 1 (5)
with

J(d) =        min w,b,ξ 1 2
M m=1

1 dm w m 2 + C n i=1 ξ i subject to: y i ( M m=1 w m , Φ m (x) + b) ≥ 1 -ξ i , ∀i ∈ {1, . . . , n} ξ i ≥ 0, ∀i ∈ {1, . . . , n} (6)
where Φ m (x) corresponds to the embedding function associated to k m . This minimization problem is the same type of problem as solved by a standard SVM by optimizing vector d up to constraints defined by equation 5. Minimization problem defined in equation 5 includes a first constraint on vector d which is defined as a positivity constraint. This constraint ensures that the weighted kernel (equation 4) is positive definite. The second constraint imposes to the L 1 norm of vector d to be equals to 1. This constraint induces a sparse vector d and thus allows to keep only the most relevant patterns into the weighted kernel while removing irrelevant ones.

Simple MKL [START_REF] Rakotomamonjy | SimpleMKL[END_REF] problem is resolved by alternating a classical SVM resolution together with a projected gradient descent according to direction ∂J ∂dm for each element of vector d. Using a projected gradient method allows us to minimize the objective function while ensuring that constraints of sparsity and positivity defined on vector d are fulfilled. Generalized MKL [START_REF] Varma | Learning the discriminative power-invariance trade-off[END_REF] proposes a multiple kernel learning algorithm based on the same principle but where the objective function is penalized by σ d 1 instead of an equality constraint on d 1 . This regularization allows to tune the degree of sparsity of d.

In order to deal with thousands of patterns, one have to either compute each gram matrix for each sub kernel at each iteration or to store each gram matrix. When considering thousands of patterns and graphs, these two options induce too much computational time or memory space to be applicable. In order to handle such datasets, infinite MKL [START_REF] Yger | Wavelet kernel learning[END_REF] defines a MKL method based on Simple MKL which only considers a sub set of sub kernels at each iteration. This set of active kernels is updated between two Simple MKL iterations until convergence or a maximal numbers of active kernels is reached. This algorithm allows to consider an high, possibly infinite, number of subkernels and to select most relevant ones according to a particular property to predict.

Initially, multiple kernel learning methods have been defined on classification problems. However, they can easily be adapted to SVM for regression. This adaptation mainly consists in replacing SVM objective function by SVM for regression objective function. Obviously, gradient values must be updated accordingly. Therefore, multiple kernel learning methods allow to compute a weighting for a set of kernels for either a classification or a regression problem. This weight is optimal according to the used training set and not defined a priori or using only structural information. When applied together with treelet kernel, each weight is associated to a given treelet. On one hand, this weighting may allow to increase prediction accuracy obtained by treelet kernel. On the other hand, computed weights may be seen as a measure of the influence of each treelet according to the predicted property. This measure of influence may be used by chemical experts in order to understand chemical properties. Indeed, a treelet associated to an high weight may be considered as a potential pharmacophore.

Including cross pattern information

As mentioned in section 1, if we consider the hypothesis that similar molecules have similar properties, we should consider that similar substructures may have a similar influence on molecular properties. Recently, Shervashidze has proposed to adapt Weisfeiler-Lehman kernel in order to include comparison of non isomorphic subtree patterns [START_REF] Shervaszide | Scalable graph kernels[END_REF]. This comparison is based on Jaccard coefficient which defines a similarity measure between sets. Considering this similarity measure, Shervashidze has proposed an efficient computation in order to compare nodes' neighbourhoods. However, this approach only compares structurally isomorphic patterns and the set of patterns is restricted to balanced trees.

In order to include non-isomorphic treelet comparison into treelet kernel, let us recall convolution kernel theory. Haussler's convolution kernels [START_REF] Haussler | Convolution kernels on discrete structures[END_REF] are defined on objects x ∈ X which can be associated to a decomposition into finite sets X x . Considering a subkernel k s : X x × X x → R, Haussler's convolution kernel K : X × X → R is defined as follows:

K(x, y) = (x ′ ,y ′ )∈Xx×Xy k s (x ′ , y ′ ) (7) By considering a decomposition X G = {(t, f t (G)) | t G} of each graph and a tensor product (k ⊗ k ′ ) of two kernels k ′ : T × T → R and k : R × R → R, treelet kernel k T (equation 2
) can be reformulated as a convolution kernel k inter :

k inter (G, G ′ ) = (t,ft(G))∈X G (t ′ ,f t ′ (G ′ ))∈X G ′ (k ′ ⊗ k)(t, f t (G), t ′ , f t ′ (G ′ )) k inter (G, G ′ ) = (t,ft(G))∈X G (t ′ ,f t ′ (G ′ ))∈X G ′ k ′ (t, t ′ )k(f t (G), f t ′ (G ′ )) (8)
In treelet kernel definition (equation 2), k ′ is defined such that comparisons are restricted to isomorphic treelets, i.e. k ′ (t, t ′ ) = 1 ⇔ t ≃ t ′ , and 0 otherwise. In this section, we propose to define a kernel k ′ between treelets which relaxes this restriction and includes the comparison of similar patterns.

Inter treelet kernel based on edit distance

Considering the hypothesis that similar patterns may have a similar influence, kernel k ′ between treelets must encode a similarity measure between t and t ′ . This similarity measure may be defined from graph edit distance [START_REF] Neuhaus | Bridging the Gap Between Graph Edit Distance and Kernel Machines[END_REF]. Graph edit distance is defined as the sequence of edit operations transforming G into G ′ with a minimal cost. A sequence of edit operations, called edit path, may include vertex or edge addition, removal and relabeling. Given a cost function c(.) associated to each operation, the cost of a sequence of edit operations is defined as the sum of each elementary operation's costs. A high edit distance corresponds to a low similarity between two graphs while a small one encodes a strong similarity. According to [START_REF] Neuhaus | Bridging the Gap Between Graph Edit Distance and Kernel Machines[END_REF], the computational cost of the exact edit distance grows exponentially with the size of graphs. To overcome this problem, Fankhauser et al. [START_REF] Fankhauser | Speeding up graph edit distance computation through fast bipartite matching[END_REF] propose a method to compute an approximate edit distance in O(n 3 ) where n is equal to the number of nodes of both graphs. Such an edit distance computation provides an efficient way to compute an approximate edit distance between graphs at the cost of a lower precision.

Exact treelet edit distance

Exact edit distance is hard to compute when considering the whole set of possible graphs. Given a finite set of

n structures B = {(V 1 , E 1 ), . . . , (V n , E n )}, we re- strict our study to sets of graphs D such that for any graph G = (V, E, µ, ν) ∈ D we have (V, E) ∈ B.
We show in the remaining of this section that within this framework, exact edit distance may be computed within a reasonable computational time using ad hoc methods.

In order to present such methods, let us introduce some definitions. A graph

G ′ = (V ′ , E ′ , µ ′ , ν ′ ) is a structural subgraph of G = (V, E, µ, ν), denoted G ′ ⊑ s G, iff V ′ ⊆ V and E ′ ⊆ E ∩ (V ′ × V ′ ). In addition, if µ ′ |V ′ = µ and ν ′ |E ′ = ν, g | denoting the restriction of function g to a particular domain, then G ′ is a subgraph of G, denoted G ′ ⊑ G. A graph G = (V, E, µ, ν) is structurally isomorphic to a graph G ′ = (V ′ , E ′ , µ ′ , ν ′ ), denoted G ≃ s G ′ iff it exists a bijective function f : V → V ′ such that (u, v) ∈ E ⇔ (f (u), f (v)) ∈ E ′ . If µ ′ • f = µ and ν ′ • f = ν, then G is isomorphic to G ′ , denoted G ≃ G ′ . If G = G ′ then f is called an automorphism. If f is only injective then it exists a subgraph isomorphism between G and G ′ . A graph Ĝ is a maximal common subgraph of G 1 and G 2 if it is a subgraph of G 1 and G 2 and if it is not a sub graph of any other common subgraph of G 1 and G 2 . A graph Ĝ is called a maximum common subgraph of G 1 and G 2 if it is a common subgraph of G 1
and G 2 with a maximal number of nodes. The notions of maximal structural subgraph and maximum structural subgraph are defined in the same way but without conditions on the mapping of labels of both graphs. Under mild assumptions [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF], the sequence of edit operations encoding an edit path can be ordered into a sequence of deletions, substitutions and additions as illustrated in figure 2(a). The first sequence transforms the initial graph G 1 into one of its subgraphs Ĝ1 by deleting a set of nodes corresponding to V 1 \ V1 and a set of edges corresponding to E 1 \ Ê1 . The second sequence encodes a set of substitution operations which allows to transform Ĝ1 into Ĝ2 . This set of substitutions corresponds to a one to one matching between V1 and V2 on one hand and between Ê1 and Ê2 on the other hand. Substitutions matching two elements having a same label correspond to identical substitutions and are associated to a null cost since they do not induce any changes. Finally, the last sequence of operations corresponds to a set of addition operations required to obtain G 2 from Ĝ2 . Note that the set of operations transforming Ĝ1 into Ĝ2 is only composed of substitutions which do not alter graph structures. Therefore, Ĝ1 and Ĝ2 have a same structure and correspond to two structurally isomorphic subgraphs of G 1 and G 2 .

Edit operation costs are defined as non-negative constant functions for edges (c e * ) and nodes (c v * ) deletions (c * d ), insertions (c * i ) or substitutions (c * s ). Using the different steps depicted in figure 2(a) and cost functions previously defined, the cost associated to an edit path is equal to: [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] where V f , resp. E f , corresponds to the number of non identical substitutions on nodes, resp. edges, required to transform Ĝ1 into Ĝ2 . Bunke has shown that under some slightly different conditions on edge operations, constraining the costs to c vd + c vi < c vs and c es < c vs induces that Ĝ1 ≃ Ĝ2 correspond to a maximum common subgraph of G 1 and G 2 [START_REF] Bunke | Error correcting graph matching: On the influence of the underlying cost function[END_REF]. However, maximum common subgraph of two graphs depends both on structural and labeling information which does not allow us to use our assumption that the set of structures encoding graphs is finite and known a priori. In this section, we propose to study different assumptions on edit costs leading to an efficient algorithm to compute an exact edit distance. Proof 1 Proof of proposition 1 can be found in [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF].

γ(P ) = |V 1 -V1 |c vd +|E 1 -Ê1 |c ed +V f c vs +E f c es +|V 2 -V2 |c vi +|E 2 -Ê2 |c ei
Considering two graphs G 1 and G 2 , this first proposition ensures that an optimal edit path transforming G 1 into G 2 passes through one of their maximal common structural subgraphs. Since the maximal common structural subgraph does not depend on labeling, the set of maximal common structural subgraphs may be pre computed between any pair of structures belonging to B. Nevertheless, this number of maximal common structural subgraphs may remain large hence forbidding an efficient pre computation of the exact edit distance. However, by further restricting cost conditions, we obtain a relationship involving a reduced set of substructures:

Proposition 2 Let us suppose that c ed = c ei = 0 and c es ≤ c vs . Given two graphs G 1 and G 2 , let us further denote by δ v the number of vertices of their maximum common structural subgraphs and by δ e the maximal number of edges of all maximum common structural subgraphs. Then if

c vd +cvi cvs ≥ δ v + δ e , Ĝ1 is a maximum common structural subgraph of G 1 and G 2 .
Proof 2 Proof of proposition 2 can be found in [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF].

Proposition 2 states that under some hypothesis on the costs c * d , c * i and c * s , any optimal edit path between two graphs G 1 and G 2 should pass through one of their maximum common structural subgraphs. Let us consider two graphs G 1 and G 2 sharing only one maximum common structural subgraph Ĝ = ( V , Ê). Let us denote as { Ĝ0

γ(P ) = γ struc (P ) + γ label (P ) (10)
Following equation 9, we have:

γ struc (P ) = |V 1 -V1 |c vd + |E 1 -Ê1 |c ed + |V 2 -V2 |c vi + |E 2 -Ê2 |c ei γ label (P ) = V f c vs + E f c es (11)
For any i ∈ {1, . . . , n 1 }, since Ĝi

1 ⊑ G 1 , we have V i 1 ⊆ V 1 and Êi 1 ⊆ E 1 . Therefore: | V i 1 -V 1 | = |V 1 | -| V i 1 | = |V 1 | -| V | | Êi 1 -E 1 | = |E 1 | -| Êi 1 | = |E 1 | -| Ê| (12)
Similarly, same equalities hold for G 2 and Ĝj 2 for any j ∈ {1, . . . , n 2 }. Structural cost corresponding to edit path P is thus equal to:

γ struct (P ) =|V 1 |c vd + |V 2 |c vi + |E 1 |c ed + |E 2 |c ei -| V |(c vd + c vi ) -| Ê|(c ed + c ei ) (13)
Computing substitution cost γ label (P ) (equation 11) relies on computing the number of non identical node substitutions V f and edge substitutions E f transforming Ĝi 1 into Ĝj 2 . Let Φ( Ĝ) denote the set of structural automorphisms of Ĝ. Given both subgraphs Ĝi 1 and Ĝj 2 , each automorphism φ ∈ Φ( Ĝ) induces a mapping of Ĝi 1 onto Ĝj 2 and thus a substitution of the label of each vertex v (resp. edge e) of Ĝi 1 onto the label of φ(v) (resp. φ(e)) in Ĝj 2 . More precisely, let us denote by P i,j,φ the edit path associated to the triplet ( Ĝi 1 , Ĝj 2 , φ). the number of non identical substitutions V f and E f induced by P i,j,φ is equal to:

V f (P i,j,φ ) = |{v ∈ V1 | μi 1 (v) = μj 2 (φ(v))}| E f (P i,j,φ ) = |{(v, v ′ ) ∈ Ê1 | νi 1 (v, v ′ )) = νj 2 (φ(v), φ(v ′ ))}| (14)
Substitution cost of edit path P i,j,φ is thus equal to γ label (P i,j,φ ) = V f (P i,j,φ )c ns + E f (P i,j,φ )c es . Let us denote by P opt the edit path minimizing the substitution cost:

P opt = P i ⋆ ,j ⋆ ,φ ⋆ with (i ⋆ , j ⋆ , φ ⋆ ) =

argmin

(i,j,φ)∈{1,...,n1}×{1,...,n2}×Φ( Ĝ)

γ label (P i,j,φ ) (15) Since γ struct (P i,j,φ ) is the same for any (i, j, φ) ∈ {1, . . . , n 1 }×{1, . . . , n 2 }×Φ( Ĝ) (equation 13), P opt is an edit path having a minimal cost. Therefore, under our assumptions, the edit path associated to the edit distance is the one which passes through the pair of maximum common structural subgraphs and which minimizes the number of substitutions (equation 15). This exact edit distance computation algorithm can be applied to treelets since the set of treelets is composed of 14 different structures. In addition, by restricting the set of edit paths to the ones which preserve the connectedness of intermediate graphs [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF], we obtain a lower bound on the ratio between substitutions and insertion/deletion costs.

Proposition 3 Considering edit paths preserving connectedness and given two trees

T 1 , T 2 ∈ T , if c vd +cvi cvs ≥ δ v and c ed +cei ces ≥ δ v -1, then Ĝ1 is a maximum common structural subtree of T 1 and T 2 .
Proof 3 Can be found in [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF].

When computing tree edit distance on the set of treelets, δ v is bounded by 6 and if we define costs as symmetric, i.e. c vd = c vi and c ed = c ei , bounds on costs lead to: c vd > 3c vs and c ed > 2.5c es . Since the set of treelets is defined as all trees having a size less than or equal to 6, the maximum common structural subtree of two treelets T 1 and T 2 is a treelet. The set of possible subgraphs and automorphisms for any pair of treelets can be easily pre computed since we have to consider only 14 structures. Therefore, computing the exact edit distance between two treelets consists in comparing at most max (i,j)∈{0,...,13} 2 (n i * n j * |Φ ij |) label sequences where Φ ij denotes the set of automorphisms of the maximum common structural subtree T of treelets T i and T j and n i , n j the numbers of subtrees of T i and T j isomorphic to T . The value of this product on the set of treelets is bounded by 120, hence inducing a constant time complexity for the computation of the exact treelet edit distance. Note that, without our restriction to a set of specific tree structures, the complexity of the edit distance calculation between labeled unordered unrooted trees is NP-Complete [START_REF] Zhang | On the editing distance between unordered labeled trees[END_REF].

Given a training set D = {G 0 , . . . , G N } and a set of treelets {t 1 , . . . , t m } extracted from graphs in D, we define a m by m similarity matrix corresponding to a gaussian RBF kernel applied on the exact graph edit distance:

K ted = e - d 2 (t i ,t j ) σ inter (i,j)∈{1,...,m} 2 (16)
Since graph edit distance does not define an euclidean matrix [START_REF] Dattorro | Convex optimization & Euclidean distance geometry[END_REF], matrix K ted may not be semi definite positive and thus may not define a kernel on {t 1 , . . . , t m }. In order to define a valid kernel, we define a Gram matrix K on {t 1 , . . . , t m } 2 by regularizing K ted :

K = K ted -Iλ m ( 17
)
where λ m corresponds to the lowest eigenvalue of K ted . Note that this regularization has to be performed only once since this kernel only operates on treelets and not directly on graphs. In order to be applied on any test set, kernel k ′ between treelets is defined as:

k ′ (t, t ′ ) =      K (i,j) if t = t i ∈ {t 1 , . . . , t m } and t ′ = t j ∈ {t 1 , . . . , t m }, 1 if t = t ′ ∈ {t 1 , . . . , t m } and 0 otherwise (18)
This kernel deduced from the 0-extension of K is trivially definite positive. This kernel between treelets encodes a similarity measure between treelets based on an efficient computation of the graph edit distance. Using such a kernel allows us to include the contribution of non isomorphic but similar treelets. Considering the kernel k inter defined in equation 8, k ′ associates isomorphic treelets to an high value since d(t i , t j ) = 0 if t i ≃ t j . Conversely, highly dissimilar treelets are removed from kernel contribution since an high distance corresponds to a low value of gaussian kernel.

Including stereo information

As mentioned in section 1, stereoisomers correspond to molecules encoded by a same molecular graph which only differ by the relative positioning of their atoms. For example, considering figure 3(a) and looking at the central carbon (C) from the hydrogen atom (H), the remaining neighbors of C may be considered as lying on a plane and encountered clockwise. These remaining neighbors can thus be encoded by the sequence (C N , O H , O Cl1 ) which identifies a particular stereoisomer whereas an opposite sequence of neighbors (e.g. (O Cl , O H , C N )) corresponds to a distinct stereoisomer. This example is called an asymmetric carbon, a carbon with four different neighbours, and its presence is one of the most frequently encountered cause of stereoisomerism. Another cause of stereoisomerism is the presence of a double bond between carbons. According to chemical experts, 98% of the stereoisomers currently used in chemistry are stereoisomers because of the presence of one of this two configurations. Graph kernel proposed by [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] allows to encode these two forms of stereoisomerism by adapting the tree pattern kernel. However, in this approach, patterns which encode stereo information, and patterns which do not, are combined without any weighting in the final kernel value. Therefore, patterns which do not encode any stereo information may be assimilated to noise when predicting a property only related to stereoisomerism. In this section, we propose to adapt the treelet kernel to stereoisomers in order to obtain a kernel encoding only stereo information.

Ordered graphs and stereo vertices

Let us first consider asymmetric carbon. The spatial configuration of the stereoisomer depicted in figure 3(a) can be encoded by the sequence (H, C N , O H , O Cl ) where the atom fixing the point of view (H) and the first atom of the remaining neighbors cyclically ordered are arbitrary chosen. For each atom, the relative positioning of its neighbors may thus be encoded by an ordered list. An ordered graph G = (V, E, µ, ν, ord) is defined as a molecular graph G m = (V, E, µ, ν) with a function ord : V → V * which associates to each node an ordered list of its neighbors. Two ordered graphs G and The order encoding the neighborhood of a vertex being relative to the choice of two of its neighbors, two different ordering functions may encode a same configuration. Re-ordering functions associate to each vertex v of degree n a permutation on {1, . . . , n} which allows to re-order its neighborhood. The set of re-ordering functions encoding a same configuration is called a valid family Σ [START_REF] Grenier | Incorporating chirality within the graph kernel framework[END_REF]. Two ordered graphs G and G ′ are considered as equivalent according to Σ (denoted

G ′ are isomorphic (G ≃ o G ′ ) if it 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 ).
G ≃ Σ G ′ ), if it exists a re-ordering function σ ∈ Σ such that σ(G) ≃ o G ′
. This relationship defines an equivalence relationship [START_REF] Grenier | Incorporating chirality within the graph kernel framework[END_REF] and two different stereoisomers are encoded by non equivalent ordered graphs. This global graph's characterization may be translated into a local one in order to characterize vertex's stereo property: Definition 1 (Stereo vertex) Let G = (V, E, µ, ν, ord) be an ordered graph. A vertex v ∈ V of degree n is called a stereo vertex iff:

∀(i, j) ∈ {1, . . . , n} 2 , i = j, G ≃ Σ τ v i,j (G). ( 19
)
where τ v i,j (G) corresponds to an ordered graph deduced from G by permuting nodes of index i and j in ord(v).

Minimal stereo subtree

Using definition 1, vertex's stereo property is characterized using the whole ordered graph G. Given a vertex v whose stereo property has to be checked by definition 1, one can observe that, on some configurations, the removal of some vertices far from v should not change its stereoisomerism. We should thus determine the minimal subgraph of G including v which fulfills equation 19, in order to obtain a local characterization of a stereo vertex. In the following, we restrict our attention to acyclic graphs. Considering such a restriction, the minimal subgraph characterizing the stereo property of a vertex v corresponds to the smallest ordered subtree rooted on v which allows to define v as a stereo vertex (definition 1). Such a subtree is called the minimal stereo subtree of v. Let us consider an ordered subtree T of G rooted on v and the set of subtrees {T 1 , . . . , T n } of T rooted on each node adjacent to v, n being thus equals to the degree of v. Let us additionally consider the subtree T j i of T i with the same root as T i and whose depth is equal to j. We denote by T (j 1 , . . . , j n ) the subtree of T rooted on v and connected to the set of subtrees {T j1 1 , . . . , T jn n }. We then associate to each i ∈ {1, . . . , n}, the index j ⋆ i corresponding to the minimal value, and thus the minimal depth, such that T

j ⋆ i i is not isomorphic to any T j k , k = i, j ≥ 1. Any permutation of T j ⋆ i i and T j ⋆ k k , i = k in T (j ⋆
1 , . . . , j ⋆ n ) leads thus to a non-isomorphic ordered tree and T (j ⋆ 1 , . . . , j ⋆ n ) is the minimal stereo subtree of v (equation [START_REF] Wale | Comparison of descriptor spaces for chemical compound retrieval and classification[END_REF]. A molecule can thus be associated to a set of minimal stereo subtrees, each subtree being associated to a stereo vertex. Considering only acyclic graphs allows us to efficiently compare rooted ordered trees and thus minimal stereo subtrees. Indeed, an ordered tree is encoded by a string corresponding to the sequence of labels encountered during its depth first traversal. The canonical representation of an ordered tree, up to equivalence relationships is thus defined as the minimal string according to lexicographic order among all possible equivalent ordered trees (section 4.1). Ordered isomorphisms with equivalences between two trees can then be tested efficiently by comparing their unique string encodings [START_REF] Grenier | Incorporating chirality within the graph kernel framework[END_REF].

Graph contraction and stereotreelet

We assume that the stereo properties of an acyclic molecule are determined both by its set of minimal stereo subtrees and by the relationships between these subtrees and the remaining parts of the molecule. These relationships may be encoded by a contracted graph (figure 3) where a minimal stereo subtree is contracted into a single node C S . This contracted node is then connected to each leaf l of the corresponding minimal stereo subtree. Edges encoding these adjacency relationships are labeled by the sequence of child's indexes traversed to reach leaf l from the minimal stereo subtree's root.

Each stereo vertex v is associated to a contracted graph which encodes its minimal stereo subtree and the adjacency relationships of this tree with the other parts of the molecule. We then associate to v the set of treelets extracted from its contracted graph. This set of treelets is reduced to treelets containing the contracted node encoding the minimal stereo subtree. Each graph G can thus be associated to a set of stereotreelets T S (G) defined as the union of stereotreelets associated to the stereo vertices of G. The stereotreelet kernel is then defined as a treelet kernel (equation 2) between the set of stereotreelets of both graphs to be compared:

k T S (G, G ′ ) = t∈T S (G)∩T S (G ′ ) k(f t (G), f t (G ′ )) (20)
This extension defines a graph kernel which allows to distinguish two stereoiso-mers. Although it is restricted to acyclic molecules, this kernel allows to take into account local and non local chiral information. The extension of this framework to double bond between carbons is straightforward [START_REF] Grenier | Incorporating chirality within the graph kernel framework[END_REF].

Including cyclic information

As mentioned in section 1, kernels based on linear or tree patterns do not encode any cyclic information while molecular cycles reduce the atom's degrees of freedom and have thus an high influence on molecular properties. Horváth et al. [START_REF] Horváth | Cyclic pattern kernels for predictive graph mining[END_REF] have proposed the cyclic pattern kernel which compares the cycles of two graphs by computing their number of common simple cycles. However, the complexity required to enumerate the set of simple cycles is NP-Hard. Therefore, Horváth has proposed a new formulation [START_REF] Horváth | Cyclic pattern kernels revisited[END_REF] using relevant cycles [START_REF] Vismara | Union of all the minimum cycle bases of a graph[END_REF] instead of simple cycles which reduces algorithm complexity. Nevertheless, this kernel deduces cyclic similarity from the number of common cycles but does not encode any adjacency relationships between cycles.

Relevant Cycles

Let us introduce relevant cycles, as defined by Vismara [START_REF] Vismara | Union of all the minimum cycle bases of a graph[END_REF]. According to [START_REF] Vismara | Union of all the minimum cycle bases of a graph[END_REF], a simple cycle is defined as a subgraph C = (V ′ , E ′ , µ, ν) of a graph G = (V, E, µ, ν) where each vertex v ∈ V ′ has a degree equal to 2. Each cycle C G can be represented as a vector C ∈ {0, 1} |E| where C i is equal to 1 if i is an edge of C and to 0 otherwise. The set of vectors encoding cycles of G defines a vector space where the addition of two cycles C and C ′ corresponds to a XOR bitwise operation on their vectorial representations [START_REF] Vismara | Union of all the minimum cycle bases of a graph[END_REF]. The set of relevant cycles of a graph, denoted C R (G), is defined as the union of all bases of the vector space of minimum length. The length of a base is defined as the sum of lengths of its cycles. Note that this set of cycles allows to encode all cycles of a molecular graph by combining them. Vismara has proposed an efficient algorithm which allows to compute the set of relevant cycles of a graph with a polynomial complexity according to the number of nodes of a graph [START_REF] Vismara | Union of all the minimum cycle bases of a graph[END_REF].

Relevant Cycle Graph

Topological relationships between relevant cycles can be encoded by the relevant cycle graph. Given a graph G = (V, E, µ, ν), its associated relevant cycle graph (figure 4) is defined as • µ C (v): relevant cycle c encoded by v can be associated to a sequence of edge and vertex labels encountered during the traversal of c in G. In order to obtain a label sequence invariant to cyclic permutations, µ C (v) is defined as the sequence having the lowest lexicographic order;

G C (G) = (V C , E C , µ C , ν C ) where each vertex v ∈ V C corresponds to a relevant cycle c ∈ C R (G). Each vertex v ∈ V C is associated to the set c V (v) ⊆ V of
• ν C (u, v): an edge e = (u, v) ∈ E C is associated to each path shared by two cycles. Since this path can be traversed in two differents ways, we define ν C (e) as the minimal sequence of vertex and edge labels according to lexicographic order. Note that generally two relevant cycles share an unique path.

Cyclic information may be encoded into a graph kernel by applying treelet kernel on the relevant cycle graph instead of the original molecular graph. This kernel is thus defined by:

k C (G, G ′ ) = k T (G C (G), G C (G ′ )) = t C ∈T (G C (G))∩T (G C (G ′ )) k(f t C (G C (G)), f t C (G C (G ′ ))) (21)
Where k T refers to our treelet kernel (equation 2).

Using equation 21, extracted treelets no longer encode atom adjacency relationships but relevant cycle adjacency relationships. We can note that this kernel generalizes the cyclic pattern kernel. Indeed, the cyclic pattern kernel may be retrieved from the treelet kernel applied on the relevant cycle graph by restricting the set of treelets to the G 0 treelet structure (figure 1) and defining k as an intersection kernel. Considering others treelet structures allows us to encode adjacency relationships between relevant cycles.

However, we can note that kernel defined by equation 21 only includes cyclic information. Therefore, the cyclic pattern kernel, defined by equation 21, may be combined with a kernel encoding acyclic similarity such as treelet kernel applied on the original molecular graph:

k(G, G ′ ) = λk T (G , G ′ ) + (1 -λ)k C (G, G ′ ) ( 22
)
This kernel allows to encode both cyclic and acyclic information. Parameter λ allows to tune the trade-off between cyclic and acyclic information into kernel value computation. This parameter may be adapted according to a given property, by cross validation or multiple kernel learning (section 2.1.1). However, note that in this last case, sparsity constraint must be relaxed in order to insure that both subkernels are taken into account. Kernel defined by equation 22 encodes a global similarity measure by a sum of two subkernels where each subkernel exclusively encodes cyclic or acyclic information. Although this approach allows to split acyclic and cyclic contributions, it does not allow to encode adjacency relationships between cyclic and acyclic parts of a molecule. For example, adjacency relationships between a cycle and its substituents (e.g. C 3 and N in figure 4) is not encoded by our kernel, neither by any graph kernel to the best of our knowledge.

Relevant Cycle Hypergraph

In order to encode adjacency relationships between cyclic and acyclic parts of a molecule, a first approach consists in adding vertices and edges corresponding to acyclic parts to our relevant cycle graph defined in section 5.2. Unfortunately, such an approach can not handle cases where an atom is connected to two distinct relevant cycles. As shown in figure 5(a), the atom labeled O is connected by an unique edge to two distinct cycles in the molecular graph representation. This adjacency relationship can not be encoded by a graph since an edge defines an adjacency relationship between two nodes. Therefore, in order to handle such relationships, we propose to define a new hypergraph representation encoding a molecular graph.

A directed hypergraph [START_REF] Berge | Graphs and hypergraphs[END_REF] H = (V, E) can be defined as a set of vertices V and a set E = E e ∪E h encoding the union of a set of edges E e ⊂ V ×V and a set of hyperedges E h ⊂ P(V ) × P(V ) where P(V ) encodes the set of all subsets of V . Note that unlike classical hypergraph's definitions, we explicitly distinguish the hyperedges from the classic edges. An ordered hyperedge e = (s u , s v ) ∈ E h with s u = {u 1 , . . . , u i } and s v = {v 1 , . . . , v j } defines an adjacency relationship between node sets {u 1 , . . . , u i } and {v 1 , . . . , v j }, as illustrated in figure 5(c). In the following, we assume that if there exists an e ∈ E with e = (s 1 , s 2 ) then it exists e ′ ∈ E with e ′ = (s 2 , s 1 ) and e and e ′ are considered as a same and unique hyperedge. Such a definition allows us to encode adjacency relationships between an acyclic atom and a set of cycles, each cycle being encoded as a vertex.

A molecular graph G = (V, E, µ, ν) can be encoded as a relevant cycle hypergraph

H CH (G) = (V CH , E CH , µ CH , ν CH ). Considering the relevant cycle graph G C (G), the set of relevant cycles C R (G) is associated to a set V C R ⊆ V corresponding to the union of all nodes included within a cycle, i.e. V C R = {u ∈ c V (v) | v ∈ V C }. Similarly, E C R = {e ∈ c E (v) | v ∈ V C }
encodes the set of edges included within a relevant cycle (section 5.2). The relevant cycle graph encodes all nodes and edges of a graph G which are included within a cycle. Therefore, molecular parts which are missing in the relevant cycle graph correspond to acyclic parts, i.e. nodes and edges which are not included within a cycle. These sets are respectively defined by the complement of V C R , resp. E C R , in V , resp. E. In order to encode both acyclic and cyclic parts into the relevant cycle hypergraph, V CH is defined by the union of two subsets. A first subset V C encoding the set of relevant cycles and a second subset {V \ V C R } corresponding to the set of atoms not included within a cycle.

Considering the set of vertices V CH , we can define a function p :

V → P(V CH ) defined as p(u) = {u} if u / ∈ V C R and p(u) = {v ∈ V C | u ∈ c V (v)} if not.
The set p(u) encodes either the cycles which include atom u or the atom itself. Similarly to vertices, the set of hyperedges E CH is composed of two subsets:

1. A set of edges E e CH composed of: • edges between relevant cycle nodes which correspond to the set of edges E C defined in the relevant cycle graph;

• edges e = (p(u),

p(v)) such that (u, v) ∈ E \ E C R , |p(u)| = 1 and |p(v)| = 1.
This set of edges corresponds to edges of the molecular graph G which encode three distinct adjacency relationships:

an edge connecting two acyclic atoms; -an edge between two single relevant cycles (for example C 2 and C 4 in figure 4); -or an edge connecting an acyclic atom of G to a single relevant cycle (C 3 and N in figure 4).

and a set of hyperedges

e = (p(u), p(v)) ∈ E h CH such that (u, v) ∈ E \ E C R and |p(u)| > 1 or |p(v)| > 1.
This set of hyperedges encodes special cases depicted in figure 5 where an edge connects at least two distinct relevant cycles to another part of the molecule. This edge connects two sets of vertices s 1 = p(u) and s 2 = p(v) and is thus encoded by an hyperedge e = (s 1 , s 2 ) ∈ E h CH . The labeling function µ CH is equal to the vertex labeling function µ C of the relevant cycle graph (section 5.1) for each vertex v ∈ V C corresponding to a relevant cycle, and to the vertex labeling function µ of the mocular graph otherwise. In the same way, the edge labeling function ν CH is equal to the edge labeling function ν C of the relevant cycle graph for each edge encoding an adjacency relationship between two cycles and to the one of the molecular graph (ν) otherwise. Since hyperedges correspond to edges of the molecular graph connecting at least two distinct cycles to another part of the molecule, their labels are set as the ones of their associated edges in the molecular graph.

(G) = (V CH , E CH ). If ∃e = (s 1 , s 2 ) ∈ E h CH and c 1 , c 2 ∈ V CH such that {c 1 , c 2 } ⊆ s 1 or {c 1 , c 2 } ⊆ s 2 , then (c 1 , c 2 ) ∈ E e CH , i.e. c 1 is adjacent to c 2 .
Proof 4 Without loss of generality, let us assume that {c 1 , c 2 } ⊆ s 1 . Then by construction of

E h CH , ∃e = (u, v) ∈ E such that {c 1 , c 2 } ⊆ p(u) = s 1 . By definition of function p and since c 1 , c 2 ∈ C R (G), it holds that u ∈ c V (c 1 ) ∩ c V (c 2 ). By definition of the relevant cycle graph, (c 1 , c 2 ) ∈ E C ⊆ E e CH .

Similarity between relevant cycle hypergraphs

Previous section defines a new molecular representation which allows to encode adjacency relationships between cyclic and acyclic parts of a molecule. In order to apply QSAR/QSPR methods using this molecular representation, we have to define a kernel between relevant cycle hypergraphs. An hypergraph encodes global relationships defined between sets of nodes. Conversely, treelet kernel is defined on graphs where relationships are defined locally between elementary nodes. Therefore, in order to apply treelet kernel to our hypergraph representation, we have to transform global relationships encoded in an hypergraph representation to local relationships between elementary nodes. This transformation may be performed by merging sets of vertices incident to an hyperedge. This merging operation relies to transform hyperedges to edges. An equivalence relation ∼ between vertices c ∈ V RH is defined by the transitive closure of the relation R such that c 1 R c 2 if and only if it exists e = (s 1 , s 2 ) ∈ E CH such that {c 1 , c 2 } ⊆ s 1 or {c 1 , c 2 } ⊆ s 2 . Using equivalence relation ∼ previously defined, we can define the equivalence class c = {c ′ ; c ∼ c ′ } of a node c ∈ V CH . Intuitively, two cycles sharing a common hyperedge belong to the same equivalence class. Then, by applying a contraction kernel on each class c, we define a reduced relevant cycle graph (figure 5(d)) G RC (G) = (V RC , E RC , µ RC , ν RC ) associated to graph G with:

• V RC = {c, c ∈ V CH }, • E RC = {e = ( c1 , c2 ), (c 1 , c 2 ) ∈ E CH , c 1 ≁ c 2 }.
Intuitively, the set of edges E RC corresponds to the union of the usual edges E e CH of H CH and the transformation of hyperedges E h CH into usual edges. Labeling function µ RC (c), c ∈ V CH , is defined in a canonical way by the sequence of vertex and edge labels encountered during a depth first traversal of the spanning tree covering c and having the lowest lexicographic order. Such a spanning tree exists since any pair of vertices {c, c ′ } sharing a same hyperedge is connected (Proposition 4).

Considering reduced relevant cycle graph, our new similarity measure based on treelet kernel is defined in two parts. A first step consists in extracting the set of treelets T 1 = T (V CH , E e CH ). The couple (V CH , E e CH ) corresponds to a subhypergraph of H CH which does not include any hyperedge and which thus corresponds to a graph. The set of treelets T 1 does not include special cases illustrated in figure 5. These special cases, corresponding to hyperedges e ∈ E h CH , are encoded by the set of treelets T 2 which is defined as the set of treelets extracted from the reduced relevant cycle graph G RC . In order to avoid redundancy, we reduce the set of treelets T 2 to treelets containing at least one edge corresponding to an hyperedge e h ∈ E h CH . Finally, we define the set of treelets T CR (G) associated to a molecular graph G by T 1 ∪T 2 . Our treelet kernel extension is then defined as a treelet kernel applied on the set of treelets T CR :

k RH (G, G ′ ) = t∈T CR (G)∩T CR (G ′ ) k(f t (G), f t (G ′ )) (23)
where k(., .) is defined as a kernel between real numbers. Note that, multiple kernel learning methods defined in section 2.1 can be applied in order to extract relevant subtrees involving cycles and acyclic parts. 20) (4) k C (Equation 21) (5) k T + λk C (Equation 22) (6) k RH (Equation 23)

The two new molecular representations defined in this section allows us to encode molecular cyclic information into our treelet kernel. Cyclic information can be taken into account separately from acyclic information by considering the relevant cycle graph or combined with acyclic information using the global molecular representation provided by the relevant cycle hypergraph. Prediction ability of each method depends on the chemoinformatics problem addressed by each dataset.

Experiments

We proposed several extensions of the treelet kernel in order to define a more accurate similarity measure for QSAR/QSPR problems. Table 1 summarizes the different informations took into account by each proposed extension. The first line corresponds to the treelet kernel k T [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] which only takes into account acyclic information. Based on the hypothesis that similar sub structures should have a similar influence, the first extension (line 2) aims to include the comparison of non-isomorphic treelets into kernel computation. Similarity between treelets is deduced from graph edit distance. Second, the next extension (line 3) consists in encoding stereo information which is crucial for predicting certain molecular properties. Finally, the last three extensions (lines 4 to 6) consist in encoding cyclic information into graph kernels. First, we have proposed to apply the treelet kernel on the relevant cycle graphs (line 4) which allows us to encode the cyclic system of a molecule. However, considering such a kernel does not allow us to take into account acyclic parts. This drawback can be tackled by computing a kernel as a combination of a treelet kernel and a treelet kernel on relevant cycle graph (line 5). The parameter λ allows to weight the influence of the cyclic information and is choosen by cross-validation. However, this combination dissociates cyclic and acyclic parts and can't thus encode relationships between cyclic and acyclic parts of a molecule. Therefore, we proposed the relevant cycle hypergraph as a new molecular representation. This hypergraph representation allows us to encode the whole molecular graph and to explicitly encode cyclic information. We adapted the treelet kernel (line 6) in order to compare relevant cycle hypergraphs which defines thus a similarity measure 16) and σ range in [0. [START_REF] Johnson | Concepts and Applications of Molecular Similarity[END_REF][START_REF] Poezevara | Discovering emerging graph patterns from chemicals[END_REF] for RBF gaussian kernels and λ ∈ [10 -7 , 1] for kernel ridge regression. We also consider linear, gaussian, intersection and binary kernels as basic kernel between treelet's frequencies.

Boiling point prediction

The first prediction problem consists in predicting the boiling point of 185 acyclic molecules [START_REF] Cherqaoui | Use of a neural network to determine the normal boiling points of acyclic ethers, peroxides, acetals and their sulfur analogues[END_REF]. The results obtained using a kernel ridge regression with corresponding execution times in seconds are displayed in table 2. Column "learn." corresponds to the time required to compute the Gram matrix and column "pred." corresponds to the time required to predict the boiling point of a new molecule. We measure the accuracy of each method by computing the Root Mean Squared Error (column "RMSE") and confidence intervals at 95% (±). In this first experiment, we tested different graph kernels based on bags of patterns and two of our proposed extensions in order to show the gain obtained by the pattern weighting step and the comparison on non-isomorphic patterns. The two first lines of table 2 correspond to graph kernels based on linear patterns: the first line corresponds to a kernel based on paths extracted from the graphs [START_REF] Suard | Kernel on bag of paths for measuring similarity of shapes[END_REF] and the second line corresponds to the random walks kernel, as defined in [START_REF] Kashima | Kernels for graphs[END_REF]. Line 3 corresponds to the tree pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF]. Line 4 corresponds to our treelet kernel (with λ = 1 and an intersection kernel) and lines 5 and 6 correspond to results obtained by including the comparison of similar patterns into treelet kernel computation using graph edit distance with c i = 3 and c s = 1 (section 3 and table 1, line 2). Best results have been obtained with an intersection kernel, λ = 10 -2 and σ inter = 0.5 for line 5 and σ inter = 1 for line 6. Finally, line 7 corresponds to the combination of the treelet kernel and MKL using SVM regression with C = 10, ǫ = 0.005 and an intersection kernel (section 2.1.1).

The results show that the low expressiveness of linear patterns does not allow to predict accurately the boiling point of molecules conversely to kernels based on non linear patterns which obtain a more accurate prediction. In addition, we can note that the use of a limited set of structures allows to obtain low execution times. Then, we can note that the comparison of non-isomorphic patterns allows to obtain a better prediction accuracy than the treelet kernel, hence showing the relevance of including pairs of non-isomorphic treelets within kernel computation. In addition, we can note that the use of an exact edit distance provides a slightly better accuracy than using an approximate edit distance. Finally, best results are obtained thanks to the use of multiple kernel learning which allows to only consider relevant patterns at the cost of an higher computational time. However, note that prediction time is not altered by multiple kernel learning step since weighting is only computed during the learning step. The second regression experiment aims to show the relevancy of taking into account stereoisomerism. This experiment consists in predicting the optical rotation angle, which strongly depends on stereoisomerism properties, of 35 acyclic and chiral molecules by using a leave one out prediction and a SVM regression. Table 3 shows results obtained by the treelet kernel with ǫ = 20, C = 2 and σ = 0.5 (line 1), tree pattern kernel adapted to stereoisomerism [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] (line 2), stereo treelet kernel (table 1, line 3) with ǫ = 10, C = 10 3 and σ = 4 (line 3) and a combination of two kernels with ǫ = 5, C = 2 and a binary kernel (line 4). This combination consists in predicting the sign of the optical rotation angle using the stereo treelet kernel and predicting its absolute value using the treelet kernel. On one hand, we can note that treelet kernel is not able to predict correctly this property since it can not distinguish two stereoisomers having nearly opposite optical rotation angles. On the other hand, stereo treelet kernel allows to distinguish stereoisomers and obtains a better prediction accuracy. The combination of the two kernels leads to the best results. Sign prediction step Therefore, patterns which include stereo information are useful to predict the sign of the optical rotation angle and patterns which do not are useful to predict its absolute value. As the tree pattern kernel adapted to stereoisomerism does not clearly identify the contribution of each kind of patterns, it can not obtain as good results as the stereo treelet kernel.

Optical rotation prediction

Predictive Toxicity Challenge

The third experiment aims to show the relevancy of explicitly including the cyclic information of molecules into kernel computation. The dataset used in this experiment is taken from the Predictive Toxicity Challenge [START_REF] Toivonen | Statistical evaluation of the predictive toxicology challenge 20002001[END_REF] which aims to predict carcinogenicity of chemical compounds applied to four type of animals : female (F) and male (M) rats (R) and mice (M). This experiment consists in ten different datasets for each class of animal, each of them being composed of one training set and one test set. The amount of predicted molecules is equal to 336 for male mice, 349 for female mice, 344 for male rats and 351 for female rats. Table 4 shows the amount of correctly classified molecules over the ten test sets for each method and for each class of animal. In addition, the column time shows the learning time required by gram matrices computation and by the SVM learning step. First line of table 4 corresponds to original treelet kernel. The three next lines correspond to methods encoding three different levels of cyclic information. Line 2 corresponds to cyclic pattern kernel using relevant cycles [START_REF] Horváth | Cyclic pattern kernels revisited[END_REF]. Line 3 corresponds to treelet kernel applied on the relevant cycle graph (section 5.2 and table 1, line 4) which allows to encode relevant cycles relationships. Line 4 corresponds to the adaptation of treelet kernel to relevant cycle hypergraphs (section 5.3 and table 1, line 6) which allows to encode ad-jacency relationships between relevant cycles and acyclic parts. First, we can note that finer the cyclic information is encoded, better is the accuracy among the three methods explicitly encoding it (lines 2 to 4). These results validate our hypothesis on the importance of encoding adjacency relationships between relevant cycles in one hand and between relevant cycles and acyclic parts on the other hand. From a computational point of view, we can note that the low number of treelets extracted from the relevant cycle graph allows a fast learning step. In addition, the computational time required by the transformation of molecular graphs into relevant cycle graphs is balanced by the lower number of extracted treelets. The second part of table 4 (lines 5 to 8) shows results obtained by different kernels based on treelet kernel combined with a multiple kernel learning step as defined in section 2.1. Multiple kernel learning allows to significantly enhance the accuracy obtained by the different tested kernels (according to a Friedman test with a p-value equals to 0.01) at the price of an higher computational time. After this weighting step, treelet kernel adapted to relevant cycle hypergraph (line 7) obtains the best results on two datasets over four (datasets MM and FM) and kernel only based on acyclic patterns obtains the best results over the two others datasets (line 5, datasets MR and FR). This observation can be explained by the fact that some properties are influenced by cyclic information whereas some others depend more on acyclic information. Note that multiple kernel learning step selects about 25 relevant treelets among the 5700 extracted from relevant cycle hypergraphs. In comparison, treelet weighting step selects 150 treelets among 3500 when applied to molecular graph. The selected treelets consists of non linear treelets and treelets having 6 nodes which validates the use of non linear patterns composed of up to six nodes. Finally, treelet kernel on molecular graph has been combined with treelet kernel on relevant cycle hypergraph (table 4, line 8). This combination of two molecular representations obtains the best results on all datasets by taking the best combination of the two kernels for each dataset. As observed on the second part of results, best results are obtained for a λ equals to 0.9 for mice's datasets whereas best results are obtained for a λ equals to 0.1 for rats' datasets.

Conclusion

In this article, we have presented several extensions to treelet kernel which take into account chemical relevant characteristics such as pattern weighting, the contribution of non-isomorphic sub structures, stereoisomerism and cyclic information. As shown in experiments, these extensions allow to enhance prediction results obtained on several chemoinformatics datasets. In order to achieve a better prediction accuracy, we aim to encode the substituents' relative positioning around a cycle in order to encode a finer cyclic information. Another outlook consists in using optimal solvers such as MKL to define an inter treelet kernel based on a training set instead of using an a priori treelet edit distance. Finally, our next work regarding stereo information will focus on extending stereo treelet

Figure 1 :

 1 Figure 1: Set of treelet's structures

  (a) Different steps describing an edit path. (b) Edit paths passing through maximum common structural subgraphs { Ĝ1 1 , . . . , Ĝn 1 1 } and { Ĝ1 2 , . . . , Ĝn 2 2 }. Dashed lines correspond to structural operations, other to substitutions.

Figure 2 :

 2 Figure 2: Edit path scheme(a) and edit paths passing through maximum common structural subgraphs(b).

Proposition 1

 1 Given two graphs G 1 and G 2 , let us denote by δ v the number of nodes of their maximum structural common subgraph and by δ e the maximal number of edges of their structural common subgraphs. If c vd +cvi cvs ≥ δ v + ces cvs δ e and c ed +cei ces ≥ δ e + cvs ces δ v , then Ĝ1 is a maximal common structural subgraph of G 1 and G 2 .

  (a) Molecule with one stereo vertex. Minimal stereo subtree is surrounded by a dashed line. (b) Contracted graph obtained by contracting minimal stereo subtree into node C S .

Figure 3 :

 3 Figure 3: A stereoisomer with minimal stereo subtree and contracted graph representation.

Figure 4 :

 4 Figure 4: A molecular graph and its associated relevant cycle graph. Canonical key µ C (C 2 ) is equal to C1C1C1O1C1C2C.

  Molecular graph G including cycles. (b) Relevant cycle graph G C (G). Relevant cycle hypergraph H CH (G). Hyperedge e encodes an adjacency relationship between atom O and C1 and C2. Reduced relevant cycle graph G RC (G).

Figure 5 :Proposition 4

 54 Figure 5: Different encodings of a same molecule.

  Ĝn2 2 } the sets of subgraphs of G 1 and G 2 structurally isomorphic to Ĝ (figure2(b)). Considering proposition 2, any optimal edit path P between G 1 and G 2 should pass through one Ĝi1 and Ĝj 2 . The cost associated to P can be decomposed into two parts: a structural cost γ struc (P ), corresponding to insertion and deletion operations, and a substitution cost γ label (P ) corresponding to label substitutions required

	to transform Ĝi 1 into Ĝj

1 , . . . , Ĝi 1 , . . . , Ĝn1 1 } and { Ĝ0 2 , . . . , Ĝi 2 , . . . , 2 :

Table 1 :

 1 Information encoded by each treelet's kernel extension.

	Kernel	Acyclic	Non-isomorphic Stereo Cyclic patterns	Acyclic \Cyclic
	(1) k T (Equation 2)
	(2) k inter (Equation 8)
	(3) k T S (Equation

Table 2 :

 2 Boiling point prediction of 185 acyclic molecules. Computation times are displayed in seconds. between relevant cycles, acyclic parts, and between relevant cycles and acyclic parts. These contributions have been tested on three chemoinformatics datasets 2 in order to determine their relevancy from an experimental point of view. These experiments consists in two regression problems and one classification problem. Best parameters have been tuned by using a cross validation over the intervals [10 -2 , 10 4 ] for C (equation6) and [σ(y), σ(y) 20 ] for ǫ in SVM problems, where σ(y) denotes the standard deviation of the predicted property. The values of σ inter (equation

	Method

Table 3 :

 3 Optical rotation angle prediction on acyclic chiral molecules.

	Method	RMSE ( • )	Time (s)
	(1) Treelet kernel	26.24 ± 6.43	2
	(2) Stereo tree-pattern kernel	24.16 ± 5.64	21
	(3) Stereo treelet kernel	15.63 ± 3.54	0.4
	(4) Treelet and stereo treelet kernel combination 14.80 ± 3.30	2

Table 4 :

 4 Classification accuracy on PTC dataset. errors by stereo treelet kernel, hence showing the relevancy of this extension, and angle absolute value prediction performed by treelet kernel allows to slightly enhance the results obtained by the stereo treelet kernel alone.

	Method	# correct predictions MM FM MR FR Time (s)
	(1) Treelet kernel (TK)	208 205 209 212	27
	(2) Cyclic pattern kernel	209 207 202 228	≤ 1
	(3) TK on relevant cycle graph (TC)	211 210 203 232	≤ 1
	(4) TK on relevant cycle hypergraph (TCH) 217 224 207 233	19
	(5) TK + MKL	217 224 223 250	85
	(6) TC + MKL	216 213 212 237	62
	(7) TCH + MKL	225 229 215 239	117
	(8) λ TK + (1 -λ) TCH	225 230 224 252	202
	is performed without

C N denotes the atom C of the branch C-N, O H the atom O of the branch O-H and O Cl the atom O of the branch O-Cl.

All these datasets are available on the IAPR TC15 Web page: https://iapr-tc15.greyc.fr/links.html

Acknowledgements

The authors would like to thank the computing center CRIHAN for providing the resources required by the computations of experiments.

kernel to cyclic molecules in order to enlarge its application domain.