Rune Matthiesen
email: rune.matthiesen@nms.unl.pt

Manuel S Rodriguez

Ana Sofia Carvalho

A Computational Tool for Analysis of Mass Spectrometry Data of Ubiquitin-Enriched Samples

Keywords: Ubiquitin proteasome system, ubiquitin enrichment, mass spectrometry, R programming language, ubiquitin branch statistics, proximity drugs, proteolysis targeting chimera

Mass spectrometry data on ubiquitin and ubiquitin-like modifiers are becoming increasingly more accessible and the coverage progressively deepen as methodologies mature. This type of mass spectrometry data is linked to specific data analysis pipelines for ubiquitin. This chapter describes a computational tool to facilitate analysis of mass spectrometry data obtained on ubiquitin enriched samples. For example, the analysis of ubiquitin branch site statistics and functional enrichment analysis against ubiquitin proteasome system protein sets are completed with a few functional calls.

We foresee that the proposed computational methodology can aid in proximity drug design by, for example, elucidating the expression of E3 ligases and other factors related to the ubiquitin proteasome system.

Introduction

Mass spectrometry (MS) methodologies for studying post translational modifications (PTMs) continue to develop. We might have elucidated the genetic code, but there are a lot of unexplored combinations of PTMs that are poorly understood in terms of their effect on protein function. The number of possible combinations of PTMs on a specific protein grows exponentially with the number of modifications and modification sites we consider in the analysis. For example, given hundreds of possible modifications, each with 5-50 possible modification sites, leads to an astronomically large number of combinations (1). Furthermore, a number of modifications can form heterogeneous branch structures such as for example glycosylation (2), ubiquitination and ubiquitin-like modifiers.

Ubiquitination and ubiquitin-like modifiers (3) mainly function intracellularly. However, the system is complex and incompletely understood, which constitute one justification for the proposed computational tool presented in this chapter.

The design of proximity drugs is based on understanding the ubiquitin proteasome system (UPS), which constitute a vast number of protein families with main players such as ubiquitin and ubiquitinlike modifiers, E1, E2 and E3 ligases, deubiquitinases and the proteasome. For example, the expression level of E3 ligases can vary depending on the cellular state as demonstrated in the analysis in this chapter. Given that proximity drugs are dependent on the presence of a specific targeted ligase, this type of analysis should prove useful in the design process. Furthermore, the majority of the literature on UPS is not systematized. For example, frequently specific proteins are referred to by nonstandard names, making systematic computational analysis complex. One example is FAT10 which is often used in the literature but the official gene name is UBD (4). Another example is ubiquitin which is coded by four genes in the human genome, namely RPS27A, UBB, UBC and UBA52. These genes contain one, three, nine and one ubiquitin modifying protein, respectively, all with exactly the same sequence. Therefore, it can be concluded that identification of N terminal diglycine can either arise from one of the polyubiquitin coding genes or from N-terminal modification with ubiquitin by ubiquitin. The proposed R package contains annotation of the official gene names of protein in the ubiquitin system, which facilitates automated analysis of MS data.

Ubiquitin and ubiquitin-like modifiers are covalently bound to amino groups of lysine residues or to the N-terminal of the proteins that they modify. Ubiquitin and ubiquitin-like modifiers also contain lysine residues that, in turn, can be modified. Specific branch linkages of ubiquitin have been linked to specific molecular functions. Although, the system is far more complex, having heterogeneous linkage structures that mix ubiquitin with ubiquitin-like modifiers. Furthermore, ubiquitin can also undergo other modifications such as acetylation and phosphorylation (3). The proposed R package contains functions that automatically estimate the overall average level of linkages in each sample for cross comparisons. This tool was developed based on our past research on tandem ubiquitin binding entities (TUBEs) combined with MS (5-7). However, it can be applied to basically all the current ubiquitin enrichment strategies that currently are being combined with MS identification (see Figure 1). These technologies TUBEs (8), UbiSite (9), His6-tag enrichment (10) and in vivo biotinylation of ubiquitin (11). Each of these technologies can be combined with additional di-glycine enrichment. The R package "ubiquitin proteasome system in R based on mass spectrometry" (UPSRM) is demonstrated here with a data set obtained using a recent technology called UBISITE for large scale enrichment of ubiquitin modified peptides combined with MS identification (12). However, UPSRM works for all enrichment strategies that end with identification of di-glycine by MS.

The output results of R package UPSRM compare ubiquitin occupancy branch sites on ubiquitin and ubiquitin like modifiers in different conditions. For example, cell treatment with protease inhibitors.

Overall, these comparisons can potentially highlight the main ubiquitin branches affected by a specific drug targeting ubiquitin ligases, deubiquitinases or more recently the proteolysis targeting chimera (PROTAC) drugs targeting protein degradation using the ubiquitin code.

Materials

