Alain Billionnet
email: billionnet@iie.cnam.fr

Sourour Elloumi
email: elloumi@cnam.fr

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

Keywords: Integer Programming, Quadratic 0-1 optimization, Convex Quadratic Relaxation, Semidefinite Positive Relaxation, Experiments, Max-cut 1 corresponding

In this paper, we consider problem (P ) of minimizing a quadratic function q(x) =

x t Qx + c t x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x 2 i = x i , we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P ) is solved.

We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods to several other exact solution methods. Furthermore, we report computational results for the max-cut problem.

Introduction

Consider the quadratic function q(x) = x t Qx + c t x and the 0-1 quadratic problem (P ) : min {q(x) :

x ∈ {0, 1} n } ( 1
)
where Q is an n × n real matrix, and c ∈ R n . Without loss of generality, we can suppose that Q is symmetric and also that the diagonal terms of Q are equal to 0. If this is not the case, Q can be converted to the symmetric form (Q + Q t )/2 and the linear terms q ii x i can be substituted for the diagonal terms q ii x 2 i because x 2 i = x i for x i ∈ {0, 1}. Problem (P ) is NP-hard and has numerous applications. Consult, for example, [START_REF] Hansen | A simple enumerative algorithm for unconstrained 0-1 quadratic programming[END_REF] and (Boros and Hammer 2001). Furthermore, a recent application of (P ) in the medical field is reported in [START_REF] Iasemidis | Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures[END_REF]).

Various approaches have been used to solve (P ) exactly. Three recent overviews of these approaches are presented in [START_REF] Beasley | Heuristic algorithms for the unconstrained binary quadratic programming problem[END_REF], [START_REF] Helmberg | Solving quadratic (0,1)-problems by semidefinite programs and cutting planes[END_REF], and [START_REF] Hansen | A simple enumerative algorithm for unconstrained 0-1 quadratic programming[END_REF]. One of the possible techniques is to relax (P ) to a tractable nonlinear continuous problem in order to obtain lower bounds. As mentioned in (Poljak and Wolkowicz 1995), this approach was used for different Combinatorial Optimization problems. In addition to the references cited by Poljak and Wolkowicz, we have the following ones, which concern unconstrained quadratic 0-1 programming: McBride and Yormak (1980) and [START_REF] Helmberg | Solving quadratic (0,1)-problems by semidefinite programs and cutting planes[END_REF]. More recently, second order cone programming has been used for solving (P ).

See [START_REF] Kim | Second order cone programming relaxation of nonconvex quadratic optimization problems[END_REF] and [START_REF] Muramatsu | A new second order cone programming relaxation for max-cut problems[END_REF].

Beside these exact methods, several heuristic approaches have been proposed for solving large instances of (P). The reader can find a brief review and many references on the subject in (Merz and Katayama (to appear)).

For any vector u ∈ R n , let us define the perturbed function q u (x) in the following way

q u (x) = x t (Q -diag(u))x + (c + u) t x (2)
where diag(u) is the diagonal matrix obtained from vector u. One can easily observe that q u (x) can also be written as q(x) + n i=1 u i (x ix 2 i ), and that q u (x) = q(x) for all x ∈ {0, 1} n . Therefore, one can solve problem (P ) by solving the equivalent problem 2 (P u ) : min {q u (x) : x ∈ {0, 1} n } (3) Moreover, we define the lower bound β(u) of the optimal value of problem (P ) as the optimal value obtained by the continuous relaxation of problem (P u )

β(u) = min {q u (x) : x ∈ [0, 1] n } (4)
In this paper, we will focus on vectors u such that matrix (Qdiag(u)) is positive semidefinite ((Qdiag(u)) 0). In this case, computing the lower bound β(u) amounts to solving a convex quadratic problem, which can be done in polynomial time (see [START_REF] Kozlov | Polynomial solvability of convex quadratic programming[END_REF]). Our motivation comes from the fact that the new versions of optimization software are now able to solve quadratic integer programs, that have a convex quadratic objective function and a set of linear constraints. This new tool is called an MIQP solver. Hence, whenever (Qdiag(u)) 0, these new versions can handle problem (P u ) directly. This gives us a family of exact solution methods for problem (P ), which differ by the preprocessing phase, i.e. the method used to find an appropriate vector u.

In Section 2, we present a simple way to find a first vector u with (Qdiag(u)) 0, based on the computation of the smallest eigenvalue of matrix Q. This constitutes a first exact solution method for problem (P ).

In Section 3, we consider the problem of finding the best vector u * , i.e. that maximizes β(u) under the constraint (Qdiag(u)) 0. In addition, we use the known relationship between β(u * ) and semidefinite programming. This relationship provides us with a practical method for computing u * , based on the resolution of an SDP relaxation of problem (P ).

This constitutes a second exact solution method for problem (P ), through the resolution of problem (P u * ). SDP relaxations are known to provide tighter bounds than quadratic convex relaxations but more effort is required to compute them. In our second method, the strength of an SDP relaxation of (P ) is captured in a quadratic convex relaxation of (P ).

Sections 4 and 5 report the computational results together with comparisons with existing methods. Section 6 is a conclusion.

A first choice of the perturbed function q u

Let λ min ∈ R be the smallest eigenvalue of matrix Q. If at least one term of Q is nonzero then λ min is a real negative number. Consider the perturbed function q u where u = λ min e and e is the vector of all ones

q λ min e (x) = x t (Q -diag(λ min e))x + (c + λ min e) t x
Matrix (Qdiag(λ min e)) is positive semidefinite and then function q λ min e is convex. So, problem (P λ min e ) can be solved by an MIQP solver. Recall that problems (P λ min e ) and (P ) are equivalent in the sense that ∀ x ∈ {0, 1} n , q λ min e (x) = q(x).

The idea of transforming (P ) into (P λ min e ) has already been considered by [START_REF] Hammer | Some remarks on quadratic programming with 0-1 variables[END_REF]. However, to the authors' knowledge, no computational results associated to this approach have been reported in the literature.

    and c =     -119 27 -187 -2     .
The smallest eigenvalue of matrix Q is λ min = -149.8 and the bound β(λ min e) is equal to -302. [START_REF] Pardalos | Computational aspects of a branch and bound algorithm for quadratic 0-1 programming[END_REF]. The optimal value is -267.

3 An optimal perturbed function q * u We have seen in the introduction that any vector u satisfying (Qdiag(u)) 0 gives a new problem (P u ), defined by (3), and equivalent to our initial problem (P ), defined by [START_REF] Beasley | Heuristic algorithms for the unconstrained binary quadratic programming problem[END_REF]. We also recall the definition β(u) = min {q u (x) : x ∈ [0, 1] n } already given by (4).

As mentioned above, any problem (P u ) can be submitted for resolution by the branchand-bound algorithm of the MIQP solver. But, it is well known that the behavior of a branch-and-bound algorithm is very dependent upon the bound at the root of the search tree. Hence, we would say that formulation (P u 1 ) is better than formulation (P u 2 ) if its continuous relaxation amounts to a better bound or, in other words, if β(u 1 ) is larger than β(u 2 ). Furthermore, one can make an "optimal" choice by computing a vector u * that maximizes β(u), under the constraint (Qdiag(u)) 0. More precisely, let us define u * and the associated lower bound β * as

β * = β(u * ) = max u∈R n (Q-diag(u)) 0 β(u) (5)
It is already known that β * can be computed as the optimal value of a semidefinite programming relaxation of problem (P ). This result appears, for example, in (Poljak, Rendl, and Wolkowicz 1995), but we can consider it was already proved in [START_REF] Körner | Zur effektiven Lösung von Booleschen, quadratischen Optimierungsproblemen[END_REF], [START_REF] Shor | Class of global minimum bounds of polynomial functions[END_REF], and [START_REF] Körner | A tight bound for the Boolean quadratic optimization problem and its use in a branch and bound algorithm[END_REF]). Besides, [START_REF] Lemaréchal | SDP relaxations in combinatorial optimization from a Lagrangian point of view[END_REF] give an interpretation of this result through lagrangian duality. In order to recall this result inside our context and notations, we state the following proposition.

Proposition 1 Bound β * is equal to the optimal value of the semidefinite program:

(SDP ) : max r s.t.:

-r

1 2 (c + u) t 1 2 (c + u) Q -diag(u) 0 r ∈ R u ∈ R n
and is also equal to the optimal value of its dual:

(DSDP ) : min c t x + n i=1 n j=1 Q ij X ij s.t.: X ii = x i i = 1, ..., n 1 x t x X 0 x ∈ R n X ∈ R n×n
Moreover, if (r * , u * ) is an optimal solution of (SDP), then (Qdiag(u * )) 0 holds and

β(u * ) = β * .
Proposition 1 gives a practical method for computing the best vector u * and the lower bound β * , based on the resolution of a semidefinite program. Let us consider again the instance of Example 1 to show that β * can be strictly better than β(λ min e). The optimal vector one obtains by solving the SDP is u * = (-174.85, -74.62, -177.62, -145.71), and the corresponding lower bound is β * = β(u * ) = -290.50, which is indeed better than β(λ min e) = -302.25. Recall that, in this example, the optimal value is equal to -267.

The SDP relaxation we consider is not new. It has already been considered by several authors. It was shown in [START_REF] Goemans | 878-approximation for max cut and max 2sat[END_REF]) that, for the max-cut problem with non-negative weights -a particular case of problem (P )-, this SDP relaxation leads to a bound with an error of at most 13.8%. Furthermore, in [START_REF] Helmberg | Solving quadratic (0,1)-problems by semidefinite programs and cutting planes[END_REF],

this SDP relaxation has been both used in a cutting-plane approach and embedded in a branch-and-bound framework. We provide an alternative use of this SDP relaxation, as a preprocessing phase of an MIQP resolution.

4 Computational results for the Unconstrained Quadratic 0-1 Problem

