V T Nguyen

A F Sommer

K Steger-Jensen

H H Hvolby

The misalignment between hospital planning frameworks and their planning environment -A conceptual matching approach

Keywords: Hospital planning frameworks, hospital planning and control, planning and control frameworks, hospital environment, conceptual matching

Scientifically developed hospital planning frameworks have emerged during the last decade to support and prescribe planning and control practice in hospitals. The three presented frameworks are generally based on manufacturing planning and control frameworks attuned for manufacturing environments. This is critical to the adaptability of the frameworks, since manufacturing environments are focused on optimization of repetitive production processes whereas hospital processes are characterised by complex problem-solving processes with a high degree of uncertainty. In this paper, we identify and describe the misalignment from an environment variables perspective through analysis and comparison of three prominent hospital planning frameworks and hospital planning variables derived from empirical studies in existing research.

Introduction

Inspired from manufacturing industry, scholars from the field of operations management have proposed several frameworks for effective and efficient hospital planning. However, the planning environment of a hospital is different from the planning environment of a manufacturing company, and since research on hospital planning and control is a relatively new research area, little empirical evidence currently supports the applicability of planning and control frameworks in a hospital environment. Thus, the purpose of this paper is to conduct evaluations of adapted frameworks for hospital planning and control in relation to the planning environment of hospitals.

Hence, the main focus of this paper is the relation between the planning environment and the planning framework used for hospital planning in practice. Jonsson and Mattson [START_REF] Jonsson | The implications of fit between planning environments and manufacturing planning and control methods[END_REF] used a similar analysis between planning environment and planning methods in manufacturing environments both empirically and conceptually. However, this paper will only focus on the conceptual matching between planning frameworks and planning environment, where the reasoning is that the planning environment and planning framework must be aligned and match in order to derive value from the planning methods in practice. Based on this notion, the three dominant planning frameworks for hospitals are first presented followed by identification of hospital environment variables through existing research. Afterwards, the appropriateness of the planning frameworks in the hospital environment is conceptually explained.

Conceptual Frameworks for Hospital Planning and Control

During the last decade several hospital planning and control frameworks have been proposed, many of which are based on or heavily inspired by frameworks from production planning and control scholar, like Hax and Meal [START_REF] Hax | Hierarchical integration of production planning and scheduling[END_REF], Silver et al [START_REF] Silver | Inventory management and production planning and scheduling[END_REF], and Vollman [START_REF] Vollmann | Manufacturing Planning and Control for Supply Chain Management: The Definitive Guide for Professionals[END_REF]. Through a broad literature review, three predominant frameworks have been found to highlight the variety between existing frameworks, and are also the most academically recognized; Roth & Van Dierdonck [START_REF] Hulshof | Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS[END_REF], Vissers et al. [START_REF] Adan | Patient mix optimisation in hospital admission planning: a case study[END_REF], and Hans et al. [START_REF] Testi | A three-phase approach for operating theatre schedules[END_REF]. These frameworks have inspired researchers within the field to structure the scope of research studies such as literature reviews [START_REF] Hulshof | Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS[END_REF], adaption to different areas of health care [6] [7] , and further development of the frameworks [START_REF] Brailsford | OR in healthcare: A European perspective[END_REF]. An overview of the characteristics of the three frameworks is presented in Table 1.

Table 1. Characteristics of three dominant hospital planning frameworks

In 1995, Roth & Dierdonck introduced a framework called "Hospital Resource Planning" aimed specifically at healthcare cost reduction through improved hospital planning and control. The framework is based on the introduction of a classification system that identifies the health care services received by patients. The framework is directly inspired by the manufacturing system approach, with materials requirement planning as the backbone. The framework considers both the resource capacity planning and material planning of hospitals and introduces a classification system as the Elective and urgent patients only, integration of all managerial areas in health care delivery, operational integration focus bill of resources to classify products services hospitals provides including calculating prices of services [START_REF] Forgione | DRGs, Costs and Quality of CARE: An Agency Theory Perspective[END_REF]. The study is an exploratory study based on longitudinal data from two hospitals, one 300-bed community hospital and one 1,100-bed teaching hospital. Hence, they acknowledge that the traditional MRP logic has shortcomings. Thus, the key assumptions of the framework are that:

Author

1. Hospitals have superior capabilities for managing capacity and resources. 2. Procedure and treatment protocols are standardized, and variation in patient flow decreases over time. 3. All necessary processes are well defined.

Based on the requirements, the framework will fit a hospital environment with repetitive processes and variables similar to a mass-production environment with mature planning and control processes.

The second framework was developed by Vissers et al. in 2001 [10]. The framework is based on existing literature at the time, partly inspired by De Vries et al. [START_REF] De Vries | Design requirements for health care production control systems[END_REF], which was limited to resources planning and patient flow, including optimization of batching rules for resource utilization, frequency of service to a patient group and size, and composition patient batches. However, most of the literature within hospital planning and control takes point of departure of this paper in relation to their empirical studies such as within operating theatre [START_REF] Van Merode | Enterprise resource planning for hospitals[END_REF] [13] [START_REF] Guerriero | Operational research in the management of the operating theatre: a survey[END_REF]. The framework prescribes identification of planning horizons and different types of decisions that have to be taken in an organization, distinguished by five hierarchical levels including strategic planning, patient volumes planning, resource planning, single patient/patient groups planning. The key assumptions of the framework are that:

1. Hospitals are organized in independent business units. 2. The patient-group is homogeneous 3. One primary predictable and stable process flow of treatment for each patient group.

Thus, this framework is suitable for a predictable process after the treatment plan setup, including low variety in the treatment process, common requirements in quality and service, homogeneous in resource requirement and no requirements for flexibility within the patient-group.

Finally, Hans et al. [START_REF] Hans | A framework for health care planning and control[END_REF] proposed a generic health care framework with the objective to structure the various planning and control functions in a health care system, which is the latest framework among these three The framework is based on hierarchical planning principles divided by planning horizons and is intended to be applicable to any type of health care delivery. Furthermore, Hans et al. [START_REF] Hans | A framework for health care planning and control[END_REF] argue that traditional planning frameworks are often too simplistic as they are oriented towards one managerial area (in particular resource capacity planning or material planning) and neglect the reactive decision functions, which are important given the inherently sto-nature of health care processes. The framework integrates the managerial areas of medical planning, resource capacity planning, materials planning, and financial planning. These are integrated due to the authors' assumption that collaboration and dialogue between all types of managers in healthcare planning is a core mechanism for optimized planning of the entire system. Related to the broad scope of the framework, the prerequisites of the framework are blurred. The framework can be applied at all health care levels from a supply chain of care providers down hospital departments, and thus from a contingent viewpoint, the framework must be tailored according to environment characteristics. Hence, the key assumptions of the framework are that:

1. Planning is an interdependent process between managerial hospital areas. 2. Patient groups are homogeneous across the healthcare system. 3. Two distinctive processes; reactive processes (offline (elective) patient), proactive processes (online (emergency) patient)

Hospital environmental variables

Jonsson and Mattsson [START_REF] Jonsson | The implications of fit between planning environments and manufacturing planning and control methods[END_REF] identify that environmental variables have significant impact on the sustainability of planning methods in manufacturing companies. Therefore, the hospital environmental variables must be identified. All three framework studied are addressing the environmental characteristic, which can be divided into three groups of patient, resource, and hospital process.

In health care, the patient is both a customer and involved in the health care production process [START_REF] Hall | Modeling patient flows through the healthcare system. Patient Flow Reducing Delay[END_REF]. Demand can be defined as the patients' need for health care services, which is partly predictable and partly random too which it is similar to the demand in the industry [START_REF] Womack | Lean thinking: banish waste and create wealth in your corporation[END_REF]. However, the differences between a traditional definition of a product and the patient as a product are that the patient's condition may even change during the time while waiting as well as during the process of treatment [START_REF] Van Merode | Enterprise resource planning for hospitals[END_REF], which is causing the high variability and uncertainty in hospital planning and control. Patients are classified in the range of medical urgency categorization at hospitals, which is based severity of their condition in order to prioritize job task of patients; elective, semi-urgent, and emergency [START_REF] Vos | Evaluating hospital design from an operations management perspective[END_REF]. Looking from the planning point of view, it is frequently interrupted by both the unexpected arrival of critically emergency patients and by the changes of the patients' condition during the admission process [START_REF] Hall | Modeling patient flows through the healthcare system. Patient Flow Reducing Delay[END_REF]. In order to capture patients' needs for health care, it requires a flexibility and agility in operations from the hospital. There is a high variability of patients in hospitals, needing individual hospital health care services, and to some extent they can be grouped based on their medical profile [START_REF] De Vries | Design requirements for health care production control systems[END_REF]. However, patients also need an individual evaluation of the medical profile complexity in order to determine the process of treatment generating variation within a patient group [START_REF] Vissers | A framework for production control in health care organizations[END_REF]. Furthermore, patient volume needs to be considered especially in relation to limited resources [START_REF] De Vries | Design requirements for health care production control systems[END_REF] Hence, the patient variables are deduced to be medical profile complexity, medical urgency, patient variety, demand uncertainty, and patient volume.

