Sarah Ben Othman
email: sara.ben-othman@centralelille.fr

Faten Ajmi

Hayfa Zgaya
email: 2hayfa.zgaya-biau@univ-lille.fr

Slim Hammadi

A Cubic Chromosome Representation for Patient Scheduling in the Emergency Department

Keywords: emergency department, dynamic scheduling, scheduled and unscheduled patients, genetic algorithm, three-dimensional cubic algorithm

In healthcare institution management, hospital flow control and the prediction of overcrowding are major issues. The objective of the present study is to develop a dynamic scheduling protocol that minimizes interference between scheduled and unscheduled patients arriving at the emergency department (ED) while taking account of disturbances that occur in the ED on a daily basis. The ultimate goal is to improve the quality of care and reduce waiting times via a two-phase scheduling approach. In the first phase, we used a genetic algorithm (based on a three-dimensional cubic chromosome) to manage scheduled patients. In the second phase, we took account of the dynamic, uncertain nature of the ED environment (the arrival of unscheduled patients) by continuously updating the schedule.

Introduction

Controlling hospital flows and anticipating overcrowding phenomena are major challenges in the management of healthcare production systems. Due to fluctuations in patient flow, healthcare stakeholders have to manage congestion and peaks of activity. Long patient waiting times now constitute a key problem in healthcare institutions in general and emergency departments (EDs) in particular. In France, this is often because the arrival of unscheduled patients at the ED interferes with the treatment of scheduled patients (i.e. patients to whom a scheduled consultation time has been already given and who are being treated or are in the waiting room). These unscheduled, real-time perturbations in the ED mean that rescheduling is then required. However, EDs lack procedures and tools for decision-making and appropriate rescheduling.

The present study was performed in the ED at Lille University Medical Centre (Lille, France), which is particularly concerned with the issue of scheduling. As elsewhere in France, many patients wait in the ED for hoursas many as 10 hours, in some cases -before seeing a physician. These delays can even endanger the patient's life. The problem of long waiting times highlights the need to review the ED management process and implement measures to improve the quality of patient care. In the present study, we focused on optimizing the care process. We had noticed that the unscheduled arrival of patientsparticularly those requiring emergency treatment -perturbs the treatment process in the ED. If the ED is overcrowded, the arrival of unscheduled patients may interrupt the treatment of scheduled patients and/or require rescheduling around the more urgent cases. We have developed a novel, dynamic approach to patient scheduling based on two complementary processes. The first step concerns the management of scheduled patients in the ED, and is based on a genetic algorithm (GA) with a three-dimensional, cubic chromosome. The second phase involves updating the schedule after the arrival of an unscheduled patient, while taking account of staff availability and skills. The priorities here are to save patients' lives, minimize the overall waiting time for both scheduled and unscheduled patients, and optimize resource use. This approach has proved its effectiveness in improving healthcare processes. It optimizes patient treatment while taking account of the various perturbations that can occur in the ED. Performance indicators (such as total workload of medical staff, overall patient waiting time and response time for healthcare tasks) are then generated and analyzed as a guide to the effectiveness of patient management.

State of the art 2.1 Optimization of resource allocation and patient scheduling in healthcare organizations

Many studies have focusing on helping health system managers to make decisions and then evaluate their choices' impacts on the system's efficiency and effectiveness [START_REF] Flessa | Where efficiency saves lives: a linear programme for the optimal allocation of health care resources in developing countries[END_REF] [START_REF] Zon | Patient flows and optimal health-care resource allocation at the macro-level: A dynamic linear programming approach[END_REF]. Managers have to make the best possible decisions when faced with the constraints imposed by the environment within which they operate. Furthermore, managers must optimize cost and performance. To this end, optimization systems [START_REF] Baubeau | Les passages aux urgences de 1990 à 1998: une demande croissante de soins non programmés[END_REF] [4] [START_REF] Jacobson | An integer programming model for vaccine procurement and delivery for childhood immunization: A pilot study[END_REF] have been used to evaluate alternatives [6] [7]. The effectiveness of optimization systems is often measured in terms of the cost and the quality of services (a reduction in waiting times, the avoidance of a lack of resources, etc.).

Scheduling problems in health facilities are usually linked to the services required by various categories of users. Each service involves several types of resource (e.g. physicians, beds, instruments, etc.), each of which has its own costs. Hence, a range of different data must be gathered, and resources must be assigned to care tasks [START_REF] Burke | Opening the Black Box: Measuring Hospital Information Technology Capability[END_REF]. In this context, the notion of scheduling in healthcare organizations is becoming increasingly complex: (i) staff should have the diverse skills required to meet the patients' needs, (ii) it is not possible to predict a patient's pathway into a healthcare organizations because factors such as the pathology and the institution's management approach are involved, and (iii) the hospital environment is highly stochastic, which complicates resource planning.

Allocation of resources

A general problem in healthcare is the allocation of scarce medical resources (such as operating theatres or medical staff) so that waiting times are as short as possible. A major difficulty lies in the fact that this distribution must be implemented several months in advance -even when the exact number of patients for each specialty remains uncertain. Another problem arises for cyclical schedules, where the allocation is defined over a short period (a week, for example) and then repeated over the time horizon. In most cases, however, demand varies from week to week: even when the exact demand for each week is known in advance, the weekly schedule cannot be adapted accordingly.

Resource optimization

Mathematical optimization is increasingly relevant in healthcare management. As Belien (2006) pointed out: "In the near future of public health, resources will become insufficient.

Therefore, we need to find effective ways to plan, prioritize and make decisions" [START_REF] Jeroen | Exact and Heuristic Methodologies for Scheduling in Hospitals: Problems, Formulations and Algorithms[END_REF]. The hospital administration's main task is therefore to efficiently distribute the available medical services and resources. A wide variety of assignment and scheduling problems can arise [START_REF] Abdur | Operations Research in Healthcare: a survey[END_REF] [11]. Resource allocation is directly linked to a planning problem which consists in establishing the sequence for patient admission. As a general rule, patients requiring specific therapy are first placed on a waiting list and then admitted to hospital. Performance indicators related to the length of these lists are used to determine effectiveness. Long queues are to be avoided, as they represent an enormous cost to the healthcare system [12] [13]. The cost of queuing is a design parameter that must be established by the hospital board for each specialty. In a typical case, the cost is represented by a convex function in which marginal costs increase as the tail lengthens. Shorter lists are obviously preferred, although it is usually impossible (and sometimes perhaps not even desirable) to avoid a certain degree of queueing.

Indeed, the absence of a queue for certain specialties might reveal the inefficient allocation of certain scarce resources. Hence, the basic scheduling problem in healthcare is the allocation of resources to medical specialties so as to minimize queuing costs. Clearly, the attribution process must be determined in advance, and may involve negotiations. Thus, resources are allocated at the beginning of a time horizon which can be quite long, ranging from a few months to several years. The number of patients for each specialty is therefore estimated in advance, and the actual number may differ considerably from the initial estimate.

Furthermore, schedules are often created with reference to the planning horizon (e.g. one to four weeks), and then repeated cyclically. Actual demand may vary from one period to another, even when it is known in advance. A schedule must ensure that queues are as short as possible when the demand for care is maximal (relative to the selected schedule).

Staff assignment

