Samia Maza
email: samia.maza@ensem.inpl-nancy.fr

Dynamic modelling and simulation of fault tolerant systems based on Stochastic Activity Networks

Keywords: Stochastic Actvitiy Networks (SANs), dependability, availability, diagnosis, Monte Carlo simulation, fault-tolerant systems, maintenance

Dependability analysis is crucial to control the risks resulting from failures in modern industrial systems whose complexity increases by leaps and bounds. This paper proposes a modeling approach to construct dynamic models of fault-tolerant (FT) systems based on Stochastic Activity Networks (SANs). This approach allows the systematic inclusion of the diagnosis performances to make the dependability analysis. This SANmodel is used jointly with the Monte Carlo simulation to make a study of the impact of diagnosis' performances on the availability of a FT system when various redundancy and maintenance policies are employed.

Introduction

To meet the productivity and safety requirements in industrial systems, many components are added to the original system or process in order to improve its dependability, such as supervision or diagnosis systems, control systems and reconfiguration or backup systems. This leads to the creation of autonomous and adaptive systems capable of making decisions in a given context. These systems become more and more complex. Consequently, the dependability analysis in those systems becomes a difficult task. The overall system, i.e. the one composed of the process and its supervision and backup subsystems, is called a fault-tolerant (FT) system. The role of the supervision system is to diagnose the occurrence of faults, i.e., to detect and localize the system's faults. However, the backup system allows the reconfiguration when faults occur. These components are used to improve the system's reliability. Nevertheless, they are not totally reliable and therefore, their performances should be taken into account when assessing the dependability of the FT system.

In fact, fault detection is based on some diagnosis algorithm which defines a procedure to detect a failure based on some tuning parameters. The quality of detection depends on those parameters, and so are the actions needed to recover from faults like reconfiguration and maintenance. This shows that the performance of the diagnosis systems should be considered explicitly when evaluating the system's dependability. In the same way, the dependability information and objectives could be considered in fault detection and isolation (FDI) procedures, to improve the decision making.

In other words, the diagnosis issue and dependability analysis should be considered jointly in order to improve the system's performances.

There are few papers in the literature which deal with the interaction between supervision and dependability analysis and design. For example, in [START_REF] Bhushan | Design of sensor location based on various diagnostic observability and reliability[END_REF] the authors consider the sensor placement problem by combining a fault diagnostic observability study by signed directed graphs and reliability information on component failures probability. Weber et al [START_REF] Weber | Component reliability in fault-diagnosis decision making based on dynamic Bayesian networks[END_REF] propose a new approach that improves the performance of the decision making in fault diagnosis by taking into account a priori knowledge of the system/components' reliability. Aslund et al [START_REF] Aslund | Safety analysis of autonomous systems by extended fault tree analysis[END_REF], consider the safety study of FT control systems that include diagnosis subsystem. They propose an approach allowing the inclusion of diagnosis performance in the fault-tree analysis in order to evaluate its impact on the overall system's safety. In the same way, Gustafsson et al, propose a method to optimize the detection threshold based on the previously cited approach [START_REF] Gustafsson | On threshold optimization in fault-tolerant systems[END_REF]. Bonivento et al [START_REF] Bonivento | Reliability evaluation for fault diagnosis in complex systems[END_REF] suggest a procedure for evaluating reliability of diagnostic systems in terms of capability of not generating false alarms and missed diagnosis using statistical tools. Castaneda et al [START_REF] Castaneda | Simulation de Monte Carlo par automate stochastique hybride: application à un cas test pour la fiabilité dynamique[END_REF] address the problem of dynamic reliability estimation of hybrid systems modelled by stochastic hybrid Automata. Some diagnosis performances are included in their simulation study. Guenab et al [START_REF] Guenab | Système tolérant aux défauts : Synthèse d'une méthode de reconfiguration et/ou restructuration intégrant la fiabilité de certains composants[END_REF] work on FT control systems and their reconfiguration. They propose a control strategy which incorporates both the reliability and dynamic performance of the system for control reconfiguration.

The aim of this paper is, in one side to propose a modelling approach which systematically includes the diagnosis system, to make the dependability analysis of FT systems. For that, stochastic activity networks (SANs) are used. The major advantage of such formalism (i.e. SANs) is that it allows the modelling of dynamic systems by modelling all their possible states, but unlike tools such as automata and Markov processes, this can be done simply and in a compact manner. On the other side, the proposed modelling approach is combined with Monte Carlo simulation to assess the system's availability and to study the impact of the supervisor performances. The use of simulation is justified by the fact that the considered systems may have non-homogenous components; active and passive redundancies, repairable components, they may include both discrete and continuous dynamics, etc. This makes the analytical formulation very difficult. The paper deals with repairable FT systems and is organized as follows:

Section 2 is dedicated to the dependability analysis tools and presents a description of the stochastic activity networks in comparison to the well known Petri nets (PNs). The principle of fault detection in diagnosis systems and some of its performances are discussed in section 3. Section 4 is devoted to the presentation the proposed modelling approach. This procedure is applied on an automated thermal process in section 5. This section is also dedicated to the simulation study and results discussion. Finally, the paper is concluded in section 6 where some perspectives are also given.

Dependability analysis

The dependability of a system can be defined as a property that allows its users to have a justified reliance on the service they are delivered. It is described by various non-functional properties such as: reliability, availability, safety and maintenability [START_REF] Laprie | Dependability: Basic concepts and associated terminology[END_REF]. The present paper deals essentially with the availability factor. Availability analysis is performed to verify that an item has a satisfactory probability of being operational, so it can achieve its intended objective [START_REF] Modarres | Reliability engineering and risk analysis[END_REF]. Formally, it is the probability that a system, under stated conditions, is operational at a given time.

There is a variety of classical methods for reliability and availability analysis, which can be either static or dynamic, like fault-trees, Markov processes and Petri nets [START_REF] Villemeur | Reliability, Availability, Maintainability and Safety assessment: methods and techniques[END_REF]. This section presents the stochastic activity networks (SANs). SANs are extension of Petri nets (PNs) [START_REF] Cassandras | Introduction to discrete event systems[END_REF]. A Petri net structure is a directed weighted bipartite graph defined by a 4-tuple PN=(P, T, Pre, Post), where T and P are two distinct sets of vertexes. T={t 1 , t 2 ,…t n } is a set of transitions, and P={p 1 , p 2 , …p k } a set of places. A transition can be seen as an event or an action, and a place represents either a condition for the event or a consequence of it. Pre and Post are two applications, defined from the set of arcs to the set of natural numbers : and  ( , ): is the number of places and models the system's initial state. A marking vector could be written as: , where M(p i ) is the number of tokens in place p i . The SANs were first introduced by Mogavar et al. [START_REF] Mogavar | Performability modeling with stochastic activity network[END_REF], and used as a modelling formalism for the performance and dependability evaluation of a wide range of systems [START_REF] Sanders | Stochastic activity networks: formal definitions and concepts[END_REF]. Hereafter is given an informal definition of SANs in comparison to PNs.