We will first describe the machine and software we use all along the computational results in the current section and in Section 5 . Then we consider a large set of instances, randomly generated by the generator in [START_REF] Pardalos | Computational aspects of a branch and bound algorithm for quadratic 0-1 programming[END_REF]. We apply the two algorithms of Sections 2 and 3 to these instances and we compare our results to a general linearization method and to methods in the literature. Finally, we provide computational results for a set of 45 benchmak instances introduced in (Glover and al. 1998) and available in OR-Library [START_REF] Beasley | Or-library: Distributing test problems by electronic mail[END_REF]).

Machine and software

Our experiments are carried out on a portable PC with a Pentium IV of 1600 MHz and 1024 MB of RAM.

Implementing our first exact solution method described in Section 2 is particularly easy.

The preprocessing phase consists of computing the smallest eigenvalue λ min . We do this using Scilab (Gomez 1999).

For our second exact solution method described in Section 3, the preprocessing phase consists of computing the best vector u * as part of an optimal dual solution (r * , u * ) for problem (DSDP ). In order to solve (DSDP ), we use SDP S, the modeling language for semidefinite programming designed by [START_REF] Delaporte | Sdp s : A tool to formulate and solve semidefinite relaxations for bivalent quadratic problems[END_REF]. SDP S works with SBmethod, an SDP solver that implements the spectral bundle method of [START_REF] Helmberg | A spectral bundle method for semidefinite programming[END_REF].

Then, for our two solution methods, the preprocessing phase is followed by the exact solution phase. For this, we use the modeling language AMPL (Fourer et al. 1994) together with the MIQP solver of CPLEX 8.1 [START_REF] Ilog | ILOG CPLEX 8.0 Reference Manual[END_REF]. Observe that only the formulation (P λ min e ) or (P u * ) is provided to the solver. For example, we do not provide a starting feasible solution although this could be done easily.

Results and comparisons for randomly generated Instances

We use the Sparse Problem Generator of (Pardalos and Rodgers 1990) which we implemented in C ++. We restrict our parameters to the following profile, already used by several authors:

-the linear (or diagonal) coefficients c i are in the range [-100, 100],

-the off-diagonal coefficients of the symmetric matrix Q are in the range [-50, 50], and,

-matrix Q has a density equal to d, a fraction of 1. This is a parameter of the generator.

Density is here meant to be the probability that a nonzero will occur for any off-diagonal entry.

For any considered pair (n, d) where n is the number of variables and d, the density of matrix Q, we generate 10 instances with seeds 1, 2, ..., 10. Then, we choose 15 pairs (n, d),

6 of which have been used by [START_REF] Pardalos | Computational aspects of a branch and bound algorithm for quadratic 0-1 programming[END_REF] in their Table 5.4 which was intended to show the limits of their method. These instances have also been used in [START_REF] Hansen | A simple enumerative algorithm for unconstrained 0-1 quadratic programming[END_REF]. The remaining 9 pairs are intended to show the performances and limits of our new solution methods, as shown in Tables 1 and2. For several instances, we could compute the optimal value by our solution methods. But, for the large-sized instances, we only have the value of the best integer solution computed by our second method through the MIQP solver, after three hours of CPU time.

Computational results concerning the solution of P through the solution of

(P λ min e )
In Table 1, Column 1 gives the size n. Column 2 indicates the density of matrix Q. Column 3

gives the average CPU time in seconds for preprocessing, i.e. for computing the smallest eigenvalue λ min . Column 4 gives the average gap at the root, which is also the error associated to lower bound β(λ min e), i.e. β(λ min e)-opt opt where opt is either the optimal value or the value of the best known integer solution obtained as described above. Column 5 gives the number of instances (over 10) for which the MIQP solver was able to solve the quadratic MIP problem within three hours of CPU time. For the instances solved within three hours, Columns 6, 7, and 8 (resp. 10) report the min, average, and max CPU time needed (resp.

number of nodes explored) by the branch-and-bound algorithm to prove optimality. For the instances which could not be solved, the MIQP solver stops with a final gap, i.e. bb-opt opt where bb is the lower bound computed by the branch-and-bound algorithm after three hours.

Column 9 gives this average final gap. For example, for the n = 100 and d = 1 row, 4 instances over 10 could be solved to optimality within an average time of 4080 seconds and after 3736585 nodes have been explored. For the 6 unsolved instances, the final gap is equal to 2.6% in average.

For all the instances of Table 1, the preprocessing phase is very fast, and the gap at the root is rather independent of the size and of the density. These results are already satisfactory if compared to literature and we will show in the following that they are much improved by the results of our second solution method. Computational results concerning the solution of P through the solution of (P u * )

Here, we consider again the same instances. We apply the two-phase solution method described in Section 3. Table 2 reports the results for the instances of Table 1, and the same meaning is associated to each column. When compared to the results of Table 1, we can observe that the gap at the root of the branch-and-bound tree is approximatively divided by 2. This mainly explains the fact that in Table 2, 107 instances over 150 are solved within three hours, i.e., our improved method could solve 23 instances that the first method could not solve within three hours. Moreover, the new method is much faster. For example, for the instances with n=70, and density=0.8, the 10 instances were solved by both of the methods. The new method took 1.7+5.4=7.1 seconds while the first method took 0.3+104=104.3 seconds in average, i.e. the new method is about 15 times faster for those instances.

We can also observe that, as expected, the preprocessing by solving an SDP takes quite a long time. For the (n=100, density=1.0) instances, the computation of the smallest eigen-value by Scilab took about 0.7 seconds in average, versus 4.5 seconds for solving the SDP.

Hence, for those instances, we spent about 4 seconds of additional time to move the gap on the relaxation at the root from 15.3% to 7.6%, and this is globally very profitable. Let us point out that, although only 6 of the (n=120, density=0.8) instances are solved within three hours of CPU time, the gap between the best node and the best known solution after three hours is about 1% for the 4 remaining instances. Comparison with the solution of (P ) by linearization Consider problem (LP ) which is equivalent to (P ):

(LP ) : min As already observed by other authors, the integrality gap associated to problem (LP ) and reported in Column 3 of Table 3 is large for this class of instances. Moreover, when n is large or Q is not sparse, only a few nodes can be explored within three hours. By a brief comparison of Tables 1,2, and 3, we can conclude that the LP-based method outperforms the one based on the solution of (P λ min e ) for sparse instances, but the method based on the solution of (P u * ) largely outperforms the LP-based method for all instances.

n i=1 c i x i + n-1 i=1 n j=i+1 2 * Q ij y ij s.t.: y ij ≤ x i i < j, Q ij < 0 y ij ≤ x j i < j, Q ij < 0 y ij ≥ x i + x j -1 i < j, Q ij > 0 y ij ≥ 0 i < j, Q ij = 0 x i ∈ {0, 1}

Comparison to enumerative methods

Here, we focus on a comparison of our approach to two enumerative methods. A well known enumerative method is the one proposed by [START_REF] Pardalos | Computational aspects of a branch and bound algorithm for quadratic 0-1 programming[END_REF]. [START_REF] Hansen | A simple enumerative algorithm for unconstrained 0-1 quadratic programming[END_REF] improve this method by first transforming the objective function into a posiform.

The main feature of Pardalos and Rodgers algorithm consists in using first order boolean derivatives in order to progressively fix variables in a branch and bound process. Consider the quadratic function of binary variables q(x)

= i c i x i + i j =i c ij x i x j and let ∆ i (x) = c i + j =i c ij x j .
The following property allows to fix some variables: if ∆ i (x) > 0 for all x then

x i = 0 in all optimal solutions, if ∆ i (x) < 0 for all x then x i = 1 in all optimal solutions, and if ∆ i (x) = 0 for all x then there exist an optimal solution with x i = 0 and an optimal solution with x i = 1.

In Hansen et al.'s algorithm, at the root of the search tree, thanks to a max-flow algorithm, q(x) is written as q(x) = c * + φ(x, x), φ(x, x) being a quadratic posiform and c * being a constant as large as possible. The lower bound c * belongs to the family of roof dual bounds [START_REF] Hammer | Roof duality, complementation and persistency in quadratic 0-1 optimization[END_REF]) and is precisely equal to the LP-bound reported in our Table 3.

Recall that φ(x, x), a function of the literals x i and xi = 1x i , is a quadratic posiform if

φ(x, x) = m k=1
a k T k with a k > 0 for all k and T k is a literal or a product of two literals. Then some variables are fixed by using the following so-called persistency property: all minimizing solutions of q(x) satisfy T k = 0 for all k such that T k is a linear term [START_REF] Hammer | Roof duality, complementation and persistency in quadratic 0-1 optimization[END_REF], Our method has an average gap equal to about 7%, smaller by a factor 8 compared to HJM(2000) and by a factor 37 compared to PR(1990). This makes us think that it would still need significantly less CPU time than the two others if a more accurate comparison was carried on by using the same machine.

(

Results for Glover et al. Instances

Here, we consider a set of 45 instances that are available in OR-Library [START_REF] Beasley | Or-library: Distributing test problems by electronic mail[END_REF]). All We first run our method of Section 3 on the 25 instances from classes a, b, and c. Each of these instances are solved within a limit of two hours of CPU time (the largest one having n = 125 and d = 1). But, we also observed that all these instances are much faster solved by the trivial linearization method described above in Section 4.1. The total CPU time needed by the linearization method for these 25 instances is 79 seconds ! The largest CPU time needed by a single instance is 21 seconds and the largest number of branch and bound nodes is 3942. In view of these results and of the results reported in [START_REF] Glover | Adaptive memory tabu search for binary quadratic programs[END_REF] about the exact solution of these instances by the Pardalos and Rodgers software, we can now consider that the linearization method is largely the best to solve these instances.

Then, we consider the 10 instances of class d. For all of them, n = 100, the linear (or diagonal) coefficients c i are in the range [-75, 75], the off-diagonal coefficients of the symmetric matrix Q are in the range [-50, 50], and matrix Q has a density equal to d, a fraction of 1. Table 5 reports the results of our method applied to these instances, where

Column opt provides the optimal solution value. It shows that each of them can be solved within 10 minutes of CPU time. To the best of our knowledge, for 6 instances over 10, they are solved to optimality for the first time. We can also indicate that, when applied to these instances, the linearization method performs very well for instance 1d but fails in solving the remaining instances within a limit of 1 hour of CPU time.