Staff assignment is defined as an optimized construction process for the execution of care tasks. It is generally necessary to assign appropriately qualified staff to specific tasks, in order to meet the service's organization demands while complying with work regulations and seeking to satisfy individual preferences. This method has been adapted and applied to different fields, such as transport systems, healthcare systems, manufacturing, emergency services, and public services. Jaumard et al. (1998) presented a generalized linear programming model (based on the branch and bound algorithm) for the assignment of nurses with different skills [START_REF] Jaumard | A generalised linear programming model for nurse scheduling[END_REF]. The main problem is to find a set of individual schedules that satisfy demand-side constraints while minimizing wage costs and maximizing nursing preferences and quality of care. Millar and Kiragu (1998) used a network model for the cyclical and noncyclical planning of nurse schedules, in which the network's nodes represented a feasible model of work-stretch and off-stretch patterns [START_REF] Millar | Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming[END_REF]. The resulting problem was essentially a model of the shortest path with lateral constraints. According to [START_REF] Blöchliger | Modeling staff scheduling problems. A tutorial[END_REF], construction of a practical model must provide a detailed analysis and a description of the basic elements [START_REF] Blöchliger | Modeling staff scheduling problems. A tutorial[END_REF]. [START_REF] Ernst | Staff scheduling and rostering: A review of applications, methods and models[END_REF] provided a detailed review of applications, models and algorithms for staff assignment, including the assignment of medical residents in hospitals [START_REF] Ernst | Staff scheduling and rostering: A review of applications, methods and models[END_REF]. [START_REF] Musa | Scheduling nurses using goal-programming techniques[END_REF] focused on a single-phase algorithm that took account of scheduling policies for hospital nurses and their preferences for the weekend [START_REF] Musa | Scheduling nurses using goal-programming techniques[END_REF]. [START_REF] Arthur | Multiple objective nurse scheduling[END_REF] were the first to use this method with the following four objectives: taking account of staff preferences, and decreasing the number of staff, the minimum number of employees, and staff dissatisfaction [START_REF] Arthur | Multiple objective nurse scheduling[END_REF]. In the first phase of their approach, a goal-based programming model was used to assign days-on and days-off to nurses over the two-week planning horizon. The second phase dealt with specific changes to nurse assignment via a heuristic procedure. Lastly, [START_REF] Bard | Cyclic preference scheduling of nurses using a Lagrangian-based heuristic[END_REF] developed a dual heuristic to solve nurses' cyclical preference schedules [START_REF] Bard | Cyclic preference scheduling of nurses using a Lagrangian-based heuristic[END_REF].

Formulation of the problem

Emergency services are permanently confronted by interference between the care of scheduled patients and the arrival of unscheduled patients (particularly those requiring urgent treatment). At present, there is no satisfactory solution to this problem.

The term "emergency" covers two distinct phenomena: recurring flows and sanitary crises.

Firstly, recurring flows may be seasonal but the average short-or medium-term trends are known (i.e. per month or per year). However, even when the flows are known, the establishment of an efficient, effective, short-term management structure is a major challenge for healthcare production systems. Secondly, flows due to sanitary crises (flu epidemics, heat waves, cold waves, etc.) cannot be foreseen in terms of their magnitude and nature.

In the present study, we considered that a given patient's treatment can be "splittable" or "non-splittable". In fact, a patient's treatment can be interrupted in order to deal with a patient requiring treatment more urgently. A patient may be treated at different times in different places.

We next introduce the mathematical model used to formulate the problem, and then assess the set of solutions obtained with our approach.

Parameters

NP: a set of N patients to be treated, NP={P1, P2,…,PN}.

MS: a set of M medical staff members, MS={m1, m2,..,mM}.

Ns: the number of scheduled patients in the ED.

Nns: the expected number of unscheduled patients.

k: the medical staff member index mk.

s j P : the subset of patients corresponding to "splittable" treatments. C : Boolean, set to 1 if medical staff members ml and mk are managing patients in common and are placed in healthcare rooms located at different sites during two periods with a gap between them, and set to 0 if not. For this, travel T is necessary.

Institutional parameters

T w : penalty weighting for patient travel between different sites within the healthcare organization.

c w : penalty weighting for using the Emergency Department (ED) corridor c. r p BC : penalty weighting for exceeding the capacity of room r at the period p.

k p MS : penalty weighting for exceeding medical staff member mk's workload during period p.

PS G : gap of the treatment period spread penalty.

The objective function

Minimize:

  Cw +   T Cw +   c Cw + () r p C BC + ) ( k p C MS +   PS CG (1)
where

 

Cw : the cost generated by the waiting times of both scheduled and unscheduled patients in the ED. W is calculated as follows:

, , 1 1, ( ) ns
N Ns s j ns k j k k j W Min W W     



, where Ws,j is the scheduled patients' waiting time and Wns,k is the unscheduled patients' waiting time.

 

T Cw : the cost generated by patient travel between the different sites within the healthcare organization. The objective function is a sum of penalty terms. Each of the terms refers to a specific, flexible constraint (see section 3.6).

Strong constraints

The following strong constraints influence the solution's feasibility. p r SSPT : the sum of splittable patient treatments (or portions of treatments) allocated to treatment room r at period p should not exceed the treatment room's capacity:

, € s jj jpr PP A  ≤ (2)
Linking the variables jpr X and jpr A related to splittable treatments:

€ s j j PP  , rR  , p  ,   * s jpr j jpr jpr jpr A Card P X AX        (3)
The two parts of the above equations are required to check whether jpr X = 1, 0 jpr A  .

p r SPS : the sum of patients with splittable treatments should be equal to:

  s j Card P , ∀𝑃 𝑗 ∈ 𝑃 𝑗 𝑆 , () s jpr j r R p H A Card P    (4)
p r NSPT : a non-splittable patient treatment should be assigned to a single treatment room:

ns jj PP  , 1 jpr p H r R X    (5)
pq r RP : a room cannot be used by two patients in two overlapping periods p and q:

1 2 1 2
1, , ,

j pr j qr j j X X P P NP r R       (6)
pq r MSP : two medical staff members managing patients in common cannot be allocated during the same period or during two overlapping periods p and q:

1 2 1 2
1, ,

j p j q j j X X P P NP     (7)

Flexible constraints

The solution's quality is determined by the following flexible constraints.

SP lk

CPP : whenever two medical staff members managing patients in common are placed on different sites in two consecutive periods, a patient travel penalty is applied:

, lk SP SP T m l mS k M Cw C    (8)
p MPC : whenever a medical staff member is allocated to treat one or more patients in the corridor at period p, a corridor penalty is applied:

, j c c jpc p NP p H U w U    (9)
r p

Cap : whenever at least two patients are treated at the same period p in the same room r specially in the overcrowding situation, a capacity penalty is applied:

, r R p     R r S ,, rr p jpr p NP r R p H BC BC U      (10)
In the following section, we solve the above-described problem while meeting the different constraints. To optimize the solution, we decided to adopt an aggregative approach without seeking to apply appropriate weightings. In real-life healthcare situations, it is very difficult to define suitable weights for these criteria. The present study assessed the results of simulations that generated some of these criteria separately or (in some cases) together.

4 The rolling-horizon approach to scheduling

The scheduling environment

Figure 1 shows the scheduling environment with three kinds of patients: urgent patients (UPs), scheduled patients (SPs) and non-scheduled patients (NSPs).

Assumptions



A medical staff member is present in the scheduling horizon in the ED. The number of scheduled patients in a scheduling horizon is Ns, whereas the expected number of unscheduled patients is Nns. All the unscheduled patients arrive randomly at the ED; on arrival, they must be assigned with a theoretical scheduled consultation time.



In France, EDs never close. Each arriving patient j should be registered at the reception desk at time tarj. None of the patients who arrive at the ED are rejected, and all patients should be treated during the current scheduling horizon or the next scheduling horizon.  Each patient corresponds to a set of healthcare operations to be executed in a parallel or in a sequential manner by one or more medical staff members (staff physicians, nurses, interns, etc.).



Medical staff members are organized into teams. Each team contains at least one physician. Some teams contain additional staff members (nurses, paediatricians, etc.), depending on the patient's pathology.



The scheduling horizon H starts at time DH and ends at the time FH. In the present study, we consider that the duration of the scheduling horizon is 4 hours.



The scheduling horizon is divided into several periods whose durations are not necessarily equivalent. If two periods have the same duration, the number and the duration of slots in each period may differ. In general, a period contains multiple slots.

A slot is allocated to a scheduled patient. Each period contains at least one slot. A slot's scheduled consultation time is given by the start time of the period to which it belongs. Hence, if two or more slots are included in a period, the scheduled patients assigned to the same slot have the same scheduled consultation time.  When the medical staff member becomes available, the waiting patient with the earliest scheduled consultation time is called. If the waiting room is full and it is not possible to call all the patients during the same scheduling horizon, the remaining patients and the new arrivals will receive a scheduled consultation time in the next scheduling horizon.

 In the ED, the most urgent cases are given the highest priority. Hence, when patients requiring urgent treatment arrive, the current scheduling can be interrupted and rescheduling is required because these patients should not have to wait for a consultation.

Performance measures

Let the waiting time for a scheduled patient j (Ws,j) be the sum of the patients' waiting times between the registration and the theoretically scheduled consultation time War, and the waiting time before the first consultation Wfc, where:

)