-Places, as for Petri nets, can be seen as a state of the modelled system, and are represented graphically by circles (Fig. 1).

-Activities, like transitions in Petri nets, they are of two kinds: timed and instantaneous. This duration can be either deterministic or stochastic. In Petri nets vocabulary, we say that transitions fire while in SANs vocabulary, activities complete. Each activity has a non-zero integer number of cases probabilities.

-Cases probabilities allow the modelling of the uncertainty about the enabled activity to complete. Here, the term case is used to denote a possible action that may be taken upon the completion of an event such as a routing choice in a network, or a failure mode in a faulty system. Cases are graphically represented by small circles on the right side of an activity (Fig. 1). Moreover, a case probability distribution can depend on the marking of the network when the activity completes.

-Input gates are used to control the activation or enabling of the activities. An input gate is defined by two functions: the predicate and the input function. The enabling predicate of an input gate defines the condition which enables or activates the activity. It depends on the marking of the gate's input places. An activity is enabled when the predicates of all its input gates are true. When the activity completes, the new marking of its input places is defined by the gate's input function. Input gates are graphically represented by triangles, with the flat side inside connected to the activity via its input arc (Fig. 1).

-Output gates are used to change the state of the system when an activity completes. It defines the marking change of the output places thanks to the output function. They are graphically represented by triangles, with the flat side inside connected to the activity via its output arc. Each input or output gate is connected to only one activity. An example of a SAN model with the previously cited elements is given in (Fig. 2). The predicate function of the input gate I_G expresses the enabling condition of the timed activity Timed_A. This latter is enabled if and only if M(P1)=4 and M(P2)=2. When this predicate is true, the activity Timed_A will complete after a delay T which is the time duration of the activity. The input function of I_G specifies the new marking of the places P1 and P2 after the completion of Timed_A, in this example, M(P1)= M(P1)-2 and M(P2)= M(P2)-1. The output function of the output gate O_G defines the marking of place P3 after the completion of Timed_A, here: M(P3)=2*M(P3). The instantaneous activity I_A has three cases probabilities, each related to one place. These probabilities are fixed in this example to P(Case1)=0.3, P(Case2)=0.2 and P(Case3)=0. [START_REF] Bonivento | Reliability evaluation for fault diagnosis in complex systems[END_REF]. This means that I_A has for example 50% chances to complete through case3 and a token will be added to place P2. As said before, these probabilities can depend on the marking of some places like P3, which shows the modelling power of the SANs. Fig. 2 Example of a SAN model with its previously defined elements.

Diagnosis analysis: performance measures

The diagnosis system is a key component in fault-tolerant systems. It allows the detection of faults or abnormal functioning of components under supervision. In FT systems, the fault detection and isolation (FDI) allows reactivity, such as reconfiguration, to avoid losing the system's function, safety, etc.

Consequently, fault detection and isolation (FDI) procedures are essential to improve system's dependability and different approaches are proposed in the literature to design such procedures (see for example [START_REF] Ould Bouamama | Model builder using functional and bond graph tools for FDI deign[END_REF]).

One common way to perform fault detection is to define a set of tests quantities r i , called residuals. A residual is defined as the difference between the measured value of some system's variables and the expected ones, estimated from a system's fault-free model as the observer. In fault-free situations, these residuals should be equal to zero and non-zero otherwise. In practice, systems operate in noisy environment. This may affect the residuals and thus, the decision making. Consequently, the residuals are compared to some tuning parameter called the thresholds instead of zero. If then the test is said to alarm.

i r i J i i J r 
In the residual evaluation problem and according to the statistical theory: the hypothesis "component is Ok" is called the null hypothesis of a test and is denoted [START_REF] Weber | Component reliability in fault-diagnosis decision making based on dynamic Bayesian networks[END_REF][START_REF] Aslund | Safety analysis of autonomous systems by extended fault tree analysis[END_REF]. When the supervised component is Ok and the test produces an alarm, is called false alarm (FA). Not alarm when the supervised component is down is called missed detection (MD). As a conclusion, the residual analysis will produce, according to whether the null hypothesis is true or not, three results: good detection , false alarm and missed detection as shown in table 1.

