Zvi Lotker

Boaz Patt-Shamir

Dror Rawitz
email: rawitz@cri.haifa.ac.il

RENT, LEASE OR BUY: RANDOMIZED ALGORITHMS FOR MULTISLOPE SKI RENTAL

Keywords: competitive analysis, ski rental, randomized algorithms

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost ("buying price"), and cost proportional to the duration of the usage ("rental rate"). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an e-competitive randomized strategy for any (non-additive) instance.

Introduction

Arguably, the "rent or buy" dilemma is the fundamental problem in online algorithms: intuitively, there is an ongoing game which may end at any moment, and the question is to commit or not to commit. Choosing to commit (the 'buy' option) implies paying large cost immediately, but low overall cost if the game lasts for a long time. Choosing not to commit (the 'rent' option) means high spending rate, but lower overall cost if the game ends quickly. This problem was first abstracted in the "Ski Rental" formulation [START_REF] Karlin | Competitive snoopy caching[END_REF] as follows.

In the buy option, a one-time cost is incurred, and thereafter usage is free of charge. In the rent option, the cost is proportional to usage time, and there is no one-time cost. The deterministic solution is straightforward (with competitive factor 2). In the randomized model, the algorithm chooses a random time to switch from the rent to the buy option (the adversary is assumed to know the algorithm but not the actual outcomes of random experiments). As is well known, the best possible online strategy for classical ski rental has competitive ratio of e e-1 ≈ 1.582. In many realistic cases, there may be some intermediate options between the extreme alternatives of pure buy and pure rent: in general, it may be possible to pay only a part of the buying cost and then pay only partial rent. The general problem, called here the Multislope Ski Rental problem, can be described as follows. There are several states (or slopes), where each state i is characterized by two numbers: a buying cost b i and a rental rate r i (see Fig. 1). Without loss of generality, we may assume that for all i, b i < b i+1 and r i > r i+1 , namely that after ordering the states in increasing buying costs, the rental rates are decreasing. The basic semantics of the multislope problem is natural: to hold the resource under state i for t time units, the user is charged b i + r i t cost units. An adversary gets to choose how long the game will last, and the task is to minimize total cost until the game is over.

The Multislope Ski Rental problem introduces entirely new difficulties when compared to the classical Ski Rental problem. Intuitively, whereas the only question in the classical version is when to buy, in the multislope version we need also to answer the question of what to buy. Another way to see the difficulty is that the number of potential transitions from one slope to another in a strategy is one less than the number of slopes, and finding a single point of transition is qualitatively easier than finding more than one such point.

In addition, the possibility of multiple transitions forces us to define the relation between multiple "buys." Following [START_REF] Augustine | Optimal power-down strategies[END_REF], we distinguish between two natural cases. In the additive case, buying costs are cumulative, namely to move from state i to state j we only need to pay the difference in buying prices b j -b i . In the non-additive case, there is an arbitrarily defined transition cost b ij for each pair of states i and j. Our results. In this paper we analyze randomized strategies for Multislope Ski Rental. (We use the term strategy to refer to the procedure that makes online decisions, and the term algorithm to refer to the procedure that computes strategies.) Our main focus is the additive case, and our main result is an efficient algorithm that computes the best possible randomized online strategy for any given instance of additive Multislope Ski Rental problem. We first give a simpler algorithm which decomposes a (k + 1)-slope instance into k two-slope instances, whose competitive factor is e e-1 . For the non-additive model, we give a simple e-competitive randomized strategy. Related Work. Variants of ski rental are implicit in many online problems. The classical (two-slope) ski rental problem, where the buying cost of the first slope and the rental rate of the second slope are 0, was introduced in [START_REF] Karlin | Competitive snoopy caching[END_REF], with optimal strategies achieving competitive factors of 2 (deterministic) and e e-1 (randomized). Karlin et al. [START_REF] Karlin | Dynamic TCP acknowledgment and other stories about e/(e -1)[END_REF] apply the randomized strategy to TCP acknowledgment mechanism and other problems. The classical ski rental is sometimes called the leasing problem [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF].

Azar et al. [START_REF] Azar | On capital investment[END_REF] consider a problem that can be viewed as non-additive multislope ski rental where slopes become available over time, and obtain an online strategy whose competitive ratio is 4 + 2 √ 2 ≈ 6.83. Bejerano et al. [START_REF] Bejerano | Dynamic session management for static and mobile users: a competitive on-line algorithmic approach[END_REF], motivated by rerouting in ATM networks, study the non-additive multislope problem. They give a deterministic 4-competitive strategy, and show that the factor of 4 holds assuming only that the slopes are concave, i.e., when the rent in a slope may decrease with time. Damaschke [START_REF] Damaschke | Nearly optimal strategies for special cases of on-line capital investment[END_REF] considers a static version of the problem from [START_REF] Azar | On capital investment[END_REF], namely non-additive multislope ski rental problem where each slope is bought "from scratch."1 For deterministic strategies, [START_REF] Damaschke | Nearly optimal strategies for special cases of on-line capital investment[END_REF] gives an upper bound of 4 and a lower bound of 5+ √ 5 2 ≈ 3.618; [START_REF] Damaschke | Nearly optimal strategies for special cases of on-line capital investment[END_REF] also presents a randomized strategy whose competitive factor is 2/ ln 2 = 2.88. As far as we know, Damaschke's strategy is the only randomized strategy for multislope ski rental to appear in the literature.

Irani et al. [START_REF] Irani | Competitive analysis of dynamic power management strategies for systems with multiple power savings states[END_REF] present a deterministic 2-competitive strategy for the additive model that generalizes the strategy for the two slopes case. They motivate their work by energy saving: each slope corresponds to some partial "sleep" mode of the system. Augustine et al. [START_REF] Augustine | Optimal power-down strategies[END_REF] present a dynamic program that computes the best deterministic strategy for non-additive multislope instances. The case where the length of the game is a stochastic variable with known distribution is also considered in both [START_REF] Irani | Competitive analysis of dynamic power management strategies for systems with multiple power savings states[END_REF][START_REF] Augustine | Optimal power-down strategies[END_REF].

Meyerson [START_REF] Meyerson | The parking permit problem[END_REF] defines the seemingly related "parking permit" problem, where there are k types of permits of different costs, such that each permit allows usage for some duration of time. Meyerson's results indicate that the problems are not very closely related, at least from the competitive analysis point of view: It is shown in [START_REF] Meyerson | The parking permit problem[END_REF] that the competitive ratio of the parking permit problem is Θ(k) and Θ(log k) for deterministic and randomized strategies, respectively. Organization. The remainder of this paper is organized as follows. In Section 2 we define the basic additive model and make a few preliminary observations. In Section 3 we give a simple algorithm to solve the multislope problem, and in Section 4 we present our main result: an optimal online algorithm. An e-competitive algorithm for the non-additive case is presented in Section 5.

Problem Statement and Preliminary Observations

In this section we formalize the additive version of the multislope ski rental problem. A k-ski rental instance is defined by a set of k + 1 states, and for each state i there is a buying cost b i and a renting cost r i . A state can be represented by a line: the ith state corresponds to the line y = b i + r i x. Fig. 1 gives a geometrical interpretation of a multislope ski rental instance with five states. We use the terms "state" and "slope" interchangeably.

The requirement of the problem is to specify, for all times t, which slope is chosen at time t. We assume that state transitions can be only forward, and that states cannot be skipped, i.e., the only transitions allowed are of the type i → i + 1. We stress that this assumption holds without loss of generality in the additive model, where a transition from state i → j for j > i + 1 is equivalent to a sequence of transitions i → i + 1 → . . . → j (cf. Section 5). It follows that a deterministic strategy for the additive multislope ski rental problem is a monotone non-decreasing sequence (t 1 , . . . , t k ) where

t i ∈ [0, ∞) corresponds to the transition i -1 → i.
A randomized strategy can be described using a probability distribution over the family of deterministic strategies. However, in this paper we use another way to describe randomized strategies. We specify, for all times t, a probability distribution over the set of k + 1 slopes. The intuition is that this distribution determines the actual cost paid by any online strategy. Formally, a randomized profile (or simply a profile) is specified by a vector p(t) = (p 0 (t), . . . , p k (t)) of k + 1 functions, where p i (t) is the probability to be in state i at time t. The correctness requirement of a profile is k i=0 p i (t) = 1 for all t ≥ 0. Clearly, any strategy is related to some profile. In the sequel we consider a specific type of profiles for which a randomized strategy can be easily obtained.

The performance of a profile is defined by its total accrued cost, which consists of two parts as follows. Given a randomized profile p, the expected rental cost of p at time t is

R p (t) def = i p i (t) • r i ,
and the expected total rental cost up to time t is

t z=0 R p (z)dz .
The second part of the cost is the buying cost. In this case it is easier to define the cumulative buying cost. Specifically, the expected total buying cost up to time t is

B p (t) def = i p i (t) • b i .
The expected total cost for p up to time t is

X p (t) def = B p (t) + t z=0 R p (z)dz .
The goal of the algorithm is to minimize total cost up to time t for any given t ≥ 0, with respect to the best possible. Intuitively, we think of a game that may end at any time. For any possible ending time, we compare the total cost of the algorithm with the best possible (offline) cost. To this end, consider the optimal solution of a given instance. If the games ends at time t, the optimal solution is to select the slope with the least cost at time t (the thick line in Fig. 1 denotes the optimal cost for any given t). More formally, the optimal offline cost at time t is

opt(t) = min i (b i + r i • t) .
For i > 0, denote by s i the time t instance where b i-1 + r i-1 • t = b i + r i • t, and define s 0 = 0. It follows that the optimal slope for a game ending at time t is the slope i for which t ∈ [s i , s i+1 ] (if t = s i for some i then both slopes i -1 and i are optimal). Finally, let us rule out a few trivial cases. First, note that if there are two slopes such that b i ≤ b j and r i ≤ r j then the cost incurred by slope j is never less than the cost incurred slope i, and we may therefore just ignore slope j from the instance. Consequently, we will assume henceforth, without loss of generality, that the states are ordered such that r i-1 > r i and b i-1 < b i for 1 ≤ i ≤ k.

Second, using similar reasoning, note that we may consider only strategies that are monotone over time with respect to majorization [START_REF] Marshall | Inequalities: Theory of Majorization and Its Applications[END_REF], i.e., strategies such that for any two times t ≤ t ′ we have

j i=0 p i (t) ≥ j i=0 p i (t ′ ) .
(2.1)

Intuitively, Eq. (2.1) means that there is no point is "rolling back" purchases: if at a given time we have a certain composition of the slopes, then at any later time the composition of slopes may only improve. Note that Eq. (2.1) implies that B p is monotone increasing and R p is monotone decreasing, i.e., over time, the strategy invests non-negative amounts in buying, resulting in decreased rental rates.

An e e-1 -Competitive Algorithm