fc k fc k s k W t t   (16)
The two equations ( 11) and ( 14) are mathematically equivalent but semantically different. In

The scheduling procedure

The sequential treatment of patients is dynamically scheduled, which requires the real-time generation of activity plans for each medical staff member. A multidisciplinary medical team is formed, and a treatment role is assigned to each team member. The schedule is updated whenever the patient input stream changes.

Figure 2: the scheduling approach

Our approach is based on an offline phase and an online phase.

The offline phase consists in scheduling the scheduled patients who arrive at the ED. A GA is applied in this phase, and the scheduled patients correspond to the constraints of the GA.

The online phase takes account of a dynamic feature; the arrival of unscheduled patients at the ED. These patients are treated with regard to their pathologies and their emergency status.

Hence, the online phase uses a shifting and insertion method based on the notion of periods and horizons.

The offline phase: scheduling with a GA

The treatment plan is generated by applying a dynamic, responsive GA. The algorithm is designed to (i) optimize the assignment of patients to medical staff with the skills needed to treat them, and (ii) minimize patient waiting times and overall costs while maintaining the quality of care. The scheduling algorithm selects the appropriate medical staff member for the treatment of a given patient, according to the staff's availability and skills. An emergency alert resulting from the need for a medical staff member triggers an updating process by the scheduling algorithm. This situation may lead to the interruption of a patient's treatment and the initiation of treatment of a more urgent case or a shift in one or more treatment processes to make space for unscheduled patients requiring urgent treatment.

The goal is to minimize the overall waiting time that the patient spends in the ED and the costs described in the third section of this article.

The purpose of the GA is to provide an approximate solution to the optimization problem, insofar as an exact method cannot solve the problem within a reasonable time. The potential solution(s) provided by the GA necessarily requires the involvement of the different medical staff members in the ED. In the following section, we will describe our patient scheduling approach in detail.

Definition of the chromosome

We chose to use a three-dimensional cube chromosome with the following three axes: "medical staff", "patients", and "time". The time axis is divided into intervals of different sizes. The scheduling horizon is divided into several periods that do not necessarily have the same duration. If two periods have the same duration, the number and the duration of slots in each period may differ. In general, a period contains more than one slot. In view of the division of the time axis into many slots, each medical staff member is assigned to a patient in a specific slot from a specific period. For example, Figure 4 shows a medical staff member M1 treating patient P1 in the second slot of period 3. The Figure 5 shows the sequential assignment of medical staff members My1 and My2, to patients Pz1 and Pz2 in periods 3 and 4, respectively. The Figure 6 shows a multiskill cubic assignment, which is made possible by our choice of the type of chromosome. Here, patient PZ1 needs two different skill sets for his/her treatment, medical staff members My1 and My3 are assigned to the same period 3 and the same slot. Patient PZ2 needs a pair of different skills, and medical staff members My2 and My3 are assigned to the same period 4 and the same slot.

The initial chromosome population

The first step is the formation of an initial population as the starting point for execution of the algorithm. We used two methods to build the initial population:

 The first method consists in recovering the initial population solutions (IniPopL) generated by a list algorithm with dynamic priority rules.

 The second method consists in generating initial population solutions at random (IniPopR) but which are viable because they comply with the strong constraints.

The details of the GA used in the present study are as follows:

The controlled crossover schema

This used in order to move the start time of the patient treatment process forward or backward for a given medical staff member. It does not change the assignment of patients, i.e. which medical staff member treats which patient). Only the "time" and "patient" axes are considered.

Example

The time axis is divided into 5 min intervals. Each slot in the time axis is a Boolean equal to 1 if the patient is assigned to the slot, or 0 if not. The crossover yields two viable offspring chromosomes, so no correction is needed. The viability is checked on the "medical staff" axis. In fact, we need two different medical staff members in the slots [START_REF] Abdur | Operations Research in Healthcare: a survey[END_REF][START_REF] Lee | Mediator approach to direct workflow simulation[END_REF][START_REF] Patrick | Dynamic multipriority patient scheduling for a diagnostic resource[END_REF][START_REF] Hans | Robust surgery loading[END_REF][START_REF] Jaumard | A generalised linear programming model for nurse scheduling[END_REF][START_REF] Millar | Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming[END_REF] This phenomenon shows the value of using a three-dimensional cubic chromosome to check compliance with strong constraints.

Chromosome A:

The controlled mutation schema

The mutation is a partially random operation that enables us to modify the solutions and move towards an optimum or perhaps move out of a local optimum. In our case, the mutation modifies the Booleans present in our chromosomes. Not all chromosomes are mutated; the probability of mutation is <1. If the chromosome is selected, it will then go through the slots (according to the "medical staff", "patient to treat", "time" axes) and change their values in accordance with simple rules.

The slots are changed at random. Each slot has a predetermined probability of being mutated.

If the selected slot is to be changed from 1 to 0, there are no additional conditions; only one patient is treated at a given time by a medical staff member. If the selected slot is to be changed from 0 to 1, we have to check that the medical staff member has the requisite skills and is available to treat the patient in the slot. If the condition is checked, the slot is mutated. This first phase of the mutation can thus remove patients from a medical staff member or assign them to him/her if he has the needed skills and is available. However, the durations of the patient treatment processes may be inaccurate, and the treatment is divided into several slots. This mutation is controlled by the "medical staff" axis.

In order to comply with the viability of the final set of generated solutions (resulting from the application of the GA with controlled crossover and mutation operators), we set a number of constraints to be complied with by these operators. These constraints guide us in the search for the optimal solution and accelerate the convergence.

Selection

After crossover, our population increases as the offspring chromosomes join the parent chromosomes. It is then necessary to select the chromosomes that will be part of the new population before rescheduling.

We first evaluated our set of solutions by calculating the value of the objective function (see section 3.3). We calculated its strength of each solution and normalized it as a percentage of the total strength. Selecting only the strongest solutions would not guarantee a great diversity in our solutions, and selecting solutions at random would perhaps remove good solutions. We decided to select a percentage of the best solutions, and then select those that remain on the roulette wheel. The probability of selection corresponds to the normalized strength. This ensures the selection of varied, strong solutions.

The online phase: real-time rescheduling

This phase deals with the interference between scheduled and unscheduled patients arriving at the ED, which prompts real-time rescheduling. The goal is to reduce the waiting time of both scheduled and unscheduled patients. The process looks at whether an unscheduled patient can be inserted into the schedule generated by the offline phase without affecting his/her neighbouring patients. To this end, the process first seeks medical staff members who have

Mutation: changes are in shown grey

the appropriate skills for treating the patient to be inserted.

To take account of interference between scheduled and unscheduled patients, we need to consider the inter-period waiting time in each horizon.

This work assumes that the scheduling horizon which represents consultation time window is divided into several periods as already mentioned above. A consultation for an unscheduled patient is scheduled in the first empty slot in the period, as shown in Figure 7. In principle, the start time of the first empty slot gives the patient's theoretical scheduled consultation time. The maximum acceptable number of unscheduled patients in the period is difficult to estimate because slots in the same period can have different lengths. For nonurgent patients, the real-time rescheduling is performed by the algorithms described below. The end of the consultation window max,H t is used as the scheduled consultation time for patients who are not included in any of the periods in the horizon H.

The present approach assumes that each period p has its own length Δp, and that the start time of each period is x minutes behind the start time of its first free slot (Figure 7). The maximum workload level per period is

Simulations and results

Prior to our simulations, we collected data in the ED at Jeanne de Flandre Hospital (part of Lille University Medical Centre). This ED receives about 24,000 visits per year (an average of 458 per week and 66 per day), of which 20% take place in a short-stay hospitalization unit (SSHU) and 80% take place in an outpatient unit. It has 10 beds in the SSHU, 10 consultation boxes in the outpatient unit, a suturing room, a plaster room, an emergency room, and two waiting rooms. In the event of overcrowding, vacant beds in the SSHU can be transformed into consultation boxes.

In the present section, we describe the effectiveness and efficiency of our approach to scheduling. We first describe the real data collected in the ED. Next, we generated realistic random instances of the real data and studied dynamic, rolling-horizon scheduling in more detail. With a view to investigating the interactions between the objective functions and determining how the patients' waiting times affect costs, we carried out several different computational experiments.

Description of the data

