-Three-hybrid screens: inducible third-party systems

INTRODUCTION

Recent studies have brought up the existence of several molecular complexes either stable, like the RNA polymerase II holoenzyme, transcription factor TFIID and mediators, or transient as could be observed in the various steps of the transcription process e.g. initiation, elongation and termination. These observations point out the fact that regulation of different cellular mechanisms is orchestrated by interactions between molecular species either to modify proteins or to position one of them within a complex that then will be functional. Several techniques such as affinity precipitation, glycerol gradient sedimentation and the yeast two-hybrid system are currently used to study protein-protein interactions (1). These various methods, usually investigating the connection between two partners, keep in account only the strong (and stable) interactions and neglect the weaker ones. Considering the complexes studied so far, it is suspected and sometimes shown that interactions often occur between more than two proteins, e.g. to stabilize the complex. In an effort to understand the various biological mechanisms -and in our case gene expression regulation-, we were interested in developing the yeast three-(or tri-)hybrid system.

, is based on the reconstitution of a transcriptional activator complex either to search for or to study a protein that interacts with two others and to acquire information about ternary complex assembly (2). This technique detects direct or mediated interactions between two fusion proteins that contain either a DNA binding domain (DBD; the DBD-X protein) or an activation domain (AD; the AD-Y protein). In some cases, when these two hybrid proteins interact weakly or not at all, a third partner (the protein Z) is necessary to promote (to induce) the formation of the transcriptional activator allowing the transcription of the reporter genes. Thus, specific and stable protein-protein interactions between X, Y and Z lead to the activation of the reporter genes that are integrated in the yeast genome. The HIS3 reporter gene contains a specific DNA sequence which can be recognized by the DBD of the transcriptional activator. Activation of the HIS3 gene permits the endogenous synthesis of histidine allowing the yeast to grow on histidine-lacking media. Activation of the LacZ gene, another reporter gene containing the same DNA binding element, will lead to the synthesis of the β-galactosidase (β-Gal) that catalyses the transformation of either X-Gal (5-bromo-4-chloro-3-indolyl β-D-galactopyranoside) or ONPG (o-nitrophenyl-β-Dgalactopyranoside) into a detectable blue or yellow product, respectively.

), an enzyme that will not necessarily be part of the reconstituted transcriptional activator.

) by interacting with, or enzymatically modifying, one of the two main partners, thus preventing their interactions. This will result in the inhibition of the expression of the reporter genes followed by growth restriction on histidine-lacking media as well as repression of the β-Gal activity.

In order to control the specificity of the ternary complex formation that depends on the expression of one of its components, we have set up an inducible three-hybrid system, in which the expression of the third partner Z can be easily switched "on" or "off". Therefore we have used the already characterized yeast Met25 promoter (3). Excess of methionine in the culture medium leads to the transcriptional repression of a cDNA cloned downstream of this promoter. Thus, we have designed the two plasmids, pBridge and pLexA9-3H (Fig. 2, left panel), containing first the DNA of either GAL4 or second LexA DBD, which can be fused to the cDNA of the X protein, and second the methionine regulated expression cassette, containing the Met25 promoter, which can be fused to the cDNA of the third partner Z.

Figure 1: The three-hybrid system

The three-hybrid system can be used to characterise or detect new factors such as (A) a bridging factor Z, which interacts with both proteins, X and Y, that do not interact each other, (B) a stabilising factor Z that strengthens a weak interaction between the two proteins X and Y, (C) a regulating factor Z that stimulates the interaction between the two fused proteins X and Y by modifying one of them, (D) an inhibitor Z that prevents the interaction between two interacting proteins X and Y. In the three first cases, upon expression of the third partner (Z) the transcriptional activator formed stimulates the transcription of the reporter genes whereas in the last case, the third polypeptide inhibits the transcriptional activator formation thus preventing the transcription of the reporter genes.

The inducible third partner Z as Activator

In order to reconstitute the transcriptional activator, the third partner Z (as shown in Figure .1: A,B,C) can be overexpressed in the absence of methionine. We have illustrated this feature with the formation of the cdk-activating kinase (CAK) that contains three subunits: a cyclin dependent-kinase, cdk7, the cyclin H and MAT1, a stimulatory factor (4). Although the role of CAK, a subcomplex of the multiprotein complex TFIIH, is not well known in the various events that regulate the cell cycle cascade, it seems to play a role in protein coding gene transcription through the phosphorylation of the carboxy-terminal domain (CTD) of RNA polymerase II (5). It has been shown that cdk7 and cyclin H interact with each other but the role of MAT1 in the assembly of CAK was still unknown (6, 7). Using the three-hybrid system, we could demonstrate that the weak interaction between the two fused proteins DBD-cdk7 (X) and AD-MAT1 (Y) was stabilized upon expression of the third partner, cyclin H (Z), cloned in the Met25 expression cassette (8). This assembly does not occur in the presence of methionine that prevents the expression of cyclin H. This assay shows, that MAT1 contacts cdk7 or integrates the CAK complex in the presence of cyclin H.

The inducible three-hybrid system could be used to screen a cDNA library in order to search for some activating partners. Therefore two different screenings are possible: 1.) To identify proteins (Y) that may target an already formed binary complex (X-Z; see Fig. 1A), the screening is made with a cDNA library inserted downstream of the activation domain (AD) sequence like most of the commercially available cDNA libraries. In this case, in order to isolate positive clones, yeast growth will be performed on a medium lacking methionine; the colonies will then be replicaplated on a medium containing both methionine and X-Gal on which they will no longer grow or stay white. 2.) To identify proteins (Z) that stabilize or regulate a weak interaction (X-Y; see Fig. 1B,C), the cDNA-library must be cloned downstream of the Met25 promoter. The screening is then made on a histidine-lacking medium in the absence of methionine. Positive clones will be identified through a replica-plating on methionine-containing medium as mentioned above.

The inducible partner Z as Inhibitor

As an example to investigate Z components that target either X or Y proteins and consequently prevent the reconstitution of the transcriptional activator, we studied two oncogenic proteins, Raf and Ras (9), involved in signal transduction. The fused DBD-Ras (X) and AD-Raf (Y) proteins specifically interact each other in a two-hybrid system (9). An inhibition of the transcription of the reporter gene can be observed (8) in the absence of interaction between DBD-Ras (X) and AD-Raf (Y). This may occur when the cDNA of a nonfused cRaf is cloned downstream of the Met25 promoter and further expressed as the third partner (Z) in the absence of methionine. In this case, cRaf (Z) competes with AD-Raf (Y) for targetting DBD-Ras (X). Because the Met25 promoter is stronger than the hybrid gene promoter (3), its activation (in absence of methionine) leads to an excess of cRaf titrating out the DBD-Ras. Thus the transcriptional activator will not be reconstituted resulting in the repression of the reporter genes.

MATERIALS 2.1. Growth and maintenance of yeast

1. YPD Medium: 20 g/l Bacto™ Peptone (Difco); 10 g/l yeast extract (Difco); 20 g/l D(+)-Glucose (Riedel-deHaën, Germany); water to 1 l; autoclave at 121°C for 15 min (or add water to 950 ml; autoclave for 30 min, then add 50 ml sterile filtrated 40% D(+)-Glucose). For culture plates add 20 g/l Agar (Difco). 2. Yeast-Minimal Medium (MM): 6.7 g/l yeast nitrogen base without amino acids (Difco); 20 g/l D(+)-Glucose; water to 1 l; autoclave at 121°C for 15 min (or add water to 950 ml; autoclave for 30 min, then add 50 ml 40% D(+)-Glucose). For culture plates add 20 g/l Agar. Depending on the different strains the following amounts of specific nutrients should be added (either as a tenfold stock for small volumes or directly as powder for higher volumes) except the one(s) for which the medium should select: 0.2 g/l L-Tryptophane; 0.2 g/l L-Histidine; 0.2 g/l L-Adenine; 1.0 g/l L-Leucine 0.3 g/l L-Lysine; 0.2 g/l Uracile (Sigma).

Colony lift filter assays

For LexA-transformants, use plates which contain MM with 2% D(+)-Galactose and 1% Raffinose instead of D(+)-Glucose. 1. Hybond™ Nylon membranes (Amersham); 3MM Whatman paper; liquid Nitrogen.

2. X-Gal (5-Bromo-4-chloro-3-indolyl-β-D-galactopyranoside; Merck) solution: 20 mg X-Gal/ml of N,N-Dimethylformamide (DMF; Sigma); store in the dark at -20°C. 3. Z-M-X-buffer: 100 ml Z-Buffer; 0.27 ml β-Mercaptoethanol; 1.67 ml X-Gal solution. 2.5.2. Liquid culture assay 1. Z-M-buffer: 100 ml Z-buffer; 0.27 ml β-Mercaptoethanol. 2. Z-O solution: dissolve 4 mg ONPG (o-nitrophenyl-β-D-galactopyranoside; Sigma)/ ml Z-buffer (prepare ca. 1 hour before each use).

3. 1 M Na 2 CO 3 2.5.3. On-plate assay 1. 10x S-buffer (for 500 ml): 68 g KH 2 PO 4 , 9.9 g (NH 4 ) 2 SO 4 , 21 g KOH; pH≈8.0. X-Gal: as described under subheading 2.5.1. 2. Minimal medium as described under subheading 2.1.

METHODS

Growth and maintenance of yeast

Working with yeast should be done under sterile conditions, because the different culture media do not contain antibiotics. Thus, contaminations should be avoided using sterile glass and plastic ware. It is recommanded to work at a cleanbench or beside a burning flame.

Yeast strains

