Preface

Sustainable agriculture implies solving not only problems of food production but also environmental problems. The diffusion of progress and the evolution of techniques should allow the solution of some of the problems of mankind without any tension or catastrophic events. However, as with any scientific breakthrough, new pesticide knowledge is often applied too fast to solve practical issues. If pesticides could be as effective as claimed by manufacturers, they should contribute significantly to the satisfaction of human requirements.

The International Meeting entitled "Crop Protection" was held in Aix-en-Provence, France, and organised jointly by the "Groupe Français des Pesticides" and the "Mediterranean Group of Pesticide Research". During the opening session Drs. Paolo CABRAS, Michel MONTURY and Jean François COOPER quoted: "Semantically, this word "pesticide" should seem more "positive" than certain other terms such as "biocide" or even "antibiotic", which, based on current usage, is a far more acceptable term, notwithstanding the fact that both terms simply refer to potential biological activity. The reasoning behind this may simply lay in the general subconsciousness -the first affects man via his food whilst the other two supposedly affect only parasites. The reflex is entirely human -what is harmful is bad, what is beneficial is good, or so it would seem! And yet, if we turn the clock back just one or two centuries, these "pest eradicators", capable of saving our harvests and, no doubt, our lives as well, would have been welcomed with open arms. More recently, when the potato colorado beetle, downy mildew or powdery mildew threatened to wipe out our harvests and our heritage, we survived the use of agrochemical products quite well. What's more, they are put to good use, replacing certain jobs in the fields, and therefore making our lives that much easier."

But the overconsumption of pesticides, largely supported by the agrobusiness, has and will have major impacts on ecosystems. The ecological consequences are not yet fully known for several reasons such as the lack of knowledge on the behaviour of pesticides and their metabolites in complex ecosystems. Moreover, few impact studies have been undertaken in specific crop production areas such as crops under Mediterranean climate. The selected articles of this meeting highlight the need to conduct more investigations into the interactions, the reactivity and the transfer of pesticides.

Dr. Fabienne Trolard

Article published by EDP Sciences and available at http://www.edpsciences.org/agro or http://dx.doi.org/10.1051/agro:2005023


Patricia Thébault

Simon De Givry

Thomas Schiex

Christine Gaspin
email: gaspin@toulouse.inra.fr

Combining constraint processing and pattern matching to describe and locate structured motifs in genomic sequences

In molecular biology and bioinformatics, searching RNA gene occurrences in genomic sequences is a task whose importance has been renewed by the recent discovery of numerous functional RNA, often interacting with other ligands. Even if several programs exist for RNA motif search, no program exists that can represent and solve the problem of searching for occurrences of RNA motifs in interaction with other molecules.

In this paper, we present a CSP formulation of this problem. We represent such RNA as structured motifs that occur on more than one sequence and which are related together by possible hybridization. Together with pattern matching algorithms, constraint satisfaction techniques have been implemented in a prototype MilPat and applied to search for tRNA and snoRNA genes on genomic sequences. Results show that these combined techniques allow to efficiently search for interacting motifs in large genomic sequences and offer a simple and extensible framework to solve such problems.

Introduction

Our understanding of the role of RNA has changed in recent years. Firstly considered as being simply the messenger that converts genetic information from DNA into proteins, RNA is now seen as a key regulatory factor in many of the cell's crucial functions, affecting a large variety of processes including plasmid replication, phage development, bacterial virulence, chromosome structure, DNA transcription, RNA processing and modification, development control and others (for review [Storz, 2002]). Consequently, the systematic search of non-coding RNA (ncRNA) genes, which produce functional RNAs instead of proteins, represents an important challenge.

RNA sequences can be considered as texts over the four letter alphabet {A,C, G,U}. Unlike double-stranded DNA, RNA molecules are almost exclusively found in an oriented (left or 5' to right or 3') single-stranded form and often fold into more complex structures than DNA by making use of so called complementary internal sequences. This characteristic allows different regions of the same RNA strand (or of several RNA strands) to fold together via a variety of interactions to build structures that are essential for the biological function. The level of organization relevant for biological function corresponds to the spatial organization of the entire nucleotides chain and is called the tertiary structure. The most prevalent interactions which stabilize folded molecules are stacking and hydrogen bonding between nucleotides on strands oriented in antiparallel directions. Similarly to what exists in DNA, hydrogen bonds appear mostly between specific pairs of nucleic acids to form G-C and C-G or A-U and U-A bonds. Therefore the interactions inside an RNA molecule usually involve one part of a molecule and the nucleic acid complement of a another part of the same molecule (for example, 5'-ACUCGA-3' and 5'-UCGAGU-3'), and the two antiparallel regions bind together.