i 0 i H ) (D ) (FA ) (MD 0 i H is true 0 i H is false 0 i H is accepted: i i J r  Ok i MD 0 i H is rejected: i i J r  i FA i D Table 1. Definition of the diagnosis decisions i i i MD FA D
and ,

The probability of the events FA i and MD i is:

) ( ) ( 0 true H J r P FA P i i i i   and ) ( ) ( 0 false H J r P MD P i i i i  
These probabilities represent measures of the diagnosis performances and the threshold value adjusts the compromise between a small FA probability FA P and MD probability MD P .

The SAN modelling of diagnosis performances for dependability analysis of FT-systems

In the reliability literature, it is always assumed that the detection is made with certainty however; as seen before, the dependability of a system depends on the quality of the detection. Indeed, FDI procedures have a direct impact on the actions made to recover from faults. The dependability of the system is thus tightly related to the performances of the diagnosis system. This section proposes a procedure to model FT-systems using SANs, with a systematic inclusion of the diagnosis performances.

The objective of such modelling is to make reliability/availability analysis. Only components' failures are considered in the paper.

SAN-modelling of physical components

Each physical component j C of the system can be modelled by two places:  

( down j ) M C ( ) ( ) up down j j M C M C 1   .
The two places are linked to each other by a timed activity called " " j fail representing the failure of j C (Fig. 3). This duration can follow any probabilistic distribution such as the exponential distribution function.

If a component is repairable, maintenance action can be modelled by some timed activity connected to

place j C up j
C to add a token in it when the component is repaired. This activity will not be connected to place but to the diagnosis SAN sub-model since maintenance is made only if the supervision system diagnoses the failure. Indeed, if the detection is made instantaneously and with certainty, the activity modelling the repair action will connect place to

SAN-modelling of the diagnosis system

The diagnosis system can be modelled as a generator of three mutually exclusive events: D , FA and MD (Cf. §3). Knowing the probability of these, the supervisor could be modelled by a place, called , with an initial marking of one token (i.e.

ALGO 0 ( ) M ALGO 1  ).
The place ALGO has an output activity, named Diag , with four cases probabilities (Fig. 4). Each place in { , , } is related to one Case (k=1,3) and models the events D, MD and FA respectively. For a specific network's marking, these cases have the probability of their associated event, i.e., P MD , P FA and P D respectively. is added only to satisfy the condition Fig. 4 The SAN-modelling of the diagnosis system and its performance

     otherwise C M if P Case P down k MD 0 1 ) ( ) 1 ( 1 ( ( 4) 1 M D D FA P P if P Case P otherwise          , , and
     otherwise C M if P Case P up k FA 0 1 ) ( ) 2 ( ) 1 dow n k M C       otherwise C M if P Case P down k D 0 1 ) ( ) 3 (
The SAN-model of the diagnosis system satisfies the following:

        1 ) ( ) ( ) ( ) ( 1 ) ( 0 Detection FAlarm MDetection P M P M P M ALGO M ALGO M

The global SAN-modelling

In the final SAN-model, each place in   FAlarm MDetection Detection P P P , , will be related, using logic operators like AND and OR, to activities of other SAN sub-models, like the components' models, to activate them.

For sake of clarity, the combination of such sub-models will be explained on an example in the following section.

Notice here that the SAN-modelling of the system's components is quite similar to the automata modelling since the places of the components' SAN-models are binary and denote the components' states.

But when automata are used, the overall model states number will explode exponentially according to the components number.

Case study

This modelling approach is illustrated hereafter on a simulation example of a heating water process (Fig. 5.a). The aim of such a thermal process is to provide water at a given temperature with a constant flow rate. From the automatic point of view, the process's inputs are the water flow rate Q i and the heater electric power P and the outputs are the water's temperature T and flow rate Q o . The system has two actuators: the valve and the resistors (R1 and R2), and three sensors to measure the temperature (SensorT), the flow rate (SensorF) and the water height (SensorH). Since there is a physical relationship between the flow rate and the water's level [START_REF] Weber | Component reliability in fault-diagnosis decision making based on dynamic Bayesian networks[END_REF], the flow and height sensors are considered in redundancy.

The flow controller can use both of them. A diagnosis system monitors the flow sensor which makes the reconfiguration to the height sensor possible when an alarm is produced.

The SAN modelling of the process

The process described before is composed of two control subsystems: temperature control and flow rate control systems. The functional decomposition and analysis of this automatic system can be made according to this two main control functions (See [START_REF] Conrard | Distributed system design based on dependability evaluation: a case study on a pilot thermal process[END_REF][START_REF] Benard | The Safe-SADT method for aiding designers to choose and improve dependable architectures for complex automated systems[END_REF][START_REF] Marca | SADT: Structured analysis and design techniques[END_REF] for details on functional decomposition and analysis). To achieve any control function, an automated system should be equipped with actuators, sensors and controllers. Communication network and software are not considered in this paper. Thus, if one of these components fails, the automated system will not deliver correctly or not at all the service it was designed for (Fig. 5.b). Based on this idea of functional decomposition, the SAN-model of this automated process can be derived easily as shown on (Fig. 6). The supervised component, here the flow sensor , is assumed repairable and can be maintained each time the supervisor alarms. This action is modelled by the timed activity " " and place " SensorF Repair Maint_SF ". This latter is connected to the instantaneous activities " Maint_1 " and " Maint_2 ". The activity " Maint_1 " can be assimilated to a preventive maintenance action since its input place is " FAlarm " which models a false alarm. While " Maint_2 " has two input places: " " and " " which models the failure detection. Activity "

_ Ko SensorF Detection

Maint_2 " is used in an AND-logic way (i.e.

places " " and " " should be marked together) and can be assimilated to a corrective maintenance action. When the diagnosis system produces an alarm, either correct or false, the FT-system will switch from the flow sensor ( ) to height sensor ( ). When this latter is used in cold passive redundancy, the place " " is connected to activities "

_ nsorF Se Ko Detection SensorF _ ensorH O SensorH S k
Maint_1 " and " Maint_2 " and will be marked each time an alarm occurs. The place " _ FlowMea SensorF sure Ko Sensoring " models the failure of the sensing part in the flow control system. It is connected to activities " " and " ": the first one models the fact that is turned-off for maintenance and its backup is down, and the second one models the missed failure of .

_ Ko

_ SF Ko Sens SensorF orH
The entire flow control system fails (place " _ _ Flow Ctrl Ko 1 VC ") if the valve or the controller or the sensing loop is down. This is modelled by activities " ", " " and " " respectively. These 2 VC 3 VC activities are connected to place" _ _ Flow Ctrl Ko _ System Ko mp " according to the logical operator OR. In the same way, the FT-system fails (place " ") if the temperature control system or the flow control system is failed (resp. activities " Te " and " Flow "). Then the whole FT-system can be maintained through the timed activity " Maintenance " and tokens will be added to all places of type " " if and only if their marking is null (i.e. the component is down). This condition is expressed in the output gate " OG ". Since place " " can receive more than one token, the input gate "

_ Component Ok 1 _ stem Ko Sy
IG " is used to avoid making a maintenance more than once at a time. The input function of gate "IG1" is: M(System_Ko)=0.

To study the impact of the diagnosis performances and recovery actions on the availability of the supervised process, four simulations SAN-models are designed with various redundancy and maintenance policies, using Möbius software tool: -Model A (P&NM): SensorH is in passive cold redundancy and SensorF is not maintained; -Model B (P&M): SensorH is in passive cold redundancy and SensorF is maintained (Fig. 6); -Model C (A&NM): SensorH is in active redundancy and SensorF is not maintained; -Model D (A&M): SensorH is in active redundancy and SensorF is maintained;

Monte Carlo simulation

Monte Carlo simulation is often used to assess the dependability factors estimation. In MC simulation, a model is solved by simulation and is executed multiple times using different randomly generated event streams. Each execution generates a different trajectory through the possible event space of the system, called history. To get statistically significant estimations, it is necessary to generate many trajectories.

Möbius computes confidence intervals as the observations are collected to give an estimate of the accuracy of the calculated estimates. When the desired confidence level for every studied variable is reached, the simulator will stop. The confidence level specifies the desired probability that the exact value of the measured variable will be within the specified interval around the variable estimate. However, the confidence interval specifies the width of the acceptable interval around the variable estimate. In this study, simulations are conducted over at least 5.10 4 and at most 8.10 5 histories. Each history has a duration T h of 20000 time units. The simulator stops if the maximum number of histories is reached, or if the discrepancy between the results is less than 5% with a confidence level of 95%, i.e. 95% of the results are contained within an interval of 5% around their mean value.