We analyzed a sample of data collected over a period of almost three years, from January 2011 to November 2013. The weekly variations in Figure 10 show troughs for holiday periods and peaks for flu epidemics. Outside the summer holidays, the mean data were very similar from one week to another. In contrast, we observed regular variations over the seven days of the week; this can be seen as recurring peaks in correlogram with a period of 7 (Figure 14). The value of managing overcrowding is emphasized by refining the time horizon. For effective decision-making, it is best to adopt a time scale that enables patient rescheduling.

Following our observations in the ED and interviews with the medical staff, we noted that waiting times in the ED could be as long as 5 hours. The ED at Jeanne de Flandre Hospital did not have a decision support system or information system capable of managing overcrowding. Medical staff members gave the highest consultation priority to the most urgent patients and then to previously scheduled patients. Unscheduled patients in the ED had to wait in the waiting room and sometimes in corridors without obtaining a scheduled first consultation time, which increased their level of anxiety.

Our approach's level of performance was compared with that of the conventional method used in the ED. A database analysis enabled us to simulate the patients' waiting times, which appeared to be excessive in some cases.

Computational results and discussion

As emphasized in section 4, our two-phase, rolling-horizon patient scheduling is revised whenever unscheduled patients requiring urgent treatment arrive in the ED, in order to optimize the schedule for patients whose waiting times are longer or shorter than expected.

The waiting list varies over time as patients arrive and as patients are treated.

We analyzed our computational results in two main steps. Firstly, we investigated the effectiveness of the GA-based algorithm and validated our chromosome model. Secondly, we implemented our approach in a real ED, and evaluated its applicability and performance.

In order to evaluate our approach's level of performance, extend our computational results and generalize our method, we applied our two scheduling phases to solve 10 randomly generated problem instances with different numbers of patients. The results were compared with those obtained in practice (according to the ED database used by the medical staff) and those generated by the list algorithm (implemented in Java). These instances were generated from real data. In the ED, emergencies can be treated with the list algorithm in order to find a quick (but not necessary optimal) solution. The list algorithm's dynamic priority rules mean that it is particularly suited to the scheduling problem. It is flexible and is easily implemented in real time. Our problem is solved by dynamic priority rules: the patients' arrival time and level of urgency. The algorithm maintains a list of all the ready-to-be-scheduled tasks after registration at the reception desk. 1 shows the real ED data related to the test problem scheduling, together with the results obtained with the list algorithm, the GA-based approach, and the practical case. The gap between the solutions (related to the mean total waiting time per patient per instance (a day) is shown in Figure 15.

Figure 15: the waiting time as a function of the number of patients

Table 1 shows that minimization of the waiting time is associated with an increase in the medical staff's workload -especially when using the GA-based approach (see Figure 16). In fact, adjusting the physicians' total idle time minimizes the average total waiting time.

Figure 16: the medical staff's workload on day instances

As can also be seen from Table 1, the solutions obtained with the list algorithm for the first seven test instances are close to those obtained by the practical solution. For instances 8, 9

and 10, the list algorithm is markedly better than the practical solution. The gap between the solutions was low and never exceeded 5.41%.

In fact, the list algorithm uses dynamic priority rules to schedule the patients. These rules depend on the care tasks that have yet to be performed. As the tasks do not have the same care pathway, the waiting time can be reduced for some patients (for the same scenario), while the workload of the medical staff remains the same. Table 2 shows the computation times for the list algorithm and the GA-based approach. In order to avoid the blind aspect of the genetic operators, we designed a controlled genetic crossover and mutation operators for the cubic representation of the chromosome. Furthermore, we integrated the solutions found by the list algorithm in the initial population into the GA, in order to accelerate convergence on the best solution. As can be seen from Table 2, the GA-based approach performs far better than the list algorithm in terms of the computation time and performs better than both the current system and the list algorithm in terms of the waiting time. The computation time are compared in Figure 17. The GA-based approach's computation time is significantly shorter than that of the other methods.

In Table 2, the difference in execution time between the GA and the list algorithm is less than one minute. If this time difference is sufficient for the GA to generate high-quality solutions minimizing the patients' waiting time, then the solutions are relevant for clinical practice.

As discussed above, the GA-based method can address real-life scheduling problems in EDs, so that the patients' waiting time can be minimized as a function on the urgency of the required treatment. The second phase of our scheduling method reschedules the medical staff's tasks whenever a new patient arrives in the ED; the goal is to minimize the patients' waiting times by optimizing the use of resources (medical staff members) and ensuring that a patient with a more severe condition is prioritized. Hence, to better address scheduling in realworld EDs, the GA-based scheduling approach requires a reliable information system and an adequate amount of training for scheduling staff.

In addition, we have already studied and developed a multi agent system to model the communication and the interaction between the different medical staff member and the software agents [START_REF] Ben Othman | Agents endowed with uncertainty management behaviors to solve a multiskill healthcare task scheduling[END_REF]. The scheduled and re-scheduled approaches proposed in this paper are integrated in the agent behaviour in order to communicate to the medical staff member, the new care tasks to realize.

Conclusion

In the present study, we developed an innovative GA-based approach for scheduling both scheduled and unscheduled patients in an ED. The GA-based method assigns a theoretical consultation time to each patient on arrival. The goal of patient scheduling is to minimize the total waiting time and the overall cost. The GA-based approach grant a higher priority to the most urgent patients, while optimizing the medical staff's workload. The GA's performance has been enhanced by the incorporation of a cubic chromosome representation with novel, controlled genetic operators. In order to demonstrate the superiority of our approach, we applied it to a real ED. Simulations revealed that the GA-based approach improves the performance of patient scheduling in the ED and makes efficient use of the available resources. The computational results of our approach exceeded those of the practical approach. In the future, we intend to improve our approach to multiskilled healthcare task scheduling in the ED by combining a GA with multi-agent systems.

  cost generated by treating a patient in the corridor of the ED. cost generated by exceeding the capacity of room r at the period p. cost generated by exceeding medical staff member mk's workload at the period p. PS CG : the cost generated by the gap of the treatment period spread penalty.

Figure 1 :

 1 Figure 1: the scheduling environment  According to the stochastic behaviour of the medical staff's consultation time, let

W

  fact, the scheduling method developed in the present study assigns a theoretical scheduled consultation time to each unscheduled patient at his/her time of arrival and then guides him/her to the waiting room at the scheduled consultation time. On the basis of the scheduled consultation time, War is calculated for each registered patient. The objective is to comfort patients and reduce their stress by keeping them informed of their waiting time prior to the first consultation. If the first consultation time is equal to the scheduled consultation time, are equal to 0. In the event of perturbations (overcrowding, a lack of medical staff, worsening in the patient's health status, etc.), the consultation times are rescheduled, the first consultation time increases, and so the patient's waiting time lengthens.Most of patients prefer early scheduled consultation times -especially when they arrive. To satisfy these preferences, the waiting time (based on the arrival time , ar k W ) should be reduced by assigning available medical staff with appropriate skills as quickly as possible.

Figure 3 :Figure 4 :

 34 Figure 3: a representation of a cubic chromosome (a patient/medical staff/time cube)

Algorithm 1 :

 1 construction of the IniPopL Input: Fixed NL, the size of the chromosome population InitPopL Fixed NR, the size of the chromosome population IniPopR Output: IniPopL of NL chromosomes generated by applying the list algorithm IniPopR of NR chromosomes generated by applying a random process Begin i:=0; IniPopL = Ø; while i<=NL do Find a cubic chromosome i as a feasible (or suboptimal) solution of a single objective optimization model by applying a list algorithm; end while IniPopL = IniPopL  {chromosome i}; i:=i+1; end Algorithm 2: the cubic GA approach Input InitPopL, InitPopR, N is the global size of initial population Output: a set of N good scheduling solutions Begin Construction of IniPopL: find NL feasible cubic chromosomes Construction of IniPopR: find NR=N-NL partial feasible solutions at random Merging of IniPopL and IniPopR (N cubic chromosomes) while (stop criterion are not reached) do  Evaluate individuals  Select 2 parents P1 and P2 at random  Apply a controlled crossover algorithm with a probability pc, in order to obtain offspring1 and offspring2  Apply a controlled mutation algorithm with a probability pm  Select N new individuals and build a new population  Update the stopping criterion end while end

  the mask is 0110, then the chromosome resulting from the crossover will be as follows:

  , [55-60] and [60-65] on offspring chromosome 2 because the same medical staff member cannot treat two different patients at the same time (a constraint related to the equation 7). Furthermore, patient 2 and patient 4 in offspring chromosome 2 must be treated by two different medical staff members in the slot [80-95].

Figure 7 :

 7 Figure 7: an example in which an unscheduled patient's consultation time is determined on the basis of free slots.

C

   <HWp,h,max ) then Assign-patient w to the period p; End_If Tw= Debp: the slot's start time For i=1 to Nbsp do If FREE[i] ==0 then return Tw Else Tw = Tw + TAB[i] End_For Tw = Finp //the period p is overloaded Return Tw End_ Search-First-Free_Slot Algorithm: Scheduling_new_arrivals (Patient w, Time t, Horizon H) Input: DebH: the Start time of the horizon H represents the start time of the consultation; We consider that the arrival of unforeseen patient follows poisson distribution t: Current arrival time of patients FinH: The end of the horizon H; NBp,H: Number of periods in the horizon H; TABH: Table [1…. NBp,H] contains the different lengths of each period. Output: Tw the start time of the first consultation specifying the horizon, period and slot. Begin If Urgent_patient then No-wait-consultation If t<= DebH then p = 1 (the first period in the horizon) Else For (i = 1 to NBp,H ) do If t<= DebH + TABH [i] then p = i; Save the start of the period Debp Save the end of the period Finp End_If End_For End_If Tw = Search-First-Free_Slot (p, Horizon H, Patient w, Debp, Finp) End Scheduling_new_arrivals

