Studzinski Filipo

Perotto
email: fsperotto@inf.ufrgs.br

Jean-Christophe Buisson
email: buisson@enseeiht.fr

Luis Otávio Alvares
email: alvares@inf.ufrgs.br

Constructivist Anticipatory Learning Mechanism (CALM) -dealing with partially deterministic and partially observable environments

This paper presents CALM (Constructivist Anticipatory Learning Mechanism), an agent learning mechanism based on a constructivist approach. It is designed to deal dynamically and interactively with environments which are at the same time partially deterministic and partially observable. We describe in detail the mechanism, explaining how it represents knowledge, and how the learning methods operate. We analyze the kinds of environmental regularities that CALM can discover, trying to show that our proposition follows the way towards the construction of more abstract or high-level representational concepts.

Introduction

The real world is a very complex environment, and the transition from sensorimotor intelligence to symbolic intelligence is an important aspect to explaining how human beings successfully deal with it [START_REF] Piaget | Construction of Reality in the Child[END_REF]). The problem is the same for a situated artificial agent (like a robot), who needs to incrementally learn the observed regularities by interacting with the world.

In complex environments (Goldstein 1999), special 'macroscopic' properties emerge from the functional interactions of 'microscopic' elements, and generally these emergent characteristics are not present in any of the sub-parts that generate it. The salient phenomena in this kind of environment tend to be related to high-level objects and processes [START_REF] Thornton | Indirect sensing through abstractive learning[END_REF], and in this case it is plainly inadequate to represent the world only in terms of primitive sensorimotor terms [START_REF] Drescher | Made-Up Minds: A Constructivist Approach to Artificial Intelligence[END_REF]).

An intelligent agent (human or artificial) who lives in these conditions needs to have the possibility to overpass the limits of direct sensorial perceptions, organizing the universe in terms of more abstract concepts. The agent needs to be able to detect highlevel regularities in the environment dynamics, but it is not possible if it is closed into a rigid 'representational vocabulary'.

The purpose of this paper is to present an agent learning architecture, inspired in a constructivist conception of intelligence [START_REF] Piaget | Construction of Reality in the Child[END_REF], capable of creating a model to describe its universe, and using abstract elements to represent unobservable properties.

The paper is organized as follows: Section 2 and 3 describe both the agent and the environment conceptions. Section 4 and 5 show the basic CALM mechanism, respectively detailing how to represent the knowledge, and how to learn it. Section 6 presents the way to deal with hidden properties, showing how these properties can be discovered and predicted through synthetic elements. Section 7 presents example problems and solutions following the proposed method. Section 8 compares related works, and section 9 finalizes the paper, arguing that this is an important step towards a more abstract representation of the world, and pointing some next steps.

Agent and Environment

The concepts of agent and environment are mutually dependent, and they need to be defined one in relation to the other. In this work, we adopt the notions of situated agent and properties based environment.

A situated agent is an entity embedded in and part of an environment, which is only partially observable through its sensorial perception, and only partially liable to be transformed by its actions [START_REF] Suchman | Plans and Situated Actions[END_REF]. Due to the fact that sensors will be limited in some manner, a situated agent can find itself unable to distinguish between differing states of the world. A situation could be perceived in different forms, and different situations could seem the same. This ambiguity in the perception of states, also referred to as perceptual aliasing, has serious effects on the ability of most learning algorithms to construct consistent knowledge and stable policies [START_REF] Crook | Learning in a State of Confusion: Perceptual Aliasing in Grid World Navigation[END_REF].

An agent is supposed to have motivations, which in some way represent its goals. Classically, the machine learning problem means enabling an agent to autonomously construct polices to maximize its goal reaching performance. The model based strategy separates the problem in two parts: (a) construct a world model and, based on it, (b) construct a policy of actions.

CALM (Constructivist Anticipatory Learning Mechanism) responds to the task of constructing a world model. It tries to organize the sensorial Berthouze, L., Prince, C. G., Littman, M., Kozima, H., and Balkenius, C. (2007) information in a way to represent the regularities in the interaction of the agent with the environment.

There are two common ways to describe an environment: either based on states, or based on properties. A states based environment can be expressed by a generalized states machine, frequently defined as POMDP [START_REF] Singh | Learning Predictive State Representations[END_REF] or as a FSA [START_REF] Rivest | Diversity-based inference of finite automata[END_REF]. We define it as Є = {Q, A, O, δ, γ} where Q is a finite not-empty set of underlying states, A is a set of agent actions, O is a set of agent observations, δ : Q × A → Q is a transition function, which describes how states change according to the agent actions, and γ : Q → O is an observation function, which gives some perceptive information related to the current underlying environment state.

A properties based environment can be expressed by ξ = {F, A, τ} where F is a finite not-empty set of properties, composed by F (p) , the subset of perceptible or observable properties, and F (h) , the subset of hidden or unobservable properties, A is a set of agent actions, and τ (i) :

F 1 × F 2 × ... × F k × A → F i
is a set of transformation functions, one for each property F i in F, describing the changes in property values according to the agent actions.

The environment description based on properties (ξ) has some advantages over the description based in states (Є) in several cases. Firstly because it promotes a clearer relation between the environment and the agent perception. In general we assume that there is one sensor to each observable property. Secondly, because the state identity can be distributed in the properties. In this way, it is possible to represent 'generalized states' and, consequently, compact descriptions of the transformation functions, generalizing some elements in the function domain, when they are not significant to describe the transformation. A discussion that corroborates our assumptions can be read in (Triviño-Rodriguez and Morales-Bueno 2000).

The most compact expression of the transition function represents the environment regularities, in the form λ * (i) :

F 1 |ε × F 2 |ε × ... × F k |ε × A|ε → F i .
This notation is similar to that used in grammars, and it means that at each property j, we can consider it for the domain or not (F j |ε).

Types of Environments

We adopt the properties based description (ξ), defining 3 axis to characterize different types of environments. The axis ∂ represents the environment determinism in the transformations, the axis ω indicates the perceptive accessibility that the agent has to the environment, and the axis ϕ represents the information gain related to the properties.

The determinism axis level (∂) is equivalent to the proportion of deterministic transformations in τ in relation to the total number of transformations. So, in the completely non-deterministic case (∂ = 0), the transformation function (τ) to any property i needs to be represented as

F 1 × F 2 × ... × F k × A → Π(F i ),
where Π(F i ) is a probabilistic distribution. On the other hand, in the completely deterministic case (∂ = 1), every transformation can be represented directly by

F 1 × F 2 × ... × F k × A → F i .
An environment is said partially deterministic if it is situated between these two axis extremities (0 < ∂ < 1). When ∂ = 0.5, for example, half of the transformations in τ are deterministic, and the other half is stochastic.

It is important to note that a single transition in the function δ of an environment represented by states (Є) is equivalent to k transformations in the function τ of the same environment represented by properties (ξ). So, if only one transformation that integrates the transition is non-deterministic, all the transition will be nondeterministic. Conversely, a non-deterministic transition can present some deterministic component transformations. This is another advantage of using the properties representation, when we combine it with a learning method based on the discovery of deterministic regularities.

The accessibility axis level (ω) represents the degree of perceptive access to the environment. It is equivalent to the proportion of observable properties in F in relation to the total number of properties.

If ω = 1 then the environment is said completely observable, which means that the agent has sensors to observe directly all the environment properties. In this case there is no perceptual confusion, and the agent always knows what is its current situation. If ω < 1, then the environment is said partially observable. The lesser ω, the higher the proportion of hidden properties. When ω is close to 0, the agent is no longer able to identify the current situation only in terms of its perception.

In other words, partially observable environments present some determinant properties to a good world model, which cannot be directly perceived by the agent. Such environments can appear to be arbitrarily complex and non-deterministic on the surface, but they can actually be deterministic and predictable with respect to unobservable underlying elements [START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF].

There is a dependence relation between these two axis -accessibility and determinism. The more an agent has sensors to perceive complex elements and phenomena, the more the environment will appear deterministic to it.

Finally, the informational axis level (ϕ) is equivalent to the inverse of the average number of generalizable properties to represent the environment regularities (λ * ), divided by the total number of properties in F. The greater is ϕ (rising to 1), the more compactly the transformation function (τ) can be expressed in terms of regularities (λ * ).

