Marine Le Boulch

Emad K Ahmed

Adelina Rogowska-Wrzesinska

Martín A Baraibar

Bertrand Friguet
email: bertrand.friguet@upmc.fr

Proteome oxidative carbonylation during oxidative stress-induced premature senescence of WI-38 human fibroblasts

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

ABSTRACT

Accumulation of oxidatively damaged proteins is a hallmark of cellular and organismal ageing, and is also a phenotypic feature shared by both replicative senescence and stressinduced premature senescence of human fibroblasts. Moreover, proteins that are building up as oxidized (i.e. the "Oxi-proteome") during ageing and age-related diseases represent a restricted set of cellular proteins, indicating that certain proteins are more prone to oxidative carbonylation and subsequent intracellular accumulation. The occurrence of specific carbonylated proteins upon oxidative stress induced premature senescence of WI-38 human fibroblasts and their follow-up identification have been addressed in this study. Indeed, it was expected that the identification of these proteins would give insights into the mechanisms by which oxidatively damaged proteins could affect cellular function. Among these proteins, some are belonging to the cytoskeleton while others are mainly involved in protein quality control and/or biosynthesis as well as in redox and energy metabolism, the impairment of which has been previously associated with cellular ageing. Interestingly, the majority of these carbonylated proteins were found to belong to functional interaction networks pointing to signalling pathways that have been implicated in the oxidative stress response and subsequent premature senescence.

KEY WORDS

Protein oxidation; stress-induced premature senescence (SIPS); fibroblasts; oxidative stress; proteomics; ageing.

HIGHLIGHTS

> Oxidative carbonylation proteomics have been performed in fibroblasts after SIPS > A restricted set of increasingly carbonylated proteins have been identified > Several proteins belonging to the cytoskeleton have been found > Other proteins are involved in protein maintenance and intermediate metabolism > Data mining reveals potentially affected stress response-related signalling pathways ABBREVIATIONS SIPS: stress-induced premature senescence; HDFs: human diploid fibroblasts; SIPS fibroblasts: stress-induced premature senescent fibroblasts; t-BHP: tert-butyl hydroperoxide; ROS: reactive oxygen species; IEF: isoelectrofocusing; DTT: dithiothreitol; RMI: relative modification index; MS: mass spectrometry; PBS: phosphate buffered saline; DNPH: dinitrophenylhydrazine; BSA: bovine serum albumin.

INTRODUCTION

Premature senescence can be induced in proliferating cells under conditions of increased oxidative stress (Toussaint et al., 2002a). Several experimental conditions have been used such as exposure of human diploid fibroblasts (HDFs) to subcytotoxic doses of stressing agents: hydrogen peroxide, tert-butyl hydroperoxide (t-BHP), ethanol, UV irradiation, strong electromagnetic fields, hyperoxia, etc… (Toussaint et al., 2000a). Within few days after exposure to the subcytotoxic stressor, HDFs become post-mitotic, display a typical senescent morphology and express several biomarkers of replicative senescence [START_REF] Dumont | Induction of replicative senescence biomarkers by sublethal oxidative stresses in normal human fibroblast[END_REF].

Hence, this senescent state occurring after subcytotoxic stresses was named stress-induced premature senescence (SIPS) (Toussaint et al., 2000b). Since the cell cycle is irreversibly arrested in stress-induced senescent cells, even if they are stimulated by various growth factors, it is thought that SIPS results in a cellular impairment that prevents cells from replicating. The recent demonstration that senescent cells are found in aged tissues and are important contributors to the ageing process in vivo and the development of age-associated pathologies, has led to an increased interest in those alternative senescence pathways that were previously evidenced only in vitro [START_REF] Baker | Clearance of p16Ink4a-positive senescent cells delays ageing-associated disorders[END_REF][START_REF] Campisi | Cell senescence: role in aging and age-related diseases[END_REF][START_REF] Adnot | Telomere Dysfunction and Cell Senescence in Chronic Lung Diseases: Therapeutic Potential[END_REF]. Cells undergoing replicative senescence and those undergoing SIPS share common features but these two pathways for reaching senescence are different mostly because of the time at which these features are expressed. In replicative senescence, it has been proposed that the pathway is programmed and switched on when telomere attrition reaches a critical point, while for SIPS this is rather a response to a given stress. However, SIPS and replicative senescence are common in that the DNA damage response machineries are activated, either due to damage at non-telomere specific sites as signal in SIPS or at specific telomere ends as activating signal in replicative senescence. Using both transcriptomic and proteomic approaches, it was shown that SIPS and replicative senescence exhibit distinct gene and protein expression levels, even if they share similar phenotypic features [START_REF] Dierick | Transcriptome and proteome analysis in human senescent fibroblasts and fibroblasts undergoing premature senescence induced by repeated sublethal stresses[END_REF][START_REF] Dierick | Identification of 30 protein species involved in replicative senescence and stress-induced premature senescence[END_REF].

Among the phenotypic features shared by both SIPS and replicative senescence of HDFs is the accumulation of oxidatively damaged proteins [START_REF] Debacq-Chainiaux | Repeated exposure of human skin fibroblasts to UVB at subcytotoxic level triggers premature senescence through the TGF-1 signaling pathway[END_REF][START_REF] Chondrogianni | Central role of the proteasome in senescence and survival of human fibroblasts: induction of a senescence-like phenotype upon its inhibition and resistance to stress upon its activation[END_REF], which also represents a hallmark of cellular and organismal ageing [START_REF] Levine | Oxidative modification of proteins during aging[END_REF][START_REF] Nystrom | Role of oxidative carbonylation in protein quality control and senescence[END_REF]. Furthermore, it has been proposed that the accumulation of damaged proteins during ageing is due to the dysregulation of both redox and protein homeostasis, resulting from an increased production of reactive oxygen species (ROS) and a decreased efficacy of cellular protein maintenance systems, such as the proteasome, that are responsible for their removal or repair [START_REF] Friguet | Oxidized protein degradation and repair in ageing and oxidative stress[END_REF]Baraibar and Friguet, 2012;[START_REF] Chondrogianni | Protein damage, repair and proteolysis[END_REF]. Oxidative damage to the cellular proteome, leading to the formation of carbonylated proteins derives from the direct oxidation of several amino acids side chains and also through protein adducts formation with lipid peroxidation products and dicarbonyl glycating compounds. Protein oxidative carbonylation is one of the most prominent protein damage since it is irreversible and it is related to a loss of function or a gain of toxic function of the targeted proteins [START_REF] Grune | Decreased proteolysis caused by protein aggregates, inclusion bodies, plaques, lipofuscin, ceroid, and 'aggresomes' during oxidative stress, aging, and disease[END_REF][START_REF] Stadtman | Protein oxidation and aging[END_REF][START_REF] Nowotny | Accumulation of modified proteins and aggregate formation in aging[END_REF]. In addition, targeting of cellular proteins by carbonylation in ageing, cellular senescence and oxidative stress appears to be a rather selective process and recent studies have evidenced that the "Oxi-proteome" (i.e. the proteins that are building up as carbonylated) during ageing and age-related diseases is restricted to specific cellular proteins (Baraibar et al., 2012;Baraibar and Friguet, 2013). Factors underlying such selectivity are not completely understood and the relative abundance of proteins does not seem to be a necessary condition for a protein to be carbonylated. These factors have been proposed to rather include the presence of a transition metal-binding site that allow metal-catalysed oxidation, the abundance of amino acids susceptible to metal-catalysed oxidation, the rate of protein turnover, the protein conformation and its location in the proximity of ROS and other toxic compounds generation sites. As previously described for human fibroblasts and myoblasts undergoing replicative senescence [START_REF] Ahmed | Protein modification and replicative senescence of WI-38 human embryonic fibroblasts[END_REF][START_REF] Baraibar | Impaired energy metabolism of senescent muscle satellite cells is associated with oxidative modifications of glycolytic enzymes[END_REF], the identification of the "Oxi-proteome" of fibroblasts undergoing stress-induced premature senescence is expected to give insights into the mechanisms by which these oxidatively damaged proteins could affect cellular function and may also help to understand why these damaged proteins are building up in these prematurely senescent cells. In this study, we have investigated the occurrence of carbonylated proteins upon premature senescence of WI-38 fibroblasts 2 hours after oxidative stress and after a 30 days recovery period and we have identified in both cases proteins that belongs to the cytoskeleton and proteins that are mainly involved in protein quality control and/or biosynthesis as well as in redox and energy metabolism, the impairment of which has been previously associated with cellular ageing.