The resources in a hospital environment refer to all resources involved in the hospital's planning and control processes. The main resource types include human resources (doctors, nurses, secretaries, porters, and planning personnel), medical equipment (operation packages and medicines ), and facilities (beds and operating theatres) [START_REF] Blake | A goal programming approach to strategic resource allocation in acute care hospitals[END_REF], [START_REF] Harper | A framework for operational modelling of hospital resources[END_REF]. Furthermore, the resource type is dependent on the profiles and experience of the particular resource. For human resources the profile includes, for instance, the nurse profile (operational or ward), and the doctors' clinical profile including their experience. For medical equipment the profile relates to the treatment area, and the experience is for instance the maturity of the medicine technology or treatment, which in some situations is short-lived down to a few hours lifetime from development. Apart from the main resource types, supporting resources are also essential to include as an environmental variable [START_REF] Carter | Diagnosis: mismanagement of resources[END_REF]. Supporting resources include all influencing resources that are not directly part of the hospital process in question including for instance hospital managers and expensive critical care resources. Thus, the hospital resource variables include; resource types, profile, experience, and supporting resources.

The hospital processes can be divided into operation processes and organizational support processes, and operational processes can be further divided into diagnostics process phase and therapy process phase [START_REF] De Vries | Design requirements for health care production control systems[END_REF]. The operation processes are driven by resources such as medical specialists, mainly in charge of the medical treatment, researching and teaching with the aim of providing and developing new medical methods of health care services to increase the inhabitants' health quality of life [START_REF] Kopach-Konrad | Applying Systems Engineering Principles in Improving Health Care Delivery[END_REF] [START_REF] Vissers | A framework for production control in health care organizations[END_REF]. The individual caregivers such as doctors and nurses are patient-centred in their work, where different knowledge and experience has an impact in planning and scheduling incoming patients on top of the degree of complexity of the process itself [START_REF] Williams | Emergency department patient classification systems: A systematic review[END_REF]. The organizational processes are often divided in groups of clinical specialties focusing on single procedures or patient groups in order provide most effective care for the patients. Building up around disciplines enhances the specialization of treatments of different patient group, where the clinical staff develops an in-depth knowledge and experience, resulting in a high quality, fully integrated, operational organization at its disposal [START_REF] Van Merode | Enterprise resource planning for hospitals[END_REF]. Thus, the hospital processes are identified as the diagnostic and therapy processes, process task complexity, interdependency with other resources, and organization support processes. In Table 2, the hospital planning environment variables are presented within the category of patient, resources, and hospital processes based the study of this section.

Conceptual Matching

Overall, frameworks presented above are addressing the hospital environmental variables to some extent, as they all include aspects of patient variables, resources, and the hospital processes. However, the frameworks generally simplify the complexity of the system by only including the simplest variables, omitting, for instance, the condition of the patient, their medical profile, or the variety of patients [START_REF] Brailsford | OR in healthcare: A European perspective[END_REF]. In the three frameworks prioritization of patients is only briefly addressed through the by 'first in first out' principles, whereas the medical urgency is not being addressed. Hans et al [START_REF] Hans | A framework for health care planning and control[END_REF] acknowledge the importance of medical urgency in the planning processes by including both elective patient and emergency patient processes. Even so, uncertainty of the medical profile and the patient's condition is missing along with the need for flexibility in the health care system generating robustness of the framework. On the other hand, Visser et al [START_REF] Vissers | A framework for production control in health care organizations[END_REF] acknowledge the need for high flexibility during the diagnostic process due to high degree of uncertainty, but then choose to limit the framework to the therapy process phase, where the process flow is more predictable. Thus, it indicates that hospital planning can be improved through inclusion of patient variety and medical profile variables in applied hospital planning frameworks.

The theoretical frameworks generally regard resources as a constraint in hospital planning and consider mainly the resource type variable. However, as the environment variables imply, this approach is not sufficient in planning environments with varying resource profiles, varying experience, and the influence of supporting resources. One consequence is the lack of precision in hospital planning practice in situations where these variables are not distributed evenly according to the applied planning model. Hence, it indicates based on the findings that hospital planning accuracy can be improved by inclusion of resource profiles, experience, supporting resources in the hospital planning model oriented around patients.

The planning frameworks in this paper are all hierarchical in nature, where the purpose is to improve coherent and efficient planning of operational hospital processes. However, the point of departure such as objectives and point of view differ. In Visser et al [START_REF] Vissers | A framework for production control in health care organizations[END_REF], one of the assumptions is that hospitals are organized in independent business units, whereas, Hans et al [START_REF] Hans | A framework for health care planning and control[END_REF] emphasize the need to incorporate both multiple managerial areas to capture the complex relationships in health care and the reactive decision functions, which are important the inherently stochastic nature of health care processes. Oppositely, Roth and Van Dierdonck [START_REF] Roth | Hospital Resource Planning: Concepts, Feasibility, and Framework[END_REF] focus at the process flow but disregard the hospital organization. In a sense, the hospital can be categorized as a hybrid organization as introduced by Van Merode et al [START_REF] Van Merode | Enterprise resource planning for hospitals[END_REF], where one part of the organization is of a mechanistic nature suited for rather deterministic processes and another is a more organic part, directed to non-routine, innovative tasks. Thus, suggest for further research that hospital planning include both deterministic and complex process models in accordance with phases, process task complexity, interdependency and influencing support processes'.

The mismatch identified between the theoretical frameworks and theoretically derived environment variables generates incentives for further investigation of how a more general hospital environment relates to applied frameworks in practice. Thus, based on the developed propositions we suggest the following research question for an empirical explorative study: "What is the misalignment between hospital environmental variables and applied planning frameworks, and what are the effects on operational practice? "

Conclusion

This paper contributes to existing research with a conceptual analysis of existing hospital planning and control frameworks, and a set of propositions for further research improving the match between planning frameworks and the hospital environment.

Based on the study, it indicates that hospital planning frameworks need a more integrated holistic planning perspective. It is found that the hospital environmental variables can be grouped into three; patient, resource, and process. However, existing frameworks do not properly addresses these variables in the hospital planning environment, nor do they acknowledge the hybrid nature of hospital organization.

We propose that the existing frameworks are misaligned with several environment variables, and thus further research on alignment is recommended. This includes explorative in-depth studies on the empirical matching between hospital environments and applied planning frameworks.

Table 2 .

 2 Overview of hospital planning environment variables

		Hospital environmental variables
	Patient	Resources	Hospital processes


Michel Gourgand
email: michel.gourgand@isima.fr

Janvier Pensi
email: janvier.pensi@isima.fr

Alain Tanguy
email: alain.tanguy@isima.fr

Programming integrated surgical operations and preventive maintenance activities

Keywords: Surgical unit, operating planning, MIP, heuristics 1

The operating theatre (OT) represents a significant component of the technical means centre. This facility is the largest cost and revenue centre. To be efficient, it needs an optimal operational programme, which takes into account maintenance activities and not only surgical operations. To build such a programme, various methods have been used: mixed integer programming (MIP), three classic heuristics for Bin-Packing and a coupling of the first alternative with a stochastic descent (SD). Then we compare the obtained results from generated data.

Introduction

The renovation of the hospital centre: Laquintinie Hospital of Douala (LHD) in Cameroon has started for a few months with the aim to improve work conditions in the medical system environments. It was launched by the Cameroonian public authorities. Hospital team manager wants to reduce cost and to maximize the level of patient satisfaction. The OT was firstly chosen, to be optimized. Researchers having carried out works on the OT are unanimous: it is an important care provider, which generates large incomes and it is among the most important sources of expenditure. It is consuming between 10% and 15% of the hospital budget [START_REF] Macario | Where Are the Costs in Perioperative Care?: Analysis of Hospital Costs and Charges for Inpatient Surgical Care[END_REF]. Hospital is generally organized in centres of responsibilities [START_REF] Combes | Un environnement de modélisation pour les systèmes hospitaliers[END_REF]. Each one is divided into functional units. Hospital is thus a complex structure, where various functions are provided by a multifield corporation. Managing the OT is hard due to the conflicting priorities and the preferences of its stakeholders [START_REF] Glauberman | Managing the care of health and the cure of disease[END_REF], but also due to highly stochastic OT activities, such as the breakdown of equipment in the operating rooms. The actual realization of the planning and scheduling cannot be perfectly predicted. To improve management of the OT, this randomness has, to be taken into account. The problems the OT are known for the greatest part, and researchers proposed tools of decision-making aid, based on modelling, simulation and optimization. In this paper, we propose a tool to help OT managers in LHD, to improve the realization of the directing programme of surgical operations (DPSO), which takes into account surgical operations but also preventive maintenance activities (MA).