In other words, higher levels of ϕ mean that the information about the environment dynamics is concentrated in the properties (i.e. there is just a small sub-set of highly relevant properties for each prediction), and lower levels of ϕ indicate that the information about the dynamics is fuzzily distributed over all the set of properties, and in this case the agent needs to describe the transformation in function of almost all properties.

Learning methods based on the discovery of regularities can be very efficient in environments where the properties are highly informative.

The Basic Idea

In this section we present the basic CALM mechanism, which is developed to model its interaction with a completely observable but partially deterministic environment (COPDE), where ω=1, but ∂<1 and ϕ<1.

CALM tries to construct a set of schemas to represent perceived regularities occurring in the environment through its interactions. Each schema represents some regularity checked by the agent during its interaction with the world. It is composed by three vectors: Ξ = (context + action → expectation). The context and expectation vectors have the same length, and each of their elements are linked with one sensor. The action vector is linked with the effectors.

In a specific schema, the context vector represents the set of equivalent situations where the schema is applicable. The action vector represents a set of similar actions that the agent can carry out in the environment. The expectation vector represents the expected result after executing the given action in the given context. Each element vector can assume any value in a discrete interval defined by the respective sensor or effector.

Some elements in these vectors can undertake the undefined value. For example, an element linked with a binary sensor must have one of three values: true, false or undefined (represented, respectively, by '1', '0' and '#'). In both the context and action vectors, '#' represents something ignored, not relevant to make the anticipations. But for the expectation vector, '#' means that the element is not deterministically predictable.

The undefined value generalizes the schema because it allows to ignore some properties to represent a set of situations. There is compatibility between a schema and a certain situation when the schema's context vector has all defined elements equal to those of the agent's perception. Note that compatibility does not compare the undefined elements. For example, a schema which has the context vector = '100#' is able to assimilate the compatible situations '1000' or '1001'.

The use of undefined values makes possible the construction of a schematic tree. Each node in that tree is a schema, and relations of generalization and specialization guide its topology (quite similar to decision trees or discrimination trees). The root node represents the most generalized situation, which has the and action vectors completely undefined. Adding one level in the tree is to specialize one generalized element, creating a branch where the undefined value is replaced by different defined values. This specialization occurs either in the context vector or in the action vector. The structure of the schemas and their organization as a tree are presented in Figure 1. The context in which the agent is at a given moment (perceived through its sensors) is applied in the tree, exciting all the schemas that have a compatible context vector. This process defines a set of excited schemas, each one suggesting a different action to do in the given situation. CALM will choose one to activate, and then the action proposed by the activated schema will be performed through the agent's effectors. The algorithm always chooses the compatible schema that has the most specific context, called decider schema, which is the leaf of a differentiated branch. Each decider has a kind of episodic memory, which represents (in a generalized form) the specific and real situations experimented in the past, during its activations.

### # ### ### 0 #0# ### 1 111 0## 0 000 1## 0 10# context action expectation

Learning Methods

The learning process happens through the refinement of the set of schemas. The agent becomes more adapted to its environment as a consequence of that. After each experienced situation, CALM checks if the result (context perceived at the instant following the action) is in conformity to the expectation of the activated schema. If the anticipation fails, the error between the result and the expectation serves as parameter to correct the tree or to adjust the schema. combines top-down and bottom-up learning strategies. In the schematic tree topology, the context action vectors are considered together. This concatenated vector identifies the node in the tree, which grows up using the top-down strategy.

The agent has just one initial schema. This root schema has the context vector completely general (without any differentiation, ex.: '#####') and expectation vector totally specific (without any generalization, ex.: '01001'), created at the first experienced situation, as a mirror of the result directly observed after the action.

The context vector will be gradually specialized by differentiation. In more complex environments, the number of features the agent senses is huge, and, in general, only a few of them are relevant to identify the situation class (1 > ϕ >> 0). In this case, a top-down strategy seems to be better, because there is a shorter way beginning with an empty vector and searching for these few relevant features to complete it, than beginning with a full vector and having to eliminate a lot of useless elements.

Selecting the good set of relevant features to represent some given concept is a well known problem in AI, and the solution is not easy, even to approximated approaches. As it will be seen, we adopt a kind of forward greedy selection [START_REF] Blum | Selection of relevant features and examples in machine learning[END_REF].

The expectation vector can be seen as a label in each decider schema, and it represents the predicted anticipation when the decider is activated. The evolution of expectations uses a bottom-up strategy. Initially all different expectations are considered as different classes, and they are gradually generalized and integrated with others. The agent has two alternatives when the expectation fails. In a way to make the knowledge compatible with the experience, the first alternative is to try to divide the scope of the schema, creating new schemas, with more specialized contexts. Sometimes it is not possible and the only way is to reduce the schema expectation.

Three basic methods compose the CALM learning function, namely: differentiation, adjustment and integration. Differentiation is a necessary mechanism because a schema responsible for a context too general can hardly make precise anticipations. If a general schema does not work well, the mechanism divides it into new schemas, differentiating them by some element of the context or action vector.

In fact, the differentiation method takes an unstable decider schema and changes it into a two level sub-tree. The parent schema in this sub-tree preserves the context of the original schema. The children, which are the new decider schemas, have their context vectors a little bit more specialized than their parent. They attribute a value to some undefined element, dividing the scope of the original schema. Each one of these new deciders engages itself in a part of the domain. In this way, the previous correct knowledge remains preserved, distributed in the new schemas, and the discordant situation is isolated and treated only in its specific context. Differentiation is the method responsible to make the schematic tree grows up. Each level of the tree represents the introduction of some constraint into the context vector. Figure 2 The algorithm needs to choose what will be the differentiator element, and it could be from either the context vector or the action vector. This differentiator needs to separate the situation responsible for the disequilibrium from the others, and the algorithm chooses it by calculating the information gain.

When some schema fails and it is not possible to differentiate it, then CALM executes the adjustment method. This method reduces the expectations of an unstable decider schema in order to make it reliable again. The algorithm simply compares the activated schema's expectation and the real result perceived by the agent after the application of the schema, setting the incompatible expectation elements to undefined value ('#').

As CALM always creates schemas with expectations totally determined (as a mirror of the result of its first application), the walk performed by the schema is a reduction of expectations, up to the point it reaches a state where remains only those elements that really represent the regular results of the action carried out in that context. Figure 3 The adjustment method changes the schema expectation (and consequently the anticipation predicted by the schema). Successive adjustments can reveal some unnecessary differentiations. After an adjustment, CALM needs to verify the possibility to regroup some related schemas. It is the integration method that searches two schemas with equivalent expectations to approach different contexts in a same sub-tree, and join these schemas into a single one, eliminating the differentiation. The method is illustrated in figure 4. To test this basic CALM method, we have made some experiments in simple scenarios showing that the agent converges to the expected behavior, constructing correct knowledge to represent the environment deterministic regularities, as well as the regularities of its body sensations, and also the regular influence of its actions over both. We may consider that these results have corroborated the mechanism ability to discover regularities and use this knowledge to adapt the agent behavior. The agent has learned about the consequences of its actions in different situations, avoiding emotionally negative situations, and pursuing those emotionally positive. A detailed description of these experiments can be viewed in (Perotto and Alvares 2006).

### A 0#0 0## A 0#0 1## A 0#0 (b) (a) ### A 0#0

Dealing with the Unobservable

In this section we will present the extended mechanism, developed to deal with partially observable and partially deterministic environments (CALM-POPDE), where ∂<1, ϕ<1, and also ω<1.

In the basic mechanism (CALM-COPDE), presented in previous sections, when some schema fails, the first alternative is to differentiate it based on direct sensorimotor (context and action) elements. If it is not possible to do that, then the mechanism reduces the schema expectation, generalizing the incoherent anticipated elements. When CALM reduces the expectation of a given schema, it supposes that there is no deterministic regularity following the represented situation in relation to these incoherent elements, and the related transformation is unpredictable.

However, sometimes the error could be explained by considering the existence of some abstract or hidden property in the environment, which could be able to differentiate the situation, but which is not directly perceived by the agent sensors. In the extended mechanism, we introduce a new method which enables CALM to suppose the existence of a non-sensorial property in the environment, which it will represent as a synthetic element.