All together, these interactions define the molecule threedimensional structure which is essential to characterize its function and interactions with other molecules. Due to the difficulty of determining such three dimensional RNA structures, one first explores the so-called RNA secondary structure, a simplified model of the RNA three dimensional tertiary structure.

This secondary structure gives only a subset of those interactions represented by C-G, G-C, A-U, and U-A pairs and provides an important constraint for determining the three dimensional structure of RNA molecules.

An RNA molecule secondary structure can be represented on a circular planar graph where the N nucleotides of the sequence are represented as vertices and are connected by edges representing either (along the circle) covalent bonds between successive nucleotides in the RNA sequence or (inside the circle) hydrogen bonds between nucleotides from different regions. Such a graph gives rise to characteristic secondary structural elements (see Fig. 1) such as helices (a succession of paired nucleotides), and various kinds of loops (unpaired nucleotides surrounded by helices).

A more complete definition of secondary structure of RNA allows for crossing edges in the representation graph making possible the representation of another type of helix usually called a pseudoknot (see Fig. 1). RNA structures can also include nucleotide triples inside triple helices... This definition extends the usual definition which is often limited to planar structures (therefore excluding pseudo- knots and multiple helices) and is always restricted to intrasequences interactions.

A U C G G C U A C C G G G A C G A A A A A A A U A U A G C C C G C A A U C A G C A G U U G A A A U U U U G G A U A C G G 5' 3'
In this paper, we use the extended definition where the secondary structure of an RNA gene is defined as the set of paired nucleotides which appear in the folded RNA, including possible pseudoknots, triple helices but also duplexes which are possible bindings forming helices with other RNA molecules.

Screening a sequence database with tools designed for sequence similarity search quickly reveals similarities between the query sequence and a range of database sequences. This can be achieved for ribosomal rRNA sequences and other ncRNAs recently reported in the literature (although it is difficult to establish the beginning and end of the RNA in question). But the nucleotide sequence of the RNA itself is poorly conserved, the observation that the functionally important structural regions are usually conserved in an RNA family (see for example Fig. 2) allows one to search for those elements that characterize the family more precisely.

Thus, the information contained both in the sequence itself and the secondary (tertiary) structure can be viewed as a biological signal to exploit and search for. Thus, whatever the method, it appears necessary to include both conserved primary sequence elements and higher order structure elements as signals to screen for. These common structural characteristics can be captured by a signature that represents the structural elements which are conserved inside a set of related RNA molecules.

We focus here on the problem of searching for new members of a gene family given their common signature. Solving this problem requires (1) to be able to formalize what a signature is and what it means for such a signature to occur in a sequence (2) to design algorithms and data-structures that can efficiently look for such occurrences in large sequences. For sufficiently general signatures, this is an NP-complete problem [Vialette, 2004] that combines combinatorial optimization and pattern matching issues.

Traditionally, two types of approaches have been used for RNA gene finding: signatures can be modelled as stochastic context free grammars (excluding pseudo-knots or complex structures) and then searched using relatively time consuming dynamic programming based parsers. This is e.g. used in [START_REF] Sakakibara | [END_REF]Eddy and Durbin, 1994] for RNA genes or in [Bockhorst and Craven, 2001] for terminators.

Another approach defines a signature as a set of interrelated motifs. Occurrences of the signature are sought using simple pattern-matching techniques and exhaustive tree search. Such programs include RnaMot [START_REF] Gautheret | [END_REF], RnaBob [Eddy, 1996], PatScan [START_REF] Dsouza | [END_REF], Palingol [START_REF] Billoud | [END_REF] and RnaMotif [START_REF] Macke | [END_REF]. Although most allow pseudo-knots to be represented, they have very variable efficiencies and are all restricted to single RNA molecule signatures.

In this paper, we clearly separate the combinatorial aspects from the pattern matching aspect by modelling a signature as a CSP. The CSP model captures the combinatorial features of the problem while the constraints use pattern matching techniques to enhance efficiency. This combination offers an elegant and simple way to describe several RNA motifs in interaction and a general purpose efficient algorithm to search for occurrences of such motifs.

Methods

The CSP formalism (see e.g. [Dechter, 2003]) is a powerful and extensively used framework for describing combinatorial search problems in artificial intelligence and operations research. This is usually well adapted to the definition of mathematical problems raised by molecular biology (see [Gaspin and Westhof, 1994;Muller et al., 1993;Altman et al., 1994;Major et al., 1991;Barahona and Krippahl, 1999]) and has been used to model the structured motif search problem in [START_REF] Eidhammer | A constraint based structure description language for biosequences[END_REF]Policriti et al., 2004].