In this section we describe how to solve the multislope problem by reducing it to the classical two-slope version, resulting in a randomized strategy whose competitive factor is e e-1 . This result serves as a warm-up and it also gives us a concrete upper bound on the competitiveness of the algorithm presented in Section 4. The case of r k = 0. Suppose we are given an instance (b, r) with k + 1 slopes, where r k = 0. We define the following k instances of the classical two-slopes ski rental problem: in instance i for i ∈ {1, . . . , k}, we set instance i: b i 0 = 0 and

r i 0 = r i-1 -r i ; b i 1 = b i -b i-1 and r i 1 = 0 . (3.1)
Observe that b i 1 = r i 0 • s i , i.e., the two slopes of the ith instance intersect exactly at s i , their intersection point at the original multislope instance. Now, let opt(t) denote the optimal offline solution to the original multislope instance, and let opt i (t) denote the optimal solution of the ith instance at time t, i.e., opt i (t) = min{b i 1 , r i 0 • t}. We have the following.

Lemma 3.1. opt(t) = k i=1 opt i (t). Proof. Consider a time t and let i(t) be the optimal multislope state at time t. Then,

k i=1 opt i (t) = i:s i ≤t b i 1 + i:s i >t r i 0 • t = i:s i ≤t (b i -b i-1 ) + i:s i >t (r i-1 -r i ) • t = b i(t) + r i(t) • t = opt(t) .
Given the decomposition (3.1), it is easy to obtain a strategy for any multislope instance by combining strategies for k classical instances. Specifically, what we do is as follows. Let p i be the e e-1 -competitive profile for the ith (two slope) instance (see [START_REF] Karlin | Competitive snoopy caching[END_REF]). We define a profile p for the multislope instance as follows: pi (t) = p i 1 (t) -p i+1 1 (t) for i ∈ {1, . . . , k -1}, p0 (t) = p 1 0 (t), and pk (t) = p k 1 (t). We first prove that the profile is well defined.

Lemma 3.2. (1) p i 1 (t) ≤ p i-1 1 (t) for every i ∈ {1, . . . , k} and time t. (2) k i=0 pi (t) = 1 .

Proof. By the algorithm for classical ski rental, we have that the strategy for the i instance is p i 1 (t) = (e t•r i 0 /b i 1 -1)/(e -1). Claim (1) of the lemma now follows from that fact that b

i 1 /r i 0 = s i > s i-1 = b i-1 1 /r i-1 0
for every i ∈ {1, . . . , k}. Claim (2) follows from the telescopic sum

k i=0 pi (t) = p 1 0 (t) + k-1 i=1 (p i 1 (t) -p i+1 1 (t)) + p k 1 (t) = p 1 0 (t) + p 1 1 (t) = 1 .
Next, we show how to convert the profile p into a strategy. Note that the strategy uses a single random experiment, since arbitrary dependence between the different p i s are allowed.

Lemma 3.3. Given p one can obtain an online strategy whose profile is p.

Proof. Define Pi (t) def = j≥i pj (t) and let U be a random variable that is chosen uniformly from [0, 1]. The strategy is as follows: we move from state i to state i + 1 when U = Pi (t) for every state i. Namely, the ith transition time t i is the time t such that U = Pi (t).

Thus we obtain the following: Theorem 3.4. The expected cost of the strategy defined by p is at most e e-1 times the optimal offline cost.

Proof. We first show that by linearity, the expected cost to the combined strategy is the sum of the costs to the two-slope strategies, i.e., that X p(t) = k i=1 X p i (t). For example, the buying cost is

B p(t) = k i=0 pi (t) • b i = k-1 i=0 (p i 1 (t) -p i+1 1 (t)) • b i + p k 1 (t) • b k = k i=1 p i 1 (t) • (b i -b i-1 ) = k i=1 B p i (t) .
Similarly, R p(t) = k i=1 R p i (t) by linearity, and therefore,

X p(t) = B p(t) + t z=0 R p(z)dz = k i=1 B p i (t) + t z=0 k i=1 R p i (z) dz = k i=1 X p i (t) .
Finally, by Lemma 3.1 and the fact that the strategies p 1 , . . . , p k are e e-1 -competitive we conclude that

X p(t) = k i=1 X p i (t) ≤ k i=1 e e -1 • opt i (t) = e e -1 • opt(t)
which means that p is e e-1 -competitive. The case of r k > 0. We note that if the smallest rental rate r k is positive, then the competitive ratio is strictly less that e e-1 : this can be seen by considering a new instance where r k is subtracted from all rental rates, i.e., b ′ i = b i and r ′ i = r i -r k for all 0 ≤ i ≤ k. Suppose p is e e-1 -competitive with respect to (r ′ , k ′ ) (note that r ′ k = 0). Then the competitive ratio of p at time t w.r.t. the original instance is:

c(t) = X p (t) opt(t) = X ′ p (t) + r k • t opt ′ (t) + r k • t ≤ e e-1 • opt ′ (t) + r k • t opt ′ (t) + r k • t = e e -1 - 1 e -1 • 1 opt ′ (t) r k •t + 1 d dt opt ′ (t) = r i -r k for t ∈ [s i-1 , s i ).
Hence, the ratio opt ′ (t) r k •t is monotone decreasing, and thus c(t) is monotone decreasing as well. It follows that

c ≤ e e -1 - 1 e -1 • 1 r 0 -r k r k + 1 = e -r k /r 0 e -1
Observe that c = e e-1 when r k = 0, and that c = 1 when r k = r 0 (i.e., when k = 0).

An Optimal Online Algorithm

In this section we develop an optimal online strategy for any given additive multislope ski rental instance. We reduce the set of all possible strategies to a subset of much simpler strategies, which on one hand contains an optimal strategy, and on the other hand is easier to analyze, and in particular, allows us to effectively find such an optimal strategy.

Consider an arbitrary profile. (Recall that we assume w.l.o.g. that no slope is completely dominated by another.) As a first simplification, we confine ourselves to profiles where each p i has only finitely many discontinuities. This allows us to avoid measure-theoretic pathologies without ruling out any reasonable solution within the Church-Turing computational model. It can be shown that we may consider only continuous profiles (details omitted).

So let such a profile p = (p 0 , . . . , p k ) be given. We show that it can be transformed into a profile of a certain structure without increasing the competitive factor. Our chain of transformations is as follows. First, we show that it suffices to consider only simple profiles we call "prudent." Prudent strategies buy slopes in order, one by one, without skipping and without buying more than one slope at a time. We then define the concept of "tight" profiles, which are prudent profiles that spend money at a fixed rate relative to the optimal offline strategy. We prove that there exists a tight optimal profile. Furthermore, the best tight profile can be effectively computed: Given a constant c, we show how to check whether there exists a tight c-competitive strategy, and this way, using binary search on c, we can find the best tight strategy. Finally, we explain how to construct that profile and a corresponding strategy.

Prudent and Tight Profiles

Our main simplification step is to show that it is sufficient to consider only profiles that buy slopes consecutively one by one. Formally, prudent profiles are defined as follows.

Definition 4.1 (active slopes, prudent profiles). A slope i is active at time t if p i (t) > 0. A profile is called prudent if at all times there is either one or two consecutive active slopes.

At any given time t, at least one slope is active because i p i (t) = 1 by the problem definition. Considering Eq. (2.1) as well, we see that a continuous prudent profile progresses from one slope to next without skipping any slope in between: once slope i is fully "paid for" (i.e., p i (t) = 1), the algorithm will start buying slope i + 1.

We now prove that the set of continuous prudent profiles contains an optimal profile. Intuitively, the idea is that a non-prudent profile must have two non-consecutive slopes with positive probability at some time. In this case we can "shift" some probability toward a middle slope and only improve the overall cost. Theorem 4.2. If there exists a continuous c-competitive profile p for some c ≥ 1, then there exists a prudent c-competitive profile p.

Proof. Let p = (p 0 , . . . , p k ) be a profile and suppose that all the p i s are continuous. It follows that B p is also continuous. Define best(t) = max {i : b i ≤ B p (t)} and next(t) = min {i : b i ≥ B p (t)}. In words, best(t) is the most expensive slope that is fully within the buying budget of p at time t, and next(t) is the most expensive slope that is at least partially within the buying budget of p at time t. Obviously, best(t) ≤ next(t) ≤ best(t) + 1 for all t. Now, we define p as follows:

pi (t) =              b next -B p (t) b next -b best i = best(t) and best(t) = next(t), Bp(t)-b best bnext-b best i = next(t) and best(t) = next(t), 1 i = best(t) = next(t), 0 otherwise.
It is not hard to verify that i p i (t) = 1 for every time t. Furthermore, observe that p is prudent, because B p is continuous. It remains to show that p is c-competitive. We do so by proving that B p(t) = B p (t) and R p(t) ≤ R p (t) for all t. First, directly from definitions we have

B p(t) = p best(t) (t) • b best(t) + p next(t) (t) • b next(t) = b next(t) -B p (t) b next(t) -b best(t) • b best(t) + B p (t) -b best(t) b next(t) -b best(t) • b next(t) = B p (t) .
Consider now rental payments. To prove that R p(t) ≤ R p (t) for every time t we construct inductively a sequence of probability distributions p = p 0 , . . . , p ℓ = p. The first distribution p 0 is defined to be p. Suppose now that p j is not prudent. Distribution p j+1 is obtained from p j as follows. For any t such that there are two non-consecutive slopes with positive probability, let i 1 (t), i 2 (t), i 3 (t) be any three slopes such that i 1 (t) = argmin{i : p j i (t) > 0}, i 3 (t) = argmax{i : p j i (t) > 0}, and i 1 (t) < i 2 (t) < i 3 (t) (such i 2 (t) exists because p j is not prudent). Define

p j+1 i (t) =              p j i (t) -∆ j (t) b i 2 (t) -b i 1 (t) i = i 1 (t), p j i (t) + ∆ j (t) b i 2 (t) -b i 1 (t) + ∆ j (t) b i 3 (t) -b i 2 (t) i = i 2 (t), p j i (t) -∆ j (t) b i 3 (t) -b i 2 (t) i = i 3 (t), p j i (t) i ∈ {i 1 (t), i 2 (t), i 3 (t)}
where ∆ j (t) > 0 is maximized so that p j+1 i (t) ≥ 0 for all i. Intuitively, we shift a maximal amount of probability mass from slopes i 1 (t) and i 3 (t) to the middle slope i 2 (t). The fact that ∆ j (t) is maximized means that we have either that p j+1 i 1 (t) = 0, or p j+1 i 3 (t) = 0, or both. In any case, we may already conclude that ℓ < k. Also note that by construction, for all t we have B p j+1 (t

) = i p j+1 i (t) • b i = i p j i (t) • b i = B p j (t).
Hence, p ℓ = p. As to the rental cost, fix a time t, and consider now the rent paid by p j and p j+1 :