Finally, we consider the instances from classes e (n = 200) and f (n = 500). These instances are globally beyond the practical capability of our method. However, the preprocessing phase by semidefinite programming remains tractable within about 7 minutes for the largest instance (n = 500, d = 1) and the associated gap varies from 5.6% to 10.7%.

Nevertheless, none of these instances could be solved within the limit of 1 hour of CPU time.

Computational results for the max-cut problem

A very large literature concerns max-cut, a central combinatorial optimization problem. Our objective here is to apply our method to max-cut. We make almost no adaptation of our general method described in Section 3. Our computational experiment gives a first idea of what can be obtained by our approach on a particularly-structured problem.

Let G = (V, E) be a weighted undirected graph. The max-cut problem consists in finding a partition (S, V \ S) of the set of vertices V such that the total weight of the crossing edges is maximum. Many equivalent formulations exist for max-cut. We consider the following one, which matches our general problem (P ):

(M C) : min {mc(x) : x ∈ {0, 1} n } with mc(x) = - n i=1 ( n j =i w ij )x i + n i=1 j =i w ij x i x j
where w ij = w ji is the weight of edge (i, j), x i is the decision variable equal to 1 if and only if vertex i is in S, and mc(x) is precisely the cut weight multiplied by -2.

Following the general method described in Section 3, we first solve the SDP relaxation (DSDP M C ) of (M C):

(DSDP M C ) : min -n i=1 ( n j =i w ij )x i + n i=1 j =i w ij X ij s.t.: X ii = x i i = 1, ..., n 1 x t x X 0 x ∈ R n X ∈ R n×n
and we get the optimal convexified function mc (x), which is equivalent to mc(x) over {0, 1} n .

Then, we solve the following quadratic 0-1 problem :

(M C ) : min {mc (x) :

x i 0 = 1, x ∈ {0, 1} n }
The variable fixation x i 0 = 1 is the only adaptation we introduce in our general method described in Section 3. It is a classical trick to break the symmetry of the max-cut solutions.

We choose a vertex i 0 for which j =i w ij is maximum. We observed that this simple trick divides by about 4 the number of nodes while solving (M C ) by the MIQP solver. Observe that, for the results of Tables 6 and7, we let the MIQP solver of CPLEX use the default branching rules for a general mixed integer problem. This turns out, for the max-cut problem, to select a node i and branch on the fact that node i is either in subset S or not.

Following (Helmberg and Rendl 1998), we generate two types of test problems. The first, called G .5 , consists of unweighted graphs with edge probability 1/2. The second type, G -1/0/1 is a weighted (complete) graph with edge weights chosen uniformly from {-1/0/1}. To explore the limits of our method for the max-cut problem, we run it on a 450 nodes graph from the G .5 class. The SDP-based preprocessing phase takes 208 seconds of CPU time. In three hours of the MIQP solver phase, about 320000 nodes are explored. The deviation of the lower bound from the best cut, given after three hours, moves only from 1.56% to 1.51%.

Helmberg and Rendl (1998) consider the same SDP relaxation (DSDP M C ) and combine it with a cutting plane technique. This bounding process is embedded within a branchand-bound algorithm. Our method seems to be competitive with the Helmberg and Rendl's from the computational time point of view. For example, with the 80 nodes G .5 instances of Table 6, Helmberg and Rendl's method needs about one hour and 46 minutes (average on 2 instances) of CPU time on a HP9000/715 workstation while our's needs about 8 minutes, on the above Pentium IV PC. But their branch-and-bound algorithm performs 154 nodes when our's performs 876623 nodes.

In [START_REF] Helmberg | Solving quadratic (0,1)-problems by semidefinite programs and cutting planes[END_REF], the branching rule is carefully discussed and selected among five different rules. All these rules use the so-called edge-branching. Edge branching is commonly used for the max-cut problem. It consists in selecting an edge (i, j) and branch on either (i, j) contributes in the cut or not. It is well-known that, in both cases, the two vertices i and j can be contracted into a single vertex. In our approach, an implementation of this branching scheme can simply be done by adding constraint x i = x j to the quadratic program of one node, and constraint x i + x j = 1 to the other node's. Hence, the convexity of the quadratic objective function is again preserved. An implementation of this specialized branch-and-bound algorithm would probably improve the results of Tables 6 and7. But it makes us loose the ability to use a general-purpose algorithm in the solution process.

Conclusion

In this paper, we have proposed two methods to state the problem of minimizing a quadratic 0-1 function q(x) as the problem of minimizing an equivalent 0-1 function q (x) whose continuous relaxation is convex. The first method is fast and easy to implement since it only requires eigenvalues computation. The second one, which requires the solution of a positive semidefinite program, takes more computation time and is more sophisticated. The experiments show that the relative gap between the optimum of the continuous relaxation of q (x) and the optimum of q(x) is about twice smaller in the second method than in the first one.

In both approaches, the computation of the optimum of the 0-1 function q (x) (and therefore the optimum of q(x)) is entirely carried out by the general-purpose MIQP solver of CPLEX.

At each node of the search tree, the computation of the lower bound consists in minimizing a convex quadratic function over [0, 1] n , which is particularly fast. The experiments show that these two methods allow to minimize quadratic 0-1 functions efficiently in terms of computation time and the size of the problems considered, in comparison to existing methods.

Finally, the approaches that we propose can be easily generalized to linearly constrained quadratic 0-1 optimization problems.

  Billionnet and Sutter 1992). Then, the fixation of variables to 0 or 1 by branching or reduction tests can create new linear terms in the posiform that can be used by relation of the form x i + xi = 1 to improve the lower bound. Conversely, in a classical way, the lower bound is used to fix some variables. Finally, fixation of variables are carried out by using the partial derivatives as in Pardalos and Rodgers algorithm. Table 4 presents a comparison between the method of Pardalos and Rodgers (1990), the one of Hansen et al. (2000) and ours. Each line of this table corresponds to average results for 10 instances. These instances are exactly the same as the instances pointed out by * in Tables 1-3. Hansen et al. run their program and the one of Pardalos and Rodgers on a Sun Sparc SS20/514 MP with 128 MB of RAM, with 0 as initial solution, and Table 4 reports their results.

  these instances were generated by the Pardalos and Rodgers generator and are divided into 5 classes having different characteristics (n, density, and ranges of diagonal and off-diagonal coefficients). These classes are referred to as problem sets a, b, c, d, and e. Problems from classes a, b, and c were already introduced in (Pardalos and Rodgers 1990), the others were generated in (Glover et al. 1998).

Table 1 :

 1 Results through the solution of (P λ min e )

			Preproc				MIQP solver
	n density CPU1 Gap (%) solved (3h)		CPU2		final Gap (%)	nodes
			av.	av.		min	av.	max	av.	av.
	*50	0.4	0.1	15.3	10	0.3	4.3	16.8	0	17865
	*50	0.6	0.2	13.7	10	0.1	3.3	10	0	13007
	50	1.0	0.2	14.5	10	0.2	5.2	19.4	0	16952
	*60	0.2	0.1	16.6	10	0.1	45.4	228	0	185911
	*60	0.4	0.2	15.4	10	1.1	35.7	247	0	111388
	*70	0.3	0.2	13.8	10	0.9	209	1580	0	455052
	70	0.8	0.3	15.1	10	12.6 104 208.5	0	224661
	*80	0.2	0.2	14.5	10	72	681	3447	0	1298802
	100	1.0	0.7	15.3	4	2661 4080 7412	2.6	3736585
	120	0.3	0.4	15.8	0		-		4.4	-
	120	0.8	0.8	16.2	0		-		5.2	-
	150	0.3	0.6	16.7	0		-		NC	-
	150	0.8	1.2	16.2	0		-		NC	-
	200	0.3	1.0	16.8	0		-		NC	-
	200	0.8	2.4	15.5	0		-		NC	-

* : these instances have already been considered in (Pardalos and Rodgers 1990) -: no instance could be solved to optimality within 3h

Table 2 :

 2 Results through the solution of (P u * )

			Preproc				MIQP solver
	n density CPU1 Gap (%) solved (3h)		CPU2		final Gap (%)	nodes
			av.	av.		min	av.	max	av.	av.
	*50	0.4	1	6.1	10	0.1	0.3	0.8	0	910
	*50	0.6	1	5.8	10	0.1	0.3	1	0	1034
	50	1.0	0.7	6.6	10	0.1	0.5	1.7	0	1367
	*60	0.2	2.4	5.5	10	0.1	0.5	1.5	0	1768
	*60	0.4	1.2	9.0	10	0.2	1.4	7.7	0	4366
	*70	0.3	1.7	6.1	10	0.1	2.8	11	0	8841
	70	0.8	1.7	7.3	10	1	5.4	10.6	0	10899
	*80	0.2	4.7	5.9	10	0.6	5.4	28.7	0	16046
	100	1.0	4.5	7.6	10	27.4 372.7 1671	0	370358
	120	0.3	5.5	7.1	10	168 1263.6 4667	0	1405507
	120	0.8	6.8	8.7	6	322 3909.5 9898	1.3	2703558
	150	0.3	9.8	8.4	1		6789		2.5	3964619
	150	0.8	12.2	8.8	0		-		2.9	-
	200	0.3	17.7	8.9	0		-		4.9	-
	200	0.8	22.5	8.5	0		-		4.8	-

* : these instances have already been considered in (Pardalos and Rodgers 1990) -: no instance could be solved to optimality within 3h

Table 3 :

 3 Solution of (P) through (LP) and a MILP solver

	n density Gap (%) solved (3h)		CPU		final Gap (%)	nodes
			av.		min	av.	max	av.	av.
	*50	0.4	55.3	10	0.7	4.4	16.7	0	2297
	*50	0.6	88.4	10	1.8	90.1	250	0	34781
	50	1.0	146.2	7	1130 3420 5555	14.3	393864
	*60	0.2	19.0	10	0.1	0.4	0.8	0	86
	*60	0.4	75.0	10	22	122.8 581	0	49104
	*70	0.3	54.2	10	6	60	208	0	21666
	70	0.8	169.5	0		-		60.2	-
	*80	0.2	36.6	10	1.6	16.3	88	0	6031
	100	1.0	266.6	0		-		187.3	-
	120	0.3	112.2	0		-		NC	-
	120	0.8	267.8	0		-		NC	-
	150	0.3	145.6	0		-		NC	-
	150	0.8	302.4	0		-		NC	-
	200	0.3	186.1	0		-		NC	-
	200	0.8	354.7	0		-		NC	-