Structured motifs as CSPs

The elements that may characterize an RNA gene family are usually described:

• in terms of the gene sequence itself (e.g. it must contain some possibly degenerated pattern);

• in terms of the structures the sequence creates: loops, helices, hairpins and possible duplexes with other molecules;

• by specifying how these various elements are positioned relatively to each other.

A possible occurrence of such a structured motif on a genomic sequence can be described by the positions of the various elements on the genomic sequence. A true occurrence is such that the required patterns, structures actually appear in the genomic sequence and are correctly positioned relatively to each other. Note that a genomic sequence is represented as a string defined over the RNA alphabet {A,U, G,C}.

A natural CSP model emerges from this description: the variables will represent the positions on the nucleotide sequence of the elements of the description. More formally, each variable x i ∈ X will represent a position on an associated RNA sequence (denoted t i ). The initial domain of variable x i , unless otherwise stated, will therefore be equal to [1, |t i |]. In order to represent information on required patterns, structures and on relative positions of these elements, constraints will be used. To describe a constraint we separate the variables x i , ..., x j involved in the constraint (its scope) and possible extra parameters p 1 , ..., p k that influence the actual combination of values that are authorized by the constraint. Such a constraint will be denoted as name[p 1 , ..., p k ](x i , ..., x j ). We now introduce the basic constraint types which are useful for RNA signature expression: composition[word, error, type err ](x i ) this unary constraint is satisfied iff some given sequence (a pattern) occurs at position x i on sequence t i . The pattern that must occur is specified by the following constraint parameters:

• word is a word on the so-called IUPAC alphabet which includes meta-characters that match several characters of the RNA alphabet.

• error specifies the maximum number of tolerated mismatches between an occurrence and the specified string.

• type err indicates if the error count is interpreted under the Hamming or Levenstein distance metric [START_REF] Smith | TF Smith and MS Waterman. Identification of common molecular subsequences[END_REF].

An example of possible use of this constraint is illustrated in Fig. 3(1) where variable x 1 is constrained to a position where the AGGGCUAG pattern must appear with no error. A position satisfying this constraint (or occurrence of the pattern) is indicated by the arrow.

distance[l min , l max ](x i 1 , x i 2 )
this binary constraint is use to enforce the relative position of elements. It is satisfied iff

l min ≤ x i 2 -x i 1 ≤ l max
The parameters l min , l max specify the bounds for the difference between the two position variables. It is a simple usual arithmetic constraint.

helix[rule, error, type err , l min , l max , b min , b max ](x i 1 , x i 2 , x i 3 , x i 4 ) this 4-ary constraint is used to enforce the existence of an helix between the sequence regions delimited by [x i 1 , x i 2 ] and [x i 3 , x i 4 ]. This constraint assumes that the four variables are related to the same sequence (it models intra-sequence interactions) and each region represents a substring of this sequence. The length and distances between these regions are also constrained. The constraint must be specified by the following parameters:

• rule: a binary relation on the RNA alphabet that characterizes which pairs of nucleotides are allowed inside an helix. For an RNA helix, one typically uses Watson-Crick (A-U and G-C) pairs,possibly extended with Wobble (G-U) pairing.

• error: the maximum number of tolerated mismatches between the two regions (nucleotides that do not satisfy the previous paring relation).

• type err : the Hamming or Levenstein distance metric for error counts.

Algorithms and implementation