When a new synthetic element is created, it is included as a new term in the context and expectation vectors of the schemas. Synthetic elements suppose the existence of something beyond the sensorial perception, which can be useful to explain non-equilibrated situations. They have the function of amplifying the differentiation possibilities.

In this way, when dealing with partially observable environments, CALM has two additional challenges: a) infer the existence of unobservable properties, which it will represent by synthetic elements, and b) include these new elements into its predictive model. A good strategy to do this task is looking at the historical information. [START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF] have proved that it is always possible to find sufficient little pieces of history to distinguish and identify all the underlying states in D-POMDPs.

The first CALM-POPDE additional method is called abstract differentiation. When a schema fails in its prediction, and when it is not possible to differentiate it by the current set of considered properties, then a new boolean synthetic element is created, enlarging the context and expectation vectors. Immediately, this element is used to differentiate the incoherent situation from the others. The method attributes arbitrary values to this element in each differentiated schema. These values represent the presence or absence of some unobservable condition, necessary to determine the correct prediction in the given situation. The method is illustrated in figure 5, where the new elements are represented by card suites. Once a synthetic element is created, it can be used in next differentiations. A new synthetic element will be created only if the existing ones are already saturated. To avoid the problem of creating infinite new synthetic elements, CALM can do it only until a determined limit, after which it considers that the problematic anticipation is simply unpredictable, undefining the expectation in the related schemas by adjustment.

The synthetic element is not associated to any sensorial perception. Consequently, its value cannot be observed. This fact can place the agent in ambiguous situations, where it does not know whether some relevant but not observable condition (represented by this element) is present or absent.

Initially, the value of a synthetic element is verified a posteriori (i.e. after the execution of the action in an ambiguous situation). Once the action is executed and the following result is verified, then the agent can rewind and deduce what was the situation really faced in the past instant (disambiguated). Discovering the value of a synthetic element after the circumstance where this information was needed can seem useless, but in fact, this delayed deduction gives information to the second CALM-POPDE additional method, called abstract anticipation.

If the unobservable property represented by this synthetic element has a regular behavior, then the mechanism can "backpropagate" the deduced value for the activated schema in the previous instant. The deduced synthetic element value will be included as a new anticipation in the previous activated schema.