Figure 8 :

 8 Figure 8: Database from the ED in Jeanne de Flandre Hospital

Figure 9 :

 9 Figure 9: The number of patients per month at the ED in Jeanne de Flandre Hospital

Figure 10 :

 10 Figure 10: the number of patients per week at the ED in Jeanne de Flandre Hospital

Figure 11 :

 11 Figure 11: the number of patients per day at the ED in Jeanne de Flandre Hospital

Figure 12 :

 12 Figure 12: Correlogram related to the monthly period. ACF: autocorrelation function.

Figure 13 :

 13 Figure 13: Correlogram relating to the daily period. ACF: autocorrelation function.

Figure 14 :

 14 Figure 14: Correlogram related to the hourly period. ACF: autocorrelation function.

  Medical staff Workload in practice (%)Medical staff Workload by GA (%)

Figure 17 :

 17 Figure 17: Execution times using the list algorithm and the GA-based approach

Algorithm: Search-First-Free_Slot (Period p, Horizon H, Patient w, Debp, Finp) Inputs: Nbsp:

  Number of slots in the period p. TAB [1… Nbsp] a table contains the length of each slot. FREE[1… Nbsp] a table contains 1 or 0. FREE(i) = 0 if the slot i is free, otherwise the slot i is full. Output: Tw the start time of the first free slot Begin Calculate HWp,h ;

	If (HWp,h +

Table 1 :

 1 a comparison of the GA-based approach, the list algorithm and the practical case

	Day	Number of patients	GA based approach	List algorithm	Practical		Number of
										no-wait
	Scheduled patients	Unscheduled patients	W (min)	Medical staff's	W	Medical staff's workload (%)	W	Medical staff's	consultation s (%)
					workload				workload
					(%)				(%)
	1	8	48	205.3	80.2	242.2	82	245.72	80	0.55
	2	17	50	212.6	71.3	216.4	73.5	218.47	72	0.5
	3	20	44	230.5	67	267.8	65	266.39	65	0.48
	4	28	31	298.5	88.2	358.8	87.2	359.08	85	0.58
	5	6	58	197.5	80.5	215.2	79	215.65	78	0.52
	6	12	105	290.2	88.3	303.4	90.2	305.05	89	0.50
	7	12	70	222.6	75	230.2	76	231.04	76	0.64
	8	14	38	223.5	85	265.4	90	270.18	90	0.68
	9	10	29	278.4	93.2	296.2	92	305.26	92	0.58
	10	18	24	187.6	83.2	198.5	82.5	209.63	81	0.78
	Table

Table 2 :

 2 Computation time

	Day instance		GA-based approach		List algorithm
		W (min)	Computation time (s)	W (min)	Computation time (s)
	1	205.3	9.3	242.2	10.2
	2	212.6	10.5	216.4	11.4
	3	230.5	77.9	267.8	65.7
	4	298.5	120.6	358.8	119.3
	5	197.5	14.2	215.2	15.2
	6	290.2	120.2	303.4	140.2
	7	222.6	80.9	230.2	76.9
	8	223.5	92.6	265.4	146.7
	9	278.4	70.2	296.2	89.3
	10	187.6	9.6	198.5	10.4

Acknowledgments

This work was supported and funded by the Federative Research Structures Technologies for Health and Drugs (SFR-TSM): http://sfr-tsm.ec-lille.fr/ The three components: CRIStAL CNRS UMR 9189 (http://www.cristal.univ-lille.fr/), the EA2694 of the Public Health Laboratory of Lille University (http://ea2694.univ-lille2.fr) and the adult emergency department of CHRU de Lille are full partners of the SFR-TSM


Irina Gutsche

Fasséli Coulibaly

James E Voss

Jérôme Salmon

Jacques D'alayer

Myriam Ermonval

Eric Larquet

Pierre Charneau

Thomas Krey

Françoise Mégret

Eric Guittet

Félix A Rey
email: felix.rey@pasteur.fr

Marie Flamand
email: marie.flamand@pasteur.fr

Secreted dengue virus nonstructural protein NS1 is an atypical barrel-shaped high-density lipoprotein

Keywords: Glycoprotein, secretion, electron cryomicroscopy, HDL, triglycerides

INTRODUCTION

DENV (genus Flavivirus, family Flaviviridae) is responsible for the major arthropodborne viral human disease of the tropics [START_REF] Mackenzie | Emerging flaviviruses: the spread and resurgence of Japanese encephalitis, West Nile and dengue viruses[END_REF]. It is estimated that 50-100 million dengue cases occur annually, ranging from mild fever to life-threatening dengue hemorrhagic fever (DHF) and dengue shock syndrome (DSS) [START_REF]Dengue: Guidelines for diagnosis, treatment, prevention and control[END_REF]. The number of severe forms can exceed half a million per year, and lead to tens of thousand deaths [START_REF] Mackenzie | Emerging flaviviruses: the spread and resurgence of Japanese encephalitis, West Nile and dengue viruses[END_REF]. DHF is associated to thrombocytopenia, coagulopathy, acute inflammation, frequent hepatomegaly, and most importantly, plasma leakage to which the risk of fatal hypovolemic shock (DSS) is associated [START_REF] Lei | Immunopathogenesis of dengue virus infection[END_REF][START_REF] Halstead | Dengue[END_REF][START_REF] Mairuhu | Treating viral hemorrhagic fever[END_REF]. It has been proposed that an inadequate immune response is the major cause of severe clinical manifestations [START_REF] Fink | Role of T cells, cytokines and antibody in dengue fever and dengue haemorrhagic fever[END_REF][START_REF] Green | Immunopathological mechanisms in dengue and dengue hemorrhagic fever[END_REF][START_REF] Lin | Autoimmune pathogenesis in dengue virus infection[END_REF]. Soluble mediators produced during the acute phase of the disease likely play a pivotal role in vascular permeability, as suggested by the rapid recovery of most DHF patients [START_REF] Basu | Vascular endothelium: the battlefield of dengue viruses[END_REF][START_REF] Seneviratne | Pathogenesis of liver involvement during dengue viral infections[END_REF][START_REF] Lisman | Haemostatic abnormalities in patients with liver disease[END_REF].

There is accumulating evidence that flavivirus NS1, a ~50 kDa nonstructural glycoprotein, participates to different stages of the virus life cycle. Part of NS1 resides in virally-induced intracellular organelles where it plays an essential role in viral replication [START_REF] Welsch | Composition and three-dimensional architecture of the dengue virus replication and assembly sites[END_REF][START_REF] Mackenzie | Immunolocalization of the dengue virus nonstructural glycoprotein NS1 suggests a role in viral RNA replication[END_REF][START_REF] Lindenbach | trans-Complementation of yellow fever virus NS1 reveals a role in early RNA replication[END_REF][START_REF] Muylaert | Genetic analysis of the yellow fever virus NS1 protein: identification of a temperature-sensitive mutation which blocks RNA accumulation[END_REF][START_REF] Westaway | Ultrastructure of Kunjin virus-infected cells: Colocalization of NS1 and NS3 with double-stranded RNA, and of NS2B with NS3, in virus-induced membrane structures[END_REF]. The protein, possibly modified by glycosylphosphatidylinositol (GPI), also associates to lipid rafts at the plasma membrane and mediates a signaling pattern common to GPI-anchored proteins in the presence of specific antibodies [START_REF] Noisakran | Association of dengue virus NS1 protein with lipid rafts[END_REF][START_REF] Noisakran | Characterization of dengue virus NS1 stably expressed in 293T cell lines[END_REF][START_REF] Jacobs | Dengue virus nonstructural protein 1 is expressed in a glycosyl-phosphatidylinositol-linked form that is capable of signal transduction[END_REF]. NS1 is eventually secreted by DENV-infected mammalian cells [START_REF] Flamand | Dengue virus type 1 nonstructural glycoprotein NS1 is secreted from mammalian cells as a soluble hexamer in a glycosylation-dependent fashion[END_REF][START_REF] Pryor | The effects of site-directed mutagenesis on the dimerization and secretion of the NS1 protein specified by dengue virus[END_REF][START_REF] Winkler | Evidence that the mature form of the flavivirus nonstructural protein NS1 is a dimer[END_REF] and released in the blood stream of infected individuals [START_REF] Alcon | Enzyme-linked immunosorbent assay specific to Dengue virus type 1 nonstructural protein NS1 reveals circulation of the antigen in the blood during the acute phase of disease in patients experiencing primary or secondary infections[END_REF][START_REF] Young | An antigen capture enzymelinked immunosorbent assay reveals high levels of dengue virus protein NS1 in the sera of infected patients[END_REF]. The protein is detectable in plasma from the onset of fever up to the first days of convalescence, at concentrations that can exceed several µg/mL [START_REF] Alcon | Enzyme-linked immunosorbent assay specific to Dengue virus type 1 nonstructural protein NS1 reveals circulation of the antigen in the blood during the acute phase of disease in patients experiencing primary or secondary infections[END_REF][START_REF] Young | An antigen capture enzymelinked immunosorbent assay reveals high levels of dengue virus protein NS1 in the sera of infected patients[END_REF][START_REF] Alcon-Lepoder | Secretion of flaviviral non-structural protein NS1: from diagnosis to pathogenesis[END_REF]. The amount of NS1 circulating in human sera appears significantly higher in patients who developed DHF rather than dengue fever [START_REF] Libraty | High circulating levels of the dengue virus nonstructural protein NS1 early in dengue illness correlate with the development of dengue hemorrhagic fever[END_REF], although it is not clear whether this effect is a cause or a consequence of plasma leakage. In vitro, the protein binds cell surface glycosaminoglycans [START_REF] Avirutnan | Secreted NS1 of dengue virus attaches to the surface of cells via interactions with heparan sulfate and chondroitin sulfate E[END_REF] and is targeted to late endosomes upon entry into target cells [START_REF] Alcon-Lepoder | The secreted form of dengue virus nonstructural protein NS1 is endocytosed by hepatocytes and accumulates in late endosomes: implications for viral infectivity[END_REF]. Pre-incubation of hepatocytes with soluble NS1 enhances subsequent infection by a homologous strain of DENV [START_REF] Alcon-Lepoder | The secreted form of dengue virus nonstructural protein NS1 is endocytosed by hepatocytes and accumulates in late endosomes: implications for viral infectivity[END_REF]. In addition, both soluble and cell-surfaceassociated NS1 are capable of modulating complement activation pathways through the formation of immune complexes or binding to host proteins such as the regulatory protein factor H, complement factor C4 or clusterin [START_REF] Avirutnan | Antagonism of the complement component C4 by flavivirus nonstructural protein NS1[END_REF][START_REF] Avirutnan | Vascular leakage in severe dengue virus infections: a potential role for the nonstructural viral protein NS1 and complement[END_REF][START_REF] Chung | West Nile virus nonstructural protein NS1 inhibits complement activation by binding the regulatory protein factor H[END_REF][START_REF] Kurosu | Secreted complement regulatory protein clusterin interacts with dengue virus nonstructural protein 1[END_REF].

In this paper, we investigated the structure/function relationship of DENV NS1.

We determined a low-resolution three-dimensional reconstruction of the hexamer, which appears as an open barrel with a wide central channel. We identified that specific lipids associate to the NS1 particle, in particular triglycerides, cholesteryl esters and phospholipids that likely fit into the central cavity. These results point to striking similarities between DENV NS1 and high density lipoproteins (HDL) involved in vascular homeostasis.

6

RESULTS

Three-dimensional (3D) organization of the DENV NS1 hexamer

To get insights into the NS1 structure/function relationship, we sought to characterize the 3D organization of the secreted hexamer. We analyzed an authentic NS1 protein purified from the extracellular medium of Vero cells infected with DENV serotype 1 (DENV-1). Numerous crystallization trials failed to yield diffraction quality crystals. Using cryo-electron microscopy (cryo-EM), we obtained a 3D reconstruction of the DENV-1 NS1 hexamer. The resolution of the reconstruction (at about 3.0 nm) allows to visualize the protein as an open barrel with a 32 point-symmetry, approximately 10 nm in diameter and 9 nm in height, featuring a prominent central channel running along the molecular 3-fold axis (Fig. 1). Three 2-fold symmetric twisted rods, corresponding to the dimeric subunits, form the walls lining the channel.

The lateral interactions between the dimeric building blocks take place along a fairly thin area representing at most 5 nm 2 . Each rod is made of two ellipsoidal lobes, which most likely correspond to the individual protomers (Fig. 1 and Fig. S2). The central channel has an estimated volume of 80 nm 3 with triangular openings of about 9 nm 2 at each end, rotated by 40 degrees about the 3-fold axis (Fig. 1C).

The DENV NS1 dimeric subunits behave as membranous proteins in a Triton X-114 detergent phase partitioning assay.

The very narrow interfaces observed between the dimeric subunits, together with the previously reported instability of the NS1 hexamer in nonionic detergents [START_REF] Flamand | Dengue virus type 1 nonstructural glycoprotein NS1 is secreted from mammalian cells as a soluble hexamer in a glycosylation-dependent fashion[END_REF][START_REF] Crooks | The NS1 protein of tick-borne encephalitis virus forms multimeric species upon secretion from the host cell[END_REF] and its resistance to high molarities of salt or to chelating agents (Fig. S3), indicated that the dimers are essentially held together by weak hydrophobic interactions. Further elements localizing within the channel are likely to be necessary to hold the dimeric rods together, for instance amphiphilic molecules such as lipids, as inferred by the dual behavior of the protein in a TX-114 detergent phase partitioning assay (Fig. 2).

Whereas soluble and membranous proteins segregate in the aqueous and detergent phases, respectively, the detergent-treated NS1 partitions into both phases, with a higher proportion of protein retained in the detergent fraction (Fig. 2A). The DENV E protein, which contains a transmembrane anchor, remains exclusively in the detergent phase, as expected (Fig. 2A). NS1 recovered from the detergent-rich phase is essentially dimeric, as observed by treatment of the corresponding fraction with chemical cross-linker dimethylsuberimidate (DMS) and analysis of the resulting products by SDS/PAGE and Coomassie blue staining or mass spectrometry (Fig. 2B and 2C, respectively). In contrast, NS1 from the aqueous phase maintains its characteristic hexameric pattern with DMS treatment (Fig. 2B,2C). Thus, the soluble hexamer is composed of amphipathic dimeric subunits that behave as membrane proteins upon dissociation. This indicates that dimeric precursors likely interact with lipid membranes prior to hexamer assembly, possibly dragging lipids out of the membrane during the oligomeric transition.

The NS1 protein is secreted as a lipoprotein particle rich in triglycerides. chromatography (TLC). A predominant species, well resolved on the TLC plate (Fig. 3A, arrow), was recovered and analyzed by nuclear magnetic resonance (NMR, Fig. 3B). The 1H NMR spectrum displays the characteristic signals of triglycerides (TG), including peaks at 5.17, 4.17 and 4.03 ppm related to protons of the glycerol moiety, and the corresponding cross peaks in 2D double quantum filtered correlation spectroscopy (DQF-COSY) (Fig. 3B). This was corroborated by gaz-liquid chromatography (GLC) analysis of NS1-associated TG (Fig. 3C). TG molecules are formed by three fatty acid chains that can all be different or all alike. Their length and degree of saturation is variable, although aliphatic chains with 16, 18 and 20 carbon atoms, which may contain one or two double bonds, are most frequently observed. GLC analysis of fatty acids derived from DENV-1 NS1 TG shows two major peaks corresponding to saturated palmitic acid (16:0) and unsaturated oleic acid (18:1), as well as minor polyunsaturated palmitoleic acid (16:1) and linoleic acid (18:2), and other peaks that likely correspond to background signals (Fig. 3C). Compared to authentic NS1 recovered from the supernatant of DENV-1 infected Vero cells, recombinant DENV-2 NS1 produced in Drosophila S2 cells also contains TG that display a homogeneous fatty acid profile composed of palmitic acid and stearic acid (18:0) (Fig. 3C). TG molecules extracted from control HDL particles are formed by palmitic, oleic and linoleic acid (Fig. 3C).

The NS1 lipid moiety is similar to the lipid cargo of high density lipoproteins.

In addition to TG, we were able to isolate cholesteryl ester (CE) molecules from the NS1 hexamer of DENV type-1 and -2. Sterol esters were isolated from recombinant NS1 preparations, separated on TLC plate and saponified. The corresponding sterol fractions were found to be identical to standard cholesterol both by GLC and mass spectrometry (Fig. 4). Other lipid species were identified by TLC and GLC, including mono-and diacylglycerol, phosphatidylcholine (PC) and phosphatidyl-ethanolamine (PE). We estimated the number of lipid molecules by comparing the amount of fatty acid chains (fatty acid methyl esters recovered by transesterification of NS1-associated lipids) to a defined amount of a C17 standard on GLC. By this method, we found that each NS1 hexamer binds 6 TG molecules (i.e. one per protomer), twice as many monoand diacylglycerol molecules, 16-33 CE and 18-27 phospholipids (Table 1).

Cholesterol and sphingomyelin (SM) were also observed on TLC but not quantified.

Overall, the NS1 lipid composition is very similar to that of HDL, although HDL show a higher lipid:protein weight ratio (Table 1). Accordingly, the NS1 hexamer is denser than what would be expected for an HDL particle of similar size (1.20-1.23 g/mL for the NS1 hexamer in comparison to 1.063-1.12 g/mL for 9-12 nm wide HDL) and rather fits within the class of very high density lipoproteins (VHDL, 1.21-1.25 g/mL), close to soluble proteins (1.26-1.28 g/mL). Of note, we found that the hexameric organization and lipid content is identical for two different DENV serotypes of the NS1 protein (Table 1 and Fig. 3C).

Modeling lipid organization within the DENV NS1 channel.

We calculated that about 70 lipid molecules could be extracted from a single NS1 hexamer particle, representing a total volume of roughly 75 nm 3 based on the specific volumes of the various lipid species [START_REF] Kumpula | Reconsideration of hydrophobic lipid distributions in lipoprotein particles[END_REF][START_REF] Nagle | Structure of lipid bilayers[END_REF]. These numbers do not take into account molecules of cholesterol and SM that are part of the lipid cargo. Depending on the lipid composition, and the presence of cholesterol in particular [START_REF] Nagle | Structure of lipid bilayers[END_REF], lipid compaction events can occur, suggesting that the whole NS1 lipid cargo can fit well into the 80 nm 3 channel. TG and CE probably constitute the central lipid core while charged lipids such as PC, PE and SM rather occupy the outer layers, at either end of the NS1 channel. As described above, we estimate that there are between 18-27 phospholipids in total (i.e. 9-13 per channel opening). Considering an average surface area of 0.5 nm 2 per phospholipid [START_REF] Kumpula | Reconsideration of hydrophobic lipid distributions in lipoprotein particles[END_REF][START_REF] Nagle | Structure of lipid bilayers[END_REF], these can fill about 60% of the 9 nm 2 triangular surface present at each end of the NS1 channel (Fig. 1), leaving extra space for other polar lipids, such as sphingolipids and glycolipids. Altogether, the amount of lipids extracted from the NS1 particle is compatible with the dimensions of the central channel.

DISCUSSION

The flavivirus nonstructural protein NS1 has long been reported to undergo a complex maturation process. On the one hand, it is attached to intracellular membranes and the surface of infected cells, on the other, it is secreted in the extracellular medium and circulates in the serum of infected patients. In this study, we used a combination of biochemical and structural approaches to investigate the organization and composition of NS1 released by DENV-infected cells.

We obtained a cryo-electron microscopy reconstruction of the secreted form of NS1, which reveals a barrel-like hexameric particle of about 10 nm in diameter, in which the three dimeric rods interact along narrow lateral surfaces and form a wide central channel (Fig. 1). The channel was a most unexpected finding and we investigated its possible contribution to NS1 structure/function. As the contact areas between the dimers appeared insufficient to maintain the hexameric state of NS1 in solution [START_REF] Wodak | Structural basis of macromolecular recognition[END_REF], and were not consistent with the high stability of the protein in an aqueous environment, we searched for the presence of stabilizing elements that would localize within the channel. The dual behavior of the NS1 protein in a TX-114 detergent phase partitioning assay, in which the dimeric subunits partition to the detergent phase just as membrane proteins while the NS1 hexamer remains in the aqueous phase, indicated that amphiphilic molecules such as lipids could possibly be present (Fig. 2). Lipids could indeed be isolated from purified hexamer preparations and we observed a heterogenous population by TLC with one predominant species identified by NMR as TG (Fig. 3). Other NS1-associated lipid species included mono-and diacylglycerol, cholesterol, CE, PC, PE and SM, an overall lipid composition thus very close to that of endogenous HDL circulating in plasma.

Despite the notable homology of their lipid content, DENV NS1 and HDL particles have a fundamentally different protein organization. While HDL particles are composed of narrow ribbons of apolipoprotein A1 that tie up a large lipid bundle [START_REF]Biochemistry of Lipids, Lipoproteins and Membranes[END_REF][START_REF] Silva | Structure of apolipoprotein A-I in spherical high density lipoproteins of different sizes[END_REF][START_REF] Catte | Structure of spheroidal HDL particles revealed by combined atomistic and coarse-grained simulations[END_REF], the NS1 hexamer consists of a thick protein shell organized as an open barrel that can only accommodate a much smaller lipid cargo compared to HDL of similar size.

Accordingly, the density of the NS1 hexamer (1.20-1.23 g/mL) rather corresponds to the smallest subclass of HDL particles (i.e., less than 7 nm in diameter). We estimate that over 70 lipid molecules associate to an NS1 hexamer, which is in agreement with the amount of lipids that could theoretically fit into the central channel [START_REF] Nagle | Structure of lipid bilayers[END_REF]. According to a model of lipid distribution in lipoprotein particles [START_REF] Kumpula | Reconsideration of hydrophobic lipid distributions in lipoprotein particles[END_REF], we hypothesize that TG, along with CE, preferentially constitute the central core of the lipid cargo, around which polar lipids (PC, PE, SM in particular) can pack, their charged heads facing the aqueous environment at either opening of the NS1 channel.

The mechanism by which NS1 acquires its lipid cargo appears to involve an initial interaction of NS1 dimers with intracellular membranes. Since recombinant NS1, lacking the putative glycosylphosphatidylinositol (GPI)-anchor signal present in the downstream NS2A coding region [START_REF] Noisakran | Association of dengue virus NS1 protein with lipid rafts[END_REF][START_REF] Jacobs | Dengue virus nonstructural protein 1 is expressed in a glycosyl-phosphatidylinositol-linked form that is capable of signal transduction[END_REF], shows no difference in lipid binding capacity in comparison to native NS1, a GPI modification cannot account for NS1 attachment to membranes. Early studies following the folding process of NS1 in the endoplasmic reticulum (ER) indicated that the NS1 monomer is water-soluble and becomes membrane-associated once the protein dimerizes [START_REF] Winkler | Newly synthesized dengue-2 virus nonstructural protein NS1 is a soluble protein but becomes partially hydrophobic and membrane-associated after dimerization[END_REF]. We propose that lipidbinding sites form during the dimerization process itself, possibly at the dimer interface (i.e. between the two lobes of the dimer, Fig. 1). The 1:1 molar ratio of TG to NS1 (i.e., six TG molecules per NS1 hexamer, Table 1) suggests that NS1 dimers would bind specifically the hydrophilic head of the lipid. As intracellular TG essentially accumulates between the two leaflets of the ER membrane, from which cytosolic lipid droplets (LD) arise [START_REF] Murphy | Mechanisms of lipid-body formation[END_REF][START_REF] Fujimoto | Cytoplasmic lipid droplets: rediscovery of an old structure as a unique platform[END_REF], one possibility is that NS1 dimers insert into the hemimembrane, thus gaining access to the neutral lipid pool. Such insertion would locally destabilize the organization of lipids, favoring the association of three NS1 dimers around a lipid cargo and its release from the membrane by pinching off, as pictured in Fig. S1. The association of secreted NS1 with TG links the DENV cycle to the biogenesis of LD within the infected cell. This corroborates a recent report indicating that the interaction of the DENV capsid (C) protein with LD is essential for viral replication and virus particle assembly [START_REF] Samsa | Dengue virus capsid protein usurps lipid droplets for viral particle formation[END_REF], thus raising the question as to whether C and NS1 cooperate in any way to hijack nascent LD and support intracellular viral processes.

The discovery that DENV NS1 carries lipids in the extracellular milieu (Fig. S1) also has important pathophysiological implications. Lipoproteins are known to play a key role in vascular homeostasis and defects in lipoprotein functions can affect coagulation and predispose to vascular inflammation and thrombosis [START_REF] Stemerman | Lipoprotein effects on the vessel wall[END_REF][START_REF] Byrne | Triglyceride-rich lipoproteins: are links with atherosclerosis mediated by a procoagulant and proinflammatory phenotype?[END_REF]. By diverting certain lipids from their original fate, NS1 has the potential to interfere with the biogenesis of endogenous lipoprotein particles [START_REF] Blasiole | The physiological and molecular regulation of lipoprotein assembly and secretion[END_REF] or to deregulate the intracellular lipid sensing machinery during entry into target cells [START_REF] Glatz | Lipid sensing and lipid sensors[END_REF][START_REF] Huwiler | Lipids as targets for novel anti-inflammatory therapies[END_REF]. In line with our observations, several reports show that DENV-infected patients who developed DHF/DSS present a decrease of high-and low-density lipoprotein content in plasma, and altered levels of cholesterol and triglycerides [START_REF] Van Gorp | Changes in the plasma lipid profile as a potential predictor of clinical outcome in dengue hemorrhagic fever[END_REF][START_REF] Villar-Centeno | Biochemical alterations as markers of dengue hemorrhagic fever[END_REF][START_REF] Suvarna | Serum lipid profile: a predictor of clinical outcome in dengue infection[END_REF]. Moreover, the nutritional status of children appears to impact the risk of developing a fatal DHF/DSS [START_REF] Kalayanarooj | Is dengue severity related to nutritional status? Southeast Asian[END_REF]53).