* : these instances have already been considered in (Pardalos and Rodgers 1990) -: no instance could be solved to optimality within 3h

Table 4 :

 4 Comparison between Pardalos and Rodgers (PR), Hansen et al. (HJM), and our approach

				Gap (%)		CPU (sec.)
	n density PR (1990) HJM (2000) our PR (1990) (1) HJM (2000) (1) our (2)
	50	0.4	238	55	6.1	317.8	46.4	1.3
	50	0.6	299	88	5.8	-	636.6	1.3
	60	0.2	176	18	5.5	34.2	2.1	2.9
	60	0.4	276	75	9.0	-	3525	2.6
	70	0.3	232	53	6.1	-	6190	4.5
	80	0.2	204	36	5.9	-	5011	10.1
			(1): on a Sun Sparc SS20/514 MP with 128 MB of RAM
			(2): on a PC with a Pentium IV of 1600 MHz and 1024 MB of RAM

Table 5 :

 5 Results through the solution of (P u * ) for d-instances of Glover et al. (n = 100)

				Preproc		MIQP solver
	instance density	opt	CPU1 Gap (%) CPU2	nodes
	1d * * 2d 3d 4d	0.1 0.2 0.3 0.4	6333 * 6579 * 9261 * 10727 *	8.4 3.7 3.6 4.8	4.1 10.0 7.6 8.1	4 188 114 137	9320 367962 216551 224352
	5d	0.5	11626	3.5	8.7	545	786445
	6d	0.6	14207	4.1	7.2	80	108890
	7d	0.7	14476	4.6	8.3	490	598217
	8d	0.8	16352	5.3	6.1	39	46885
	9d	0.9	15656	5.1	8.7	372	411085
	10d	1.0	19102	6.0	6.9	221	241924
	* : these values are already announced to be optimal in (Boros et al. 2005)
	** : instance 1d is solved within 1.7 seconds and 59 nodes by the linearization method

Table 6 :

 6 Results for the G .5 instances through the solution of (P u * )

		Preproc				MIQP solver
	n CPU1 Gap (%) solved (3h)		CPU2		final Gap (%)	nodes
		av.	av.		min	av.	max	av.	av.
	40	0.9	2.5	10	0.2	1.0	3.2	0	1894
	50	1.1	2.6	10	2.4	7.3	17.2	0	11239
	70	2.8	2.4	10	7.2	103	128.4	0	242225
	80	4.0	2.2	10	35.5 481 1934.4	0	876623
	90	5.9	2.4	9	582 6044 10572	0.3	6317736
	100	7.8	2.2	2	7071 7848	8624	0.4	7915644

Table 7 :

 7 Results for the G -1/0/1 instances through the solution of (P u * )

		Preproc				MIQP solver
	n CPU1 Gap (%) solved (3h)		CPU2		final Gap (%)	nodes
		av.	av.		min	av.	max	av.	av.
	40	0.5	14.5	10	0.1	0.3	0.6	0	1150
	50	0.6	15.5	10	0.2	1.9	6.8	0	6897
	70	1.1	16.2	10	32.6	73	190.6	0	154730
	80	1.3	17.9	10	199 1016 2952	0	1419577
	90	1.9	18.0	6	270 5208 10321	3.1	4787156
	100	2.3	16.6	0		-		2.1	-
			-: no instance could be solved to optimality within 3h


domain: chim sdv

text:
Dany Pechalrieu

Fanny Assemat

Ludovic Halby

Marlene Marcellin

Pengrong Yan

Karima Chaoui

Sahil Sharma

Gabriela Chiosis

Odile Burlet-Schiltz

Paola B Arimondo
email: paola.arimondo@pasteur.fr

Dr Marie Lopez
email: marie.lopez@cnrs.fr

Bisubstrate-Type Chemical Probes Identify GRP94 as a Potential Target of Cytosine-Containing Adenosine Analogs

Keywords: Adenosine-cytosine analogues, chemical probes, affinity-based protein profiling (ABPP), heat shock protein 90 (HSP90), GRP94 inhibitors Cytosine

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Bisubstrate-type enzyme inhibitors consist in the association of two distinct substrate derivatives of an enzyme within the same molecule. In a previous work, we synthesized a library of molecules containing the adenosine motif, present in the SAM (S-adenosyl-L-methionine) cofactor of methyltransferases, bound to cytosine analogues to target DNA methyltransferases (DNMTs). [START_REF] Halby | Rational design of bisubstrate-type analogs as inhibitors of DNA methyltransferases in cancer cells[END_REF] Surprisingly, this class of compounds appeared to target protein (i.e. histone) arginine methyltransferases (PRMTs). [START_REF] Halby | Hijacking DNA methyltransferase transition state analogues to produce chemical scaffolds for PRMT inhibitors[END_REF] Here, in order to better understand the mode of action of these bisubstrate-type enzyme inhibitors we used both conjugates 1 and 2 (FIG. 1), inactive against DNMT, PRMT and histone-lysine N-methyltransferases (KHMT), as a starting point to synthesize chemical probes in order to identify their cellular target using affinity-based protein profiling (ABPP) approach. [START_REF] Kawatani | Affinity-based target identification for bioactive small molecules[END_REF][START_REF] Weigt | Studying epigenetic complexes and their inhibitors with the proteomics toolbox[END_REF] In this strategy, appropriate chemical probes are used to pull-down the protein targets they bind. We chose to incorporate a photoreactive moiety to ensure a covalent crosslink between the chemical probe and protein target. The chemical probes consist of (i) an affinity moiety (e.g. inhibitor) to bind to the target protein, (ii) a photoreactive group to trap the complexes in the cells upon irradiation and (iii) a reactive entity to label and purify the complexes. The key feature consists of using "click chemistry" to label the chemical probe with a fluorescent or affinity tag. We used copper (I)-catalyzed azide-alkyne cycloaddition (CuAAC) as "click reaction" to tag our probes with biotin and purify the associated proteins. [START_REF] Sletten | Bioorthogonal Chemistry: Fishing for Selectivity in a Sea of Functionality[END_REF] To this aim, we designed a chemical probe derived from the adenosine-cytosine scaffold common to compounds 1 and 2 bearing a benzophenone and an alkyne moiety (compound 4, FIG. 1) and an inactive probe containing the probe reactive scaffold (in green) coupled to a Boc protecting group (compound 5, FIG . 1). Five cancer cell lines were treated with the chemical probe, followed by UV irradiation of the cells to initiate crosslinking and a click reaction was then carried out on the cellular extracts to visualize and pull-down the proteins and analyze them by mass spectrometry. A clear protein pattern was observed and the proteomic analysis results identified glucose-regulated protein 94 (GRP94), a chaperone protein, as a potential target. This is not surprising since the adenosine motif is present in the ATP (adenosine triphosphate) cofactor of GRP94. We then validated GRP94 as a target, thus identifying the adenosine-substituted cytosine scaffold as a starting point for novel inhibitors of this family of molecular chaperones.

RESULTS

In our quest for transition state analogues of DNMTs, we synthesized a chemical library of adenosinecytosine conjugates. Two conjugates (compounds 1 and 2), inactive against DNMT, KHMTs and PRMTs (supporting information GRAPH SI-1) are depicted in FIGURE 1 together with the intermediate 3, the corresponding chemical probe 4 and the probe 5 as control.

Chemical synthesis

Synthesis of the adenosine-cytosine analogues 1-3 (SCHEME 1) started from the ethyl cytosine-5carboxylate prepared according to the reported literature. [START_REF] Whitehead | The Reactions of Orthoesters with Ureas. A New Synthesis of Pyrimidines[END_REF][START_REF] Vardanyan | Isomerization/recyclization of some 5-ethoxycarbonyl-pyrimidines[END_REF] The ethyl cytosine-5-carboxylate was then N-alkylated with MOM, BOM or Boc-aminoethyl groups to afford compounds 6-8, respectively. The ester group was then hydrolyzed under basic conditions to afford the carboxycytosine derivatives 9-11. The carboxylic acids 9-11 were coupled to 2',3'-O-isopropylidene-5'-deoxy-5'-aminomethyldenosine 8 to provide the amide derivatives 12-14 and the target compounds 1-3 after deprotection. The synthesis of chemical probe 4 is presented in SCHEME 2. First, mono-functionalization of the diamino-benzophenone was achieved using HATU as a coupling reagent and 5-hexynoic acid to yield compound 15. A small linker was then added on the second primary amine of the benzophenone following lactone ring opening with succinic anhydride, which afforded disubstituted benzophenone 16. The last step involved the coupling of the adenosine-based compound 3 with the benzophenone derivative 16 using HATU as a coupling reagent.

The control probe 5 was synthesized using the alkynylated benzophenone 15 and the Boc-protected 5aminopentanoic acid 17 (SCHEME 2). The Boc group in control probe 5 was kept for in-cell experiments in order to enable cell permeability.

ABPP experiments

For the gel-based experiments, breast cancer MCF-7 cells were first treated with increasing concentrations of the probe 4. This was followed by UV irradiation to allow covalent binding of the benzophenone moiety of 4 to the surrounding proteins, leading to an irreversible binding of the probe to the potential protein targets. After cell lysis, the probe was then reacted with TAMRA-biotin-azide through CuAAC, separated by SDS-PAGE, and visualized by in-gel fluorescence scanning to observe the proteins bound to the probe (FIG. 2A AND 2B). We observed an increase in the labeled protein level from 1 to 50 M of 4 with a highly intense band around 100 kDa. Total protein staining with SYPRO Ruby was used as loading control (FIG. 2B AND 2C lower panel). A 10 M probe concentration was chosen for the following experiments because the best ratio between fluorescence intensity of the band at 100 kDa over the background was obtained at this concentration when compared to 25 or 50 M. As expected, in the absence of irradiation, only a weak non-specific fluorescence was detected with no intense band at 100 kDa (FIG. 2C LEFT). To confirm that the labeling is a consequence of recognition of the bisubstrate moiety, we performed competition experiments by adding 100 M of compound 1 or 2 to the MCF-7 cell culture prior to treatment with the chemical probe 4. Under these conditions, labeling of probe 4 was completely abolished by competition with the free compounds 1 and 2 (FIG. 2C RIGHT), which confirm that labeling is due to the affinity of the bisubstrate moiety for this target.