The strains used in the three-hybrid system are the same that the ones used for the two-hybrid. There are different yeast strains either more or less sensitive for the detection of protein-protein interactions, depending on the vectors, the transcriptional activator (Gal4 or LexA-VP16) and the protein used as the bait (see note 4.1.). The most common yeast strains are the L40 strain (MATa, trp1, his3, leu2, ade2, LYS2::(LexAop) 4 -HIS3, URA3::(LexAop) 8 -LacZ) for the LexA-VP16 system and the HF7c strain (ura3, his3, lys2, ade2, trp1, leu2, LYS2::Gal1 UAS -Gal1 TATA -HIS3, URA3::GAL4 17mersx3 , CyC1 TATA -lacZ) or the Y190 (ura3, his3, lys2, ade2, trp1, leu2, cyh r 2, LYS2::Gal1 UAS -HIS3 TATA -HIS3, URA3::GAL1 UAS -GAL1 TATA -lacZ) when using the GAL4 system. These strains are commercially available.

Yeast amplification

Freshly streaked yeast grow at 28°C for 4-5 days until colonies are 1-2 mm in diameter. One such colony can then be used for amplification in liquid culture. For the maintenance of yeast strains, a colony resuspended in 0.5 ml of sterile water should be restreaked every 6-8 weeks. For long-time storage yeast strains can be stored in the appropriate medium containing 15% glycerol at -70°C.

Plasmid constructs

For the activation experiments we used the LexA-VP16 system. Thus, the bait (cdk7) is linked to the DBD of LexA in pLex9-3H (Fig. 2; left panel) carrying the TRP1 selection gene that allows growth on tryptophane lacking MM. The second partner (MAT1), which has no significant interaction properties with the bait, is fused to the AD of VP16 in pVP16 (Fig. 2; right panel), containing the LEU2 selection gene that allows growth on leucine lacking MM. In addition, the cDNA of the third partner (cyclin H) is cloned in the Met25 expression cassette (see note 4.2.), which is on the same plasmid as the bait (pLex9-3H).

For the inhibition experiments we used the GAL4 system, in which the bait (H-Ras(V12)) is fused to the DBD of GAL4 in pBridge and the interacting partner (cRaf1) is added behind the AD of GAL4 in pGAD-GH. The cDNA of the third partner (cRAF1) is cloned into the Met25 expression cassette, which is on the same plasmid as the bait (pBridge). Left panel: pBridge, derived from the pGBT9 vector, contains the TRP1 selective gene, the DNAbinding domain of GAL4 and the Met25 expression cassette (see note 4.2.) with the NotI and BglII cloning sites. pLex9-3H, derived from the pBTM116 vector, contains the TRP1 selective gene, the DNA-binding domain of LexA and the Met25 expression cassette with the NotI and SrfI cloning sites. The Met25 cassette contains a hemagglutinine (HA) tag sequence, a nuclear localisation signal (NLS) sequence and the terminator of the phosphoglycerate kinase (tPGK). Right panel: The plasmids pGAD-GH and pVP16 contain the LEU2 selective gene and the activation domain of GAL4 and VP16, respectively.

Transformation

To introduce plasmid DNA into yeast, the LiAc-mediated transformation is very easy, fast and reproducible. The method described here allows single transformation or simultanous cotransformation of two different plasmids carrying different selection genes. Our protocol can be used for up to 10 parallel transformations but can easily be scaled-up. Furthermore, with this method a cDNA library transformation can be performed; the culture or buffer volumes are indicated in brackets. It is important to mention that a positive and a negative control should be incorporated to demonstrate the efficiency of the transformation. This efficiency should be around 10 5 colonies/µg plasmid for a single transformation. 1. Inoculate 10 ml of YPD or the appropriate MM with a single colony of about 2 mm in diameter and incubate overnight at 28°C. (For the library screening, further inoculate 150 ml of the same medium with the 10 ml of the preculture and let grow overnight.) Dilute the suspension to an OD 600 of 0.2 to 0.3 and incubate the culture for approximately 3 hours to get an OD 600 around 0.5±0.1 (the log phase). 2. Centrifuge 50 ml (1000 ml) of the culture for 5 min at 1000 g. Discard the supernatant and wash the cells in 30 ml (500 ml) of sterile water. After a second centrifugation step, resuspend the cells in 1 ml (8 ml) sterile TE/LiAC. 3. Mix 0.1 mg (20 mg) herring sperm DNA with 0.1 µg of each plasmid -for simultaneous cotransformation use 0.2 µg of each different plasmid-(0,5 mg cDNA library) in a sterile 1.5 ml (500 ml) tube and add 100 µl (8 ml) of the yeast solution. Mix vigorously and add 600 µl (60 ml) PEG/LiAc. Vortex and incubate for 30 min at 30°C with shaking (200 rpm). 4. Add 70 µl (7 ml) DMSO, mix carefully by inverting the tubes and incubate for 15 min at 42°C. Centrifuge for 20 sec (5 min) at 13000 rpm and remove the supernatant. Dissolve the yeast-pellet in 500 µl (10 ml) TE and plate 100 µl (200 µl) of this suspension on a 90 mm (245*245 mm) plate which allows selection for the desired transformant(s). 5. Incubate the plate(s) at 30°C until the colonies are 1-2 mm in diameter (4-5 days).

Methionine selection

The advantage of the three-hybrid system using the Met25 inducible promoter resides in the "on" or "off" switch for the expression of the third protein (see note 4.3.). A simple replica-plating experiment allows to quickly check the interaction specificity between the various partners: 1. Select at least three different clones from the leucine and tryptophane lacking plates selective for both plasmids. Scrape the whole colony and resuspend in 100 µl of sterile H 2 O. 2. Make one to ten dilutions in sterile H 2 O up to 10 -4 . 3. Drop 10 µl of each dilutions either on selective MM plates containing or lacking 1 mM methionine. 4. Let the yeast grow 4 days at 28°C. The duration of the growth may be dependent on the proteins expressed and can take up to 10 days.

Figure 3: A. L40 yeast cells cotransformed with pLex9-3H, containing LexA-cdk7 and cyclin H under the dependence of the Met25 promoter, and with MAT1pVP16 were spotted at various dilutions, as indicated at the left of the figure, on a selective minimal medium lacking histidine. Yeast growth was performed during 4 days at 30°C, in absence (-) or presence (+) of 1 mM methionine, controlling the expression of the third partner, cyclin H. In presence of the third partner we can observe a yeast growth for the highest dilutions whereas in presence of methionine, and so in absence of the cyclin H, we can observe yeast growth only for the first dilutions. B. β-Galactosidase assay from liquid culture of pLex9-3H/cdk7/Met-cyclinH-pVP16/MAT1 cotransformed yeast was done as described in subheading 3.6.2. The β-Gal activity was measured as a function of the methionine concentration and so as a function of the presence of the third partner. The interaction, reflected by the β-Gal activity, is no more detectable in presence of 1 mM methionine. 100% corresponds to the β-Gal activity of the yeast grown on a methionine lacking medium and 0% to the activity of yeast grown on a 10 mM methionine containing medium.

An example of the methionine dependent reconstitution of the transcriptional activator is shown in figure 3A. The three proteins of the TFIIH CAK complex (constructions described in subheading 3.2.) were expressed in yeast. Cyclin H is conditionally expressed from the Met25 promoter. The complex is then formed only if the three proteins are present. Thus, the yeast are able to grow in the absence of methionine because the cyclin H is expressed and the ternary complex is reconstituted leading to the transcriptional activation of the reporter genes. The colonies that are plated on selective MM lacking 1 mM methionine grow faster than colonies plated on MM containing methionine. Thus, the methionine repression is observed for the 10 -2 to 10 -4 dilutions. Because of a weak interaction between DBD-cdk7 and AD-MAT1, a background growth can be observed for the lower dilutions. Furthermore, non-specific interactions can take place between one of the hybrid proteins and the fused DBD directly. In order to remove these background, 3-Amino-1,2,4-triazole (3AT; between 5 and 50 mM) can therefore be added to the medium. Moreover, the Met25 promoter is known to be leaky, meaning that the expression of the third partner, cyclin H, is not completely repressed, resulting in some detection of yeast growth on a methionine containing medium. As shown above, the Met25 promoter is down regulated upon addition of methionine. To determine the optimum conditions of the methionine repression, several concentrations have been tested out using the liquid β-galactosidase assay (see subheading 3.6.2) with the system containing the three proteins of the CAK complex, as described above. Thus, the resulting β-Gal activity, corresponding to the concentration of the third partner, was measured as a function of the methionine concentration. As shown in figure 3B, the β-Gal activity, reflecting the cyclin H expression, is about 30% of the activity without methionine for 0.01 mM methionine, 10% for a concentration of 0.5 mM and completely repressed for 1 mM. Actually, this system can also be useful for the control of the expression of toxic proteins, in order to decrease the amount of these proteins in the cell.

Protein extraction and immunopurification 3.5.1. Protein extraction

To investigate whether or not the hybrid-proteins are well expressed, it is necessary to prepare yeast protein extracts and to perform western-blotting assays. 1. Inoculate 50 ml of selective medium for the plasmids (described in subheading 2.1.) to OD 600 of 0.05. Grow at 28°C with shaking until an OD 600 between 0.8 and 1. Depending on the protein that is expressed, the growth can take between over-night and 3 days. 2. Transfer the culture in a 50 ml tube and cool the cells by placing the tube on ice for few minutes. Centrifuge 5 min at 3000 rpm, 4°C. 3. Resuspend the cell pellet in 1 ml cold H 2 O, transfer to a microfuge tube, centrifuge 30 sec. at maximum speed, remove the supernatant and add 300 µl of extraction buffer. Different buffers can be used for the extraction but usually a high salt buffer (300 mM KCl) is recommended for a higher recovery. To analyse the in vitrointeraction between the hybrid proteins using immunoprecipitation or immunopurification assays, the cell pellet should be resuspended at this stage in a low salt extraction buffer (100 mM KCl), in order to retain potential weak interactions. 4. Add glass beads to 1-2 mm below the surface and keep on ice for 10 minutes. 5. Vortex vigorously in cold room 3 times 1 minute with intervals of 1 minute on ice. 6. Centrifuge at maximum speed (13000 rpm) for 15 minutes at 4°C. 7. Transfer the supernatant to a microspin-column (Ultrafree-MC; Millipore) in order to filter residual big particles (see note 4.4.). Centrifuge 30 sec at maximum speed. 8. Samples can be frozen at -80°C and kept for several months. 9. Estimate the total protein concentration by performing a Bradford assay. 10. Run 10 to 100 µg of protein on a SDS-PAGE (8 to 15%) and perform a western blot.