The NS1 lipoprotein particle can also directly modulate host response by binding to factors of the complement system [START_REF] Avirutnan | Antagonism of the complement component C4 by flavivirus nonstructural protein NS1[END_REF][START_REF] Kurosu | Secreted complement regulatory protein clusterin interacts with dengue virus nonstructural protein 1[END_REF], either as part of a viral escape mechanism or as a mean to exacerbate inflammation [START_REF] Falgarone | Chapter 8: Clusterin, a multifacet protein at the crossroad of inflammation and autoimmunity[END_REF][START_REF] Heinecke | The HDL proteome: a marker--and perhaps mediator--of coronary artery disease[END_REF].

In conclusion, our study identifies a novel class of lipoprotein particle, exemplified by the barrel-like DENV NS1 protein. The organization of the NS1 hexamer around a "soft" lipid core explains at least in part the lack of success in the crystallization efforts and the limited resolution of the cryo-EM reconstruction. The striking similarities of the NS1 lipid moiety with that of HDL suggests that NS1 has the potential of interfering with the vascular system and inducing important physiological disorders during its circulation in infected patients. The NS1 properties reported here are common to different DENV serotypes, opening promising new therapeutic avenues to fight dengue disease, such as interfering with NS1 secretion or targeting its hydrophobic channel.