For example, in time t 1 CALM activates the schema Ξ 1 = (#0 + x → #1), where the context and expectation are composed by two elements (the first one synthetic and the second one perceptive), and one action. Suppose that the next situation '#1' is ambiguous, because it excites both schemas Ξ 2 = (♣1 + x → #0) and Ξ 3 = (♦1 + x → #1). At this time, the mechanism cannot know the synthetic element value, crucial to determine what is the real situation. Suppose that, anyway, the mechanism decides to execute the action 'x' in time t 2 , and it is followed by the sensorial perception '0' in t 3 . Now, in t 3 , the agent can deduce that the situation really dealt with in t 2 was '♣1', and it can include this information into the schema activated in t 1 , in the form Ξ 1 = (#0 + x → ♣1).

Example Problem and Solution

To exemplify the functioning of the proposed method we will use the flip problem, which is also used by [START_REF] Singh | Learning Predictive State Representations[END_REF] and [START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF]. They suppose an agent who lives in a two states universe. It has 3 actions (l, r, u) and 2 perceptions (0, 1). The agent do not have any direct perception to know what is the underlying current state. It has the perception 1 when the state changes, and the perception 0 otherwise. Action u keeps the state the same, action l causes the deterministic transition to the left state, and action r causes the deterministic transition to the right state. The flip problem is showed as a Mealy machine in figure 6. CALM-POPDE is able to solve this problem. Firstly it will try to predict the next observation in function of its action and current observation. However, CALM quickly discovers that the perceptive observation is not useful to the model, and that there is not sufficient information to make correct anticipations. So, it creates a new synthetic element which will be able to represent the underlying left (♣) and right (♦) states.

Figure 7 shows the first steps in the schematic tree construction for the flip problem. We suppose that the first movements do not betray the existence of a hidden property. These movements are : "r1, u0, l1, r1, l1, u0, r1". Figure 8 shows the first abstract differentiation, after the sequence "r0", and also the abstract anticipation, that refers to the immediately previous sequence ("r1"). Figure 9 shows the abstract anticipation coming from the repetition of "r0". Figure 10 shows a new abstract differentiation and its anticipations by following "l1, l0, l0". Finally, figure 11 shows the final solution, with the last differentiation resulting from the execution of "u0, l0, r1, u0, r0". # # r

F p F h A # r 1 # l 1 # u 0 # # # F p F h A # r # r 1 1 # l # l 1 1 # u # u 0 0 # # # # # #
♣ # r ♦ 1 ♦ # r ? 0 # # l ? 1 # # u ? 0 # # # # # r # # r ♣ # r ♣ # r ♦ 1 ♦ 1 ♦ # r ♦ # r ? 0 ? 0 # # l # # l ? 1 ? 1 # # u # # u ? 0 ? 0 # # # # # # Figure 8. First abstract differentiation. # # r ♣ # r ♦ 1 ♦ # r ♦ 0 # # l ? 1 # # u ? 0 # # # # # r # # r ♣ # r ♣ # r ♦ 1 ♦ 1 ♦ # r ♦ # r ♦ 0 ♦ 0 # # l # # l ? 1 ? 1 # # u # # u ? 0 ? 0 # # # # # # Figure 9. Abstract anticipation. # # r ♣ # r ♦ 1 ♦ # r ♦ 0 # # u ? 0 # # # # # l ♣ # l ♣ 0 ♦ # l ♣ 1 # # r # # r ♣ # r ♣ # r ♦ 1 ♦ 1 ♦ # r ♦ # r ♦ 0 ♦ 0 # # u # # u ? 0 ? 0 # # # # # # # # l # # l ♣ # l ♣ # l ♣ 0 ♣ 0 ♦ # l ♦ # l ♣ 1 ♣ 1 Figure 10
. New abstract differentiations and anticipations.

# # r In a second problem, we consider a robot which have the mission of buying some cans in a drink machine. It has 3 alternative actions: "insert a coin" (i), "press the button" (p), or "go to another machine" (g); it can see the state of an indicator light in the machine: "off" ( ) or "on" ( ); and it perceives whether a can is returned (☺) or not ( ). There are 2 hidden properties: "no coin inserted" ( ) or "coin inserted" ( ); and "machine ok" ( ) or "machine out of service" ( ). The light turns on ( ) just during one time cycle, and only if the agent presses the button without having inserted a coin before, otherwise the light indicator is always off. The goal in this problem is to take a determined number of drinks without losing coins in bad machines.

♣ # r ♦ 1 ♦ # r ♦ 0 # # # # # l ♣ # l ♣ 0 ♦ # l ♣ 1 ♣ # u ♣ 0 ♦ # u ♦ 0 # # u # # r # # r ♣ # r ♣ # r ♦ 1 ♦ 1 ♦ # r ♦ # r ♦ 0 ♦ 0 # # # # # # # # l # # l ♣ # l ♣ # l ♣ 0 ♣ 0 ♦ # l ♦ # l ♣ 1 ♣ 1 ♣ # u ♣ # u ♣ 0 ♣ 0 ♦ # u ♦ # u ♦ 0 ♦ 0 # # u # # u
This example poses two challenges to the agent: First, the machine does not present any direct perceptible change when the coin is inserted. Since the agent does not have any explicit memory, apparently it faces the same situation both before and after having inserted the coin. However, this action changes the value of an internal property in the drink machine.

Precisely, the disequilibrium occurs when the agent presses the button. In an instantaneous point of view, sometimes the drink arrives, and the goal is attained ( + p → ☺), but sometimes only the led light turns on ( + p → ). To reach its goal, the agent needs to coordinate a chain of actions (insert the coin and press the button), and it can do that by using a synthetic element which represents this machine internal condition ( or ).

Second, the agent does not have direct perceptive indications to know if the machine is working, or if it is out of service. The agent needs to interact with the machine to discover its operational condition ( or ). This second problem is a little bit different from the first, but it can be solved by the same way. The agent creates a test action, which enables it to discover this hidden property before inserting the coin. It can do that by pressing the button.

Table 1 presents the set of decider schemas that CALM learns to the drink machine problem. We remarks that Ξ 4 presents the unpredictable transformation that follows the action g (go to another machine) due to the uncertainty of the operational state of the next machine. The test is represented in Ξ 1 and Ξ 2 , that can be simultaneously activated because the ambiguity of the result that follows the activation of Ξ 4 but anticipates the operational state of the machine.

Ξ 1 = ( # # # + p → ) Ξ 2 = ( # # + p → ) Ξ 3 = ( # # + p → ☺) Ξ 4 = ( # # # # + g → # ) Ξ 5 = ( # # # + i → ) Ξ 6 = ( # # # + i → )

Related Works

CALM-POPDE is an original mechanism that enables an agent to incrementally create a world model during the course of its interaction. This work is the continuity of our previous work (Perotto [START_REF] Alvares | Incremental Inductive Learning in a Constructivist Agent[END_REF], extended to deal with partially observable environments.

The pioneer work on Constructivist AI has been presented by [START_REF] Drescher | Made-Up Minds: A Constructivist Approach to Artificial Intelligence[END_REF]. He proposed the first constructivist agent architecture (called schema mechanism), that learns a world model by an exhaustive statistical analysis of the correlation between all the context elements observed before each action, combined with all resulting transformations. Drescher has also suggested the necessity to discover hidden properties by creating 'synthetic items'.

The schema mechanism represents a strongly coherent model, however, there are no theoretical guarantees of convergence. Another restriction is the computational cost of the kind of operations used in the algorithm. The need of space and time resources increases exponentially with the problem size. Nevertheless, many other researchers have presented alternative models inspired by Drescher, like as [START_REF] Yavuz | PAL: A Model of Cognitive Activity[END_REF], [START_REF] Birk | Schemas and Genetic Programming[END_REF], (Morrison et al. 2001), [START_REF] Chaput | The Constructivist Learning Architecture[END_REF]) and [START_REF] Holmes | Schema Learning: Experience-based Construction of Predictive Action Models[END_REF].

Our mechanism (CALM) differs from these previous works because we limit the problem to the discovery of deterministic regularities (even in partially deterministic environments), and in this way, we can implement direct induction methods in the agent learning mechanism. This approach presents a low computational cost, and it allows the agent to learn incrementally and find high-level regularities.

We are also inspired by [START_REF] Rivest | Diversity-based inference of finite automata[END_REF]) and (Ron 1995), who had suggested the notion of state signature as an historical identifier to the DFA states, strongly reinforced recently by [START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF], who have developed the idea of learning anticipations trough the analysis of relevant pieces of history.

Discussion and Next Steps

The CALM mechanism can provide autonomous adaptive capability to an agent, because it is able to incrementally construct knowledge to represent the deterministic regularities observed during its interaction with the environment, even in partially deterministic universes.

We have also presented an extension to the basic CALM mechanism in a way which enables it to deal with partially observable environments, detecting highlevel regularities. The strategy is the induction and prediction of unobservable properties, represented by synthetic elements.

Synthetic elements enable the agent to overpass the limit of instantaneous and sensorimotor regularities. In the agent mind, synthetic elements can represent 3 kinds of "unobservable things". (a) Hidden properties in partially observed worlds, or sub-environment identifiers in discrete non-stationary worlds. (b) Markers to necessary steps in a sequence of actions, or to different possible agent points of view. And (c), abstract properties, which do not exist properly, but which are powerful and useful tools to the agent, enabling it to organize the universe in higher levels.

With these new capabilities, CALM becomes able to overpass the sensorial perception, constructing more abstract terms to represent the universe, and to understand its own reality in more complex levels.

CALM can be very efficient to construct models in partially but highly deterministic (1 > ∂ >> 0), partially but highly observable (1 > ω >> 0), and its properties are partially but highly informative (1 > ϕ >> 0). Several problems found in the real world present these characteristics.

Currently, we are improving CALM to enable it to form action sequences by chaining schemas. It will allow the creation of composed actions and plans. We are also including methods to search good policies of actions using the world model constructed by the learning functions.

The next research steps comprehends: to formally demonstrate the mechanism efficiency and correctness; to make comparisons between CALM and related solutions proposed by other researchers; and to analyze the mechanism performance in more complex problems.

Future works can include the extension of CALM to deal with non-deterministic regularities, noisy environments, and continuous domains.

Figure 1 .

 1 Figure 1. Schematic Tree. Each node is a schema composed of three vectors: context, action and expectation. The leaf nodes are decider schemas.

Figure 2 .

 2 Figure 2. Differentiation method; (a) experimented situation and action; (b) activated schema; (c) real observed result; (d) sub-tree generated by differentiation.

Figure 3 .

 3 Figure 3. Adjust method; (a) experimented situation and action; (b) activated schema; (c) real observed result; (d) schema expectation reduction after adjustment.

Figure 4 .

 4 Figure 4. Integration method; (a) sub-tree after some adjustment; (b) an integrated schema substitutes the sub-tree.

Figure 5 .

 5 Figure 5. Synthetic element creation method; (d) incremented context and expectation vectors, and differentiation using synthetic element.

Figure 6 .

 6 Figure 6. The flip problem.

Figure 7 .

 7 Figure 7. Initial schematic tree to the flip problem. The vector represents synthetic elements (Fh), perceptible elements (Fp) and actions (A). The decider schemas show the expectations.

Figure 11 .

 11 Figure 11. Final schematic tree to solve the flip problem.

  . Proceedings of the Seventh International Conference on Epigenetic Robotics: Modeling Cognitive Development in Robotic Systems. Lund University Cognitive Studies, 135.

Table 1 .

 1 Schemas to the drink machine problem.


Sylvie Luche

Cécile Lelong

Hélène Diemer

Alain Van Dorsselaer

Thierry Rabilloud
email: thierry.rabilloud@cea.fr

Ultrafast coelectrophoretic fluorescent staining of

come

Introduction

The analysis of proteins separated on electrophoresis gels, mono-or bidimensional, relies on the ability to detect them in a suitable way. The ideal protein detection protocol should be sensitive, homogeneous from one protein to another and linear throughout a wide dynamic range. In addition, suitable features include compatibility with digestion and mass spectrometry, speed, convenience and low cost. Up to now, no protein detection method matches perfectly these prerequisites. Colloidal Coomassie Blue [START_REF] Neuhoff | Improved staining of proteins in polyacrylamide gels including isoelectric focusing gels with clear background at nanogram sensitivity using Coomassie Brilliant Blue G-250 and R-250[END_REF] is simple, cheap and rather linear, but its lacks sensitivity and requires long staining times for optimal sensitivity. Conversely, silver staining is sensitive, but labor-intensive, and its linearity is limited. Moreover, despite recent advances [START_REF] Richert | About the mechanism of interference of silver staining with peptide mass spectrometry[END_REF], [START_REF] Chevallet | Improved mass spectrometry compatibility is afforded by ammoniacal silver staining[END_REF], its compatibility is limited. Fluorescent detection methods, on their side, show a convenient linearity and an adequate sensitivity, although the latter varies from the one of colloidal Coomassie [START_REF] Steinberg | SYPRO orange and SYPRO red protein gel stains: one-step fluorescent staining of denaturing gels for detection of nanogram levels of protein[END_REF] to the one of silver [START_REF] Berggren | Background-free, high sensitivity staining of proteins in one-and two-dimensional sodium dodecyl sulfate-polyacrylamide gels using a luminescent ruthenium complex[END_REF], [START_REF] Mackintosh | A fluorescent natural product for ultra sensitive detection of proteins in one-dimensional and two-dimensional gel electrophoresis[END_REF] . Although superior to the one of silver staining, their compatibility with mass spectrometry does not always equal the one of Coomassie Blue, and this has been unfortunately shown to be the case for Sypro Ruby [START_REF] Rabilloud | A comparison between Sypro Ruby and ruthenium II tris (bathophenanthroline disulfonate) as fluorescent stains for protein detection in gels[END_REF] and Deep Purple [START_REF] Chevalier | Different impact of staining procedures using visible stains and fluorescent dyes for large-scale investigation of proteomes by MALDI-TOF mass spectrometry[END_REF], i.e. the most sensitive variants. In addition to this drawback, optimal sensitivity requires rather long staining times, and the cost of the commercial reagents can become a concern when large series of gels are to be produced.

Last but not least, all these staining methods take place along with gel fixation, i.e. protein insolubilization in the gel. This means in turn that recovery of proteins after staining, e.g. for electroelution or blotting purposes, is rather problematic. There are however a few exceptions to the latter rule. Protein staining with zinc and imidazole [START_REF] Castellanos-Serra | Detection of biomolecules in electrophoresis gels with salts of imidazole and zinc II: a decade of research[END_REF] is rather sensitive, but absolutely not linear. In addition, protein excision for mass spectrometry is difficult because of poor contrast. Fluorescent staining with Nile Red [START_REF] Daban | Use of the hydrophobic probe Nile red for the fluorescent staining of protein bands in sodium dodecyl sulfate-polyacrylamide gels[END_REF] is rapid and does not require fixation. However, the staining is quite photolabile, which complicates imaging and excision, and the sensitivity is limited. Finally, staining with Sypro Tangerine [START_REF] Steinberg | Fluorescence detection of proteins in sodium dodecyl sulfate-polyacrylamide gels using environmentally benign, nonfixative, saline solution[END_REF] just requires a single bath in saline solution containing the fluorophore. However, its cost and limited sensitivity have limited its use. So the situation is worse in this category of non-fixing detection than in the case of classical detection after fixation. We report here protein detection with carbocyanines in SDS gels. This method is most efficient by co-electrophoresis of proteins with the fluorophore. This provides in turn excellent staining speed (30 minutes between end of electrophoresis and imaging). In addition, the method is cost-effective and compatible with several downstream processes, e.g. mass spectrometry or blotting. Finally, the sensitivity is intermediate between the one of Coomassie blue and the one of ruthenium complexes.

Material and methods

Samples

Molecular weight markers (broad range, Bio-Rad) were diluted down to 10 ng/µl for each band in SDS buffer (Tris-HCl 125mM pH 7.5, containing 2% (w/v) SDS, 5% (v/v) thioglycerol, 20% (v/v) glycerol and 0.005% (w/v) bromophenol blue). The diluted solution was heated in boiling water for 5 minutes. A tenfold dilution in SDS buffer was performed to get a 1ng/µl per protein dilution JM 109 E. coli cells were grown up to an OD of 0.5 in LB medium. Bacteria were collected by centrifugation (2000g 5 minutes) and washed twice in PBS, and once in isotonic wash buffer (Tris-HCl 10mM pH 7.5, 0.25M sucrose, 1mM EDTA). The final pellet was suspended in its volume of isotonic wash buffer, transferred in an ultracentrifuge tube, and 4 volumes of concentrated lysis solution (8.75M urea, 2.5M thiourea, 5% CHAPS, 50mM DTT and 25mM spermine base) were added. After lysis at room temperature for 30 minutes, the viscous lystae was centrifuged at 200,000g for 1 hour at room temperature. The supernatant was collected, the protein concentration was estimated and the solution was made 0.4% (w/v) in carrier ampholytes (Pharmalyte 3-10). The solution was stored frozen at -20°C until use. J774 cells and HeLa cells were grown in spinner flasks in DMEM + 5% fetal calf serum up to a density of 1 million cells /ml. The cells were collected by centrifugation (1000g 5 minutes), washed and lysed as described for bacteria.

Electrophoresis

SDS electrophoresis

10%T gels (160x200x1.5 mm) were used for protein separation. The Tris taurine buffer system was used [START_REF] Tastet | A versatile electrophoresis system for the analysis of high-and low-molecular-weight proteins[END_REF], operated at a ionic strength of 0.1 and a pH of 7.9. The final gel composition is thus Tris 180mM, HCl 100 mM, acrylamide 10% (w/v), bisacrylamide 0.27%. The upper electrode buffer is Tris 50mM, Taurine 200mM, SDS 0.1%. The lower electrode buffer is Tris 50mM, glycine 200mM, SDS 0.1%. For 1D SDS gels, a 4% stacking gel in Tris 125mM, HCl 100mM was used. No stacking gel was used for 2D electrophoresis.

The gels were run at 25V for 1hour, then 12.5W per gel until teh dye front has reached the bottom of the gel.

Alternatively, the standard Tris-glycine system, operating at pH 8.8 and ionic strength of 0.0625 was used.

IEF

Home made 160mm long 4-8 or 3-10.5 linear pH gradient gels were cast according to published procedures [START_REF] Rabilloud | Sample application by in-gel rehydration improves the resolution of two-dimensional electrophoresis with immobilized pH gradients in the first dimension[END_REF]. Four mm-wide strips were cut, and rehydrated overnight with the sample, diluted in a final volume of 0.6ml of rehydration solution (7M urea, 2M thiourea, 4% CHAPS and 100mM dithiodiethanol [START_REF] Rabilloud | Improvement of the solubilization of proteins in two-dimensional electrophoresis with immobilized pH gradients[END_REF], [START_REF] Luche | About thiol derivatization and resolution of basic proteins in two-dimensional electrophoresis[END_REF]). The strips were then placed in a multiphor plate, and IEF was carried out with the following electrical parameters 100V for 1 hour, then 300V for 3 hours, then 1000V for 1 hour, then 3400 V up to 60-70 kVh.

After IEF, the gels were equilibrated for 20 minutes in Tris 125mM, HCl 100mM, SDS 2.5%, glycerol 30% and urea 6M. They were then transferred on top of the SDS gels and sealed in place with 1% agarose dissolved in Tris 125mM, HCl 100mM, SDS 0.4% and 0.005% (w/v) bromophenol blue. Electrophoresis was carried out as described above.

Detection on gels

Colloidal coomassie blue staining was performed using a commercial product (G-Biosciences) purchased from Agro-Bio (La Ferté Saint Aubin, France).

Silver staining was performed according to the fast silver staining method of Rabilloud [START_REF] Rabilloud | A comparison between low background silver diammine and silver nitrate protein stains[END_REF].

Ruthenium fluorescent staining was performed according to Lamanda et al [START_REF] Lamanda | Improved Ruthenium II tris (bathophenantroline disulfonate) staining and destaining protocol for a better signal-tobackground ratio and improved baseline resolution[END_REF], and Sypro tangerine staining was performed in PBS accoding to Steinberg et al [START_REF] Steinberg | Fluorescence detection of proteins in sodium dodecyl sulfate-polyacrylamide gels using environmentally benign, nonfixative, saline solution[END_REF]. The gels were imaged with a Fluorimager laser scanner, operating at 488nm excitation wavelength.

For co-electrophoretic carbocyanine staining, the desired carbocyanine (all were purchased from Fluka, Switzerland) was first dissolved at 30mM in DMSO.This stock solution is stable for severla weeks at room temperature, provided it is stored in the dark. Various carbocyanines were tested, varying in their aromatic nucleus (oxacarbocyanine, thiacarbocyanine and tertramethylindocarbocyanine) and in the size of the side chains (ethyl to octadecyl). All carbocyanines can be excited at 302nm on a UV table. Oxacarbocyanines are also excited at 488nm, while thia-and indo-carbocyanines can be excited at 532nm. The carbocyanine of interest was dissolved at 3µM (final concentration) in the upper electrode buffer. The fluorescent electrode buffer was used in place of standard buffer. After electrophoresis, the colored gel was rinsed with 5-10 volumes of water. One 15 minutes rinse is sufficient for Tris-glycine gels operating at an ionic strength of 0.0625. Two 15 minutes rinses are required for gels operating at an ionic strength of 0.1. The gels were then visualized on a UV table or using a laser scanner. Alternate washing solutions (e.g. 5% acetic acid, or 5% acetic acid + 20% ethanol, or 0.05% SDS) were also tested. they often required longer washing times to provide contrast, without leading to increased sensitivity. For staining decay experiments, the gels were stained as described above, using water as a contrasting agent. After the initial rinses, the gels were scanned, and then returned to their water bath without shaking. The gels were then scanned at hourly intervals, and retruned to their bath between each scan For post-electrophoretic carbocyanine staining, the general scheme described by Malone [START_REF] Malone | Practical aspects of fluorescent staining for proteomic applications[END_REF] was used and adapted as follows/ After electrophoresis, the gels are fixed overnight in 2% phosphoric acid, 30% ethanol and 0.004% SDS. They are then washed 3 x 20 minutes in 2% phosphoric acid, 0.004% SDS, and then equilibrated for 4 hours in 2% phosphoric acid, 0.004% SDS containing 3 µM of the desired carbocyanine. Visualization could be carried out directly from the carbocyanine bath on a UV table or using a laser scanner.

Image analysis

Images acquired on a Fluorimager laser scanner (488nm excitation wavelength, no emission filter, 200 micron pixe size) were analyzed directly by the ImageQuant software provided with the instrument for SDS-PAGE gels of markers. For two-dimensional gels, the images were converted to the TIFF format, and then analyzed with the delta 2D sotware (Decodon, Germany). The default detection parameters calculated by the software were used and no manual edition of the spots was performed.

Blotting

Proteins were transferred on PVDF membranes using the semi-dry blotting system of Kyhse-Andersen [START_REF] Kyhse-Andersen | Electroblotting of multiple gels: a simple apparatus without buffer tank for rapid transfer of proteins from polyacrylamide to nitrocellulose[END_REF]. Gels can be transferred directly after electrophoresis. Otherwise, gels stained with carbocyanines were first re-equilibrated for 30 minutes in carbocyanine-free electrode buffer prior to transfer. Mock-colored gels, i.e. gels run with a colorless-electrode buffer but rinsed 2x15 minutes in water, were also reequilibrated prior to transfer. After transfer, the proteins were detected on the PVDF sheets with india ink [START_REF] Hancock | India ink staining of proteins on nitrocellulose paper[END_REF].

2.6. Mass spectrometry 2.6.1. Spot excision: For fluorescent stains, spot excision was performed on a UV table operating at 302nm. The spots were collected in microtiter plates. The spots were generally not destained prior to acetonitrile washing. However, the carbocyanine-stained spots were sometimes fixed in 50% ethanol for 30 minutes. The solvent was then removed and the spots were stored at -20°C until use.

In gel digestion :

In gel digestion was performed with an automated protein digestion system, MassPrep Station (Waters, Manchester, UK). The gel plugs were washed twice with 50 µL of 25 mM ammonium hydrogen carbonate (NH4HCO3) and 50 µL of acetonitrile. The cysteine residue were reduced by 50 µL of 10 mM dithiothreitol at 57°C and alkylated by 50 µL of 55 mM iodoacetamide. After dehydration with acetonitrile, the proteins were cleaved in gel with 10 µL of 12.5 ng/µL of modified porcine trypsin (Promega, Madison, WI, USA) in 25 mM NH4HCO3. The digestion was performed overnight at room temperature. The generated peptides were extracted with 60% acetonitrile in 5% acid formic.

MALDI-TOF-MS analysis

MALDI-TOF mass measurements were carried out on UltraflexTM TOF/TOF (Bruker DaltonikGmbH, Bremen, Germany). This instrument was used at a maximum accelerating potential of 25kV in positive mode and was operated in reflectron mode. The sample were prepared by standard dried droplet preparation on stainless steel MALDI targets using α-cyano-4hydroxycinnamic acid as matrix. The external calibration of MALDI mass spectra was carried out using singly charged monoisotopic peaks of a mixture of bradykinin 1-7 (m/z=757.400), human angiotensin II (m/z=1046.542), human angiotensin I (m/z=1296.685), substance P (m/z=1347.735), bombesin (m/z=1619.822), renin (m/z=1758.933), ACTH 1-17 (m/z=2093.087) and ACTH 18-39 (m/z=2465.199). To achieve mass accuracy, internal calibration was performed with tryptic peptides coming from autolysis of trypsin, with respectively monoisotopic masses at m/z = 842.510, m/z = 1045.564 and m/z = 2211.105 . Monoisotopic peptide masses were automatically annotated using Flexanalysis 2.0 software. Peaks are automatically collected with a signal to noise ratio above 4 and a peak quality index greater than 30. 2.6.4. MS Data analysis Monoisotopic peptide masses were assigned and used for databases searches using the search engine MASCOT (Matrix Science, London, UK) [START_REF] Perkins | Probability-based protein identification by searching sequence databases using mass spectrometry data[END_REF]. All proteins present in Swiss-Prot were used without any pI and Mr restrictions. The peptide mass error was limited to 50 ppm, one possible missed cleavage was accepted.

Results and discussion

Three different principles can be used for fluorescent detection on gels. The most obvious one, covalent labelling, has been used with limited sensitivity in the past with UV-excitable probes such as fluorescamine [START_REF] Jackowski | Fluorescamine staining of nonhistone chromatin proteins as revealed by two-dimensional polyacrylamide gel electrophoresis[END_REF] or MDPF [START_REF] Urwin | A multiple high-resolution mini two-dimensional polyacrylamide gel electrophoresis system: imaging two-dimensional gels using a cooled charge-coupled device after staining with silver or labeling with fluorophore[END_REF]. An important improvement of this approach has been made recently with the introduction of multiplex labelling [START_REF] Unlu | Difference gel electrophoresis: a single gel method for detecting changes in protein extracts[END_REF]. However, the low number of labelling sites on proteins limits the absolute sensitivity of this approach. While this can be partly compensated by the increase of software performance for pure detection purposes, the approach suffers from a weak signal, which renders spot excision for characterization purposes difficult. The second obvious approach is to use a probe that binds non covalently to proteins, in which case the contrast between the fluorescent protein zones and the background is governed by the differential concentration of the probes in the two sites. This approach is used in the very popular staining methods with ruthenium complexes [START_REF] Berggren | Background-free, high sensitivity staining of proteins in one-and two-dimensional sodium dodecyl sulfate-polyacrylamide gels using a luminescent ruthenium complex[END_REF] [START_REF] Lamanda | Improved Ruthenium II tris (bathophenantroline disulfonate) staining and destaining protocol for a better signal-tobackground ratio and improved baseline resolution[END_REF] or with epinococconone [START_REF] Mackintosh | A fluorescent natural product for ultra sensitive detection of proteins in one-dimensional and two-dimensional gel electrophoresis[END_REF]. The last approach uses molecules which fluorescence depends on the chemical environment in which they are. Classical examples are Nile red [START_REF] Daban | Use of the hydrophobic probe Nile red for the fluorescent staining of protein bands in sodium dodecyl sulfate-polyacrylamide gels[END_REF], Sypro Orange and Sypro Red [START_REF] Steinberg | SYPRO orange and SYPRO red protein gel stains: one-step fluorescent staining of denaturing gels for detection of nanogram levels of protein[END_REF] and Sypro Tangerine [START_REF] Steinberg | Fluorescence detection of proteins in sodium dodecyl sulfate-polyacrylamide gels using environmentally benign, nonfixative, saline solution[END_REF]. This latter approach suffers generally from a lack of sensitivity. Despite commercial claims, their sensitivity is close to the one of colloidal Coomassie Blue for a substantially higher cost. This is not true for Nile red, but the limited solubility of this dye and its photolability limit the practicability of this approach. As a matter of facts, the ideal fluorescent probe in this family should combine a high absorptivity, an important differential quantum yield between hydrophilic and lipophilic environment, yet being water-soluble. Last but not least, the molecule should have a high photostability to provide flexibility to the staining, e.g. for spot excision. Carboyanines are a family of molecules that show many of these positive features. They are indeed at the basis of the high sensitivity multiplex labelling methods [START_REF] Unlu | Difference gel electrophoresis: a single gel method for detecting changes in protein extracts[END_REF]. However, initial trials of incubating electrophoresis gels in dilute carbocyanine solutions, mimicking the Sypro Orange protocol, did not give any interesting result. We therefore tried to infuse the dye in the gel by co-electrophoresis along with the proteins, as has been described with Coomassie Blue [START_REF] Schagger | Coomassie blue-sodium dodecyl sulfatepolyacrylamide gel electrophoresis for direct visualization of polypeptides during electrophoresis[END_REF]. Interesting results were obtained using water or water-alcohol-acid mixtures as the contrast-developing agent after electrophoresis, as shown in figure 1. However, acidic fixatives showed a tendency to develop an intense background in the low molecular weight region of the gels when carrier ampholytes are present, as in the case of 2D electrophoresis. Furthermore, the suggestion to lower the SDS concentration [START_REF] Schagger | Coomassie blue-sodium dodecyl sulfatepolyacrylamide gel electrophoresis for direct visualization of polypeptides during electrophoresis[END_REF] induces some tailing in the 2D spots, as shown in figure 2.

These results prompted us to carry out a more thorough investigation of the structure-efficiency relationships in the carbocyanine family. Carbocyanine can vary in the side chains and/or in the aromatic nucleus, as shown on figure 3. As the staining is supposed to be driven by the interaction between the probe and the protein-SDS complexes, a long side chain is supposed to increase the affinity for lipophilic environments and thus a strong fluorescence. However, a long side chain also increases the likelihood of selfaggregation of the probe (inducing background) and also decreases the solubility of the probe. The results of such tests are shown in figure 4. This figure clearly shows an optimum at moderately long side chains. Too short side chains (ethyl) show poor sensitivity, while very long side chains (octadecyl) are not very soluble and cannot be used at optimal concentrations, thereby limiting sensitivity. Initial tests were carried out at 3µM carbocyanine concentration, i.e. 1 molecule of probe per 1000 molecules of SDS. While lowering this concentration decreased the sensitivity of staining, increasing it did not enhance staining. We therefore kept the 3µM concentration, which also allowed a very economical staining. We also tried to replace the oxacarbocyanines with indocarbocyanines or with thiacarbocyanines. Tests on a UV table, the only "universal" source able to excitate all these molecules, suggested that oxacarbocyanines were the optimal family to work with (data not shown). At this point, we tried to determine the response factor of the staining for different proteins. To this purpose, we used 1D electrophoresis of serial dilution of marker proteins, as shown in figure 1, and then quantified the fluorescence of the bands with the ImageQuant software. The results are shown on figure 5. The stain appears fairly linear for each protein, but diferent response factors are clearly obvious from one protein to another. Serum albumin showed the highest response factor, which might be linked to the propensity of this protein to bind various low molecular weight organic compounds. We then compared this stain with the most closely stain operating under non-fixing conditions, i.e. Sypro Tangerine. The results are shown on figure 6. Sypro Tangerine is clearly inferior in sensitivity, especially in the low molecular weight region of the gel. This discrepancy between carbocyanine and Sypro tangerine could however be due to the diffusion of low molecular weight proteins in the gel during non-fixing staining, suggesting that the carbocyanine stain could be indeed a fixing one due to a special property of these molecules. To rule out this possibility, we performed blotting experiments, which are shown in figure 7. While a deleterious effect of the staining process can be noted, the protein can still be transferred efficiently to the membrane,while the stain went through the membrane. Finally, we tested the sensitivity and the compatibility of this fluorescent stain with mass spectrometry, in comparison to standard methods such as colloidal Coomassie Blue [START_REF] Neuhoff | Improved staining of proteins in polyacrylamide gels including isoelectric focusing gels with clear background at nanogram sensitivity using Coomassie Brilliant Blue G-250 and R-250[END_REF] or ruthenium complexes [START_REF] Lamanda | Improved Ruthenium II tris (bathophenantroline disulfonate) staining and destaining protocol for a better signal-tobackground ratio and improved baseline resolution[END_REF]. The results are shown on figure 8 and on table 1. On the sensitivity level, the carbocyanine stain lies between Coomassie Blue and ruthenium complexes, while being much quicker to complete. A comparison of the homogeneity of staining was made between ruthenium, Coomassie Blue and carbocyanine. To this purpose, triplicate gels were run, stained and the resulting images were analyzed with the Delta2D software. The distributions of the staining intensities standard deviations are shown for both methods on figure 9.

On the mass spectrometry compatibility level, the carbocyanine stain was comparable to colloidal Coomassie Blue and to ruthenium complexes,as shown on Table 1 on spots showing detected with the three staining methods but probing a range of staining intensities, and spread on various positions of the gels. Due to the non-fixing nature of the stain, we could use the spots as coming from the gels, i.e. without fixation, but with the buffer components. In this case, the usual spot washes prior to digestion were the only cleaning step. Alternatively, we could also fix the excised spots with classical acid-alcohol mixtures, thereby insolubilizing the proteins more efficiently in the gel but also providing more extensive cleaning by removal of electrophoresis buffer components. Finally, it can be noted that carbocyanines offer excellent resistance to photoinduced fading, allowing ample time for spot excision on a UV table.

Quite differently from the method described in patents [START_REF] Gee | Methods for detecting anionic and non-anionic compositions using carbocyanine dyes. US patent application 20050244976[END_REF], this cyanine staining method is based on the interaction of oxacarbocyanine molecules with SDS-protein complexes, and is thus nonfixing. As the cyanine fluorescence is maximal in lipophilic environments, the rationale of this method is to disrupt SDS micelles causing the background fluorescence, while keeping enough SDS at the protein containing sites to promote fluorescence. This is achieved by water rinses, which decrease the ionic strength of the gel, thereby increasing the critical micellar concentration of SDS [START_REF] Helenius | Properties of detergents[END_REF], and thus promoting SDS micelles dissociation. This means in turn that the protocol has to be adapted to the electrophoretic system used, as shown in figure 10. While a single rinse is optimal for systems operating at low ionic strength, such as the popular Laemmli system, increased rinses are required for systems operating at higher ionic strength, such as the Tris taurine system. While a non-fixing process provides interesting features (speed of staining, further mobilization of the proteins, e.g. for protein blotting), it also means in turn that the stain decreases and the proteins diffuse with time, as shown in figure 11. Evaluation of the total stain by the Delta 2D software showed a 10% decrease in total signal intensity over 6 hours, but it can easily be seen that the fuzziness of the stain increases. Another staining scheme can also be devised, starting from gels that are fixed in the presence of SDS, as described by Malone et al. [START_REF] Malone | Practical aspects of fluorescent staining for proteomic applications[END_REF]. Typical results are shown on figure 12. In this case, the short chain oxacarbocyanines proved more efficient than carbocyanines with longer chains.

Concluding remarks

Carbocyanine staining is based on the increase of fluorescence of these molecules in the SDSprotein complexes obtained after SDS PAGE. Two setups can be used. The long setup, starting from fixed gels, gives a stable staining pattern. However, it is not as sensitive as ruthenium complexes, almost as long, so that its only advantage is economical. The short setup, which uses coelectrophoresis of the fluorescent probe along with the proteins in the SDS gel, does not give a stable pattern over time, so that its applicability for very large gel series is limited. However, the staining pattern is stable for more than one hour, which allows ample time for image acquisition. In addition this short setup provides a very fast (less than one hour), economical, sensitive (intermediate between Coomassie Blue and ruthenium complexes) and versatile stain because of its non fixative nature. Loadings from left to right, per band of protein: 400ng, 200ng, 100ng, 50ng, 20ng, 10ng, 5ng, 2ng. The upper electrode buffer contained 3µM diheptyloxacarbocyanine and 0.1% SDS. After electrophoresis, the gels were rinsed 3x20 minutes prior to imaging A: water rinses. B: rinses in 20% ethanol. C: rinses in 20% ethanol + 5% acetic acid Figure 2: effect of SDS concentration 200 micrograms of E.coli proteins were separated by two dimensional electrophoresis (4-8 pH gradients, Tris taurine system). The electrode buffer contained 3µM diheptyloxacarbocyanine and 0.1% SDS (panel A) or 0.05% SDS (panel B). After electrophoresis, the gels were soaked 3x20 minutes in 5% acetic acid, 20% ethanol and 75% water (by volume) prior to imaging. Note the stained crescent of ampholytes (panel A, arrow) and the deformation of the lower part of the gels and the vertical tailing of some spots induced by the reduced SDS concentration (panel B, arrows). Ro check thatb this tailing is not just a staining artefact, a second pair of gels were run with normal (panel C) and reduced (panel D) SDS concentrations, without carbocyanine staining, and silver stained. Vertical tailing was also observed in this case The molecular weight marker proteins used in figure 1 were separated by SDS PAGE, as detailed in figure 1. The gels were stained by co-electrophoretic staning with diheptyloxacarbocyanine, using water as the contrasting agent. The fluorescence intensity was then measured by the ImageQuant software, and plotted against protein load for different proteins. Squares : bovine serum albumin ; diamonds : hen ovalbumin ; circles : rabbit phosphorylase ; crosses : E. coli beta-galactosidase

  5. Acknowledgments.The support from the Région Rhone Alpes by a grant (analytical chemistry subcall, priority research areas call[2003][2004][2005][2006]) is gratefully acknowledged.

Figure 1 :

 1 Figure 1: staining of molecular weight markers serial dilutions of broad range molecular weight markers were loaded onto a SDS gel (10% acrylamide, Tris taurine system). the standard composition is the following: MYO: myosin; GAL: beta galatosidase; PHO: glycogen phosphorylase; BSA: bovine serum albumin; OVA: ovalbumin; CAR: carbonic anhydrase; STI: soybean trypsin inhibitor; LYS: lysozyme. Loadings from left to right, per band of protein: 400ng, 200ng, 100ng, 50ng, 20ng, 10ng, 5ng, 2ng. The upper electrode buffer contained 3µM diheptyloxacarbocyanine and 0.1% SDS. After electrophoresis, the gels were rinsed 3x20 minutes prior to imaging A: water rinses. B: rinses in 20% ethanol. C: rinses in 20% ethanol + 5% acetic acid

Figure 3 :

 3 Figure 3: general structural formula of carbocyanines carbocyanines can vary in the side chains (R1 and R2), in the bridge length (n) (n=1 in carbocyanines and n=2 in dicarbocyanines) and in the aromatic nucleus, where the X and Y positions can be occupied by an oxygen atom (oxacarbocyanines), a sulfur atom (thiacarbocyanines) or a dimethyl subsituted carbon atom (indocarbocyanines).

Figure 4 :

 4 Figure 4: evaluation of optimal chain length in carbocyanine staining 200 micrograms of proteins (J774 cells) were separated by two dimensional electrophoresis (4-8 pH gradients, Tris taurine system). The gels were stained by co electrophoretic carbocyanine staining using diethyl oxacarbocyanine (panel A), dipentyl oxacarbocyanine (panel B), diheptyl oxacarbocyanine (panel C), dioctadecyl oxacarbocyanine (panel D). A sensitivity optimum appears at 5-7 carbons in the side chain.

Figure 5 :

 5 Figure 5 : Dynamic response factor for various proteins.The molecular weight marker proteins used in figure1were separated by SDS PAGE, as detailed in figure1. The gels were stained by co-electrophoretic staning with diheptyloxacarbocyanine, using water as the contrasting agent. The fluorescence intensity was then measured by the ImageQuant software, and plotted against protein load for different proteins. Squares : bovine serum albumin ; diamonds : hen ovalbumin ; circles : rabbit phosphorylase ; crosses : E. coli beta-galactosidase

Figure 6 :

 6 Figure 6: Comparison of carbocyanine staining with other commercial stains

Figure 7 :

 7 Figure 7: Blotting efficiency after carbocyanine staining

Figure 8 :

 8 Figure 8: Comparison of staining by different methods. 300 micrograms (panel A) or 150 micrograms (panels B and C) of proteins from a complete cell extract (J774 cells) were separated by two dimensional gel electrophoresis (pH 3-10), using the Tris-Taurine system, either under control conditions (panels A and B) or with co-electrophoretic carbocyanine staining (panel C). The gel shown in panel A was then stained with Coomassie Blue with a commercial product and without prior fixation (note the intense blue zone corresponding to carrier ampholytes). The gel shown in panel B was stained with a fluorescent ruthenium complex. The spots excised for further characterization with mass spectrometry are shown with arrows

Figure 9 :

 9 Figure 9 : relative standard deviation of spot quantitation with different detection methods. Triplicate gels were run according to the conditions and loadings detailed in figure 8. The spots were then quantitated and matched with the delta2D software, and the relative standard deviation (rsd) for quantitation (i.e. standard deviation/mean , experssed in percentile) was calculated for each standard method and displayed as a histogram. A : histogram for carbocyanine staining (2571 spots detected) B : histogram for ruthenium complex staining (3492 spots detected) C : histogram for colloidal coomassie staining (2231 spots detected) The median rsd (i.e. equal numbers of spots with a lower and higher rsd) are the following : Carbocyanine : 19.6% ; Ruthenium : 20.1% ; Coomassie Blue 23.9%

Figure 10 :

 10 Figure 10: Effect of rinses in different buffer systems

Figure 11 :

 11 Figure 11: Stability of staining over time. 150 micrograms of proteins from a complete cell extract (J774 cells) were separated by two dimensional gel electrophoresis (4-8 pH gradients) and stained co-electrophoretically with carbocyanine. After the initial stain, the gels were left in water and scanned preiodically. Gel A: Starting gel (three water rinses, 15 minutes each). Gel B: two hours stay in water after first scan. Gel C: Three hours stay in water after gels scan. Gel D: Starting gel (three water rinses, 15 minutes each). Gel E: four hours stay in water after first scan. Gel F: six hours stay in water after gels scan Two sets of gels were required because of gel breakage upon repetitive manipulation.

Figure 12 :

 12 Figure 12: fixing staining with carbocyanines 300 micrograms of E.coli proteins were separated by two dimensional electrophoresis (3-10 pH gradients, Tris taurine system). The gels were stained co-electrophoretically with diheptyl oxacarbocyanine (panel A), or migrated without carbocyanine. The gels were then fixed and poststained with dipentyl oxacarbocyanine (panel B) or diethyl oxacarbocyanine (panel C)

Table 1 :

 1 MS analysis of proteins stained by different methodsHomologous spots excised from two-dimensional gels (4-8 linear pH gradients, 10% acrylamide) loaded with equal amounts of J774 proteins (200µg) and stained by various methods were digested, and the digests were analysed by MALDI mass spectrometry First column: detection method: CBB= colloidal Coomassie Blue; OF: diheptyloxacarbocyanine, fixation of the spots post excision in aqueous alcohol; ONF: diheptyloxacarbocyanine, no fixation; Ru: ruthenium complex Second and third column: protein name and SwissProt accession number, respectively Fourth column: theoretical Mw and pI Fifth column: sequence coverage of the MS analysis Sixth column: number of observed peptides matching the protein sequence in the database

	STAIN	PROTEIN NAME	ACC.	MW / pI	%C	nb pep.
	CBB HEAT SHOCK PROTEIN 84B	Q71LX8 83229 / 4,57	56%	43
	OF HEAT SHOCK PROTEIN 84B	Q71LX8 83229 / 4,57	57%	49
	ONF HEAT SHOCK PROTEIN 84B	Q71LX8 83229 / 4,57	55%	47
	Ru HEAT SHOCK PROTEIN 84B	Q71LX8 83229 / 4,57	57%	45
	CBB ELONGATION FACTOR 2	P58252	95122 / 6,42	25%	21
	OF ELONGATION FACTOR 2	P58252	95122 / 6,42	34%	29
	ONF ELONGATION FACTOR 2	P58252	95122 / 6,42	31%	24
	Ru ELONGATION FACTOR 2	P58252	95122 / 6,42	54%	41
	CBB	HEAT SHOCK COGNATE 71 KDA PROTEIN	P63017	70827 / 5,37	56%	36
	OF	HEAT SHOCK COGNATE 71 KDA PROTEIN	P63017	70827 / 5,37	53%	37
	ONF	HEAT SHOCK COGNATE 71 KDA PROTEIN	P63017	70827 / 5,37	63%	44
	Ru	HEAT SHOCK COGNATE 71 KDA PROTEIN	P63017	70827 / 5,37	56%	29
	CBB TRANSKELOTASE	P40142	67588 / 7,23	50%	32
	OF TRANSKELOTASE	P40142	67588 / 7,23	56%	23
	ONF TRANSKELOTASE	P40142	67588 / 7,23	48%	25
	Ru TRANSKELOTASE	P40142	67588 / 7,23	64%	39
		UBIQUINOL-CYTOCHROME-C
	CBB	REDUCTASE COMPLEX CORE	Q9CZ13 52735 / 5,75	53%	30
		PROTEIN I, …
		UBIQUINOL-CYTOCHROME-C
	OF	REDUCTASE COMPLEX CORE	Q9CZ13 52735 / 5,75	52%	22
		PROTEIN I, …
	ONF	UBIQUINOL-CYTOCHROME-C REDUCTASE COMPLEX CORE	Q9CZ13 52735 / 5,75	38%	16