The paper is organized as follow: in the next section, we review the related literature. The third section describes the problem to be handled. In the fourth section, we describe our model. The fifth section presents the generated data and the compared results, finally, we conclude and discuss extensions.

State of the art

The aim of this literature research is to guide the OT managers in programming (planning and scheduling) this facility, by taking into account the impact of equipment breakdowns, on functioning and the benefice of the equipment maintenance. In the 60 last years, researchers focused on the OT management. Regarding planning and scheduling within the OT, [START_REF] Cardoen | Operating room Planning and scheduling: A literature review[END_REF] present a substantive state of the art survey. What the planning concerns, its resolution is quite not easy considering the number of constraints, namely: the intervention duration, the emergencies, the material availability, etc. In this section, we focus on proposed models and methods to solve problems having stochastic aspects. In the related literature, we met the following approaches: mixed integer programming (MIP), heuristics, simulation and Markov theory.

MIP method has been applied in various OT studies, with the aim to optimize the management of this facility. Most of the studies are concerned with the optimization of costs. For instance, minimization of costs of overused or underused operating rooms [START_REF] Jebali | Operating rooms scheduling[END_REF], or with the maximization of the daily benefit [START_REF] Marcon | The operating theatre scheduling: an approach centred on the follow-up of the risk of no realization of the planning[END_REF]. Authors focus on the minimization of the allocated time slots of surgeons [START_REF] Hammami | Une programmation opératoire robuste[END_REF]. To build a stable and flexible operational programme, others [START_REF] Agnetis | Long term evaluation of operating theater planning policies[END_REF] applied MIP method so as to maximize the use of operating rooms.

Heuristics are more and more used. To minimize the costs of the intervention hours, [START_REF] Fei | Ordonnancement journalier dans un bloc opératoire dans le cadre d'une stratégie « open scheduling[END_REF] designed a genetic algorithm coupled with a procedure implementing a taboo search. In [START_REF] Iser | Heuristics for balancing operating room and postanesthesia resources under uncertainty[END_REF], they used heuristics after they identified the problem as a two level Flow-Shop, they minimized the overtime costs in the recovery rooms.

The simulation approach has been used to investigate particular cases, taking advantage of its main asset, i.e., the ability to model specific systems in details. In [START_REF] Hans | Robust surgery loading[END_REF], a Monte Carlo simulation was coupled with a heuristics to maximize the room occupation rate and to minimize the overtime. Authors proposed a planning method to solve emergency problem [START_REF] Lamiri | A stochastic model for operating room planning with elective and emergency demand for surgery[END_REF], they combined a Monte Carlo simulation with MIP, to minimize overtime costs and the operation day costs.

Markov chains have been applied to health care management in various studies too. In [START_REF] Tancrez | Assessing the impact of stochasticity for operating theater sizing[END_REF], they proposed an analytical approach to evaluate the risks in the OT, to determine the number of operations which must be planned, in order to limit overtime.

Concerning the equipment maintenance, industrial managers are unanimous: the zero risk does not exit unfortunately, because human and material failures ever occur.

We focus works that proposed methods for solving maintenance activity problem and its impact to production activities. Several approaches have been developed to address MA problems. In [START_REF] Fitouhi | Optimisation de la planification intégrée de la maintenance préventive et de la production des systèmes multi-états[END_REF], they used mathematical models solved with LINGO and MATLAB, to optimize integrated planning, taking into account preventive MA in production. In industrial systems, production programme could not be designed without regarding MA. This reality must be regarded too in health care systems. We have not found any papers solving together OT optimization and MA. In the present work, we proposed a model that combines the flows of planned surgical operations (SO) and preventive MA.

3

Problem to be handled

The research originates from collaboration with a Cameroonian hospital in the Douala area, from which we will receive real data that can be used to evaluate the reliability of our approach and illustrate its application. This hospital is composed of three surgical units: a gynaecologist-obstetrics unit, an emergencies unit and an OT, this OT is the object of our study. In this hospital, the OT is open five days a week (except for emergencies), for 8 hours a day. It can happen that the duration of an operation overflows closing time. The OT comprises six operating rooms (OR). Four rooms are dedicated to visceral surgery and urology, orthopaedic surgery, orthopaedic surgery and neurosurgery, and endoscopic surgery; the two other rooms are reserved for emergency cases. They are open 24 hours a day. But in this present work, we consider that all those as versatile rooms (able to accommodate any type of surgery). Each OR has his team consists of: 2 nurses, 1 instrumentalist, 1 anesthetist nurse, 1 team leader, 1 health care assistant, 1 anaesthetist doctor who supervises two OR. If the OR is not in service, the team is going to serve in other units. According to the operation, the team is supplemented by a surgeon and his assistant. The number of operations per OR and day does not exceed 4 (except for emergencies). After one operation, the staff has 30 minutes rest. The average time of decontamination is 25 minutes. To realize a daily scheduling in the OR, some criteria are applied: medical or clinical ones and availability of equipment.

Approach

In order to construct the DPSO model, some hypotheses are made: the open strategic planning and scheduling are used, DPSO is focusing only on the OR, the operation day is communicated to each patient, there is the possibility to postpone one planned operation, no criterion is considered to appointing patients, the equipment in the OR is only taken into account, emergencies are not regarded, the operation duration is estimated; health care units, induction and recovery rooms are well sized. We propose a tool to help OT managers in assessing the impact of equipment breakdown by planning DPSO. The aim is to help them, by guiding their decisions at an operational tactical level. We have to assign of MA and SO, it is a similar problem to that of Bin-Packing. It is a NP-hard problem. This problem is solved by three heuristics, a MIP model and the first heuristic variant coupled with a stochastic descent. We established first the algorithms First Fit (FT), Next Fit (NF) and Best Fit (BF). An MA can be planned at the opening time, either just before closing or in midday. So the day of medical use of a room can be cut in one or two periods. The approach is described as follows:

• Insert the MA on the weekly schedule: indicate the day, the room, the starting hour and the end hour of every MA • For every day ─ Operating day planning: indicate the day, the room and the period 1 or 2; ─ Daily sequencing of the SO and the appointment of the surgeons: indicate the room and the time slot, postpone the SO in conflict the next day.

• Publishing of the weekly schedule and the untreated SO

The heuristics principle ones is to affect MA and SO respecting various constraints. We applied followings heuristic variants:

─ Heuristics 1 (H1) affects SO in arrival order, according to the ascending order of the compatible rooms, days and period duration, without exceeding the maximum period use (First Fit Decreasing). ─ Heuristics 2 (H2) proceeds initially by sorting SO in decreasing order of duration, then to their assignment (Next Fit Decreasing). ─ Heuristics 3 (H3) proceeds by sorting SO in decreasing order of duration. Every day and before assignment, rooms are maintained sorted in ascending order of the remaining period duration. It assigns an SO to a compatible room period having the smallest availability duration (Best Fit).

Mathematical formalization

Only

∑ ∑ ; 1 … , 1 … (1)
SO c is allocated in only one room and in only one day

∑ ∑ 1 " # ; $ 1 … %& (2)
Parameter verifier MA m is allocated in only one room and in only one day

∑ ∑ " # ; ' 1 … ( (3)
Integrity constraints

, ) *0, 1,; $ 1 … %&, 1 … , 1 … , ' 1 … ( (4)

Multi-objectives function

We have first to minimize the number of not allocated SO (NNASO), then the number of used room-day couples (NURDC) and finally, the minimum activity time (MAT)

(%& %& -∑ ∑ ∑ " # (5)
A Boolean function

. ∑ / 0 ) *0, 1,, 1 … , 1 … (6)
0 ∑ ∑ . " # (7) (1 min , ∑ 1 -. 10 (8)
The following multi-criterion objective results from the three ones (MCO)