Table 2 shows the values of the timed-activities distribution function parameters used in the simulation study. Here, the failures of components follow an exponential distribution with a constant rate j C j C  .

Exponential distribution

Uniform distribution

 Temp  Valve  Ctrl  SensorF  SensorH  1  1  2  2
2.10 -4 5.10 -4 3.10 -4 5.10 -3 5.10 -3 10 25 20 100

Table 2. Distribution functions of the timed activities.

In the simulation models, it is supposed that a maintenance operator and resources are immediately available when a maintenance action is needed. Its duration is supposed to follow a uniform distribution.

The parameters 1

 and 1  (resp.  2 and  2 ) denote the lower and upper bound of the uniform distribution associated with the timed activity Repair for the supervised component (resp. Maintenance for the whole system). The maintenance action may be only an inspection action since false alarms are possible.

Simulation results

The goal of these simulations is to study the impact of the diagnosis system on the mean availability of the The mean availability results for six different values of P FA and P MD are reported in (Fig. 7). It can be seen that globally for all the models, excepted model C, the mean availability increases as the false alarm rate increases. This growth is more significant when maintenance actions are provided to the supervised component (Models B and D). In addition, these models give better results than models A and C. This shows that maintaining the supervised component improves the availability of the whole system. This action is possible thanks to the diagnosis.

The model B, where passive cold redundancy is employed gives the best mean availability. Indeed, the backup sensor (SensorH) is turned-on only when the supervisor alarms, while the supervised sensor is tuned-off to be maintained. Each time this latter is repaired, the system switches back to the principal sensor. The backup sensor is then tuned-off. Such a redundancy allows the persistence of the liquid's flow measurement part and increases its life-time. However, when the backup sensor is used in active redundancy, even if the information provided by it is not used in the control loop, the sensor is still functioning, and may fail as well as the principal sensor. This is why the model D gives a lower availability than model B. Indeed, let's consider the contribution in per cent of the flow sensing part, to failure of the system in comparison to the other components of the flow control system (Fig. 8). False alarm rate (Model D) False alarm rate (Model B) Here, of (Fig. 8) are related to their corresponding activities VCj of (Fig. 6) and express the cumulative contribution of the number of times that these activities have completed leading to the system's failure. The contribution of the flow sensing part, i.e.

, is more important when active redundancy is employed (Fig.

VC

These results show that the combination of the redundancy policy together with the maintenance policy makes one model better than another. They also show that in the studied system, it is better to over detect faults than to miss them, since the availability is improved as the false alarm probability grows. Indeed, when the supervisor alarms, even if the fault is not real, actions like the reconfiguration and repair of the supervised sensor will increase the system's functioning time. Maintaining a non-faulty component can be assimilated to a preventive maintenance action. Such an action will contribute to reduce the total number of repair actions on the whole system as shown in (Fig. 9). Finally, the hypothesis which considers that failure detection is made with certainty is too optimistic as the system's availability is greater than in any other case. In Figs 7 to 9, it corresponds to the case where the FA rate is null.

Conclusion

This paper proposes a method to construct dependability models for fault tolerant systems using the Stochastic Activity Networks. Combined with Monte Carlo simulation, these models allow the evaluation of dependability factors by including events associated with the supervision system and maintenance actions.

This modelling approach was tested on an example of a heating process. A simulation study is made for this FT system, where different redundancy and maintenance policies were employed. Monte-Carlo simulation has been used to evaluate the system's mean availability and to study the impact of diagnosis performances, as well as the redundancy and maintenance policies on the system's availability.

As said in section 3, the diagnosis performances depend on the design parameter called threshold. The next step of this research work is to study the direct impact of this parameter on the system's dependability. For that, there is a need to model the physical process and its supervisor, and to incorporate this diagnosis model into the whole dependability evaluation SAN-model. This may help for choosing the design parameters with respect to the dependability objectives.

     . They define the valuation of arcs relating places to transitions (Pre) and transitions to places (Post). A marked Petri net is a 5-tuple PN m =(P, T, Pre, Post, M 0 ), where M 0 is the initial marking of the PN. It is a k-dimension vector, where k

Fig. 1

 1 Fig. 1 The graphical representation of SANs elements.

  component is up (resp. failed or down). The marking of these places (i.e.

CC 4 . 2 .Fig. 3

 423 Fig.3The SAN modeling of a physical component j C

P

  k) and means no event is produced by the supervisor. Case 4 is connected to the place to conserve the token in it when completes through this case in order to activate "Notice however, that these probabilities depend also on the markings of the SAN model associated with the supervised component/system. Consider for example that a component C is supervised. Then the probability of each case is given by the following:

Fig. 5

 5 Fig.[START_REF] Bonivento | Reliability evaluation for fault diagnosis in complex systems[END_REF] The controlled heating water process and an example of its functional analysis.

1

 1

Fig. 6

 6 Fig. 6 SAN-model of the water-heating process (Model B).

Fig. 7

 7 Fig. 7 The mean availability evolution according to the false alarm rate for: model A (P & NM), model B (P & M), model C (A & NM) and model D (A & M).

0% 0 Fig. 8

 08 Fig. 8 The cumulative contribution to the failure of the FT-system of the flow sensing part ( ) in comparison to the actuating ( ) and control ( ) parts (Models B and D).

  8.a) than passive redundancy (Fig. 8.b). For both models B and D, this contribution decreases as false alarm rate increases.

Fig. 9

 9 Fig. 9 The total number of repair actions of the FT-system according to the false alarm rate for model A (P & NM), model B (P & M), model C (A & NM) and model D (A & M).

  FT-system. Many simulations were conducted with different values of P FA , P MD and P D . For that, P D is set to 80% while the values of P FA and P MD are varied between 1% and 19%. The hypothesis of certainty fault detection is also considered (i.e. P D =1). Even if it's false, this is still widely used in the literature.The statistics on the time occupation of place "System_Ko" are used to calculate the mean availablitiy 'A'.If T System_Ko is the mean time occupation of place "System_Ko", then:

						A	(1  	_ System Ko h T T	) 100 	.
	The simulations were made on an Intel® core™ Duo CPU with a clock speed of 2.26 Ghz. The
	simulation execution time varies, according to simulation data and model, from few seconds to about 50
	minutes.
		95,000%
		90,000%
	Mean availability	75,000% 80,000% 85,000%						P & M P & N M A & M A & NM
		70,000%
		65,000%
		0	1	3	6	1 0	1 5	1 9
				False Alarm rate (%)

FUNDING

This research received no specific grant from any funding agency in the public, commercial, or not-forprofit sectors.

LIST OF CAPTIONS