Given such CSPs, our problem is to find all solutions. Compared to usual applications of the CSP formalism, this one is characterized by the potential huge domain size (the length of a complete pseudo-molecule can be greater than several million of nucleotides) and its specific constraint types (except for the distance constraint which is a usual arithmetic constraint). For efficiency and memory space reasons, it is not possible to represent variable domains exhaustively and to enforce arc consistency on them. As it is done in Constraint Programming [Dechter, 2003], we represent the domain of each variable x i by an interval [lb i , ub i ] and reason only on domain bounds as done in arc-bound consistency [Lhomme, 1993]. This limited bound filtering is done at each node inside a usual tree search algorithm. For n-ary constraints, the typical form of local consistency used enforces the fact that the bounds in the domain of one variable in the constraint scope must participate in at least one tuple that is authorized by the constraint and the other domains. The exploration method we used is a depth-first search algorithm with a refutation mechanism (during backtracks, it propagates the removal of values

Dedicated constraint propagation

For each type of constraint, we developed specific filtering algorithm using appropriate pattern matching algorithms (except for the distance constraint where we used the filtering algorithm described in [Hentenryck et al., 1992]):

• composition[...](x i ): to enforce arc consistency on the lower bound of the domain of x i , one can simply update this to the position of the first occurrence of the pattern after lb i in the text t i . To find this occurrence, the algorithm of Baeza-Yates and Manber [START_REF][END_REF]Wu and Manber, 1991] is used. This algorithm is based on a boolean representation of the search state and exploit the intrinsic parallelism of bitwise logical operations in modern CPU. It has a linear complexity for exact string search and a complexity in O(m × n) for the Levenstein distance (m being the length of the text and n that of the pattern sought). A similar processing can be done on the other bound (but is not used in our prototype). • helix[...](x i 1 , x i 2 , x i 3 , x i 4 ): Consider for example variable x i 1 . To filter x i domain, we must find the first helix (a support) that satisfies the parameters of the constraint. By first we mean the helix with the smallest position of the 5' extremity of the first arm (pointed by x 1 ). The problem for helices (which can be seen as two related substrings) is more complex than for composition since the two strings are initially unknown. This makes it impossible to use string matching algorithms relying on a preprocessing of the string searched. The most naive approach that successively tries all possible positions for the first and second string is obviously quadratic. However, in our case, the distance between the regions where the words may appear is constrained by the length parameters b min and b max . Together with parameters l min and l max , this makes the complexity of the naive approach linear in the text length. This is therefore the method implemented. A similar approach can be used for other bounds. • duplex[...](x 1 , x 2 , y 3 , y 4 ): this constraint differs from the previous one by the precise fact that there is no

C U A UACUACA 1234567 U C A A U A C U A C UACU ACUA CUAC UACA [ 2 ,5 ] [1,3] [ 1 ,1 ] [2 ,2 ] [ 3 ,6 ]
Figure 6: The k factor tree (with k = 4) for UACUACA. This data structure represents the set of substrings of length 4 of the text.

possible b min and b max parameters since the two interacting substrings do not necessarily appear on the same sequence. The previous naive approach is therefore impractical. We decided to use a specialized version of suffix-trees [McCreight, 1976;Ukkonen, 1992] that captures occurrences of patterns of bounded length. This data structure, called a k-factor tree [Allali and Sagot, 2003] allows to perform string search in time linear in the length of the pattern searched (independently of the text length). The data structure, illustrated in Fig. 6, is built once before the search, in space and time linear in the length of the text [McCreight, 1976;Ukkonen, 1992]. The associated filtering algorithm does not enforce generalized bound arc consistency but is only triggered when one of the two variables x 1 or y 3 is assigned. All the occurrences of the Watson-Crick reverse complement can then be efficiently found in the k-factor tree and used to update the bounds of the other variables (the position of the first and last possible occurrences define the new bounds).

Because these constraint propagation are quite expensive compared to the simple distance constraint, and in order to avoid repeated useless applications of the filtering algorithms, once a support is found it is memorized and will not be sought again until one of its value is deleted (as in AC2001 [Bessiere and Regin, 2001]).

Results and discussion

This approach has been implemented in C++ and results in a specific solver called MILPAT: Motifs and Inter-moLecular motifs searching tool using csP formAlism and solving Techniques. We tested our approach on different RNA gene search problems in order to assess its efficiency and modelling capacities.

tRNAs

The tRNA structure and sequence profiles are perhaps the best studied among RNAs; hence, they are very appropriate for a first benchmarking.

tRNA genes include four helices corresponding respectively to A-stem (7 nucleotide pairs), D-stem (from 3 to 4 nucleotide pairs), C-stem (5 nucleotide pairs) and T-stem (5 nucleotide pairs), six loops corresponding respectively to the single strand between A-stem and D-stem (sequence UN with U invariant), D-loop (4 to 14 nucleotides), the single strand between D-stem and C-stem (one nucleotide), C-loop ( 6 to 60 nucleotides), the single strand between C-stem and T-stem (also called V-loop, 2 to 22 nucleotides), T-loop (NUC).

The signature of tRNAs used here is deliberately a simple one that can be modelled in all existing general purpose tools. We have concentrated on finding sequences that can adopt a cloverleaf-like secondary structure within given ranges of stem and loop lengths. We searched the Escherichia coli and Saccharomyces cerevisiae genomes.

We compared the time execution of MILPAT with three other general purpose programs. The tRNA signature used in our comparisons is from Gautheret and al. [START_REF] Gautheret | [END_REF]. It includes four helices constraints, 14 distance constraints and 2 composition constraints (see Fig. 4). The results of this comparison are shown in Table 1. For each genome search test, all the programs gave the same number of solutions (545 solutions are found for the E. coli genome and 849982 for the S. cerevisiae genome).