Considering these promising results in MCF-7 cells, other cancer cell lines, i.e. leukemia cell lines K-562, KG-1 and MOLM-13, and melanoma cell line WM-266-4, were likewise treated in triplicate with probe 4 (FIG. 3). Similar to that observed in MCF-7 cell line, a band at 100 kDa was strongly labeled in each of these cell lines. Additionally, other significant bands were observed at about 75 and 50 kDa for K-562, KG-1 and WM-266-4 and about 50 and 37 kDa for K-562, KG-1 and MOLM-13. DMSO and probe 5 controls were also analyzed by SDS-PAGE and the absence of fluorescent labeling was confirmed under these conditions (two examples are shown in FIG. 3 right panels). As previously, total protein staining with SYPRO Ruby was used as loading control (FIG. 3 lower panel). After probe treatment, UV irradiation and CuAAC functionalization of the probe using the trifunctional compound TAMRA-biotin-azide, probe-bound proteins were enriched with avidin beads. After several washings, proteins were trypsin-digested and peptides subjected to LC-MS/MS analysis.

Proteomic analysis

To identify the potential protein targets, quantitative proteomic analysis was carried out on ABPP samples obtained using chemical probe 4 and control probe 5. The Volcano plot reporting the comparison results is presented in FIGURE 4 for KG-1 cell line and in supplementary information for the other cell lines, i.e. MCF-7, K-562, MOLM-13 and WM-266-4 cell lines (GRAPH SI-2 to 5). For KG-1 cell line, about 540 proteins were identified. However as expected, only 24 proteins were found statistically over-represented (i.e. Log difference >1 or ratio >2 and -Log 10 p-value >1.33) when the active probe 4 was compared to the inactive probe 5 containing only the Boc moiety (FIG. 4 and TABLE SI-1). The different data sets from the five cell lines analyzed were then compared. A Venn diagram analysis revealed that, several proteins were significantly enriched in at least 3 cell lines (FIG. 5A andB, TABLE SI-1 to 5). *Ratio values are reported as a mean of the three replicates.

Among these proteins, HSP90B1, also known as GRP94 (M w = 92 kDa), is the only protein found as significantly enriched in all cell lines with high ratios and abundances in probe 4 treated samples compare to the inactive Boc-containing probe 5 (FIGURE 5 A and C). Therefore, GRP94 represents a promising target of our active chemical probe.

Target validation

To assess the specificity and the binding property of our probe with GRP94, fluorescence polarization competition assays with recombinant GRP94 and HSP90α were performed under conditions of equilibrium binding (FIG. 6). [START_REF] Taldone | Experimental and structural testing module to analyze paralogue-specificity and affinity in the Hsp90 inhibitors series[END_REF] As controls, PU-H71, which is a pan-HSP90 inhibitor under conditions of equilibrium binding but kinetically selects HSP90 residing in epichaperome networks, [START_REF] Rodina | The epichaperome is an integrated chaperome network that facilitates tumour survival[END_REF][START_REF] Joshi | Adapting to stress -chaperome networks in cancer[END_REF][START_REF] Kourtis | Oncogenic hijacking of the stress response machinery in T cell acute lymphoblastic leukemia[END_REF][START_REF] Kishinevsky | HSP90-incorporating chaperome networks as biosensor for disease-related pathways in patient-specific midbrain dopamine neurons[END_REF][START_REF] Taldone | A Chemical Biology Approach to the Chaperome in Cancer-HSP90 and Beyond[END_REF][START_REF] Pillarsetty | Paradigms for Precision Medicine in Epichaperome Cancer Therapy[END_REF] and PU-WS13, which is selective for GRP94 over other isoforms of HSP90, [START_REF] Shrestha | Chemical Tools to Investigate Mechanisms Associated with HSP90 and HSP70 in Disease[END_REF][START_REF] Patel | Structure-activity relationship in a purine-scaffold compound series with selectivity for the endoplasmic reticulum Hsp90 paralog Grp94[END_REF][START_REF] Patel | Paralog-selective Hsp90 inhibitors define tumor-specific regulation of HER2[END_REF] were used and showed submicromolar EC 50 s, as previously described. [START_REF] Patel | Paralog-selective Hsp90 inhibitors define tumor-specific regulation of HER2[END_REF] Interestingly, the EC 50 binding of probe 4 is approximately 10 M for GRP94 and shows no significant binding to HSP90α up to 50 M, the highest concentration tested. This assay allows us to confirm that our probe binds to GRP94 specifically compared to HSP90α, confirming the proteomic data and gels. We also assessed compounds 1 and 2 from which the chemical probe was derived. Although both compounds 1 and 2 showed minor binding to GRP94 at 50 M, no significant binding to HSP90α was observed at this concentration. Therefore, the absence of the large benzophenone-containing moiety led to a lower inhibition potency but the GRP94 selectivity is maintained for compounds 1 and 2.

DISCUSSION

Here we applied the ABPP strategy using a chemical probe derived from adenosine-cytosine conjugates to identify potential binding proteins. Since compounds 1 and 2 have no activity on DNMT, HMTs and PRMTs, we were interested in synthesizing a chemical probe from them to use as bait to trap proteins that bind by the APBB strategy. Chemical probe 4 was synthesized and after incubation with five cancer cell lines, the in-cell UV-crosslinked proteins were labeled following click chemistry with the fluorescent TAMRA for visualization and biotin for affinity purification. The TAMRA label revealed, by SDS PAGE, a clear protein-labeling profile, with a common band around 100 kDa. The proteins crosslinked by probe 4 in the five cancer cell lines were analyzed by quantitative proteomics in comparison to the control probe 5 lacking the affinity moiety and with DMSO. The proteomic data analysis showed that, in all tested cancer cell lines, the ATP-binding molecular chaperone GRP94, of the HSP90 family, was selectively labeled by the chemical probe 4 over the DMSO control and control probe 5. Its detection level was significant and its molecular weight is consistent with the 100-kDa band observed in SDS-PAGE. Additionally, equilibrative nucleoside transporter SLC29A1 (ENT1), hydroxyacyl-CoA dehydrogenase trifunctional multienzyme complex subunit alpha (HADHA), pyruvate carboxylase (PC) and propionyl-CoA carboxylase (PCCA) were also identified by proteomic analysis across at least three cell lines (Figure 5B). SLC29A1 mediates cellular uptake of nucleosides and possess a high affinity for adenosine, chemical moiety present in chemical probe 4. [START_REF] Tromp | Inhibition of nucleoside transport proteins by C8-alkylamine-substituted purines[END_REF] Its activity is inhibited by anticancer agents (dipyridamole and dilazep) [START_REF] Visser | Mutation of residue 33 of human equilibrative nucleoside transporters 1 and 2 alters sensitivity to inhibition of transport by dilazep and dipyridamole[END_REF] and in leukemia, a down regulation of SLC29A1 expression, due to a decrease in H3K27 acetylation, was observed in AraC-resistant cell lines. [START_REF] Stief | Loss of KDM6A confers drug resistance in acute myeloid leukemia[END_REF] HADHA catalyzes mitochondrial oxidations producing acetyl-CoA from fatty acids and is a component of RNA silencing machinery. [START_REF] Kakumani | Association of HADHA with human RNA silencing machinery[END_REF] HADHA expression level is involved in risk of breast cancer [START_REF] Mamtani | Association of HADHA expression with the risk of breast cancer: targeted subset analysis and meta-analysis of microarray data[END_REF] and HADHA has a prognostic value in renal cell carcinoma [START_REF] Zhao | Prognostic significance of two lipid metabolism enzymes, HADHA and ACAT2, in clear cell renal cell carcinoma[END_REF] . PC and PCCA are carboxylases of therapeutic interest since the PC is up-regulated in breast cancer and associated with growth and invasion [START_REF] Phannasil | Pyruvate Carboxylase Is Up-Regulated in Breast Cancer and Essential to Support Growth and Invasion of MDA-MB-231 Cells[END_REF] and PCCA dysfunction leads to severe metabolic disorders [START_REF] Wongkittichote | Propionyl-CoA carboxylase -A review[END_REF] . These carboxylases possess ATP and nucleotide binding sites. Their identification is then compatible with the adenosine-cytosine chemical structure of the probe 4. Despite the interest of these additional targets, GRP94 was selected since its molecular weight is consistent with 100 kDa in-gel observed band. Therefore, further validation experiments were focused on GRP94 and fluorescence polarization experiments confirmed selective binding of probe 4 for GRP94 compared to HSP90α. GRP94 (encoded by the HSP90β1 gene), belonging to the heat shock protein 90 (HSP90) family, is an essential chaperone that has ATPase activity enabling the folding of target proteins to their active conformation. HSP90s are very promising clinical targets and several clinical trials are ongoing. [START_REF] Patel | Structure-activity relationship in a purine-scaffold compound series with selectivity for the endoplasmic reticulum Hsp90 paralog Grp94[END_REF][START_REF] Xiao | Recent Advances in the Discovery of Novel HSP90 Inhibitors: An Update from 2014[END_REF] Contrary to other HSP90 members that are located in the cytoplasm (HSP90α and HSP90β) or the mitochondria (Trap-1), GRP94 resides in the endoplasmic reticulum (ER). GRP94 was shown to be overexpressed in different types of cancers, including breast, colorectal, lung, pancreatic, gastrointestinal cancers and multiple myeloma. [START_REF] Lee | Glucose-regulated proteins in cancer: molecular mechanisms and therapeutic potential[END_REF] The expression of GRP94 is associated with advanced stage, poor survival and cancer growth and metastasis [START_REF] Marzec | GRP94: An HSP90-like protein specialized for protein folding and quality control in the endoplasmic reticulum[END_REF][START_REF] Martinez-Aranda | FN14 and GRP94 expression are prognostic/predictive biomarkers of brain metastasis outcome that open up new therapeutic strategies[END_REF][START_REF] Wei | Glucose-regulated protein 94 mediates metastasis by CCT8 and the JNK pathway in hepatocellular carcinoma[END_REF][START_REF] Buc Calderon | Glucose-regulated protein of 94 kDa contributes to the development of an aggressive phenotype in breast cancer cells[END_REF] and GRP94 was identified as a biomarker of gastrointestinal cancer [START_REF] Tramentozzi | Grp94 in complexes with IgG is a soluble diagnostic marker of gastrointestinal tumors and displays immune-stimulating activity on peripheral blood immune cells[END_REF] . GRP94 was also shown to be linked with chemoresistance. [START_REF] Zhang | Upregulation of GRP78 and GRP94 and its function in chemotherapy resistance to VP-16 in human lung cancer cell line SK-MES-1[END_REF][START_REF] Fu | Glucose regulated proteins in cancer progression, drug resistance and immunotherapy[END_REF] All these data provide rationale for the high interest in GRP94 as a therapeutic target for the development of anticancer therapies. However, the selective inhibition of GRP94 is highly complex due to the high conservation of the ATP-binding site. Currently, only a few selective GRP94 inhibitors have been reported, [START_REF] Patel | Structure-activity relationship in a purine-scaffold compound series with selectivity for the endoplasmic reticulum Hsp90 paralog Grp94[END_REF][START_REF] Duerfeldt | Development of a Grp94 inhibitor[END_REF] and none have yet reached clinical evaluation. Thus there is a great interest in identifying new chemical scaffolds as starting points for new inhibitors.