Fig. 1 The graphical representation of SANs elements. Fig. 2 Example of a SAN model with its previously defined elements.

Fig. 3 The SAN-modelling of a physical component C j .

Fig. 4 The SAN-modelling of the diagnosis system and its performance.

Fig. 5 The controlled heating water process and an example of its functional analysis.


Cell wall from S. pneumoniae strain R36A was prepared as described [6]. Twelve mg of 26 cell wall was suspended in 1.2 ml of water and stirred for 30 min at ambient temperature.

27

The sample was cooled with ice and 750 l of saturated NaHCO 3 solution and 1 ml of 5% 28 freshly prepared, [ 3 H]-labelled acetic anhydride (total 25 mCi) were added and the sample 29 was stirred on ice for 30 min. After the addition of 0.5 ml of 5% unlabelled acetic 30 anhydride the sample was sirred for 30 min on ice and for 1 h at ambient temperature.

31

Thirty ml of water was added and the acetylated cell wall was collected by centrifugation to the deacetylated version of the major monomeric muropeptide, Tri(deAc) (Figure 3D).

4

PgdA was also active against peptidoglycan from S. suis, which has similar basic 5 structure as that from S. pneumoniae, but was inactive against peptidoglycans from S. 463 . Supplemental Table 1 shows the effect of compounds on PgdA activity. 9 10

6 122

 6 Abbreviations:

A c c e p t e d M a n u s c r i p t 4 [

 4 8]. More recently, PgdA from L. monocytogenes has been shown to be able to release 1 acetate from Listeria peptidoglycan and to deacetylate GlcNAc [12]. The growth and 2 morphology of the L. monocytogenes pgdA mutant resembled those of the parental strain. 3 However, the mutant was more susceptible to lysozyme or muramidases and was more 4 prone to EDTA-or Triton X-100-induced autolysis. 5 PgdA is a validated antibiotic target as demonstrated by the reduced virulence of mutant 6 strains of various pathogens [6, 11-15].