1. R Cran (https://cran.r-project.org/) 2. R studio (optional -https://www.rstudio.com/) 3. R packages: ggpubr, plyr, gplots, ComplexHeatmap. 4. MaxQuant (13) data: "GlyGly (K)Sites.txt" and "proteinGroups.txt" (see Note 1). For this tutorial the data set PXD027328 in ProteomeXchange was used. Only the two text files "GlyGly (K)Sites.txt" and "proteinGroups.txt" are necessary to download.

Methods

Software setup and installation of R packages

1. Follow the instructions in the provided links to install R Cran.

Run the below commands in an R session to install UPSRM:

install.packages("ggpubr") install.packages("plyr") install.packages("gplots") install.packages("ComplexHeatmap") install.packages("remotes") library(remotes) remotes::install_github("ruma1974/UPSRM@main") 3. Load all packages needed (see Note 2): library(UPSRM) library(ComplexHeatmap)

Perform UPS protein expression analysis

The example analysis is performed on a recent data set in PXD027328. The data set consists of U2OS cell lines treated with DMSO, MG132 (proteasome inhibitor), PR619 (DUB inhibitor) or TAK243 (UAE inhibitor). The below steps demonstrate the R commands to run and the expected output. "Proteasome", "SUMO", "

"ProteasomeActivators", "Ub", "E1", "E1sumo", "E2", "E3", "Ubl" 4. Annotated genes in a specific UPS group can be retrieved with for example:

showGenes("E3") 5. Quantitative LFQ values for the E3 ligases can be extracted with:

M=getQdata(res,"E3")

Visualize quantitative UPS data in R

The R package "ComplexHeatmap" provides useful functions for visualizing numeric matrix data.

1. Rename columns to remove redundant information.

colnames(M)=c("DMSO1", "DMSO2", "DMSO3", "MG1", "MG2", "MG3", "PR1", "PR2", "PR3", "TAK1", "TAK2", "TAK3")

Define sample conditions

Fac=c("DMSO", "DMSO", "DMSO", "MG", "MG", "MG", "PR", "PR", "PR", "TAK", "TAK", "TAK")

3. Use sample condition information to generate a heatmap annotation. We observe that E3 ligase levels are heavily affected by treatment conditions in the same cell line.

This illustrates the need to profile E3 ligases in specific cell conditions for proximity drug design.

Comparative average branch topology for ubiquitin

The below code demonstrates how UPSRM convince functions can be used to explore average ubiquitin branch topology across sample conditions. It assumes that the MaxQuant data is already loaded (see section 3.2).

1. The possible ubiquitin or ubiquitin like modifiers that can be analyzed can be retrieved by: UPSRM::showUBls() 2. Next we define the comparisons to perform (DMSO is used as reference in below example):

comp <-list( c("MG", "DMSO"), c("PR", "DMSO"), c("TAK", "DMSO") )

Fac=c("DMSO", "DMSO", "DMSO", "MG", "MG", "MG", "PR", "PR", "PR", "TAK", "TAK", "TAK")

3. Boxplot summarizing average ubiquitin branch sites across conditions is written to a pdf file by the below command (see Figure 3):

1 .

 1 Provide the directory with the MaxQuant text output files Dir="[Directory]" 2. The command below automatically loads the two data files into R. res=loadMaxQuant(Dir) 3. Run the command below to see the protein groups available. showUPSgroups() Output (see Note 3):

  ha = ComplexHeatmap::HeatmapAnnotation(Sample = Fac,col = list(Sample = c(DMSO = "red", MG = "green",PR="brown", TAK = "blue")),na_col = "black") 4. Plot the expression heatmap of E3 ligases to generate Figure 2. x11(w=20,h=10) # only need on linux systems ComplexHeatmap::Heatmap(log2(M+1), col=gplots::redgreen(255), name = "LFQ", top_annotation =ha,show_row_names =FALSE)

FiguresFigure 1 . 11 231Figure 2 .

 1112 Figures

Figure 3 .

 3 Figure 3. Average ubiquitin branch sites across sample conditions. 234

Figure 4 .

 4 Figure 4. Average ubiquitin-SUMO1 branch sites across sample conditions.

Acknowledgment R.M. is supported by Fundação para a Ciência e a Tecnologia (CEEC position, 2019-2025 investigator). This article is a result of the projects (iNOVA4Health-UIDB/04462/2020), supported by Lisboa Portugal Regional Operational Programme (Lisboa2020), under the PORTUGAL 2020 Partnership Agreement, through the European Regional Development Fund (ERDF). This work is also funded by FEDER funds through the COMPETE 2020 Programme and National Funds through FCT-Portuguese Foundation for Science and Technology under the projects number PTDC/BTM-TEC/30087/2017 and PTDC/BTM-TEC/30088/2017. This publication is based upon work from 8 COST Action, CA20113 `PROTEOCURE` supported by COST (European Cooperation in Science and Technology).

M=getUbQdata(res,"Ub",Fac,comp,"Q_Ubsites.pdf") 4. Boxplot summarizing average SUMO1-ubiquitin branch sites across conditions is written to a pdf file by the command below (see Figure 4): M=getUbQdata(res,"Ub",Fac,comp,"Q_SUMO1sites.pdf")

Notes

1. The file "GlyGly (K)Sites.txt" is optional. If only "proteinGroups.txt" is provided then expression analysis of UPS factors is still possible. The columns in "GlyGly (K)Sites.txt" must include "Intensity.[sample]", "Gene.names", "GlyGly..K..Probabilities". The columns in "proteinGroups.txt" must contain "LFQ.[sample]" and "Gene.names". If interest exists the authors will update the R package with support for other database dependent search engines.

2. The other installed R packages are used by UPSRM and will be loaded indirectly when using UPSRM functions.

3. The genes annotated to each UPS group will likely change overtime as more knowledge is generated on UPS. We consider the current annotations as core annotations but we will be pleased to receive user feedback to update UPSRM with additional UPS groups.


Grégoire Quinet

Pierre Génin

Naima Belgareh-Touzé

Oznur Ozturk

Robert Weil

Mickael M Cohen

Renaud Legouis

Manuel S Rodriguez
email: manuel.rodriguez@lcc-toulouse.fr

Analysis of ATG8 family members using LC3-interacting regions (LIR)-based molecular traps

Keywords: LIR, ATG8-family, LC3, GABARAP, Autophagy, Isolation, Purification

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Autophagy is a conserved mechanism that drives bulk degradation in mammalian, plants, insects and fungi. This degradation process occurs within an organelle called autophagosome that fuses with mammalian lysosomes or plant/yeast vacuoles after substrate engulfment (1). Distinct autophagy mechanisms selectively eliminate different types of cargoes through the lysosomes. Therefore, several types of selective autophagy pathways have been identified depending on the nature of the cargo (2). For example, mitophagy, xenophagy, proteaphagy are the names for selective autophagy of mitochondria, pathogens or proteasomes, respectively.

Among the AuTophaGy (ATG) proteins identified in yeast, ATG8 is essential for the autophagy regulatory cascade (3). ATG8 homologs in other species have been distinctly named LGG1 and LGG2 in C. elegans or LC3/GABARAP in mammalians (4, 5). LC3B is often used as autophagy activation marker in human cells. Lipidated ATG8 proteins are tethered into the autophagosome membrane, hence driving autophagosome maturation and cargo recruitment through a complex combination of autophagy receptor, cofactors and ubiquitin signals (2). Consequently, ATG8 proteins have been extensively used as biomarkers to monitor autophagosome formation, localisation and dynamics in physiological and pathological conditions (6).

To easily isolate and analyse ATG8 proteins from various biological models, we developed innovative molecular tools as an alternative to expensive antibodies or probes overexpression. These tools named LC3 traps contain multiple LC3-Interacting Regions (LIR) disposed in tandem that efficiently isolate endogenous ATG8 from cell lysates (7) (see Figure 1). Distinct LC3-traps were developed based in LIR concensus sequences with hydrophobic core residues W (Wx8-LC3 traps), F (Fx8-LC3 traps). These easy-to-use tools enhance the attractiveness of the LC3 traps to monitor selective autophagy events.

Protocols detailing the production and use of LC3 traps for purification of ATG8associated complexes in several biological models are detailed below.

Materials

Prepare solutions with ultrapure water (8 MΩ x cm at 25°C) and use analytical grade reagents. Store all reagents at 4°C unless indicated otherwise. If sodium azide is not added to stock reagents, it is advised to prepare solutions as fresh as possible. To avoid contaminations, solution can be filtered and conserved as frozen aliquots.

Buffers and reagents

1. GST expressing plasmid (i.e. pGEX-6P-1).

2. Bacteria culture media: supplement Luria Broth (LB) and LB-agar with 100 µg/ml of carbenicillin or 100 µg/ml of ampicillin when indicated.

3. 1 M isopropyl β-D-1-thiogalactopyranoside (IPTG) stock solution.

Sterile cold 1x Phosphate Buffered Saline (PBS).

5. Empty plastic 30 ml columns for affinity chromatography.

6. Gluthatione agarose beads 7. Dialysis tubbing with a 12.4 kDa cut-off

Affinity Chromatography

1. Prepare lyophilised glutathione beads by adding 3 volumes of de-ionised water per 10 ml of lyophilised glutathione-agarose beads (see Note 2). Rotate beads 30 minutes at room temperature then overnight at 4°C. Wash agarose beads with ten volumes of de-ionised water or 1x PBS three times (see Note 3). Centrifuge at 300 x g for 5 minutes to separate beads/buffer phases. Finally, resuspend the agarose beads in PBS to obtain 50% (v/v) slurry and store at 4°C until use.

2. LC3 traps can be produced as indicated below or purchased (BMolecular).

Dialysis

1. Dialysis Buffer: 1x PBS, 0.8 M NaCl.

2. Dialysis tubbing 12.4 kDa cut-off.

Methods

Carry out all steps at 4°C unless specified otherwise. All the procedure is illustrated in

Purification of recombinant LC3 traps

1. Transform Escherichia coli BL21 strain with plasmids expressing GST control or GST-LC3 traps containing 8 LIRs and plate onto LB-agar plates supplemented with 100 µg/ml of carbenicillin (see Note 4) (7).

2. Grow 1 single colony of transformed bacteria in precultures of 30 ml of LB supplemented with 100 g/ml of ampicillin, overnight at 28°C with shaking.

3. Grow the cells in 1 L of LB plus 100 g/ml of ampicillin at 37°C with shaking. Start with a 0.05-0.1 OD600 culture that should reach 0.4-0.5 OD600 in approximately 3-4 hours.

Put aside one aliquot (1 ml) of culture as control before induction with IPTG.

4. Induce expression of LC3 traps by addition of 1 mM of IPTG and shake culture overnight at 20°C. Put aside an aliquot (1 ml) of culture after induction with IPTG.

5. Centrifuge saved 1 ml aliquots and wash bacterial pellets with 1x PBS. Discard the supernatant and resuspend the pellet in 100 µg of EB buffer. Shake and boil samples at 95°C during 30 minutes. 8. Resuspend frozen pellets in 20 ml of BL buffer. 9. Sonicate cell pellets at 30% Amp during 30 seconds. Repeat 6 times and between each pulse incubate 1 minute on ice to avoid sample heating.

10. Supplement lysates with 2% (v/v) of Triton X-100, then rotate for 15 minutes at 4°C. 11. Clarify lysates by ultracentrifugation for 1 hour at 48,000 x g and 4°C. Save 100 µg of clarified lysates (input) to be analysed together with all other fractions. 12. Equilibrate the glutathione-agarose beads (1 ml of beads per L of bacterial culture) with BL buffer containing 2% (v/v) Triton X-100.

13. Incubate clarified lysates with equilibrate beads and supplemented with 2 mM DTT.

Incubate overnight rotating at 4°C (incubation time can be reduced at 4 hours) (see Note 6).

Load agarose beads into an empty plastic column. Collect flow through (FT) to verify if most GST protein was captured in the column (see Note 7).

15. Wash 4 times with 10 column volumes of BL buffer supplemented with 1% Triton X-100.

16. Elute LC3 traps with 6-12 fractions of 1 ml of 50 mM Tris-HCl pH 9.5 supplemented with 0.8 M NaCl and 10 mM of reduced glutathione. Verify the protein elution peak by using Bradford assay for each fraction (see Note 8). 17. Dialyse eluted fraction against PBS supplemented with 0.8 M NaCl. Load all samples in one or two dialysis tubbing with a 12.4 kDa cut-off. Perform dialysis at 4°C during 24 hours changing buffer every 2-3 hours of dialysis (see Note 9).

18. Concentrate LC3 traps up to 5 g/l by using ultracentrifuge filter with a 3 kDa molecular weight cut-off (see Note 10). Protein concentration can be estimated by UV absorbance.

19. Store purified LC3 traps at -80°C in PBS 0.8 M NaCl containing 10% glycerol in small aliquots. Avoid refreezing samples (see Note 11).

Pull down of recombinant ATG8 proteins

1. Equilibrate glutathione-agarose beads with 1x PBS supplemented with 0.1% Igepal and 2 mM DTT. 3. Save 1/10 of the sample to be used as input fraction. Dilute the sample in equal volume of EB buffer to be analysed with other fractions. 4. Add to the 100 µl of dried equilibrated glutathione-agarose beads, sufficient BL buffer volume to complete the final volume of reaction of 500 l.

Incubate binding reaction by rotating at 4°C for 1 hour (see Note 13).

6. Centrifuge beads at 300 x g during 5 minutes at 4°C and collect supernatant (FT fraction) for analysis.

7. Wash the beads three times with 1 ml of cold 1x PBS supplemented with BW buffer, centrifuge beads at 300 x g during 5 minutes at 4°C. Discard supernatant and make sure no liquid remains in the beads. 8. To elute bound fraction from beads using a shaker-incubator, add 100 µl of EB buffer and heat 5 minutes at 95°C with shaking at 1,000 rpm. 2. In the morning, dilute the cells in 20 ml of SD-Ura to an OD600 of 0.1 and grow the cells at 30°C with shaking, until late exponential phase (OD 600: 1.5-2). At this step, the level of GFP-ATG8 is very low.

3. Dilute the cells in 100 ml of SG-Ura to an OD 600 of 0.1. Grow the cells overnight at 30°C with shaking, to an OD 600 >1 (see Note 24 and Note 25). After 16-18 hours of growth in glycerol containing media, the level of GFP-ATG8 is enhanced and some free GFP resulting from GFP-ATG8 cleavage in the vacuole, a hallmark of autophagy, is detected (7, 9). 4. Pellet cells with a 4,000 x g centrifugation during 5 minutes and wash pellets twice with an equivalent volume of sterile water (see Note 26).

5.

Incubate the cells at 30°C with shaking during 2 hours in an equivalent volume of nitrogen depleted medium (SD-N) to induce mitophagy (7, 9) (see Note 27).

6. Measure the OD600 of the yeast culture and harvest 100 OD600 units by centrifugation at 4,000 x g during 5 minutes. Resuspend the cells at a concentration of 1 mg/ml of yeast cells in cold CLB. Add protease inhibitors just before using the buffer.

2.

Different commercially available glutathione beads have different sizes and are covered with distinct densities of glutathione. Make sure to work with beads having at least the capacity to capture 10 mg of protein per ml of glutathione dried beads.

3.

Glutathione beads may come already in solution when purchased from distinct distributors. In all cases, eliminate preservative reagents by exhaustively washing with 1x PBS. Just before use, equilibrate beads in CLB.

4.

Carbenicillin can be substituted to ampicillin and is preferred for LB-agar plate selection since it is more resistant to light and temperature and can be stored for longer periods.

5.

Long term storage of pellets can be done at -80°C. Thaw pellets on ice with direct contact with the BL buffer.

6.

GST binding to glutathione is a slow process, a minimum of 4 hour binding is recommended to obtain >80% of protein binding to beads.

7.

Store the FT at -20°C. If after gel verification this fraction contains a significant amount of GST/LC3-trap protein, load it again into a new column to recover more protein.

8.

Usually, protein peaks between fraction 2 and 7 but it depends on the quality of the induction.

9.

Most glutathione is eliminated during the first 2-3 hours of dialysis. However, to optimise the recovery of the LC3-trap and captured ATG8 molecules from cell extracts, it is highly recommended to extend the dialysis time.

10. LC3 traps are highly hydrophobic and the limit of solubility is around 3-5 mg/ml. 11. LC3 traps are highly hydrophobic and are thus prone to aggregation. It is advisable to prepare small aliquots conserved at -20°C for short term storage and -80°C for long term storage. Storage buffer contains 10% glycerol. LC3 traps should not be frozen and thawed more than 2-3 times. 12. To avoid saturation of the LC3 traps, do not use too many proteins in the input compared to the quantity of the traps added. The optimal amount of LC3 traps used depends on the relative abundance of ATG8 proteins available in the samples. It is recommended to set up conditions by analysing by western blot the different fractions from the pull-down experiments to optimise the traps/target ratio. For example, for an optimised pull down of recombinant GABARAP proteins using Fx8-LC3 traps, we recommend to use at least 0.25 molar of traps per molar of target (i.e. traps/target molar ratios superior to 1:4).

Binding time could be decreased up to 30 minutes if the concentration of ATG8

proteins is high.

14.

Ponceau, Coomassie and silver stainings provide useful information about size and transfer of proteins, as well as efficiency and background of pull-down experiments performed. These controls are strongly recommended while setting up a pull-down experiment with LC3 traps.

15. This could be achieved by analysing total cell extracts by western blot or by immunofluorescence.

16. The total protein concentration used depends on the cell type and relative abundance of LC3/GABARAP proteins present in each cell type. Cell type depending settings are recommended to be established before capture with LC3 traps. Alternative lysis buffer and procedures can be considered as long as they do not alter LC3 traps conformation.

Compatibility of lysis buffer with an optimal LC3 trap capture must be performed. 17. Use nematode strains according to the needs of the experiments, for instance wild-type strain (N2) versus transgenic strains of interest.

18. Worms can also be grown in liquid culture.

19.

A minimum of 5,000 worms is needed but scaling up the culture allows to freeze aliquots.

20.

Grinding can be done using 1.4 mm and 2.8 mm ceramic beads (zirconium oxide) three times for 20 seconds at 6,500 rpm separated by 30-second pauses.

21.

It is essential to avoid heating of the samples. If a non-refrigerated grinder is used samples must be kept on ice during 5 minutes between the 2 cycles.

22.

The pGFP-ATG8 plasmid is optional since the traps interact with the LIR domain.

However, it is a precious tool to precisely follow induction of mitophagy by fluorescence microscopy and western blot.

23. GFP-ATG8 is under the control of its natural promoter.

24.

The doubling time for wild type yeast cells is different in glucose and glycerol containing media. Depending on the genetic background, the doubling time can be 3 times higher in glycerol (>180 minutes) versus glucose containing media (60-120 minutes).

25.

Growth in glycerol induces respiration and enhances the mitochondrial mass.

26. These washing steps are essential to get rid of any trace of nitrogen.

27.

In glucose containing SD-N media the cells undergo fermentation and the absence of nitrogen induces autophagy. In such conditions, mitochondria are less essential. They can be "sacrificed" and degraded by mitophagy.

32.

To reduce background in the bound fraction, perform up to 6 washing steps with cold BW buffer. Tween 20 concentration in 1x PBS can also be increased to 0.1%. Be aware that increasing the stringency of the washes will reduce the binding of specific interacting proteins.

33. pH of elution buffer must be between 8.5 and 9.5 for an optimal elution. A single elution may not be sufficient. A second elution could be considered to elute proteins retained to the beads. If a more concentrated eluted fraction is needed, the volume of EB buffer can be reduced. Glutathione-agarose beads must be soaked in the EB buffer. LGG-2 ATG8

LGG

Figure 2 .

 2 Figure 2.

6 .

 6 Run both samples in SDS-PAGE. Stain gels with Coomassie blue to verify the induction of the GST-LC3 traps with IPTG. 7. Centrifuge 1 L of bacterial culture at 6,600 x g during 30 minutes at 4°C. Wash pellets twice with cold 1x PBS. Discard supernatant and store pellets at -20°C until use (see Note 5).

2 .

 2 Dilute the recombinant ATG8 proteins in 1x PBS supplemented with 0.1% Igepal and 2 mM DTT. The final volume should integrate the amount of LC3 traps required for the pull down (see Note 12).

9 . 3 . 3 2 . 3 .

 93323 Analyse 10 µl of eluted fractions in PAGE (15% polyacrylamide) according to the molecular size of AT8 proteins of interest. Stain gels by Coomassie blue or detect proteins by western blot (see Note 14). Capture and identification of ATG8 proteins from distinct biologic models 3.3.1 Lysis of mammalian cells 1. Grow cells until the desired confluence. For example, 1-2 mg total proteins can be extracted from 10-20 x 10 6 HeLa cells (150 mm plate) after 48 hour growth. If any treatment is used, set up conditions to select the best time of treatment to better accumulate LC3/GABARAP proteins (e.g. bafilomycin A1) (see Note 15). Before cell harvesting, wash them twice with 1x PBS to eliminate serum and treatments used. Centrifuge cells for 5 minutes at 500 x g at room temperature and remove supernatant.

4 .

 4 Add 800 µl to 1 ml of CLB on the pellet and slowly homogenise cells. 1. Inoculate 1 single colony of wild type yeast cells (W303 or BY4741 for instance) transformed with the pGFP-ATG8 plasmid (see Note 22 and Note 23) (8) into 2 ml of SD-Ura and grow the cells overnight at 30°C with shaking.

7 . 3

 73 Add an equal volume of 425-600 µm acid washed glass beads and break the cells by vortexing at 4°C with 5 cycles of 30 seconds with 5-minute rests.8. Transfer the yeast cell lysate and the beads on a mini spin chromatography column, to get rid of glass beads without loosing cell lysate (optional), and centrifuge during 1 minute at 3,500 x g and 4°C.10. Typical results are illustrated in Figure

28.

  During this step unbroken cells and cell debris are pelleted and discarded. 29. Repeat this step, if necessary, until all cell debris are pelleted. 30. These cell extracts are mainly cytoplasmic proteins. If total cell extracts are required, cell lysis by sonication is recommended.31.In case saturated signals of ATG8 proteins are observed in the FT fraction, binding time can be increased up to overnight to optimise the capture of the target. If increasing the binding time is not enough, consider increasing the amount of LC3 traps used.

FiguresFigure 1 .

 1 Figures

- 1 BLIRFigure 2 .Figure 3 :

 123 Figure 2. Procedure for purification of ATG8 molecules using LC3 traps. The main

Acknowledgements

We do thank all members of UbiCARE laboratory for stimulating discussions and/or technical assistance. We thank Agnès Delahodde for providing the RPN-11::GFP strain and Céline Largeau for technical help with C. elegans. This work was supported by the REPERE and prématuration (Ubipiège) programs of Occitanie (France). We acknowledge the COST Action CA20113 `PROTEOCURE` supported by COST (European Cooperation in Science and Technology). MSR was also funded by CONACyT-SRE (Mexico) grant 0280365. RL was funded by Ligue Régionale contre le Cancer (M29506). MMC and NBT are supported by the labex DYNAMO (ANR-11-LABX-0011-DYNAMO), by the ANR grant MOMIT (ANR-17-CE13-0026-01) and by the ANR grant MITOFUSION (ANR-19-CE11-0018).

GQ benefit of a PhD fellowship from the French ministry of education.


Christine Chevallereau
email: christine.chevallereau@ls2n.fr

Philippe Wenger
email: philippe.wenger@ls2n.fr

Anick Abourachid

A new bio-inspired joint with variable stiffness

Keywords: antagonist actuation, stiffness, tendon driven manipulator, pulley

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The scope of this work is the design of bio-inspired collaborative robots suitable for safe interactions, i.e. allowing joint stiffness modulation. Biological organs constitute interesting models of inspiration for the roboticist. Indeed, they propose frugal solutions both in matter and energy. To mimick the joint between two animal vertebrae, the simplest mechanism is a revolute joint but, if the center of rotation is not fixed like in the knee joint [START_REF] Hamon | Cross four-bar linkage for the knees of a planar bipedal robot[END_REF], an anti-parallelogram mechanism would be more appropriate. Biological joints are actuated by antagonistic muscles. Most of the time, two antagonistic muscles work in opposite ways: when one contracts, the other relaxes, so that energy consumption is minimized [START_REF] Latash | Muscle coactivation: definitions, mechanisms, and functions[END_REF]. However, simultaneous activation of antagonistic muscles may occur for a short time. This so-called coactivation principle aims to increase the stiffness of the joint [START_REF] Latash | Muscle coactivation: definitions, mechanisms, and functions[END_REF]. Moreover, energy consumption should be minimized and one should be able to increase joint stiffness when needed. Variable stiffness actuators (VSA) have been developed to allow for joint stiffness modulation in applications involving interactions, such as in robots and biped [START_REF] Vanderborght | Variable impedance actuators: A review[END_REF]. Stiffness modulation in VSA can be achieved through software or hardware. Several different hardware implementations of VSA have been proposed with appropriate spring arrangement and properties [START_REF] Jafari | Awas-ii: A new actuator with adjustable stiffness based on the novel principle of adaptable pivot point and variable lever ratio[END_REF][START_REF] Esteveny | A novel actuation technology for safe physical human-robot interactions[END_REF][START_REF] Medina | Design and characterization of a novel mechanism of multiple joint stiffness(mmjs)[END_REF] or by changing transmission angle with cams [START_REF] Ham | Compliant actuator designs[END_REF]. Other solutions use antagonistic cable actuation together with springs [START_REF] Zhou | A Cable Based Active Variable Stiffness Module With Decoupled Tension[END_REF]. In such solutions, several pulleys are needed and stiffness modulation uses rather complex solutions.

In this paper, a simple solution is proposed to allow for stiffness modulation in tendon-actuated joints. This solution uses a elliptical pulley. This rest of this paper is organized in two parts. Section 2 studies and compares coactivation of antagonistic forces in a circular pulley and in a X-joints. The proposed solution, called E-pulley, is proposed in section 3. Section 4 concludes this paper.

Joints actuated by antagonist tendons

In biological systems, the joints are often modeled with revolute joints actuated by antagonistic tendons and/or muscles [START_REF] Biewener | Animal locomotion[END_REF]. However, it was shown recently that stiffness descreases when antagonistic tendon forces increase in simple revolute joints [START_REF] Muralidharan | Optimal design and comparative study of two antagonistically actuated tensegrity joints[END_REF]. When designing tendon-driven joints, the attachment points of the tendons must be defined carefully to avoid singularities when the tendon line crosses the joint. Accordingly, tendons can be attached via pulleys. Not only this solution avoids singularities but it also produces a constant lever arm and it mimics bones swelling at their extremities [START_REF] Elmas | Toute l'UE 5-Anatomie-Cours+ QCM: Organisation des appareils et des systèmes-Aspects morphologiques et fonctionnels[END_REF].

Some biological joints such as the knee joint [START_REF] Hamon | Cross four-bar linkage for the knees of a planar bipedal robot[END_REF] or intervertebrae joints in the bird neck [START_REF] Fasquelle | Identification and control of a 3-X cable-driven manipulator inspired from the bird neck[END_REF] can be modeled by crossed four-bar joints or X-joints. On the other hand, we observed that the knee and ankle joints can be modelled as pulleys, with antagonistic muscles being used to modulate stiffness. Measurements on the bones suggest that the pulleys may not be circular. In the work presented here, we compare the coactivation of X-joint solutions with circular and elliptical pulleys, which could be found in the osteo-muscular system of birds.

We first compare the two joints actuated with antagonistic tendons shown in Fig. 1: the P-module (for pulley) on the left and the X-module (for antiparallelogram joint) on the right. The P-module (resp. the X-module) is defined by parameter R (resp. b and L). The moving link is attached to the pulley or to the upper bar of the anti-parallelogram.

Joint stiffness

Let U be the potential energy of a module:

U = U g + U k + F 1 l 1 + F 2 l 2 , where U g (resp. U k )
is the contribution of gravity (resp. of the springs if any), l 1 , l 2 are the cable lengths and F 1 , F 2 are the forces applied by the cables (see Fig. 1). The equilibrium condition of a module is dU dα = 0, that is:

G + dl 1 dα F 1 + dl 2 dα F 2 = 0 (1)
where G = dUg dα + dU k dα . From fig. 1, it is apparent that dl1 dα ≤ 0 and dl2 dα ≥ 0 around α = 0 (this will be detailed later). The equilibrium solution with minimal forces s.t. 0 ≤ F min ≤ F i ≤ F max is therefore obtained when one of the forces is at F min . For simplicity, we take F min = 0. Suppose that we want to reach a desired configuration α d such that G(α d ) < 0. Then, the minimum force solution denoted by F * is:

F * 2 = - G(α d ) dl2 dα , F * 1 = 0 (2)
Other solutions, which would involve coactivation, can be defined in terms of F 2 as follows:

F 2 = - G(α d ) + dl1 dα F 1 dl2 dα = F * 2 - dl1 dα dl2 dα F 1 (3)
The joint stiffness, for given cable forces F 1 , F 2 is defined by :

K = d 2 U dα 2 = dG dα + d 2 l 1 dα 2 F 1 + d 2 l 2 dα 2 F 2 (4)
For the equilibrium with minimal forces, the stiffness is :

K * = dG(α d ) dα - d 2 l2 dα 2 G(α d ) dl2 dα (5)
The impact of a non-zero force F 1 on the system stiffness is written using equation ( 4):

K = K * + D 1 F 1 (6)
with

D 1 =   d 2 l1 dα 2 dl2 dα -d 2 l2 dα 2 dl1 dα dl2 dα   (7)
To be able to change the joint stiffness by the antagonistic forces, when must have D 1 ̸ = 0. Finding a behavior similar to that observed in biological systems implies that D 1 > 0 for values of α s.t. G(α d ) < 0. Let C be the numerator of D 1 . Since dl2 dα > 0, this condition can be written:

C = d 2 l 1 dα 2 dl 2 dα - d 2 l 2 dα 2 dl 1 dα > 0 (8)
A similar condition can be written for values of α s.t. G(α d ) > 0. It can be shown that this leads to the same conditions (8).

Joint stiffness modulation for the P-module

For the P-module shown in Fig. 1, when the output rotates of an angle δα, the length variation of the left tendon is obviously the length of an arc of circle of angle δα, namely, Rδα. Note that the point of contact of the cable around the pulley does not move since it is defined by the point where the tendon is tangent to the pulley. The length variation of the left tendon is: Rδα.

Accordingly :

dl 1 dα = R, dl 2 dα = -R, d 2 l 1 dα 2 = d 2 l 2 dα 2 = 0, C = 0 (9)
This shows that stiffness modulation is not possible with a P-module and additional devices must be used, see [START_REF] Ham | Compliant actuator designs[END_REF] for example.

Joint stiffness modulation for the X-module

The cable lengths l 1 , l 2 are:

l 1 = l 10 + l -bsin( α 2 ), l 2 = l 20 + l + bsin( α 2 ) ( 10
)
where l 10 , l 20 are constant values, and l is the distance between the midpoints of bottom and top bars [START_REF] Fasquelle | Identification and control of a 3-X cable-driven manipulator inspired from the bird neck[END_REF]:

l = L 2 -b 2 cos 2 ( α 2 ) (11)
Upon successive differentations, we obtain:

dl 1 dα = b 2 cos( α 2 ) sin( α 2 ) 2 L 2 -b 2 cos 2 ( α 2 ) - b 2 cos( α 2 ) ( 12
) dl 2 dα = b 2 cos( α 2 ) sin( α 2 ) 2 L 2 -b 2 cos 2 ( α 2 ) + b 2 cos( α 2 ) (13) d 2 l 1 dα 2 = b 2 (L 2 cos(α) -b 2 cos 4 ( α 2 )) 4(L 2 -b 2 cos 2 ( α 2 )) 3/2 + b 4 sin( α 2 ) (14) d 2 l 2 dα 2 = b 2 (L 2 cos(α) -b 2 cos 4 ( α 2 )) 4(L 2 -b 2 cos 2 ( α 2 )) 3/2 - b 4 sin( α 2 ) (15)
Thus :

C = b 3 (L 2 -b 2 ) cos 3 ( α 2 ) 4(L 2 -b 2 cos 2 ( α 2 )) 3/2 (16)
Since cos( α 2 ) > 0 within the joint limits and since L > b, C is always positive.

A novel module : the E-module

From the previous study, we observe that an increase in stiffness by forces coactivation requires that the cable length expression be non-linear in α and this condition is not satisfied with a classical pulley. We now show that it can be the case if the pulley is elliptical For more simplicity, we are interested in a symmetrical joint with a rotation center fixed at the center of the ellipse. We call this joint and its antagonistic actuation a E-module (for ellipse). Figure 2 shows an example with a = 0.045 m, b = 0.06 m, base point at A = (0.02, -0.1) m for the right tendon and a symmetric base point for the left tendon. Each tendon is attached to the ellipse at a certain point (indicated as B for the right tendon) and passes through a certain base point (A for right tendon). We now need to express the tendon lengths as functions of α. To this goal, we calculate the coordinates of the point of tangency between the ellipse and the tendon (at point C for the blue tendon) as a function of α. For the ellipse, no closed form expression of the arc length CB exists, we thus proceed by numerical integration.

Let us consider the E-module of Fig. 2. The plots of the tendon lengths l 1 and l 2 (resp. of their derivatives dl1 dα , dl2 dα , d 2 l1 dα 2 , d 2 l2 dα 2 ) are shown in Fig. 3, top left (resp. top right and bottom left). The coefficient C is calculated using Eq. ( 8) and its plot is shown in Fig. 3, bottom right. It turns out that C is positive in the range -0.70 rad < α < 0.70 rad. This means that coactivation is possible within this range. We call this range coactivation range.

Design parameters of the E-module

We first study the effect of the ellipse shape on the coactivation range. We fix b and the attachment points of the tendons as in Fig. 2 and we investigate several values of a, namely, a = 0.03 m, a = 0.045 m (as in Fig. 2), a = 0.06 m (i.e. a circle) and a = 0.075 m. For each case, C is plotted against α in Fig. 4. When a = 0.03 m and a = 0.045 m, coactivation around α = 0 is possible and the coactivation range is similar for these two values. However, coactivation is not possible when a = 0.075. This means that the orientation of the ellipse axes plays a central role: the long axis must be vertical at α = 0 to have coactivation. However, the length of the semi-axis has little influence on the coactivation range. We also notice the special case a = b (circle) for which C = 0, as expected.

A second study is the effect of the direction of the antagonistic tendons. Considering the symmetric E-module of Fig. 2, the lateral distance of point A x A is varied from 0 to 0.08 m, and the corresponding of C(α) is plotted in Fig. 5. It appears that for coactivation to exist, x A must be lower than a certain value. In fact, we have observed that this value is the length of the horizontal semi-axis but this result needs to be proved. In other words, the limit is when the two tendons are vertical at α = 0. Besides, decreasing x A does not change the range of coactivation. In conclusion, the choice of the tendon base points also affects coactivation.

Conclusion

The ability to modulate joint stiffness is an important property in collaborative robotics. To move safely with low energy consumption, it is desirable to provide low stiffness. In contrast, it can be necessary to increase stiffness by coactivation when needed, such as, e.g., during process tasks. In this study, we have proposed a new way to design a rotating joint with variable stiffness via the E-module. This new design can have applications in the design of variable stiffness SEA joints in robotics and for studying biological joints. Interesting avenues of study include studying non-symmetrical pulleys, eccentric or moving rotation axis.

Fig. 1 .

 1 Fig. 1. Two possible ways to build a rotating joint actuated by antagonistic tendons: a P-module (left) and a X-module (right)

1 Fig. 2 .

 12 Fig.2. A E-module is a rotating joint actuated by antagonistic tendons attached to an elliptical pulley.

Fig. 3 .

 3 Fig. 3. Plot of tendon length (top left) and of their successive derivatives (top right, bottom left). Bottom right: plot of coefficient C showing the coactivation range.

Fig. 4 .

 4 Fig. 4. Influence of the ellipse shape on coactivation range for a E-module.

Fig. 5 .

 5 Fig. 5. Influence of the location of tendon base points on coactivation for a E-module.


Emmanuel Nauer

Jean Lieber

Mathieu D'aquin

Lazy Adaptation Knowledge Learning based on Frequent Closed Itemsets

Keywords: adaptation knowledge learning, lazy learning, closed itemset extraction, case-based reasoning

This paper focuses on lazy adaptation knowledge learning (LAKL) using frequent closed itemset extraction. This approach differs from eager adaptation knowledge learning (EAKL) by the number of cases used in the learning process and by the moment at which the process is triggered. Where EAKL aims to compute adaptation knowledge once on the whole case base with the idea of solving every future target problem, LAKL computes adaptation knowledge on a subset of cases close to the target problem when a new problem has to be solved. The paper presents experiments on generated datasets from Boolean functions and on a real-world dataset, studying especially how the size of the case base used impacts performance. The results show that LAKL outperforms EAKL in precision and correct answer rate and that it is therefore better not to use the whole case base for adaptation knowledge learning.

Introduction

Case-based reasoning (CBR [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF]) aims at reusing past experience, represented by cases, and case adaptation plays an important part in many CBR applications. Adaptation often relies on the use of adaptation knowledge (AK), hence the usefulness of an AK learning (AKL) process. For example, AKL has been shown useful to improve the results of Taaable, a cooking system that adapts cooking recipes [START_REF] Cordier | Taaable: a Case-Based System for personalized Cooking[END_REF]. AK can take many forms. In this paper, it is assumed to be given by a set of adaptation rules.

If adaptation rules can be extracted in a general context (that is, by exploiting the cases of the whole case base), it appears that the rules extracted from a focused set of cases provide better results. In Taaable, preliminary work showed this interest in proposing an AKL suited to a given recipe (e.g., an apple tart recipe) by computing adaptation rules from recipes of the same type (e.g., fruit tart recipes) [START_REF] Gaillard | Adaptation knowledge discovery for cooking using closed itemset extraction[END_REF]. However, this approach, which focuses on a subset of recipes, computes adaptation rules a priori without considering the target problem. This paper addresses adaptation knowledge discovery and its application for adaptation with respect to the target problem, by considering the cases close to the target problem as input data for learning of adaptation rules. This work follows the idea of [START_REF] Badra | Opportunistic Adaptation Knowledge Discovery[END_REF] in which knowledge acquisition is triggered opportunistically at the time of problem solving. However, if such an approach has already been used, a comparative evaluation between exploiting the whole case base or a focused subset of it has, to the best of our knowledge, never been studied. This paper addresses this issue, in the context of a Boolean representation of cases, with the AKL process being based on the extraction of frequent closed itemset (FCI) variations between pairs of cases to compute adaptation rules, as in [START_REF] Gillard | Improving Adaptation Knowledge Discovery by Exploiting Negative Cases: First Experiment in a Boolean Setting[END_REF][START_REF] Lieber | Adaptation knowledge discovery using positive and negative cases[END_REF] using only positive cases.

These two ways of using learning, either as an offline process or as a process done at problem solving time, are respectively called eager and lazy learning [START_REF] Aha | Lazy learning[END_REF]. It can be noted that the whole CBR process can be likened to lazy learning. Indeed, one can consider that retrieving k cases nearest to the target problem and learning a solution from them matches closely the case-based problem-solving process. Now, what is studied in this paper, is lazy learning for adaptation, not for the whole CBR process and the supervised learning performed here is not on cases but on variations between cases. The objective of this paper is to study lazy adaptation learning and compare it with the performance of eager adaptation learning. This study shows that, on the tested datasets, lazy learning outperforms eager learning in an AKL process.

Section 2 recalls some general notions about CBR, AKL and the technique for extracting FCIs. Section 3 presents the approach used for AKL in a classical (i.e. eager AKL, or EAKL) way: this reuses some previous work with a little-yet significant-improvement. Section 4 presents lazy AKL (LAKL): from a general viewpoint and the way it is applied using FCI extraction. EAKL and LAKL are evaluated and compared in Section 5. Section 6 concludes and points out some future work.

Preliminaries

This section first introduces the main notions and notations related to CBR. Then it describes the principles of adaptation knowledge learning (AKL). Finally, it presents the notions related to the extraction of frequent closed itemsets (FCIs).

Case-based reasoning: notions, notations, and assumptions

Let P and S be two sets. A problem (resp., a solution) is an element of P (resp., of S). The existence of a binary relation with the semantics "has for solution" is assumed, although it is not completely known to the CBR system. Moreover, in this article it is assumed that this relation is functional (every problem has exactly one correct solution). Let f be the function from P to S such that y = f(x) if y is the solution of x. A case is a pair (x, y) ∈ P × S where y = f(x).

A CBR system on (P, S, f) is built with a knowledge base KB = (CB, DK, RK, AK) where CB, the case base, is a finite set of cases, DK is the domain knowledge, RK is the retrieval knowledge (in this work, RK = dist, a distance function on P), and AK is the adaptation knowledge often represented by a set of adaptation rules.

A CBR system in (P, S, f) aims to associate to a query problem x tgt a y tgt ∈ S, denoted by y tgt = f cbr (x tgt ). The function f cbr is intended to be an approximation of f. It is built using the following functions:

-The retrieval function, with the profile retrieval : x tgt → (x s , y s ) ∈ CB; -The adaptation function, with the profile adaptation : ((x s , y s ), x tgt ) → y tgt ∈ S; it is usually based on DK and AK. ((x s , y s ), x tgt ) is an adaptation problem.

Thus, f cbr (x tgt ) = adaptation(retrieval(x tgt ), x tgt ).

Adaptation principle using adaptation rules. Generally speaking, an adaptation rule ar is a function that maps an adaptation problem ((x s , y s ), x tgt ) ∈ CB × P into a y tgt ∈ S ∪ {failure}. If y tgt ̸ = failure then it is proposed as a solution to x tgt , by adaptation of (x s , y s ) according to ar. The adaptation consists in selecting a set ApplicableAR of applicable adaptation rules, i.e. for each ar ∈ ApplicableAR, ar((x s , y s ), x tgt ) ̸ = failure (the number of selected adaptation rules and the way they are selected depends on the approach and is presented further in the article). Then, the multiset of solutions proposed by the ar ∈ ApplicableAR is combined (e.g. by a majority vote) in order to propose a solution y tgt to x tgt . One way to represent an adaptation rule is by an ordered pair (∆x, ∆y) where ∆x is a problem variation and ∆y is a solution variation. Intuitively, a problem variation is the representation of changes in a problem knowing that this notion depends on the way the problems are represented (and this is similar for solutions): this idea is clarified in Section 3.

Given an adaptation rule ar = (∆x, ∆y) and an adaptation problem ((x s , y s ), x tgt ), ar((x s , y s ), x tgt ) is computed according to the following principle:

-The variation ∆x s,tgt from x s to x tgt is computed. -If ∆x s,tgt does not match exactly ∆x then the value failure is returned (the adaptation rule is not applicable to this adaptation problem). -Else, from y s and ∆y, a solution y tgt is computed, such that the variation ∆x s,tgt from y s to y tgt matches ∆y, and, if such a y tgt exists, it is returned (else the process returns failure).

Adaptation knowledge learning

Adaptation based on adaptation rules requires the acquisition of rules that can be done thanks to a learning process. In [START_REF] Hanney | Learning adaptation rules from a case-base[END_REF], an approach to adaptation knowledge learning (AKL) is presented that is based on the case base. The intuition is that, given (x i , y i ), (x j , y j ) ∈ CB, one can consider ((x i , y i ), x j ) as an adaptation problem-(x i , y i ) is the case to be adapted and x j is the target problem-and y j is a solution to this adaptation problem. Therefore, each pair of distinct source cases can be used as an example for a supervised learning process. This idea has been successfully applied to CBR in many studies (e.g. [START_REF] Craw | Learning adaptation knowledge to improve case-based reasoning[END_REF][START_REF] Jalali | Learning and applying adaptation rules for categorical features: An ensemble approach[END_REF][START_REF] D'aquin | Case base mining for adaptation knowledge acquisition[END_REF]). More precisely, the idea is to consider, for a pair of distinct source cases ((x i , y i ), (x j , y j )), the problem variation ∆x ij from x i to x j and the solution variation ∆y ij from y i to y j . Then, the supervised learning system provides a model that maps a problem variation ∆x into a solution variation ∆y. This model may be of different natures, for example, it can be a neural network (see e.g. [START_REF] D'aquin | A Factorial Study of Neural Network Learning from Differences for Regression[END_REF]). In this article, the learning technique used is frequent closed itemset extraction, in the continuation of previous studies (see e.g. [START_REF] Lieber | Adaptation knowledge discovery using positive and negative cases[END_REF]).

Frequent Closed Itemset extraction

Itemset extraction is a collection of data mining methods to extract regularities from data, by aggregating object items that appear together. Like formal concept analysis, itemset extraction algorithms start from a formal context K, defined by K = (G, M, I), where G is a set of objects, M is a set of items, and I is the relation on G × M stating that an object is described by an item [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF].

An itemset I is a set of items, and the support of I, supp(I), is the number of objects of the formal context that have all the items of I. I is frequent, with respect to a threshold τ supp , whenever supp(I) ≥ τ supp . I is closed if there does not exist a proper superset J of I (I ⊊ J) with the same support.

Given an itemset I ⊆ M with at least two items, an association rule R generated from I is any pair (U, V ) of nonempty itemsets such that

I = U ∪ V and U ∩ V = ∅. Such a rule is denoted by U → V . The support of R is the support of I and the confidence of R is conf(R) = supp(U ∪V )
supp(U ) . The confidence of R can also be defined as the conditional probability of an object having the items of V knowing that it has the items of U (given a uniform probability distribution on G).

EAKL based on FCI Extraction

In previous studies, AKL based on FCI extraction has already been studied as an offline process, that is, as an eager AKL [START_REF] Gillard | Improving Adaptation Knowledge Discovery by Exploiting Negative Cases: First Experiment in a Boolean Setting[END_REF][START_REF] Lieber | Adaptation knowledge discovery using positive and negative cases[END_REF]. This section recalls the principles of this approach with an improvement in the way the set of adaptation rules is selected at adaptation time.

This (eager) learning process, as mentioned in Section 2.2, uses the following training set:

TS = ∆x ij , ∆y ij | (x i , y i ), (x j , y j ) ∈ CB, (x i , y i ) ̸ = (x j , y j ) (1)
This involves the issue of the representation of problem and solution variations. It is assumed that a problem can either be represented by a set of attribute-value pairs with Boolean values or that it can be translated into such a formalism,1 which is consistent with the choice of FCI as a learning technique.

The attribute-value pair (a, 1) is simply written a and the attribute-value pair (a, 0) is simply written a. It is also assumed that problems are fully described: for a problem x and for each attribute a in V P , either a ∈ x or a ∈ x. Now, let us consider the following examples of problems:

x i = {a, b, c, d}

x j = {a, b, c, d}
The variation ∆x ij is represented by a set of expressions of the form a v where a ∈ V P and v is a variation symbol. The variation symbols considered here are = = =0, = = =1, + + +, and ---, meaning respectively "staying false", "staying true", "changing from false to true", and "changing from true to false". Therefore,

∆x ij = {a = = =1 , b = = =0 , c + + + , d ---}
Solution variations are represented similarly, on the set of attributes V S (and it is assumed that

V P ∩ V S = ∅).
Then, the EAKL process builds a formal context K = (G, M, I) from TS as follows:

-G is the set of elements of TS, indexed by the pairs (i, j),

thus |G| = |CB| × (|CB| -1); -M is the set of a v for a ∈ V P ∪ V S and v ∈ {= = =0, = = =1, + + +, ---} thus |M| = 4 |V P ∪ V S |; -I is
defined by the fact that the object indexed by (i, j) is described by the item a v meaning that a v ∈ ∆x ij ∪ ∆y ij .

After this, FCI extraction is run on K and the results is filtered in order to keep only the itemsets I having at least one item a v where a ∈ V P and one item A w where A ∈ V S (with v and w, two variation symbols). Each FCI I is then translated into an adaptation rule. For example, I = {a = = =1 , c + + + , A ---} is translated into ar = (∆x, ∆y) with ∆x = {a = = =1 , c + + + } and ∆y = {A ---}.

In this way, a set AK of NER adaptation rules is built and can be used at adaptation time, where NER is a parameter that sets the number of rules to be extracted, selecting the ones with greater support. The value for NER has to be chosen carefully, since an insufficient number of rules can cause the adaptation process to fail, while a large number of rules would make the process too time-consuming. Given an adaptation problem ((x s , y s ), x tgt ), ∆x s,tgt is computed and, for each adaptation rule (∆x, ∆y) the application process follows the principle given in Section 2.1 knowing that -∆x s,tgt matches ∆x if ∆x ⊆ ∆x s,tgt (and the same definition of matching holds for solutions); -∆y is said to be applicable to y s if there exists a y ∈ S such that the variation from y s to y matches ∆y (for example, {A + + + } is applicable on {A, B} but not on {A, B}); -If ∆y is not applicable to y s , then the application of the rule fails, else, for each A ∈ V S :

• If no A w occurs in ∆y then the value of attribute A in y s is reused for y tgt (if A ∈ y s then A ∈ y tgt else A ∈ y tgt ); • Else, the value of attribute A in y tgt is computed according to its value in y s and the variation w (e.g. if y s = {A} and w = ---then y tgt = {A}).

For the purpose of selecting adaptation rules among AK, it is useful to assign them a score used to rank adaptation rules in order of preference: the higher the score, the more preferred the adaptation rule. In the previous work, this score was simply the support of the itemset on which the adaptation rule is built. In this work, the notion of confidence of an adaptation rule has been used and has led to better results. We therefore switched to the use of confidence in our experiments. This confidence is defined as follows. First, four new variation symbols 1•, •1, 0• and •0 are introduced: 1• (resp. •1) corresponds to a variation from a true value to any value (resp. from any value to a true value), and similarly for the two other variations. Therefore, {A = = =1 } can be rewritten as {A 1• , A •1 }, {A + + + } can be rewritten as {A 0• , A •1 }, etc. This decomposition is useful to separate the information on y s (in the premise of the rule) from the information on y tgt (in its conclusion). Let (∆x, ∆y) be an adaptation rule built from an itemset I, where the A w for A ∈ V S are replaced with A w1 and A w2 ,

w 1 ∈ {1•, 0•} and w 2 ∈ {•1, •0}.
Then, the confidence of the adaptation rule (∆x, ∆y) is the confidence of the association rule U → V where V is the subset of I with variation symbols •1 and •0, and

U = I \ V . For example, if ∆x = {a = = =1 , b ---, c = = =0 } and ∆y = {A ---} then U = {a = = =1 , b ---, c = = =0 , A 1• } and V = {A •0 }.

LAKL based on FCI Extraction

LAKL consists in learning AK at adaptation time, that is, when an adaptation problem ((x s , y s ), x tgt ) is known. Therefore, unlike EAKL, LAKL can rely on knowledge of the retrieved case (x s , y s ) and the target problem x tgt . The general principle of LAKL is presented in Section 4.1 and its application using FCI extraction, in Section 4.2. In Section 4.3, it is explained that an approach to CBR developed in previous studies can be considered as a particular approach to LAKL.

Main principles

The main idea of LAKL is to restrict the training set TS defined by (1) by taking into account the adaptation problem: given two distinct source cases (x i , y i ) and (x j , y j ), the pair (∆x ij , ∆y ij ) is filtered out from the training set if these source cases do not satisfy conditions related to (x s , y s ) and x tgt . Generally speaking, three types of conditions are considered below in an informal way.

(x i , x j ≃ x tgt ) The problems x i and x j are "around" x tgt : the way adaptation works for the target problem is assumed to be better represented in its neighborhood then elsewhere in the problem space;

(∆x ij ≃ ∆x s,tgt ) The variation between the two source problems x i and x j are similar to the variation between the problem x s of the retrieved case and the target problem. (y i ≃ y tgt ) The variation ∆y ij from y i to y j has to be "compatible" with the value of the solution of the retrieved problem so that rules that are not applicable to y s are avoided; this condition adds a constraint on the "left part" of ∆y ij , that is, y i .

Our approach to applying LAKL, as described in the following, consists in specifying and implementing these conditions.

Lazy adaptation knowledge learning based on FCI extraction

The principles of LAKL have been implemented for an AKL based on FCI extraction.

Condition (x i , x j ≃ x tgt ) is implemented simply by choosing the k nearest cases to the target problem that are different from the case (x s , y s ). This can be done at retrieval time: k + 1 nearest cases are retrieved, the nearest one being the retrieved case, and the k other ones being selected for building the training set. Different values of k can be considered. In our experiments, those values have been chosen to correspond to different percentages of the size of the case base, starting with 10% |CB|.

One effect of applying this condition (x i , x j ≃ x tgt ) on the training set is to reduce the number of objects in the formal context K = (G, M, I), which goes from |CB| (|CB| -1) to k(k -1), hence a reduction of about (|CB| /k) 2 of its size. For example, if k = 10% |CB|, this leads to a reduction by a factor 100.

In this version, the condition (∆x ij ≃ ∆x s,tgt ) has not been implemented for practical reasons and this is left for future work.

Finally, the condition (y i ≃ y tgt ) is implemented in this work considering that y i and y tgt must be equal. This can be justified as follows, in the situation where there is only one solution attribute A (as in the experiments). Considering an (x i , y i ) such that y i ̸ = y s would lead to the extraction of FCIs that are interpreted as inapplicable rules. For example, y i = {A} would lead to extract adaptation rules containing either A + + + or A = = =0 . Therefore, if y i ̸ = y s then y s = {A} and no such adaptation rule can be applied on y s , hence not contributing to the learning effort. This condition further reduces the number of objects in the formal context. Moreover, the set of items M is also reduced since items not related to any object are not included in the formal context: in the example above, the items A + + + and A = = =0 are excluded from M (and this reduces the computing time).

Analogical extrapolation seen as a LAKL process

In [START_REF] Lieber | Making the best of cases by approximation, interpolation and extrapolation[END_REF], the analogical extrapolation approach to CBR is described. It is based on analogical proportions, i. -Selection of all pairs ((x a , y a ), (x b , y b )) ∈ CB2 such that x a :x b ::x s :x tgt ; -For each of these pairs, solve the analogical equation y a :y b ::y c :y in y and,

if it has at least one solution, add this solution to a multiset Y of candidate solutions (initially, Y is empty); -The solution y tgt is based on a vote on Y (this vote is weighted in [START_REF] Lieber | Improving analogical extrapolation using case pair competence[END_REF] using the notions of support and confidence of a case pair, that are similar to the notions of support and confidence of an FCI).

This analogical extrapolation adaptation process can be reformulated as an adaptation following a LAKL process with the training set corresponding to some implementation choices for the conditions introduced in 4.1. More precisely, conditions (x i , x j ≃ x tgt ) and (y i ≃ y tgt ) are not considered and condition (∆x ij ≃ ∆x s,tgt ) is defined as follows:

-The set of variation symbols is reduced to {---, + + +} (i.e. items of the forms a = = =1 and a = = =0 are discarded 2 ); -The matching between the two problem variations is implemented as an equality: ∆x ij = ∆x s,tgt .

Evaluation

The objective of the evaluation is to study the behavior of LAKL compared to EAKL, in representative types of Boolean functions as well as on a "real life" dataset, in order to determine which approach achieves greater performance and under which circumstances. The experimental results are presented and discussed.

Experiment setting

In the experiment, problems have 16 Boolean features and S, 1. The function f : P → S is generated randomly using the following generators that are based on two normal forms, with the purpose of generating a wide variety of functions:

DNF f is generated in a disjunctive normal form, i.e., f(x) is a disjunction of n conj conjunctions of literals, for example f(x) = (x 1 ∧ ¬x 7 ) ∨ (¬x 3 ∧ x 7 ∨ x 8 ) ∨ x 4 .
The value of n conj is randomly chosen uniformly in {3, 4, 5}. Each conjunction is generated on the basis of two parameters, p + > 0 and p -> 0, with p + + p -< 1: each variable x i occurs in the disjunct in a positive (resp. negative) literal with a probability p + (resp., p -). In the experiment, the values p + = p -= 0.1 were chosen.

Pol is the same as DNF, except that the disjunctions (∨) are replaced with exclusive or's (⊕), thus giving a polynomial normal form. The only different parameter is p -= 0 (only positive literals occur in polynomial normal form).

A case base CB of a given size (|CB| ∈ {128, 256, 512}) is generated randomly in the following way: each source case (x, y) is generated by randomly choosing x in P with a uniform distribution and y = f(x).

Let ntp be the number of target problems posed to the system, na be the number of (correct or incorrect) answers (ntpna is the number of target problems for which the system fails to propose a solution), and nca be the number of correct answers (i.e., number of problems for which the predicted answer is the correct answer). For each method, the following scores are computed:

The precision prec is the average of the ratios nca na .

The answer rate arate is the average of the ratios na ntp .

The correct answer rate car is the average of the ratios nca ntp .

The average is calculated by solving 100 problems for each of 20 generated functions, for each function generator. For the sake of reproducibility, the code for this experiment is available at https://tinyurl.com/EAKLvsLAKLTests with the detailed results of this paper (generated functions and details of the evaluation).

Results

Comparing EAKL and LAKL requires a lot of attention because some parameters involved in the evaluation may have an impact on the interpretation of the results. For example, one of the parameters is the number of rules to be learned using FCI extraction, and it is not fair to use the same number of rules for EAKL, in which rules are extracted once to solve all coming target problems, as for LAKL, in which a focused rule extraction is done for each target problem. The number of extracted rules has a direct and important impact on the answer rate for EAKL, since it is less likely to find applicable rules for a given target problem if that number is too small. The impact of the number of rules is lower for LAKL, and the same number of rules will more likely lead to a higher answer rate in LAKL than in EAKL. Table 1 illustrates this with precision and answer rate scores for EAKL with a number of rules extracted ranging from 100 to 2, 400. It can be seen that an answer rate of 100% is almost always achieved if a sufficient number of rules is used. This sufficient number of rules depends on the size of the case base, sometimes requiring more than 1, 000 rules. However, a (close to perfect) score of 99% is reached in all cases from 400 rules.

The precision also increases with the number of rules until a plateau is reached. Therefore, using more rules (e.g. 2, 000 for DNF functions with a size of case base of 256) improves precision and, thanks to an almost perfect answer rate, the correct answer rate. It appears that precision could have a higher score with fewer rules (e.g., 100 rules for DNF functions using 512 cases), but in this case, at the cost of a lower answer rate. The standard deviation is also stable with lower values when the number of rules is high. Based on these observations, the tests for comparing EAKL and LAKL (presented in the next section) have been performed with the extraction and use at most 2,400 rules for EAKL and 1,000 for LAKL, with the idea of having the best possible results for EAKL (best answer rate, best precision and therefore best correct answer rate) and of studying how LAKL performs in comparison.

EAKL vs. LAKL results. Table 2 shows the precision, standard deviation, answer rate, and correct answer rate obtained with the nearest neighbor adaptation (NN, i.e., simply reusing the solution of the most similar problem) used as baseline, EAKL, and LAKL. The left part of the table presents the results for NN and EAKL while the right part presents the LAKL results with various LAKL always provides better scores for all measures regardless of the percentage of cases used for learning, except for the limits (10% and 100% of CB). The best precision, as well as the best correct answer rate (because the answer rate is at its maximum), is obtained with a size of the subpart of the case base between 20% and 50% of CB. Fig. 1 shows the correct answer rate according to the percentage of CB used. This measure is relatively stable, except for the extreme percentage: 10% and 100% for which the adaptation rules are of lower quality. Thus, an unexpected result is that it is better not to use the whole case base to learn adaptation rules.

Computation aspects. The experiments use Coron, a software platform that implements efficient algorithms for symbolic data mining and, especially, FCI computation [START_REF] Szathmary | CORON: A Framework for Levelwise Itemset Mining Algorithms[END_REF].

LAKL provides an important advantage for large case bases. Indeed, computing frequent closed itemset is a process with a high level of complexity, especially with the use of case variations. For 1024 cases, the formal context is lower or equal to) the class's mean result (10.42). One run consists of a random selection in CB and the evaluation of 100 random target problems that are not in CB, using 1, 000 rules for EAKL as well as for LAKL, as this leads to high answer rates. 20 runs were performed for |CB| = 128 and |CB| = 256. Table 3 presents the results for NN, EAKL and LAKL depending on various percentages of CB used for adaptation rule learning. EAKL and LAKL with 100% give the same results because they both use the same number of rules and the same number of cases. The analysis of the results is similar to the experiment on Boolean functions: LAKL outperforms EAKL. In this particular experiment, when at most 60% of CB is used. The results are especially good for low percentages. For |CB| = 128 (resp. 256), the better result is when using 20% (resp. 10%) of CB, with an improvement of the correct answer rate of +4% (resp. +7%) compared to EAKL. Moreover, in this experiment, EAKL leads to results that are less satisfactory than those of NN, which is not the case with LAKL.