On the computing efficiency basis, three groups may be formed from the slowest to the fastest: (i) RnaMot and RnaMotif, (ii) Patscan and MILPAT with variable selection order A, and (iii) MILPAT with variable selection order B. It is well known that variable assignment order may have a significant influence on efficiency. The static order A used by MILPAT consists in ordering variables according to the topological order of the elements in the structured motif, from 5' to 3'. Order B is a dynamic order following the first fail principle: most constrained variables are chosen first by the backtrack algorithm. Without this order, MILPAT already has an execution time close to the most efficient program, PatScan. Just changing the order leads to an early pruning of the search tree and a considerably improved execution speed for Saccharomyces cerevisiae.

snoRNAs

To validate the ability of MILPAT to model interactions between different molecules, we performed a computational scan of the Pyrococcus abyssi genome for C/D snoRNA genes. Since no existing general purpose tool allows to model interaction between a snoRNA and its target, we compared MILPAT to Snoscan, a tailored software for the C/D snoRNA genes. This program sequentially identifies six specific components of these genes (see Fig. 5): a RUGAUGA string (so called C box), a sequence region, able to form a duplex with another "target" sequence and a CUGA string (so called D box). We used a S. cerevisiae tailored version of snoScan as no archae-bacteria version is available. This fact probably explains the limited sensitivity shown in

Conclusion

The main aim of our work is to offer a way of describing new generations of RNA patterns, including the specification of complexes which can be formed by anti-sense interactions between different regions of a genome. The use of CSP methodology together with efficient pattern matching data structures and algorithms provides increased efficiency, extended modelling capabilities for intermolecular interactions and an easily extensible framework. Beyond this ability to describe inter and intra-molecular interactions with a great flexibility, a number of evolutions are possible to improve MILPAT efficiency and modelling capabilities, including the ability to describe optional or alternative motifs. Within the framework of biological applications, these possibilities are essential to be closer to the structural reality of the molecules.

In its current version, MILPAT is just providing all the true occurrences (satisfying all constraints). It does not optimize any scoring system based on mismatches, thermodynamics or probabilistic parameters. Taking into account such information would require the use of more complex Weighted CSP algorithms such as in [START_REF] Schiex | [END_REF]Larrosa and Schiex, 2004].