A c c e p t e d M a n u s c r i p t 5 (41(

 5 25,000×g, 30 min, 4°C), washed with 6 × 30 ml of water and dried in a SpeedVac. To 1 remove wall teichoic acid 3.5 mg of [ 3 H]-labelled cell wall was incubated with 48% 2 hydrofluoric acid for 48 h at 4°C. The resulting tritiated peptidoglycan was washed as 3 described [6] and had a specific activity of 5.67×10 6 dpm/mg. pgdA gene (nucleotides 735-1389) was amplified from DNA from S. 8 pneumoniae R36A using standard polymerase chain reaction (PCR) procedures. The 9 following oligonucleotides (Biomers, Ulm, Germany) were used: 10 (PgdA735) TCA CATATG ATC CAA TCT TCG TAC TTA CTC and PgdA(1389) CCA 11 GAATTC GTC TGT CAA ATA TCT AAC CAG (NdeI and BamHI restriction sites 12 underlined). 13 The PCR products were digested with NdeI and BamHI (Fermentas, St. Leon-Rot, 14 Germany) and ligated into pET14b plasmid (Novagen, Darmstadt, Germany) digested with 15 the same restriction enzymes. This cloning strategy introduced an N-terminal His-tag. 16 After transformation into E. coli XL1-Blue the plasmid was isolated and transformed into 17 the expression strain E. coli BL21(DE3) pLysS resulting in strain BL21 (DE3) pLysS 18 pET14b-pgdA(735-1389). The product is a truncated PgdA version which lacks the signal 19 peptide and the N-terminal non-catalytic domain. It contains part of the middle domain and 20 the catalytic C-terminal domain and has the sequence MGSHHHHHHSSGLVPRGSHM-21 PgdA 245-463 (numbers are according to amino acid sequence). Upon cleavage with thrombin 22 the recombinant protein has the sequence GSHM-PgdA 245-463 and is designated PgdA 245) pLysS pET14b-pgdA(735-1389)was inoculated into 400 ml of LB medium 28 containing chloramphenicol (34 µg/ml) (Serva, Heidelberg, Germany) and ampicillin (50 29 µg/ml) (Boehringer, Mannheim, Germany) and incubated at 37°C to an A 578 of 0.6. The 30 cells were harvested by centrifugation (20 min, 8300 g) and resuspended in 400 ml LB 31 medium. Isopropyl--D-thiogalactopyranoside (IPTG) was added to a final concentration A c c e p t e d M a n u s c r i p t 6 of 0.4 mM to induce the expression of pgdA(735-1389) and the cells were incubated for a 1 further 3 h. The cells were harvested by centrifugation and resuspended in 25 mM 2 Tris/HCl buffer, pH 7.5, 100 mM NaCl (buffer 1). 3 DNase (0.5 -1 mg) and 1 mM PMSF were added before cell disruption by French press 5 (AIC, Silverspring Maryland, USA) (700 psi). The soluble fraction was collected by 6 centrifugation (90 min, 29,600×g) and was incubated with Co-affinity beads (Talon™, 7 Clonetech, Mountain View, USA) at 4°C for 2 h on a vertical rotating device at 4°C. The 8 beads were transferred to a column and washed with 20 mM Tris/HCl pH 7.5, 0.5 M NaCl, 9 10 mM imidazole followed by elution of the protein with 20 mM Tris/HCl pH 7.5, 0.5 M 10 NaCl, 200 mM imidazole. The protein was dialysed for 18 h against buffer 1 containing 10 11 units of Thrombin (Novagen, Germany) to remove the oligo-His-tag. The protein purity 12 and completeness of thrombin cleavage were verified by sodium dodecyl sulfate-13 polyacrylamide gel electrophoresis (SDS-PAGE) (Supplemental material Figure 1). used in assays with PgdA 245-463 . The samples contained 1 µM 18 enzyme and 5 µM CoCl 2 and had a total volume of 100 µl. The incubation temperature 19 was 37°C. 20 The enzyme activity was determined with chemically [ 3 H]acetylated peptidoglycan (total 21 radioactivity used in each assay was 65000 dpm) from S. pneumoniae R36A in 25 mM 22 Tris-maleate, pH 5.0 (buffer A), 25 mM Tris/HCl, pH 7.0 (buffer B), 25 mM Tris/HCl, pH 23 8.0 (buffer C) or 25 mM sodium borate, pH 9.5 (buffer D). The reaction was terminated by 24 the addition of 100 µl 0.2 M HCl and 5 µl 1 M acetic acid. Acetic acid was extracted with 25 500 µl ethyl acetate and radioactivity in the organic phase was measured by scintillation 26 counting. 27 For testing the maximal release of acetate from the [ 3 H]acetylated peptidoglycan from S. 28 pneumoniae R36A the reaction was performed in 25 mM Tris/HCl pH 7.0 in a total 29 volume of 400 l. After 24 h one quarter of the sample was added to 100 µl 1% 30 cetyltrimethylammonium bromide (CTAB) and incubated for 20 min on ice to precipitate 31 the high-molecular weight peptidoglycan. The mixture was centrifuged (20 min, 16,000×g) A c c e p t e d M a n u s c r i p t 7 and the radioactivity present in 100 µl of the supernatant was quantified by scintillation 1 counting. The remaining of the sample was split into 3 aliquots that received either another 2 M of enzyme, 5 l of peptidoglycan (13000 dpm/µl) or nothing. After 24 h of further 3 incubation the peptidoglycan was precipitated as described above and the radioactivity in 4 the supernatant was measured. 5 PgdA activity was also tested with cell wall, peptidoglycan and muropeptides from S. 6 pneumoniae; peptidoglycan and muropeptides from E. coli, cell wall from S. aureus and 7 from S. carnosus, and N,N,N,N,N-pentaacetylchitopentaose (GlcNAc 5 ) as possible 8 substrates. The incubation was performed in 25 mM Tris/HCl, 5 µM CoCl 2 pH 7.0. 9 Muropeptides and GlcNAc 5 were incubated for 2 h, while cell wall or peptidoglycan was 10 incubated for 16 h. The samples were analysed by HPLC and fractions collected were 11 analysed by mass spectrometry (see below). Cell wall, peptidoglycan and muropeptides 12 from S. pneumoniae, cell wall from S. aureus and S. carnosus were analysed by HPLC as 13 described [17]. Peptidoglycan and muropeptides from E. coli, the muropeptides from S. 14 aureus and GlcNAc 5 were analysed as described [18]. muropeptides were desalted using ZipTip C18 pipette tips (Millipore, 19 Schwalbach, Germany). The samples were eluted with 4 µl 0.5% acetic acid and an aliquot 20 of 0.5 µl was applied on a metal well-plate coated with -cyano-hydroxy-nitrocellulose. 21 MALDI-TOF analysis was performed on the Reflex III Mass Spectrometer (Bruker, 22 Bremen, Germany) using XACQ 4.0 software. The data was processed using the software 23 XMASS 5.1. Offline electrospray MS was performed as published [19]. 24 25 2.7 Determination of the kinetic parameters 26 27 Samples contained 1 µM enzyme and 5 µM CoCl 2 and had a total reaction volume of 100 28 µl. The assay buffer was either 25 mM Tris/HCl pH 7.0 (buffer B) or 25 mM Tris/HCl pH 29 8.0 (buffer C). The kinetic parameters were determined with p-nitrophenyl acetate (pNPA) 30 and 4-methylumbelliferyl acetate (4MUA). The substrate concentrations ranged from 2 -31 10 mM for pNPA and 0.2 -1.0 mM for 4MUA, which is below the K m values (Table 1), 32 A c c e p t e d M a n u s c r i p t 8 due to their insufficient solubility. The assays were performed in buffer B, 10% DMSO in 1 a 96-well microtiter plate for 30 min at 37°C. The kinetic property of 4MUA was also 2 determined in buffer C. The reaction progress was monitored in a Spectra-Max 340 PC 3 (Molecular Devices, Sunnyvale, CA, USA)microplate reader at 405 nm for the pNPA 4 assay and at 354 nm for the 4MUA assay. The kinetic parameters K m and V max were 5 determined by fitting the data to the Michaelis Menten equation by non-linear regression 6 using the Prism 5 software (GraphPad Software, La Jolla, CA, USA). was performed in 25 mM Tris/HCl pH 7.0 at 37°C for 15 min using 1 11 mM 4MUA as a substrate and 1 µM PgdA 245-463 enzyme with or without 1 mM compound 12 dissolved in DMSO. The total volume was 100 µl with a final concentration of 10% 13 DMSO. Some samples contained 0.01% Triton X-100. Reactions were monitored with the 14 BMG Labtech FluoStar Optima microtiter plate reader. The excitation wavelength was 355 15 nm and the emission wavelength was 460 nm. 16 17 2.9 Computer-aided virtual high-throughput screening to identify potential inhibitors of 18 PgdA 19 20 Computational part was done on workstation with 4 dual core AMD Opteron 2.0 GHz 21 processors, 16GB of RAM, 4 320GB hard drives in RAID10 array and nVidia GeForce 22 7900 graphic card. Workstation has Fedora 7 64bit installed. 23 For initial virtual screening the American National Cancer Institute (NCI) bank of 280000 24 compounds was selected. Due to the size of NCI bank of compounds, filtering procedure 25 was applied first to eliminate compounds with unwanted properties. Filtering was based on 26 simple molecular descriptors and was done with program Filter (OpenEye Scientific 27 Software Inc). Choice of descriptors was based loosely on Lipinski rule of five [20]: 28 molecular weight: 200-600 g/mol, number of ring systems: 1-5, number of hetero atoms: 4-29 20, number of H-bond donors: 0-6, number of H-bond acceptors: 0-14; LogP: -3.0 -4.0. 30 Additional filters were used to eliminate insoluble compounds (set to moderate), to 31 eliminate all the compounds with atoms other than H, C, N, O, F, S, Cl and Br, and to A c c e p t e d M a n u s c r i p t 9 eliminate all the compounds with reactive functional groups. Also a function developed by 1 Shoichet, implemented in the program Filter, that eliminates know aggregators and also 2 removes the predicted aggregators was used [21]. Using this function we anticipate 3 eliminating potential promiscuous inhibitors. Result of filtering was a new subset of 4 compounds containing roughly 55000 structures. 5 For docking experiment, FlexX 3.1. (BioSolveIT GmbH) [22] was used on the crystal 6 structure of PgdA from S. pneumoniae co-crystallized with acetate (PDB entry: 2C1G) 7 [16]. The active site was defined as an area of the enzyme within 7.5 Å from the co-8 crystallized acetate. The co-crystallized zinc bound in zinc finger was left in the active site 9 and octahedral coordination was selected. Water 176 was defined as freely rotatable and 10 displaceable so that it can bridge H-bonds if possible, if not FlexX ignores it. Protonations 11 of amino acids and orientations of H-bond donors were setup manually. Since zinc ion is 12 an important part of the active site, docking experiment was set up in such manner that it 13 considers only the solutions that predict the binding of compounds with zinc ion. For base 14 placement Triangle Matching was used and the program generated maximally 200 15 solutions per iteration and 200 per fragmentation. 16 All of the 55000 compounds were then docked in the active site of PgdA and ranked 17 according to their scores. 40 of the best compounds were selected and ordered from NCI, 2 18 were out of stock and 38 compounds were tested in vitro (Supplemental material Table 1). 19 After obtaining in vitro results, a 3D similarity search was performed to obtain compounds 20 similar to the most active compound 2. This time, the combined bank of compounds from 21 suppliers ChemBridge, Maybridge, Asinex and NCI, containing 1.8 million structures, was 22 used. 3D Similarity search was done with ROCS (OpenEye Scientific Software Inc.) [23]. 23 Additionally, LIQUID plugin for PyMol [24] was used to visualize pharmacophoric 24 features of query compound 2 and only the compounds with the same features were 25 selected. Finally, 9 compounds (compounds 3-11) with similar volume, shape and 26 pharmacophoric features as compound 2 were selected and purchased. from E. coli a recombinant, soluble version of PgdA, PgdA 245-463 , 1 containing an N-terminal His 6 -tag, by Co 2+ -affinity chromatography. PgdA 245-463 consists 2 of the catalytic C-terminal domain and part of the middle domain. The oligohistidine tag 3 was removed by cleavage with thrombin (FigureS1). We found that PgdA was able 4 to de-acetylate the GlcNAc 5 (Figure1A) but not GlcNAc (not shown). GlcNAc 5 was 5 almost quantitatively converted to mono-, di-and tri-de-acetylated products as shown by 6 HPLC and MALDI-MS analysis of the products (Figure1assayed the activity of PgdA against peptidoglycan or peptidoglycan 11 fragments (muropeptides) isolated from different bacterial species. The first substrate we 12 tested was peptidoglycan from wild-type S. pneumoniae that has been chemically N-13 acetylated with 3 H-labelled acetic anhydride. PgdA was able to release a small 14 fraction (~4%) of the radioactive acetate from this substrate (Figure2). We would expect 15 to obtain a low percentage of radioactivity release from this substrate because (i) a large 16 proportion (30-50%) of naturally acetylated GlcNAc residues were not labelled and thus 17 their deacetylation is not detectable by the method, and (ii) the chemical acetylation most 18 likely also labels the primary amino groups in the peptide part that cannot be deacetylated 19 by PgdA. In addition, the low percentage of acetate release could be due to a limited 20 number of acetate residues being susceptible to the enzyme or due to the inactivation of the 21 enzyme during the period of the reaction. To test these possibilities we added either a 22 second aliquot of acetylated cell wall or more enzyme at the end of the reaction followed 23 by a second period of incubation. The addition of more enzyme could not release more 24 acetate, whereas more acetate was released upon addition of more peptidoglycan substrate 25 Figure2). We concluded that a limited fraction of GlcNAc residues in chemically 26 acetylated pneumococcal peptidoglycan is prone to deacetylation by PgdA.27Peptidoglycan from wild-type S. pneumoniae contains a fraction of de-acetylated 28 glucosamine residues. When the peptidoglycan was incubated with PgdA 245-463 the 29 percentage of deacetylation did not further increase indicating that the residual GlcNAc 30 residues are not accessible to the enzyme (Figure3A). Interestingly, PgdA 245-463 was active 31 against peptidoglycan isolated from the pgdA mutant strain, which does not contain A c c e p t e d M a n u s c r i p t 11 glucosamine residues (Figure 3B, [5]), demonstrated by the presence of 7 -21% 1 deacetylated muropeptides in the cellosyl-digested peptidoglycan (Figure 3B). MS and 2 MS/MS analysis confirmed that one of the muropeptides generated by PgdA corresponded 3