EXPERIMENTAL PROCEDURES

Three-dimensional reconstruction of the DENV NS1 hexamer. Cryo-electron microscopy analysis of the NS1 protein sample was carried out with a Philips CM12 transmission electron microscope using a LaB6 filament at 120 kV. Images were analyzed with EMAN and EM software packages. Characteristic class averages representing different orientations of the particles on the micrograph were used to calculate an initial 3D reconstruction, which was further refined, as described in the Supporting Information section, to obtain a final electron density map to a resolution of about 3 nm.

Triton X-114 detergent phase partitioning assay. Triton X-114 detergent phase partitioning was performed on purified preparations of NS1 using a pre-condensed preparation of Triton X-114 at a 1% final concentration. Following an overnight incubation at 4°C, potential aggregates were pelleted by high speed centrifugation (insoluble fraction) before separating the detergent from the aqueous phase at 30°C. In Full experimental procedures and associated references are available as Supporting Information.

a

  set of experiments, proteins from the aqueous and detergent phases were further cross-linked with dimethylsuberimidate (DMS) at 4°C. Proteins were analyzed by SDS-PAGE and Coomassie Blue staining or by mass spectrometry on a PBS II mass reader (Ciphergen Biosystems, Inc.). The DENV envelope protein E was used a control transmembrane protein and detected by Western Blotting. Characterization of the NS1 lipid moiety. Potential lipid components were extracted using a standard solvent extraction procedure. Lipid were analyzed by TLC and stained with iodine or dichlorofluoresceine. Different lipid classes were trans-esterified for their characterization by GLC. Fatty acid methyl esters (FAMEs) were analyzed on an Agilent Technologies chromatograph model 6890 equipped with a BPX 70 fused silica capillary column (60mx 0.25mm i.d., 0.25 µm film thickness). One of the predominant lipid species was also subjected to NMR (see Supplemental Methods). The NMR spectra were acquired on a Bruker 600MHz spectrometer equipped with a triple resonance z-axis gradient cryoprobe at 298K, in CDCl3.