R p j (t) -R p j+1 (t) = = r i 1 (t) ∆ j (t) b i 2 (t) -b i 1 (t) -r i 2 (t) ∆ j (t) b i 2 (t) -b i 1 (t) ∆ j (t) b i 3 (t) -b i 2 (t) + r i 3 (t) ∆ j (t) b i 3 (t) -b i 2 (t) = ∆ j (t) • r i 1 (t) -r i 2 (t) b i 2 (t) -b i 1 (t) - r i 2 (t) -r i 3 (t) b i 3 (t) -b i 2 (t) > 0
where the last inequality follows from the fact that if i < j, then b j -b i r i -r j is the x coordinate of the intersection point between the slopes i and j.

Our next step is to consider profiles that invest in buying as much as possible under some spending rate cap. Our approach is motivated by the following intuitive observation. Observation 4.3. Let p 1 and p 2 be two randomized prudent profiles. If B p 1 (t) ≥ B p 2 (t) for every t, then R p 1 (t) ≤ R p 2 (t) for every t.

In other words, investing available funds in buying as soon as possible results in lower rent, and therefore in more available funds. Hence, we define a class of profiles which spend money as soon as possible in buying, as long as there is a better slope to buy, namely as long as p k (t) < 1.

Definition 4.4. Let c ≥ 1. A prudent c-competitive profile p is called tight if X p (t) = c • opt(t) for all t with p k (t) < 1.
Clearly, if the last slope is flat, i.e., r k = 0, then it must be the case that p k (s k ) = 1 for any profile with finite competitive factor: otherwise, the cost to the profile will grow without bound while the optimal cost remains constant. However, it is important to note that if r k > 0, there may exist an optimal profile p that never buys the last slope, but still its expected spending rate as t tends to infinity is c • r k .

It is easy to see that a tight profile can achieve any achievable competitive factor.

Lemma 4.5. If there exists a c-competitive prudent profile p for some c ≥ 1, then there exists a c-competitive tight profile p.

Proof. Let p be the prudent profile satisfying X p(t) = c • opt(t) for all t for which pk (t) < 1. We need to show that p is feasible. Since by definition, p buys with any amount left, it suffices to show that for all t, the rent paid by p is at most c • d dt opt(t). Indeed, R p(t) ≤ R p (t) for every t due to Observation 4.3, and since p is c-competitive it follows that R p (t) ≤ c • d dt opt(t) and we are done.

Constructing Optimal Online Strategies

We now use the results above to construct an algorithm that produces the best possible online strategy for the multislope problem. The idea is to guess a competitive factor c, and then try to construct a c-competitive tight profile. Given a way to test for success, we can apply binary search to find the optimal competitive ratio c to any desired precision.

The main questions are how to test whether a given c is feasible, and how to construct the profiles. We answer these questions together: given c, we construct a tight c-competitive profile until either we fail (because c was too small) or until we can guarantee success. In the remainder of this section we describe how to construct a tight profile p for a given competitive factor c.

We begin with analyzing the way a tight profile may spend money. Consider the situation at some time t such that p k (t) < 1. Let j be the maximum index such that s j ≤ t. Then d dt opt(t) = r j . Therefore, the spending rate of a tight profile at time t must be c • r j . If j < k, the tight profile may spend at rate c • r j until time s j+1 (or until p k (t) = 1), and if Algorithm 1 -Feasible(c, M): true if the k-ski instance M = (b, r) admits competitive factor c

1: Let s i = bi-bi-1 ri-1-ri for each 1 ≤ i ≤ k 2: Boundary Condition ← "p 1 (0) = 0" 3: j ← 0; i ← 1 4: loop 5: Define p i (t) = c•rj-ri-1 ri-ri-1 + Γ • exp( ri-1-ri bi-bi-1 • t) 6:
Try to solve for Γ using Boundary Condition if i > k or j ≥ k then return true ⊲ we're done 18: end loop

An e-Competitive Strategy for the Non-Additive Case

In this section we consider the non-additive multislope ski rental problem. We present a simple randomized strategy which improves the best known competitive ratio from 2/ ln 2 = 2.88 to e. Our technique is a simple application of randomized repeated doubling (see, e.g., [START_REF]Search Games[END_REF]), used extensively in competitive analysis of online algorithms. For example, deterministic repeated doubling appears in [START_REF] Aspnes | On-line routing of virtual circuits with applications to load balancing and machine scheduling[END_REF], and a randomized version appears in [START_REF] Motwani | Non-clairvoyant scheduling[END_REF].

Before presenting the strategy let us consider the details of the non-additive model. Augustine at el. [START_REF] Augustine | Optimal power-down strategies[END_REF] define a general non-additive model in which a transition cost b ij is associated with every two states i and j, and show that one may assume w.l.o.g. that b ij = 0 if i > j and that b ij ≤ b j for every i < j. Observe that we may further assume that b ij = b j for every i and j, since the optimal (offline) strategy remains the unchanged. It follows that the strategies from [START_REF] Azar | On capital investment[END_REF][START_REF] Bejerano | Dynamic session management for static and mobile users: a competitive on-line algorithmic approach[END_REF][START_REF] Damaschke | Nearly optimal strategies for special cases of on-line capital investment[END_REF] that were designed for the case of buying slopes "from scratch" also work for the general non-additive case.

We propose using the following iterative online strategy, which is similar to the one in [START_REF] Damaschke | Nearly optimal strategies for special cases of on-line capital investment[END_REF], except for the choice of the "doubling factor." Specifically, the jth iteration is associated with a bound B j on opt(τ ), where τ denotes the termination time of the game. We define B 1 def = opt(s 1 )/α X , where α > 1 and X is a chosen at random uniformly in [0, 1). We also define B j+1 = α • B j . Let τ j = opt -1 (B j ) and let i j be the optimal offline state at time τ j . In case there are two such states, i.e., τ j = s i for some i, we define i j = i -1. It follows that i 1 = 0. In the beginning of the jth iteration the online strategy buys i j and stays in i j until the this iteration ends. The jth iteration ends at time τ j . Observe that the first iteration starts with B 1 = opt(s 1 ), namely we use slope 0 until s 1 .

Theorem 5.1. The expected cost of the strategy described above is at most e times the optimum.

Proof. Observe that the first iteration starts with B 1 = opt(s 1 ), namely we use slope 0 until s 1 , and hence, if the game ends during the first iteration, i.e., before s 1 /α X , then the online strategy is optimal. Consider now the case where the game ends at time τ ≥ s 1 /α X , and suppose that τ ∈ [τ ℓ , τ ℓ+1 ) for ℓ > 1. In this case, the expected cost of the online strategy is bounded by

E   ℓ j=1 opt(τ j ) + opt(τ )   ≤ E   ℓ+1 j=1 opt(τ j )   ≤ E α α -1 • opt(τ ℓ+1 ) = E α 2-X α -1 • opt(τ ) = α α -1 • 1 x=0 α x dx • opt(τ ) = α ln α • opt(τ )
By choosing α = e the competitive ratio is α ln α = e as required.

4 Figure 1 :

 41 Figure 1: A multislope ski rental instance with 5 slopes: The thick line indicates the optimal cost as a function of the game duration time.

It can be shown that strategies that work for this case also work for the general non-additive case (seeSection 5).

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Acknowledgment

We thank Seffy Naor and Niv Buchbinder for stimulating discussions.

The second author was supported in part by the Israel Science Foundation (grant 664/05) and by Israel Ministry of Science and Technology Foundation.

c Z. Lotker, B. Patt-Shamir, and D. Rawitz

CC

j = k the tight profile may continue spending at this rate forever. Hence, for t ∈ (s j , s j+1 ), we have