In this work we used an innovative in cell ABPP strategy never applied in an HSP90 context. Compared to the other chemical biology methods previously reported to study HSP90 binding properties that used co-immunoprecipitation [START_REF] Chavany | p185erbB2 binds to GRP94 in vivo. Dissociation of the p185erbB2/GRP94 heterocomplex by benzoquinone ansamycins precedes depletion of p185erbB2[END_REF] or on-beads immobilized affinity scaffold, [START_REF] Schulte | Interaction of radicicol with members of the heat shock protein 90 family of molecular chaperones[END_REF][START_REF] Taldone | Design, synthesis, and evaluation of small molecule Hsp90 probes[END_REF] the method reported here is carried out directly in live cells. Thereby, we identified compound 4 as a GRP94-selective inhibitor over HSP90α. For the GRP94 inhibitor PU-WS13, its selectivity is due to the occupation by the substituted phenyl ring of an allosteric pocket (FIG. 7 Site 2), which is not present in HSP90α/β. [START_REF] Patel | Paralog-selective Hsp90 inhibitors define tumor-specific regulation of HER2[END_REF] On the other hand, PU-H71, a pan-HSP90 inhibitor under conditions of equilibrium binding but kinetically selective for HSP90 residing in epichaperome networks, [START_REF] Rodina | The epichaperome is an integrated chaperome network that facilitates tumour survival[END_REF] binds to Site 1 present in both HSP90 α/β and GRP94. Our compound 4 bears an adenosine moiety (FIG. 7), shared by GRP94-selective inhibitor NECA, [START_REF] Huck | NECA derivatives exploit the paralog-specific properties of the Site 3 side pocket of Grp94, the ER Hsp90[END_REF] that binds to the ATP binding site. Additionally, NECA was also shown to interact with Site 3 of GRP94. [START_REF] Huck | NECA derivatives exploit the paralog-specific properties of the Site 3 side pocket of Grp94, the ER Hsp90[END_REF][START_REF] Soldano | Structure of the N-terminal domain of GRP94. Basis for ligand specificity and regulation[END_REF] From our results, we showed that the addition of a cytosine substituted with MOM (compound 1) or BOM (compound 2) group to the adenosine moiety results in a loss of activity. The bulky substituted cytosine might prevent from interacting within Site 3. However, the cytosine substitution by a large benzophenone-containing linker leads to active and selective GRP94 inhibitor. Thus, the affinity of compound 4 might be due, in addition to the presence of the adenosine moiety, to the flexible and large benzophenone-containing scaffold that could reach to the similar allosteric pocket as for PU-WS13 (Site 2). However, the reasons for the selectivity of 4 are still not clear and will require further investigation.

Therefore, in this study using an innovative in-cell ABPP strategy we identified the adenosinesubstituted cytosine analogues as an interesting starting point for further improvement. Crystallographic data could give highly valuable information to improve the potency of our compounds and afford potent and selective GRP94 inhibitors to be used potentially as therapeutic anticancer agents.

ACKNOWLEDGMENT

METHODS

Chemical Synthesis

All chemicals were purchased from Sigma-Aldrich or Alfa Aesar. PU-H71, PU-WS13 and GM-cy3B were synthesized and characterized as previously reported. [START_REF] Rodina | The epichaperome is an integrated chaperome network that facilitates tumour survival[END_REF][START_REF] Patel | Structure-activity relationship in a purine-scaffold compound series with selectivity for the endoplasmic reticulum Hsp90 paralog Grp94[END_REF][START_REF] Patel | Paralog-selective Hsp90 inhibitors define tumor-specific regulation of HER2[END_REF][START_REF] Moulick | Synthesis of a red-shifted fluorescence polarization probe for Hsp90[END_REF][START_REF] He | Identification of potent water soluble purine-scaffold inhibitors of the heat shock protein 90[END_REF] The NMR spectra were recorded on a Bruker Avance II spectrometer equipped with a 13 C cryoprobe at 500 MHz for 1 H and 125 MHz for 13 C; 2D experiments were performed using standard Bruker programs and atoms attribution was performed thanks to 2D correlations. Chemical shifts are given in ppm. Coupling constants J are measured in Hz. Splitting patterns are designed as follows: s, singlet; bs broad singlet; d, doublet; bd, broad doublet; t, triplet; brt, broad triplet; dd, doublet of a doublet; m, multiplet; ddd, doublet of a doublet of a doublet; q, quartet; quint, quintet, sext, sextet.

HRMS-ESI were obtained on a Bruker MicroTOF.

Column chromatography was carried out on a puriflash 430 apparatus (Interchim) equipped with 30 m porated silica column.

Semi preparative HPLC was performed on an apparatus equipped with a VWR International LaPrep pump P110, a VWR LaPrep P314 Dual l absorbance detector and EZChrom software. C18 reversedphase column (Waters x-bridge, RP-18, 25 x 250 mm, 5 m) were used for semi preparative HPLC with a binary gradient elution (solvent A: H 2 O/0.01% TEA and solvent B: CH 3 CN/0.01% TEA), a flow rate of 20 mL.min -1 and the chromatogram was monitored at 250 and 320 nm.

General procedure for synthesis of compounds 1, 2 and 3

Water (100 l) was added to a solution of 12 (102 mg; 0.20 mmol), 13 (126 mg; 0.22 mmol) or 14 (121 mg; 0.20 mmol) in TFA (1 mL). The reaction mixtures were stirred at room temperature for 1h.

The solvent was removed and the residues were co-evaporated three times with 1N ammonia in methanol under reduce pressure. The residues were purified by reversed phase HPLC using a linear gradient H 2 O/acetonitrile:100/020/80 with 0.2% of TEA to give the desired products.

1-(methoxymethyl)-N-((5'-deoxyadenosin-5'-yl)methyl)cytosine-5-carboxamide (1)

Compound 1 was obtained as a white amorphous solid (74 mg; 0.16 mmol; 80%).

1-(benzoxymethyl)-N-(5'-deoxyadenosin-5'-yl)methyl)cytosine-5-carboxamide (2)

Compound 2 was obtained as a white amorphous solid (96 mg; 0.18 mmol; 81%).

1-(2-aminoethyl)-N-(5'-deoxyadenosin-5'-yl)methyl)cytosine-5-carboxamide (3)

Compound 3 was obtained as a white amorphous solid (69 mg; 0.15 mmol; 75%).

Synthesis of chemical probe 4

To a solution of 4-((4-(4-(hex-5-ynamido)benzoyl)phenyl)amino)-4-oxobutanoic acid 16 (6.7 mg; 16 mol), HATU (8 mg; 20 mol) and DIPEA (7 l; 38 mol) in DMF (0.4 mL) was added 3 (6.3 mg; 4 mol). The mixture was stirred at room temperature for 16 hours. The residue was then directly purified by reversed phase HPLC using a linear gradient H 2 O/acetonitrile:100/020/80 with 0.01% of TEA to afford 4 as a amorphous white solid (8.3 mg; 9.8 mol; 72%).

N-(4-(4-(5-(Boc-amino)pentanamido)benzoyl)phenyl)hex-5-ynamide (5)

HATU (396.0 mg; 1.04 mmol) was solubilized in DMA (2 mL) at RT under argon. The carboxylic acid 17 (215.0 mg; 0.99 mmol) and DIPEA (0.19 mL; 1.39 mmol) was added to the solution. After 20 min of stirring at room temperature, the compound 15 (198.9 g; 0.65 mmol) was then added. The reaction mixture was stirred at room temperature for 16 h. The residue was diluted with ethyl acetate and washed with water and brine, and dried over sodium sulfate. The solvent was removed and the residue was purified by silica gel flash chromatography using a linear gradient of cyclohexane/ethyl acetate:0/10080/20 to afford the title compound 5 as an amorphous white solid (309.8 mg; 0.57 mmol; 88% yield).

Cell culture

KG-1, MOLM-13 and K-562 human leukemia cell lines, WM-266-4 human melanoma cancer cells and MCF-7 human breast cancer cells were obtained from ATCC (USA). Cells were grown in RPMI 1640 GlutaMAX™ (ThermoFisher Scientific) medium containing 10% FCS (Lonza) for K-562 and MCF-7 cells and 20% for KG-1 and MOLM-13 cells, WM-266-4 cell line was grown in EMEM containing 10% FCS at 37 °C and under 5% CO 2 .