6in vitro assay 2 3

 2 aureus, S. carnosus or E. coli that have different peptide structure than peptidoglycan from 7 S. pneumoniae. PgdA was inactive against soluble muropeptides from the S. 8 pneumoniae pgdA mutant strain (Figure3C) and from other species (not shown). These 9 data confirm that PgdA has the ability to release in vitro a limited number of acetate 10 residues from pneumococcal peptidoglycan, but not from other species, and that it 11 deacetylates the high-molecular weight substrate but not small, soluble peptidoglycan 12 fragments. The limited activity of PgdA 245-463 against natural substrates was not due to the 13 absence of the N-terminal domain because a soluble version comprising the N-terminal 14 domain and lacking the signal peptide, PgdA 39-463 , did not have higher activity than 15 PgdA (data not shown). 16 17 3.3 Enzyme activity against chromogenic substrates and development of an assay for activity against natural substrates we aimed to develop a 21 simple enzyme assay for screening of inhibitors. For this we have tested various possible 22 chromogenic substrates of PgdA. Indeed, we found that PgdA 245-463 released acetate from 23 p-nitrophenyl acetate (pNPA) or 4-methylumbelliferyl acetate (4MUA). The assays were 24 performed at pH 7.0 for all chromogenic substrates used. For 4MUA the assay was also 25 carried out at pH 8.0. The enzyme reaction for these chromogenic substrates followed the 26 steady-state kinetics described by the Michaelis-Menten equation. The kinetic parameters 27 K m and V max were determined by non-linear regression (Table1). PgdA had the 28 highest k cat /K m value with4MUA (128.61 M -1 s -1 ) compared to the pNPA. With 4MUA as 29 substrate the enzyme exhibited a ca. 6-fold higher k cat /K m value at a pH of 8.Discovery of a new potential inhibitor of PgdA by computational virtual screening and 1 Virtual screening was done on NCI bank of 280000 compounds which was filtered to 4 loosely comply with the Lipinski rule of five [20]. The remaining 55000 compounds were 5 then docked in PgdA active site using FlexX [22]. PgdA has well defined active site with 6 typical zinc finger. Zinc ion is complexed by two histidines (His326 and His330) and 7 aspartic acid (Asp276) (Figure 4A). This structural feature is conserved throughout CE-4 8 family of enzymes. In addition to amino acid residues mentioned above, water 176 and 9 acetate (product of the reaction catalyzed by PgdA) coordinate zinc in octahedral 10 coordination. Acid-base catalysis is performed by two charge relay pairs. One is formed by 11 Asp275 and Arg664 and the other by His417 and Asp 391. Zinc bound water 176 functions 12 as a nucleophile [16]. For docking experiment the active site was defined as an area of the 13 enzyme within 7.5 Å from the co-crystallized acetate. All 55000 pre-filtered compounds 14 were docked and 40 compounds with best scores were ordered from NCI. 38 available 15 compounds were tested in in vitro assay (Supplemental Table 1). Two compounds showed 16 promising inhibitory activities: compound 1 had an IC 50 value of 638 µM and compound 2 17 an IC 50 value of 132 µM. We determined the inhibitory activity of compound 2 also in 18 presence of 0.01% of Triton X-100 and it remained unchanged confirming nonpromiscous 19 mode of inhibition [21]. 20 Our docking study shows that compound 2 complexes zinc with the carboxylic and keto 21 functional groups (Figure 4B). The carboxylic group is placed at the same position as 22 acetate in the crystal structure 2C1G.pdb, while the keto group replaces water 176. The 23 keto group also forms an additional interaction with His417, while the aromatic hydroxyl 24 group forms a H-bond with Asp276. 25 In order to find additional inhibitors with structures related to compound 2, 3D similarity 26 search was performed which involved the complete NCI bank of compounds and some 27 commercially available banks of compounds. 3D similarity search was done with the 28 program ROCS [23]. Results were then visualized with PyMol and only compounds that 29 comply to pharmacophoric model (Figure 4C) were selected. Nine structurally related 30 compounds were found; however, none of them exhibited better inhibitory activity than the 31 parent compound 2 (compounds 3-11, Table2).

  specific sugar N-acetylmuramic acid is GlcNAc with a lactoyl residue 4 at C3 and so the poly-(GlcNAcMurNAc) glycan strand backbone of peptidoglycan is 5 chemically similar to linear oligo-GlcNAc chains, i.e. soluble N-acetylchitooligomers. It is 6 therefore not surprising that the peptidoglycan deacetylase PgdA is related to chitin 7 deacetylases and to nodulation factors that work on oligo-GlcNAc substrates. Moreover, 8 PgdA from S. pneumoniae has been shown to deacetylate GlcNAc 3 [16] and two homologs 9 from B. cereus were active against GlcNAc 2-6 , with highest activity against GlcNAc 4 [8]. 10 Both B. cereus enzymes were inactive against monomeric GlcNAc, whereas PgdA from L. 11 monocytogenes was capable of deacetylating GlcNAc as detected by mass spectrometry 12 analysis [11]. Our data confirmed an activity of S. pneumoniae PgdA against GlcNAc 5 , 13 which was deacetylated to the mono-, di-and tri-deacetylated compounds by the enzyme, 14 and like in the case of the B. cereus enzymes we were unable to detect an activity against 15 monomeric GlcNAc. Together these data suggest that the S. pneumoniae and B. cereus 16 enzymes are capable of deacetylating only a limited number of GlcNAc residues in oligo-17 GlcNAc chains but this might not be a general property of PgdA deacetylases. 18 19 There are few reports on the activity of PgdA enzymes on natural substrates. Two B. 20 cereus PgdA homologs BC1960 and BC3618 deacetylated the muropeptide GlcNAc-21 MurNAc-L-Ala-D-Gln as well as peptidoglycan from H. pylori [8] although H. pylori 22 peptidoglycan contains different peptides than that of B. cereus. S. pneumoniae PgdA was 23 active against pneumococcal peptidoglycan, as shown in this work by the release of 24 radioactive acetate and by the HPLC/MS-detection of deacetylated muropeptides obtained 25 from a PgdA-treated peptidoglycan sample of a pgdA mutant strain. The extent of 26 deacetylation in vitro was lower than that observed in peptidoglycan from wt cells 27 indicating that the enzyme is more active in the cell, perhaps due to its membrane-location 28 in proximity of the newly made peptidoglycan or due to the stimulatory effects of cellular 29 components not present in the in vitro system. Interestingly, PgdA was neither active 30 against soluble peptidoglycan fragments, i.e. the muropeptides, nor against peptidoglycan A c c e p t e d M a n u s c r i p t 14 from other bacterial species. The structural basis for this specificity remains to be 1 determined. 2 PgdA had a higher catalytic efficiency at pH 8.0 as compared to pH 7.0 with 3 4MUA substrate (

  18 potent inhibitors, it provided some insight into which structural elements are beneficial for 19 inhibition of PgdA within this series. Compounds 2-11 share a common 2-benzoylbenzoic 20 acid scaffold with different substituents on benzoyl part of the molecule and all except 21 compounds 3 and 9 show some inhibitory activity. Substitution on the position 4 of the 22 benzoyl part appears to be of significant importance for inhibitory activities of compounds 23 with diethylamino substituent (compound 2) being the most promising. In order to find 24 inhibitors with improved PgdA inhibitory activities, we propose to use compound 2 as a 25 starting point for further medicinal chemistry efforts. We propose the synthesis of extended 26 series of structurally related compounds where 2-(4-(diethylamino)benzoyl)benzoic acid is 27 retained and different substituents are systematically introduced to various positions Vollmer and Alice Eberhardt for cell wall from S. pneumoniae, Teresa 1 de Almeida Figueiredo for cell wall from S. aureus, Jacob Bilboy for the critical reading of 2 the manuscript and OpenEye Scientific Software Inc. for free academic licenses of their 3 software. This work was supported by the European Commission through the EUR-S1 demonstrates completeness of thrombin cleavage of PgdA 245-

  8

11 12Figure 1 . 21 22Figure 2 .Figure 3 .Figure 4 .

 11121234 Figure 1. Deacetylation of GlcNAc 5 by PgdA 245-463 .

  Figure 1

  Figure 3

  Table 1). Based on the suggested reaction mechanism for pneumococcal

	4
	5	PgdA [16] it is possible that the abstraction of a proton from the Zn 2+ -bound water
	6	molecule by Asp275, which initiates the reaction, is more efficient at pH 8.0 than at pH7.0,
	7	but this hypothesis requires further testing. Notably, previous work showed different pH
	8	optima for two peptidoglycan deacetylases from B. cereus. BC1960 has a pH optimum at
	9	pH 6.0, BC3618 at pH 8.0 [8] and the reason for this difference is not known.
	10	Virtual screening methods are increasingly used to identify potential new lead
	11	compounds in drug discovery [25, 26] and have also been successfully used on
	12	antibacterial targets [27]. To date no inhibitor of PgdA has been published. Using
	13	computational structure-based virtual screening followed by biochemical evaluation, we
	14	were able to identify two promising inhibitors of PgdA, compounds 1 and 2 (Table 2), with
	15	IC 50 values of 584 µM and 130 µM, respectively. Our enzyme assays developed could also
	16	be used for high-throughput screening. The more potent inhibitor 2 was selected as a
	17	starting point for further computational similarity search in order to rapidly identify a
		series of structurally related compounds. Although this similarity search did not yield more

Table 1 .

 1 Activity of PgdA 245-463 against artificial substrates.

	1

Table 1

 1

Acknowledgements

31

*Graphical Abstract