Figure 2 :

 2 Figure2: Alignment of a subset of ten sequences of the tRNA family extracted from the RFAM RNA database (http://www.sanger.ac.uk/cgi-bin/Rfam). Each line gives the tRNA gene sequence. Both sides of each helix are underlined for each sequence of the alignment. Consensus helices are identified by boxes at the end of the alignment. tRNA genes include four helices corresponding respectively to helix 1 called A-stem (7 nucleotide pairs), helix 2 called D-stem (from 3 to 4 nucleotide pairs), helix 3 called C-stem (5 nucleotide pairs) and the last fourth helix, called, T-stem (5 nucleotide pairs). Six loops corresponding respectively to the single strand between A-stem and D-stem (sequence UN with U invariant), D-loop (4 to 14 nucleotides), the single strand between D-stem and C-stem (one nucleotide), C-loop ( 6 to 60 nucleotides), the single strand between C-stem and T-stem (also called V-loop, 2 to 22 nucleotides), T-loop (NUC) allow to build a signature of the family. Note several hundred tRNA sequences are now available from biological databanks (see in particular RFAM).

Figure 4 :

 4 Figure 4: (A) Signature of tRNA genes family. White circles : nucleotides with unknown composition, black circles : known composition, little circles : number of nucleotides given by an interval, and edge : interaction between two nucleotides. (B) Corresponding CSP model.

Figure 5 :

 5 Figure 5: Signature of snoRNA genes family including its target interaction.

Table 1 :

 1 Comparison of the time efficiency.

	Software	E. coli	S. cereviciae
	(genome size)	(4.610 6 )	(12.0710 6 )
	PatScan	1 min. 32	1 h 40
	RnaMotif	4 s.	8h40
	RnaMot	2 min.	92 h
	MILPAT (order A)	39 s	1 h52
	MILPAT (order B)	39 s	20 min.

Table 2 .

 2 The descriptor

	Software Solutions True positives	Time
	SnoScan	1611	27	20 min.
	MILPAT	852	42	8 s.

Table 2 :

 2 Pyrococcus abyssi genome (1.710 6 characters) -59 annotated snoRNAs. used by MILPAT is described in Fig.5. The missing annotated genes (17 out of 59) are due to the current limitation of the duplex constraint to Watson/Crick matches. These first results show the modelling flexibility and solving efficiency of MILPAT.

The constraint graph contains one variable with a unary constraint represented by a loop. (case 2): an helix and a loop defined by two related segments separated by specified lengths. The constraint graph contains four variables, four implicit distance constraints represented by edges and one hyper-edge (for the helix constraint) connecting all four variables with a rectangle in the middle. (case 3): a duplex composed of two independent substrings (from two sequences). The constraint graph is similar to the previous one (two distance constraints are removed). (cases 4 and 5): two helix constraints can describe a pseudo-knot (4) or a triple helix (5).

• l min , l max : the interval specifying possible lengths of the two substrings.

• b min , b max : the interval specifying the possible distance between the two substrings (i.e., x i 3 -x i 3 ).

This constraint is illustrated in Fig. 3(2), involving variables x 1 , x 2 , x 3 and x 4 . Assuming Watson-Crick pairing, no error and suitable lengths, the constraint is satisfied for the values indicated by arrows on the sequence below.

duplex[l min , l max ](x 1 , x 2 , y 3 , y 4 ) this 4-ary constraint is used to enforce the existence of a (Watson-Crick based) duplex between the regions delimited by [x 1 , x 2 ] and [y 3 , y 4 ]. Although semantically equivalent to the previous one, it does not assume that the two substrings represented by the two regions belong to the same sequence. This has important computational impact. Only Watson-Crick pairing is considered. This constraint is used to model RNA-RNA interactions between possibly different molecules.

• l min , l max : the interval specifying possible lengths of the two substrings.

The constraint is illustrated in Fig. 3(3) involving x 1 , x 2 (on one sequence) and y 3 and y 4 on another sequence. Values satisfying the constraint (an occurrence) is indicated by the arrows.

Note that together these constraints can describe more complex structures like pseudo-knots (Fig. 3(4)), triple helices (Fig. 3(5)), and so on.

The flexibility of the CSP formalism using simply the four previous basic constraints can be illustrated on famous RNA gene families. The tRNA signature is represented in Fig. 4 where tRNA genes include four helices. The corresponding CSP is build from 16 variables (the variable numbering follows the 3' → 5' orientation) with 15 distance constraints (one constraint between each successive pair of variables), 2 composition constraints and 4 helix constraints.

The same process can be applied to the snoRNA signature depicted in Fig. 5. snoRNA genes include a C box (RUGAUGA) with one error allowed, a single strand from 22 to 44 nucleotides, a duplex with a target RNA from 9


Pavel Diev
email: pavel.diev@banque-france.fr

Walid Hichri

Dynamic voluntary contributions to a discrete public good: Experimental evidence *

Keywords: Public Goods, Experiments, Voluntary contributions, Dynamic contributions JEL Classification: C92; H41

We experiment a mechanism for the provision of a discrete public good where individuals are allowed to update upwards their contribution during a fixed time interval. Experimental evidence shows that the subjects are increasing their contributions in order to finance the cost of the good. The public good is financed more frequently when its cost is low relative to the social willingness to pay.

Introduction

Consider the following example of a real situation captured by our framework. Ph.D. students in a research lab want to jointly buy a new workstation. In order to buy it at a special tariff they must order it before the end of the week. During the current week they can at any moment write a check towards the purchase of the machine. The director of the lab collects the checks and announces the total amount collected each time he receives a check. A student that already wrote one or several checks can write another one at any time. At the end of the week, if the sum of the checks covers the cost, the workstation is bought. If the total amount is larger than the cost the director can dispose at will of the extra amount (no refund of extra contributions). If the total amount is less than the cost the checks are destroyed (refund of contributions). In this paper we perform an experiment for this situation.

Theory says that, in itself, dynamic structure of contribution to a public good cannot lead to an efficient outcome, see Fersthman and Nitzan (1991), [START_REF] Admati | Joint Projects without Commitment[END_REF], [START_REF] Gradstein | Time Dynamics and Incomplete Information in the Private Provision of Public Goods[END_REF]. The reason for negative results is that introducing dynamics allows individuals to free ride upon future contributions. This can be counteracted by assuming some form of punishment for free riders. For example, [START_REF] Marx | Dynamic Voluntary Contributions to a Public Project[END_REF] assume that the individuals commit to stop contributing if some individual contributes 0 in the current period. In our paper the punishment stems from the introduction of a fixed contribution period and a discrete public good. That is, there is no benefit from contributing if a given total amount is not reached and individuals cannot delay infinitely their contribution if they want to obtain some positive gain.

With regard to the experimental analysis of the dynamic public goods games the experiment in our paper presents similarities with the one in [START_REF] Dorsey | The voluntary contributions mechanism with real time revisions[END_REF]. Dorsey is interested in the relationship between the production technology of the public good and the amount collected, while we are mainly concerned with the efficient provision of the discrete public good. As in our paper, Dorsey allows the individuals to update their contribution during a fixed period. He uses linear public good production technologies which are continuous save for the following: if a given minimum amount of total contributions is not reached, the good is not provided at all, but the individuals are not refunded. There are two types of possible updates, increase or decrease. All individuals are originally given the same amount of (experimental) money-that is, they have identical WTP. By contrast, in our paper, we allow only increasing updates. We have a binary production function: either the good is produced in a given amount, or it's not produced at all. The individuals do not pay anything if the good is not provided and individuals are originally given different amounts of (experimental) money-that is, they have heterogeneous WTP.

Another related experimental paper is [START_REF] Levati | An Application of the English Clock Market Mechanism to Public Goods Games[END_REF]. The authors consider a situation where the contributions are increasing at a fixed rate (English clock mechanism) and an individual can decide to stop contributing (i.e. exit the game) at any moment, and never contribute again. The decision to stop contributing is observed by the others. In contrast, in our paper, an individual can increase his contribution freely, and can only see the total amount collected but not each individual's contribution. Furthermore, Levati and Neugebauer assume identical WTP which are common knowledge, and a linear production function. In contrast, we assume heterogeneous WTP which are private information, and a discrete public good.

Experimental design

The experiments are conducted by groups of four subjects, n = 4. Two of the subjects are endowed with 100 tokens (i.e. experimental money) and the two others with 200 tokens, W T P i = {100, 200}. The endowments are private information. As in [START_REF] Hichri | Interior Collective Optimum in a Voluntary Contribution to a Public Goods Game[END_REF] we run two treatments with different levels of social surplus. In the first treatment the cost of provision of the public good, c, represents 60% of the sum of the individual WTP ( 4i=1 W T P i = 600), that is, the cost of provision is 360 tokens. 1 In the second treatment the cost c represents 80% of the sum of the WTP, that is, 480 tokens. 2 The time interval for contribution, T , is fixed to 90 seconds.

The experiment was run in January 2004 at LeeX (Laboratori d'Economia Experimental), University Pompeu Fabra in Barcelona. Each treatment included two experimental sessions of about one hour and a quarter. In each session we set three independent groups. This gives six independent statistical observations per treatment and requires 24 subjects per treatment (48 for the whole experiment). All of them were students selected randomly on the campus.

Each group played one practice period, followed by 20 paying periods. At the end of each period each subject was informed about the number of tokens he had earned. The number of subjects in a group, n, the provision cost, c, the length of the time interval, T , and the number of experimental periods was common knowledge. At the end of the session, a questionnaire was distributed to subjects.

The experiment was computerised. We used as software z-Tree, developed by [START_REF] Fischbacher | z-Tree -Zurich Toolbox for Ready made Economic Experiments-Experimenter's Manual[END_REF]. At the beginning of each session, subjects were affected randomly to each computer. The experimenter read instructions loudly 3 . Any questions were answered publicly. During the experiment communication was forbidden.

Subjects were paid privately and in cash at the end of the experiment. The payment of a player was equal to the amount of tokens he won converted into euros according to the rate 100 tokens = 1 euro plus 6 euros as show up fees.

Results

We are primary interested on the ability of the mechanism to provide efficiently the public good. A second question is: how do individuals behave during the interval of 90 seconds; in particular do they increase their contributions? To study the efficiency of the mechanism, we look on the total amount of contributions after 90 seconds and we construct an index, denoted Ef , representing the ratio of the number of times a group succeeded in contributing an amount sufficient for providing the public good (≥ c) over the total number of playing periods.

Low threshold treatment (c = 360)

From Figure 1 we observe that in the first experimental periods some subjects (groups 1, 2 and 4) contribute big amounts, bigger than their WTP for instance. The reason is that they have not understood the game. Because their payoff was negative, they quickly learned not to contribute more that their WTP. Thus, we dropped out the first 5 periods from the analysis of the results, considering them as learning periods. The ratio Ef was computed over the 15 last periods. We observe that the total amount of contributions is close to the cost of provision, even if it is less than c in some periods or slightly larger than c in other periods. When the amount exceeds the cost of provision, we find out that this is because at the end of the period (in the last 3 seconds) several individuals contribute simultaneously in order to complete the project. On average the public good is financed 65.5% of the time.

Turning to individual behaviour, Figure 2 reports the average contribution of each individual inside a period, that is, after 15, 30, 45, 60, 75 and 90 seconds. This average is calculated over the 15 last periods. As it can be seen from the figure, all subjects increase their contribution within the time interval of 90 seconds. This behaviour suggests that they have incentives to reach the cost of provision. Intuitively, the only way to obtain a positive payoff is to contribute a total amount that is greater than c. Acting in favour of this objective requires that subjects have to increase their individual contribution. We could distinguish two main types of behaviour: (1) individuals contributing large amount during the 15 first seconds and contributing only slightly thereafter; (2) individuals contributing low amounts during the first 75 seconds and contributing large amounts during the last 15 seconds. There are also individuals following a mixture of type 1 and type 2 behaviours.

We also observe that subjects with low WTP (W T P i = 100; dashed lines) contribute on average 69% of their WTP that compared to subjects with high WTP whose relative contribution is 52%. This could be explained by a tendency to equal cost sharing observed in groups 5 and 6 (all members contribute nearly 90 tokens regardless their WTP). In groups 2 and 3 this tendency is mitigated by the behaviour of one individual with low WTP who commit to low contributions.

High threshold treatment (c = 480)

As an alternative interpretation of the experiment, the time interval T can be seen as a bargaining period in which a cost-sharing agreement might be found. A benchmark agreement in such a bargaining situation is to share the cost equally. As we saw in the previous section, there is a tendency towards equal cost sharing in some groups. What will happen if equal cost sharing is not compatible with the individual rationality of some individuals? The aim of the second treatment is to give insights to this question. The results can be seen in Table 2 and Figure 3. We observe that the amount of contributions exceeds the cost of provision less frequently. On average the public good is financed 24.7% of the time. In other words, subjects have more difficulties to find a cost-sharing agreement. Intuitively, the reason might be that the set of agreements compatible with individual rationality is now restricted making it harder to reach an agreement. Indeed, if the number of agreements that can be explored by a group during a given time interval is fixed, determined by individual's cognitive capacities for instance, restricting the set of possible agreements automatically means that the chances to find an agreement during a fixed time interval are decreased. However, we still observe that the amount of contributions is close to the cost of provision and that in some groups and periods individuals are able to finance the public good. This means that the incentives to finance the cost are still present. This can be recognised from Figure 4, where we can see that subjects are increasing their contributions during the interval. We also observe that subjects with low WTP (W T P i = 100; dashed lines) contribute now on average almost the same relative amount than subjects with high WTP, 72% and 71% respectively. This indicates that subjects have understood that equal cost sharing is no possible, but eventually they had no enough time to find a different cost-sharing agreement, leading to less frequent provision of the public good 4 . Unfortunately, because of budgetary constraints we were unable to test if increasing the contribution interval would improve the efficiency of the mechanism. This is left for future research.

Conclusion

Experimental results have to be interpreted with great caution as they are sensitive to the design of the protocol and provide a limited number of independent observations such that general conclusions are not possible. Nevertheless, the experimental evidence that we provide in this paper shows that using a dynamic voluntary contribution mechanism to provide a discrete public good would induce incentives for the individuals to increase their contribution. This behaviour could be explained by the intuition that each individual have an interest to act in favour of the objective of providing the public good. In other words, we have a situation where when acting in favour of his own interest an individual also acts in favour of the interest of the society.

6 Figure 1 :

 61 Figure 1: Contribution of each group over the 20 experimental periods (low treatment)

Figure 2 :

 2 Figure 2: Individual contribution inside a period (low treatment)

6 Figure 3 :

 63 Figure 3: Contribution of each group over the 20 experimental periods (high treatment)

Figure 4 :

 4 Figure 4: Individual contribution inside a period (high treatment)

Table 1 :

 1 Efficiency ratio (low treatment)

		Group 1 Group 2 Group 3 Group 4 Group 5 Group 6 Average
	Ef	0.60	0.80	0.73	0.40	0.67	0.73	0.66

Table 2 :

 2 Efficiency ratio (high treatment)

		Group 1 Group 2 Group 3 Group 4 Group 5 Group 6 Average
	Ef	0.07	0.20	0.47	0.27	0.40	0.07	0.25

Note that in the first treatment equal cost sharing imply that every subject has to pay 90 tokens, which is compatible with individual rationality.

In the second treatment equal cost sharing imply that every subject has to pay 120 which is not compatible with the individual rationality of individuals with W T Pi = 100.

Instructions and a screenshot are available upon request.

For comparison, we note that in[START_REF] Dorsey | The voluntary contributions mechanism with real time revisions[END_REF] experiments the time interval was fixed to 180 seconds, i.e. the double of the time given here.