Immunoprecipitation of HA tagged protein from yeast

The purification of a new protein, identified as an interacting partner during a cDNA library screening, is important for further analysis. It is therefore useful that the proteins expressed by the vectors containing the cDNA library are tagged. We have introduced the hemagglutinine sequence corresponding to the HA-tag (SYPYDVPDYASLGGPSS, one amino acid code), upstream of the cloning site (Fig. 2) in the methionine regulated expression cassette. Thus, the expressed protein can be immunoprecipitated or immunopurified directly from a yeast crude extract with a HA-tag specific antibody (commercially available). Instead of the HA-antibody, a specific antibody can as well be used in the following protocol.

1. Antibody crosslink to protein A-Sepharose via DMP a. Wash the protein A-Sepharose 3 times with 10 volumes of crosslink wash buffer. b. Add 0.7 volume of purified anti-HA monoclonal antibody with 4.3 volumes of crosslink wash buffer. Incubate at RT 1 h under gentle shaking. c. Wash 2 times with 10 volumes of crosslink wash buffer d. Add 10 volumes of crosslinking buffer. DMP should be added immediately before use. Incubate 30 min at RT under gentle shaking. e. Wash once with 10 volumes of Ethanolamine 0.2 M and incubate with 10 volumes of Ethanolamine 0.2 M at RT for 2h30 or at 4°C over night. f. Wash 2 times with 10 volumes of TG 10 EK 300 / 0.05% NP40. The beads are then ready to use. If you want to keep the antibody crosslinked to protein A-Sepharose for several weeks, add 1 mg/ml BSA and 0.2% Na azide. Before use, wash then 3 times with 10 volumes of TG 10 EK 300 / 0.05% NP40. 2. Immunoprecipitation of the HA tagged protein.

For a pull down assay, very little yeast extract is needed. Remember that if the strength of the interaction is not known, it is recommended to make the yeast extract at low salt concentration or to dialyse the extract against a low salt buffer. a. Incubate 300 µl of the yeast extract with 50 µl of the antibody sample crosslinked to the protein A-Sepharose for at least 4 hours at 4°C under gentle shaking. b. Wash the beads 3 times with 1 ml of TG 10 EK 100-500 (usually 300 mM KCl is preferred, once more depending on the strength of the interaction). c. Add 50 µl of Laemmli sample buffer to the beads removed of the supernatant and load (5-20 µl) on a SDS-polyacrylamide gel.

Immunopurification of the HA tagged protein.

Using the three-hybrid system, it is possible to directly purify the protein under the control of the Met25 promoter as well as the tripartite complex. The immunoprecipitation procedure can be scaled up to 2 liters of yeast culture or even more, if necessary. We describe the method for a 20 ml culture: 1. Proceed as in subheading 3.5.2. until step 2.b. After the TG 10 EK 100-500 washings, wash 2 times more with 1 ml of TG 10 EK 50 . 2. Remove the supernatant and add 50 µl of elution buffer which contains the oligopeptide corresponding to the HA, or the specific antibody epitope. Incubate at 4°C over-night with gentle shaking. 3. Centrifuge at low speed (2000 rpm) for few seconds and transfer the supernatant to a microfuge tube. Centrifuge and transfer once more to discard all the remaining beads. Most of the time the oligopeptide does not interfere with the activity of the purified protein; if necessary, dialyse against TG 10 EK 50 for 4 hours at 4°C. 4. Verify by western blot the presence of the protein in the elution fraction using the HA or the specific antibody. Compare with a yeast extract transfected with a control expression vector.

β-Gal assays

Three different β-galactosidase assays are described. The colony lift filter assay with the substrate X-Gal (5-bromo-4-chloro-3-indolyl-β-D-galactopyranoside) is a qualitative method similar to the on-plate assay. Both techniques allow the analysis of a large number of transformants appearing on the plates. However they are less sensitive than the liquid culture assay with the substrate ONPG (o-nitrophenyl-β-Dgalactopyranoside). The liquid culture assay allows the quantification of β-Gal activity. It can then be used to compare the relative strength of protein-protein interactions of different proteins or different mutations of the same protein.

The colony lift filter assay and the ONPG assay use the freeze/thaw cycle in liquid nitrogen for the lysis of the cell walls. This is a rapid step for the accurate analysis of β-galactosidase activity.

For the on-plate assay X-Gal is added directly to the selective MM leading to a slight growth restriction because of a pH shift.

Colony lift filter assay

It is recommended to use fresh colonies (1-2 mm in diameter) that are growing on the selective MM. When colonies grown in presence of methionine have to be analysed, it is necessary that these transformants have not been plated on a 3ATcontaining medium (see subheading 3.4.). 1. For every plate to be assayed presoak a sterile 3MM Whatman paper in 2.5 ml (5 ml) Z-M-X-buffer in a 90 mm (150 mm) plate. Lay, under sterile conditions, a dry nylon membrane filter on the yeast plate for few seconds to transfer the colonies onto the filter. Poke holes through the filter into the agar using hot needles in three asymmetric locations in order to orientate the filter compared to the plate for later assignments of positive clones. 2. Carefully remove the filter from the surface and lay it colony side-up on an aluminium boat, which floats on liquid nitrogen. After 10 sec, submerge the boat with the filter for 1 min and thaw it at room temperature. Place the filter colony sideup on the presoaked Whatman filter avoiding air bubbles under the filter. 3. Incubate at 30°C until blue colonies appear (from 30 min to 12 hours).

Liquid culture assay

In order to compare the results of different experiments in a statistical manner, we suggest the analysis of at least three separate colonies of each transformant. 1. Inoculate one colony in 10 ml of the appropriate MM with or without 1 mM methionine and incubate at 30°C under gentle shaking until the stationary phase (see note 4.5.). For further comparative studies it is important to have all cultures in the same growth phase. 2. Add approximately 16 ml of MM (+/-methionine) to 2 ml of each culture to achieve an OD 600 of 0.2-0.3 and incubate for 3 hours at 30°C until the OD 600 is in the range of 0.5-0.8. Note the OD 600 and the volume of the culture. 3. After centrifugation (5 min, 1000 g), the cells are resuspended in 1 ml of Z-buffer. Transfer to a 1.5 ml microfuge tube and centrifuge at high speed for 20 sec. Discard the supernatant and dissolve the pellet in 250 µl of Z-buffer. Divide the cell suspension into two 100 µl aliquots and set up a standard reaction tube with 100 µl Zbuffer. 4. Freeze the tubes 3 times for 1 min in liquid nitrogen and thaw them each time in a water bath. 5. Add to each tube 700 µl Z-M-buffer and 160 µl of freshly prepared Z-O-solution, incubate at 30°C until a yellow color develops. It is important to note the time of this reaction. 6. Stop the reaction by adding 400 µl 1 M Na 2 CO 3 solution. Centrifuge for 10 min at maximum speed to clear the supernatant and measure the OD 420 against the standard.

The linear range of this assay lays in the area from 0.02 to 1.0 for an OD 420 . Calculate the β -Gal units using the following formula: β-Gal = 1000 * OD 420 /(OD 600* V * t), V=Volume of the culture and t=reaction time. With both V and t constant you can simplify the formula to: β-Gal = 1000 * OD 420 /OD 600 Using this technique, we could demonstrate that the formation of the CAKcomplex (Fig. 4, lanes 1 and 2) is highly dependent on cyclin H. After cotransformation of the L40 strain with both pLex9-3H, containing LexA-cdk7 and Met25-cyclinH, and pVP16-MAT1, the β-Gal activity of such clones grown in a methionine-containing medium is less than 20% of the activity of colonies grown in a methionine-lacking one, due to the repression of the cyclin H. The observed basal activity could be due to e.g. the leakiness of the Met25 promoter as discussed under subheading 3.4. In control experiments, yeast cotransformed with pLex9-3H, containing LexA-cdk7 and Met25-cyclin H, and native pVP16 (lane 3 and 4) or with pLex9-3H, containing only Met25-cyclin H, and pVP16-MAT1 (lanes 5 and 6) does not present any β-Galactosidase activity.

Figure 4: Liquid culture assay. L40 cells were cotransformed with the plasmids as indicated and analysed as described in subheading 3.6.2. with V=20 ml and t=1 min. In addition, the controls with vectors without fused protein were performed (lanes 3 to 6).

On-plate assay

β-Gal activity can be directly detected on the plates if the colonies are plated or replica-plated on a selective MM containing 1x S-buffer and 50 to 250 µl X-Gal solution and incubated at 28°C. Blue color will appear with the colonies, after 4-8 days.

Inducible three-hybrid system: Three verifications for positive clones during the library screening

The three-hybrid system described here possesses an inducible promoter for the conditional expression of the third partner. This allows to perform an additional control of an interaction specificity, especially in a screening experiment for an activator. Once the positive clones are identified first by the appearance of the histidine prototrophy and second by their β-galactosidase activity (see note 4.6.), a third control can be done by transferring these positive clones onto a methionine containing medium as described under subheading 3.4. (see note 4.7.). Only the clones whose growth will be repressed by methionine will be considered as true positives. For the screening of a cDNA library to look for an inhibitor of a stable binary complex see note 4.8..

NOTES

Different systems for different tasks