& (%& 100 0 10 (1 (9)
5 Results

Generated data

We illustrate the obtained results from generated data. It is composed of 15 preventive MA and 80 SO. Table 1 indicates following information: for the MA (number, type, start hour, end hour, room, day and the worker). Table 2 contains the data of SO: number, type and duration (Du). The decontamination time is 25 minutes. All durations are given in minutes.

Mixed integer programming

Firstly, we generalized the mathematical model so as to deal with room-dayperiods. Then we used two tools [START_REF] Glpk | [END_REF] (Gl and Gu) and [16] (Lp). Gl (Glpsol) and Gu (Gusek) used different solving options. Table 3 presents results with 60 seconds limited resolution duration. It indicates the number of allocated SO (Naso) and the room utilization duration (Rud). The first objective is studied using a MIP model solved with [START_REF] Glpk | [END_REF] and [16]. The multi-criterion objective is studied using a classic stochastic descent meta-heuristic coupled with a heuristic variant.

Heuristics results

Table 4 presents obtained results with the three heuristics. It gives Naso, the number of used room-days (Nurd) and the number of room day periods Nrdp). H1 does not affect SO better than H3 and H2. H2 affects more and uses in less Nurd than H3. When all SO are allocated, horizon 5, H1 uses less Nurd and less Nrdp than the other heuristics. In MIP, the options used for Gu allocate more SO than Gl, Lp and the three heuristics. The meta-heuristic SD generates scheduling and optimizes the criteria. H1 evaluates them for the tested scheduling. SD gives the best results.

Conclusion and extensions

We proposed a mathematical model for our problem and we implemented and applied exact methods and estimations on generated data. The obtained results are satisfying, especially the multi-criterion stochastic descent. Our tool of decision-making aid will be used in the hospital on real data. The prospects concern the surgical unit programming, the SO planning, the allocation of material resources and the management of the curative maintenance activities.

  one mathematical model is presented, because various mathematical formalizations of the Bin-Packing problem, in one dimension are similar.

	X crd	1 if SO c is allocated the d day in room r; otherwise = 0
	Constraints
	Respect of the room opening duration
	Data, parameter and variable used in the model for the main problem are
	NR	number of operating rooms
	ND	number of days
	NSO	number of surgical operations
	NMA	number of maintenance activities
	DC c	duration of SO c (including decontamination)
	DM m	duration of MA m (including cleaning-up time)
	Q	duration of the room opening (8 h)
	c	index of surgical operations
	r	index of operating rooms
	d	index of working days of the horizon
	m	index of maintenance activities
	Z mrd	1 if MA m is allocated the d day in room r; otherwise = 0

Table 1 .

 1 The MA data

	MAnum MAtype	Sh	Eh	Room	Day	Worker
	1	2	0	45	1	1	X1
	2	1	180	240	2	1	X2
	3	4	450	480	3	1	X3
	4	5	0	60	2	2	X4
	5	7	240	300	4	2	X1
	6	3	0	30	3	2	X2
	7	6	90	140	4	3	X3
	8	6	90	140	1	3	X1
	9	3	0	30	3	3	X4
	10	2	429	474	1	4	X3
	11	1	0	60	2	4	X2
	12	7	420	480	4	4	X1
	13	5	120	180	2	5	X4
	14	5	0	60	3	5	Y1
	15	4	300	350	4	5	Y2

Table 2 .

 2 The SO data

	Sonum Sotype Du Sonum Sotype Du Sonum Sotype Du Sonum Sotype Du 3 90 21 10 90 41 3 90 61 8 120 1 1 120 22 8 120 42 5 150 62 5 150 2 2 90 23 9 120 43 7 90 63 4 120 3 4 120 24 5 150 44 4 120 64 9 120 4 5 150 25 6 90 45 2 90 65 9 120 5 10 90 26 2 90 46 1 120 66 1 120 6 8 120 27 1 120 47 8 120 67 1 120 7 6 90 28 4 120 48 9 120 68 2 90 8 7 90 29 3 90 49 10 90 69 3 90 9 9 120 30 7 90 50 6 90 70 10 90 10 1 120 31 5 150 51 4 120 71 2 90 11 2 90 32 1 90 52 1 120 72 5 150 12 8 120 33 4 120 53 8 120 73 4 120 13 9 120 34 2 90 54 3 90 74 8 120 14 3 90 35 3 90 55 5 150 75 10 90 15 5 150 36 6 90 56 6 90 76 3 90 16 4 120 37 7 90 57 6 90 77 2 90 17 10 90 38 10 90 58 8 120 78 6 90 18 7 90 39 8 120 59 7 90 79 4 120 19 20 6 90 40 9 120 60 7 90 80 5

Table 3 .

 3 MIP results

	Horizon	Gl		Gu		Lp
	Day	Naso	Rud	Naso	Rud	Naso	Rud
	1	21	2415	21	2505	21	2415
	2	38	4550	42	5010	38	4580
	3	57	7155	58	7390	55	7075
	4	71	9335	74	9890	72	9570
	5	80	10700	80	10700	80	10700

Table 4 .

 4 Heuristics results

	Horizon		H1			H2			H3		SD
	Day	Naso Nurd Nrdp Naso Nurd Nrdp Naso Nurd Nrdp Naso
	1	15	6	7	17	6	7	17	6	7	21
	2	32	12	14	35	12	14	34	12	14	40
	3	49	18	20	51	18	20	51	18	20	57
	4	70	24	26	72	24	27	68	24	26	75
	5	80	27	30	80	27	31	80	29	33	80


Valérie Gabelica
email: v.gabelica@iecb.u-bordeaux.fr

Ryuichi Maeda #

Takeshi Fujimoto

||, § , Takashi Murashima #,|| Hidenobu Yaku #

|| Naoki Sugimoto #

Daisuke Miyoshi #,||

Multiple and cooperative binding of fluorescence light-up probe Thioflavin T with human telomere DNA G-quadruplex

Keywords: DNA, deoxyribonucleic acid, ThT, Thioflavin T, HPLC, high performance liquid chromatography, ESI-MS, electrospray ionization mass spectrometry, CD, circular dichroism, G-rich sequence, guanine-rich sequence

ABSTRACT: Thioflavin T (ThT), a typical probe for protein fibrils, also binds human telomeric Gquadruplexes with a fluorescent light-up signal change and high specificity against DNA duplexes. Cell penetration and low cytotoxicity of fibril probes having been widely established, modifying ThT and other fibril probes is an attractive means of generating new G-quadruplex ligands. Thus, elucidating the binding mechanism is important for the design of new drugs and fluorescent probes based on ThT. Here, we investigated the binding mechanism of ThT with several variants of the human telomeric sequence in the presence of monovalent cations. Fluorescence titrations and electrospray ionization mass spectrometry (ESI-MS) analyses demonstrated that each G-quadruplex unit cooperatively binds to several ThT molecules. ThT brightly fluoresces when a single ligand is bound to the G-quadruplex and is quenched as ligand binding stoichiometry increases. Both the light-up signal and the dissociation constants are exquisitely sensitive to the base sequence and to the G-quadruplex structure. These results are crucial for the sensible design and interpretation of G-quadruplex detection assays using fluorescent ligands in general, and ThT in particular. Some of the most frequently encountered repetitive DNA sequences throughout the genomes of most organisms are guanine (G)-rich sequences and their complementary cytosine (C)-rich strands (1). G-rich sequences can adopt a stable four-stranded structure known as the G-quadruplex (Figure 1A) (2-4). Gquadruplexes can be formed with four Hoogsteen-paired coplanar guanines called a G-quartet (Figure 1B) (2). The best known G-rich (G-quadruplex forming) sequence is found at the ends of the chromosomes, the telomeres (5,6). Moreover, bioinformatic studies have identified more than 300,000 G-rich sequences in the human genome (7,8). Interestingly, G-rich sequences are enriched in the untranslated regions of proto-oncogenes, indicating that G-quadruplexes are critical participants in the gene regulation system (9,10). However, the actual roles and functional mechanisms of G-quadruplexes remain unclear.

G-quadruplex ligands developed to investigate the functional roles of G-quadruplexes should have both high affinity for G-quadruplexes and also high specificity against DNA duplexes (11)(12)(13)(14), because the most abundant DNA structure in a living cell is the canonical duplex. Moreover, a bright light-up signal upon G-quadruplex binding is ideal for the detection and imaging of G-quadruplexes (15). Thus, various G-quadruplex probes, which can transduce the binding event into a detectable signal, have been developed (16)(17)(18)(19)(20)(21). However, the use of fluorescent probes for the detection of G-quadruplexes is still insufficient due to difficulties in designing fluorescent ligands that combine high specificity for DNA with significant changes in emission quantum yield upon binding. Moreover, such ligands should be able to penetrate cells and have low toxicity for cellular and in vivo imaging.

Here, we report on Thioflavin T, or "ThT" (4- (3,6- 1C), a new G-quadruplex ligand possessing very unique fluorescent properties.

dimethyl-1,3-benzothiazol-3-ium-2-yl)-N,N- dimethylaniline) (Figure
Mohanty and coworkers recently reported that ThT, which is a typical probe for protein fibrils, binds to Fluorescence spectroscopy. Fluorescence spectra of ThT were measured using Varioskan Flash (Thermo Fisher Scientific K.K., Yokohama, Japan) with a 96-well titer plate (SUMILON S-type plate, Sumitomo Bakelite Co. Ltd., Tokyo, Japan). The fluorescence spectra were obtained by taking the average of three scans made at 0.5-nm intervals from 450 to 700 nm. The excitation wavelength was 450 nm. Before measurement, the samples were heated at 90°C for 10 min, gently cooled at 0.5°C min -1 , and incubated at 25°C for 1 h.

Materials and Methods

Sample

DNA oligonucleotides were titrated with 0.85 µM ThT (ThT by DNA fluorescence titration). The fluorescence intensity at 485 nm (F485) was plotted against the concentration of the DNA oligonucleotide. The data were fitted to Equation ( 1) based on a model that postulates n binding sites of ThT to estimate the apparent dissociation constant (KD) at 25°C:

F485 = a•[ThT] n / (KD + [ThT] n ) + b (1)
where a is the scaling factor, and b is the initial F485 value. The "ThT by DNA" fluorescence titration curves were fitted by KaleidaGraph (Synergy Software, PA).

Reverse titrations, "DNA by ThT", were also carried out. ThT was titrated with 5 µM DNA oligonucleotide at 25°C. The fluorescence intensity at 485 nm was plotted against the concentration of ThT.

Circular dichroism (CD) spectroscopy. The G-quadruplex structure has characteristic peaks in CD spectroscopy. Antiparallel G-quadruplexes show positive and negative peaks around 295 and 265 nm, respectively, whereas parallel G-quadruplex structures show positive and negative peaks around 260 and 240 nm, respectively (25). Moreover, hybrid-type G-quadruplexes show two positive peaks at 290 nm and 265 nm, and a negative peak at 240 nm (26). CD spectra of DNA oligonucleotides were measured for 10 µM DNA total strand concentration using a J-820 spectropolarimeter (JASCO Co. Ltd., Hachioji, Japan) with a 0.1-cm path length quartz cell at 4°C. The CD spectrum was obtained by taking the average of three scans made from 200 to 350 nm. Before measurement, the DNA samples were heated at 90°C for 10 min, gently cooled at 0.5°C min -1 , and incubated at 25°C. The temperature of the cell holder was regulated by a PTC-348 temperature controller (JASCO), and the cuvette-holding chamber was flushed with a constant stream of dry N2 gas to avoid water condensation on the exterior of the cuvette.

Electrospray ionization mass spectrometry (ESI-MS).

All experiments were carried out on a Synapt HDMS mass spectrometer (Waters, Manchester, UK) operated in negative ion mode. The ion mobility mode was turned on, although the mobility data were not used in the present context. The DNA concentration was 5 µM in 100 mM NH4OAc solution, and the concentration of ThT varied between 0 and 60 µM. Typical conditions were, for 22AG, 21G, and 22GT, a cone voltage = 40 V at a backing pressure of 3.3 mbar, and for the duplex and 45G, a cone voltage = 80 V at a backing pressure of 4.8 mbar. The ions were introduced in the IMS cell (N2 at 0.532 mbar) with a bias of 15 V. We tested higher voltages as well, and observed no diminishing of the relative intensities of the complexes relative to the free DNA. Thus, we concluded that loss of the complexes by collision-induced dissociation does not occur in the chosen experimental conditions. The relative areas of the mass spectral peaks corresponding to each complex stoichiometry were extracted using MassLynx 4.0. Using the oligonucleotide dT6 as an internal intensity standard (27), we confirmed that the relative responses of free and bound DNA were similar. In addition, the ratio between the sum of the intensities of all complexes and the intensity of the internal standard did not change by more than 30% in the titrations.

Thus, it is not necessary to consider different mass spectral response factors of the different species. The equilibrium concentrations of each "DNA + nThT" species (where n is the number of bound ThT in each complex) were determined from the peak areas A(DNA + nThT) as follows:

(2)

For 22AG, three independent titration experiments were performed using different source and IMS voltages. The standard errors of the relative intensities extracted from the mass spectra were very small (see Figure 3

below).

Data fitting for multiple binding stoichiometries. With mass spectrometry, the equilibrium concentrations of all species were obtained, and it was therefore possible to determine each consecutive KD separately. These KD's are macroscopic, i.e. they reflect the total concentration of each complex stoichiometry, without distinction of the binding site. These KDn's are defined as:

KDn = [DNA+(n-1)ThT] [ThT] / [DNA+nThT] (3)
These parameters were determined simultaneously by fitting the ESI-MS titration data (concentration of each species at equilibrium as a function of total ThT concentration added) using DynaFit 3.0. (28). The DynaFit program computes the composition of complex mixtures at equilibrium by solving simultaneously the mass balance equations for the component species by using the multidimensional Newton-Raphson method. DynaFit 3.0 was also used to simulate equilibrium concentrations of each species upon titration, again using the KDn values as input parameters. The apparent dissociation constants (KD) of ThT binding with 22AG and other telomeric Gquadruplex sequences were evaluated from the fluorescence titration curves (ThT by DNA) with an assumption that n ThT and one G-quadruplex form the complex. Table 1 summarizes the KD values and Hill constants (n) deduced from fluorescence titration fittings using Equation 1. Since the number of ThT molecules binding to 22AG was evaluated to be 0.83 ~ 1.1, these results suggest a 1:1 binding in G-quadruplex-ThT complexes. However, the Hill constant does not directly reflect the number of ThTs bound to G-quadruplexes. Thus, the stoichiometry will be further discussed with ESI-MS analysis.

Results

ThT

Both the fluorescence light-up signal and the KD of ThT are influenced by the base sequence. This could be due to a specific fluorescence response in the vicinity of certain bases. For example, the KD and fluorescence response are lower with 21G or 22GT than with 22AG (Figure 2A and Table 1). This might suggest that the 5'-adenine is promoting ThT binding and fluorescence. However, the base sequence also has known effects on the G-quadruplex structure. For example, in the presence of KCl, 22AG forms a mixture of predominantly hybrid (3+1) structures (32), whereas 22GT forms a 2-tetrad antiparallel structure.

To understand the extent to which binding and fluorescence depend on the structure, we studied 22AG with different monovalent cations. The circular dichroism (CD) spectra of 10 μM 22AG with different cations (Supporting information Figure S3) are consistent with previous structural studies by NMR and X-ray crystallography and biophysical studies by spectroscopy on structural polymorphisms of 22AG that depend on the coexisting cation (32-34). In the presence of NaCl, 22AG adopts a welldefined three-tetrad antiparallel structure (34). In the presence of NH4OAc (which was used for ESI-MS), the CD spectrum show positive peaks around 295 nm and 260 nm, although of lower intensity than in the presence of KCl. We therefore suppose that in NH4OAc there is a mixture of structures that might include (3+1), 2-tetrad, and 3-tetrad antiparallel G-quadruplexes. In the presence of LiCl, 22AG

did not form a stable G-quadruplex. Fluorescence titration curves of ThT by 22AG in different cations are shown in Figure 2B, and the KD values are also summarized in Table 1. The order of KD values is:

K + < Li + ≈ NH4 + < Na + .
The affinity is independent of the thermal stability of the G-quadruplex (K + > Na + > NH4 + >> Li + ), and these results suggest that ThT preferentially binds to pre-formed (3+1) Gquadruplex folds. In addition, it is interesting that ThT has higher affinity in the presence of LiCl than in the presence of NaCl, although 22AG does not form a stable G-quadruplex in the presence of LiCl. We also found that ThT did not bind to single-stranded ssDNA, as shown Overall, our results suggest that the binding stoichiometry is at least up to 3 or 4 ThT molecules per Gquadruplex unit depending on the sequence.

Cooperative binding of ThT. Positive cooperativity can be inferred by examining the values of the macroscopic dissociation constants and considering statistics. If all binding sites are independent (no cooperativity) and equivalent, each microscopic binding event has an identical microscopic dissociation constant (Kd). The probability of populating the nth site depends on the number of sites remaining available, and therefore decreases with n. As a consequence, the macroscopic KDn values increase as n increases, even though the microscopic constants (Kd) are identical for each binding event. If the sites are independent (no cooperativity) but non-equivalent, the most affine binding sites are more likely to be populated first, so the increase of macroscopic KD with n is even larger. Therefore, any value of KDn smaller than KD(n-1) indicates positive cooperativity. With this reasoning, from Table 2, cooperativity is obvious for the second binding sites of 22AG and 45G, and for the fourth binding site of 22GT.

In all other cases, one has to take into account the number of available sites and binding statistics to detect cooperativity from the consecutive macroscopic KDn's. For example, ESI-MS shows that 22AG possesses at least four ligand binding sites. If the total number of available sites (X) is equal to 4, and if all four sites bind ThT with the same microscopic dissociation constant (Kd), independently of the fact that other sites are already occupied, the four macroscopic dissociation constants KDn can be expressed as: KD1 = (1/4)Kd, KD2 = (2/3)Kd, KD3 = (3/2)Kd, and KD4 = 4Kd (41). So, if KD2 < 8/3 KD1 when X = 4, (or similarly KD2 < 3 KD1 when X = 3), there is positive cooperativity for the binding of the second ligand. The statistics therefore show that the second ligand binding event is cooperative for all Gquadruplexes. With similar reasoning, it can be deduced that the third ThT ligand binding event is also cooperative, although the differences between the four KD values are small.

ThT-induced conformational changes in human telomeric G-quadruplex DNA. It was reported previously that ThT induces changes in the CD spectra of 22AG in the presence of 50 mM KCl, lowering the peak at 270 nm, and thereby indicating a transition towards more "antiparallel" strand arrangements ( 22). Such conformational transitions of G-quadruplexes induced by ligands have been observed. We carried out similar CD titration experiments by ThT on 5 μM 22AG in 100 mM KCl (Figure 5A) and in 100 mM NH4OAc (Figure 5B), and found similar behavior in these conditions. As the latter conditions are similar to those for the ESI-MS titrations described above, each CD spectrum of Figure 5B can be interpreted in light of the concentration of each species in solution (Figure 3D).

In the presence of NH4OAc, the 1:1 complex is already present at 10 µM ThT, but at that ThT concentration the CD spectrum of 22AG is not affected. However, the CD spectrum changes (with a lowering of the band at 265 nm) when 20 µM ThT is added, and according to ESI-MS the 2:1 complex is present in those conditions. At 40 µM and 60 µM ThT, the dip at 265 nm is even deeper. At those concentrations, the relative abundance of the 2:1 complex increases and the 3:1 complex also becomes present. At 60 µM, free 22AG represents less than 20% of the total concentration of 22AG. Thus, 22AG

with two or more ligands bound seems to have a different conformation than free 22AG or 22AG with one ligand bound. This suggests that ligand-induced conformational changes or re-organizations in the stacking and dipole interactions of bases might be responsible for cooperativity, and that conformational changes require two bound ThTs, although further detailed studies are required to reveal how ThT molecules might induce this. This conformational change induced by the higher stoichiometry can explain the cooperative binding of ThT molecules and quenching of fluorescence at higher ThT concentrations as discussed below.

Discussion

Forward and reverse titration experiments give different and complementary information. In the "forward" titration (ligand by DNA), the ligand concentration is smaller than KD1, the major species is the free DNA, and the next most abundant species is the 1:1 complex. As confirmed by simulations (Supporting information Figure S5) using the macroscopic KD's from Table 2, the abundance of other complexes with higher stoichiometries is minor in the conditions used for the "forward" titrations. The plateaus in the forward fluorescence binding curves therefore provide information on the relative response of the 1:1 stoichiometry. In contrast, the "reverse" titration (DNA by ligand) conditions are more favorable to detect the contribution of other complexes with higher stoichiometries. When the ligand concentration increases, the complexes become predominant compared to the free DNA. Such comparisons of both titrations are useful to investigate the ligand binding mechanism.

Moreover, we utilized complementary techniques to obtain information on the ligand binding mode:

(1) Separation techniques sensitive to the mass of the complex (e.g., ESI-MS) can define the stoichiometries formed and the macroscopic KD values for each ligand binding stoichiometry when performed quantitatively.

(2) Spectroscopic techniques sensitive to the ligand environment reveal how the ligand response varies with the ligand binding stoichiometry. In the case of ThT binding to human telomeric G-quadruplexes, fluorescence showed how the response of ThT changes with the total number of ligands bound to the G-quadruplexes. (3) Finally, spectroscopic techniques sensitive to the DNA conformation (e.g., CD spectroscopy for G-quadruplexes) also provide important complementary information on the ligand binding mode, and the conformation of the complexes can be probed only when their abundance is predominant over that of the free DNA.

Here we combined three independent probing techniques (ESI-MS, fluorescence, and CD), and in the case of fluorescence, forward and reverse titrations, to decipher the ligand binding mode of ThT to human telomeric G-quadruplexes. Mass spectrometry reveals each stoichiometry more clearly than any other spectroscopic method. However, it can only be performed in ammonium buffers. Nevertheless, the reverse titrations performed by fluorescence and CD spectroscopy revealed similar behavior of the complexes in NH4OAc and in KCl. Thus, it is reasonable to conclude that similar binding behavior is at work in both buffers, despite the fact that the KD values differ.

ThT binding mode to G-quadruplexes. Although the mechanism of fluorescence light-up of ThT upon biomolecule (protein fibril) binding is still a matter of debate (30,31,(42)(43)(44)(45)(46)(47)(48), it is usually thought that fluorescence light-up of ThT is caused when the rotational motion of the bond between the benzothiazole ring and the dimethylaminobenzene ring is restricted into a planar conformation in the ground and excited states upon binding (47). In addition, the stacking of aromatic amino acids has also been shown to enhance ThT fluorescence, even though ThT may not be constricted to a planar conformation (48).

Here, fluorescence titration experiments showed the influence of the nucleotide sequence on the fluorescence response: the height of the plateau is always lower with 21G and 22GT than with 22AG and the 2-unit G-quadruplexes (46AG and 45G). This observation is valid in both KCl (Figure 3A) and NH4OAc (Figure S6). This highlights the role of the 5' adenine in enhancing the light-up fluorescence.

The presence of the 5'-A, or of a full G-quadruplex unit in the neighborhood of ligand binding, could further restrict the torsional motions of the bond between the rings and be responsible for further enhancement of the fluorescence response with those sequences. Such a fluorescence intensity change depending on the rotation of a bond in a G-quadruplex ligand has been proposed in an acetylene-bridged purine dimer as a fluorescent switch-on probe (20). Fluorescence light-up upon ThT stacking on planar G-quartets is fully consistent with this mechanism.

Moreover, the presence of a 5'-A, or of a full G-quadruplex unit and a TTA linker, increases not only the fluorescence response as discussed above but also the binding affinity of ThT. In contrast, 21G and 22GT give similar KD1 values and fluorescence responses, so one can infer that the 3'-T does not influence the first binding event, but only the fourth one (see Table 2). All these results indicate higher affinity of ThT for the 5'-end than for the 3'-end of the human telomeric sequence. A likely binding site for ThT molecules in human telomeric DNA is around the 5'-A (A1); the neighboring G-quartet plane of G1, G11, G15, and G21; and the neighboring loop composing T12, T13, and A14 (highlighted in Figure 1A). Overall, these results suggest that the stacking of nucleobases influences the fluorescence light-up signal of ThT, as proposed previously for β2-microglobulin fibrils (48).

The presence of the A1 also increases the cooperativity of the second and third binding events. In 22AG, the fourth ligand binding event (KD ≈ 120 µM) appears independent, and may occur on a remote site compared to the first three. Interestingly, a similar KD ≈ 120 µM is also observed for 22GT and 21G, for the third binding site, instead of the fourth site for 22AG. The only difference between 22GT and 21G is the presence of a fourth binding site for 22GT, which shows cooperative binding relative to the third site. A possible interpretation is that the presence of A1 causes three ThT ligands to gather on the 5'-end, whereas G-quadruplexes starting with a guanine bind only two ThT ligands on the 5'-end.

Similarly, the presence of a 3'-T causes two ThT ligands to gather on the 3'-end, whereas sequences terminated by a guanine bind only one ThT ligand. Sequences containing several G-quadruplex units can bind even more ligands. ESI-MS titration experiments of ThT on 45G (which can be seen as one

22GT unit connected to a 22AG unit by a thymine linker) showed a larger number of ThT bindings, up to seven.

Multiple ligand binding to G-quadruplexes is rare for large ligands such as 50), but it is not unprecedented for smaller G-quadruplex ligands. For example, three daunomycin molecules can stack onto one G-quartet in a parallel Gquadruplex (51). In the case of the isoquinoline alkaloid berberine and its derivatives, up to 6 ligand molecules bind to one G-quadruplex with some binding modes (52). Although our DNA sequences, experimental conditions, and detection methods differ from previous reports, the results indicate that a smaller molecule can bind G-quadruplexes with higher stoichiometry. Since ThT is smaller than daunomycin (which has five six-membered rings), it is possible that up to three ThT molecules stack onto a single G-quartet.

Cooperativity can be due to proximal interactions between ligands, to ligand-induced conformational rearrangements, or most likely to both. Proximal interactions between ligands is supported by fluorescence quenching effects. Additional ThT binding events indeed changed the fluorescence of the ThT ligands that were already bound, and this is easier to understand if additional ThT molecules bind in close proximity to the ligands already in place. Ligand-induced conformational changes are also supported by CD spectroscopy. The CD titrations showed that ligand addition leads to structures having a lower proportion of guanine-guanine homo-stacking. This implies either rearrangement of the strand polarity or disruption of G-G homo-stacking by the ligand bindings.

Implications for specific fluorescence light-up detection of G-quadruplexes using ThT. Our results

show that the fluorescence response of ThT is the highest in the 1:1 complex, and quenched in higher ligand binding stoichiometries. As a consequence, quantitative fluorescence light-up detection assays of G-quadruplex presence are better carried out at low ThT concentrations in which the 1:1 complex is the major form of bound ThT. This should also be kept in mind when detecting G-quadruplexes in the presence of other G4-binding molecules, or for the quantitative interpretation of ligand-induced fluorescence displacement assays (19,53). In addition, the macroscopic KD values of 45G, which includes two G-quadruplex units (38-40), are significantly smaller than any value found for 21G, 22GT, or 22AG, which are composed of only one unit each. These results suggest that ThT could have higher affinity for longer telomeric DNA sequences, and be used for their fluorescence detection with a lower detection limit than for single-unit G-quadruplexes. These results are useful for further rational design of G-quadruplex ligands with higher affinity and sensitivity based on ThT.

Conclusion

In this study, we combined three independent probing reported previously. On the other hand, the affinity of ThT to fibril proteins is within the same order of magnitude, and this is sensitive enough for fibril detection in test tubes and living cells. This is partly because the background fluorescence of ThT is exceptionally low, leading to a high signal-to-noise ratio.

In addition, G-quadruplexes show many similarities with protein fibrils in regards to the light-up

Tables and Figures

  the human telomeric G-quadruplex sequence 22AG (dAGGG(TTAGGG)3) with a fluorescent light-up signal change and very low background, and almost no fluorescent response with DNA duplexes (22). Various ThT-DNA G-quadruplex binding modes have been discussed, but the ligand binding stoichiometry and binding mechanisms remain unclear. Also, the origins of the specific fluorescence signal with human telomeric G-quadruplexes compared to DNA duplexes are unknown. We conducted detailed investigations of the ligand binding mode and fluorescence response upon ThT binding with human telomeric DNAs of various nucleotide sequences. Although the fluorescence titration curves of ThT by DNA (22) were confirmed to show a single saturation curve corresponding to a 1:1 complex, our fluorescence reverse titration curves (G-quadruplex by ThT) and electrospray mass spectrometry (ESI-MS) data reveal multiple ligand binding stoichiometries. We discuss in detail how the ligand binding mode influences the ThT fluorescence light-up response.

  preparation. Oligodeoxynucleotides used in this study were purchased from Hokkaido System Science Co., Ltd. (Hokkaido, Japan) after purification by high pressure liquid chromatography (HPLC) or from Eurogentec (Seraing, Belgium) with RP-cartridge-Gold quality. ThT was purchased from Sigma-Aldrich (Tokyo, Japan) and used without further purification. The binding studies of ThT were carried out using G-quadruplex forming DNA sequences: 22AG [dA(GGGTTA)3GGG], 21G [d(GGGTTA)3GGG], 22GT [d(GGGTTA)3GGGT], 46AG [dA(GGGTTA)7GGG], and 45G [d(GGGTTA)7GGG].As controls, we also used the following DNA sequences: -forming sequence, and ssDNA [dT20] as a single-stranded unstructured sequence. Singlestrand concentrations of the DNA oligodeoxynucleotides were determined by measuring the absorbance at 260 nm at high temperature (23). ThT concentration was determined by measuring the absorbance at 412 nm (molar extinction coefficient ε = 32,000 mol -1 cm -1 ) (24). All other chemical reagents were of reagent grade from Wako Pure Chemical Co., Ltd. (Osaka, Japan) or Sigma-Aldrich (Diegem, Belgium) and used without further purification.

  fluorescence light-up with various human telomeric G-quadruplexes. One previous report focused exclusively on the DNA sequence 22AG (22). Figure 2A shows fluorescence titration of 0.85 µM ThT by increasing concentrations of different variants of the human telomeric sequence, and with single-stranded, double-stranded, and triplex DNAs, in KCl. Significant fluorescence enhancement was found with all G-quadruplexes but not for the other DNA structures. The intensity increased by more than 700-fold by addition of 50 μM 22AG. This significant increase is comparable with the fluorescence increase upon fibril protein binding (100-2000 fold) (29-31), and is in line with the 2100-fold fluorescence increase when 3 µM ThT is titrated in 50 mM KCl and 50 mM Tris (pH 7.2) (22). Notably, the fluorescence enhancements were only 6-fold, 12-fold, and 5-fold in the presence of 50 μM dsDNA, tsDNA, and ssDNA respectively, demonstrating the specific fluorescence change of ThT with Gquadruplexes. This drastic fluorescence enhancement allows us to detect the 22AG G-quadruplex with a limit of detection (LOD; 3σ/S, where σ and S are standard deviation and slope of the linear calibration curve) of 5.2 nM with 30 μM ThT at 25°C (Supporting information Figure S1). Equilibrium binding constants with duplex, triplex, and single stranded DNAs could not be obtained from the fluorescence titration experiments. A competition experiment where ThT was titrated by 22AG in the presence of 100 µM dsDNA (Supporting information Figure S2) showed almost the same titration curve as in the absence of dsDNA. This strongly suggests that preferential ThT binding to 22AG compared to duplex DNA is the major reason for the selectivity of the fluorescence detection. The binding selectivity has been further confirmed by ESI-MS (see below).

  Figure 2A. Thus it is possible that ThT can induce 22AG to fold into a G-quadruplex in the presence of LiCl as shown by Mohranty et al. in Tris buffer alone (without cations). Stoichiometry and dissociation constants of ThT binding to telomeric G-quadruplexes. The forward (ThT by DNA) fluorescence titration data (Figure 2) show evidence only for a 1:1 binding stoichiometry.In contrast, reverse titration experiments (fixed DNA concentration titrated by increasing ThT concentrations as shown in Figure3A) revealed bell-shaped curves, with fluorescence light-up at low ThT concentrations, then fluorescence quenching at higher ThT concentrations. The curves cannot be accounted for by a single binding site, and indicate a more complex binding mechanism.ThT-DNA binding was therefore studied by ESI-MS, which is a powerful tool to evaluate binding affinity and stoichiometry(35)(36)(37). Since ESI-MS measurements can only be carried out in a buffer containing NH4 + as a coexisting cation, we confirmed that the fluorescence titration curve obtained in the presence of NH4OAc (Figure3A, black) was similar to that obtained in the presence of KCl (red), although the fluorescence intensity was different. Figure3Bshows ESI-MS spectra of 5 µM 22AG without ThT in NH4OAc at 22°C (room temperature); the m/z peaks annotated 22AG 6-, 22AG 5-, and 22AG 4-correspond to 22AG alone with six, five, and four negative charges, respectively. Figure3Cshows ESI-MS spectra of 5 µM 22AG with 30 µM ThT. Free 22AG is still detected, and new peaks appear, corresponding to 22AG with ThT molecules simultaneously bound. Surprisingly, this spectrum demonstrates that up to four ThT molecules bind the 22AG G-quadruplex. Figure3Dshows the ESI-MS titration curve reconstructed from a series of ESI-MS spectra recorded at various total ThT concentrations. The data were fitted according to a binding model involving up to four consecutive ligand binding events, giving four consecutive macroscopic dissociation constants as defined in Equation 3 (see Materials and Methods). On the other hand, any microscopic binding model that assumed independent binding sites did not fit the data (data not shown), indicating that the binding model for the curve fitting procedure, assuming a cooperativity between the binding events, is reasonable for data analysis.ESI-MS experiments were also carried out with dsDNA, 21G, 22GT, and 45G. Representative spectra are shown in Figure4for dsDNA and 45G, and all reconstructed titrations are shown in Supporting information FigureS4. In contrast to the G-quadruplexes, 5 μM duplex DNA with 30 μM ThT showed only a very weak signal corresponding to a 1:1 complex (Figure4B), confirming the low binding affinity of ThT for duplex DNA. All consecutive dissociation constants obtained by ESI-MS in the 100 mM NH4OAc solution are summarized in Table2. The binding affinities for the 1:1 complexes (KD1) are consistent with those evaluated from the fluorescence titration experiments, indicating that the binding model for the curve fitting and the KD values evaluated from the ESI-MS titrations are appropriate. ESI-MS titrations were not pursued to ThT concentrations higher than 60 µM to minimize the risk of detecting nonspecific binding. The highest KD (156 µM), obtained for dsDNA, was therefore due either to specific binding or can be considered as the limit of nonspecific binding detection for ESI-MS in our experimental conditions.At 60 µM ThT, we detected up to three ligands bound for 21G, up to four with 22AG and 22GT (the first three KD's of 22GT being identical to those of 21G), and up to seven ThT ligands bound to 45G (up to 6 bound ThTs are visible in Figure4D, at 30 µM ThT). 45G contains two G-quadruplex units (38-40).

  techniques (ESI-MS, fluorescence, and CD), and in the case of fluorescence, forward and reverse titrations, to decipher the ThT binding mechanism to human telomeric DNA G-quadruplexes. The mechanism of ThT binding to human telomeric Gquadruplexes can be summarized as follows. Multiple ThT molecules bind to the 5' G-quartet cooperatively. The first bound ThT occurs in a binding pocket formed with the A1 and 5' G-quartet, and produces the brightest fluorescence light-up signal. When present, A1, or in the case of 2-unit sequences, a full G-quadruplex, stacks on ThT, further restraining the rotational motion between the benzothiazole ring and the dimethylaminobenzene ring. The cooperative binding starts with the binding of the second ThT molecule. It is coupled to a fine structural or base rearrangement of the G-quadruplex, and also to changes in the ThT environment that cause a decline of fluorescence response. Since the cell penetration ability and low toxicity of ThT have been confirmed, this type of information is useful to set optimal conditions for cellular imaging by use of ThT. The stoichiometry-dependent fluorescence of ThT will also help current investigations in our laboratory, in which we are designing future G-quadruplex ligands similar to how new fibril probes have been developed based on a ThT scaffold (54). The affinity of ThT with G-quadruplexes (micromolar range) is relatively low compared with G-quadruplex ligands

  ." indicates complex not detected in the mixture of 5 µM DNA and 60 µM ThT.

Figure 1 .

 1 Figure 1. (A) Solution structure of human telomere DNA (4). (B) Chemical structure of a Gquartet. M + indicates a monovalent cation coordinating guanine O6. (C) Chemical structure of ThT.

Figure 2 .

 2 Figure 2. (A) Fluorescence intensity of ThT at 485 nm with various concentrations of 22AG (black circles), 21G (red circles), 22GT (blue circles), 46AG (red diamonds), 45G (black diamonds), ssDNA (black triangles), dsDNA (red triangles), or triplex DNA (green triangles) in 100 mM KCl buffer. (B) Fluorescence intensity at 485 nm of ThT with various concentrations of 22AG in buffers containing 100 mM KCl (black), CH3COONH4 (red), NaCl (blue), or LiCl (green). All measurements were carried out with 0.85 μM ThT at 25°C. Excitation wavelength is 450 nm.

Figure 3 .

 3 Figure 3. Titration of 5 µM 22AG with ThT. (A) Fluorescence titration curve in 100 mM KCl (red) or NH4OAc (black). (B and C) ESI-MS spectra of 22AG with (B) 0 µM ThT and (C) 30 µM ThT, showing up to four ligands bound per 22AG molecule. (D) ESI-MS titration curve with equilibrium concentrations of each form deduced from the relative mass spectral peak areas. The lines correspond to fitting using sequential macroscopic binding events (KDn values are summarized in Table 2). Error bars in (A) and (D) represent standard error of triplicate measurements.

Figure 4 .

 4 Figure 4. ESI-MS spectra of 5 µM dsDNA in the absence (A) and presence (B) of 30 µM ThT, and of 5 µM 45G in the absence (C) and presence (D) of 30 µM ThT. All experiments were carried out in 100 mM NH4OAc solution at 22°C (room temperature).

Table 1 .

 1 Dissociation constants (KD) at 25°C and Hill constants (n) of ThT-G-quadruplex binding. These parameters were evaluated from fluorescence titration (ex = 450 nm, em = 485 nm) of 0.85 µM ThT by various telomeric DNA sequences in buffers with different cations. All cation concentrations are 100 mM.

	Sequence	Cation	K D (µM)	n
	22AG	K +	5.9 ± 0.4	0.98 ± 0.04
	22AG	NH4 +	40 ± 12	0.87 ± 0.09
	22AG	Na +	96 ± 7	1.1 ± 0.1
	22AG	Li +	36 ± 3	0.9 ± 0.1
	21G	K +	45 ± 17	0.90 ± 0.16
	21G	NH4 +	46 ± 5	1.0 ± 0.05
	22GT	K +	22 ± 3	0.93 ± 0.19
	22GT	NH4 +	59 ± 15	0.90 ± 0.08
	45G	K +	7.0 ± 2.6	0.83 ± 0.12
	45G	NH4 +	25 ± 9	0.73 ± 0.09
	46AG	K +	2.7 ± 0.9	0.97 ± 0.05
	46AG	NH4 +	8.8 ± 2.6	0.83 ± 0.09

Table 2 .

 2 Macroscopic, consecutive dissociation constants [KD,n (µM)] determined from ESI-MS in 100 mM NH4OAc solution at 22°C.

	Sequence	K D1	K D2	K D3	K D4	K D5	K D6	K D7
	45G	15	8.0	11	15	30	45	73
		± 0.5	± 0.3	± 0.4	± 0.6	± 1.2	± 3	± 8
	21G	55	86	120	n.d. a	n.d.	n.d.	n.d.
		± 2.1	± 7	± 4
	22GT	58	76	110	80	n.d.	n.d.	n.d.
		± 0.8	± 2.2	± 7	± 10
	22AG	37	32	56	130	n.d.	n.d.	n.d.
		± 0.6	± 0.7	± 1.6	± 9
	dsDNA	160	n.d.	n.d.	n.d.	n.d.	n.d.	n.d.
		± 3

Table of Contents

 of For Table of Contents Use Only

† This work is supported by Grants-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology, Japan (MEXT) [24350089 and 24107525 to D.M.], the Scientific Research on Innovative Areas ''Nanomedicine Molecular Science'' (No. 2306), the ''Strategic Research Foundation at Private Universities'' (2009-2014) (to N.S.), the Kurata Grants, the Kurata Memorial Hitachi Science and Technology Foundation (to D.M.), the Fonds de la Recherche Scientifique-FNRS [FRFC 2.4528.11 to V.G.], and the Japan Society for the Promotion of Science [research fellowship to T.F.].

mechanism of ThT upon binding. Further structural analysis of ThT-G-quadruplex complexes might therefore give new insights into the fluorescence light-up mechanism of ThT upon binding to protein fibrils. As shown for ThT, probes that bind to a broad spectrum of biomolecules can potentially be applied to G-quadruplexes, leading to new G-quadruplex probes and ligands with new structural and mechanistic features.

Supplemental materials

Supplementary Figures: Fluorescence intensity of 30 μM ThT with various concentrations (0 to 0.1 μM) of 22AG (S1); Fluorescence intensity of ThT at 485 nm with various concentrations of 22AG in the presence and absence of dsDNA (S2); CD spectra of 22AG (S3); ESI-MS titrations curves of 5 μM DNA with various concentrations of ThT (S4); Simulation of stoichiometric forms, demonstrating that the 1:1 complex is the main contributor to the fluorescence signal in our fluorescence "forward" titration conditions (S5); Fluorescence intensity of ThT in the presence of DNA in 100 mM CH3COONH4 buffer (S6). This material is available free of charge via the internet at http://pubs.acs.org.

Acknowledgement

The authors thank Ms. Aya Yamamoto for fluorescence measurements.