Fabien Leurent

Shared Scooter Service (S3) Model with Prior Booking 1 On a Shared Scooter Service under Ring Shape, Free-Floating and Prior

Keywords: shared mobility services, free-floating scooters, vehicle occupation, fleet sizing, stochastic model, traffic equilibrium

Shared Scooter Services (S3) have been deployed in many cities to provide public transport to individual users on a free-floating basis. The article brings about an analytical traffic model for such service under ring shape, i.e. postulating there is a ring road along which the scooters are required to park and expected to be driven, in order to avoid detours and increase vehicle productivity as well as local availability to potential users. Prior booking is postulated, supposedly on a web app. Also postulated are the homogeneity in both space and time. With respect to the ring circumference, the daily volume of potential trips, the statistical distributions of trip lengths, walk speeds an ride speeds, as well as the fleet size, operation period and transaction times, analytical formulas are provided for (i) access lengths and times, together with usage probability, (ii) ride lengths and times, (iii) vehicle occupation at the fleet level, (iv) the average number of available vehicles. Traffic equilibrium is shown to exist and to be unique or bi-valued with one fluid state versus one congested state. Its characteristic equation is recast as a fleet sizing rule according to demand volume and target access length, which stand respectively as the quantitative and qualitative service objectives.

1/ Introduction

Background. In recent years, e-scooters have emerged as a convenient mode of travel for many individuals. As a vehicle, an e-scooter is agile and its motor enables for speeds up to 20 km/h and beyond: this is quite efficient in the urban setting. Furthermore, its small size and light weight make it easy to carry out e.g. in a car trunk or in transit vehicles (buses, trains).

The parallel development of connectedness both for vehicles and for people owing to smartphones has given rise to many shared mobility services. Among them, e-scooters sharing systems have been deployed in many big cities worldwide.

To what extent may such e-scooter sharing services contribute to public transport in urban areas? This question carries obvious stakes for mobility planners in territories. Shared escooters look environmental friendly compared to private cars, not only in terms of matters utilized and energy consumed but also to the cityscape: their parking requires little space and their traffic is by far less intrusive and dangerous to pedestrians.

Objective. A number of traffic models have been developed to perform traffic studies with much detail in space and time. This paper brings about a simple traffic model for an e-scooter shared mobility service under ring shape. The principle is to channel the users' trips in the territorial space, so as to increase vehicle availability along the ring, to avoid detours, to ease the service logistics (from vehicle maintenance to energy refills, passing by fleet repositioning). By simultaneously reducing the operational costs and increasing vehicle productivity, a ring-shaped service is expected to reach commercial profitability under wider conditions of demand and territory, thereby enabling the planners to expand the spatial outreach of public transport. In the model, the territorial conditions are represented as the radius of the ring and the riding speed, a daily volume of trips and the average length of them. The fleet size is given and the service is operated in free-floating mode. The service users go to the closest available scooter, which they book in advance using a mobile application. From these assumptions, the model determines the occupation of the vehicle fleet, its availability, the access conditions in terms of walk lengths and walk times, as well as riding times depending on users' ride speeds.

Methodology.

Homogeneity is postulated regarding both space and time. Spatial homogeneity is postulated for trip origin and destination endpoints, hence for the positions of available vehicles. Combined to the ring shape, this spatial homogeneity gives rise to circular symmetry. Temporal homogeneity is postulated along a daily period of "active duty": for instance a 14h period from early morning to evening.

Traffic is modeled in disaggregate and stochastic way. Each service request is identified with its own service user. Trip lengths are modeled as a statistical distribution. Users are modeled in terms of walk speeds and ride speeds, with joint statistical distribution.

By facing the total workload demanded by the users to the fleet size times the period duration, we establish the condition of traffic equilibrium at the system level as a characteristic equation with respect to the number of vacant vehicles. In appendix, we show that the macroscopic equilibrium condition is consistent with the stochastic equilibrium of a two-state Markov model at the disaggregate level of one scooter (Available vs. Busy states). All in all, given the daily trip volume and the fleet size, the model determines the average walk length say ℓ, which indicates service quality. The relationship can be expressed equivalently as a function ℓ ( , ) or a function ( , ℓ), which is useful for planning purposes.

Article structure. The rest of the article is in seven parts. Section 2 describes the system: territorial conditions, service supply and travel demand. Section 3 introduces the model architecture. After modeling successively Service access in Section 4, User rides in Section 5 and Scooter occupation in Section 6, the model is integrated in Section 7. Lastly, Section 8 concludes and points to theoretical developments.

2/ System description and mathematical notation

Inside an urbanized territory, assume that a roadway circuit is designated as pathway for the shared e-scooters. By assumption, it can be used in either directions and its overall shape is a circular or quasi-circular ring of radius .

On the demand side, we consider that each day, during a time period of , there are trips that use the shared mobility service, half of which in each traffic direction. The trip origin points are distributed evenly along the ring. From their origin points the trips have spatial lengths with statistical distribution that is identical from all origins. From the assumptions about the trips' origins and lengths, it follows that the destination points are also evenly distributed along the ring.

Among the population of customers, each service user has his own walk speed w and ride speed v: assumedly, these are cruising speeds over the walk and ride legs respectively. Walk speeds are statistically distributed with CDF W and ride speeds with CDF S. Statistical independence is assumed between them and also with the generation of trips.

By assumption, the service is operated under free-floating mode all along the ring. (1)

Complementarily, there is a time to get to an available scooter, denoted , with subscript A for Access. Trip planning, including booking a scooter at a given place, un-parking it at the origin and parking it at the destination, takes a transaction time of . Then, to the user the overall trip time adds up to ∶= + + .

(2)

On the supply side, there are scooters constituting the service fleet, supposedly all in operational condition. At any instant, each of them has a probability of being occupied, which means Busy for riding as well as during the access of the user that has booked it, and during the transaction operations. Thus, the trip time ART is also the resource occupation time for the scooter used for riding.

At any instant, the average number of vacant scooters, say , satisfies that = .

(1 -).

(3)

From the postulates of spatial homogeneity for demand trips, we deduce that each available scooter has its position distributed evenly along the ring, and that the respective positions of the available scooters are statistically independent.

3/ Model architecture

Among the model components, the following parts are exogenous:

• on the demand side, trip volume , trip length distribution $%&( ) with mean ' , walk speed CDF W and ride speed CDF S.

• on the supply side, fleet size , operating period , transaction time ( ,

• as well as ring radius that pertains to the territory as it is involved both with the demand and the supply of the shared mobility service.

From these exogenous conditions, the model enables us to derive the following endogenous components:

• on the demand side, ride time , access length ) and time ) , trip time ART .

• on the supply side, average number of vacant scooters and occupation probability .

The model architecture involves four sub-models:

(i) the Access model that relates ) to , and then to ) and W;

(ii) the Ride model that relates to and S;

(iii) the Occupation model that relates to ART , , and ;

(iv) the Traffic equilibrium model balances the state variable : its ensures that its value is consistent throughout the chain of influences along the previous three models. In the following Sections, we will introduce in turn the Access model, the Ride model and the Occupation model, before turning to the Traffic equilibrium model. Thus, the order of presentation matches the logical thread in Figure 1.

Fig. 1: Traffic Model Layout (adapted from Leurent, 2019a).

4/ The Access model

Let us consider a service customer that is planning his trip by looking for an available scooter (typically via a mobile app). We assume he will select the available scooter closest to his initial position, so as to minimize the walk length and walk time, which is presumably more tedious than the ride time.