In situ labeling of cancer cells for in-gel visualization

For probe labeling assays, suspension cells were counted and adherent cells were grown until approximately 90-80% confluent before treatment. They were first washed twice with PBS and resuspended in their medium without FCS for the incubation with probes. Probe was added at desired concentration and incubated for 1 h at 37 °C. Chemical probe 4 was used for measurement sample and chemical probe 5 was used as control experiments for proteomic analysis. DMSO (1% v/v) was added in control samples. Competitor (1 or 2) was added 30 min after the test compound to chase. Following treatment, cells were washed once with PBS and resuspended in fresh medium for the UV-irradiation step. After 1 h of exposition at 365 nm, cells were lysed in lysis buffer (RIPA buffer (Sigma-Aldrich) + cOmplete™, EDTA-free Protease Inhibitor Cocktail (PIC) (Roche Diagnostics)) on ice for 15 min followed by 3 min of sonication (30 s / 30 s on/off, medium power, Diagenode Bioruptor®). Protein concentrations were determined and proteome samples were diluted in PBS at a final concentration of 1 mg.mL -1 for the CuAAC ligation. The premix reagents (60 M TAMRA-biotin-azide, 1 mM CuSO 4 , 1 mM TCEP and 100 M TBTA, final concentrations) were added to the lysate. The samples were agitated for 1h at room temperature. The proteins were next precipitated by addition of methanol/chloroform/water (2/0.5/1) and pelleted by centrifugation at 15,000 × g for 5 min. After removal of supernatant, protein pellet was further washed in methanol and resuspended in PBS buffer containing 2% SDS and 10 mM DTT. Läemmli sample buffer was then added and the samples were heated for 10 min at 95 °C, separated by 1D SDS-PAGE and visualized using Typhoon 9410 (GE Healthcare).

In situ labeling of cancer cells for gel and MS analysis

In parallel to SDS-PAGE visualization, samples were enriched on avidin-coupled agarose beads (Pierce™ NeutrAvidin™ Agarose, ThermoFisher Scientific) (50 L, pre-washed three times in 0.2% SDS in PBS) by incubation with gentle shaking for 2 h at room temperature to bind and enrich biotinlabeled proteins. The supernatant was then removed and the beads were washed with 1% SDS in PBS (3 x 1 mL), 4 M urea in 50 mM ammonium bicarbonate (AMBIC) (2 x 1 mL) and 50 mM AMBIC (5 x 1 mL).

On-bead proteins were then resuspended in 50 L of 50 mM AMBIC and reduced with 10 mM dithiothreitol at 55 °C for 30 min. After on-bead reduction, samples were washed twice with 50 mM AMBIC and again resuspended in 50 L of 50 mM AMBIC for alkylation of cysteines by 10 mM iodoacetamide in the dark for 30 min. Beads were then washed twice with 50 mM AMBIC and resuspended in 50 l of 50 mM AMBIC for protein digestion with trypsin (1 g, Promega), overnight at 37 °C. Supernatant was kept in clean Eppendorf and beads were washed with 50 mM AMBIC followed by 0.1% TFA in H 2 O. Supernatants of each washing step were combined, evaporated to dryness and resuspended for desalting step before LC-MS/MS analysis.

Peptides were analyzed by nanoLC-MS/MS using an UltiMate 3000 RSLCnano system coupled to an Orbitrap Velos mass spectrometer (Thermo Fisher Scientific, Bremen, Germany). 5 l of each sample were loaded on a C-18 precolumn (300 m ID x 5 mm, Thermo Fisher) in water containing 5% acetonitrile and 0.05% TFA and at a flow rate of 20 L.min -1 . After 5 min of desalting, the precolumn was switched online with the analytical C-18 column (75 m ID x 50 cm, Reprosil C18) equilibrated in 95% solvent A (5% acetonitrile, 0.2% formic acid) and 5% solvent B (80% acetonitrile, 0.2% formic acid). Peptides were eluted using a 5 to 50% gradient of solvent B over 105 min at a flow rate of 300 nL.min -1 . The orbitrap Velos was operated in a data-dependent acquisition mode with the XCalibur software. Survey scan MS were acquired in the Orbitrap on the 350-1800 m/z range with the resolution set to a value of 60000. The 20 most intense ions per survey scan were selected for CID fragmentation. Dynamic exclusion was employed within 60s to prevent repetitive selection of the same peptide.

Raw mass spectrometry files were processed with the MaxQuant software (version 1.5.2.8) for database search with the Andromeda search engine and quantitative analysis. Data were searched against human entries of the Swissprot protein database. Carbamidomethylation of cysteines was set as a fixed modification whereas oxidation of methionine and protein N-terminal acetylation were set as variable modifications. Specificity of trypsin digestion was set for cleavage after K or R, and two missed trypsin cleavage sites were allowed. The precursor mass tolerance was set to 20 ppm for the first search and 4.5 ppm for the main Andromeda database search. The mass tolerances MS/MS mode was set to 0.5 Da. Andromeda results were validated by the target-decoy approach using a reverse database at both a peptide and a protein FDR of 1%. For label-free relative quantification of the samples, the "match between runs" option of MaxQuant was enabled with a time window of 0.7 min, to allow cross-assignment of MS features detected in the different runs.

Specifically labeled proteins were identified by comparison to the alkyne probe-treated samples with the controls. The "LFQ" metric from the MaxQuant "protein group.txt" output was used and ratio between alkyne probe and controls were calculated. According to different thresholds/filters, proteins were considered specific if ratios are > 2 or Log difference is > 1, Log10 p-value > 1.33, the sum of MS2 count of probe/control > 5 and then if there is a statistically significant difference (Student's ttest, p = 0.05).

FP competition assay under conditions of equilibrium binding

The GRP94 and HSP90α FP competition assays were performed on an Analyst GT instrument (Molecular Devices, Sunnyvale, CA) and carried out in black 96-well microplates (Corning, no. 3650) in a total volume of 100 L in each well as previously described [START_REF] Taldone | Experimental and structural testing module to analyze paralogue-specificity and affinity in the Hsp90 inhibitors series[END_REF][START_REF] Kim | Development of a fluorescence polarization assay for the molecular chaperone Hsp90[END_REF] . A stock of 10 M Cy3B-GM was prepared in DMSO and diluted with Felts buffer [20 mM HEPES (K) pH 7.3, 50 mM KCl, 2 mM DTT, 5 mM MgCl 2 , 20 mM Na 2 MoO 4 , and 0.01% NP40 with 0.1 mg.mL -1 BGG]. To each well was added the fluorescent dye labeled ligand (6 nM Cy3B-GM for GRP94 and HSP90α), recombinant protein (10 nM GRP94 or HSP90α) and the tested inhibitor (initial stock in DMSO) in a final volume of 100 L of Felts buffer. Compounds were added in duplicate wells. For each assay, background wells (buffer only), tracer controls (free, fluorescent dye labeled ligand only), and bound controls (fluorescent dye labeled ligand in the presence of protein) were included on each assay plate. The assay plate was incubated on a shaker at 4 °C for 24 h and the FP values (in mP) were measured. The fraction of fluorescent dye labeled ligand bound to GRP94 or HSP90α was correlated to the mP value and plotted against values of competitor concentrations. The inhibitor concentration at which 50% of bound fluorescent dye labeled ligand got displaced was obtained by fitting the data. For Cy3B-GM, an excitation filter at 530 nm and an emission filter at 580 nm were used with a dichroic mirror of 561 nm. All experimental data were analyzed using SoftMax Pro 6.3 and plotted using Prism 6.0 (Graphpad Software Inc., San Diego, CA) and binding affinity values are given as relative binding affinity values (EC 50 , concentration at which 50% of fluorescent ligand was competed off by compound). PU-H71 and PU-WS13 were included as controls.

Figure 1 .

 1 Figure 1. Structure of the compounds 1-3 with the adenosine motif (red) linked to the 5-position of the cytosine analogue (blue). Structure of the chemical probes 4 and 5 containing the probe reactive scaffold (green).

Scheme 1 .Scheme 2 .

 12 Scheme 1. Synthesis scheme of the adenosine-cytosine derivatives 1-3. a) MOMCl or BOMBr, Boc-aminoethyl bromide, K 2 CO 3 , DMF, RT, 18h; b) NaOH, MeOH/H 2 O, RT, 12h; c) 2',3'-O-isopropylidene-5'-deoxy-5'-aminomethyladenosine, HATU, DIPEA, DMF, RT, 2h; d) TFA, H 2 O, RT, 1h.

Figure 2 .

 2 Figure 2. (A) Representation of the general strategy for target identification by using a chemical probe. (B-C) TAMRA fluorescence (upper gels) and SYPRO Ruby stained total protein (bottom gels) profiles of MCF-7 cells treated with a concentration range of probe 4 (B) or with 10 M of 4 with and without UV irradiation (left) or after competition experiments with 100 M of competitors 1 and 2 (right) (C).

Figure 3 .

 3 Figure 3. TAMRA fluorescence (upper gels) and total protein staining with SYPRO Ruby stain (bottom gels) after affinity-based profiling in K-562, KG-1, MOLM-13 and WM-266-4 cells upon 1h treatment by 10 M of probe 4, control probe 5 or 1% DMSO in triplicate. Encouraged by these gel-based experiments, we next performed affinity-based pull-down experiments in order to identify the protein targets of the transition state analogue probe 4. The experiments were performed in three biological replicates in MCF-7, K-562, KG-1, MOLM-13 and WM-266-4 cell lines. The active chemical probe 4 was compared to the inactive Boc probe 5.

Figure 4 .

 4 Figure 4. Volcano plot of the proteomic data obtained following pull-down ABPP experiments with active chemical probe 4 and inactive probe 5 in KG-1 cells. The statistical significance expression level change (pvalue) is represented as a function of the protein ratio between control and treated samples. Orange dots represent the proteins with significantly over-represented in the treated sample. For the other cell lines 165, 112, 401 and 213 proteins were identified with 26, 6, 40 and 19 statistically over-represented in MCF-7, K-562, MOLM-13 and WM-266-4 cell lines, respectively (GRAPH SI-2 to 5 and TABLE SI-2 to 5)