It is difficult to recommand a particular yeast strain for a random system. Because of the different properties concerning the activator system (GAL4 or LexA) and the promoter strength of the HIS3 or the other reporter genes, the appropriate strain has to be tested. The choice of the plasmids is also important because there are many differences in the number of copies per cell (high or low copy number). In addition, the promoter length of the alcohol-dehydrogenase I gene (ADH1), which controls the expression of the GAL4, LexA or VP16 fusion polypeptides, is varying between most of the commonly used plasmids. This leads to a different expression level of the fused proteins [START_REF] Legrain | Detection of protein-protein interactions using different vectors in the two-hybrid system[END_REF]. There are also other vectors expressing the protein of interest fused to the N-terminus of LexA (11).

Generation of the Met25-expression vectors

The Met25-expression cassette, which contains the region from -474 to -1 of the Met25 promoter (3, 12),, the hemagglutinine epitope (HA), the nuclear localisation sequence and two rare restriction sites (NotI and SrfI for pLexA; NotI and BglII for pBridge) was cloned in the unique PvuII site of the plasmid vectors pBTM116 and pGBT9 to give the plasmids pLexA and pBridge, respectively. The transcription arrest signal is provided by addition of the phosphoglycerate kinase termination region corresponding to the BglII-HindIII terminator fragment from plasmid pEMBLYe30/2 (Fig. 2, left panel) [START_REF] Tirode | A conditionally expressed third partner stabilizes or prevents the formation of a transcriptional activator in a three-hybrid system[END_REF]..

It should be taken in account that the Met25 promoter is a strong promoter in the absence of methionine, compared to the ADH1 promoter. Therefore, the third polypeptide is much more expressed than the two other fused proteins.

Methionine and other inducible promoters are possible

There are several other three-hybrid systems using various inducible promoters : -Galactokinase/galactose epimerase promoter (GAL1/GAL10), which is repressed by glucose and induced by galactose [START_REF] Johnston | A model fungal gene regulatory mechanism: the GAL genes of Saccharomyces cerevisiae[END_REF][START_REF] Mylin | Inducible expression cassettes in yeast: GAL4[END_REF]. This promoter cannot be used in a GAL4 based two-hybrid system because the GAL4 activator binds the sequence between GAL1 and GAL10 and induces transcription.

-Acid Phosphatase promoter (PHO5), regulated by the presence or absence of inorganic phosphate (15).

-Metallothionein protein promoter (CUP1), induced by addition of copper to the medium (16, 17).

Some other promoters can be used for the regulated expression of the third partner in a three-hybrid system:

-Sorbitol dehydrogenase protein (SOR1), an enzyme responsible for sugar metabolism, is up regulated in presence of sorbitol. McGonigal et al. described some inducible protein expression vectors that can be used in a two or three-hybrid system (18).

-Aromatic aminotransferase II (ARO9) that catalyses the first step of tryptophan, phenylalanine and tyrosine catabolism in S. cerevisiae is upregulated by those aminoacids (19).

Advantage of Microspin-columns

Sometimes yeast extract immunoblot could be "smear-like" independently of the antibodies used. For optimum detection we found that filtering the yeast extract on a 0.45 µm spin column can efficiently overcome this problem. Several techniques can be used such as affinity chromatography; however the advantages of the filter method reside mainly in the low cost and in time saving.

β-Galactosidase assay in function of the culture volume

To analyse the strength of an interaction or the amount of hybrid proteins in the liquid ONPG-assay, it can be useful to test different volumes of yeast culture. We have noticed that, using low culture volume, the β-galactosidase activity measured was not in the linear range (OD 600 between 0.02 to 1.0). Thus, further analyses should be done under the conditions found to be the most suitable. It has to be noticed that in the liquid ONPG-assay, weak (or background) interactions yield no yellow colour. The reaction can then be stopped if no yellow color has appeared after 30 min. 4.6. β-Galactosidase assays in cDNA library screening During the selection of positive clones by performing the on-plate and the colony lift filter assays in a yeast three-hybrid screening, only strong interactions are identified using the Y190 and L40 strains. Thus, the liquid culture assay is more sensitive for the identification of the weakest interactions in these strains.

One more hybrid -one more control

The two-hybrid system is used for detection of interaction between two proteins. Many interactions could not be detected because of the lack of specificity or because the right positioning of the interacting domains was not achieved. The three-hybrid system can overcome these problems by increasing the specificity of an interaction.

Thus, the presence of the third polypeptide is necessary to detect ternary complexes. One can imagine that a four-hybrid system can be used to detect quaternary complexes. Since many complexes involved in the different cellular processes contain more than three proteins, adding one more polypeptide to the bait means an increased specificity.

cDNA library screening for an inhibitor

To screen a cDNA library to search for a binary complex inhibitor, the methionine regulated system presented here is not appropriate. In presence of methionine, the repression of the inhibitor will lead to the formation of the transcriptional activator complex. Since each clone will express the reporter genes and will then be able to grow, replica-plating of all the corresponding colonies (approximately 2x10 6 ) will not be very practical. Therefore, a reverse three-hybrid system can be adapted from the system presented here (see chapter 24). But once a candidate is identified as an inhibitor, our system can be used to rapidly verify the inhibitory properties of the new protein.

Figure 2 :

 2 Figure 2: The three-hybrid vectors: Left panel: pBridge, derived from the pGBT9 vector, contains the TRP1 selective gene, the DNAbinding domain of GAL4 and the Met25 expression cassette (see note 4.2.) with the NotI and BglII cloning sites. pLex9-3H, derived from the pBTM116 vector, contains the TRP1 selective gene, the DNA-binding domain of LexA and the Met25 expression cassette with the NotI and SrfI cloning sites. The Met25 cassette contains a hemagglutinine (HA) tag sequence, a nuclear localisation signal (NLS) sequence and the terminator of the phosphoglycerate kinase (tPGK). Right panel: The plasmids pGAD-GH and pVP16 contain the LEU2 selective gene and the activation domain of GAL4 and VP16, respectively.

  i o n i n e + M e t h i o n i n e

2.4 Protein extraction and immunopurification 2.4.1. Protein extraction

  3. 90 mm (Greiner) and 245*245 mm (PolyLabo) culture plates.

	2.2. Transformation 1. Stock solutions: 50% PolyEthylenGlycol 4000 (MERCK; sterile filtrated); 100%
	Dimethyl sulfoxyde (DMSO; MERCK); 10x LiAc: 1 M Lithium acetate (Sigma), pH 7.5
	(autoclave); 10x TE buffer: 0.1 M Tris-HCl, 10 mM EDTA, pH 7.5 (autoclave); 10 mg/ml Herring testis carrier DNA (Sigma; boil just prior use for 5 min, then cool on ice).
	2. TE/LiAc: 1x TE, 1x LiAc. 3. PEG/LiAc: 40% PEG, 1x TE, 1x LiAc. 4. Appropriate minimal medium containing plate.
	2.3. Methionine selection 1. Yeast minimal medium as described in subheading 2.1. 2. Methionine stock: We prepare a 0.2 µm filtered 1 M L-methionine (Sigma) in
	deionized H 2 O. This solution can be frozen to -20°C and kept for years. Minimal medium is supplemented with 1 mM L-methionine. 3. 3-Amino-1,2,4-triazole (3AT; Sigma).
	1. Extraction buffer: 50 mM Tris-HCl pH 7.8, 10% Glycerol, 0.1 mM EDTA, 100-300 mM KCl, 1 mM PhenylMethylSulfonylFluoride (PMSF; Sigma) and 1x protease inhibitor cocktail (Roche Diagnostics; contains Leupeptine, Pepstatin, Aproptinin, Antipain and Chimostatin).
	2. Acid treated glass beads (Sigma). 3. A 0.45 µm microspin-column (Ultrafree-MC; Millipore) is used to remove the biggest particles. 2

.4.2. Immunopurification 1. Antibodies are crosslinked to protein

	A-Sepharose CL-4B (AP Biotech). 2. Stock solutions: 5 M NaCl; 1M Sodium Borate pH 9; 0.2 M Ethanolamine pH 8; 10 mg/ml BSA. 3. Sodium Azide (Sigma), Dimethyl Pimelidate (DMP; ICN Pharmaceuticals). 4. Buffers: TG 10 EK X : 20 mM Tris-HCl pH 7.8, 10% Glycerol, 0.1 mM EDTA,
	X mM KCl. Crosslink wash buffer: 3 M NaCl , 50 mM Na Borate pH 9. Crosslinking buffer: 3 M NaCl, 200 mM Na Borate pH 9, 20 mM DMP. Elution buffer: TG 10 EK 5 0 ; 0.01% NP40; 0.2 mg/ml insuline; 2 mg/ml peptide
	corresponding to the epitope.
	2.5. β-Gal assays Stock solution: Z-buffer: 21.5 g/l Na 2 HPO 4 •12 H 2 O; 5.5 g/l NaH 2 PO 4 •H 2 O; 0.75 g/l
	KCl; 0.246 g/l MgSO 4 •7 H 2 O; adjust to pH 7.0 and autoclave.


Olivier Ferret
email: ferret@limsi.fr

Brigitte Grau

Martine Hurault-Plantet

Gabriel Illouz
email: gabrieli@limsi.fr

Christian Jacquemin
email: jacquemin@limsi.fr

Document selection refinement based on linguistic features for QALC, a Question Answering system

Answering to precise questions requires applying Natural Language techniques in order to locate the answers inside retrieved documents. The QALC system, presented in this paper, participated t o the Question Answering track of the TREC8 and TREC9 evaluations. QALC exploits an analysis of documents based on the search for multi-word terms and their variations. These indexes are used to select a minimal number of documents to be processed. This selection is fully significant when applying further time consuming modules.

INTRODUCTION