Conclusion

This paper addresses FCI-based adaptation rule learning using a lazy approach. The AKL is triggered at problem-solving time to compute adaptation rules using cases close to the target problem, rather than a priori and on the entire case base, with the idea of solving every target problem. The lazy approach has many advantages. Experiments on Boolean functions and on a real-world dataset show that the lazy approach (LAKL) outperforms the eager approach (EAKL) in precision and correct answer rate. Moreover, computing adaptation rules in a lazy process is demonstrably more scalable as it requires a fewer number of objects to be involved in the most complex step, namely FCI extraction.

A first direction of work is the study of various ways of implementing the conditions (x i , x j ≃ x tgt ), (∆x ij ≃ ∆x s,tgt ), and (y i ≃ y tgt ) that restricts the training set for LAKL. Two implementations have already been considered: the one studied in this article and the one corresponding to analogical extrapolation as a LAKL (cf. Section 4.3).

Another direction of work consists in studying LAKL with other assumptions on case representation. First, in some domains, cases cannot adequately be translated into sets of Boolean properties. This motivates the study of LAKL with other learning techniques, suited to other case representations (e.g. texts, logical formulas or complex objects). Second, the assumption of an a priori separation between the problem and solution parts in a case is not always acceptable: for instance, in Taaable, an apple pie recipe can be seen as a solution of many problems (e.g. "Recipe of dessert with apples?" or "Recipe of pie with fruits?"). On the contrary, the knowledge at problem-solving time of the query/target problem makes it possible to make this distinction. Therefore, LAKL can benefit from this knowledge whereas EAKL cannot: studying this in detail is a future work. For example, the confidence of an adaptation rule relies on this problem-solution distinction, and using this confidence is beneficial for AKL.

  e. quaternary relations denoted by a:b::c:d ("a is to b as c is to d") where a, b, c, and d are four objects of the same space. The analogical proportion on Booleans used in this article is defined by a:b::c:d if a = b and c = d, or a = c and b = d, and on tuples of Booleans by a:b::c:d if a p :b p ::c p :d p for each component p. Analogical extrapolation, at adaptation time, consists in the following steps:

+Fig. 1 .

 1 Fig. 1. Correct answer rate (y-axis) given a percentage (x-axis) of CB used for 1000 rules extraction (DNF at the left, Pol at the right).

Table 1 .

 1 Precision, standard deviation, answer rate, and correct answer rate (in %) for EAKL (100% of CB) with various numbers of extracted rules (NER) to solve the target problems.

	NER 100 200 300 400 500 600 700 800 1000 1200 1400 1600 1800 2000 2200 2400
							DNF
	128 prec 84 83 83 84 85 85 85 85 85 85 86 86 86 86 86 86
	σ	8 8	8 7 7 7 7 7	7	7	8	8	8	8	8	8
	arate 94 99 99 99 99 100 100 100 100 100 100 100 100 100 100 100
	car	79 82 83 84 84 85 85 85 85 85 86 86 86 86 86 86
	256 prec 87 87 87 88 88 89 89 89 89 89 89 89 89 90 90 90
	σ	9 9	9	8	8	7	8	7	7	7	7	7	6	6	6	6
	arate 95 99 99 99 99 99 99 99 99 100 100 100 100 100 100 100
	car	83 86 87 88 88 89 89 89 89 89 89 89 89 90 90 90
	512 prec 95 94 93 93 93 93 93 93 93 93 93 93 93 93 93 93
	σ	4 4	4	4	4	4	4 3	4	4	4	4	4	4	4	4
	arate 91 96 98 99 99 99 99 99 100 100 100 100 100 100 100 100
	car	87 90 91 92 93 93 93 93 93 93 93 93 93 93 93 93
							POL
	128 prec 74 75 75 75 74 74 74 74 74 74 74 74 74 74 74 74
	σ	15 14 15 15 15 16 16 16 16 16 17 17 17 17 17 17
	arate 96 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99
	car	71 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74
	256 prec 74 75 76 77 77 78 78 78 79 79 79 79 79 79 79 79
	σ	18 16 17 16 15 15 15 15 14 15 14 14 14 14 14 14
	arate 99 99 100 100 100 100 100 100 100 100 100 100 100 100 100 100
	car	73 75 76 77 77 78 78 78 79 79 79 79 79 79 79 79
	512 prec 79 79 80 81 81 81 81 82 82 82 82 82 83 83 83 83
	σ	20 18 17 16 16 16 16 15 14 14 14 14 14 14 14 14
	arate 91 98 99 99 99 99 99 100 100 100 100 100 100 100 100 100
	car	72 78 80 80 80 81 81 82 82 82 82 82 83 83 83 83