Since p is tight and therefore prudent, we also have, assuming best(t) = i and next(t

Plugging the above equations into Eq. (4.1), we get

A solution to a differential equation of the form y ′ (x) + αy(x) = β where α and β are constants is y = β α + Γ • e -αx , where Γ depends on the boundary condition. Hence in our case we conclude that

and p i (t) = 1 -p i+1 (t), where the constant Γ is determined by the boundary condition.

Eq. (4.3) is our tool to construct p in a piecewise iterative fashion. For example, we start constructing p from t = 0 using p 1 (t) = c•r 0 -r 0 r 1 -r 0 +Γ•e r 0 -r 1 b 1 -b 0

•t and the boundary condition p 1 (0) = 0. We get that Γ = r 0 (c-1) r 0 -r 1 , i.e.,

and this holds for all t ≤ min(s 1 , t 1 ), where t 1 is the solution to p 1 (t 1 ) = 1.

In general, Eq. (4.2) remains true so long as there is no change in the spending rate and in the slope the profile p is buying. The spending rate changes when t crosses s j , and the profile starts buying slope i + 2 when p i+1 (t) = 1.

We can now describe our algorithm. Given a ratio c, Algorithm Feasible is able to construct the tight profile p or to determine that such a profile does not exist. It starts with the boundary condition p 1 (0) = 0 and reveals the first part of the profile as shown above. Then, each time the spending rate changes or there is a change in best(i) it moves to the next differential equation with a new boundary condition. After at most 2k such iterations it either computes a c-competitive tight profile p or discovers that such a profile is infeasible. Since we are able to test for success using Algorithm Feasible, we can apply binary search to find the optimal competitive ratio to any desired precision.

We note that it is easy to construct a strategy that corresponds to any given prudent profile p, as described in the proof of Lemma 3.3. We conclude with the following theorem. Theorem 4.6. There exists an O(k log 1 ε ) time algorithm that given an instance of the additive multislope ski rental problem for which the optimal randomized strategy has competitive ratio c, computes a (c + ε)-competitive strategy.


Julien Camperi

Bart De Cock

Valerie Pichon

Audrey Combes

Jean Guibourdenche

Thierry Fournier

Yvan Vander Heyden

Debby Mangelings

Nathalie Delaunay
email: nathalie.delaunay@espci.fr

First characterizations by capillary electrophoresis of human Chorionic Gonadotropin at the intact level

Keywords: human Chorionic Gonadotropin, Intact protein, Glycosylation, Capillary electrophoresis, Mass spectrometry

In the present work, the first characterizations by Capillary Electrophoresis of the human Chorionic Gonadotropin (hCG) hormone at the intact level were carried out. hCG is a heterodimeric glycoprotein, specific to the human pregnancy, consisting of an α and a β subunit, socalled hCGα and hCGβ, respectively. hCG has 8 potential glycosylation sites leading to a high number of isoforms (including glycoforms and other post-translational modifications) that we are interesting to characterize. First, Capillary Gel Electrophoresis (CGE) was used to separate the isoforms of two hCG-based drugs: Ovitrelle® (recombinant r-hCG) and Pregnyl (hCG isolated from the urine of pregnant women, u-hCG). As expected, CGE led to a better resolution than SDS-PAGE and confirmed the large heterogeneity of hCG. Different CGE profiles were obtained for the two hCG-based drugs, varying in number of peaks, migration times, and peak intensities, thus demonstrating that the drugs contain isoforms, different in nature and proportion. This result was confirmed by Capillary IsoElectrophoretic Focusing (CIEF). The pI ranges of the hCG isoforms were found between 3.4 and 4.7, and 4.5 and 5.2 for r-hCG and u-hCG, respectively. This information was further used to develop the separation of the hCG isoforms by Capillary Zone Electrophoresis (CZE). The pH, the nature, and the concentration of the background electrolyte as well as the nature and the content of its organic modifier were optimized. The use of a coated capillary to avoid protein adsorption was also evaluated. The final CZE-UV method allowed distinguishing at least 6 peaks, corresponding to different hCG isoforms.

To significantly improve the level of information obtained, the CZE instrument was then coupled by means of an electrospray ionization source to a triple quadrupole (TQ) mass spectrometer. Two detection strategies were used, one focusing on the lower m/z values (100-1000) in order to identify some sugar residues as diagnostic ions to confirm the presence of glycan chains, and the second focusing on the higher m/z values , corresponding to the multiple charged intact protein isoforms. For both approaches, the fragmentor and capillary voltage values were optimized. The composition and the flow-rate of the sheath liquid were then optimized for the strategy focusing on the higher m/z values in order to both increase the charge state of the ionized intact isoforms and the signal-to-noise ratio. The final method was used to compare the two hCG-based drugs, demonstrating the potential of the developed CZE-MS method for isoforms fingerprinting.

Introduction

The human Chorionic Gonadotropin (hCG) protein is a hormone essential for the maintenance of the pregnancy and the development of both placenta and fetus [START_REF] Fournier | Review: hCGs: different sources of production, different glycoforms and functions[END_REF]. hCG is a hetero-dimeric glycoprotein consisting of an α and β subunit with a total of eight potential glycosylation sites, comprising 4 N-and 4 O-linked oligosaccharides. Its subunits, hCGα and hCGβ, are non-covalently associated and internally stabilized by a cysteine knot and disulfide bonds. The α-subunit is similar to other gonadotropin hormones, such as the luteinizing hormone (LH), the follicle-stimulating hormone (FSH), and the thyroid-stimulating hormone (TSH), while the β-subunit constitutes the specific part of the hCG [START_REF] Kessler | Structures of N-glycosidic carbohydrate units of human chorionic gonadotropin[END_REF]. hCGα has a molecular weight (MW) of 10,188 Da with 92 amino acids. Two asparagine-linked carbohydrate units (Nglycans) were determined on Asn-76 and Asn-102 residues [START_REF] Guibourdenche | Physiopathologie de l'hormone chorionique gonadotrope humaine (hCG) dans la trisomie 21 foetale[END_REF][START_REF] Gromoll | Male hypogonadism caused by homozygous deletion of exon 10 of the luteinizing hormone (LH) receptor: differential action of human chorionic gonadotropin and LH[END_REF]. hCGβ is composed of 145 amino acids and has a MW of 15,509 Da with two asparagine-linked glycans localized on Asn-33 and Asn-50 residues. Moreover, four serine-linked oligosaccharides (O-glycans) attached to serine residues 121, 127, 132, and 138 have also been shown [START_REF] Kessler | Structure and location of the O-glycosidic carbohydrate units of human chorionic gonadotropin[END_REF]. With eight potential glycans, hCG is a highly glycosylated protein and about 30% of its MW is due to the glycosylation [START_REF] Liu | Silencing of the gene for the alpha-subunit of human chorionic gonadotropin by the embryonic transcription factor Oct-3/4[END_REF]. Indeed, its mass range was estimated between 30 and 50 kDa. Glycosylation is a commonly observed post-translational modification (PTM) of proteins. Indeed, more than 70% of the human proteins are glycosylated [START_REF] Mechref | Recent advances in glycomics, glycoproteomics and allied topics[END_REF]. Studies demonstrated that the glycosylated state of a protein impacts directly its biological functions, its stability, its half-life, etc [START_REF] Guibourdenche | Physiopathologie de l'hormone chorionique gonadotrope humaine (hCG) dans la trisomie 21 foetale[END_REF]. Concerning hCG, studies demonstrated that different hCG glycoforms are produced by two distinct placental sources and that the glycan profile varies for each source of production during the pregnancy [START_REF] Guibourdenche | Physiopathologie de l'hormone chorionique gonadotrope humaine (hCG) dans la trisomie 21 foetale[END_REF][START_REF] Diaz-Cueto | More invitro bioactive, shorter-lived human chorionic gonadotrophin charge isoforms increase at the end of the first and during the third trimesters of gestation[END_REF]. Based on these considerations, some glycosylated forms of hCG could be potential biomarkers to diagnose pregnancy pathologies from placental origin, which represents a major societal challenge. Nevertheless, the full characterization of a glycoprotein is very complex due to the high number of isoforms, especially for hCG and its 8 glycosylation sites, which can give a very large number of glycoforms. Furthermore, other PTMs such as deamidation or oxidation may further complicate its characterization. Generally, the glycoprotein characterization is currently performed with the analysis of the peptides obtained after the enzymatic digestion of the protein, the so-called bottom-up strategy [START_REF] Zhu | Diethylaminoethyl Sepharose (DEAE-Sepharose) microcolumn for enrichment of glycopeptides[END_REF][START_REF] Alagesan | It is all about the solvent: on the importance of the mobile phase for ZIC-HILIC glycopeptide enrichment[END_REF][START_REF] Jiang | Characterization of the Glycosylation Occupancy and the Active Site in the Follow-on Protein Therapeutic: TNK-Tissue Plasminogen Activator[END_REF]. The peptides are separated by liquid chromatography (LC) or capillary electrophoresis (CE) prior to their identification by mass spectrometry (MS). This strategy allows the identification of proteins, the localization of the glycans along the protein chain and the determination of the MW of the glycans [START_REF] Zhang | Mass spectrometry for structural characterization of therapeutic antibodies[END_REF][START_REF] Sandra | Highly efficient peptide separations in proteomics[END_REF].

Concerning hCG, different studies using the bottom-up strategy allowed the sequencing of several N-glycopeptides with the composition of the associated glycans for each Nglycosylation site [START_REF] Zhu | A LC-MS All-in-One Workflow for Site-Specific Location, Identification and Quantification of N-/O-Glycosylation in Human Chorionic Gonadotropin Drug Products[END_REF][START_REF] Nerenz | Estimating the hCGβcf in urine during pregnancy[END_REF][START_REF] Lund | Immuno-MS based targeted proteomics: highly specific, sensitive, and reproducible human chorionic gonadotropin determination for clinical diagnostics and doping analysis[END_REF]. Furthermore, the interest of the use of a pronase as enzyme to isolate the O-glycosylation sites in order to determine the O-glycan composition of the βsubunit was also demonstrated [START_REF] Wuhrer | Structural glycomics using hydrophilic interaction chromatography (HILIC) with mass spectrometry[END_REF]. Other studies on the hCG showed the interest of a second approach based on the release of the N-glycans after an enzymatic digestion with PNGase-F to obtain the N-glycan profiling of different hCG-based drugs [START_REF] Liu | Mass spectrometric characterization of nicked fragments of the betasubunit of human chorionic gonadotropin[END_REF]. However, despite the interest of the bottom-up and released N-glycans approaches to elucidate the composition, the structure and the localisation of glycans on the protein, the information on the exact combinations of multiple PTMs (macro-heterogeneity) is lost. Moreover, these approaches suffer from some disadvantages because of the numerous steps that are usually necessary such as alkylation and reduction in addition to enzymatic digestion that are expensive, time consuming, and may lead to the loss of some monosaccharides or minority isoforms. This is why, currently, the analysis of the proteins at the intact level generates a large interest in the field of protein analysis [START_REF] Tran | Comprehensive glycosylation profiling of IgG and IgGfusion proteins by top-down MS with multiple fragmentation techniques[END_REF][START_REF] Haselberg | Capillary electrophoresis-mass spectrometry for the analysis of intact proteins 2007-2010[END_REF]. For hCG, composed of two subunits that both contribute to its bioactivity, it may also allow knowing which isoform of hCGα is associated with such isoform of hCGβ. Nevertheless, a high performance separation step is required because of the structural similarity of the isoforms, in order to reach the best possible separation resolution between the isoforms to facilitate their ionization in MS [START_REF] Sinha | Comparison of LC and LC/MS methods for quantifying N-glycosylation in recombinant IgGs[END_REF].

Both LC and CE are high-performance separation techniques and are used for the analysis of intact proteins [START_REF] Štěpánová | Recent applications of capillary electromigration methods to separation and analysis of proteins[END_REF][START_REF] Zhao | Applications of capillary electrophoresis in characterizing recombinant protein therapeutics: CE and CEC[END_REF][START_REF] Fekete | High resolution reversed phase analysis of recombinant monoclonal antibodies by ultra-high pressure liquid chromatography column coupling[END_REF][START_REF] Staub | Intact protein analysis in the biopharmaceutical field[END_REF]. We recently published the first characterization of hCG at the intact level by reversed-phase liquid chromatography (RPLC) coupled with high-resolution mass spectrometry (HRMS) [START_REF] Camperi | An attempt to characterize the intact human chorionic gonadotropin protein by reversed phase liquid chromatography coupled with high-resolution mass spectrometry[END_REF]. Nevertheless, only the main isoforms of hCGα were detected with this method. As LC and CE are based on different separation mechanisms, capillary electrophoresis can provide complementary information to the LC method. Moreover, CE is characterized by high efficiencies, especially with proteins since they have a low diffusion coefficient, involves aqueous conditions, which allow avoiding the conformational change due to a stationary phase, and can separate the protein isoforms as a function of their chargeto-size ratio, their pI values or their size depending on the involved mechanism.

The analysis of intact hCG or its subunits by electrokinetic techniques was mainly carried out at the non-miniaturized scale, i.e. SDS-PAGE or isoelectric focusing [27][START_REF] Gam | SDS-PAGE electrophoretic property of human chorionic gonadotropin (hCG) and its beta-subunit[END_REF][START_REF] Sutton | Charge variants in serum and urine hCG[END_REF][START_REF] Hoermann | Molecular heterogeneity of human chorionic gonadotropin in serum and urine from patients with trophoblastic tumors[END_REF]. These approaches require the use of toxic products, show a long analysis times, use expensive materials, high sample volumes while the separation resolution is low [START_REF] Rustandi | Applications of CE SDS gel in development of biopharmaceutical antibody-based products[END_REF]. This is why the use of electrokinetic methods at the capillary format is nowadays preferred, allowing fast analysis thanks to the possibility to apply electric fields 10 to 100 times higher without joule effect, leading to a high resolution for the separation of protein isoforms whatever separation mode used [START_REF] Štěpánová | Recent applications of capillary electromigration methods to separation and analysis of proteins[END_REF][START_REF] Zhao | Applications of capillary electrophoresis in characterizing recombinant protein therapeutics: CE and CEC[END_REF][START_REF] Zhu | Protein separation by capillary gel electrophoresis: A review[END_REF][START_REF] Fonslow | Native Capillary Isoelectric Focusing for the Separation of Protein Complex Isoforms and Subcomplexes[END_REF][START_REF] Morbeck | Analysis of the microheterogeneity of the glycoprotein chorionic gonadotropin with high-performance capillary electrophoresis[END_REF]. As far as we know, the capillary gel electrophoresis (CGE) and the capillary isoelectric focusing (CIEF) modes have never been used for the hCG characterization. Concerning capillary zone electrophoresis (CZE), three papers were published for hCG, all involving a non-volatile borate-or phosphate-based buffer and UV detection, thus preventing any identification [START_REF] Morbeck | Analysis of the microheterogeneity of the glycoprotein chorionic gonadotropin with high-performance capillary electrophoresis[END_REF][START_REF] Durgaryan | Identification of human chorionic gonadotropin hormone in illegally distributed products by MALDI-TOF mass spectrometry and double-injection capillary zone electrophoresis[END_REF][START_REF] Laidler | Characterization of Human Chorionic Gonadotropin Microheterogeneity by Capillary Electrophoresis: Potential Application for Quality Control in the Pharmaceutical Industry[END_REF]. To go further in the hCG isoform characterization, the hyphenation of the CZE separation with mass spectrometry is required. Indeed, the glycoform profiling of the intact alpha subunit (hCGα) was done by CZE coupled with a high resolution MS analyser [START_REF] Thakur | Profiling the Glycoforms of the Intact α Subunit of Recombinant Human Chorionic Gonadotropin by High-Resolution Capillary Electrophoresis-Mass Spectrometry[END_REF]. Hence, this work presents for the first time the analysis of dimeric hCG by CGE, CIEF, and CZE-MS. Two hCG-based drugs were used as standards: Ovitrelle® (recombinant hCG, r-hCG) and Pregnyl® (hCG from urine of pregnant women, u-hCG).

Material and methods

Reagents and analytes

Acetonitrile (ACN), isopropanol (IPA) and methanol (MeOH) were of HPLC grade. 1 M NaOH and 0.1 M HCl solutions were purchased from VWR (Fontenay-sous-bois, France). Bovine serum albumin (BSA, molecular mass, 66,000 Da), dimethylformamide (DMF, > 99%), hydroxypropyl cellulose (HPC, molecular mass, 100,000 > 99%), polyvinyl alcohol (PVA, molecular mass, 205,000 > 99%), phosphoric acid (85%), arginine, iminodiacetic acid, urea, β-mercaptoethanol, and HPLC acetone were purchased from Sigma-Aldrich (Saint-Quentin-Fallavier, France). Hydrochloric acid (HCl), formic acid (FA), and acetic acid (AC) were obtained from Carlo Erba (Val de Reuil, France). The ultra-pure water was obtained with a Direct-Q3 UV system (Millipore, Molsheim, France) and used for the preparation of all stock solutions and the background electrolyte (BGE).

Ovitrelle® and Pregnyl®, two hCG-based drugs, were used as recombinant hCG (r-hCG) and urinary hCG (u-hCG) standards, respectively. Ovitrelle® (Serono Europe, London, UK) was available as a solution containing 250 µg of r-hCG, and Pregnyl (Organon, Oss, The Netherlands) as a lyophilized powder containing 5000 IU of u-hCG (1 IU being equivalent to a concentration of 0.092 µg L -1 [START_REF] Berger | The molecular relationship between antigenic domains and epitopes on hCG[END_REF]). A lyophilized powder, containing 500 µg of r-hCGβ (recombinant Pichia pastoris, r-hCGβ), was purchased from Sigma-Aldrich (Saint-Quentin Fallavier, France). The Ovitrelle® solution was diluted in water to obtain a stock solution containing 100 mg L -1 of r-hCG. For Pregnyl® and r-hCGβ, the lyophilized content of each ampoule was reconstituted in water at a concentration of 100 mg L -1 . The standard solutions were aliquoted and stored at -20°C. Before the analysis in CZE-MS system, the hCG fractions were cleaned and concentrated by centrifugation with ultra-centrifugal units (Merck, Darmstadt, Germany) with a molecular weight cut-off of 10 kDa, to remove small additives from drug formulations.

Experimental set-up

CGE-UV method

The capillary gel electrophoresis method was carried out using a Beckman P/ACE MDQ capillary electrophoresis system (AB Sciex, Ulis, France) equipped with a diode array detector (DAD). The detection was performed at 220 nm ± 10 nm, the reference wavelength was 350 nm ± 10 nm and the data acquisition rate 2 Hz. The acquisitions were performed by the 32 Karat ® software version 9.1 (Beckman-Coulter). The separation was achieved using a bare fused-silica capillary (Photonlines, Marly-le-Roi, France) with an inner diameter of 50 µm, an effective length of 20 cm and a total length of 30.2 cm, installed into a PA 800 cartridge. The temperature cartridge was set at 25°C. The analysis of the hCG protein was performed with the SDS-MW Analysis Kit, delivered by Beckman ® , that was designed for the separation of protein-SDS complexes using a replaceable gel matrix. The kit utilises different reagents: ProteomLab SDS-MW sample buffer (100 mM Tris-HCl, 1% SDS, pH 9) and SDS-MW gel buffer. The SDS-MW size standard (recombinant proteins, 10-225 kDa, supplied with the ProteomeLAB TM SDS-Analysis Kit) was used to estimate the protein molecular weight. The bovine serum albumin (BSA, 66 kDa) was used as an internal standard (1 µg ml -1 in H 2 O, 2.5 µL in sample). β-mercaptoethanol (5 µL) was also added to each vial, containing 95 µL of protein sample (10 µl in 85 µl of sample buffer) or diluted SDS-MW size standard.

Then, the vials were capped tightly and heated at 100°C for 3 min. Prior to the CE analysis, a capillary preconditioning was performed by consecutively rinsing the capillary with 1 M NaOH (10 min, 20 psi), 0.1 M HCl (5 min, 20 psi), ultra-pure water (2 min, 20 psi), and SDS gel (10 min, 70 psi) before the application of a voltage with reverse polarity (-15 kV, 10 min) for SDS gel equilibration. Then, the hCG sample was injected electrokinetically (-5 kV, 20 s) at a concentration of 2 mg ml -1 in H 2 O. The applied voltage during the separation was set at -15 kV during 30 min.

CIEF-UV method

CIEF experiments were performed on an Agilent G7100 (Agilent Technologies, Massy, France) instrument, equipped with a DAD, using a bare fused-silica capillary coated with HPC with a total length of 30.2 cm (effective length: 20 cm) x 50 µm inner diameter. The detection was performed at 214 nm ± 4 nm and the reference wavelength was 360 nm ± 100 nm. The data acquisition was 10 Hz and the temperature 25°C. The electropherograms were processed by means of the 3D-CE Chemstation software (Agilent Technologies). The analysis of hCG was performed using the CIEF kit delivered by Beckman ® . The kit utilises 200 mM phosphoric acid as anolyte and 300 mM NaOH as catholyte. The cathodic and anodic stabilizers were 500 mM arginine and 200 mM iminodiacetic acid, respectively. The chemical mobilizer used was 350 mM acetic acid and the ampholytes provided a pH gradient between 3 and 10. The used peptidic pI markers had pI values of 10, 9.5, 7, and 5.5. The CIEF gel contained 6 M urea while the rinsing urea solution had a concentration of 4.3 M. The applied voltages during focusing and mobilization were set at 25 and 30 kV under normal polarity, respectively. The sample consisted of 500 µg ml -1 of r-hCG in H 2 O.

For the HPC coating, a polymer solution was prepared by dissolving at 40°C HPC in water at a concentration of 5% w/v. The procedure was according to Shen and Smith's protocol [START_REF] Shen | High-resolution capillary isoelectric focusing of proteins using highly hydrophilic-substituted cellulose-coated capillaries[END_REF], based on a physical adsorption of highly-hydrophilic substitute-celluloses onto the silica wall by a thermal process. For this purpose, the capillary was first pre-treated with acetone during 10 min, and then washed with 1 M NaOH for 30 min and with 0.1 M HCl and ultra-pure water for 10 min each. The polymer solution was then hydrodynamically pumped for 5 min through the capillary at approximately 1 bar. Then, the capillary was put in a gas chromatograph oven 3800 GC (Varian, Grenoble, France), heated from 60 to 140°C at 5°C min -1 , and held at 140°C for 20 min with a nitrogen flow. To evaluate the quality of the coating, the EOF was measured according to the Vigh's procedure [START_REF] Williams | Fast, Accurate Mobility Determination Method for Capillary Electrophoresis[END_REF]. The electroosmotic mobility determination was achieved as follows: (i) the capillary was filled with a BGE composed of 5 mM sodium phosphate at pH 7.0, (ii) a neutral marker plug (1% DMF, here), diluted in the BGE, was hydrodynamically introduced into the capillary, (iii) the DMF plug was moved by pressure, with the capillary inlet introduced in a vial containing BGE, (iv) another plug of DMF was hydrodynamically injected and also moved by pressure, with the capillary inlet introduced in a vial containing BGE, (v) a voltage of 15 kV was applied during 3 min in order to move both DMF bands with electroosmotic velocity toward the UV detector, (vi) a third plug of DMF was hydrodynamically introduced into the capillary, and finally (vii) a constant pressure was applied, with the capillary inlet introduced in a vial containing BGE until CE software recorded the passage of the three plugs of DMF (neutral marker) through the detection window. The capillaries having electroosmotic mobility values superior to 2 x 10 -5 cm 2 V -1 s -1 were discarded.

CZE-UV method

The CZE-UV experiments were carried out with an Agilent G7100 instrument. The detection was performed at 214 nm ± 4 nm and the reference wavelength was 360 nm ± 100 nm. A fused silica capillary with an internal diameter of 50 µm and a total length of 60 cm (effective length: 51.5 cm) was used. The applied voltage was + 30 kV with the optimized BGE; no joule heating was observed and the generated current was 32 µA. The capillary temperature was kept at 60°C. Prior to the first use, a capillary preconditioning was performed by rinsing the capillary with consecutively 1.0 M NaOH, 0.1 M NaOH, ultra-pure water, and BGE at a pressure of 1 bar during 20 min (3.28 µL min -1 ), each corresponding to about 55 capillary volumes. The CZE BGE composition after optimization was 800 mM formic acid and 800 mM acetic acid at a pH of 2.2. Methanol and isopropanol were used as organic modifiers in the BGE and the sheath liquid. The BGE was prepared weekly as all stock solutions, filtered through a 0.25 µm syringe filter (Minisart® RC25, Sartorius, Goettingen, Germany) and placed during 10 min in an ultra-sonic bath prior to CE experiments. For the PVA coating, the capillaries were prepared according to Belder's protocol [START_REF] Belder | Cross-linked poly(vinyl alcohol) as permanent hydrophilic column coating for capillary electrophoresis[END_REF]. First, the capillary was filled with an acidified aqueous glutaraldehyde solution (200 mL of a 50% aqueous solution mixed with 300 mL of 1:10 diluted conc. HCl). Then, an acidified PVA solution (450 mL of a 5% aqueous PVA solution, mixed with 50 mL of 1:1 H 2 O diluted HCl) was pumped through the capillary at approximately 1 bar for 5 min. Then, the capillary was put in the gas chromatograph oven, heated from 40 to 160°C at 6°C min -1 , and held at 160°C for 10 min with a nitrogen flow.

Between runs, the capillary was rinsed during 2 min with acetic acid (1 M) and 3 min with BGE both at a pressure of 1 bar (corresponding to 6-8 capillary volumes). The sample was injected hydrodynamically at 50 mbar during 20 s leading to an injection volume of 102 nL. The sample consisted of 500 µg ml -1 r-hCG in H 2 O. The sample injection was followed by a BGE plug injection at 50 mbar during 20 s.

CZE-(TQ) MS method

The CE-ESI-MS experiments were performed with an Agilent G7100 instrument utilizing an uncoated fused silica capillary with identical dimensions and from the same batch as during the CE-UV experiments. An Agilent CE ESI-MS sprayer and a Nano LC-pump sending the sheath liquid (H 2 O/MeOH/FA 50:50:0.1) was used at a flow rate of 0.6 µL min -1 . The ionization was operated in the positive mode and the measurements performed on the Agilent triple quad 6400 detector MS. The fragmentor voltage, capillary voltage, used m/z ranges, and the drying gas parameters are shown in Table 1.

Table 1:

Optimized parameters of the MS detection obtained for the r-hCG analysis by CZE-(TQ)MS for low (m/z 100-1000) and high (m/z 1000-2000) masses.

Results and discussion

Gel-electrophoretic analysis of hCG

The most conventional electrokinetic method used for the characterization of proteins is gel electrophoresis. It is based, in general, on the use of SDS to unfold the proteins: the SDS molecules interact with the protein all along the amino acid-based chain and confer a constant charge-to-size ratio to all proteins. Therefore, they all have the same electrophoretic mobility and migrate across the gel according to their size. Different isoforms of dimeric hCG were detected using the SDS-PAGE technique [27, [START_REF] Gam | SDS-PAGE electrophoretic property of human chorionic gonadotropin (hCG) and its beta-subunit[END_REF][START_REF] Hoermann | Molecular heterogeneity of human chorionic gonadotropin in serum and urine from patients with trophoblastic tumors[END_REF]. As reported, for example, by Gam and Latiff [START_REF] Gam | SDS-PAGE electrophoretic property of human chorionic gonadotropin (hCG) and its beta-subunit[END_REF], many hCG bands were observed with main apparent MWs around 43.5 kDa and 38.5 kDa. Notice that it is only possible to give apparent MWs. Indeed, hCG is a highly glycosylated protein and the glycan content alters the and charge from that of the hCG, that may be itself composed of various glycoforms with some of them being highly sialylated. Therefore, gel electrophoresis leads to apparent MWs of the hCG isoforms, but allows the comparison of different hCG profiles and can be helpful for the optimization of some protein treatment steps, such as their reduction.

In this study, the SDS-PAGE technique was used to test different conditions of reduction of hCG using r-hCG as standard. The results are shown in Figure S1. Whatever the used percentage of β-mercaptoethanol between 2.5 and 7.5% at 95°C, a reduction time of 3 min was insufficient to completely reduce hCG. Using a longer reduction time of 15 min, two large bands were detected around 25-30 kDa that may correspond to the hCGβ isoforms, and one large band close to 18-20 kDa, which could be assigned to different isoforms of hCGα.

Only with the harshest tested conditions, 7.5% of β-mercaptoethanol heated at 95°C for 15 min, the hCG protein was totally dissociated into its subunits hCGα and hCGβ. Next, for the first time for hCG, a high-performance capillary gel electrophoresis method was applied to separate the hCG isoforms. This was done with two hCG-based drugs, Ovitrelle® (r-hCG) and Pregnyl® (u-hCG). Figure 1 presents the resulting electropherograms. A protein MW standard mixture containing 7 recombinant proteins within the range of 10 to 225 kDa was used, not only to get calibration curves by plotting the MW as a function of the mobility (calibrations curves not shown) but mostly to evaluate the performance of the used analytical conditions (Figure 1A). It is obvious compared to SDS-PAGE (Figure S1, lane 1) that CGE provides improved resolutions with a shorter analysis time and a reduced sample consumption. Figure 1B presents the resulting electropherogram obtained with r-hCG after a partial reduction step (5% of β-mercaptoethanol heated at 95°C for 3 min). A large number of peaks were detected between 16 and 22 min (peaks 4 to 9), which may correspond to the time window expected for the hCG isoforms having MWs between 30 and 50 kDa, considering a potential shift in migration time due to glycan moieties on hCG. This confirms the high complexity of hCG, which did not appear so clearly from the previous SDS-PAGE analysis.

From the calibration curve, the apparent MW ranges of all main peaks were estimated considering the beginning and the end of each peak (Table 2), after calculating standard deviations on the apparent MWs, inferior or equal to 12 Da (n=3). As expected from the partial reduction conditions used before injection, some peaks that may correspond to hCGα isoforms (MW without glycan: 10,198 Da) and hCGβ (MW without glycan: 15,521 Da) were detected at the beginning of the electropherogram (peaks 1 and 2 for hCGα and peak 3 for hCGβ). Figure 1B shows also two peaks with apparent MWs higher than 80 kDa (peaks 10 and 11), which may correspond either to highly-glycosylated hCG isoforms or to hCG aggregates.

A hCG-based drug obtained after extraction from urine of pregnant women, u-hCG, was next analysed by CGE-UV in the same conditions, including the same partial reduction step. The resulting electropherogram is presented on Figure 1C. As expected since u-hCG is produced from complex biological samples, the corresponding electropherogram is much more complex, with additional peaks between 10 and 14 min compared to the r-hCG electropherogram. These peaks (1 to 5) correspond to apparent MWs values between 6,300 and 9,780 Da that all are inferior to the MW of the α-subunit, even without any glycan. It can therefore be assumed that these peaks may correspond to either (i) other urinary proteins, (ii) cleaved forms of u-hCG, and/or (iii) highly sialylated hCGα. This last hypothesis is based on the fact that the presence of a high number of sialic acids on glycan moieties should accelerate the migration of the protein through the gel thanks to an additional anodic electrophoretic mobility contribution, and that some authors already observed a higher fraction of acidic hCG isoforms in urine [START_REF] Sutton | Charge variants in serum and urine hCG[END_REF][START_REF] Hoseby | Clearance of circulating γ-glutamyltransferase by the hepatic galactose receptor. Variability in clearance rate due to carbohydrate heterogeneity of the enzyme[END_REF]. As previously discussed with r-hCG, the peaks 6, 7, and 8 can be assigned with a high level of confidence to the isoforms of the α-subunit and the peak 9 to one of the β-subunit. Figure 1C also shows a wide and quite intense massif of peaks eluting within the same range of migration times (16-22 min) as those of r-hCG. They should correspond to the u-hCG isoforms. Then, the peaks 13 and 14 in u-hCG (see Figure 1D for the enlarged view) were also detected with apparent MWs above 70 kDa, which may again correspond either to aggregated or highly glycosylated hCG.

Finally, the most important result obtained by CGE analysis of both hCG-based drugs appears on Figure 1D, where the electropherograms were overlaid in the area of interest, corresponding to the hCG isoforms. Two different profiles appear, with a varying number of peaks, different migration times and intensities. This clearly demonstrates that both hCGbased drugs contained isoforms, different in nature and amount. This study constitutes the first demonstration that CGE can be a useful and high performance technique for hCG fingerprinting. Nevertheless, CGE suffers from a big drawback: its incompatibility for a direct coupling with mass spectrometry, preventing further identification of the separated isoforms.

Table 2:

Apparent MW range (determined as the estimated MWs at the beginning and end of each peak) and signal-to-noise ratio (S/N) of the main peaks seen in the CGE-UV analysis of r-hCG and u-hCG (u-hCG and r-hCG: 2 mg mL -1 ). For peak number: see Figures 1B, 1C and 1D.

CIEF-UV method

A second electrokinetic technique usually involved in protein characterization is based on isoelectric focusing allowing a separation according to pI values. It has already been used at conventional format for hCG, to compare its isoforms in urine and serum samples [START_REF] Sutton | Charge variants in serum and urine hCG[END_REF][START_REF] Hoermann | Molecular heterogeneity of human chorionic gonadotropin in serum and urine from patients with trophoblastic tumors[END_REF].

The obtained pI values were in the acidic range, between 3 and 7 in one case [START_REF] Sutton | Charge variants in serum and urine hCG[END_REF] and 3.3 and 4.9 in the second [START_REF] Hoermann | Molecular heterogeneity of human chorionic gonadotropin in serum and urine from patients with trophoblastic tumors[END_REF]. For the first time, the capillary format (CIEF) was used here for hCG in order to improve significantly the resolution, as it can distinguish two proteins whose pI differ by as few as 0.005 pH units and allows determining of protein-charge heterogeneity profiles [START_REF] Zhao | Applications of capillary electrophoresis in characterizing recombinant protein therapeutics: CE and CEC[END_REF].

For the CIEF analysis of hCG, 5 isoelectric pI markers with values between 4.1 and 10.0 were selected and analysed using a CIEF kit and an ampholyte 3-10 (Figure 2A). During the focusing step of 15 min, some pre-peaks were detected thus confirming the success of this 2B). During the CIEF study, a calibration curve was built for each acquisition. However, the pI marker at 4.1 was not added in the preparation for the experiments because it would have co-migrated with some hCG isoforms. First, r-hCG was mixed with the different pI markers, the cathodic and anodic stabilizers, the ampholytes providing a pH gradient between 3 and 10, and the CIEF gel containing 6 M urea.

After the focusing and mobilisation steps, one typical resulting electropherogram is shown in Figure 2C. At least 15 r-hCG isoforms with pI values between 3.0 and 5.5 were separated.

Table 3 presents the RSDs calculated for the migration times by taking the apex of the main peaks (n=3). They are between 0.92 and 1.23% for the migration times, which confirms the high repeatability of the CIEF method. With the calibrations curves, the corresponding pI values were determined, between 3.49 and 4.78, with RSD values below 1.55%. The results confirm the high resolution of the CIEF analysis for the characterization of protein isoforms, in particular hCG here, even if it is a very complex protein because of its 8 glycosylation sites.

Table 3: Relative standard deviation (RSD) values of the migration times and the estimated pI values of the main peaks obtained for the r-hCG analysis by CIEF-UV (n=3). r-hCG: 500 mg L -1 . For peaks number: see Figure 2C.

Then, u-hCG was analysed by CIEF at the same conditions and Figure 2D presents an overlay in the area of interest of the resulting electropherogram with the one obtained for r-hCG. Two significantly different profiles can be observed, which confirms the previous result obtained in CGE that both hCG-based drugs contained isoforms, different in nature and proportion.

Nevertheless, the u-hCG signal intensity is inferior to that of r-hCG. Two explanations can be provided. First, u-hCG is produced by extraction from urine and its bioactivity was determined to be 9,200 IU mg -1 . Since each ampoule of drug contains 5,000 IU u-hCG, the calculation of the concentration in mg L -1 u-hCG was done considering that 1 IU was equal to 0.092 [START_REF] Berger | The molecular relationship between antigenic domains and epitopes on hCG[END_REF][START_REF] Berger | The ISOBM TD-7 Workshop on hCG and related molecules. Towards user-oriented standardization of pregnancy and tumor diagnosis: assignment of epitopes to the three-dimensional structure of diagnostically and commercially relevant monoclonal antibodies directed against human chorionic gonadotropin and derivatives[END_REF]. This calculation hypothesis may be inaccurate. Secondly, it is known that cleaved forms of hCG occur in urine and they may also be present in the u-hCG-based drug.

These cleaved forms may still be bioactive and contribute to the lower intensities of the u-hCG peaks with respect to the intensities of the r-hCG peaks, for which the concentration in mg L -1 is given by the manufacturer. Nevertheless, this experiment allows estimating a pI range between 4.5 and 5.2 for the u-hCG isoforms. This pI range, though somewhat narrower, is comparable to that obtained for r-hCG.

CZE-UV

Capillary zone electrophoresis involves a migration mechanism based on the charge and friction coefficient ratio of the molecule. It is particularly relevant for the separation of intact proteins, including the fingerprinting of intact isoforms [START_REF] Štěpánová | Recent applications of capillary electromigration methods to separation and analysis of proteins[END_REF][START_REF] Haselberg | CE-MS for the analysis of intact proteins 2010-2012: CE and CEC[END_REF]. This is why this approach was implemented for hCG [START_REF] Morbeck | Analysis of the microheterogeneity of the glycoprotein chorionic gonadotropin with high-performance capillary electrophoresis[END_REF][START_REF] Durgaryan | Identification of human chorionic gonadotropin hormone in illegally distributed products by MALDI-TOF mass spectrometry and double-injection capillary zone electrophoresis[END_REF][START_REF] Laidler | Characterization of Human Chorionic Gonadotropin Microheterogeneity by Capillary Electrophoresis: Potential Application for Quality Control in the Pharmaceutical Industry[END_REF][START_REF] Thakur | Profiling the Glycoforms of the Intact α Subunit of Recombinant Human Chorionic Gonadotropin by High-Resolution Capillary Electrophoresis-Mass Spectrometry[END_REF]. Nevertheless, as already mentioned in the introduction, three of the four papers involved a non-volatile borate-or phosphate-based buffer and UV detection preventing any identification [START_REF] Morbeck | Analysis of the microheterogeneity of the glycoprotein chorionic gonadotropin with high-performance capillary electrophoresis[END_REF][START_REF] Durgaryan | Identification of human chorionic gonadotropin hormone in illegally distributed products by MALDI-TOF mass spectrometry and double-injection capillary zone electrophoresis[END_REF][START_REF] Laidler | Characterization of Human Chorionic Gonadotropin Microheterogeneity by Capillary Electrophoresis: Potential Application for Quality Control in the Pharmaceutical Industry[END_REF]. To go further in the hCG isoform characterization, the hyphenation of the CZE separation with mass spectrometry (MS) is required, as it was done for the glycoform profiling of the intact hCGα [START_REF] Thakur | Profiling the Glycoforms of the Intact α Subunit of Recombinant Human Chorionic Gonadotropin by High-Resolution Capillary Electrophoresis-Mass Spectrometry[END_REF]. The optimization of the CZE-MS method for the hCG analysis first started with a simple UV detector for the sake of simplicity, but taking into consideration that the final purpose was the hyphenation of the CZE separation with an MS detection. Therefore, a long capillary length of 60 cm (effective length: 51.5 cm) and a volatile BGE were selected.

Even if it was demonstrated that it was not possible to establish a generic CZE approach for the intact protein analysis and its transfer to CE-MS, two approaches are generally considered: working with a BGE at a pH either below or above the pI values of the proteins [START_REF] Staub | Use of organic solvent to prevent protein adsorption in CE-MS experiments[END_REF]. With a BGE pH below their pI values, proteins are positively charged and may interact with the deprotonated silanol groups at the surface of the capillary and, consequently, may adsorb more or less irreversibly, which is one of the main difficulties of protein analysis in CZE [START_REF] Štěpánová | Recent applications of capillary electromigration methods to separation and analysis of proteins[END_REF][START_REF] Staub | Intact protein analysis in the biopharmaceutical field[END_REF][START_REF] Staub | Use of organic solvent to prevent protein adsorption in CE-MS experiments[END_REF]. To limit this phenomenon, a capillary coating and/or a highly acidic pH can be used, to reduce as much as possible the deprotonation of the silanols and to favour the ESI-MS ionization in positive mode. With a BGE pH above their pI values, proteins are negatively charged, as is also the capillary wall, and electrostatic repulsions may limit their adsorption.

In previous works related to the CZE analysis of hCG, a bare fused-silica capillary and a BGE pH between 6 and 9 and containing some diaminoalkane were used [START_REF] Morbeck | Analysis of the microheterogeneity of the glycoprotein chorionic gonadotropin with high-performance capillary electrophoresis[END_REF][START_REF] Durgaryan | Identification of human chorionic gonadotropin hormone in illegally distributed products by MALDI-TOF mass spectrometry and double-injection capillary zone electrophoresis[END_REF][START_REF] Thakur | Profiling the Glycoforms of the Intact α Subunit of Recombinant Human Chorionic Gonadotropin by High-Resolution Capillary Electrophoresis-Mass Spectrometry[END_REF]. At this pH range and according to the pI values previously observed in CIEF, the hCG isoforms are negatively charged, which should limit their interactions with the capillary surface.

Thus, our first CZE experiments were carried out with a bare fused-silica capillary and a volatile BGE based on ammonium acetate at pH 8.0. It is worthwhile to note that the optimization of the parameters was done with r-hCG, which is purer than u-hCG. Unfortunately, a strong adsorption of hCG on to the capillary wall was observed, leading to peak broadening and low separation efficiencies. Different parameters were then tested to limit this phenomenon: an increase in the ionic strength from 50 up to 200 mM (maximum value allowing a voltage of 30 kV without detrimental Joule heating) by increments of 50 mM, an increase in the separation temperature from 25 to 60°C with increments of 5°C, and the use of a HPC capillary coating as usually described in the literature [START_REF] Haselberg | Capillary electrophoresis-mass spectrometry for the analysis of intact proteins 2007-2010[END_REF][START_REF] Štěpánová | Recent applications of capillary electromigration methods to separation and analysis of proteins[END_REF][START_REF] Haselberg | CE-MS for the analysis of intact proteins 2010-2012: CE and CEC[END_REF][START_REF] Balaguer | Glycoform characterization of erythropoietin combining glycan and intact protein analysis by capillary electrophoresis electrospray time-of-flight mass spectrometry[END_REF][START_REF] Balaguer | Glycoprotein Characterization Combining Intact Protein and Glycan Analysis by Capillary Electrophoresis-Electrospray Ionization-Mass Spectrometry[END_REF]. The best separation was obtained with a HPC-coated capillary, an ionic strength of 200 mM and a temperature of 60°C as shown on Figure S2. In that case, 6 wide peaks were observed with a total analysis time of about 50 min. It was highly probable that each peak corresponds to several glycoforms or other types of post-translational modifications, such as methylation, oxidation or amidation. For comparison, our second approach consists of using a highly acidic BGE as was reported for the CZE-MS analysis of hCGα (BGE composed of 2% acetic acid at pH 2.5, but without any motivation of this choice) [START_REF] Thakur | Profiling the Glycoforms of the Intact α Subunit of Recombinant Human Chorionic Gonadotropin by High-Resolution Capillary Electrophoresis-Mass Spectrometry[END_REF]. With a BGE pH below the previously determined pI values, the hCG isoforms are positively charged. BGEs based on formic acid (FA) and acetic acid (AC) at pH 2.2 were selected as they are both MS compatible and classically involved in this kind of application [START_REF] Haselberg | CE-MS for the analysis of intact proteins 2010-2012: CE and CEC[END_REF]. The effects of the nature and the concentration of the acids, alone or mixed (keeping their concentration constant) were first studied with a high voltage (30 kV) and a high temperature (60°C). As illustrated on Figure 3A, their combination led to an increased number of peaks and improved resolutions. This option was thus selected. It can also be noticed that the use of the acid BGE provides a dramatic decrease by a factor 10 in the analysis time compared to the basic BGE, whereas a similar number of peaks was observed.

The concentration of each acid in the BGE was next varied from 0.2 to 1.0 M (Figure 3B). No Joule heating even at 30 kV was observed, regardless the tested concentrations. The concentrations of 800 mM of both FA and AC led to the best resolution and the highest number of separated isoforms. Therefore, this high BGE concentration may also help to prevent protein adsorption. Nevertheless, the potential problem of protein adsorption was considered. The use of a neutral polyvinyl alcohol (PVA) coating was first evaluated (Figure 3C), but it led to an increased baseline drift and a decrease in resolution and sensitivity. A second strategy to limit hCG adsorption was the addition of an organic modifier to the BGE, as already reported [START_REF] Haselberg | CE-MS for the analysis of intact proteins 2010-2012: CE and CEC[END_REF][START_REF] Staub | Use of organic solvent to prevent protein adsorption in CE-MS experiments[END_REF]. Indeed, the solvent may modify the zeta potential of the capillary surface, change the ionization state of the proteins and the silanol groups, reduce the hydrophobic interactions between the proteins and the wall, and change the protein conformation and solvation, which all may change the selectivity and reduce the adsorption. It may also favour the desolvation process in the ESI source. Both isopropanol and MeOH were tested at 10, 20, and 30%.

Concerning the use of isopropanol as organic modifier, no improvement of the separation was seen. In return, the addition of 20% MeOH led to the best sensitivity and resolution (Figure 3D). The final BGE composition was thus 800 mM FA, 800 mM AC, and 20% MeOH, which led to the detection of 8 peaks within 8 min.

CZE-MS

The conditions optimized in CZE-UV were used for the hyphenation to a Triple Quadrupole mass spectrometer with an ESI interface and a nano-LC pump delivering a sheath liquid. Two different strategies for MS detection were used during this study: a detection targeting a low mass range (100-1000 m/z) and one targeting a high mass range (1000-2000 m/z). Both strategies needed an individual optimization. The conditions were first optimized for the low mass range. The fragmentor voltage was varied from 135 to 380 V, while keeping all other MS parameters constant. The highest sensitivity was obtained with a fragmentor voltage value of 380 V. While maintaining the fragmentor voltage at 380 V, the capillary voltage of MS was varied from 0.5 to 6 kV. Some peaks appeared on the Base Peak Electropherogram (BPE) from a value of 2 kV and the maximum sensitivity was achieved at 3 kV. For the high mass range, a low fragmentor voltage of 135 V and a high capillary voltage of 5.5 kV were selected in order to avoid the fragmentation in the MS source and allow the transfer of the heaviest ions for the detection of intact isoforms. The retained MS parameters are summarized in Table 1. These two sets of parameters were used for the analysis of r-hCG. Figure 4A shows the corresponding BPE with the MS conditions adapted to the low mass range. Using a classical sheath liquid consisting of H 2 O-IPA (1/1) and 0.01% FA, at least 10 peaks were observed with an analysis time below 5 min. The decrease in analysis time, while increasing the separation length from the previous effective length in UV (51.5 cm) to the total capillary length in MS (60 cm), may come from small variations in the low electroosmotic velocity and from some suction effect [START_REF] Mokaddem | A new insight into suction and dilution effects in capillary electrophoresis coupled to mass spectrometryvia an electrospray ionization interface. Part I-Suction effect[END_REF]. The relative standard deviation values for the migration times and the intensities are summarized in Table 4 and are all inferior to 1.1% and 3,0%, respectively (n= 3), demonstrating a good repeatability of the CZE separation with at low mass range conditions of MS detection. Figure 4B shows the resulting MS spectrum obtained for peak 4 (between 3.75 and 3.83 min).

It allows identifying some fragment ions corresponding to monosaccharides, such as galactose (Gal, m/z 163 Da) , mannose (Man, m/z 163 Da), acetylneuraminic acid (NeuAc, m/z 292 Da), and acetylglucosamine (GlcNAc, m/z 204 Da) and some combinations. These monosaccharides confirm the presence of glycan chains on the glycoprotein. However, no detection of intact isoforms is possible within the targeted mass range. 1.

Therefore, r-hCG was next analysed by CZE-ESI-MS applying the high-mass range MS conditions. With the parameters of sheath liquid used above (H 2 O-IPA (1/1) + 0.01% FA), the obtained BPEs at the high-mass range MS conditions were non-repeatable and without isotopic profiles. However, it is well-known that the composition of the sheath liquid has a strong impact on the ionization process [START_REF] Štěpánová | Recent applications of capillary electromigration methods to separation and analysis of proteins[END_REF][START_REF] Haselberg | Capillary electrophoresis-mass spectrometry for the analysis of intact proteins[END_REF]. This is why the sheath liquid composition was modified in order to improve the efficiency and repeatability of the ionization step.

Moreover, the Triple Quadrupole (TQ) MS has a low maximum mass-to-charge ratio, namely 2000 m/z, which is rather low for the analysis of intact proteins. One of our purposes was thus also to increase as much as possible the ionization state charge of the hCG isoforms to decrease their m/z values.

Therefore, the percentage of FA in the sheath liquid was varied from 0.01 to 0.5%. An increase in sensitivity was observed at 0.1% (see Figure S3 in supplementary data), but still no repeatable electropherograms were obtained. In a second approach, the nature of the sheath liquid was altered from H 2 O-IPA to H 2 O-MeOH, while maintaining 0.1% FA and a ratio of 1/1. It led to an increased charge state and thus reduced m/z values and repeatable isotopic massifs in the 1000-2000 m/z range. Finally, the sheath-liquid flow rate was optimized as it is also known that this parameter affects the ionization process [START_REF] Haselberg | Capillary electrophoresis-mass spectrometry for the analysis of intact proteins[END_REF]. It was varied from 0.2 to 1.0 µl min -1 . While applying a flow rate of 0.6 µl min -1 , a stable spray and repeatable migration times were obtained with these MS parameters for the high-mass range (1000-2000 m/z). see experimental section 2.2.4 and Table 1.

After optimization of the sheath liquid, the resulting r-hCG BPE showed at least 12 peaks between 4.25 and 5.01 min, corresponding to hCG isoforms with different glycosylations or PTMs (Figure 5A). It is worthwhile to notice the difference in migration times with the CZE separation obtained at the low mass range MS conditions (3.08-4.25 min, see Figure 4A). This is probably due to the different composition (H 2 O/MeOH/FA) of the sheath liquid, which can induce a suction effect.

These conditions were also used for the analysis of u-hCG, in order to evaluate the potential of this approach to distinguish some differences between the two drugs (Figure 5B). The separation profile showed two elution zones, the first one between 3.76 and 4.05 min, and the second one between 4.24 and 5.45 min, but the resolution is not insufficient here to distinguish individual peaks, probably due to the high complexity of the u-hCG sample. Nevertheless, the identification of the r-and u-hCG isoforms is impossible due to the low resolution of the triple quadrupole MS detector. Indeed, the analysis of glycoproteins such as hCG with 8 glycosylation sites, requires an MS detector with a higher resolution, such as a quadrupole/time-of-flight (QTOF), to obtain the isotopic profiles of each isoform allowing a correct spectrum deconvolution for their identification. However, this CZE-(TQ)MS strategy and u-hCG: 0.5 mg mL -1 . Other conditions: see experimental section 2.2.4 and Table 1.

Conclusion

In order to better characterize the heterogeneity of hCG, its analysis at the intact level by different high-performance capillary electrokinetic techniques (CGE-UV, CIEF-UV, CZE-UV, and CE-ESI-MS) was undertaken for the first time. This study confirmed the very high heterogeneity of hCG isoforms, leading to different pI and electrophoretic mobility values. After optimization of several experimental parameters, the CZE-MS analysis with a Triple Quadrupole detector demonstrates, for the first time, its potential for a fingerprinting approach as it allows to differentiating the two hCG-based drugs. In addition, this method is fast and cheap, compared to conventional bottom-up approaches. Therefore, a full validation of this method seems to be relevant as a perspective for this work. Finally, the conditions of the CZE method can be used for the hyphenation with a high-resolution mass spectrometer, such as a

Figure S1 :

 S1 Figure S1: Study of the reduction conditions on r-hCG by SDS-PAGE. Lane 1: protein molecular weight markers; lane 2: not reduced r-hCG; lane 3: 2.5% β-mercaptoethanol at 95°C during 3 min; lane 4: 2.5% β-mercaptoethanol at 95°C during 15 min; lane 5: 5% βmercaptoethanol at 95°C during 3 min; lane 6: 5% β-mercaptoethanol at 95°C during 15 min; lane 7: 7.5% β-mercaptoethanol at 95°C during 3 min; lane 8: 7.5% β-mercaptoethanol at

Figure 1 :

 1 Figure 1: Analysis by CGE-UV of r-hCG and u-hCG after a partial reduction. (A) Protein MW standard mixture; (B) r-hCG, with a zoom between 10 and 14 min (1), and between 16 and 22 min (2); (C) u-hCG; and (D) overlay of the r-hCG and u-hCG electropherograms between 16 and 23 min. BSA was added as an internal standard in all samples. r-hCG and u-hCG: 2 mg mL -1 .Other conditions: see experimental section 2.2.1.

Figure 2 :

 2 Figure 2: Analysis of r-hCG and u-hCG by CIEF-UV. (A) CIEF analysis of 5 pI markers, (B) Calibration curve, (C) CIEF analysis of r-hCG, and (D) overlay CIEF electropherograms of r-hCG and u-hCG in a reduced time range (marker 4.1 added only in the u-hCG sample). r-hCG and u-hCG: 2 mg mL -1 . Other conditions: see experimental section 2.2.2.

Figure S2 :

 S2 Figure S2: Electropherogram obtained for the r-hCG analysis by CZE-UV with a volatile basic BGE: 200 mM ammonium acetate at pH 8.0. HPC-coated silica capillary, 50 μm x 60 cm (effective length: 51.5 cm). Hydrodynamic injection: 20 s, 50 mbar. Voltage: -30 kV. Temperature: 60°C. UV detection: 214 nm. r-hCG: 0.500 mg mL -1 .

Figure 3 :

 3 Figure 3: Optimization of the CZE-UV separation of r-hCG. (A) Effect of the BGE composition. (B) Effect of the acid concentrations. (C) Comparison between the use of bare and PVA-coated capillaries. (D) Effect of MeOH addition in BGE (800 mM of AC and FA, pH 2.2). r-hCG: 0.5 mg mL -1 . Other conditions: see experimental section 2.2.3.

Table 4 :

 4 Relative standard deviation (RSD) values of the migration times and the relative intensity of 4 main peaks obtained for the r-hCG analysis by CZE-(TQ)MS with the optimized MS conditions for the low mass range (n=3). Other conditions and peak numbers: see Figure 4A. r-hCG: 500 mg L -1 .

Figure 4 :

 4 Figure 4: CZE-MS analysis of r-hCG with the MS parameters for the low-mass range (100-1000 m/z). (A) Base Peak Electropherogram (BPE). (B) MS spectrum between 3.75 and 3.83 min (peak 4) on the BPE with the different diagnostic ions. r-hCG: 0.5 mg mL -1 . Other conditions: see experimental section 2.2.4 and Table1.

Figure S3 :

 S3 Figure S3: Effect of FA percentage in the sheath liquid on the BPEs obtained from r-hCG by CZE-MS for the high-mass range (1000-2000 m/z). r-hCG: 0.5 mg mL -1 . Other conditions:

  Figures 5C and 5D present the MS spectra between 4.24 and 5.01 min on the BPEs for r-and u-hCG-based drug, respectively. The m/z values corresponding to hCG isoforms of r-hCG are mainly comprised between 1500 and 1900, with three intense peaks at m/z 1530.6, 1562.2, and 1595.0. With u-hCG, the mass range of isoforms is different with m/z values comprised between 1400 and 1650. The differences between the two MS profiles confirm clearly the presence of different isoforms in each hCG-based drug, which probably results from their different sources of production (recombinant or extracted from the urine of pregnant women).

  for fingerprinting to compare different batches of a given hCG drug or different hCG-based drugs.

Figure 5 :

 5 Figure 5: CZE-MS analysis of r-hCG and u-hCG with the MS parameters for the high-mass range (1000-2000 m/z). Base Peak Electropherograms (BPE) of (A) r-hCG and (B) u-hCG. Mass spectra between 4.24 and 5.01 min on the BPEs of (C) r-hCG and (D) u-hCG. r-hCG

  gel electrophoresis, because (i) the SDS molecules do not interact with the glycan moieties and, (ii) the glycan moieties can have a charge if they contain, for example, sialic acids. This is why the glycan moieties confer an additional electrophoretic contribution to that of the protein, which may decrease or increase its total apparent electrophoretic mobility. This explains why some authors observed what they called abnormal migration shifts in some cases when they implemented successive digestions with different enzymes to remove gradually the glycans from hCG [27]. To overcome this limitation, Magnelli et al used a glycoprotein standard ladder (Candy-Cane from Invitrogen)[27]. However, it cannot lead to a correct MW determination as the glycan content of the standard glycosylated proteins may be dramatically different in nature (size)

	hCG mobility in
	Mass range (m/z)	100-1000 1000-2000
	Voltage fragmentor (V)	380	135
	Voltage capillary (V)	3000	5500
	Drying gas	N 2	N 2
	Temperature (°C)	300	300
	Flow (L/min)	11	11
	Pressure (Psi)	15	15

Acknowledgments

The authors acknowledge the financial support from Institute Pierre Gilles de Gennes for microfluidic (IPGG, Paris, France).

QTOF, which should be helpful for the identification of the different isoforms (glycoforms and other PTMs).