Each available scooter is positioned at a point distributed evenly along the ring: thus its distance from the trip origin point is distributed uniform between 0 and * . As the available scooters are statistically independent, the access length is the minimum of i.i.d. random variables U,0, * .. Its CDF is thus, denoting F 1 (0) ≔ min50/* , 16 for 0 ≥ 0:

F 8 9 (0) ∶= Pr5 ≤ 06 = 1 -(1 -F = (0)) > . (4)
Proof. For any scooter ? ∈ 51, . . 6, the length ? from the customer origin point has CDF F 1 . The minimum ) of independent lengths so distributed satisfies that

Pr5 > 06 = Pr5 B > 0 ∶ ∀? 6 = ∏ 1 -F = (0) ?=1 = (1 -F = (0)) > .
Coming to the access time ) , from the definition of cruising walk speeds E it holds that = /E.

(5)

It can safely be assumed that ) and E are independently distributed. Then, the average access time satisfies that ̅ ∶= E, . = E, .. E,1/E..

Instance. Taking E ≈ LN(K E , L E ), then 1/E ≈ LN(-K E , L E ) and E,1/E. = exp (-K P + L E 2 /2) = exp(L P R ) /E,E.. From the properties of LN laws, exp(L P R ) = 1 + S P R with respect to the relative dispersion S P ∶= SD,E./E,E.. The relation

5/ The Ride model

So far we have defined as the trip length: the subscript R for Ride suggests that it is equivalent to the ride length. Yet the access conditions influence the effective ride lengths, say ′ , in two respects: first, depending on the direction of walking with respect to that of riding, the effective ride length will be ′ = ± . ( 7)

Second, in an even deeper way, it may occur that the Access distance be greater than the trip length. In other words, the distribution of trip lengths is shaped by service availability in space. In reality, it would not occur that < ) for a trip using the service.

Here we shall keep to the assumption of an exogenous distribution of Ride lengths, of given average ' . Neglecting the case for negative values, this is consistent with (7) as the net contribution of the ± part is null.

Coming to the ride time, from the definition of ride speeds it holds that = ′ / .

It can safely be assumed that ′ and are independently distributed. Then the average ride time satisfies that ̅ ∶= E, . = E, ′ .. E,1/ ..

6/ The Occupation model at the fleet level

Given an exogenous transaction time of T , and postulating that the scooter is booked by the user from his origin point and instant, then it is assigned to the customer during not only the ride time but also the access time and the transaction time. The total service time ART ∶= A + R + T applies to both the service user and the scooter as a resource.

At the service level, during one day of operations, the total resource occupation time amounts to ℛ = . ̅ .

To make this workload feasible in the time period , the fleet size must satisfy that . ≥ . ̅ .

Under this requirement, the proportion of occupation in resource time amounts to

∶= Y.Z ̅ [\] ^._ . ( 12
)
From our postulates of homogeneity in time and space, this proportion can be taken as the probability of occupation for any scooter at any time, in the absence of any other information (such as the particular assignment of the scooter to some user request).

7/ Model integration

We have chained up the influences between the state variables, from an exogenous number of available scooters in the Access model, to the Occupation probability in the Occupation model, passing by the formation of access time and ride time . To close the model it remains to link the variable to the occupation probability, thereby making endogenous.

From the occupation probability applied to the fleet size , on average there are . occupied vehicles. The average number of available vehicles is then = . (1 -), hence = -. ̅ / .

(13)

As ̅ stems from ' in a straightforward way, we keep its notation along with T in ̅ . As for ̅ , we put it as ̅ = ) 0 /( + 1) with `∶= * . E,1/E..

By doing so, we have assimilated an integer-valued and instantaneous involved in , with an average that is positive and real-valued. Of course it is an approximation which enables us to obtain the following characteristic equation:

= -( ̅ + Z 9 a >b= ) / . ( 14
)
This is a second-degree equation in . We restate it as follows, letting ′ ∶= -. Z ̅ RT -1 :

( + 1) = ( c + 1)( + 1) -. `/ . ( 15
)
Then, R -′ -( ′ + 1 -.

Z 9 a ) = 0 ( -′ /2) R = ′ + 1 -. Z 9 a + ( ′ /2) R * = ^e R + f g c + 1 -. Z 9 a _ + ( c /2) R for f ∈ 5-1, +16. (16)
There are two solutions to this equation:

• the high root b = ′ R + g ′ + 1 -. Z 9 a + ( ′ /2) R , • the low root h = ′ R -g ′ + 1 -. Z 9 a + ( ′ /2) R .
The high root pertains to a fluid system in which many vehicles are available, whereas the low root is associated to a congested system with few available vehicles and long access times that contribute to vehicle occupation. To the consumers, the fluid state is preferable as it provides shorter access times.

Beyond the ambiguity between the two equilibrium states, the major outcome is the "fleet sizing rule" contained in ( 14): to the service operator, the main objective of quality of service is to ensure a target access time ̂ , which is equivalent to ensure a target access distance .

This involves available scooters in average number of ∶=

8/ Conclusion

We have provided an analytical model for a shared scooter service (S3) under ring form and free-floating. Owing to postulates of homogeneity in space and time, we established simple formulas for the average access length and time, ride time, number of available vehicles and probability of occupation. Given the fleet size and the demand volume, the traffic equilibrium is characterized by a second-degree equation with respect to the number of available vehicles. Moreover, the characteristic equation constitutes a fleet sizing rule for a service operator targeting both the demand volume (a quantitative objective of service) and the access time (a qualitative objective).

The S3 traffic model is a physical and technical model. It stands as the scooter counterpart of the ring-shaped taxi service model (Leurent, 2019a) and the ring-shaped Shuttle service model C3 (Leurent, 2019b). It may represent a ring-shaped bike-sharing system as well, if operated in free-floating mode.

The economic theory of the S3 model can be developed along the same path as that for the taxi and C3 models, all the more so as the characteristic equation is very close to that of the taxi service. Yet service production for a free-floating S3 is specific as it involves charging operations and vehicle maintenance, which we did not address in detail for the other modes (since vehicle driving, be it human or robotic, enables for offline maintenance and energy refill).

Fabien

  (S3) Model with Prior Booking 3 Coming to service quality, the user spends a ride time that depends on the trip length and his own ride speed, := / .

Figure 1

 1 Figure 1 exhibits the model architecture as a graph system of components and dependences. Each model component is represented by a box, i.e. a graph node. Each straightforward influence of one model component onto another is indicated by a link between their respective nodes, with orientation according to causality. The components and links are organized by

  rule involves and ̂ in a straightforward way.

Fig. 2 .

 2 Fig. 2. Fleet size according to target access time.

April 9, 2021 Shared Scooter Service (S3) Model with Prior Booking

Appendix: a two-state Markov chain model

A shared scooter may be modeled as a stochastic system taking one out of two states A/B in alternation: state A means no current user hence Available to any newcomer, whereas state B stands for Busy, i.e. Occupied by a user. The two states communicate with each other, i.e.

April 9, 2021

Shared Scooter Service (S3) Model with Prior Booking 8 there are transitions from each state to the other one. Figure 3 depicts the two states and the stochastic transitions between them, with respective transition rates of m c and K.

.

Fig. 3. States and Transitions.

Transition rate K is the ending rate of an occupation under way. From the duration n, it is the ratio between the probability Pr5 ≤ n + on | > n6 that such occupation will end during an elementary interval ,0, on., and its incremental duration on. Making the crude approximation that the random variable of vehicule occupation, ART , is distributed exponential, then the exponential parameter is 1/ ̅ ART . Thus, the transition rate satisfies

As for the transition rate from State A (Available) to State B (Busy), it comes from the overall rate of customers arrivals per time unit, / , divided by the number of available vehicles, :

The system is in stochastic equilibrium with stationary probability distribution z ) , { | such that , } ≥ 0 and + } = 1, and the probability flow is conserved in each state:

. m c = } . K.

Put in words, the probability flow going out of State A per time unit is equal to that coming in it from State B. Substituting 1 -) for } , the balance condition becomes that . m c = (1 -)K hence

At every instant, it also holds that = / .

Substituting, the balance equation becomes an equation in :


Laurine Darcel

Louis Bornancin

Delphine Raviglione

Isabelle Bonnard

Suzanne C Mills

Julio Sáez-Vásquez

Bernard Banaigs

Nicolas Inguimbert

D-peptidase activity in a marine mollusk detoxifies a non-ribosomal cyclic lipopeptide: an ecological model to study antibiotic resistance

In the marine environment, sessile cyanobacteria have developed chemical strategies for protection against grazers. In turn, herbivores have to circumvent these defenses and in certain cases even take advantage of them as shelter from their own predators. This is the case of Stylocheilus striatus, 2 a sea hare that feeds on Anabaena torulosa, a cyanobacterium that produces toxic cyclic lipopeptides of the laxaphycin B family. Stylocheilus striatus consumes the cyanobacterium without being affected by the toxicity of its compounds, but also uses it as an invisibility cloak against predators. In this article, using different substrates analogous to laxaphycin B, we demonstrate the presence of an enzyme in the digestive gland of the mollusk that is able to biotransform laxaphycin B derivatives. The enzyme belongs to the poorly known family of Dpeptidases that are suspected to be involved in antibiotic resistance.

INTRODUCTION

Overcoming and understanding resistance to antibiotics is of major importance for human health worldwide. [START_REF] Laxminarayan | Antibiotic Resistance-the Need for Global Solutions[END_REF] Bacteria develop resistance to antibiotics through three main mechanisms: preventing the antibiotic from accessing the target, modifying the target or inactivating the antibiotic. [START_REF] Blair | Molecular Mechanisms of Antibiotic Resistance[END_REF] For example, D-peptidases are able to reengineer bacterial cell-wall which prevents antibiotics from accessing their molecular target resulting in antibiotic resistance, and -lactamases are able to hydrolyze carbapenems antibiotics destroying their activity. [START_REF] Asano | Enzymes Acting on Peptides Containing D-Amino Acid[END_REF][START_REF] Vermassen | Cell Wall Hydrolases in Bacteria: Insight on the Diversity of Cell Wall Amidases, Glycosidases and Peptidases Toward Peptidoglycan[END_REF] Recently D-peptidases have been found to act on antibiotics biosynthesized by non-ribosomal peptide synthetases (NRPS). [START_REF] Li | Resistance to Nonribosomal Peptide Antibiotics Mediated by D-Stereospecific Peptidases[END_REF] Dstereospecific resistance peptidases (DSRP) regulate the concentration of the antibiotic within the producer organism to avoid self-toxicity and are therefore closely associated with NRPS modules.

A recent genome mining study reports the presence of DSRP in a large number of bacteria. [START_REF] Li | Resistance to Nonribosomal Peptide Antibiotics Mediated by D-Stereospecific Peptidases[END_REF] For example, BogQ and TriF are DSRPs in Firmicutes (mostly Gram positive bacteria), and cleave the linear peptides bogorol and tridecaptin on the C-terminal side of D-amino acids (D-AA), but BogQ also cleaves the antibiotic bacitracin, a cyclic-non-ribosomal lipopeptide. Therefore, BogQ and TriF peptidases provide microbes with a potential of antibiotic resistance by having an enzymatic site that recognizes a minimal pattern containing D-amino acids. As such, D-peptidases might constitute a threat for the future of non-ribosomal lipopeptides used as antibiotics. However, these enzymes are poorly studied and their cleavage mechanisms are not well known. The aim of this project was to understand the specificities of this type of enzyme using a new model, a marine trophic chain. A natural model system requires the presence of an organism with the antibiotic properties in question (non-ribosomal peptides), as well as an organism that produces the resistance-bestowing enzyme. One class of natural products with promising antibiotic properties are cyclic lipopeptides (CLPs), which are among the most intriguing peptides produced by fungi and bacteria as they contain a fatty acid linked to either a D-, N-methyl, -hydroxy-ordehydro-, unusual amino acids that confer them antiparasitic, antifungal and antibacterial activities. [START_REF] Xue | Cyanobacteria-Derived Peptide Antibiotics Discovered since[END_REF][START_REF] Schneider | Cyclic Lipopeptides as Antibacterial Agents -Potent Antibiotic Activity Mediated by Intriguing Mode of Actions[END_REF] Due to these nonribosomal amino acids and the lipophilic acyl chain, CLPs are expected to show little or no susceptibility to cleavage by animal peptidases and some of these CLPs (colistin and polymyxin B) are therefore considered to be the last resort in the treatment of antibiotic resistant microbes. [START_REF] Jeannot | Resistance to Polymyxins in Gram-Negative Organisms[END_REF] Among bacteria, cyanobacteria produce a diverse array of secondary metabolites that, during blooms, are often associated with hepatotoxic and neurotoxic poisoning in humans and marine animals. [START_REF] Burja | Marine Cyanobacteria -a Prolific Source of Natural Products[END_REF]10 CLPs with biological activities on multiple targets account for the majority of secondary metabolites produced by these cyanobacteria. [START_REF] Janssen | Cyanobacterial Peptides beyond Microcystins -A Review on Co-Occurrence, Toxicity, and Challenges for Risk Assessment[END_REF] The function of these peptides in the physiology and ecology of cyanobacteria is still debated, but has been ascribed to either protection against grazing and/or allelopathy. [START_REF] Leão | The Chemical Ecology of Cyanobacteria[END_REF] The abundance of CLPs in cyanobacteria coupled with the presence of a grazing herbivore would be a novel model system providing the potential to investigate cleavage mechanisms and resistance.

The secondary metabolites of two benthic filamentous bloom-forming cyanobacteria present in French Polynesia, Lyngbya majuscula (Lm) and Anabaena torulosa (At), have been largely characterized. In both cases the major compounds are lipopeptides, cyclic hexadepsipeptides from the kulolide family [START_REF] Levert | Structures and Activities of Tiahuramides A-C, Cyclic Depsipeptides from a Tahitian Collection of the Marine Cyanobacterium Lyngbya majuscula[END_REF] in L. majuscula, and cyclic undeca-and dodeca-peptides from the laxaphycin family [START_REF] Banaigs | Marine Peptide Secondary Metabolites[END_REF] in A. torulosa. The laxaphycin secondary metabolites in A. torulosa can be classified into two types, laxaphycin A-type and laxaphycin B-type peptides, the major compounds being laxaphycin A (laxA) 1a, and laxaphycins B (laxB) 2a and B3. While laxaphycin A has no cytotoxic activity, laxaphycins B and B3 have cytotoxic effects on different cell lines, which are synergistically enhanced when laxA and laxB are combined. [START_REF] Bonnard | Total Structure and Inhibition of Tumor Cell Proliferation of Laxaphycins[END_REF] LaxB is made up of 12 amino acids with a stereochemistry alternating between L and D. This peptide contains non-proteinogenic amino acids, (3R)-β-aminodecanoic acid (Ade), (2R,3S)-hydroxyleucine (HyLeu), D-Leu, D-Asn, and N-Methyl-Ile. Laxaphycin A (laxA) is also cyclic and composed of 11 amino acids including D-AA (D-Phe, D-Leu, D-Ile) and a fatty acid (3R)-β-aminooctanoic acid (Aoc) as well as the dehydroamino acid (E-Dhb). [START_REF] Bornancin | Structure and Biological Evaluation of New Cyclic and Acyclic Laxaphycin-A Type Peptides[END_REF] Their cyclic structure, combined with the presence of D-amino acids, should make these peptides very resistant to proteolysis. [START_REF] Hamamoto | Antimicrobial Activity and Stability to Proteolysis of Small Linear Cationic Peptides with D-Amino Acid Substitutions[END_REF] An herbivorous gastropod, the sea hare Stylocheilus striatus (Ss), has been found living and feeding on both cyanobacteria in French Polynesia. [START_REF] Switzer-Dunlap | Observations on Development, Larval Growth and Metamorphosis of Four Species of Aplysiidae (Gastropoda: Opisthobranchia) in Laboratory Culture[END_REF][START_REF] Darcel | Trichormamide C Structural Confirmation through Total Synthesis and Extension to Analogs[END_REF] S. striatus, like many sea hares feeding on chemically-defended seaweeds or cyanobacteria, sequesters the whole set of lipopeptides from L. majuscula, for which no cytotoxic activity has been found, at high concentrations in its digestive gland [START_REF] Capper | The Fate of Lyngbya majuscula Toxins in Three Potential Consumers[END_REF] , while only sequesters laxaphycin A-type peptides from A. torulosa. Interestingly, S.

striatus is also able to biotransform diet-derived compounds into less repellent molecules. [START_REF] Pennings | Secondary Metabolites of the Cyanobacterium Microcoleus Lyngbyaceus and the Sea Hare Stylocheilus longicauda: Palatability and Toxicity[END_REF] Indeed, S. striatus biotransforms laxaphycin B-type peptides from A. torulosa into non-toxic acyclic compounds. These biotransformed compounds were characterized as two acyclic laxaphycin B-type peptides coming from the parent cyclic molecule laxB. [START_REF] Bornancin | Isolation and Synthesis of Laxaphycin B-Type Peptides: A Case Study and Clues to Their Biosynthesis[END_REF][START_REF] Alvariño | Biological Activities of Cyclic and Acyclic B-Type Laxaphycins in SH-SY5Y Human Neuroblastoma Cells[END_REF] Cyclic lipopeptides are relatively widespread in cyanobacteria, but biotransformation involving the opening of the ring and deletion of aminoacids, has never previously been described. We aimed to identify the mechanism that S. striatus set up to detoxify laxaphycin B-type peptides as an adaptation to feed on A. torulosa without suffering adverse effects. This project examines the process of enzymatic detoxification of laxB in S. striatus. We report a comprehensive study of the fate of laxB and its synthetic analogues exposed to the molluscan digestive gland in order to describe the enzymatic mechanism performed by an unknown enzyme of the D-peptidase family. Finally, we test the capacity of this new D-peptidase to inactivate four known antibiotics.

RESULTS AND DISCUSSION

The study of the cyanobacterium Anabaena torulosa harvested during a bloom in Moorea in French Polynesia, revealed the presence of acyclolaxaphycin B (acyclolaxB) derived from the toxic laxB (Figure 1A). AcyclolaxB is open between (2R,3S)-HyLeu in position 3 and L-alanine in position 4 (Figure 1B). [START_REF] Bornancin | Isolation and Synthesis of Laxaphycin B-Type Peptides: A Case Study and Clues to Their Biosynthesis[END_REF] As the starting point of NRPS biosynthesis of laxB is Ade 1 and elongation continues to the C-terminal Thr [START_REF] Leão | The Chemical Ecology of Cyanobacteria[END_REF] with the final cyclization mediated by a thioesterase, [START_REF] Heinilä | Shared PKS Module in Biosynthesis of Synergistic Laxaphycins[END_REF] it is unlikely that the acyclolaxaphycin is the result of a malfunction of the NRPS, but more likely results from a biotransformation process of laxB by external agents. LC-MS analysis of the digestive tract of S. striatus showed that acyclolaxB had lost Ala 4 and (2R,3S)-HyLeu 5 confirming a biotransformation process [START_REF] Alvariño | Biological Activities of Cyclic and Acyclic B-Type Laxaphycins in SH-SY5Y Human Neuroblastoma Cells[END_REF] (Figure 1D), while the non-toxic laxA 1a was bioaccumulated in the same digestive gland (Dg), but not degraded or biotransformed. Subjecting laxB to extracts of the sea hare's digestive gland highlighted that the transformation is a two-steps process beginning with the opening of the macrocycle accompanied with a mass increase of 18 m/z, followed by the deletion of Ala 4 and (2R,3S)-HyLeu 5 and a loss in mass of 200 m/z. Hereafter we will refer to the peptides using a number and a letter corresponding to the initial compound and the stage along the cleavage process, respectively. For example, compound 2a is the cyclic laxB, compound 2b is the first intermediate after an increase in mass of 18 m/z and 2c is the final stage of the biotransformation process after a loss in mass of 200 m/z (Table S1a-b). We hypothesized that the detoxification mechanism involved an enzyme targeting the D-amino acid in positions 3 and 5 of laxB. However, from this analysis it was difficult to determine if the first cleavage occurred at the C-ter of the (2R,3S)-HyLeu in position 3 resulting in the already known acyclolaxB 2d or in position 5 producing compound 2b (Figure 1C). To examine the transformation process of laxB over time we used S. striatus collected from a bloom of L. majuscula in Moorea. Unlike A. torulosa, L. majuscula does not produce laxaphycins and thus S. striatus will not be contaminated by acyclic laxaphycins, simplifying the monitoring of laxB (2a) transformation. In order to ensure that S. striatus taken from L. majuscula has the capacity to transform 2a, individual S. striatus were collected from, and fed on, L. majuscula. All individuals were dissected and their different organs analyzed. As expected, LC-MS analyses detected acyclic laxaphycin B 2c within the digestive glands of S. striatus collected from A. torulosa (Dg-Ss-At), but not within the digestive glands of S. striatus collected from L. majuscula (Dg-Ss-Lm) (Figure S17). 2a is thus detoxified within Dg-Ss-At to give the non-toxic acyclic laxaphycin B 2c. [START_REF] Alvariño | Biological Activities of Cyclic and Acyclic B-Type Laxaphycins in SH-SY5Y Human Neuroblastoma Cells[END_REF] Furthermore, adding 2a to digestive gland extracts of S. striatus collected from L. majuscula confirms that S. striatus does have the capacity to cleave 2a given that we observed the decrease of 2a to the benefit of acyclic laxaphycin B 2c by LC-MS (Figures S16B-S18). These results were reproduced using different batches of digestive glands from different individuals whose proteins levels were kept constant during each experiment via quantification using the Bradford method. [START_REF] Bradford | A Rapid and Sensitive Method for the Quantitation of Microgram Quantities of Protein Utilizing the Principle of Protein-Dye Binding[END_REF] To better characterize this enzyme, we hereafter used digestive gland extracts of S. striatus fed on L. majuscula (Dg-Ss-Lm) having confirmed its capacity to cleave 2a.

As a prerequisite of this study, we verified that laxaphycins 1a and 2a do not show any intrinsic susceptibility to cleave when exposed to protease or rat serum even though their cyclic structures and the presence of non-ribosomal amino acids should prevent their cleavage. Both peptides remained stable in Tris buffer at pH 8 when exposed to rat serum at a protein concentration of 10 mg/mL for 24 hours (Figure S19). To complete this study, compound 2a was tested against four enzymes with broad substrate specificities: Pepsin, Elastase, Thermolysin (TLN), and Subtilisin (Table S3). Only TLN at pH 8 and 75°C resulted in the linearization of laxB 2a, but differed from that observed in S. striatus, as cleavage occurred at the C-terminus of proline 10 and the hydrolysis kinetics were very different. While laxB was almost completely linearized after 30 minutes in the presence of digestive gland extracts, only 40% of laxB was consumed after 24 hours by TLN (Figure S18 and Figures S21-22). Further inspection of the enzyme highlighted that the biotransformation of 2a was inactivated if the digestive gland extracts from S. striatus (Dg-Ss-Lm) were denatured at 90°C for 5 minutes. This result reveals that cleavage involves a heat-sensitive protein similar to the enzymes (Figure S23). It is noteworthy that a 70 M solution of 2a in buffer at pH 8 does not degrade at 90°C. Moreover, we showed that linearization of 2a occurred with cleavage at the C-terminal position of the two HyLeu and was repeatable over 21 batches of digestive gland extracts obtained from 11 S. striatus. As previously reported, 2a is the archetype of a compound family that includes dozens of analogues slightly differing at the sequence level. [START_REF] Bornancin | Isolation and Synthesis of Laxaphycin B-Type Peptides: A Case Study and Clues to Their Biosynthesis[END_REF] In order to define if the observed cleavage is restricted to 2a, we used isolated natural laxB2 22 3a, synthesized trichormamide C 4a and its analogues 5a-6a to explore the importance of the nature of the amino acids at the cleavage positions 3 and 5, and also to examine the role of (2R,3R)-HyAsn in position 8, as this amino acid is replaced by a D-Asn in 4a-6a (Figure 2 -26). Following this observation, we used compounds 5a and 6a that might be considered as 3a and 4a hybrids. These fully synthetic compounds 5a and 6a have two D-Leu or two D-Thr respectively, instead of the two (2R,3S)-HyLeu present in 2a and 4a. For both compounds we observed similar cleavage at the C-ter of the D-Leu or at the D-Thr to give 5c and 6c, respectively (Figure 3, Figures S27-28).

Thus, 5a and 6a are cleaved at the same location as 2a and 4a despite the modification of the amino acids at the cleavage site. Furthermore, we observed that the cleavage rate of 2a, 3a, 4a and 5a was similar during the first few hours and 90% or more of the substrate was consumed within four hours (Figure 3). For 6a the macrocycle opening was slightly slower than the others with as much as 25% of 6a remaining 8 hours after the beginning of the reaction, while a comparable amount of cleavage occurred for the other compounds in less than three hours (Figure 3). The peptides 4a-6a confirmed that the enzymatic cleavage is a two-step process that deletes the amino acids in positions 4 and 5 of the macrocycle, but defining the location of the first cleavage point using MS-MS was not straightforward due to the observed dehydration of Thr or (2R,3S)-HyLeu that complicated the interpretation of the mass spectra as already reported [START_REF] Gaillard | Towards the Total Synthesis of Trichormamide A, a Cyclic Undecapeptide[END_REF] (Figures S36-S40). To determine the order of the two successive cleavages we focused on compound 5a to avoid synthesizing hydroxyleucines and hydroxyasparagine contained in 2a, as these amino acids are not commercially available. However, stereochemistry was respected by using D-leucines and D-asparagine. From 5a, we produced two linear peptides corresponding to the two possible cleavage points (steps 1' and 2' in path A or steps 1 and 2 in path B; Figure 4). Compound 5b is a linear analogue of 5a that is disconnected at the C-ter of D-Leu 5 . Compound 5d refers to the open compound 5a at the C-ter of D-Leu 3 . These two candidate peptides allowed us to determine the first cleavage site and subsequently the two-step enzymatic reaction pathway that produces compound 5c. It is worth noting that when both candidates 5b and 5d were exposed to digestive gland extracts, they were cleaved and produced compound 5c after deletion of compound 5e (Figures S29-30). Optimization of HPLC conditions enabled us to differentiate between peptides 5b and 5d through their retention times of 13.0 and 13.3 min respectively which correlated to their peak mass of m/z 1365.6 (Figure 4B). Subsequently, separation of both peaks remained when coinjected (Figure 4B). Based on these observations, a solution containing compound 5a was exposed to digestive gland extracts and LC-MS revealed that only the peak corresponding to 5b along with the final product 5c were observed (Figure 4C,solution B). Mixing solution B with solution A containing compounds 5b and 5d in equivalent amounts confirmed that only compound 5b was formed during the enzymatic process (Figure 4C). Thus, our test of the enzymatic processing of compound 5a provided evidence supporting path B that the ring is first cleaved at the C-ter of the amino acid in position 5 delivering compound 5b (Figure 4A Intrigued by the fact that linear compounds 5b and 5d were substrates of the enzyme, we synthesized compound 7a that corresponds to a linear analogue of 5a in which the Ade has been replaced by a decanoic acid at the N-terminus. Despite a linear structure, the peptide was still cleaved at the same location as its cyclic analogue (Figure S31) indicating that 7a manages to structure itself in order to be recognized by the enzyme as its cyclic analogue. Furthermore, compound 7a enabled us to differentiate between the fragments by mass spectrometry and to confirm the order of the two-step cleavage process (Figure 5 and Figure S41). The two cleavage studies of 5a and 7a demonstrate that 2a and its cyclic analogues (3a, 4a and 6a) are cleaved in the same way, according to path B (Figure 4A). The discovery of acyclolaxB 2d in Anabaena torulosa (Figure 1B) suggests that cleavage of 2a would produce the intermediates 2d then 2c, however, they are in fact 2b then 2c (Figure 6). The origin of acyclolaxaphycin B 2d is still unknown to date. Given the length of Ade 1 's carbon chain, this amino acid could play a crucial role in the enzyme's ability to recognize the substrate. We therefore replaced Ade 1 with -Alanine and synthesized compound 8a. This peptide was not cleaved by digestive gland extracts (Dg-Ss-Lm), demonstrating that the enzyme requires Ade 1 's long carbon chain for insertion of the peptide into the enzyme active site (Figure S32). Stereochemistry can also impact the enzyme's ability to recognize the substrate. 2a's structure is particular with an alternation of L-and D-amino acids and is cleaved at the C-terminal end of D-amino acids (D-Thr, D-Leu and (2R,3S)-HyLeu). We therefore synthesized compound 9a, an analogue of 5a, which contained two L-Leu instead of the two D-Leu at the cleavage site (Figure 7). This peptide was not cleaved by digestive gland extracts (Dg-Ss-Lm), emphasizing the importance of amino acid stereochemistry at the enzyme's recognition site (Figure S33). To reinforce our findings, we replaced only one D-Leu with a L-Leu. Knowing that 7a is recognized by the enzyme although it is a linear peptide, and that it is cleaved at the C-ter of the two D-Leu starting with D-Leu 5 then D-Leu 3 , we synthesized the same peptide sequence by replacing D-Leu in position 3 by L-Leu, while keeping D-Leu in position 5, resulting in compound 10a. LC-MS analysis showed that the peptide was cleaved at the C-ter of D-Leu 5 but no longer in position 3, where L-Leu was present (Figure 8 and Figure S34). Taken together, our results confirm that a D-peptidase within the digestive gland of S. striatus acts on cyclic lipopeptides in the laxaphycin B-type peptide family, but also on synthetic linear analogues provided that they contain D-leucine like amino acids with suitable surroundings. Indeed, the D-leucine in position 11 does not constitute a preferred cleavage site. D-peptidases are attracting increasing interest as they may be involved in the resistance of bacteria to antibiotics if transferred to pathogenic bacteria. [START_REF] Li | Resistance to Nonribosomal Peptide Antibiotics Mediated by D-Stereospecific Peptidases[END_REF] With regard to this, we tested the stability of four antibiotics, the vancomycin glycopeptide, the CLPS daptomycin, bacitracin and colistin all containing Damino acids as well as a cyclic structure like laxaphycins, against these same digestive gland extracts from S. striatus. None of these four peptides were cleaved in contact with the digestive gland extracts of the mollusk (Figure S35). This result shows that the specificity of the investigated D-peptidase is restricted to the laxB family and that the D, L alternating stereochemistry observed may be an important prerequisite for the substrate-enzyme association.

CONCLUSION

The stability of laxaphycin B was demonstrated in buffers at pH 3, pH 5 and pH 8, as well as at temperatures between 30°C and 90°C. LaxA (1a) was bioaccumulated in the digestive gland of S. striatus, while laxB (2a) was recovered as an acyclic laxB despite the fact that 2a is stable in a complex medium such as rat serum, as well as against known isolated enzymes. As the biotransformation of 2a in the digestive tract of S. striatus was the same regardless of whether S. striatus had been reared on At or Lm, we can confirm the hypothesis that the enzyme is either produced within the mollusk itself or recovered by the latter from its environment. 2a is cleaved in two steps, by a first C-terminal opening of a HyLeu and then by the loss of 2 amino acids with a C-terminal cleavage of the second HyLeu. The structure-activity relationship (SAR) study with different cyclic analogues of 2a showed that the side chain size of amino acids 3 or 5 impact enzyme recognition by affecting some of the kinetics of the cleavage. However, suppression of the hydroxy function on these amino acids does not significantly affect hydrolysis rate. On the other hand, the Ade in position 1 is crucial in CLP recognition by the enzyme as its absence precludes association with the enzyme. More importantly, the enzyme involved in the cleavage of the compounds described in this study is part of the little studied D-stereospecific peptidase for which only few examples have been previously reported. However, recently Li et al. ( 2018) identified 403 putative D-stereospecific resistance peptidases (DSRP) in the Bacillales order and found a strong association between these peptidases and the non-ribosomal peptide biosynthetic gene cluster. [START_REF] Li | Resistance to Nonribosomal Peptide Antibiotics Mediated by D-Stereospecific Peptidases[END_REF] These DSRPs cleave peptides at the C-terminal side of D-cationic amino acids, but in the present case cleavage occurs at the C-ter of D-HyLeu (2a, 3a, 4a), D-Leu (3a, 5a, 7a, 10a) and D-Thr (6a) thus highlighting a different and yet unreported specificity. We thus provide evidence of a new D-peptidase acting on CLPs that extends our knowledge of these little studied enzymes. Dpeptidases have only been reported in the Bacillales order to date, but they raise the question of their potential horizontal gene transfer to other pathogenic bacterial strains that might impact the development of CLP antibiotics. This study showed that this enzyme had no impact on three CLP known antibiotics. Furthermore, as all known D-peptidases are of bacterial origin we hypothesize that the soluble enzyme found in the digestive gland of S. striatus originates from bacteria associated with the intestinal microbiome of S. striatus. This study revealed that S. striatus contains, and potentially also concentrates, bacteria producing enzymes with unexpected specificity against laxB, transforming it into a less toxic linearized compound. Further examination of the microbiome associated with the molluscan digestive gland, as well as the chemistry of cyanobacteria surfaces, could provide new information that will be examined in the near future.

Simplified analogues of laxB provided us with more information concerning the specificity of this enzyme and will serve as a basis for the creation of new peptides which, by photo-crosslinking, will allow us to recover the enzyme more efficiently.

EXPERIMENTAL SECTION

Linear peptides were synthesized with an automated microwave peptide synthesizer (CEM Liberty One). The synthesis was performed at 50 °C under microwaves (25 W) and at 0.1 mmol scale with PyOxim (4.9 equiv)/DIEA (10 equiv) as coupling reagents. 20% piperidine in DMF were used for deprotection steps. Depending on the peptide to be synthesized, either Rink Amide resin (0.67 mmol/g) or 2-chlorotrityl chloride resin (1.6 mmol/g-Cl) preloaded with the first amino acid was used. For each amino acid the standard coupling cycle was as follows: after Fmoc deprotection of the amino acid supported by the resin, 2.5 mL of the requested amino acid at a concentration of 0.2 M in DMF was added to the resin, followed by 1 mL of PyOxim in DMF at 0.49 M and lastly by 0.5 mL 2M DIEA in NMP. The coupling of all amino acids was performed for 20 minutes except for difficult couplings which were carried out 2 or 3 times such as Fmoc-L-Gln(Trt)-OH that was coupled three times for 20 minutes, followed by capping with a solution of 100 mL of DMF, 5 mL of anhydride acetic (0.5 M, 1 equiv), 2 mL of DIEA (0.21 equiv) and 135 mg of HOBt (0.019 equiv) for 3 minutes. The Fmoc-group was deprotected by adding 20% piperidine solution in DMF for 3 minutes. At the end of the synthesis, the resin was washed three times with DMF and three times with DCM and then was dried under vacuum.

In the case of the linear peptides 5b, 5d, 7a and 10a a total cleavage was done using a solution of TFA/TIS/H2O 95:2.5:2.5 (v/v) under agitation over 2 hours. The resin was then filtered and the filtrate was concentrated in vacuo with cyclohexane as a co-solvent. Peptides were precipitated in ice-cold diethyl ether and freeze-dried. Peptides were then purified by semi-preparative HPLC.

In the case of cyclic peptides 8a and 9a, a cleavage of the protected peptide from the resin was carried out using a solution of 20% TFE in DCM under agitation for 2 hours. The resin was then filtered and the filtrate was concentrated in vacuo with cyclohexane as a co-solvent. The peptide was then freeze-dried but not purified. The linear peptide (45 mol) was dissolved in DMF (4.5 mL) into a syringe. EDC (3 equiv) was dissolved in the same amount of DMF (4.5 mL) into another syringe. OxymaPure (3 equiv) was dissolved in 4.5 mL of DMF into a three-neck round-bottom flask purged under nitrogen atmosphere. The two syringes were put on both sides of the flask and both solutions were added under a nitrogen atmosphere at a rate of 0.01 mL/min. Once the addition was complete, the mixture was stirred for 48 hours under a nitrogen atmosphere. DMF was evaporated using Genevac (T=36°C, Medium Boiling Point) over 3 hours and the resulting sediments were dissolved with 10 mL of ethyl acetate. The organic layer was washed three times with citric acid (1M), three times with NaHCO3 (1M) and three times with brine in order to separate the cyclic peptide from any potential remaining linear ones. The organic layer was dried over magnesium sulfate and then concentrated in vacuo. To allow side-chain deprotection, the resulting solid was mixed with a solution of TFA/TIS/H2O 95:2.5:2.5 (v/v) over 2 hours. TFA was evaporated under vacuum and the peptide was precipitated using ice-cold diethyl ether. The peptide was then purified by semi-preparative HPLC.

Syntheses of laxaphycin B, trichormamide C (compound 4a) and its two cyclic analogs 5a and 6a have been previously published. [START_REF] Darcel | Trichormamide C Structural Confirmation through Total Synthesis and Extension to Analogs[END_REF][START_REF] Boyaud | First Total Synthesis and Stereochemical Revision of Laxaphycin B and Its Extension to Lyngbyacyclamide A[END_REF] For LC-MS profiles, as well as the exact masses of peptides 5b, 5d, 7a, 8a, 9a and 10a, see Figures S4 to S9.

As the peptides do not have chromophores to visualize them by HPLC coupled with UV detection, their purity were estimated by LC-MS analysis. As purity was estimated from the detected peaks of the mass spectra, we cannot exclude that purity was overestimated due to the presence of trace compounds associated with the main peak. Thus the reported purities (Table S2) should be considered to be qualitative rather than quantitative. Moreover, if impurities are present, they do not impact the biotransformation process which was the main aim of the study. Indeed, it is noteworthy that no associated impurities were detected by NMR. Thus analyses of the peptides by LC-MS and NMR confirmed that the purity of the peptides was higher than 95%.

Two buffer solutions were prepared and sterilized by autoclave: a pH 8 buffer (50 mM Tris, pH adjusted with HCl 1M) and a pH 3 buffer (citric acid 0.1 M, sodium citrate 0.1 M, pH adjusted with NaOH 1M). Stock solutions of peptides were prepared at 10 mg/mL in DMSO. These solutions were diluted 10 times in buffer pH 3 and pH 8. Peptide solutions at 1 mg/mL (10% DMSO in buffer) were diluted 10 times with the same buffer used for previous dilutions resulting in peptides at 0.1 mg/mL (1% DMSO in buffer) in both buffers. Solutions were incubated under agitation (different temperatures were tested to fit with enzyme specificities, see supporting information). For each kinetic point, the same procedure was applied: solutions were centrifuged for a few seconds, then part of the solution was removed to be quenched by 90% MeOH, resulting in 0.01 mg/mL peptide solutions (DMSO/buffer/MeOH, 0.1:9.9:90, v/v). The quenched solutions were centrifuged at 21,952 x g for 20 minutes at 4°C. The maximum amount of supernatant was recovered in a LC-MS vial for analysis. All tests were performed in triplicate.

A pH 8 buffer was prepared and sterilized by autoclave (50 mM Tris, pH adjusted with HCl 1M). Stock solutions of peptides were prepared at 10 mg/mL in DMSO. These solutions were diluted 10 times in buffer pH 8 to give peptide solutions at 1 mg/mL (10% DMSO in buffer). These solutions (1 mg/mL) were mixed with Dg-Ss-Lm extracts (10 mg/mL) or rat serum (between 60 and 80 mg/mL) and completed with the same buffer resulting in peptides at 0.1 mg/mL (1% DMSO in buffer) and extracts at 1 mg/mL (concentration varying between 0.4 and 1 mg/mL depending on the extracts) or rat serum around 10 mg/mL. Solutions were incubated at 30°C under agitation.

For each kinetic point, the same procedure was applied: solutions were centrifuged for a few seconds, then part of the solution was removed to be quenched by 90% MeOH, obtaining peptide solutions at 0.01 mg/mL (DMSO/buffer/MeOH, 0.1:9.9:90, v/v). The quenched solutions were centrifuged at 21,952 x g for 20 minutes at 4°C. The maximum amount of supernatant was recovered in a LC-MS vial for analysis. All the tests were carried out in triplicate on the same extract and in several replicates with other extracts.

Adult specimens of Stylocheilus striatus were collected from either the lagoon of Moorea Island (Society Archipelago, French Polynesia) or from populations residing in flow-through aquaria at the University of California Gump Field Research Station situated in Moorea. Specimens obtained from the lagoon were collected at depths of 1-4 m within large cyanobacterial blooms of either Lyngbya majuscula or Anabaena torulosa on sandy substrates. Animals were transferred in cool boxes within 3 hours of collection into outdoor, flow-through aquaria (40 L) supplied with oxygenated running seawater (0.5 L/min) at CRIOBE. Sea hares were starved for 48 hours prior to dissection to ensure that all food items had been digested and excreted.

Opisthobranches were dissected following cold anesthesia at 4 °C for 20 minutes. A shallow incision was made through the mantle, ventrally from the head to tail. The mantle was removed to expose all internal organs (Figure S1A). The internal organs were then dissected to expose the mouth and buccal mass, gizzard, digestive gland, ovo-testis, hermaphroditic duct, and mucus and albumin gland (Figure S1B). Each body segment was placed individually into labeled 1.5 mL Eppendorfs and immediately frozen and stored at -20 °C. Ethical approval for the study was granted from The Animal Ethics Committee, Centre National de la Recherche Scientifique (permit number 006725).

Dissected digestive glands were stored in Eppendorf tubes and immersed in liquid nitrogen.

Eppendorf tubes were then placed in a Silamat S6 mill (from Ivoclar vivadent) with 8 glass beads.

4 minimum cycles of alternation between liquid nitrogen and grinding were chained. After several cycles of 8 seconds, the whole sample was completely ground. The buffer (50 mM Tris, pH 8) was added and then solutions were mixed by vortexing. Mixtures were centrifuged at 4°C for 20 minutes at 21,952 x g. The supernatants of the centrifuged solutions were recovered and placed in aliquots. Solutions were stored at 25°C. Purifications were carried out using a HPLC from Waters, Waters 1525 chromatography system fitted with a Waters 2487 tunable absorbance detector with detection at 214 nm and 254 nm. The eluents used for purification were ACN (0.1% formic acid) and H2O (0.1% formic acid). The column used was a GRACE Vydac C-18 column (250x10 mm, 5 m) at a flow rate of 3 mL/min. LC-MS analyses were carried out with a Thermo Fisher Scientific LC-MS device, Accela HPLC coupled to a LCQ Fleet fitted with an electrospray ionization source and a 3D ion-trap analyzer.

The column used was a Phenomenex BioZen™ 2.6 µm Peptide XB-C18 (LC Column 50 x 2.1 mm) and the gradient ran from 20% to 90% of ACN (0.1 % formic acid) in H2O (0.1 % formic acid) during 6 min at a flow rate of 0.5 mL/min for a 10 L injection. The LC-MS data were acquired on the XCalibur software from ThermoFisher. Once the chromatograms were obtained, ion extractions were carried out for each peptide or fragment. Areas were recovered on the peaks of these ion extractions.

Figure 1 .

 1 Figure 1. A. Structure of laxB (2a) isolated from the cyanobacterium Anabaena torulosa. B.

  and FiguresS25-28).[START_REF] Darcel | Trichormamide C Structural Confirmation through Total Synthesis and Extension to Analogs[END_REF]

Figure 2 .

 2 Figure 2. Structure of 2a and its cyclic analogues 3a, 4a, 5a and 6a.

Figure 3 .

 3 Figure 3. Cleavage rate of laxaphycin-B type peptides 2a-6a, compared to that of laxaphycin A

  , step 1 in red) and then cleaved at the C-ter of the amino acid in position 3 to form 5c (Figure 4A, step 2 in red).

Figure 4 .

 4 Figure 4. Study of the two possible enzymatic cleavage paths of compound 5a which leads to the

Figure 5 .

 5 Figure 5. Study of the cleavage path of 7a. A. Successive cleavage observed by LC-MS for

Figure 6 .

 6 Figure 6. Cleavage path of 2a determined following the studies on 5a and 7a.

Figure 7 .

 7 Figure 7. Structures of non-cleaved compounds 8a and 9a compared to 5a.

Figure 8 .

 8 Figure 8. Study of the cleavage path of 10a. A. Cleavage observed by LC-MS for compound 10a.

peptidases; EDC, 1-ethyl-3-(3-dimethylaminopropyl)carbodiimide; HCl, hydrochloric acid; HOBt, hydroxybenzotriazole; HyAsn, hydroxyasparagine; HyLeu, hydroxyleucine; lax, laxaphycin; Lm, Lyngbya majuscula; MeOH, methanol; NaHCO3, sodium bicarbonate; NRPS, Non-ribosomal peptide synthetases; Ss, Stylocheilus striatus; TFE, trifluoroethanol; TIS, triisopropylsilane; TLN, Thermolysin; W, watt

High resolution mass spectra were recorded through direct infusion on a ThermoFisher Q Exactive Plus spectrometer.

NMR spectra were acquired on a JEOL ECZ 500 spectrometer and were treated on Delta software from JEOL.

ASSOCIATED CONTENT

Supporting Information

The following files are available free of charge.

 Molecular formula strings "SMILES"

 Structures of all the compounds mentioned in this manuscript, experimental procedures for enzymatic cleavage of peptides and mollusk dissection, LC-MS parameters, LC-HRMS


Fabin Castaño
email: fabian.castano@upb.edu.co

Marc Sevaux
email: marc.evaux@univ-ubs.fr

Combining metaheuristics with column generation: successful approaches to enhance column generation algorithms performance

Keywords: Column generation, Metaheuristics, Matheuristics

Column generation algorithms are typically adopted to address mathematical programming problems defined over a huge number of variables. This approach suffers, however, from several problems that might limit its usability. In this work some of these problems are discussed along with several strategies that take advantage of the use of (meta-)heuristics to help improve the methods performance and reduce the computational effort required to compute an optimal solution. In this work the benefits of using metaheuristic strategies within CG are discussed from the viewpoint of the way they, indirectly, address some of the causes leading to a poor performance. These different methods are tested by solving the maximum network lifetime problem in wireless sensor networks for which a model that naturally leads to column generation is considered. Experimental results show how the use of metaheuristics can generate large improvements on the performance of the basic column generation framework.

Introduction

Column generation (CG) is an efficient method used to solve large scale linear programming problems that has been largely exploited to reduce the computational effort required to solve them [START_REF] Adelman | Dynamic bid prices in revenue management[END_REF][START_REF] Maher | Solving the integrated airline recovery problem using columnand-row generation[END_REF][START_REF] Castaño | A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints[END_REF]. CG essentially divides a problem in two namely a restricted master problem (RMP), and a pricing subproblem (PS). RMP represents the original problem formulated over a reduced part of the solution space expressed by a subset of columns (variables). Then, the PS is used to identify additional columns that, when added to RMP, can help to further improve the objective function of RMP.

CG is an iterative method that gradually enlarges the search space by adding new variables, not considered before, that contribute to improve the objective function for RMP. RMP is initialized with a reduced set of variables that generate an initial solution for the problem and sequentially adds new variables based on the reduced cost criterion. These new unknown columns are generated at every new iteration by using any possible method useful to solve PS, which considers the constraints that are not directly considered when solving RMP. RMP is first solved, and the dual variable values associated to the optimal solutions are used to build the objective function for PS (the reduced cost criterion). PS is then solved to check whether or not it exists a new profitable column useful to improve the objective function. If a new column is available, it is added to RMP and a new iteration is carried out; otherwise, the algorithm finishes. When the method used to solve PS can guarantee that not additional interesting columns exists, the solution to RMP is guaranteed to be optimal (at least for the linear relaxation).

Nowadays, it is widely accepted that by combining CG with metaheuristic approaches, the former method might be seriously boosted. As it could be expected, this is partially a consequence of the efficiency achieved by metaheuristics while solving the difficult optimization problems corresponding to the PS. Nonetheless, as it is shown in this work, it is also a consequence of collateral effects associated to the way metaheuristics are implemented and embedded within CG that directly tackles the causes of slow convergence. In this work, the design of metaheuristics to be embedded within CG is analyzed , and several and well known approaches used to help accelerate CG are discussed to demonstrate how CG can benefit from the characteristics and flexibility offered by metaheuristic solution approaches. Several simple ideas that can be considered when designing a CG framework for solving computationally difficult problems are evaluated through extensive computational tests that show the interest of using such approaches.

Metaheuristics and Column Generation

Pure CG approaches might suffer from several pathological issues that affect its performance (see for example: [START_REF] Rossi | Column generation algorithm for sensor coverage scheduling under bandwidth constraints[END_REF][START_REF] Castaño | A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints[END_REF]). Consequently, the use of strategies to cope with such problems is not only desirable but might be necessary. Several causes have been identified. In first place, CG demands to solve a PS at every single iteration what might cause troubles when it corresponds to a difficult optimization problem. Additionally, CG may present some issues that are inherent to the approach. One of the most typical problems corresponds to convergence, meaning that while in the first iterations the evolution of the objective function is fast, in the latter iterations these improvements may be marginal and may be reflected in a large number of iterations required to fully solve the problem (tail-off effect) [START_REF] Gilmore | A linear programming approach to the cutting-stock problem[END_REF][START_REF] Gilmore | A linear programming approach to the cutting stock problem-part ii[END_REF]. A different problem corresponds to the heading-in effect, which can be explained as the successive enumeration of irrelevant columns, that are unlikely to be part of the optimal solution. This phenomenon often appears throughout the first iterations of CG, while not enough information is available to produce interesting columns, and can affect heavily its performance [START_REF] Vanderbeck | Implementing mixed integer column generation[END_REF].

To cope with the aforementioned problems, several strategies have been successfully applied that mostly attack the problem from the viewpoint of the dual problem [START_REF] Marsten | The boxstep method for large-scale optimization[END_REF][START_REF] Neame | Nonsmooth dual methods in integer programming phd thesisdepartment of mathematics and statistics[END_REF][START_REF] Du Merle | Stabilized column generation[END_REF]. Nonetheless, it is remarkable to see that CG obtain major benefits when it is combined with metaheuristic approaches. In the latter case, it is typical to see that the basic structure of metaheuristics helps to improve CG performance compared to other exact approaches. Although, nowadays, MIP solvers are in a development state in which they are competitive against fast (meta-)heuristics in terms of the computational time required to solve difficult problems, the use of metaheuristics continues to be profitable as it seems they bring more reductions on the time required for solving problems when embedded in CG than its exact counterpart.

When using metaheuristics within a CG framework, three main approaches can be used to help accelerate the convergence towards the optimal solution:

-Intensification strategies An intensification strategy consists on returning to the RMP several interesting columns found through PS to the RMP at each iteration of CG [START_REF] Desrochers | A new optimization algorithm for the vehicle routing problem with time windows[END_REF][START_REF] Macambira | Integer programming models for the sonet ring assignment problem[END_REF]. This strategy usually leads to a reduction in the number of iterations required for solving CG to achieve the optimal solution [START_REF] Moungla | Solutions diversification in a column generation algorithm[END_REF]. If a population based or trajectory based metaheuristic approach is used to solve PS, all the columns found during the optimization process might be saved to be added to the columns pool. The number of added columns might be limited to only κ columns such that the problem size is kept under control without losing the benefits offered by the intensification strategy. -Diversification strategies Diversification strategies expand the idea of intensification. The purpose in this case is to compute at each iteration of CG an interesting set of columns contributing to different constraints [START_REF] Moungla | Solutions diversification in a column generation algorithm[END_REF]. This strategy might be powered if a metaheuristic approach used to solve PS is available that computes several columns simultaneously and offers naturally methods to increase diversity, e.g genetic algorithms, GRASP, etc. -Sequential application of metaheuristics and exact approaches In this latter case, the idea is to exploit the easiness of the process of finding new profitable columns during the first iterations of CG. In this way, it is possible to compute columns that are easy to find with not-very-strong metaheuristics that can be sequentially replaced with more sophisticated metaheuristics or exact approaches when it becomes necessary while the CG solution process evolves [START_REF] Castaño | A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints[END_REF]. Finally, once the solution process evolves enough, metaheuristics might be even replaced for exact approaches so as to confirm whether or not the current solution for RMP is optimal.

Results and discussion

Building an efficient column generation approach to solve a difficult optimization problem is a hard task. Furthermore, solving the pricing subproblem remains a complex task that often requires developing efficient specialized approaches to face it. The methods previously mentioned are tested for solving the Maximum Network Lifetime Problem in Wireless Sensor Networks with Coverage Constraints (α-MLP) [START_REF] Gentili | α-coverage to extend network lifetime on wireless sensor networks[END_REF]. For this problem, a pretty simple model based on an exponential number of variables is available. To solve the problem, an approach based on CG is proposed for which the three aforementioned approaches are adopted through the use of diverse metaheuristic approaches, e.g. Evolutionary algorithms, GRASP, VNS. As shown in Figure 1 and 2 by applying the mentioned approaches, CG can be boosted compared to its basic implementation (CG-Exact). The experimental results show the benefits obtained for each of the presented methods and seem to indicate that, although not directly intended, the previously discussed strategies help to address the causes of slow convergence, e.g. the unstable behavior of dual variables values [START_REF] Marsten | The boxstep method for large-scale optimization[END_REF], diminishing the tail-off and heading-in effects. To help accelerate CG, it can be possible to combine CG with solution approaches that exploit several metaheuristics offering different performances both, in terms of the quality of the solution and in terms of the computational effort required for each. Furthermore, when these are used to return multiple and diverse columns, the number of iterations required to solve the problem might be heavily reduced while keeping CG being an exact method.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Euclidean distance of dual variables to their optimal values along CG iterations