This translation may involve some loss of information. For example, a numerical feature is typically translated into several Boolean attributes, each of them consisting in the membership to an interval.

This is related to the following result. Letδx ij = {a v ∈ ∆x ij | v ∈ {---, + + +}}.Then, it can be shown that x a :x b ::x s :x tgt iff δx ab = δx s tgt .

sizes of subparts of the case base used for learning. For EAKL, all measures vary according to the number of rules used in the adaptation process; the detailed EAKL results of Table 1 are presented through an interval in the column titled EAKL. The interval is defined by the minimum and maximum scores, using between 100 and 2,400 rules. For example, in the first line, for |CB| = 128, the precision of the eager approach varies between 83% and 86% depending on the number of rules used in the adaptation process. The first remark is that EAKL always outperforms the NN approach. This is not a surprise since previous studies (e.g. [START_REF] Gillard | Improving Adaptation Knowledge Discovery by Exploiting Negative Cases: First Experiment in a Boolean Setting[END_REF]) already showed this. Also unsurprisingly, the larger the case base size, the better the results of EAKL in precision and correct answer rate (up to +4% and +6% for both measures, respectively, for DNF and Pol functions when |CB| = 512).

The comparison of EAKL and LAKL shows that LAKL performs better with some variations in the DNF and Pol functions. For DNF, it can be observed that of 1, 024 × 1, 023 pairs of cases, so over one million objects. Extracting up to 2, 500 rules requires to compute closed itemsets with a low support (around 1% of the number of objects). Our experiment has shown that this computation is not possible on a computer without at least 32Gb of memory available for this process with Coron. Therefore, computing the adaptation rules on a smaller formal context (e.g. with |CB| = 1024, taking 10% produces a formal context of around 10, 000 objects, instead of 1, 000, 000) is an interesting option for a large case base. This remark holds also for the execution time, for which the smaller the set of cases used to compute adaptation rules, the shorter the computational time. For example, for the DNF functions, with |CB| = 512 and 2, 500 rules extracted for EAKL, the mean computation time is 41.78 seconds. This can be compared to the time increases from 8.66 seconds using 20% of CB to 11.6 for 50%, up to 31.2 seconds for 90%, when getting 1, 000 rules with LAKL. However, even if LAKL is more scalable, FCI extraction being done at adaptation time, and therefore for every target problem, its computational time cannot be claimed to be advantageous.

Experiment on a real-world dataset

To further validate the benefits of LAKL, we conducted an experiment on a real-world dataset. This dataset, taken from the UCI Machine Learning Repository, describes students and their results in a final exam. 3 In fact, there are 2 datasets, but we only use the one with the final result of the math exam. The raw attributes that are binary, multivalued, or even numeric have been transformed to fit our Boolean representation formalism. The details of the transformation are described at https://tinyurl.com/EAKLvsLAKLTests.

In this experiment, problems have 29 Boolean features and S, 1. The dataset contains 395 records, which produces 391 cases after removing duplicates. The distribution of the solutions of these 391 cases is 207 (resp. 184) results over (resp.

3 https://archive.ics.uci.edu/ml/datasets/student+performance