Fig. 1 .

 1 Fig. 1. Cryo-EM analysis of DENV-1 secreted NS1. (A) Representative field

Fig. 2 .

 2 Fig. 2. The NS1 hexamer is composed of amphipathic dimeric subunits.

Fig. 3 .

 3 Fig. 3. The NS1 hexamer carries a lipid cargo rich in triglycerides. (A) Thin layer

Fig. 4 .

 4 Fig. 4. Identification of NS1-associated cholesteryl ester by GLC-MS. (A, B) Gas

Figure 1 Figure 2 AT

 12 Figure 1

Table 1 :

 1 Quantification by gas-liquid chromatography of different lipid species associated to the DENV-1 NS1 hexamer a,b a nmol, relative values using a C17 fatty acid calibration standard b lipids recovered from 200 µg purified protein preparations (approximately 4.5 nM of the 50 kD NS1 protomer; See Supplemental Material) c values reported for two different purified NS1 preparations Triglycerides Mono-/Diglycerides Cholesterol Ester

ACKNOWLEDGEMENTS

We thank Michel Guichardant (INSA Lyon/Institut Multi-disciplinaire de Biochimie des Lipides, Villeurbanne, France) and Paulette Hervé (Institut de Biologie Physico-Chimique, Paris, France) for their contribution to lipid characterization, Claire Huang and Rich Kinney (Center for Disease Control and Prevention, Fort Collins, CO) for providing the DENV-2 16681 cDNA clone, Michèle Bouloy (Institut Pasteur, Paris, France) and Vincent Deubel (Institut Pasteur, Cambodia) for their support. We acknowledge funds from the Institut Pasteur, Paris, France (DARRI 27265).

Author Information Correspondence and requests for materials should be addressed to F.A.R. (felix.rey@pasteur.fr) or M.F. (marie.flamand@pasteur.fr).