A question answering system has to find a precise answer in response to a natural language question. Question answering (QA) issue was introduced at the end of the seventies by [START_REF] Lehnert | Human and computational question answering[END_REF]. She mainly focused on question taxonomy providing question type classes that still now inspire many question answering systems. Her QUALM system used complex semantic information but retrieved answers in a small size corpus. With the expansion of Internet, the QA issue gained a fresh interest both from Information Retrieval (IR) and Natural Language Processing (NLP) communities. But the retrieval documents corpora thereby become very large. For instance, the natural language question answering system START [START_REF] Katz | From Sentence Processing t o Information Access on the World Wide Web[END_REF] is connected to the World Wide Web since 1993. Questions are requests for information from STARTÕs knowledge base. Indeed, START attempt to solve the problem of retrieving information in a large and unstructured collection of documents by annotating documents. So, STARTÕs knowledge base is made of natural language descriptive information attached to the documents available through the Web. As a token of interest in this issue, the TREC (Text REtrieval Conference) evaluation conference added two years ago the Question Answering track to the other IR tasks yet existing. Participants to TREC are provided with a very large corpus of documents (about 3 gigabytes) from which they have to extract answers in response to a list of questions. Answering precise questions requires applying NLP techniques in order to locate the answers inside the documents of the corpus. As such techniques are time consuming, the size of the corpus to process is of great importance. To solve this problem, all systems presented at TREC used a search engine in order to select firstly a subset of relevant documents from the corpus, and then to apply NLP techniques on this subset. Most of the systems processed document selection either by getting few of the best ranked documents retrieved by the search engine [START_REF] Litkowski | Syntactic Clues and Lexical Resources in Question-Answering[END_REF][START_REF] Vicedo | A semantic approach to Question Answering systems[END_REF], or by selecting relevant paragraphs within a larger amount of the best ranked documents (HarabagiuÊetÊal. 2000[START_REF] Kwok | TREC-9 Cross Language, Web and Question-Answering Track Experiments using PIRCS[END_REF]. The first solution generally leads to lower results when selecting too few documents because many documents containing the correct answer are then eliminated. The solution that we used in QALC, our question answering system, consists in using a NLP based re-indexing of the best ranked documents retrieved by the search engine and a subsequent reranking of the documents. The new index is made of the multi-word terms extracted from the question and their morphological and syntactic variants retrieved in the documents. The ranking of the documents relies on a weighted combination of the terms and their variants indexing the document. This technique appears t o rank better most of the relevant documents and subsequently allows the selection of few documents to process by NLP techniques. In this paper, we will present the QALC system that was developed for the QA track at TREC8 and TREC9. In the next section we describe the architecture of the QALC system. Then we present the NLP based document selection process, and the experimentations that we made on the TREC corpus concerning the document selection. Finally, we discuss the results obtained by the QALC system and a number of related works.

OVERVIEW OF THE QALC SYSTEM

Natural Language Processing components in the QALC system (see Figure 1) enrich the selected documents with terminological indexes in order t o go beyond reasoning about single words. Rich linguistic features are also used to deduce what is a question about.

The analysis of a question relies on a shallow parser which spots discriminating patterns and assigns categories to a question. The categories correspond to the types of entities that are likely to constitute the answer to this question. The QALC system In order to select the best documents from the results given by the search engine and to locate the answers inside them, we work with terms and their variants, i.e. morphologic, syntactic and semantic equivalent expressions. A term extractor has been developed, based on syntactic patterns which describe complex nominal phrases and their subparts. These terms are used by FASTR (Jacquemin, 1999), a shallow transformational natural language analyzer that recognizes their occurrences and their variants. Each occurrence or variant constitutes an index that is used in the process of document ranking and questionsentence pairing. Documents are ordered according to the number and the quality of the terms they contain. For example, original terms with proper names are considered more reliable than semantic variants. An analysis of the weight graph enables the system to select a relevant subpart of the documents, whose size varies along the questions. This second selection takes all its importance when applying the last processes which consist of recognizing named-entities and analyzing each sentence to decide whether it is a possible answer or not. Such processes are time consuming, and we limit their application to a minimal number of documents. Thus, when the curve presents a high negative slope, we only select documents before the fall, otherwise a fixed threshold is used.

Named entities are recognized in the documents and used to measure the similarity between the document sentences and a question. Named entities receive one of the following types: person, organization, location (city or place), number (a time expression or a number expression). They are defined in a way similar t o the MUC task and recognized through a combination of lexico-syntactic patterns and significantly large lexical data. The three lists used for lexical lookup are CELEX (1998), a lexicon of 160,595 inflected words with associated lemma and syntactic category, a list of 8,070 first names (6,763 of which are from the CLR (1998) archive) and a list of 211,587 family names also from the CLR archive.

Finally, a pairing module uses all the data extracted from the questions and the documents by the preceding modules. We developed a similarity measure that attributes weights to each characteristic and makes a combination of them. The QALC system proposes large and short answers. Concerning the short ones, the system focuses on parts of sentences that contain the expected named entity tags, when they are known, or on the larger subpart without any terms. For a description of the whole system, see [START_REF] Ferret | QALC Ñ the Question-Answering system of LIMSI-CNRS[END_REF].

DOCUMENTS SUBSET SELECTION

The selection of relevant documents relies on an NLP-based indexing composed of both singleword and phrase indices and linguistic links between the occurrences in the document and the original terms. The original terms are extracted from the questions. The tool used for extracting text sequences that correspond to occurrences or variants of these terms is FASTR (Jacquemin, 1999). The ranking of the documents relies on a weighted combination of the terms and variants extracted from the documents.

Term Extraction

For automatic acquisition of terms from questions, we use a simple technique of filtering through patterns of part-of-speech categories. No statistical ranking is possible because of the small size of the questions from which terms are extracted. First, questions are tagged with the help of the TreeTagger [START_REF] Schmid | Improvements in Part-of-Speech Tagging with an Application To German[END_REF]. Patterns of syntactic categories are then used to extract terms from the tagged corpora. They are very close t o those described by [START_REF] Justeson | Technical terminology: some linguistic properties and an algorithm for identification in text[END_REF], but we do not include post-posed prepositional phrases. The pattern used for extracting terms is:1

(((((JJ|NN|NP|VBG))?(JJ|NN|NP|VBG)(NP|NN)))| (VBD)|(NN)|(NP)|(CD))
The longest string is acquired first and substrings can only be acquired if they do not begin at the same word as the superstring.

NLP-based Indexing through FASTR

The automatic indexing of documents is performed by FASTR (Jacquemin, 1999), a transformational shallow parser for the recognition of term occurrences and variants. Terms are those extracted from the questions, plus the other single content words of the questions. They are transformed into grammar rules and the single words building these terms are extracted and linked to their morphological and semantic families.

The morphological family of a single word w is the set M(w) of terms in the CELEX database (CELEX, 1998) which have the same root morpheme as w. For instance, the morphological family of the noun maker is made of the nouns maker, make and remake, and the verbs to make and to remake.

The semantic family of a single word w is the union S(w) of the synsets of WordNet1.6 [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF] to which w belongs. A synset is a set of words that are synonymous for at least one of their meanings. Thus, the semantic family of a word w is the set of the words w' such that w' is considered as a synonym of one of the meanings of w. The semantic family of maker, obtained from WordNet1.6, is composed of three nouns: maker, manufacturer, shaper and the semantic family of car is car, auto, automobile, machine, motorcar.

Variant patterns that rely on morphological and semantic families are generated through metarules. They are used to extract terms and variants from the document sentences in the TREC corpus.

The following pattern2 extracts the occurrence making many automobiles as a variant of the term car maker: VM('maker') RP? PREP? (ART (NN|NP)? PREP)?

ART? (JJÊ|ÊNNÊ|ÊNP |ÊVBDÊ|ÊVBG) 0-3 NS('car')

VM('maker') is any verb in the morphological family of the noun maker and NS('car') is any noun in the semantic family of car.

Relying on the above morphological and semantic families, auto maker, auto parts maker, car manufacturer, make autos, and making many automobiles are extracted as correct variants of the original term car maker through the metarule set used for the QA-track experiment.

Unfortunately, some incorrect variants are extracted as well, such as make those cuts in auto produced by the preceding metarule.

Document Ranking

The output of NLP-based indexing is a list of term occurrences composed of a document identifier d, a term identifierÑa pair t(q,i) composed of a question number q and a unique index iÑ, a text sequence, and a variation identifier v (a metarule). For instance, the following index:

LA092690-0038 t(131,1) making many automobiles NtoVSemArg means that the occurrence making many automobiles from document d=LA092690-0038 is obtained as a variant of term i=1 in question q=131 (car maker) through the variation given in Section 5.1. Each document d selected for a question q is associated with a weight W q (d) given by formula (1). The weighting scheme relies on a measure of quality of the different families of variations described by JacqueminÊ(1999): non-variant occurrences are weighted 3.0, morphological and morpho-syntactic variants are weighted 2.0, and semantic and morpho-syntactico-semantic variants are weighted 1.0.

Since proper names are more reliable indices than common names, each term t(q,i) receives a weight P(t(q,i)) between 0 and 1.0 corresponding to its proportion of proper names. For instance, President Cleveland's wife is weighted 2/3=0.66. Since another factor of reliability is the length of terms, a factor |t(q,i)| in the weighting formula denotes the number of words in term t(q,i).

The weight W q (d) of a document d for a query q is given by the following formula (1). The products of the weightings of each term extracted by the indexer are summed over the indices I(d) extracted from document d and normalized according to the number of terms |T(q)| in query q.

W (d) ( ) ( ( ( , ))) ( , ) ( ) q ( ( , ), ) ( ) = × + × ∈ ∑ w v P t q i t q i T q t q i v I d 1 2
(1)

For each query q, the 100 best ranked documents are retrieved. Mainly two types of weighting curves are observed for the retrieved documents: curves with a plateau and a sharp slope at a given threshold (Figure 2.a) and curves with a slightly decreasing weight (Figure 2.b).

The edge of a plateau is detected by examining simultaneously the relative decrease of the slope with respect to the preceding one, and the relative decrease of the value with respect to the preceding one. The following algorithm is used for calculating the cutoff threshold i 0 associated with the weighting scheme W of a given query q:

If W (d ) W (d ) 0.5 then i = 2 else i = min i 3 100 0.8 100 q 2 q 1 0 0 ≤ ∈ … { } - -       ≥ ∧ ≤               ∪ { } - - - - . ( ) ( ) ( ) ( ) ( ) ( ) W d W d W d W d W d W d q i q i q i q i q i q i 1 1 2 1 2
(2)

Through this method, the threshold i 0 is 6 for question 854 (How do you abbreviate "Original Equipment Manufacturer"?, Finally, the system retains the i 0 best ranked documents with a minimum number set to 20.

EXPERIMENTS

One module of the QALC system is the selection, through a search engine, of documents that may contain an answer to a given question from the whole collection made of about 3 gigabytes.

Search Engine Evaluation

We tested three search engines with the 200 questions that were proposed at the TREC8 QA task. The first one is Zprise, a vectorial search engine developed by NIST. The second is Indexal (de [START_REF] Loupy | Query Expansion and Classification of Retrieved Documents[END_REF], a pseudo-boolean search engine developed by Bertin Technologies 3 . The third search engine is ATT whose results to the TREC questions are provided by NIST in the form of ranked lists of documents. We based our search engine tests on the list of relevant documents extracted from the list of correct answers provided by TREC organizers.

We compared the results given by the three search engines for a threshold of 200 documents. Table 1 gives the tests results. The ATT search engine revealed itself the most efficient according to the following two criteria: the lowest number of questions for which no relevant document was retrieved, and the most relevant documents retrieved for all the 200 questions. We thus chose two different search engines for the TREC9 QA task. The first one is ATT, for the obvious reason that it provides the best results. The other is Indexal as Bertin Technologies is in the process of improving its system.

Since a search engine produces a ranked list of relevant documents, we had to define on the number of documents to retain for further processing. Indeed, having too many documents leads to a question processing time that is too long, but conversely, having too few documents reduces the possibility of obtaining the correct answer.

Document Selection Threshold

We carried out four different tests with the Zprise search engine, respectively with the top 50, 100, 200, and 500 retrieved documents. Table 2 shows the test results.

According to Table 2, the improvement of the search engine results tends to decrease beyond the threshold of 200 documents. For the TREC9 QA task, we then chose the threshold of the top 200 ranked documents that seemed to offer the best arrangement between the number of documents in which the answer may be found and the processing time by FASTR. This first subset of documents, ordered by the search engine, is then re-indexed and re-ranked in order to retain only a minimal number of documents.

Document Ranking Evaluation

In order to evaluate the efficiency of the ranking process, we proceeded to several measures. First, we apply our system on the material given for the TREC8 evaluation, one time with the ranking process, and another time without this process. Thus the 200 documents were retained for each of the 200 questions. The system was scored by 0.463 in the first case, and by 0.452 in the second case. These results show that the results do not decreased when processing less documents and overall that the relevant documents are selected in the minimal subset. The interest to perform such a selection is also illustrated by the results given Table 3, computed on the TREC9 results. We see that the selection process discards documents for 50% of the questions (340 questions are processed from less than 100 documents). QALC finds more often the correct answer and in a better position for these 340 questions than for the 342 remaining ones. The average number of documents selected when there is less than 100 documents is 37. These results are very interesting when applying such timeconsuming processes as named-entities recognition and question/sentence pairing. The efficiency of our ranking process is also illustrated by Figure 3. It shows that the documents containing the right answer are better ranked by our process than by the ATT search engine. The graph shows the number of relevant document, represented by their mean over the 682 questions of TREC9, among different documents subset sizes.

RESULTS AND DISCUSSION

Participants to TREC evaluation proposed up t o 5 ordered answers to about 700 questions. The size of the answer should be either 250 or 50 bytes maximum. The score of a run is the mean reciprocal rank of the correct answers (0 otherwise) over the 682 questions.

We sent to TREC9 two runs which gave answers of 250 characters length. The first run used A T T as search engine, and for the second one, Indexal.

Results are consistent with our previous analysis (see Section 4.1). Indeed, the run with A T T search engine gives slightly better results (0.407 strict) 4 than those obtained with the Indexal search engine (0.375 strict). Table 4 sums up the number of answers found by our two runs. In addition to the benefit for each participant from getting an evaluation of his/her own question-answering system, the TREC evaluation conference provides an interesting 4 With this score, the QALC system was ranked sixth at TREC9 QA task.

experimentation field for comparing the efficiency of the methods used by various QA systems. Even if the basic components of QA systems are about the same, methods used are rather different.

All systems that participated in TREC9 have a search engine component that firstly selects a subset of the provided database of about one million documents. Some of them just get the ranked list of documents retrieved by ATT, while others used their own search engine or an available search engine that they can adapt.

For instance, [START_REF] Vicedo | A semantic approach to Question Answering systems[END_REF] KwokÊetÊal (2000), for instance, have an IR engine, namely PIRCS, that retrieves the top 300 sub-documents of about 300-550 words. Their best score is 0.464 for answers of 250 characters length. Harabagiu et alÊ(2000) uses a boolean search engine whose results are post-processed in order to retrieve only text paragraphs defined by the presence of the question words within a window of about ten lines. Their system, namely FALCON, uses a semantic approach to perform the matching between the question and the answer. After the paragraph selection stage, a unification is searched between the semantic representation of the question and that of selected paragraphs. Furthermore, FALCON is the only system that adds a logical justification for the correctness of the answer. Their system was ranked first with a score of 0.760 for answers of 250 characters length.

CONCLUSION

It is well known that QA systems have to use NLP techniques that add semantic and pragmatic knowledge to numerical IR methods, thus leading to more efficient systems. As such techniques are time consuming, the corpus where the answer is seeked should not be too large. In this paper, we presented a NLP-based document selection process as well as the experiments that show its efficiency. This selection is processed on the documents retrieved by a conventional search engine. We prefered this solution to the one consisting of adapting a search engine t o paragraph selection because it is independent of the search engine that is used. As such, our document selection process can easily be used after any search engine and thus could be used for instance when searching an answer on the Web. Furthermore, this document selection is the more important as the improvements that we want t o bring to our system will essentially pertain to a semantic and pragmatic approach: a better use of the specific relations between words in WordNet, the introduction of a semantic representation of the expected answer type, and finally a justification for the correctness of the answer.

Figure 1 :

 1 Figure 1: The QALC systemIn order to select the best documents from the results given by the search engine and to locate the answers inside them, we work with terms and their variants, i.e. morphologic, syntactic and semantic equivalent expressions. A term extractor has been developed, based on syntactic patterns which describe complex nominal phrases and their subparts. These terms are used by FASTR(Jacquemin, 1999), a shallow transformational natural language analyzer that recognizes their

Figure 2 .

 2 Figure 2. Two types of weighting curve.Each document d selected for a question q is associated with a weight W q (d) given by formula (1). The weighting scheme relies on a measure of quality of the different families of variations described by JacqueminÊ(1999): non-variant occurrences are weighted 3.0, morphological and morpho-syntactic variants are weighted 2.0, and semantic and morpho-syntactico-semantic variants are weighted 1.0.

  Figure 2.a) and 100 for question 842 (At what time of year is air travel at a peak?, Figure 2.b). As indicated by Figure 2.a, there is an important difference of weight between documents 6 and 7. The first documents have high weights due to the presence of the term Original Equipment Manufacturer, while documents after the sixth only contain few of the question words.

Figure 3 .

 3 Figure 3. Mean number of relevant documentsfor different amounts of selected documents.

Table 1 . Compared performances of the Indexal, Zprise and ATT search engines

 1

	Search Engine	Indexal Zprise ATT
	Number of questions
	with relevant documents	182	193	194
	retrieved
	Number of questions
	without relevant	18	7	6
	documents retrieved
	Total number of relevant
	documents that were	814	931	1021
	retrieved

Table 2 . Number of questions with and without relevant documents retrieved for different thresholds Selection Threshold Questions with relevant documents Questions with no relevant documents

 2

	50	181	19
	100	184	16
	200	193	7
	500	194	6

Table 3 . Evaluation of the ranking process Number of documents selected by

 3

	ranking	100	<<100
	Distribution among the	342 (50%) 340 (50%)
	questions
	Number of correct answers	175 (51%) 200 (59%)
	Number of correct answer at	88 (50%) 128 (64%)
	rank 1

Table 4 . Number of correct answers retrieved, by rank, for the two runs at 250 characters Rank of the correct answer retrieved Run using ATT

 4

			Run using
			Indexal
	1	216	187
	2 to 5	159	185
	Total of correct answers retrieved	375	372
	No correct answer retrieved	307	310

NN are common nouns, NP proper nouns, JJ adjectives, VBG gerunds, VBD past participles and CD numeral determiners.

RP are particles, PREP prepositions, ART articles, and V verbs.

We are grateful to Bertin Technologies for providing u s with the outputs of Indexal on the TREC collection for the TREC9-QA question set.


Olivier Ferret
email: ferret@limsi.fr

Brigitte Grau
email: grau@limsi.fr

Martine Hurault-Plantet

Gabriel Illouz
email: gabrieli@limsi.fr

Christian Jacquemin
email: jacquemin@limsi.fr

Terminological variants for document selection and question/answer matching

Answering precise questions requires applying Natural Language techniques in order to locate the answers inside retrieved documents. The QALC system, presented in this paper, participated to the Question Answering track of the TREC8 and TREC9 evaluations. QALC exploits an analysis of documents based on the search for multi-word terms and their variations. These indexes are used to select a minimal number of documents to be processed and to give indices when comparing question and sentence representations. This comparison also takes advantage of a question analysis module and recognition of numeric and named entities in the documents.

Introduction

The Question Answering (QA) track at TREC8 and TREC9 is due to the recent need for more sophisticated paradigms in Information Retrieval (IR). Question answering generally refers to encyclopedic or factual questions that require concise answers. But current IR techniques do not yet enable a system to give precise answers to precise questions. Question answering is thus an area of IR that calls for Natural Language Processing (NLP) techniques that can provide rich linguistic features as output. Such NLP modules should be deeply integrated in search and matching components so that answer selection can be performed on such linguistic features and take advantage of them. In addition, IR and NLP techniques have to collaborate in the resulting system in order to cope with large-scale and broad coverage text databases while deriving benefit from added knowledge.

We developed a system for question answering, QALC, evaluated in the framework of the QA tracks at TREC8 and TREC9. The QALC system comprises NLP modules for multi-word term and named entity extraction with a specific concern for term conflation through variant recognition. Since named entity recognition has already been described extensively in other publications [START_REF] Baluja | Applying machine learning for high performance named-entity extraction[END_REF], we present the contribution of terminological variants to adding knowledge to our system.

The two main activities involving terminology in NLP are term acquisition and term recognition. Basically, terms can be viewed as a particular type of lexical data. Term variation may involve structural, morphological, and semantic transformations of single or multiwords terms [START_REF] Fabre | Boosting variant recognition with light semantics[END_REF].

In this paper, we describe how QALC uses high level indexes, made of terms and variants, to select among documents the most relevant ones with regard to a question, and then to match candidate answers with this question. In the selection process, the documents first retrieved by a search engine, are then postfiltered and ranked through a weighting scheme based on high level indexes, in order to retain the top ranked ones. Similarly, all systems that participated in TREC9 have a search engine component that firstly selects a subset of the provided database of about one million documents. Since a search engine produces a ranked list of relevant documents, systems then have to define the highest number of documents to retain. Indeed, having too many documents leads to a question processing time that is too long, but conversely, having too few documents reduces the possibility of obtaining the correct answer. For reducing the amount of text to process, one approach consists of keeping one or more relevant text paragraphs from each document retrieved. [START_REF] Kwok | TREC9 Cross Language, Web and Question-Answering Track experiments using PIRCS[END_REF], for instance use an IR engine that retrieves the top 300 sub-documents of about 300-550 words and, on the other hand, the FALCON system (Harabagiu et all 2000) performs a paragraph retrieval stage after the application of a boolean retrieval engine. These systems work on the whole database and apply a bag-of-words technique to select passages whereas QALC first retains a large subset of documents, among which it then selects relevant documents by applying richer criteria based on the use of the linguistic structures of the words.

QALC indexes, used for document selection, are made of single and multi-word terms retrieved by a 2-step procedure: (1)Êautomatic term extraction from questions through part-ofspeech tagging and pattern matching and (2)Êautomatic document indexing through term recognition and variant conflation. As a result, linguistic variation is explicitly addressed through the exploitation of word paradigms, contrarily to other approaches like the one taken in COPSY [START_REF] Schwarz | The TINA Project: text content analysis at the Corporate Research Laboratories at Siemens[END_REF] where an approximate matching technique between the query and the documents implicitly takes it into account. Finally, terms acquired at stepÊ(1) and indexes from stepÊ(2) are also used by the matching procedure between a question and the relevant document sentences.

In the next section, we describe the architecture of the QALC system. Then, we present the question processing for term extraction. We continue with the description of FASTR, a transformational shallow parser that recognizes and marks the extracted terms as well as their linguistic variants within the documents. The two following sections present the modules of the QALC system where terms and variants are used, namely the document selection and question/answer matching modules. Finally, we present the results obtained by the QALC system as well as an evaluation of the contribution of this NLP technique to the QA task through the use of the reference collections for the QA track. In conclusion, suggestions for more ambitious, but still realistic, developments using NLP are outlined.

System Overview

Natural Language Processing components in the QALC system (see Figure 1) enrich the selected documents with terminological indexes in order to go beyond reasoning about single words. Rich linguistic features are also used to deduce what a question is about. The analysis of a question relies on a shallow parser which spots discriminating patterns and assigns categories to the question. The categories correspond to the types of entities that are likely to constitute the answer to the question.

In order to select the best documents from the results given by the search engine and to locate the answers inside them, we work with terms and their variants, i.e. morphologic, syntactic and semantic equivalent expressions. A term extractor has been developed, based on syntactic patterns which describe complex nominal phrases and their subparts. These terms are used by FASTR [START_REF] Jacquemin | Syntagmatic and paradigmatic representations of term variation[END_REF], a shallow transformational natural language analyzer that recognizes their occurrences and their variants. Each occurrence or variant constitutes an index that is subsequently used in the processes of document ranking and question/document matching.

Documents are ordered according to a weight computed thanks to the number and the quality of the terms and variants they contain. For example, original terms with proper names are considered more reliable than semantic variants. An analysis of the weight graph enables the system to select a relevant subpart of the documents, whose size varies along the questions. This selection takes all its importance when applying the last processes which consist of recognizing named-entities and analyzing each sentence to decide whether it is a possible answer or not. As such processes are time consuming we attempt to limit their application to a minimal number of documents.

Named entities are recognized in the documents and used to measure the similarity between the document sentences and a question. Named entities receive one of the following types: person, organization, location (city or place), number (a time expression or a number expression). They are defined in a way similar to the MUC task and recognized through a combination of lexico-syntactic patterns and significantly large lexical data.

Finally, the question/answer matching module uses all the data extracted from the questions and the documents by the preceding modules. We developed a similarity measure that attributes weights to each characteristic, i.e. named entity tags and terms and variants, and makes a combination of them. The QALC system proposes long and short answers. Concerning the short ones, the system focuses on parts of sentences that contain the expected named entity tags, when they are known, or on the largest subpart without any terms of the question.

Terms and Variants

Term extraction

For automatic acquisition of terms from questions, we use a simple technique of filtering through patterns of part-of-speech categories. No statistical ranking is possible because of the small size of the questions from which terms are extracted. First, questions are tagged with the help of the TreeTagger [START_REF] Schmid | Improvments in Part-of-Speech Tagging with an Application To German[END_REF]. Patterns of syntactic categories are then used to extract terms from the tagged questions. They are very close to those described by Justeson and KatzÊ(1995), but we do not include post-posed prepositional phrases. The pattern used for extracting terms is:

(((((JJ | NN | NP | VBG)) ? (JJ | NN | NP | VBG) (NP | NN))) | (VBD) | (NN) | (NP) | (CD))
where NN are common nouns, NP proper nouns, JJ adjectives, VBG gerunds, VBD past participles and CD numeral determiners.

The longest string is acquired first and substrings can only be acquired if they do not begin at the same word as the superstring. For instance, from the sequence name NN of IN the DT US NP helicopter NN pilot NN shot VBD down RP , the following four terms are acquired: U S helicopter pilot, helicopter pilot, pilot, and shoot.

The mode of acquisition chosen for terms amounts to considering only the substructures that correspond to an attachment of modifiers to the leftmost constituents (the closest one). For instance, the decomposition of US helicopter pilot into helicopter pilot and pilot is equivalent to extracting the subconstituents of the structure [US [helicopter [pilot]]].

Variant recognition through FASTR

The automatic indexing of documents is performed by FASTR [START_REF] Jacquemin | Syntagmatic and paradigmatic representations of term variation[END_REF]), a transformational shallow parser for the recognition of term occurrences and variants. Terms are transformed into grammar rules and the single words building these terms are extracted and linked to their morphological and semantic families.

The morphological family of a single word w is the set M(w) of terms in the CELEX database (CELEX 1998) which have the same root morpheme as w. For instance, the morphological family of the noun maker is made of the nouns maker, make and remake, and the verbs to make and to remake.

The semantic family of a single word w is the union S (w ) of the synsets of WordNet1.6 [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF] to which w belongs. A synset is a set of words that are synonymous for at least one of their meanings. Thus, the semantic family of a word w is the set of the words w' such that w' is considered as a synonym of one of the meanings of w. The semantic family of maker, obtained from WordNet1.6, is composed of three nouns: maker, manufacturer, shaper and the semantic family of c a r is car, auto, automobile, machine, motorcar.

Variant patterns that rely on morphological and semantic families are generated through metarules. They are used to extract terms and variants from the document sentences in the TREC corpus. For instance, the following pattern, named NtoSemArg, extracts the occurrence making many automobiles as a variant of the term car maker: VM('maker') RP? PREP? (ART (NN|NP)? PREP)?

ART? (JJÊ|ÊNNÊ|ÊNP |ÊVBDÊ|ÊVBG) [0-3] NS('car')

where RP are particles, PREP prepositions, ART articles, and VBD, VBG verbs. VM('maker') is any verb in the morphological family of the noun maker and NS('car') is any noun in the semantic family of car.

Relying on the above morphological and semantic families, auto maker, auto parts maker, car manufacturer, make autos, and making many automobiles are extracted as correct variants of the original term car maker through the set of metarules used for the QA track experiment. Unfortunately, some incorrect variants are extracted as well, such as make those cuts in auto produced by the preceding metarule.

Document selection

The output of NLP-based indexing is a list of term occurrences composed of a document identifier d, a term identifierÑa pair t(q,i) composed of a question number q and a unique index iÑ, a text sequence, and a variation identifier v (a metarule). For instance, the following index : LA092690-0038 t(131,1) making many automobiles NtoVSemArg means that the occurrence making many automobiles from document d=LA092690-0038 is obtained as a variant of term i=1 in question q=131 (car maker) through the variation NtoVSemArg given in Section 3.2. Each document d selected for a question q is associated with a weight. The weighting scheme relies on a measure of quality of the different families of variations described by JacqueminÊ(1999): non-variant occurrences are weighted 3.0, morphological and morphosyntactic variants are weighted 2.0, and semantic and morpho-syntactico-semantic variants are weighted 1.0.

Since proper names are more reliable indices than common names, each term t(q,i) receives a weight P(t(q , i )) between 0 and 1.0 corresponding to its proportion of proper names. For instance, President Cleveland's wife is weighted 2/3=0.66. Since another factor of reliability is the length of terms, a factor |t(q,i)| in the weighting formula denotes the number of words in term t(q,i). The weight W q (d) of a query q in a document d is given by the following formula (1). The products of the weightings of each term extracted by the indexer are summed over the indices I(d) extracted from document d and normalized according to the number of terms |T(q)| in query q.

W (d) ( ) ( ( ( , ))) ( , ) ( ) q ( ( , ), ) ( ) = × + × ∈ ∑ w v P t q i t q i T q t q i v I d 1 2 (1)
Mainly two types of weighting curves are observed for the retrieved documents: curves with a plateau and a sharp slope at a given threshold (Figure 2.a) and curves with a slightly decreasing weight (Figure 2.b). The edge of a plateau is detected by examining simultaneously the relative decrease of the slope with respect to the preceding one, and the relative decrease of the value with respect to the preceding one. When a threshold is detected, we only select documents before this threshold, otherwise a fixed cutoff threshold is used. In our experiments, for each query q, the 200 best ranked documents retrieved by the search engine 1 were subsequently processed by the reindexing module. Our studies [START_REF] Ferret | QALC Ñ the Question-Answering system of LIMSI-CNRS[END_REF] show that 200 is a minimum number such as almost all the relevant documents are kept. When no threshold was detected, we fixed the value of the threshold to 100. weight of document #9 is 7.29 because the term Federal Republic only exists in document #8. This term has a high weight because it is composed of two proper names.

Question-Answer Matching

Question type categorization

Question type categorization is performed in order to assign features to questions and use these features for the similarity measurement between a question and potential answer sentences. Basically, question categorization allows the prediction of the kind(s) of answer, called target (for instance, NUMBER). Sentences inside the retrieved documents are labeled with the same tags as questions. During the similarity measurement, the more the question and a sentence share the same tags, the more they are considered as involved in a question-answer relation. For example:

Question:

How many people live in the Falklands? Ñ> target = NUMBER Answer:

F a l k l a n d s p o p u l a t i o n o f <bnumex TYPE=NUMBER> 2,100 <enumex> is concentrated.

We established 17 types of answer. Some systems define more categories. For instance Prager et all (2000) identify about 50 types of answer.

Answer Selection

In the QALC system, we have taken the sentence as a basic unit because it is large enough to contain the answer to questions about simple facts and to give a context that permits the user to judge if the suggested answer is actually correct. The module associates each question with the N a most similar sentences (N a is equal to 5 for the QA task at TREC).

The overall principle of the selection process is the following: each sentence from the documents selected for a question is compared with this question. To perform this comparison, sentences and questions are turned into vectors that contain three kinds of elements: content words, term identifiers and named entity tags. A specific weight (between 0 and 1.0) is associated with each of these elements in order to express their relative importance.

The content words are the lemmatized forms of mainly adjectives, verbs and nouns such as they are given by the TreeTagger. Each content word in a vector is weighted according to its degree of specificity in relation to the corpus in which answers are searched through the tf.idf weighting scheme. For questions, the term identifiers refer to the terms extracted by the term extractor described in SectionÊ3.1 and receive a fixed weight. In sentence vectors, term identifiers are associated with the normalized score from the ranking module (see Section 3.3). The named entity tags correspond to the possible types of answers, provided by the question analysis module. In each sentence these tags delimit the named entities that were recognized by the corresponding module of the QALC system and specify their type. Unlike term identifiers, named entity tags are given the same fixed weight in both sentence and question vectors because the matching module uses the types of the named entities and not their values.

In our experiments, the linguistic features (terms and named entities) are used to favor appropriate sentences when they have not enough content words in common with the question or when the question only contains a few content words. Thus, the weights of term identifiers or named entity tags are reduced by applying a coefficient in order to be globally lower than the weights of the content words.

Finally, the comparison between a sentence vector V d and a question vector V q is achieved by computing the following similarity measure:

∑ ∑ = j j i i d q wq wd V V sim ) , ( (2)
where wq j is the weight of an element in the question vector and wd i is the weight of an element in a sentence vector that is also in the question vector. This measure evaluates the proportion and the importance of the elements in the question vector that are found in the sentence vector with regards to all the elements of the question vector. Moreover, when the similarity value is nearly the same for two sentences, we favor the one in which the content words of the question are the least scattered.

The next part gives an example of the matching operations for the TREC8 question Q16 What two US biochemists won the Nobel Prize in medicine in 1992? This question is turned into the following vector: two (1.0) US (1.0) biochemist (0.9) nobel (1.0) prize (0,6) medicine (0,5) win (0,3) 1992 (1.0) <PERSON> (0.5) 16.01 (0.5) 16.04 (0.5)

where <PERSON> is the expected type of the answer, 16.01 is the identifier of the U S biochemist term and 16.04 is the identifier of the Nobel Prize term. The same kind of vector is built for the sentence <NUMBER> Two </NUMBER> US biochemists, <PERSON> Edwin Krebs </PERSON> and <CITY> Edmond </CITY> Fischer, jointly won the <NUMBER> 1992 </NUMBER> Nobel Medicine Prize for work that could advance the search for an anti-cancer drug, coming from the document FT924-14045 that was selected for the question where the weight 0.0 is given to the elements that are not part of the question vector. The term US biochemist is found with no variation and Nobel Prize appears as a syntactic variant. Finally, according to (2), the similarity measure between theses two vectors is equal to 0.974.

Results and Evaluation

We sent to TREC9 three runs whose variations concern the searched engine used and the length of the answer (250 or 50 characters). Among those runs, the best one obtained a score of 0.407 with 375 correct answers among 682 questions, for answers of 250 characters length. The score computed by NIST is the reciprocal mean of the rank, from 1 to 5, of the correct answer. With this score, the QALC system was ranked 6th among 25 participants at TREC 9 QA task. Document selection relies on a quantitative measure, i.e. the document weight, whose computation is based on syntactic and semantic indices, i.e. the terms and the terminological variants. Those indices allow the system to take into account words as well as group of words and their internal relations within the documents. Following examples, that we have got from selected documents for TREC9 QA task, show what kind of indices are added to the question words.

For the question 252 When was the first flush toilet invented? , one multi-word extracted term is flush toilet. This term is marked by FASTR when recognized in a document, but it is also marked when a variant is found, as for instance low-flush toilet in the following document sentence where low-flush is recognized as equivalent to flush: Santa Barbara , Calif. , is giving $ 80 to anyone who converts to a low-flush toilet. In the given examples, after the identification number of the term, appears the reference term, made of the lemmatized form of the words and their syntactic category, followed by the variant found in the sentence, with each word, its lemmatized form and its category, and finally its weight.

In the example above, the term found in the sentence is equivalent to the reference term, and thus its weight is 1.00.

The second example shows a semantic variant. Salary and average salary are terms extracted from the question 337, What's the average salary of a professional baseball player ?. The semantic variant pay, got from WordNet, was recognized in the following sentenceÊ: Did the NBA union opt for the courtroom because its members, whose average pay tops $500000 a year, wouldn't stand still for a strike over free agency ? In order to evaluate the efficiency of the selection process, we proceeded to several measures. We apply our system on the material given for the TREC8 evaluation, one time with the selection process, and another time without this process. At each time, 200 documents were returned by the search engine for each of the 200 questions. When selection was applied, at most 100 documents were selected and subsequently processed by the matching module. Otherwise, the 200 documents were processed. The system was scored by 0.463 in the first case, and by 0.452 in the second case. These results show that the score increases when processing less documents above all because it is just the relevant documents that are selected.

The benefit from performing such a selection is also illustrated by the results given in Table 1, computed on the TREC9 results. We see that the selection process discards a lot of documents for 50% of the questions (340 questions are processed from less than 100 documents). The document set retrieved for those questions had a weighting curve with a sharp slope and a plateau as in Figure 2(a). QALC finds more often the correct answer and in a better position for these 340 questions than for the 342 remaining ones. The average number of documents selected, when there are less than 100, is 37. These results are very interesting when applying such time-consuming processes as named entity recognition and question/sentence matching. Document selection will also enable us to apply later on syntactic and semantic sentence analysis.

Conclusion

The goal of a question-answering system is to find an answer to a precise question, with a response time short enough to satisfy the user. As the answer is searched within a great amount of documents, it seems relevant to apply mainly numerical methods because they are fast. But, as we said in the introduction, precise answers cannot be obtained without adding NLP tools to IR techniques. In this paper, we proposed a question answering system which uses terminological variants first to reduce the number of documents to process while increasing the system performance, and then to improve the matching between a question and its potential answers. Furthermore, reducing the amount of text to process will afterwards allow us to apply more complex methods such as semantic analysis. Indeed, TREC organizers foresee a number of possible improvements for the futureÊ: real-time answering, evaluation and justification of the answer, completeness of the answer which could result from answers distributed along multiple documents, and finally interactive question answering so that the user could specify her/his intention. All those improvements require more data sources as well as advanced reasoning about pragmatic and semantic knowledge.

Thus, the improvements that we now want to bring to our system will essentially pertain to a semantic and pragmatic approach. For instance, WordNet that we already use to get the semantic variants of a word, will be exploited to refine our set of question types. We also plan to use a shallow syntactico-semantic parser in order to construct a semantic representation of both the potential answer and the question. This representation will allow QALC to select the answer not only from the terms and variants but also from the syntactic and semantic links that terms share with each other.

Figure 1 .

 1 Figure 1. The QALC system

Figure 2 .

 2 Figure 2. Two types of weighting curve.

  252.01 flush toilet[JJ][NN] low-flush[flush][JJ] toilet[toilet][NN]1.00

  337.01 salary[NN] pay[pay][NN] 0.25 337.00 average [JJ]salary[NN] average[average][JJ] pay[pay][NN] 0.40

Table 1 .

 1 Evaluation of the ranking process

	Number of documents selected	100	<<100
	by ranking
	Distribution among the	342	340
	questions	(50%)	(50%)
	Number of correct answers	175	200
		(51%)	(59%)
	Number of correct answer at	88	128
	rank 1	(50%)	(64%)

This sentence is taken from the output of the named entity recognizer.