Interestingly, these carbonylated proteins belongs to functional interaction networks pointing to signalling pathways as TGF-1, NTRK1, NFB, Pkc, P38 MAPK, Akt, AMPK and ERK that are known to play a role either in the oxidative stress response and/or in premature cellular senescence (Toussaint et al., 2002b;[START_REF] Bernard | Involvement of Rel/nuclear factor-kappaB transcription factors in keratinocyte senescence[END_REF][START_REF] Maruyama | Stress-activated MAP kinase cascades in cellular senescence[END_REF][START_REF] Salminen | Emerging role of NF-κB signaling in the induction of senescence-associated secretory phenotype (SASP)[END_REF][START_REF] Boilan | Role of p38MAPK and oxidative stress in copper-induced senescence[END_REF].

MATERIAL AND METHODS

WI-38 culture conditions and exposure to oxidative stress

Human embryonic fibroblasts WI-38 were grown in Dulbecco's minimal essential medium (1 g/L glucose) supplemented with 10 % foetal calf serum, 100 U/ml penicillin, 100 μg/ml streptomycin and 2 mM L-glutamine. Cultures were kept in an incubator at 37 °C and 5 % CO 2 -containing atmosphere. Subconfluent cultures were obtained by seeding 5x10 5 cells/75 cm 2 culture flasks and early passages (Cumulative population doublings < 25) WI-38 cultures were used for exposure to oxidative stress. Cells were exposed to increasing amount of H 2 O 2 for 2 hours at 37°C in a serum free media, then the cells were washed and given fresh culture medium. The sublethal dose of H 2 O 2 was assessed by counting the number of total and nonviable cells using Trypan blue staining after a 24 hours recovery period. For the induction of SIPS the H 2 O 2 concentration was set at the sublethal concentration of 500 M and the 2 hours exposure to H 2 O 2 was repeated two times at one week interval.

β-galactosidase staining

Staining for β-galactosidase activity was performed as described by [START_REF] Dimri | A biomarker that identifies senescent human cells in culture and in skin in vivo[END_REF].

Briefly, WI-38 cells were washed with PBS, fixed in 0.2% glutaraldehyde / 2% formaldehyde for 5 minutes at room temperature, and washed again with PBS. Cells were then stained at 37°C (in the absence of CO 2 ) with fresh SA-β-gal staining solution (150 mM NaCl, 2 mM MgCl 2 , 5 mM potassium ferricyanide, 5 mM potassium ferrocyanide, and 40 mM citric acid/sodium phosphate, pH 6.0) containing 1 mg/ml 5-bromo-4-chloro-3-indolyl-β-Dgalactoside. Staining was maximal after 15-20 h of incubation. 400 cells were counted each time and the number of positive cells was calculated as a percentage of the whole cells.

Proteasome peptidase activities

Peptidase activities of the proteasome were assayed with 20 μg of protein lysate in 25mM Tris-HCl, pH 7.5 at 37°C using fluorogenic peptides, Succinyl-Leu-Leu-Val-Tyraminomethylcoumarin at 12.5 μM for the chymotrypsin-like activity and Nbenzyloxycarbonyl-Leu-Leu-Glu-naphthylamide at 150 μM for the peptidylglutamyl-peptide hydrolase activity in a final volume of 200 μl as previously described [START_REF] Bulteau | Age-related alterations of proteasome structure and function in aging epidermis[END_REF].

Enzymatic kinetics were conducted in a temperature-controlled microplate fluorimetric reader (Fluostar Galaxy, bMG, Stuttgart, Germany). Proteasome activities were determined as the difference between total activity and the remaining activity of the crude lysate in the presence of 20 μM of proteasome inhibitor N-Cbz-Leu-Leu-Leucinal (MG132). All measurements were repeated a minimum of three times and results are expressed as mean ± standard deviation (SD). Data were analysed by two-way ANOVA followed by Bonferroni's post hoc test and significance was set at P<0.05.

Two-dimensional gel electrophoresis

Sample preparation-WI-38 fibroblasts were washed once with PBS, scrapped into 5 ml PBS, pelleted by centrifugation for 5 min at 1000g and then kept at -20 °C until analysis. Cell pellets were suspended in lysis buffer (2% CHAPS, 0.1 M DTT in 50 mM Tris-HCl, pH 7.4 and complete protease inhibitor cocktail). Cells were lysed by sonication for 4 x 5 sec using a Branson Sonifier 150 followed by incubation with benzonase (500 U/ml) for 90 min at 4 °C with agitation. Cell lysates were obtained after centrifugation at 15000g for 10 min at 4°C and protein concentration was determined by the method of Bradford (Bio-Rad protein assay, Marnes La Coquette, France).

Isoelectrofocusing (IEF) -Aliquots of 150-300 μg of proteins were diluted in 250 μl rehydration solution (7 M urea, 2 M thiourea, 4 % 3-[(3-cholamidopropyl) dimethylammonio]-1-propanesulfonate (CHAPS), 65 mM DTT, 2 % IPG buffer (v/v). The protein samples were loaded into the IPG strips 3-10 NL (13 cm), by in gel rehydration at room temperature overnight. IEF was performed as previously described [START_REF] Ahmed | Protein modification and replicative senescence of WI-38 human embryonic fibroblasts[END_REF]. After IEF, the IPG strips were stored at -80 °C until used in the second dimension.

In-strip derivatisation of protein-bound carbonyls, SDS-PAGE and 2D-OxyBlot-After IEF

the IPG strips 3-10 NL were incubated at room temperature in 10 ml of 10 mM DNPH / 2 M HCl for 20 min with agitation. Strips were neutralized with 2 M Tris-base containing 30% glycerol for 10 min and this step is repeated one time for 30 min. IPG strips were equilibrated for 15 min in 10 ml equilibration buffer (6 M urea, 2% SDS, 30% glycerol, 1% DTT in 50 mM Tris-HCl, pH 8.8) and then for 15 min in equilibration buffer containing traces of bromophenol blue and 3% iodoacetamide instead of DTT. The strips were placed on 12% polyacrylamide gels according to [START_REF] Laemmli | Cleavage of structural proteins during the assembly of the head of bacteriophage T4[END_REF] and electrophoresis was carried out using the cooling Protean II system (BioRad, Marnes La Coquette, France). After 2D electrophoresis the proteins are blotted onto a nitrocellulose membrane for 3 h at a fixed voltage of 100 V. The blots were then incubated for 2 h at room temperature in blocking buffer (PBS supplemented with 1% BSA and 0.1% Tween 20) and detection of carbonyl groups was performed with the OxyBlot TM oxidized protein detection kit according to the manufacturer's protocol.

Protein staining and image analysis

The 2D separated protein spots were visualized with colloidal blue staining and the stained gels and films were digitized with UMAX UTA-100 scanner (GE Healthcare, Saclay, France). The spot detection and quantification were done with the Image Master 2D Platinium 7 software (GE Healthcare, Saclay, France) and the data were expressed as spot % volume in pixels.

In-gel digestion, mass spectrometry and database searches

Spots of interest were manually excised from gels and proteins were digested with trypsin as described previously [START_REF] Ahmed | Protein modification and replicative senescence of WI-38 human embryonic fibroblasts[END_REF]. Peptide mass spectra were acquired in positive reflector mode on a 4800 Plus MALDI TOF/TOF™ Analyser (Applied Biosystems, Foster City, CA, USA) using 20 kV of acceleration voltage. MS and MS/MS peak lists were combined into search files and used to search SwissProt databases using the Mascot search engine (Matrix Science Ltd, London, UK). Mascot protein scores greater than 56 are significant at p <0.05.

Metabolic Analyses.

Intracellular metabolites profiling analysis was performed by Metabolon, Inc. as previously described [START_REF] Reitman | Profiling the effects of isocitrate dehydrogenase 1 and 2 mutations on the cellular metabolome[END_REF]. Cellular pellets (10 6 cells) from six different batches from control WI-38 fibroblasts and four different batches of SIPS WI-38 fibroblasts were prepared and accessioned into the Metabolon LIMS system.

Ultrahigh performance liquid chromatography/Mass Spectroscopy (UPLC/MS/MS).

The LC/MS portion of the platform was based on a Waters ACQUITY ultra-performance liquid chromatography (UPLC) and a Thermo-Finnigan linear trap quadrupole (LTQ) mass spectrometer. Sample extracts were dried and then reconstituted in acidic or basic LCcompatible solvents, each of which contained 8 or more injection standards at fixed concentrations to ensure injection and chromatographic consistency.

Gas chromatography/Mass Spectroscopy (GC/MS). The samples destined for GC/MS analysis were re-dried under vacuum desiccation for a minimum of 24h prior to being derivatised under dried nitrogen using bistrimethyl-silyl-triflouroacetamide (BSTFA). Samples were analysed on a Thermo-Finnigan Trace DSQ fast-scanning single-quadrupole mass spectrometer using electron impact ionization.

Data extraction and compound identification. Raw data was extracted, peak-identified and QC processed using Metabolon's hardware and software [START_REF] Dehaven | Organization of GC/MS and LC/MS metabolomics data into chemical libraries[END_REF]). Welch's two-sample t-test was used to identify biochemicals that differed significantly between experimental groups.

Functional pathways analysis

Functional pathway and network analyses were generated using the Ingenuity pathway analysis software (version 2.0, Ingenuity Systems, Mountain view, CA). Ingenuity pathway analysis identified those canonical pathways, biological processes and gene interactions networks that were most significant for the carbonylated proteins identified in WI-38 fibroblasts upon oxidative stress-induced premature senescence. Each protein designation was mapped in the Ingenuity Pathways Knowledge Base.

RESULTS

Determination of the subcytotoxic dose of H 2 O 2 and induction of premature senescence of WI-38 human fibroblasts:

WI-38 human fibroblasts were grown as described in Material and Methods until they have reached 80% confluence and they were exposed to increasing amount of H 2 O 2 for 2 hours at 37°C in a serum-free media, then the cells were washed and given fresh culture medium. The subcytotoxic dose of H 2 O 2 was assessed by counting the number of total and non-viable cells after a 24 hours recovery period. As shown in Figure 1A, cell mortality was evident at concentrations of H 2 O 2 higher than 500 M. Hence, for the induction of SIPS the H 2 O 2 concentration was set at 500 M and the 2 hours exposure to H 2 O 2 was repeated two times at one week interval. The occurrence of oxidized proteins was monitored in cellular protein lysates using the protein carbonyl Oxyblot TM assay as described in Material and Methods at different recovery periods after oxidative stresses. As shown in Figure 1B, the level of oxidized protein is increased during the first hours after stress and then comes back to basal for about one week before increasing again after two weeks. Since the proteasome is the main proteolytic system that has been implicated in the removal of oxidized proteins, proteasome peptidases activities were also measured in cellular protein extracts as described in Material and Methods at different recovery periods following oxidative stresses. Interestingly, both chymotrypsin-like and peptidyl-glutamylpeptide hydrolase activities were decreased during the first hours after stress and then came back to normal after one week and stayed around this level during the following three weeks (Figure 1C). Finally, the senescent status of the cell culture was evaluated qualitatively by the characteristic cellular enlargement and flattening of the fibroblasts (Figure 1D) and quantitatively by the count of the -galactosidase positive cells and total cells (Figure 1E) as described in Material and Methods. At two hours after the oxidative stresses, around 80% of the cells were already positive for -galactosidase activity and almost 100% -galactosidase positive senescent cells were found after a thirty days recovery period.

Characterization of carbonylated proteins in WI-38 fibroblasts submitted to oxidative stresses and SIPS

SIPS was induced in WI-38 fibroblasts upon their exposure for 2 hours to a 500 M concentration of H 2 O 2 two times at one week interval. Cellular lysates were prepared from WI-38 fibroblasts that have not been treated with H 2 O 2 (i. e. control fibroblasts) and from H 2 O 2 twice treated WI-38 fibroblasts (i.e. SIPS fibroblasts) after a short recovery period of 2 hours and a long recovery period of 30 days, respectively. Proteins modified by carbonylation were analysed by a 2D gel-based proteomic approach as described in Material and Methods.

Two gels were prepared in parallel for each sample, the first one for the visualization of total proteins after Coomassie colloidal blue staining and the subsequent identification by MS analysis and the second one for blotting against specific polyclonal anti-DNP antibodies to visualize the carbonylated proteins as described in Material and Methods. Such an experiment is presented in Figure 2 and the protein spots were quantified over gels and blots using the Image Master 2D software from GE Healthcare. Protein spots were quantified as % volume (%V) which is a normalized value that remains relatively independent of irrelevant variations between images. Because of possible variations in protein expression levels, for each spot a relative modification index (RMI) was calculated, which is the ratio of quantification value of protein spot on membrane to its corresponding value on gel. These RMI values were further normalized as RMI ratios (RMI SIPS / RMI Control ). Several spots were found on the immunoblots which are increasingly carbonylated by at least 30% (RMI ratio ≥ 1.3) in SIPS WI-38 fibroblasts after either a short recovery period of 2 hours (26 spots for SIPS 2h) and a long recovery period of 30 days (19 spots for SIPS d30) when compared with control ones, respectively (Figure 3). For most of these protein spots, their expression level variations were within 30% increase or decrease, the highest increased and decreased expression levels being 1.8 fold for spot 1 and 2.2 fold for spot 21, respectively.

Identification of carbonylated proteins in WI-38 fibroblasts submitted to oxidative stresses and SIPS

The increasingly carbonylated protein spots were excised from their respective Coomassie colloidal blue stained gels, subjected to tryptic digestion and analysed by MALDI-TOF/TOF-MS for protein identification as described in Material and Methods. All spots were successfully identified and the proteins listed on Tables 1 and2 have been assigned a significant Mascot score. In either situation of short and long recovery periods, the 27 identified proteins were belonging to either the cytoskeleton or were proteins that are mainly involved in protein quality control and/or biosynthesis as well as in redox and energy metabolism, the impairment of which has been previously associated with cellular ageing.

The subcellular location of the carbonylated proteins was mainly cytosolic (21 out of 27 which is almost 80%) with few other proteins belonging to either plasma membrane (3 proteins out of 27), endoplasmic reticulum (2 proteins out of 27) and nucleus (1 protein out of 27). Interestingly, 6 proteins were found increasingly carbonylated for both situations of short or long recovery periods (Figure 4A). Since, among those modified proteins were represented glucose-6-phosphate dehydrogenase and enolase that are both involved in carbohydrate metabolism, the pentose phosphate and the glycolytic pathways respectively, as well as protein disulfide isomerase A3, a redox chaperone involved in the refolding of disulfide containing proteins, the level of several carbohydrates and redox metabolites were monitored two weeks after SIPS as described in Material and Methods. None of the assayed glycolytic and Krebs cycle intermediate metabolites in SIPS fibroblasts showed significant variation as compared with control fibroblasts but for isobar: ribulose 5-phosphate, xylulose 5-phosphate which was increased by 2.2 fold for pentose metabolism (Figure 4B) while the total level of NADP was decreased by 2.6 fold (Figure 4C) and the level of coenzyme A was decreased by 4 fold (Figure 4D). Among redox metabolites, both cysteine-gluthatione disulfide and methionine sulfoxide were increased by 1.6 and 2.6 fold, respectively (Figures 4E &4F) while no significant variation of reduced and oxidized glutathione was observed.

Functional network integration of SIPS associated carbonylated proteins

The carbonylated proteins identified in SIPS WI-38 fibroblasts after either a short recovery period of 2 hours (20 proteins for SIPS 2h) or a long recovery period of 30 days (13 proteins for SIPS d30) were analysed for network integration using the Ingenuity Pathway Analysis TM Software. Indeed, such information would be of interest to point out metabolic and/or signalling pathways that may be impacted by the loss of protein function and/or regulation that has been generally associated to protein oxidative carbonylation. The proteins identified for SIPS-2h were found to belong to two different networks (Figures 5A &5B), one being centered on NTRK1, a pro-survival kinase that has been implicated in MAP kinase kinase activity, and TGF-1 (Figure 5A), a secreted polypeptide member of the transforming growth factor beta superfamily of cytokines that performs many cellular functions, including the control of cell growth, cell proliferation, cell differentiation and apoptosis. Interestingly, TGF-1 has also been causally involved in the induction of SIPS upon H 2 O 2 treatment and UVB irradiation of human fibroblasts [START_REF] Frippiat | Subcytotoxic H2O2 stress triggers a release of transforming growth factor-beta 1, which induces biomarkers of cellular senescence of human diploid fibroblasts[END_REF][START_REF] Debacq-Chainiaux | Repeated exposure of human skin fibroblasts to UVB at subcytotoxic level triggers premature senescence through the TGF-1 signaling pathway[END_REF].

The second network obtained with increasingly carbonylated proteins for SIPS-2h was more complex (Figure 5B) and included such signalling proteins as NFB, P38 MAPK, ERK, Akt, Pkc and AMPK. For the carbonylated proteins identified in SIPS WI-38 fibroblasts after a long recovery period of 30 days (13 proteins), only one network was obtained with Histone H3 and most of the signalling proteins reported above for the second network of increasingly carbonylated proteins for SIPS-2h: P38 MAPK, ERK, Pkc and AMPK (Figure 5C).

DISCUSSION

In this study, we have investigated the occurrence of protein carbonylation in WI-38 fibroblasts upon SIPS, 2 hours following H 2 O 2 induced oxidative stress and after a 30 days recovery period. In addition, we have successfully identified the "Oxi-proteome" (i.e. the restricted set of increasingly carbonylated proteins) of these fibroblasts undergoing stressinduced premature senescence. Indeed, increased protein oxidative damage has been clearly associated to both cellular and organismal ageing and accumulation of oxidatively damaged proteins has been also reported in HDFs upon both replicative and SIPS [START_REF] Chondrogianni | Central role of the proteasome in senescence and survival of human fibroblasts: induction of a senescence-like phenotype upon its inhibition and resistance to stress upon its activation[END_REF][START_REF] Debacq-Chainiaux | Repeated exposure of human skin fibroblasts to UVB at subcytotoxic level triggers premature senescence through the TGF-1 signaling pathway[END_REF]. We have previously identified proteins targeted by such modifications as carbonylation, conjugation by the lipid peroxidation product 4hydroxynonenal and formation of advanced glycated end-products in human fibroblasts and myoblasts upon replicative senescence [START_REF] Ahmed | Protein modification and replicative senescence of WI-38 human embryonic fibroblasts[END_REF][START_REF] Baraibar | Impaired energy metabolism of senescent muscle satellite cells is associated with oxidative modifications of glycolytic enzymes[END_REF]. As for the current study, these studies were carried out using 2D gel-based proteomic approach combined with immunodetection of these oxidatively modified proteins since this methodology gives the possibility to globally analyse the pattern of modified proteins in cells and tissues [START_REF] Møller | Protein carbonylation and metal-catalyzed protein oxidation in a cellular perspective[END_REF][START_REF] Rogowska-Wrzesinska | 2D gels still have a niche in proteomics[END_REF]. For protein carbonylation, highly sensitive fluorescent hydrazide probes have been set up since and were found to match the sensitivity of immunodetection of the protein carbonyldinitrophenylhydrazone derivatives. These probes represent powerful tools for the quantitative assessment of the "Oxi-proteome" within the complex mixture of proteins found in any protein containing biological sample [START_REF] Tamarit | Analysis of oxidative stress-induced protein carbonylation using fluorescent hydrazides[END_REF]Baraibar et al., 2013;[START_REF] Rogowska-Wrzesinska | Analysis of protein carbonylation--pitfalls and promise in commonly used methods[END_REF].

Concerning fibroblasts and myoblasts undergoing replicative senescence, restricted sub-sets of oxidatively modified proteins were previously found with some overlapping proteins and some cell-type specific proteins, suggesting that these latter proteins may differently affect cellular function during replicative senescence. Among them were proteins belonging to the cytoskeleton, proteins involved in energy, carbohydrate and redox metabolism as well as proteins involved in protein maintenance [START_REF] Ahmed | Protein modification and replicative senescence of WI-38 human embryonic fibroblasts[END_REF][START_REF] Baraibar | Impaired energy metabolism of senescent muscle satellite cells is associated with oxidative modifications of glycolytic enzymes[END_REF]. Interestingly, although the method used to prepare cell lysates and the protein extraction protocol were basically the same, an important number of modified mitochondrial proteins were found in senescent fibroblasts while most of the modified proteins found in senescent myoblasts were cytosolic. In this study, only carbonylated proteins were analysed in SIPS fibroblasts and they were mainly cytosolic and also either belonging to the cytoskeleton, involved in redox and energy metabolism or involved in protein maintenance (Tables 1 &2 and Figure 4A). Interestingly, cytoskeleton, redox and energy metabolism as well as protein maintenance have been all reported to be impaired during cellular ageing. Such carbonylated proteins accumulating in SIPS that were already found for replicative senescence of both fibroblasts and myoblasts include: Vimentin, Glucose-6-phosphate dehydrogenase and Heat shock cognate 71 kDa protein. Other carbonylated proteins that were previously identified in either myoblasts exposed to H 2 O 2 induced oxidative stress or senescent myoblasts include:

Enolase, Protein disulfide-isomerase A3, Glyceraldehyde-3-phosphate dehydrogenase, Pyruvate kinase, Heat shock cognate 71 kDa protein, Glucose-6-phosphate dehydrogenase and Annexin A2. Finally, such proteins as Vimentin, Tubulin, Actin, Glyceraldehyde-3phosphate dehydrogenase, Enolase, Pyruvate kinase, Protein disulfide-isomerase, Catalase and Heat shock cognate 71 kDa protein have also been identified as increasingly modified in different models of ageing and age-related diseases (Baraibar et al., 2012;Baraibar and Friguet, 2013).

A similarity in the proteins targeted by oxidation emerges, to a certain extent, from these comparisons and suggests that specific cellular functions might be affected by the buildup of this restricted set of oxidatively modified proteins due to their impaired functionality and/or altered regulation. This assumption is supported in SIPS fibroblasts by changes in the levels of such metabolites as ribulose 5-phosphate + xylulose 5-phosphate (Figure 4B). Both metabolites are part of the pentose-phosphate pathway which is providing intracellular reducing power through reduced NADPH production and is critically dependent on Glucose-6-phosphate dehydrogenase integrity. In addition, the overall level of NADP, which is a cosubstrate of both Glucose-6-phosphate dehydrogenase and 6-phosphogluconate dehydrogenase was decreased in SIPS fibroblasts (Figure 4C), arguing for a decreased efficiency of the pentose-phosphate pathway. Since, NADP is mostly produced through the phosphorylation of NAD [START_REF] Love | NAD kinase controls animal NADP biosynthesis and is modulated via evolutionarily divergent calmodulindependent mechanisms[END_REF], the decreased level of NADP may be related with previously reported alterations in NAD + metabolism in replicatively senescent human fibroblasts [START_REF] James | Replicatively senescent human fibroblasts reveal a distinct intracellular metabolic profile with alterations in NAD+ and nicotinamide metabolism[END_REF]. However, no significant change was found in NAD + and NADH levels in SIPS fibroblasts while elevated levels of NADP were reported in replicatively senescent human fibroblasts [START_REF] James | Replicatively senescent human fibroblasts reveal a distinct intracellular metabolic profile with alterations in NAD+ and nicotinamide metabolism[END_REF]. Another important metabolite for energy metabolism is Coenzyme A, the level of which was decreased by 4 fold in SIPS fibroblasts. This may results in a negative impact on both the transfer of fatty acids from the cytoplasm to the mitochondria for their -oxidation and on the delivery of the acetyl group to the citric acid cycle to be oxidized for mitochondrial energy production.

Oxidatively modified proteins build-up that occurs during ageing and cellular senescence is believed to result, at least in part, from the increase of reactive oxygen species and other toxic compounds coming from both cellular metabolism and external factors.

Experimental evidence has also indicated that failure of protein maintenance systems such as the proteasome, can also be a major contributor to the age-associated accumulation of damaged proteins [START_REF] Chondrogianni | Central role of the proteasome in senescence and survival of human fibroblasts: induction of a senescence-like phenotype upon its inhibition and resistance to stress upon its activation[END_REF][START_REF] Petropoulos | Protein maintenance in aging and replicative senescence: a role for the peptide methionine sulfoxide reductases[END_REF]Baraibar and Friguet, 2012) that is believed to participate to the age-related decline in cellular function.

Although the proteasome peptidase activities were transiently decreased after oxidative stress, they were almost restored in the senescent cells after one week up to four weeks recovery periods while a build-up of carbonylated proteins is still observed. These results are in line with those obtained upon UVB induced premature senescence of human fibroblasts and keratinocytes for which no proteasome inhibition was reported [START_REF] Debacq-Chainiaux | Repeated exposure of human skin fibroblasts to UVB at subcytotoxic level triggers premature senescence through the TGF-1 signaling pathway[END_REF][START_REF] Boilan | Repeated exposures to UVB induce differentiation rather than senescence of human keratinocytes lacking p16(INK-4A)[END_REF]. Hence, persistent redox dysregulation, as evidenced by an increase in such metabolites as methionine sulfoxide and cysteine-glutathione (Figure 4E & 4F) which represents two compounds formed under oxidative stress conditions, is most likely implicated in the accumulation of carbonylated proteins for H 2 O 2 induced premature senescence of WI-38 fibroblasts. Moreover, the increased load of carbonylated heat shock cognate 71 kDa and heat shock protein 90 kDa  chaperone proteins may also contribute to an impaired removal of damaged or abnormal proteins by chaperone-mediated autophagy [START_REF] Cuervo | Chaperone-mediated autophagy: roles in disease and aging[END_REF] and by CHIP ubiquitin ligase mediated degradation by the proteasome [START_REF] Murata | CHIP: a quality-control E3 ligase collaborating with molecular chaperones[END_REF][START_REF] Sisoula | CHIP E3 ligase regulates mammalian senescence by modulating the levels of oxidized proteins[END_REF].

Finally, a network analysis using Ingenuity Pathways Analysis TM software was performed for carbonylated proteins that are accumulating in SIPS fibroblasts to obtain further insights into the cellular pathways that might be affected by protein carbonylation which is generally associated to a loss of protein function and/or a gain of toxic function. The 20 proteins identified for SIPS 2h (i. e. 2 hours following H 2 O 2 induced oxidative stress) were grouped in two different networks (Figures 5A &5B). The first network (Figure 5A) is based on 4 proteins that are no longer accumulating after the 30 days recovery period and is centered on NTRK1 (neurotrophic tyrosine receptor kinase 1) and TGF-1 (the transforming growth factor beta 1). NTRK1, also known as tropomyosin receptor kinase A, is a prosurvival kinase that has been implicated in the activation of downstream signalling cascades via PI3K, RAS/MAPK/ERK, and PLC- that induces cell proliferation, differentiation, apoptosis, and survival of neurons and other cells types [START_REF] Khotskaya | Targeting TRK family proteins in cancer[END_REF]. TGF-1 has been implicated in many cellular functions, including the control of cell growth, cell proliferation, cell differentiation, apoptosis and in particular in SIPS and ageing (Toussaint et al., 2002b). In particular, TGF-1 activation has been shown to drive the entrance of HDFs in premature senescence following oxidative stress [START_REF] Frippiat | Subcytotoxic H2O2 stress triggers a release of transforming growth factor-beta 1, which induces biomarkers of cellular senescence of human diploid fibroblasts[END_REF][START_REF] Debacq-Chainiaux | Repeated exposure of human skin fibroblasts to UVB at subcytotoxic level triggers premature senescence through the TGF-1 signaling pathway[END_REF]. The second network is based on 16 proteins among which 6 of them are also accumulating after a 30 days recovery period. This network includes such signalling proteins as NFκB, P38 MAPK, ERK, Akt, Pkc and AMPK among which P38 MAPK, ERK, Pkc and AMPK are also part of the network obtained for the 13 carbonylated proteins identified in SIPS WI-38 fibroblasts after a long recovery period of 30 days (Figure 5C). Interestingly, all these signalling proteins have been previously implicated in the oxidative stress response and subsequent stress-induced premature senescence (Toussaint et al., 2002b;[START_REF] Bernard | Involvement of Rel/nuclear factor-kappaB transcription factors in keratinocyte senescence[END_REF][START_REF] Maruyama | Stress-activated MAP kinase cascades in cellular senescence[END_REF][START_REF] Salminen | Emerging role of NF-κB signaling in the induction of senescence-associated secretory phenotype (SASP)[END_REF][START_REF] Boilan | Role of p38MAPK and oxidative stress in copper-induced senescence[END_REF] which suggests that the "Oxi-proteome" might interfere with functional connections within these relevant signalling pathways. Interestingly, a decreased activation of the pro-survival Akt and ERK kinases has been previously reported for aged HDFs as compared to HDFs from young individuals upon exposure to hydrogen peroxide (Gurjula et al., 2005). Taken together, these results suggest that the cellular senescence-associated "Oxi-proteome" (i. e. the restricted set of cellular proteins that are building up as oxidized proteins) may not only contribute to the senescent phenotype by affecting certain metabolic pathways, such as those involved in energy and redox metabolism (Baraibar and Friguet, 2013;[START_REF] Baraibar | Impaired energy metabolism of senescent muscle satellite cells is associated with oxidative modifications of glycolytic enzymes[END_REF], but may also participate to the establishment and maintenance of the senescent state by impacting on specific intracellular signalling pathways. Hence, improved removal of oxidized proteins and/or increased protection of the proteome against oxidation would be expected to help preventing cellular senescence and consequently slowing-down the pro-aging effects of senescent cells at the tissue and organ levels. After the second dimension, gels were either stained with colloidal Coomassie brilliant blue (right panels) or electro-transferred onto nitrocellulose membranes for subsequent immunodetection of carbonylated protein spots and their follow-up quantification and matching using Image Master 2D Platinium 7 software as described in Material and Methods (left panels). This experiment was performed in quadruplicate. Networks were obtained using Ingenuity Pathway for carbonylated proteins in SIPS WI-38 fibroblasts after a short recovery period of 2 hours (SIPS 2h / networks A and B) and a long recovery period of 30 days (SIPS d30 / network C). Proteins in red correspond to some of the proteins identified by MALDI-TOF/TOF-MS after Oxyblot TM . Proteins in green were not identified as carbonylated in this analysis but they represent central nodes associated with the regulation of some of the proteins identified. Information about the analysis of biological functions and pathways as well as network interactions is available at the Ingenuity pathway analysis website. A line denotes binding of proteins, whereas a line with an arrow denotes "acts on". A dotted line denotes an indirect interaction FOOTNOTES TO TABLES Table 1:

FIGURE LEGENDS Figure 1 :

 LEGENDS1 FIGURE LEGENDS

Figure 2 :

 2 Figure 2: 2D-Oxyblot analysis of SIPS WI-38 after H 2 O 2 oxidative stresses. 150 g of total proteins of each cellular lysates (Control, SIPS 2h and SIPS d30) were first

Figure 3 :

 3 Figure 3: Coomassie blue staining of the 2D preparative gels.Numbers and positions of selected spots located in the master gels (fold change ≥ 1.3 for increasingly carbonylated spots), for their identification by MALDI-TOF/TOF-MS as described in Material and Methods.

Figure 4 :

 4 Figure 4: Carbonylated proteins and measurement of selected metabolites in SIPS WI-38 fibroblasts.Venn diagram (A) depicting the distribution of proteins increasingly carbonylated proteins in SIPS WI-38 fibroblasts after a short recovery period of 2 hours (SIPS 2h) and a long recovery period of 30 days (SIPS d30). Altered metabolites in SIPS fibroblasts (FIS) versus control young fibroblasts (FY) were monitored as described in Material and Methods and are related to the pentose phosphate pathway (B and C), to mitochondria based energy metabolism (D) and to oxidative stress conditions (E and F).

Figure 5 :

 5 Figure 5: Cellular pathway analysis.

  Carbonylated proteins in stress-induced premature senescent WI-38 fibroblasts (SIPS 2h). Spots of interest were identified by MS as described in Material and Methods. Protein spot no (a) refer to numbered spots on Figure 3. For each spot, different parameters clarifying protein identification by MS are indicated [(accession number (b), Ingenuity Pathway Analysis symbol (c) mass (d), mascot score (e), % sequence coverage (f)]. (g) RMI ratio represents the Relative Modification Index Ratio and (h) means that the modified protein was only detected in SIPS 2h samples. Table 2 : Carbonylated proteins in stress-induced premature senescent WI-38 fibroblasts (SIPS d30). Spots of interest were identified by MS as described in Material and Methods. Protein spot no (a) refer to numbered spots on Figure 3. For each spot, different parameters clarifying protein identification by MS are indicated [(accession number (b), Ingenuity Pathway Analysis symbol (c) mass (d), mascot score (e), % sequence coverage (f)].(g) RMI ratio represents the Relative Modification Index Ratio and (h) means that the modified protein was only detected in SIPS d30 samples.

Table 1 Carbonylated proteins in stress-induced premature senescent WI-38 fibroblasts (SIPS 2h)

 1 Spots of interest were identified by MS as described in Material and Methods. Protein spot no (a) refer to numbered spots on Figure 3. For each spot, different parameters clarifying protein identification by MS are indicated [(accession number (b), Ingenuity Pathway Analysis symbol (c) mass (d), mascot score (e), % sequence coverage (f)].(g) RMI ratio represents the Relative Modification Index Ratio and (h) means that the modified protein was only detected in SIPS 2h samples.

	Protein	Identified protein name	Swiss-Prot	IPA	Protein	Mascot	Sequence	Identified	RMI
	Spot no a		accession no b	Symbol c	mass d	score e	coverage	protein function	Ratio g
							(%) f
	1	Annexin A2	ANXA2_HUMAN ANXA2	38580	677	31	Membrane	4.2
								scaffolding
	2	Vimentin	VIME_HUMAN	VIM	53619	853	42	Cytoskeletal	3.4
	3	Calumenin	CALU_HUMAN	CALU	37084	271	11	Calcium binding	5
	4	Vimentin	VIME_HUMAN	VIM	53619	1050	46	Cytoskeletal	1.3
	5	ATP synthase subunit beta,	ATPB_HUMAN	ATP5B	56525	798	56	Energy	1.7
		mitochondrial						metabolism
	6	Rab GDP dissociation inhibitor	GDIB_HUMAN	GDI2	50631	540	43	Signal	3.1
		beta						transduction
	7	Elongation factor 1-gamma	EF1G_HUMAN	EEF1G	50087	497	26	Protein	4.7
								biosynthesis
	8	Alpha-enolase	ENOA_HUMAN	ENO1	47139	643	37	Energy	8.6
								metabolism
	9	Alpha-enolase	ENOA_HUMAN	ENO1	47139	383	47	Energy	h
								metabolism
	10	Protein disulfide-isomerase A1 PDIA1_HUMAN	PDIA1	57081	573	43	Redox chaperone 2.2
	11	Protein disulfide-isomerase A3 PDIA3_HUMAN	PDIA3	56747	703	44	Redox chaperone 3.5
	12	Protein disulfide-isomerase A3 PDIA3_HUMAN	PDIA3	56747	1170	38	Redox chaperone 4.8
	13	Heterogeneous nuclear	HNRH1_HUMAN HNRNPH1 49198	676	43	RNA binding	1.6
		ribonucleoprotein H						protein
	14	Tryptophanyl-tRNA	SYWC_HUMAN	WARS	53132	484	24	Protein	1.8
		synthetase, cytoplasmic						biosynthesis
	15	Glucose-6-phosphate 1-	G6PD_HUMAN	G6PD	59219	573	35	Energy	3.3
		dehydrogenase						metabolism

Table 2 Carbonylated proteins in stress-induced premature senescent WI-38 fibroblasts (SIPS d30)

 2

	Protein	Identified protein name	Swiss-Prot	IPA	Protein	Mascot	Sequence	Identified	RMI
	Spot no a		accession no b	Symbol c	mass d	score e	coverage	protein function	Ratio g
							(%) f
	27	Tropomyosin alpha-3 chain	TPM3_RAT	TPM3	28989	233	16	Cytoskeletal	5.6
	28	Glyceraldehyde-3-phosphate						Energy
		dehydrogenase	G3P_HUMAN	GAPDH	36030	763	48	metabolism	2
	29	Actin, cytoplasmic 1	ACTB_HUMAN ACTB	41710	995	46	Cytoskeletal	10
	30	Vimentin	VIME_HUMAN VIM	53619	817	41	Cytoskeletal	1.7
	31	Vimentin	VIME_HUMAN VIM	53619	1050	46	Cytoskeletal	1.3
	32	Vimentin	VIME_HUMAN VIM	53619	969	63	Cytoskeletal	3.4
	33	Tubulin beta chain	TBB5_HUMAN	TUBB	49639	919	29	Cytoskeletal	1.7
	34	Vimentin	VIME_HUMAN VIM	53619	853	42	Cytoskeletal	2.9
	35							Energy
		Alpha-enolase	ENOA_HUMAN ENO1	47139	643	37	metabolism	7.8
	36	Protein disulfide-isomerase A3	PDIA3_HUMAN PDIA3	56747	703	44	Redox chaperone	2.3
	37	T-complex protein 1 subunit
		epsilon	TCPE_HUMAN	TCPE	59633	442	27	Chaperone	2.3
	38	Glucose-6-phosphate 1-						Energy
		dehydrogenase	G6PD_HUMAN G6PD	59219	573	35	metabolism	1.3
	39	Heat shock cognate 71 kDa
		protein	HSP7C_HUMAN HSPA8	70854	1080	36	Chaperone	h
	40	Heat shock cognate 71 kDa
		protein	HSP7C_HUMAN HSPA8	70854	849	33	Chaperone	h
	41	Annexin A6						Membrane
			ANXA6_HUMAN ANXA6	75826	757	37	scaffolding	h
	42	Annexin A6						Membrane
			ANXA6_HUMAN ANXA6	75826	528	43	scaffolding	h

ACKNOWLEDGMENTS

This paper is part of a special issue of Mechanisms of Ageing and Development on "Stress and senescence" dedicated to the memory of Dr Olivier Toussaint, University of Namur, Belgium. EKA was recipient of a fellowship from the Egyptian Ministry of Research and is currently lecturer at the Ain Shams University, Department of Biochemistry, Cairo, Egypt. MLB was appointed as technical associate in the EU Proteomage project and is currently project manager at Eukaÿs, Paris, France. The authors thank Mrs Marie-Paule Hamon for her help in operating the Ingenuity Pathway Analysis TM software. This work was supported by funds from MENRT and European 6 th Framework Program Grant Proteomage LSHM-CT-518230.


Panagiotis Charalampopoulos
email: [panagiotis.charalampopoulos@kcl.ac.uk

Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Costas S Iliopoulos
email: costas.iliopoulos@kcl.ac.uk

Tomasz Kociumaka
email: [kociumaka@mimuw.edu.pl

Solon P Pissis
email: solon.pissis]@kcl.ac.uk

Jakub Radoszewski

Wojciech Rytter
email: rytter@mimuw.edu.pl

Tomasz Waleń
email: walen]@mimuw.edu.pl

Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes

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

Introduction

A word is a sequence of letters from a given alphabet Σ. By Σ * we denote the set of all words over Σ. A word of the form U U , for some word U , is called a square. For a word W , a square factor is a factor of W which is a square. Enumeration of square factors in words is a well-studied topic, both from a combinatorial and from an algorithmic perspective. Obviously, a word of length n of may contain Θ(n 2 ) square factors (e.g. a n ), however, it is known that such a word contains only O(n) different square factors [START_REF] Fraenkel | How many squares can a string contain?[END_REF][START_REF] Ilie | A simple proof that a word of length n has at most 2n distinct squares[END_REF]; currently the best known upper bound is 11 6 n [START_REF] Deza | How many double squares can a string contain?[END_REF]. Moreover, all different square factors of a word can be listed in O(n) time using two different approaches [START_REF] Gusfield | Linear time algorithms for finding and representing all the tandem repeats in a string[END_REF][START_REF] Crochemore | Extracting powers and periods in a word from its runs structure[END_REF].

A partial word is a sequence of letters from Σ ∪ { ♦}, where ♦ denotes a hole, that is, a don't care symbol. Two symbols a, b ∈ Σ ∪ { ♦} are said to match (denoted as a ≈ b) if they are equal or one of them is a hole; note that this relation is not transitive. The relation of matching is extended in a natural way to partial words of the same length. A partial word U V is called a p-square if U ≈ V . We define the length of a p-square as |U |. Same as in the context of words, a p-square factor of a partial word W is a factor being a p-square; see [START_REF] Blanchet-Sadri | Squares and primitivity in partial words[END_REF][START_REF] Blanchet-Sadri | Computing primitivelyrooted squares and runs in partial words[END_REF]. Alongside [START_REF] Blanchet-Sadri | Squares and primitivity in partial words[END_REF][START_REF] Blanchet-Sadri | Counting distinct squares in partial words[END_REF][START_REF] Blanchet-Sadri | Computing primitivelyrooted squares and runs in partial words[END_REF], we define a full square as a square of a word and square subword of a partial word W as a full square that matches some p-square factor of W .

We introduce the notion of equivalence of p-square factors in partial words. By sq-val(U V ) let us denote the set of different full squares that match the partial word

U V : sq-val(U V ) = {XX : X ∈ Σ * , XX ≈ U V }. Then p-squares U V and U V are called equivalent if sq-val(U V ) = sq-val(U V ) (denoted as U V ≡ U V
). E.g., the following two sets are equivalence classes of p-squares: A = {aa ♦ ♦, ♦aa ♦, ♦ ♦aa, a ♦ ♦a} and B = {a ♦a ♦ ♦ ♦, ♦ ♦aa ♦ ♦, . . .}. Note that two psquare factors of a partial word W are equivalent in this sense iff they correspond to exactly the same sets of square subwords. Our work is devoted to enumeration of non-equivalent p-square factors of a partial word with a given number k of holes.

We say that W W is a general form of a square U V (see [START_REF] Blanchet-Sadri | Counting distinct squares in partial words[END_REF]), denoted as repr (U V ), if W W ≈ U V and sq-val(W W ) = sq-val(U V ) (in other words, W is the "most general" partial word that matches both U and V ). Then U V ≡ U V iff repr (U V ) = repr (U V ). E.g., repr (A) = (aa) 2 for all A ∈ A and repr (B) = (a ♦a) 2 for all B ∈ B.

Previous study of p-squares in partial words was mostly focused on their combinatorics. It started with the case of k = 1 hole [START_REF] Blanchet-Sadri | Counting distinct squares in partial words[END_REF], in which case different square subwords correspond to non-equivalent p-square factors. It was shown that a partial word with one hole contains at most 7 2 n different square subwords [START_REF] Blanchet-Sadri | A note on the number of squares in a partial word with one hole[END_REF] (later this bound was improved to 3n for binary partial words [START_REF] Halava | On the number of squares in partial words[END_REF]). Also a generalization of the three squares lemma for words [START_REF] Crochemore | Sqares, cubes, and time-space efficient string searching[END_REF] was proposed for partial words [START_REF] Blanchet-Sadri | The three-squares lemma for partial words with one hole[END_REF].

As for a larger number of holes, the study was devoted mainly to counting the number of different square subwords of a partial word [START_REF] Blanchet-Sadri | Counting distinct squares in partial words[END_REF][START_REF] Blanchet-Sadri | Squares and primitivity in partial words[END_REF] or all occurrences of p-square factors [START_REF] Blanchet-Sadri | Squares in partial words[END_REF][START_REF] Blanchet-Sadri | Squares and primitivity in partial words[END_REF]. Similarly, on the algorithmic side, [START_REF] Manea | Hard counting problems for partial words[END_REF] proved that the problem of counting different square subwords of a partial word is #P-complete and [START_REF] Diaconu | Combinatorial queries and updates on partial words[END_REF][START_REF] Manea | An algorithmic toolbox for periodic partial words[END_REF] and [START_REF] Blanchet-Sadri | Computing primitivelyrooted squares and runs in partial words[END_REF] showed quadratic-and nearly-quadratic-time algorithms for finding all occurrences of p-square factors and primitively-rooted p-square factors of a partial word, respectively. Other work includes avoidance of squares [START_REF] Halava | Square-free partial words[END_REF][START_REF] Blanchet-Sadri | Avoiding large squares in partial words[END_REF] or abelian squares [START_REF] Blanchet-Sadri | Abelian squarefree partial words[END_REF] in partial words.

Our Results

We present the following combinatorial bounds and efficient algorithms related to enumeration of non-equivalent p-square factors of a partial word of length n with k of holes. A length p is called ambiguous if there are two holes at a distance p. Otherwise it is called unambiguous.

Combinatorial results. We prove that a partial word of length n with k holes contains O(nk 2 ) non-equivalent p-squares. We also show an example of a partial word of length n with k holes that contains Ω(nk 2 ) non-equivalent psquares of ambiguous lengths and that contains Ω(nk) non-equivalent p-squares of unambiguous lengths. This work can be viewed as a generalization of the results on partial words with one hole [START_REF] Blanchet-Sadri | Counting distinct squares in partial words[END_REF][START_REF] Blanchet-Sadri | A note on the number of squares in a partial word with one hole[END_REF][START_REF] Halava | On the number of squares in partial words[END_REF] to k > 1 holes.

Algorithmic results. We present an algorithm that reports all non-equivalent p-squares in a partial word in O(nk 3 ) time. In particular, our algorithm runs in linear time for k = O(1) and its time complexity near-matches the maximum number of non-equivalent p-squares. Our algorithm generalizes the approach of [START_REF] Crochemore | Extracting powers and periods in a word from its runs structure[END_REF] and proposes, as an important tool, a non-obvious extension of the notion of runs to partial words (another definition of runs in partial words appeared in [START_REF] Blanchet-Sadri | Computing primitivelyrooted squares and runs in partial words[END_REF]).

Periodicity of Words and Partial Words

A word T is a sequence of letters over an alphabet Σ. By |T | = n we denote the length of T , and by T [i], for i = 1, . . . , n, the ith letter of T . For

1 ≤ i ≤ j ≤ n, T [i..j] denotes the factor of T equal to T [i] . . . T [j]. A positive integer q is called a period of T if T [i] = T [i + q]
for all i = 1, . . . , n -q. In this case, T [1..q] is called a string period of T . Two equal-length words S and T are called cyclic shifts if there exists an index i such that S

[i..|S|]S[1..i -1] = T .
A run (also called a maximal repetition) in T is a triple (a, b, q) such that T [a..b] has the shortest period q, 2q ≤ b -a + 1, and the interval cannot be extended to the left nor to the right without violating the above property, that is,

T [a -1] = T [a + q -1] and T [b -q + 1] = T [b + 1],
provided that the respective letters exist. The exponent of a run is defined as b-a+1 q . A word of length n has at most n runs and they can all be computed in O(n) time [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF].

From a run (a, b, q) we can produce all triples (a, b, kq) for integer k such that 2kq ≤ b -a + 1; we call such triples generalized runs. In other words, the period specified in a generalized run need not be the shortest period of the fragment. The number of generalized runs is also O(n), as the sum of exponents of runs is O(n) [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF].

A partial word is a sequence of symbols from Σ = Σ ∪ { ♦}. For a partial word T we use the same notation as for words: |T | for length, T [i] for the ith letter, T [i..j] for a factor. The relation of matching on Σ is defined as a ≈ a, a ≈ ♦ for all a ∈ Σ . We define an operation ∧ such that a ∧ a = a, a ∧ ♦ = a for all a ∈ Σ , and otherwise a ∧ b is undefined. Two equal-length partial words T and S are said to match (denoted as

T ≈ S) if T [i] ≈ S[i] for all i = 1, . . . , |T |.
In this case, by S ∧ T we denote the partial word

S[1] ∧ T [1], . . . , S[|S|] ∧ T [|S|]. Note that if U V is a p-square, then repr (U V ) = (U ∧ V ) 2 .
A quantum period of a partial word T is a positive integer q such that T [i] ≈ T [i + q] for all i = 1, . . . , |T | -q. T is called quantum periodic with a quantum period q if 2q ≤ |T |. Let T be a partial word of length n. We say that a triple (a, b, q) is a quantum generalized run (Q-run, for short) in T if T [a..b] is quantum periodic with period q and none of the partial words T [a -1..b] and T [a..b + 1] (if exists) has the quantum period q; see Example 1 and Fig. 2.

Example 1. The partial word T = caa ♦ ♦ ♦ ♦ ♦bbd contains one Q-run with period 2: (2, 10, 2) that corresponds to the factor aa ♦ ♦ ♦ ♦ ♦bb.

Generalized runs in standard words are strongly related to squares: (1) every square belongs to a generalized run and, moreover, (2) all factors of length 2q of a generalized run with period q are squares being each other's cyclic shifts. Unfortunately, Q-runs in partial words have only property [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF]. However, we can introduce a type of run in partial words for which both properties (1) and ( 2) hold. A pseudorun (P-run, in short) is a triple (a, b, q) such that: Proof.

(a) T [a..b] is quantum periodic with period q (b) T [i] ∧ T [i + q] = T [i + q] ∧ T [i + 2q] for all i such that i, i + 2q ∈ [a, b], (
(1) Let T [i..j] be a p-square factor of length q = (j -i + 1)/2 in T . Initially we set a = i, b = j; then (a, b, q) satisfies conditions (a) and (b) of a pseudorun (the latter one trivially). Now we extend (a, b, q) until it becomes maximal under the two conditions, i.e., decrement a while

T [a-1]∧T [a+q -1] = T [a + q -1] ∧ T [a + 2q -1],
and same for b.

(2) Every factor of length 2q of a P-run is quantum periodic with period q, hence a p-square. Consider two such consecutive factors

X = T [i..i + 2q -1] and Y = T [i + 1..i + 2q]. Then repr (X) = T [i..i + q -1] ∧ T [i + q..i + 2q -1] and repr (Y ) = T [i + 1..i + q] ∧ T [i + q + 1..i + 2q] = T [i + 1..i + q -1] ∧ T [i + q + 1..i + 2q -1], T [i + q] ∧ T [i + 2q] = T [i + 1..i + q -1] ∧ T [i + q + 1..i + 2q -1], T [i] ∧ T [i + q]
where the last equality is due to condition (b) of a P-run. Consequently, repr (X) and repr (Y ) are cyclic shifts.

Example 3. Let T = caa ♦ ♦ ♦ ♦ ♦bbd. Then T contains five P-runs with period 2: (2, 5, 2), (3, 6, 2), (4, 8, 2), (6, 9, 2) and (7, 10, 2), that correspond to factors: aa ♦ ♦, a ♦ ♦ ♦, ♦ ♦ ♦ ♦ ♦, ♦ ♦ ♦b, and ♦ ♦bb, respectively. The squares induced by the respective P-runs are as follows: aa ♦ ♦; a ♦ ♦ ♦; ♦ ♦ ♦ ♦ (two times); ♦ ♦ ♦b; and ♦ ♦bb.

Combinatorial Bounds

Theorem 4. There exists a partial word of length n with k holes that contains Ω(nk 2 ) non-equivalent p-squares, for k = O( √ n).

Proof. Assume that 2 | k. Consider the following partial word: Claim. For some k = O( √ n), T m,k contains Θ(mk 2 ) non-equivalent p-squares of ambiguous lengths.

T m,k = a m ♦ k/2 a m (a k/2-1 ♦) k/2 a 3m of length n = 4m + ( k 2 ) 2 + k 2 over Σ = {a
Proof. First, note that that there are ( k 2 ) 2 different ambiguous lengths and that for each such length , there is exactly one pair of holes at this distance in T m,k . Indeed, consider the i-th hole in the ♦ k/2 part and the j-th hole in the

(a k/2-1 ♦) k/2 part (1 ≤ i, j ≤ k 2 ). Then the distance between them is k 2 -i + m + k 2 • j = k 2 • j -i + ( k 2 + m)
. Finally, note that for i and j in the considered range, values of the form k 2 • j -i are all distinct (this is a known example of a differenece cover); see Fig. 1.

Let us choose k so that 2(m+

( k 2 ) 2 + k 2 ) ≤ n 2 .
Then for each ambiguous length , we have exactly p-square factors in T m,k of the general form (a i ♦a -i-1 ). As ≥ m = Θ(n), this concludes the proof. We say that a square subword has a solid occurrence if... By the following fact, there are O(n) square subwords of T with solid occurrences.

Fact 5 ([16,20,14]). ≤ 2 rightmost occurrences.

Our upper bound for partial words is based on the following key lemma that generalizes Fact 5. We call an interval

[ , r) ⊆ [1, n] is short if r ≤ 3k+3
3k+2 . Lemma 6. For a short interval [ , r), there are O(k ), where k = holes(i, i + 2r -1), p-squares of unambiguous lengths without solid occurrences in [ , r] that have their rightmost occurrence in T at position i.

Proof. Let us start with the following claim.

Proof. A position i cannot belong to I if T [i] is a hole or T [i + ..i + r] contains a hole. In total, a hole in T [i..i + -1] excludes one positions in [i, i + -1] and a hole in T [i + ..i + 2r -1] excludes at most r -+ 1 consecutive positions in [i, i + -1]
. By the pigeonhole principle, there exists a non-excluded fragment in T [i..i + -1] of consecutive positions of length at least

-k(r -l) k + 1 ≥ (3k + 2)(r -) -k(r -l) k + 1 = 2(r -).
Let X be the subword of T at positions in I. If there are at least two p-square factors of the considered type starting at position i, then X is periodic (Galil...). Let p be its shortest period.

Let U V be a p-square factor of unambiguous length of the considered type and let W W = repr (U V ) There are three cases:

(a) W W has period p (b) W has period p (c) W does not have period p.
There is at most one p-square factor U V corresponding to case (a). Assume to the contrary that there are two such p-squares, U V and U V , of lengths d < d . We have that p | d, d and the generalized forms of the two p-squares have the same string period (as they share a subword U ). Hence, repr (U V ) is a border of repr (U V ), so U V occurs in T at position i + d -d.

We will show that there are at most k + 1 p-square subwords of type (b). Assume to the contrary that at least k + 2 of them, of lengths d 1 < . . . < d k +2 . We see that d j mod k is the same, as the occurrences of X in the right half of the p-square in T differ by multiples of p. Consider the shortest U V and the longest U V these p-squares, with generalized forms W W and W W , and the subword

T [i + d 1 ..i + d k +2 -1].
It matches a prefix P of length d k +2 -d 1 of W and a suffix S of the same length of W . Both P and S have period P ; however, their string periods are not equal. Consequently, in every occurrence of the period in

T [i + d 1 ..i + d k +2 -1]
there mus be a hole; this makes (d k +2 -d 1 )/p ≥ k + 1 holes in total, a contradiction.

(c) Consider the occurrence of X in W . The periodicity of X does not cover the whole W , so there is a position j in W where the periodicity breaks. Assume w.l.o.g. that j is to the right of X. Consider the positions j 1 and j 2 that correspond to j in the subwords U , V of T . If any of T [j 1 ] and T [j 2 ] is not a hole, then it is determined uniquely as the first position where the deterministic period p breaks, starting from the corresponding occurrence of X. Hence, if both of them are not holes, then |W | = j 2 -j 1 is uniquely determined. Otherwise, if T [j 1 ] or T [j 2 ] is a hole (they cannot be both holes, as the length is unambiguous), then one of j 1 , j 2 is uniquely determined and there are at most k choices for the other. Consequently, there are at most 4k + 2 such p-squares. Theorem 8. A partial word T of length n with k holes contains O(nk 2 ) nonequivalent p-squares.

Proof. Obviously, in T there are at most k 2 ambiguous lengths. Consequently, there are O(nk 2 ) non-equivalent p-squares of such lengths. Let us consider psquares of unambiguous lengths. By Fact 5, among them there are O(n) different p-squares with a solid occurrence. From now on we consider only p-squares without a solid occurrence.

Let [ , r] be a short interval. By Lemma 6, the total number of different p-squares of unambiguous lengths in [ , r] in T is:

O n i=1 k i,i+2r-1 = O(rk). (1)
The equality is based on the fact that each of the k holes in T is counted in at most 2r terms k i,i+2r-1 .

Let us consider a family of endpoints r 0 , r 1 , . . .:

r j = n (1 + 1 3k+2 ) j = n 3k+2 3k+3 j .
We divide the p-square lengths into short intervals [r j+1 + 1, r j ]. By (1), the total number of p-squares in T is:

O   ∞ j=0 r j k   = O   nk ∞ j=0 3k+2 3k+3 j   = O nk 1 -3k+2 3k+3 = O(nk 2 ).
From the set of m Q-runs of period p we can produce the set of all P-runs with period p. The computation time is O(m + k). Lemma 11. A partial word of length n with k holes contains O(nk) P-runs and they can all be computed in O(nk) time.

Reporting Squares

Assume that the alphabet Σ is ordered and that ♦ is smaller than all the letters from Σ. We use Observation 2. If we group the P-runs by the minimal cyclic shift of the induced p-squares, then we can apply the approach of [START_REF] Crochemore | Extracting powers and periods in a word from its runs structure[END_REF] to count the p-squares in time linear in the number of P-runs and n.

First, note that the minimal cyclic shift value for a P-run (a, b, p) can be computed in O(k 2 ) time using Theorem 23 from [START_REF] Kociumaka | Minimal suffix and rotation of a substring in optimal time[END_REF]. Indeed, we can represent the representative of the p-square T [a..a + 2p -1] as a concatenation of at most k factors of T and at most k single letters that appear elsewhere in T .

...

  c) none of the partial words T [a -1..b] and T [a..b + 1] (if exists) satisfies the conditions (a) and (b). We say that a p-square T [c..d] is induced by the P-run if the length of the p-square is q and [c, d] ⊆ [a, b]. Observation 2. (1) Every p-square factor in T is induced by a P-run. (1) All factors of length 2q of a P-run with period q are p-squares and their representatives are each other's cyclic shifts.

Fig. 1 .

 1 Fig. 1. Ambiguous lengths in T3,6.

  (b) ... Now we proceed to the upper bound proof. Let us fix a partial word T of length n with k holes. Let holes(a, b) denote the number of holes in T [a..b].

Claim 7 .

 7 There exists an interval I = [a, b] ⊆ [i, i+ -1] such that holes(I) = 0, holes(J) = 0 where J = [a + , b + r), and I ≥ 2(r -).

Theorem 12 .Fig. 2 .

 122 Fig.2. A partial word together with all its Q-runs. This partial word contains 5 p-squares of length 3: aaba ♦b, ♦aaba ♦, ab ♦ ♦ba, a ♦aaba, b ♦ ♦ba ♦. The following pair is equivalent: ab ♦ ♦ba ≡ a ♦aaba.

Supported by Polish budget funds for science in 2013-2017 as a research project under the 'Diamond Grant' program. The author is a Newton International Fellow. Supported by the Polish National Science Center, grant no 2014/13/B/ST6/00770.

Main Algorithm

Let T be a partial word of length n with k holes.

Computing Q-runs

We divide Q-runs into solid Q-runs that do not contain a hole and the remaining non-solid Q-runs. A solid Q-run is a generalized run in a maximal solid factor of T . Thus all solid Q-runs can be computed in O(n) time via a linear-time algorithm for computing runs in words [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF].

Non-solid Q-runs are computed with a modification of Main-Lorentz algorithm [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF]. Let us first reformulate the algorithm in the language of computing generalized runs in words. For a word S of length n, it finds a representation of all p-squares that contain the position i = n/2 and then makes recursive computations in S[1..i] and S[i..n]. It first computes all the p-squares with first half containing the position i and then computes the remaining p-squares containing the position i symmetrically. For a pair of positions i, j, we define lcp(i, j) as the length of the longest common prefix of S[i..n] and S[j..n] and lcs(i, j) as the length of the longest common suffix of S[1..i] and S[1..j]. The algorithm for each position j > i computes lcp(i, j) + lcs(i, j) and, if this value is at least j -i, reports a generalized run (i -lcs(i, j)..j + lcp(i, j), j -i). To avoid duplicates, the generalized run can be omitted if it reaches the end of the word in the recursive call which does not coincide with the position 1 or n in the original word. The algorithm's running time is O(n log n) as lcp-queries and lcs-queries can be answered in O(1)-time after preprocessing.

For a partial word T , the longest common compatible prefix of two positions i, j, denoted lccp(i, j), is defined as the largest such that T [i..i+ -1] ≈ T [j..j + -1]. Symmetrically, we can define lccs as the length of the longest common compatible suffix. In [START_REF] Crochemore | A note on the longest common compatible prefix problem for partial words[END_REF] it was shown that after O(nk)-time preprocessing, lccp-queries (hence, lccs-queries) can be answered in O(1) time.

Thus we could directly apply the Main-Lorentz scheme for partial words; the result would be exactly the set of Q-runs in T . However, this would yield O(n log n)-time computation. We aim only at computing non-solid Q-runs, which lets us easily reduce the complexity to O(n log k). To this end, we only make recursive calls in positions that contain holes, with the recursive call taking place at the position of the k 2 -th hole in T . Together with O(n)-time solid Q-runs computation we arrive at the following.