Figure 5 .

 5 Figure 5. Significantly over-represented proteins with chemical probe 4. (A) Venn diagram showing the common and unique proteins statistically over-represented with the active probe 4 compared to the inactive probe 5. (B) Table of commonly enriched proteins represented by green highlight in different cell lines. (C) MS/MS counts and ratio values for GRP94 in KG-1, MCF-7, K-562, MOLM-13 and WM-266-4 cell lines. *Ratio values are reported as a mean of the three replicates.

Figure 6 .

 6 Figure 6. Fluorescence polarization competition assay for GRP94 (left) and HSP90α (right) performed under conditions of equilibrium binding. Binding properties of 4, 1 and 2 were assessed and PU-H71 and PU-WS13 were included as controls. Data are the mean value of two independent experiments run in triplicates (SD are shown as error bars).

Figure 7 .

 7 Figure 7. Structures of PU-H71, a pan-HSP90 inhibitor under conditions of equilibrium binding, PU-WS13 and NECA, GRP94-selective inhibitors over HSP90α and HSP90β and compounds 1, 2 and 4, new GRP94-selective inhibitors.

13 C

 13 NMR (125 MHz, DMSO-d 6 ) δ 165.7 (C c5 ), 164.4 (C c1 ), 156.5 (C a2 ), 154.7 (C c4 ), 153.1 (C a1 ), 149.8 (C a4 ), 149.7 (C a1 ), 140.3 (C c3 ), 119.6 (C a3 ), 97.8 (C c2 ), 88.1 (C a6 ), 81.8 (C a9 ), 73.8 (C a6 ), 73.5 (C a7 ), 52.5 (C c6 ), 40.5 (C c7 ), 36.3 (C a11 ), 33.5 (C a10 ). HRMS-ESI (m/z) calculated for C 18 H 25 N 10 O 5 [M+H] + : 461.2004; found: 461.2011.

13 C

 13 NMR (125 MHz, DMSO) δ 193.4 (C p11 ), 171.6 (C p19 ), 171.2 (C p6 , C p16 ), 165.2 (C c1 ), 164.1 (C c4 ), 156.07 (C c5 ), 154.1 (C a2 ), 152.7 (C a1 ), 149.4 (C a4 ), 149.0 (C c3 ), 143.0 (C p15 , C p7 ), 139.8 (C a5 ), 131.7 (C p10 and C p12 ), 130.9 (C p9 and C p13 ), 119.2 (C a3 ), 118.2 (C p8 and C p14 ), 97.6 (C c2 ), 87.7 (C a6 ), 83.9 (C p2 ), 81.3 (C a9 ), 73.4 (C a7 ), 73.1 (C a8 ), 71.8 (C p1 ), 49.2 (C a11 ), 37.8 (C c6 ), 35.8 (C c7 ), 35.2 (C p5 ), 33.1 (C a10 ), 31.6 (C p17 ), 30.0 (C p18 ), 23.8 (C p4 ), 17.3 (C p3 ). HRMS-ESI (m/z) calculated for C 41 H 45 N 12 O 9 [M+H] + : 849.3427; found: 849.3436.

13 C

 13 NMR (125 MHz, DMSO) δ 193.4 (C p11 ), 171.8 (C p6 ), 171.2 (C p16 ), 155.6 (C Boc ), 143.1 (Cp7), 143 (C p15 ), 131.7 (C p10 , C p12 ), 130.9 (C p13 , C p9 ), 118.2 (C p8 , C p14 ), 84 (C p2 ), 77.4 (C Boc ), 71.7 (C p1 ), 39.4 (C p20 ), 36.2 (C p17 ), 35.2 (C p5 ), 29.1 (C p19 ), 28.2 (C Boc ), 23.8 (C p4 ), 22.4 (Cp18), 17.3 (C p3 ). HRMS-ESI (m/z) calculated for C 29 H 35 N 3 O 5 Na [M+Na] + : 528.2469; found: 528.2471.

NMR (125 MHz, DMSO-d 6 ) δ 163

	1 H NMR (500 MHz, DMSO-d 6 ) δ 8.42 (s, 1H, H c3 ), 8.39-8.26 (m, 3H, 2H NH and H a5 ), 8.16 (s, 1H,
	H a1 ), 7.81 (brs, 1H, H NH ), 7.39-7.21 (m, 7H, H c9 , H c10 , H c11 , 2H NH ), 5.88 (d, J= 5.0 Hz, 1H, H a6 ), 5.49
	(d, J= 5.8 Hz, 1H, H OH ), 5.25-5.16 (m, 3H, H OH , H c6 ), 4.66 (ddd, J= 5.3, 10.9 Hz, 1H, H a7 ), 4.60 (s,
	2H, H c7 ), 4.14-4,08 (m, 1H, H a8 ), 3.94 (dt, J= 4.5, 9.1 Hz, 1H, H a9 ), 3.34-3.26 (m, 1H, H a11 ), 3.23-3.18
	(m, 1H, H a11 ), 2.01-1.82 (m, 2H, H a10 ).
	.6 (C c5 ), 160.3 (C c1 ), 152.1 (C a4 ), 150.3 (C c2 ), 149.0 (C a1 ),
	148.9 (Ca4), 147.3 (C c3 ), 142.5 (C a5 ), 137.6 (C c8 ), 128.7 (C c10 ), 128.3 (C c11 ), 128.2 (C c9 ), 119.4 (C a3 ),
	98.7 (C c2 ), 88.4 (C a6 ), 82.2 (C a9 ), 78.6 (C c6 ), 73.9 (C a7 ), 73.8 (C a8 ), 71.4 (C c7 ), 55.5 (C c7 ), 36.5 (C a11 ),
	33.2 (C a10 ).
	HRMS-ESI (m/z) calculated for C 24 H 28 N 9 O 7 [M+H] + : 538.2757; found: 538.2161.

13 C

1 H NMR (500 MHz, DMSO-d 6 ) δ

  8.35 (s, 1H, H c3 ), 8.28 (s, 1H, H a5 ), 8.24 (t, J= 5.1 Hz, 1H, H NH ), 8.18-8.06 (m, 3H, H a1 and 2H NH ), 7.57 (d, J= 23.6 Hz, 1H, H NH ), 7.30 (s, 2H, H NH ), 5.87 (d, J= 4.9 Hz, 1H, H a6 ), 5,65-5,04 (m, 2H, H NH ), 4.66 (t, J= 5.2 Hz, 1H, H a7 ), 4.11 (t, J= 5.0 Hz, 1H, H a6 ), 3.94 (tt, J= 9.0, 4.3 Hz, 1H, H a9 ), 3.68 (t, J= 6.2 Hz, 2H, H c6 ), 3.24-3.14 (m, 2H, H, H a11 ), 2.88-2.70 (m, 2H, H c7 ), 2.03-1.79 (m, 2H, H a10 ),

1 H NMR (500 MHz, DMSO) δ 10

  .33 (s, 1H, H NH ), 10.30 (s, 1H, H NH ), 8.32 (s, 1H, H a5 ), 8.28 (s, 1H, J= 7.0 Hz, 2H, H p17 ), 2.48 (t, J= 7.4 Hz, 2H, H p5 ), 2.41 (t, J= 7.1 Hz, 2H, H p18 ), 2.24 (dt, J= 2.8, 7.3 Hz, 2H, H p3 ), 1.96-1.81 (m, 2H, H a10 ), 1.78 (quint, J= 7.4Hz, 2H, H p4 ).

	H c3 ), 8.24 (brt, 1H, H NH ), 8.14 (s, 1H, H a1 ), 8.08 (brt, 1H, H NH ), 7.77-7.71 (m, 4H, H p9 , H p13 ), 7.71-7.66
	(m, 4H, H p8 , H p14 ), 7.28 (brs, 2H, H NH2 ), 5.86 (d, J= 5.1 Hz, 1H, H a6 ), 5.51-5.46 (m, 1H, H OH ), 5.24-
	5.18 (m, 1H, H OH ), 4.64 (t, J= 4.9 Hz, 1H, H a7 ), 4.08 (t, J= 5.2 Hz, 1H, H a8 ), 3.98-3.91 (m, 1H, Ha9),
	3.72 (t, J= 5.9 Hz, 2H, H a11 ), 3.32-3.26 (m, 3H, H c6 and H c7 ), 3.21-3.12 (m, 1H, H c7 ), 2.83 (t, J= 2.7
	Hz, 1H, H p1 ), 2.61 (t,

1 H NMR (500 MHz, DMSO) δ 10

  .31 (s, 1H, H NH ), 10.25 (s, 1H, H NH ), 7.78-7.67 (m, 8H, H p8 , Hp9, H p13 and H p14 ), 6.82 (t, J= 5.5 Hz, 1H, H NH ), 2.93 (q, J= 6.5 Hz, 2H, H p20 ), 2.83 (t, J= 2.7 Hz, 1H, H p1 ), 2.48 (t, J= 7.7 Hz, 2H, H p5 ), 2.35 (t, J= 7.5 Hz, 2H, H p17 ), 2.24 (dt, J= 2.5, 7.0 Hz, 2H, H p3 ), 1.78 (quint, J= 7.2 Hz, 2H, H p4 ), 1.58 (quint, J= 7.7 Hz, 2H, H p18 ), 1.41 (quint, J= 7.2 Hz, 2H, H p19 ), 1.37 (s, 9H, H Boc ).

SUPPORTING INFORMATION AVAILABLE

Synthesis and characterization of compounds 6-17. [START_REF] Halby | Rational design of bisubstrate-type analogs as inhibitors of DNA methyltransferases in cancer cells[END_REF] H and [START_REF] Kishinevsky | HSP90-incorporating chaperome networks as biosensor for disease-related pathways in patient-specific midbrain dopamine neurons[END_REF] C NMR spectra of compounds 1-5. SI-1 to SI-5) and volcano plot (Graph SI-1 to SI-5). This material is available free of charge via the Internet.

Inhibition percentages of various DNMT, KHMTs and PRMTs for compounds 1-4. Table of proteomic analysis result tables (Table