Marie Bergeaud

Lise Mathieu

Arnaud Guillaume

Ute M Moll

Bernard Mignotte

Nathalie Le Floc'h

Jean-Luc Vayssière

Vincent Rincheval
email: vincent.rincheval@uvsq.fr

Nathalie Le Floch

Mitochondrial p53 mediates a transcription-independent regulation of cell respiration and interacts with the mitochondrial FF-ATP synthase

Keywords: Tumor suppressor, p53, cancer, mitochondria, energetic metabolism, oxidative phosphorylation, respiration, OSCP, reactive oxygen species IMS: inner membrane space, OSCP: oligomycin sensitivity-conferring protein, ROS: reactive oxygen species

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

Introduction

The human p53 protein is encoded by the TP53 gene which is mutated in approximately 50% of human cancers, representing the most common genetic lesion associated with this type of disease. [START_REF] Hollstein | p53 mutations in human cancers[END_REF] It is well known that the p53 protein is a transcription factor [START_REF] Fields | Presence of a potent transcription activating sequence in the p53 protein[END_REF][START_REF] Raycroft | Transcriptional activation by wild-type but not transforming mutants of the p53 anti-oncogene[END_REF][START_REF] Weintraub | The MCK enhancer contains a p53 responsive element[END_REF][START_REF] El-Deiry | Definition of a consensus binding site for p53[END_REF] harbouring low basal levels which can rapidly be activated and stabilized in response to multiple stresses. [START_REF] Maltzman | UV irradiation stimulates levels of p53 cellular tumor antigen in nontransformed mouse cells[END_REF][START_REF] Tishler | Increases in sequence specific DNA binding by p53 following treatment with chemotherapeutic and DNA damaging agents[END_REF] Hundreds of p53-regulated genes have now been discovered which participate in many biological processes such as cell cycle, senescence, apoptosis, metabolism, and DNA repair, 8- 10 suggesting that the main functions of p53 might be executed by its nuclear transcriptional activities. Many efforts have been devoted to study p53-mediated apoptosis and senescence since these processes are still presumed to be particularly important for p53's tumor suppressor activity. [START_REF] Zuckerman | Tumour suppression by p53: the importance of apoptosis and cellular senescence[END_REF] More than a decade ago, it was shown that p53 can also promote apoptosis in a transcription-independent manner, although its mechanism was unknown. [START_REF] Caelles | p53-dependent apoptosis in the absence of transcriptional activation of p53-target genes[END_REF][START_REF] Gottlieb | Relationship of sequence-specific transactivation and p53regulated apoptosis in interleukin 3-dependent hematopoietic cells[END_REF][START_REF] Bissonnette | The apoptotic and transcriptional transactivation activities of p53 can be dissociated[END_REF][START_REF] Yan | Inhibition of protein phosphatase activity induces p53-dependent apoptosis in the absence of p53 transactivation[END_REF][START_REF] Haupt | Induction of apoptosis in HeLa cells by trans-activation-deficient p53[END_REF][START_REF] Haupt | p53 mediated apoptosis in HeLa cells: transcription dependent and independent mechanisms[END_REF][START_REF] Chen | p53 levels, functional domains, and DNA damage determine the extent of the apoptotic response of tumor cells[END_REF] Subsequently it was observed that in response to stress, a fraction of p53 rapidly localizes to mitochondria, prior to p53 nuclear accumulation, triggering mitochondrial outer membrane permeabilization and caspase activation. [START_REF] Marchenko | Death signal-induced localization of p53 protein to mitochondria. A potential role in apoptotic signaling[END_REF][START_REF] Mihara | p53 has a direct apoptogenic role at the mitochondria[END_REF][START_REF] Erster | In vivo mitochondrial p53 translocation triggers a rapid first wave of cell death in response to DNA damage that can precede p53 target gene activation[END_REF][START_REF] Zhao | p53 translocation to mitochondria precedes its nuclear translocation and targets mitochondrial oxidative defense protein-manganese superoxide dismutase[END_REF] It was demonstrated that targeting p53 specifically to mitochondria via fusion with import leader peptides is sufficient to induce apoptosis in p53deficient cells. [START_REF] Marchenko | Death signal-induced localization of p53 protein to mitochondria. A potential role in apoptotic signaling[END_REF] When accumulating at mitochondria, p53 is able to trigger apoptosis through its dual capacity of derepressing as well as directly activating several pro-apoptotic members of the Bcl-2 family at the outer membrane. [START_REF] Leu | Mitochondrial p53 activates Bak and causes disruption of a Bak-Mcl1 complex[END_REF][START_REF] Chipuk | Direct activation of Bax by p53 mediates mitochondrial membrane permeabilization and apoptosis[END_REF][START_REF] Deng | Bcl2's flexible loop domain regulates p53 binding and survival[END_REF] These activities respectively depend on the ability of p53 to dissociate anti-apoptotic Bcl-xL, Bcl-2 and Mcl-1 from their pro-apoptotic partners Bax, Bak and tBid or to directly activate Bak and Bax (reviewed in Vaseva [START_REF] Vaseva | The mitochondrial p53 pathway[END_REF] ).

Several studies have reported that the DNA binding domain of p53 is also important in its mitochondrial roles of Bcl-2 family de-repressor and activator. [START_REF] Mihara | p53 has a direct apoptogenic role at the mitochondria[END_REF][START_REF] Sot | Comparative biophysical characterization of p53 with the proapoptotic BAK and the anti-apoptotic BCL-xL[END_REF][START_REF] Tomita | WT p53, but not tumor-derived mutants, bind to Bcl2 via the DNA binding domain and induce mitochondrial permeabilization[END_REF][START_REF] Petros | Defining the p53 DNA-binding domain/Bcl-x(L)-binding interface using NMR[END_REF][START_REF] Pietsch | Oligomerization of BAK by p53 utilizes conserved residues of the p53 DNA binding domain[END_REF] On the other hand, it is now becoming obvious that some p53 functions occur in the absence of acute stress. These p53 functions depend on basal levels of p53 or the activation of p53 by low levels of constitutive stress. [START_REF] Vousden | Blinded by the Light: The Growing Complexity of p53[END_REF] Several studies have indicated that p53 can participate in the regulation of metabolism, [START_REF] Vousden | p53 and metabolism[END_REF] for instance by inducing transcription of the nuclear gene encoding the SCO2 protein, which is critical for regulating the mitochondrial cytochrome c oxidase (COX) respiratory chain complex. [START_REF] Matoba | p53 regulates mitochondrial respiration[END_REF] Changes in metabolic regulations are important in the development of cancers. The Warburg effect describes the seemingly paradoxical fact that despite sufficient oxygen availability, most cancer cells predominantly produce energy by a high rate of (low yielding) glycolysis rather than by (high yielding) oxidative phosphorylation. [START_REF] Warburg | On respiratory impairment in cancer cells[END_REF] Interestingly, p53 can inhibit glycolysis by decreasing the expression of several glucose transporters. [START_REF] Schwartzenberg-Bar-Yoseph | The tumor suppressor p53 downregulates glucose transporters GLUT1 and GLUT4 gene expression[END_REF][START_REF] Kawauchi | p53 regulates glucose metabolism through an IKK-NF-kappaB pathway and inhibits cell transformation[END_REF] The p53-dependent induction of the TIGAR gene also triggers an inhibition of glycolysis via a decrease in fructose-2,6-biphosphate levels. [START_REF] Bensaad | TIGAR, a p53inducible regulator of glycolysis and apoptosis[END_REF] Furthermore, basal levels of p53 were shown to diminish reactive oxygen species (ROS) levels within the cell by inducing the expression of detoxifying enzymes such as GPX, [START_REF] Tan | Transcriptional activation of the human glutathione peroxidase promoter by p53[END_REF][START_REF] Hussain | p53-induced up-regulation of MnSOD and GPx but not catalase increases oxidative stress and apoptosis[END_REF][START_REF] Sablina | The antioxidant function of the p53 tumor suppressor[END_REF] MnSOD, [START_REF] Hussain | p53-induced up-regulation of MnSOD and GPx but not catalase increases oxidative stress and apoptosis[END_REF] catalase in certain cell types [START_REF] O'connor | A novel antioxidant function for the tumorsuppressor gene p53 in the retinal ganglion cell[END_REF] and sestrins. [START_REF] Velasco-Miguel | PA26, a novel target of the p53 tumor suppressor and member of the GADD family of DNA damage and growth arrest inducible genes[END_REF][START_REF] Budanov | Identification of a novel stress-responsive gene Hi95 involved in regulation of cell viability[END_REF] Paradoxically, p53 has also been described to upregulate the expression of pro-oxidant factors such as PIG3, [START_REF] Polyak | A model for p53-induced apoptosis[END_REF] PIG6 [START_REF] Rivera | The p53-induced gene-6 (proline oxidase) mediates apoptosis through a calcineurin-dependent pathway[END_REF] or FDXR [START_REF] Liu | The ferredoxin reductase gene is regulated by the p53 family and sensitizes cells to oxidative stress-induced apoptosis[END_REF] and to repress expression of MnSOD during acute stress. [START_REF] Dhar | Nuclear factor kappaB-and specificity protein 1-dependent p53mediated bi-directional regulation of the human manganese superoxide dismutase gene[END_REF] This complex situation has led to the postulate that p53 could assume the role of a protector or a killer, depending on the type and severity of stress.

As previously observed in studies focusing on p53 apoptotic functions, it has been shown that p53 can also regulate normal mitochondrial physiology through transcriptionindependent activities. Several studies, performed with cells that either overexpress or lack p53 have shown that p53 can interact with mitochondrial proteins located in the mitochondrial matrix, such as the DNA polymerase  which is involved in the synthesis and repair of mtDNA. This interaction could account for a higher mtDNA copy number in p53 +/+ versus p53 -/-cells. [START_REF] De Souza-Pinto | p53 functions in the incorporation step in DNA base excision repair in mouse liver mitochondria[END_REF][START_REF] Chen | The p53 pathway promotes efficient mitochondrial DNA base excision repair in colorectal cancer cells[END_REF][START_REF] Lebedeva | Loss of p53 causes mitochondrial DNA depletion and altered mitochondrial reactive oxygen species homeostasis[END_REF][START_REF] Kulawiec | p53 regulates mtDNA copy number and mitocheckpoint pathway[END_REF][START_REF] Park | p53 improves aerobic exercise capacity and augments skeletal muscle mitochondrial DNA content[END_REF] We and others have previously characterized that endogenous p53 can be located at mitochondria in the absence of exogenous stress, further supporting that p53 has a role in the normal physiology of this organelle. [START_REF] Mahyar-Roemer | Mitochondrial p53 levels parallel total p53 levels independent of stress response in human colorectal carcinoma and glioblastoma cells[END_REF][START_REF] Ferecatu | Mitochondrial localization of the low level p53 protein in proliferative cells[END_REF][START_REF] De | RECQL4 is essential for the transport of p53 to mitochondria in normal human cells in the absence of exogenous stress[END_REF] In the present study, our aim was to better characterize the intramitochondrial localization of p53 and to identify new partners and functions of p53 in mitochondria in the absence of induced stress. Here we established that most of the intramitochondrial pool of p53 is present in the two soluble compartments of mitochondria, with higher amounts of p53 in the intermembrane space (IMS) than in the matrix. Using the human lung carcinoma H1299 cell line specifically expressing mitochondrially targeted p53 in the IMS (H1299-p53-IMS) or in the matrix (H1299-p53-Mx), we have observed that addressing low levels of p53 to the matrix is sufficient to simultaneously increase oxygen consumption and decrease mitochondrial superoxide production. By immunoprecipitation and mass spectrometry approaches, we also identified the Oligomycin Sensitivity-Conferring Protein (OSCP), a component of the F1F0-ATP synthase, as a new partner of endogenous mitochondrial p53, specifically interacting with p53 localized in the matrix. Interestingly, we have observed that this interaction could be implicated in mitochondrial localization of p53. We have also shown that p53 localized in the matrix promotes the assembly of the F1F0-ATP synthase complex. In conclusion, our results demonstrate that in the absence of stress, low levels of mitochondrial p53 can have important effects on mitochondrial physiology, notably on cell respiration. Considering the importance of such processes in the development of several pathologies such as cancer, we suggest that mitochondrial p53 could be an important regulator of normal mitochondrial and cellular physiology, potentially exerting tumor suppression activities inside mitochondria.

Materials and Methods

Construction of cell lines stably expressing mitochondrially targeted p53. The p53-Mx vector allowing the expression of p53 to the mitochondrial matrix was constructed by Pr. Ute M. Moll's laboratory. [START_REF] Marchenko | Death signal-induced localization of p53 protein to mitochondria. A potential role in apoptotic signaling[END_REF] In this pcDNA3 derived vector, the sequence encoding mitochondrial import leader of ornithin transcarbamylase is fused to the N-terminus of human wild type p53 coding sequence. The p53-IMS vector was used to address p53 to the mitochondrial intermembrane space. This vector was derived from the pIRES-cytb2-WTSOD1 plasmid that was kindly given by Dr. Jordi Magrané, Weill Medical College of Cornell University, USA. 56 Briefly, the WTSOD1 coding sequence was replaced with the human wild type p53 coding sequence. The WTSOD1 sequence was removed by enzymatic cleavage with NotI and BstXI.

The p53 sequence was PCR-amplified using primers displaying NotI (forward primer) or BstXI (reverse primer) restriction sites. The PCR product was then subcloned into pJET1.2 vector (CloneJet PCR cloning kit, Fermentas) to facilitate the cleavage by the appropriate restriction enzymes. The digestion product was cloned in frame with the C-terminus of the mitochondrial targeting sequence plus four amino acids of CytB2. The p53-IMS vector construction was verified by sequencing (Eurofins MWG Operon). For establishment of cell lines, H1299 p53-null cells were plated in 60 mm diameter Petri dishes, transfected with 10 µg of the p53-IMS vector, p53-Mx vector or pcDNA3 plasmid as control, using lipofectamin 2000 (Invitrogen) at 80% confluence and transferred in two 100 mm diameter Petri dishes 24 hours post-transfection. Transfected cells were then selected under G418 treatment and individual clones were isolated after 2 weeks of selection.

Cell lines and cell culture. HCT116 human colorectal carcinoma cells p53 +/+ and p53 -/-, 57 H1299 human lung adenocarcinoma cells (p53 null) and its derivatives (p53-Mx, p53-IMS and pcDNA3), were grown in DMEM F-12 medium (Invitrogen) supplemented with 10% fetal bovine serum, 1% Glutamax (v/v), 100 µg/ml penicillin and 100 U/ml streptomycin, at 37°C in a humidified atmosphere containing 5% CO2. In order to induce genotoxic stress, cells were treated with 125 μg/ml etoposide (Sigma Aldrich) for 24 hours. siRNA transfection. To inhibit OSCP expression, 7.10 5 HCT116 cells were seeded in 60 mm cell culture dishes. 24 hours later, cells were transiently transfected with lipofectamine 2000 (Invitrogen) according to the manufacturer's instructions, with a mix containing 11 µl of Lipofectamine 2000 reagent (Invitrogen) and 162 nM of siRNA oligonucleotides for OSCP (sc-62452, Santa Cruz Biotechnology) or 162 nM of control siRNA (sc-37007, Santa Cruz Biotechnology). 72 hours following transfection, cells were collected for cell fractionation with Qproteome Mitochondria Isolation kit (Qiagen).

Cell fractionation and mitochondria isolation. Mitochondria from HCT116 and H1299 cells have been prepared using (1) the Qproteome mitochondria isolation kit (Qiagen) or (2) a conventional differential centrifugation procedure [START_REF] Ferecatu | Evidence for a mitochondrial localization of the retinoblastoma protein[END_REF] for preparation of large amounts of mitochondrial fractions. (1) Briefly, cells were harvested, washed in 0,9% NaCl and incubated for 10 min at 4°C in lysis buffer. The homogenate was centrifuged at 1000 g for 10 min at 4°C, the supernatant was designated as cytosolic fraction. The pellet was resuspended in disruption buffer, passed through a 26-gauge needle 15 times. Enriched nuclei fraction was pelleted by centrifugation at 1000 g during 10 min and was homogenized in disruption buffer.

To obtain the enriched mitochondrial fraction, the supernatant was centrifuged at 6000 g for 10 min at 4°C and resuspended in mitochondria storage buffer. All buffers except mitochondria storage buffer were supplemented with protease inhibitors at 1:100, provided within the kit. Protein concentration of the different fractions was determined with the BCA protein assay kit (Pierce). (2) Cell pellets were resuspended in fractionation buffer A (250 mM sucrose, 0,1 mM EDTA, 1 mM EGTA, 10 mM Hepes-KOH pH 7,4) and incubated 30 min at 4°C. Cell disruption was performed by passing the cells through a 26-gauge needle 10-15 times. The homogenates were centrifuged at 700 g for 10 min at 4°C. The supernatants were removed and centrifuged at 7000 g for 20 min at 4°C. The mitochondria pellets were washed in fractionation buffer B (250 mM sucrose, 5 mM succinate, 5 mM KH2PO4, 10 mM Hepes-KOH pH 7,4). All buffers were supplemented with 1mM protease inhibitors (Aebsf, Roche).

Mitochondrial subfractionation. For subfractionation, mitochondria were harvested using the Qproteome mitochondria isolation kit (Qiagen) and washed in isotonic buffer (250 mM sucrose, 10 mM Tris-HCl) by centrifugation at 14000 g for 10 min at 4°C to discard mitochondria storage buffer (Qiagen). Mitochondria pellets were resuspended in 10 mM Tris-HCl buffer with or without 250 mM sucrose. Mitochondria or mitoplasts were respectively obtained and treated with increasing quantities of proteinase K (150 ng, 300 ng and 450 ng per 50 µg of mitochondrial proteins) and incubated on ice for 45 min. Proteinase K was finally inactivated by adding the protease inhibitor PMSF at 1mM. Treated samples were resuspended in a 250 mM sucrose, 10 mM Tris-HCl, 90 mM KCl buffer supplemented with PMSF at 1mM and immediately loaded onto NuPAGE 4-12% Bis Tris polyacrylamide gels (Invitrogen) for western blot analysis.

Immunoprecipitation and Mass Spectrometry. Mitochondrial pellets, isolated by a conventional differential centrifugation procedure, [START_REF] Ferecatu | Evidence for a mitochondrial localization of the retinoblastoma protein[END_REF] were lysed in 1% digitonin buffer (150 mM NaCl, 5 mM EDTA, 1% digitonin, 50 mM Tris-HCl pH7,5) for 1 hour. p53 was immunoprecipitated from 250 μg of mitochondrial lysate with anti-p53 agarose conjugated beads (FL-393; sc-6243 AC, Santa Cruz Biotechnology) or with control IgG agarose conjugated beads (normal rabbit IgG-AC; sc-2345, Santa Cruz Biotechnology) at 4°C overnight. Samples were next washed 5 times with 0,5% digitonin buffer (150 mM NaCl, 5 mM EDTA, 0,5% digitonin, 50 mM Tris-HCl pH7,5). All buffers were supplemented with 1mM protease inhibitors (Aebsf, Roche). The immunoprecipitated proteins were eluted, loaded onto NuPAGE 4-12% Bis Tris polyacrylamide gels (Invitrogen) and analyzed by immunoblotting or stained with Coomassie Blue (Bio-Safe Coomassie Stain, BIO-RAD) for 1 hour and rinsed in ultrapure H2O for LC-MS/MS analyses. After staining, spots corresponding to immunoglobulin were eliminated. The remaining gel was treated, proteins isolated and digested with trypsin prior to analysis by an LTQ Orbitrap mass spectrometer, at mass spectrometry facility PAPPSO (Dr A. Guillot, INRA Jouy-en-Josas, France).

SDS-PAGE electrophoresis and Western blot.

Protein samples were resolved by NuPAGE 4-12% Bis Tris polyacrylamide gels (Invitrogen) and transferred to polyvinylidene difluoride membranes (Millipore). Membranes were blocked with 5% nonfat milk in TBS-Tween (25 mM Tris-HCl pH 7,6, 150 mM NaCl, 0,1 % Tween 20) for 1 hour at room temperature and incubated with primary antibody for 2 hours at room temperature or overnight at 4°C. The following primary antibodies were used: anti-p53 (DO-1, sc-126, Santa Cruz Biotechnology) 1:500, anti-PCNA (Sigma Aldrich) 1:500, anti-enolase (gift from N. Lamande, College de France) 1:500, anti-VDAC1 (31HL Ab-1, Calbiochem) 1:1000, anti-OSCP (ATP5O, Mitosciences) 1:1000, anti-mitofilin (PA1-16918, Pierce antibodies) 1:2000, anti-Tom40 (H300, sc-11414, Santa Cruz Biotechnology) 1:500, anti-actin (Sigma Aldrich) 1:200, anti-Bak (G23, sc-832, Santa Cruz Biotechnology) 1:500, anti-lamin A/C (Cell Signaling) 1:1000, anti-MnSOD (Millipore) 1:500. After washing with TBS-Tween 0.1% (v/v), immunoblots were incubated with horseradish peroxidase-conjugated secondary antibodies (Jackson ImmunoResearch) 1:10000, for 1 hour. Proteins on the membranes were detected by immobilon chemiluminescent HRP Substrate (Millipore), visualized and quantified using ChemiDoc XRS+ system (BIO-RAD). Statistical analyses. To compare two groups Student t-test was used. p < 0.05 was accepted as significant. Probabilities values were indicated in the figures.

Analysis of F1F0-ATP synthase complex assembly by blue native gel electrophoresis (BN-PAGE). Mitochondria prepared using the

Results p53 localizes at mitochondria in the intermembrane space and matrix compartments in

HCT116 unstressed cells. p53 localization in stress conditions has been intensively studied and it was observed that p53 accumulates in nucleus and in mitochondria after stress induction. Without stress induction, the endogenous level of p53 is low and its functions remain to be precisely identified. In this condition, we previously reported that p53 can localize at mitochondria in human and rodent proliferative cells. [START_REF] Ferecatu | Mitochondrial localization of the low level p53 protein in proliferative cells[END_REF] Here we attempted to verify if this phenomenon is general. To this end, we tested if basal p53 is located at mitochondria in other cell lines, including human colorectal carcinoma HCT116 cells expressing wild type p53. Cells were also cultivated with etoposide for 24 hours, a treatment used as control for stress condition. Etoposide is a topoisomerase II inhibitor that induces to single-strand and double-strand DNA breaks. [START_REF] Burden | Mechanism of action of eukaryotic topoisomerase II and drugs targeted to the enzyme[END_REF] These damages cause post-translational modifications and stabilization of p53, which accumulates in nucleus and mitochondria. In both conditions (+/-etoposide), we examined p53 localization by cell fractionation (Fig. 1A, left panel). The reliability of fractionation experiments was confirmed by the relative enrichment of compartment-specific proteins. Contamination of the mitochondrial fraction was assayed by nuclear and cytosolic marker proteins. The mitochondrial Tom40 protein was used to control for enrichment of the mitochondrial fraction. The purity of these mitochondria was highlighted by the fact that they were enriched for Tom40, but not for the abundant nucleo-cytosolic protein PCNA and the cytosolic protein enolase.

Consistent with the literature, etoposide leads to p53 stabilization and accumulation in both the nuclear and mitochondrial compartments of HCT116 cells. In unstressed cells, we detected a low p53 signal in the mitochondrial fraction showing that p53 localized at mitochondria in proliferating conditions. The same observations were obtained with human colorectal carcinoma RKO cells and human fibrosarcoma HT1080 cells (data not shown). The ratio of mitochondrial p53 level to total cellular p53 level is constant between stressed and unstressed cells and it is of approximately 3% (Fig. 1A, right panel). This result suggests that p53 rather accumulate than translocate at mitochondria in stress conditions.

To better define the mitochondrial localization of p53 we next performed subfractionation experiments in unstressed HCT116 cells. First, to test whether p53 was associated with mitochondrial membranes, mitochondria purified from HCT116 cells were alkali-treated and the soluble and membrane fractions were analyzed by immunoblotting (Fig. 1B, left panel). p53 is found mostly in the soluble fraction after alkali treatment, but is also weakly detected in the membrane fraction (Fig. 1B). As expected, Bak and Tom40, which are embedded in the outer membrane, were recovered only in the pellet fractions while the soluble actin protein (mitochondrial periphery) was found in the supernatant (Fig. 1B). Thus, p53 appears not to be embedded in mitochondrial membranes but is soluble and/or weakly associated with membranes. According to these results, p53 could have the following sublocalizations within mitochondria: organelle periphery, intermembrane space and/or matrix.

Next, we performed swelling experiments to disrupt the outer membrane of isolated mitochondria from unstressed HCT116 cells in the presence or absence of proteinase K.

Figure 1C shows that without osmotic swelling the intermembrane space protein mitofilin and the matrix protein OSCP, a component of the F1F0-ATP synthase (complex V of the oxidative phosphorylation chain), are well protected from protease degradation, whereas the extra-mitochondrial protein actin is completely degraded. Quantifications using OSCP as control for both loading and mitochondrial membrane integrity show that p53 is partially degraded (about 50%; Fig. 1C, left panel lane 4). Consistent with the literature, this confirms that a fraction of p53 is present at the outer mitochondrial membrane facing the cytosolic compartment. Moreover, proteinase K treatment on mitoplasts highlights a second mitochondrial fraction of p53 that is degraded after protease treatment, as is most of fulllength mitofilin (Fig. 1C, left panel lane 7). This fraction appears to be located in the intermembrane space (about 30%). The last mitochondrial fraction of p53 that remains stable and protected from the protease degradation in both intact mitochondria and mitoplasts is therefore located within the mitochondrial matrix (about 20%, Fig. 1C lane 7). Altogether our results indicate that p53 can be found in mitochondria in two mitochondrial subcompartments, i.e. the intermembrane space and matrix, suggesting a multi-functional role for p53.

The H1299-p53-Mx and H1299-p53-IMS stable cell lines respectively express p53 in the mitochondrial matrix and intermembrane space. Since we observed that low levels of endogenous p53 can be located inside mitochondria in unstressed cells, we have constructed a cellular model allowing the study of p53 effects in these specific compartments. We used the H1299 lung carcinoma cell line, which has a homozygous partial deletion of the TP53 gene and does not express p53, to generate a stable line expressing mitochondrially targeted p53.

The stable H1299-p53-Mx cell line results from transfection with a pcDNA3 vector in which the sequence encoding mitochondrial import leader of ornithin transcarbamylase (OTC) was fused to the 5' end of human wild type p53 (Fig. 2A, upper left panel). This leader sequence allows the fused protein to be imported inside the mitochondrial matrix where the leader peptide is cleaved off by matrix endopeptidases, and has previously been used to target p53 to mitochondria. [START_REF] Marchenko | Death signal-induced localization of p53 protein to mitochondria. A potential role in apoptotic signaling[END_REF] A H1299-pcDNA3 control cell line containing the empty vector was also indicating that p53 is localized inside mitochondria. The same observation was made with mitoplasts obtained after osmotic choc, demonstrating that p53-Mx is, as expected, localized into the mitochondrial matrix. Indeed, the p53 protein behaves similarly to the matrix OSCP protein, whereas mitofilin, which is inserted into the inner mitochondrial membrane, is mostly degraded. We chose this line since it showed very low basal levels of matrix p53 and did not undergo spontaneous cell death.

The stable H1299-p53-IMS (clone 1, C1) cell line results from transfection with a vector in which the sequence encoding mitochondrial import leader composed of two cleavable sorting signals of cytochrome B2 (CytB2), a soluble protein of the intermembrane space, [START_REF] Ono | Sorting of cytochrome b2 to the intermembrane space of mitochondria. Kinetic analysis of intermediates demonstrates passage through the matrix[END_REF] was fused to the 5' end of human wild type p53 (Fig. 2B, upper left panel). A comparison between the H1299-p53-IMS and the pcDNA3 control line confirms that H1299-p53-IMS cells specifically express p53 (Fig. 2B, lower left panel). Upon cellular fractionation and mitochondrial subfractionation (Fig. 2B, right panel), similar observations than those described for H1299-p53-Mx cells can be made for Wcl, N*, Ctrl fractions and proteinase K treatments on intact mitochondria, indicating that p53-IMS is effectively localized inside mitochondria (actin was used as contamination control instead of lamins). However, proteinase K treatments on mitoplasts shows an almost complete degradation of p53, indicating that p53-IMS is localized in the intermembrane space as expected.

Mitochondrial p53 promotes respiration and decreases ROS production. Mitochondria

are the main site of ATP production in cells through oxidative phosphorylation, a process that consumes oxygen but also leads to ROS generation as unavoidable side-product. Recent evidence indicates that p53 is able to regulate mitochondrial function in unstressed cells through its transcriptional activities. Indeed, p53 activates transcription of nuclear genes coding mitochondrial proteins such as the SCO2, implicated in the cytochrome c oxidase complex assembly of the respiratory chain, or the superoxide dismutase MnSOD that helps detoxifying ROS. [START_REF] Matoba | p53 regulates mitochondrial respiration[END_REF][START_REF] Dhar | Nuclear factor kappaB-and specificity protein 1-dependent p53mediated bi-directional regulation of the human manganese superoxide dismutase gene[END_REF] Thus, it has been described that p53 increases oxygen consumption rate and diminishes ROS production through its transcriptional functions. Since we and others showed a mitochondrial localization of p53 in unstressed cells, we hypothesized that p53 could also directly regulate mitochondrial bioenergetics in this organelle's physiology. In order to identify mitochondrial functions of p53, we determined whether respiration and ROS production were affected by mitochondrial p53. Oxygen consumption rate and mitochondrial ROS generation rate were measured on HCT116 p53 +/+ cells compared to HCT116 p53 -/-cells (Fig. 3A). As previously described in the literature, HCT116 p53 +/+ cells have higher oxygen consumption and lower mitochondrial ROS than HCT116 p53 -/-cells. [START_REF] Matoba | p53 regulates mitochondrial respiration[END_REF][START_REF] Hu | Glutaminase 2, a novel p53 target gene regulating energy metabolism and antioxidant function[END_REF] However, these cells do not permit to discriminate nuclear from direct mitochondrial p53 functions for these activities. To determine whether p53 can directly regulate respiration and ROS production at mitochondria, these two parameters were measured on H1299 pCDNA3, H1299-p53-Mx and H1299-p53-IMS cells. Interestingly, cells with mitochondrial matrix p53 consume significantly more oxygen and produce less mitochondrial ROS than p53 null cells (Fig. 3B).

Conversely, the oxygen consumption rate of cells with p53 localized in the intermembrane space seems lower than p53 null cells, so p53 localized in this compartment could have an opposite effect compared to p53 localized in the matrix (Fig. 3C). In these H1299-p53-IMS cells the mitochondrial ROS generation rate is not modified in comparison to p53 null cells (Fig. 3C).

These results suggest that in addition to its related nuclear transcriptional functions, p53 can also directly regulate mitochondrial respiratory activity when localized in the mitochondrial matrix. Apparently, in this internal mitochondrial compartment, p53 promotes respiratory chain function by mediating an increase in oxygen consumption and a decrease in mitochondrial ROS production. In contrast, p53 localized in the intermembrane space does not seem to regulate this process in the same way. Mitochondrial mass in the three H1299 cell lines was quantified and no detectable difference was found between cells expressing or lacking p53 (data not shown), indicating that p53 does not achieve this effect by increasing mitochondrial mass or numbers per cell but rather appears to fine-tune and optimize the respiratory chain. p53 interacts with OSCP, a protein of the F1F0-ATP synthase. To gain insight into the mechanism of function of mitochondrial matrix p53, we sought to identify p53 partner proteins in mitochondria from unstressed cells. To this end, we used a global approach and performed p53 immunoprecipitation followed by mass spectrometry analysis. p53 immunoprecipitation and negative control immunoprecipitation with irrelevant antibody (normal rabbit IgG) were performed on mitochondria isolated from HCT116 cells untreated or treated with etoposide. The eluted immunoprecipitates were separated by SDS-PAGE before staining with Coomassie blue. The immunoglobulin spots detectable with this staining were removed from gel with a scalpel. The remainder gel containing immunoprecipitated proteins were harvested to analysis. After extraction from gel, proteins were digested with trypsin and the resulting peptides separated by high performance liquid chromatography and analyzed by tandem mass spectrometry.

Three peptides corresponding to the mitochondrial matrix protein Oligomycin

Sensitivity-Conferring Protein (OSCP) were identified specifically in p53 immunoprecipitates, but was absent in control IgG immunoprecipitations from etoposidetreated HCT116 cells, suggesting specificity (Fig. A). Specifically, OSCP is part of the peripheral stalk of the F1F0-ATP synthase, which links the F0 domain to the F1 domain and is positioned near the crown region at the top of the F1 domain. [START_REF] Rubinstein | ATP synthase from Saccharomyces cerevisiae: location of the OSCP subunit in the peripheral stalk region[END_REF] We verified this interaction by immunoblotting and confirmed that OSCP was weakly but reproducibly detectable in the p53 immunoprecipitate under stressed and unstressed conditions (Fig. 4B). In support, a p53-OSCP interaction was also reproducibly detected by p53 immunoprecipitation of purified mitochondria from H1299-p53-Mx cells that express mitochondrial matrix-targeted p53 (Fig. 4C). H1299-pcDNA3 cells were used as negative control. Moreover, we used the H1299-p53-IMS clone 2 that expresses mitochondrial p53 at high levels. However, the much higher levels of intermembrane space p53 in H1299-p53-IMS cells interact more weakly with OSCP than the much lower levels of matrix p53 in H1299-p53-Mx cells, consistent with the matrix localization of OSCP protein (Fig. 4C). Together, these data demonstrate that OSCP is a novel specific interaction partner of p53 in the matrix of unstressed (and stressed) mitochondria.

The interaction between p53 and OSCP prompted us to investigate the influence of p53 in ATP production, since OSCP is a component of F1F0-ATP synthase, the complex which produces ATP from ADP in the presence of a proton gradient generated across the inner membrane by electron transport complexes of the respiratory chain. We measured total and mitochondrial ATP production but observed no difference between cells expressing mitochondrially targeted p53 and p53 -/-cells (data not shown). Thus, the interaction of p53 with OSCP does not seem to regulate ATP production but instead might be implicated in ROS regulation by stabilization of oxidative phosphorylation complexes.

OSCP regulates mitochondrial localization of p53. We determined that p53 is able to localize in the mitochondrial matrix in unstressed conditions, with approximately 20% of the total mitochondrial p53 pool present in this compartment (Fig. 1C). Thus we next determined if the interaction of p53 with OSCP, a protein located in the matrix, could be implicated in p53 matrix localization. Indeed, p53 does not contain a classical mitochondrial targeting signal and co-transport mechanisms have been proposed for its mitochondrial import. [START_REF] De | RECQL4 is essential for the transport of p53 to mitochondria in normal human cells in the absence of exogenous stress[END_REF] To test this hypothesis, we examined the localization of p53 after knocking down OSCP expression. HCT116 cells were transfected with siRNA OSCP or nonspecific siRNA as control. Cells were harvested 72 hours after transfection, an aliquot of whole cell lysate was kept and mitochondrial and cytosolic fractions were isolated (Fig. 5A). Loading of mitochondrial fractions were normalized to VDAC1 (Voltage Dependent Anion Channel), the most abundant protein of the outer mitochondrial membrane (Fig. 5B). We noticed a 70% decrease of OSCP level in mitochondrial fractions of cells treated with siRNA OSCP compared to siRNA control. Interestingly, we observed a 30% reduction of the p53 protein level in the mitochondrial fraction in siOSCP mitochondria compared to control. Conversely, the total amount of cellular p53, normalized to actin levels in total cellular extracts, was not affected by OSCP expression reduction (Fig. 5C). These results suggest that OSCP might be implicated in translocation or stability of p53 in the mitochondrial matrix.

p53 is required for F1F0-ATP synthase complex assembly or stabilization. To obtain insight into the functional implication of the p53/OSCP interaction apart from mitochondrial localization regulation of p53, we analyzed whether the absence of total or mitochondrial p53 could affect the steady-state level of mature F1F0-ATP synthase, using Blue-Native PAGE and immunoblotting. As shown in Figures 6A and6B, Blue-Native gel immunoblots reveal a decrease of F1F0-ATP synthase (20%) in the HCT116 p53 -/-cells compared to HCT116 p53 +/+ cells. In support, F1F0-ATP synthase is also reduced (40%) in H1299 pCDNA3 cells compared to H1299-p53-Mx cells (Figures 6A and6C), while its steady-state level is not significantly different from H1299-p53-IMS cells (Figures 6A and6D). Hence, contrary to p53-IMS, p53-Mx can directly act on the assembly or stability of F1F0-ATP synthase.

Interestingly, these results suggest that p53 located in the matrix could affect the organization of one or several oxidative phosphorylation complexes, likely explaining its effects on cell respiration.

Discussion

Until now it was thought that p53 activities which mediate tumor suppression were limited to trigger cell cycle arrest, senescence or apoptosis in stress conditions through transcriptiondependent and independent activities. The majority of studies on p53 functions have been performed in stress conditions, where p53 is stabilized at high levels compared to the very low levels of unstressed cells due to high degradative turnover. However, data accumulates indicating an emerging role of p53 at basal levels. p53 notably seems to influence metabolism in the absence of acute stress. Solid data describe that basal p53 can diminish glycolysis, favor oxidative phosphorylation and reduce ROS production by transcription-dependent mechanisms. It has been suggested that these new basal p53 functions could also be important to inhibit tumor development, since metabolic alterations can contribute to cell transformation. Furthermore, several independent studies have shown a mitochondrial localization of p53 in the matrix compartment, where it interacts with DNA polymerase γ and mtTFA, potentially acting on maintenance and fidelity of mtDNA. [START_REF] Yoshida | P53 physically interacts with mitochondrial transcription factor A and differentially regulates binding to damaged DNA[END_REF][START_REF] Achanta | Novel role of p53 in maintaining mitochondrial genetic stability through interaction with DNA Pol gamma[END_REF][START_REF] Bakhanashvili | Excision of nucleoside analogs in mitochondria by p53 protein[END_REF] In this study we identified mitochondrial localization of basal p53 in unstressed cells, using the human wtp53 expressing HCT116 cell line as a model. In the absence of acute stress, the total cellular content of p53 is low and we estimated that approximately 3% of total cellular p53 is localized at mitochondria. Our data indicates that endogenous p53 resides in the intermembrane space and matrix in addition to its outer membrane localization. Furthermore, we observed that p53 is localized in soluble compartments in mitochondria or only weakly bound to mitochondrial membranes, in agreement with the lack of a transmembrane domain prediction within the p53 polypeptide sequence. p53-dependent transcriptional regulation of several genes encoding mitochondrial proteins implicated in oxidative phosphorylation or ROS scavenging such SCO2, MnSOD and the glutaminase 2 have been previously described. [START_REF] Matoba | p53 regulates mitochondrial respiration[END_REF][START_REF] Hussain | p53-induced up-regulation of MnSOD and GPx but not catalase increases oxidative stress and apoptosis[END_REF][START_REF] Hu | Glutaminase 2, a novel p53 target gene regulating energy metabolism and antioxidant function[END_REF] We have hypothesized that p53 can also play a direct role in mitochondrial physiology. To discriminate nuclear from mitochondrial p53 functions with respect to regulating mitochondrial metabolism, we generated stable cell lines expressing p53 targeted to the mitochondrial intermembrane space or the matrix, the two inner mitochondrial compartments identified as p53 localization sites. We selected cellular clones expressing low mitochondrial p53 levels close to the endogenous levels. This model was used to obtain evidence for new p53 roles at mitochondria. Indeed, p53 localized in the matrix increased oxygen consumption and reduced mitochondrial ROS generation in healthy cells. Conversely, p53 in the intermembrane space does not seem to regulate these processes. Thus, our data indicate that p53 is able to directly regulate mitochondrial oxidative phosphorylation in this organelle, and suggests that this effect occurs in the matrix. These results are consistent with emerging data indicating the regulation of respiration by basal p53 and show that effects observed in HCT116 cells are dependent on both nuclear and mitochondrial p53. It was recently shown that p53 in the matrix activates necrosis cell death after oxidative stress, [START_REF] Vaseva | p53 opens the mitochondrial permeability transition pore to trigger necrosis[END_REF] suggesting that p53 in this compartment can have major activities in the presence or absence of stress.

In our search of how p53 could regulate oxygen consumption and ROS production, we identified the OSCP as a new mitochondrial partner protein of p53 in the matrix compartment.

Although this protein is a matrix subunit of F1F0-ATP synthase, we found no effect of mitochondrial p53 on ATP production. Instead, this interaction might be involved in mitochondrial p53 import, since we observed that mitochondrial p53 localization is reduced when OSCP expression is knocked down by siRNA. We therefore speculate that OSCP could co-transport p53 in mitochondria or stabilize p53 in the matrix compartment. Indeed, despite intramitochondrial compartment localizations, the p53 polypeptide sequence lacks a mitochondrial-targeting signal, as do an increasing number of nuclear factors that are currently being detected at mitochondria such CREB, NF-κB, or STAT3, [START_REF] Lee | Mitochondrial cyclic AMP response element-binding protein (CREB) mediates mitochondrial gene expression and neuronal survival[END_REF][START_REF] Cogswell | NF-kappa B and I kappa B alpha are found in the mitochondria. Evidence for regulation of mitochondrial gene expression by NF-kappa B[END_REF][START_REF] Wegrzyn | Function of mitochondrial Stat3 in cellular respiration[END_REF] indicating noncanonical mechanisms of targeting and import. It has already been shown that p53 can be imported into mitochondria by co-transport mechanisms via interaction with proteins such as mtHsp70, [START_REF] Marchenko | Death signal-induced localization of p53 protein to mitochondria. A potential role in apoptotic signaling[END_REF] Tid1, [START_REF] Ahn | Tid1 is a new regulator of p53 mitochondrial translocation and apoptosis in cancer[END_REF] mitochondrial helicase RECQL4, [START_REF] De | RECQL4 is essential for the transport of p53 to mitochondria in normal human cells in the absence of exogenous stress[END_REF] or OKL38. [START_REF] Hu | Interaction of OKL38 and p53 in regulating mitochondrial structure and function[END_REF] Furthermore, a very recent study described an import mechanism of the STAT3 nuclear protein into the mitochondrial matrix via an interaction with GRIM-19, a subunit of respiratory chain complex I, [START_REF] Tammineni | The import of the transcription factor STAT3 into mitochondria depends on GRIM-19, a component of the electron transport chain[END_REF] supporting the fact that such proteins can also be involved in protein transport into mitochondria.

We also provide evidence that matrix p53 takes part in the assembly or stabilization of the mature F1F0-ATP synthase complex. Previously a transcriptional effect of p53 on cytochrome c oxidase assembly was described via SCO2 induction. [START_REF] Matoba | p53 regulates mitochondrial respiration[END_REF] Taken together, p53 could act by nuclear and direct mitochondrial functions to promote oxidative phosphorylation.

While our results suggest that p53 localized in the mitochondrial matrix could optimize oxidative phosphorylation by different activities and at different levels: electron transfert chain and F1F0-ATP synthase, we have not identified the precise molecular mechanisms of action. To determine if the interaction of p53 with OSCP is involved in this process, interaction domains of these two proteins will need to be determined and interaction mutants established. The mitochondrial respiratory chain complexes assemble into higher-order structures called supercomplexes, [START_REF] Schagger | Supercomplexes in the respiratory chains of yeast and mammalian mitochondria[END_REF] which minimize electron leakage during electron transfer between the individual respiratory complexes. These structures therefore prevent ROS generation. [START_REF] Lenaz | Mitochondrial respiratory chain super-complex I-III in physiology and pathology[END_REF] p53 might optimize respiratory chain action via an indirect mechanism. For example, we speculate that p53 could be involved in the organization of the oxidative phosphorylation complexes and favor efficient cooperation between them, since assembly or steady state levels of the F1F0-ATP synthase could influence the organization of others complexes. [START_REF] Wittig | Supramolecular organization of ATP synthase and respiratory chain in mitochondrial membranes[END_REF] Mitochondria are the major site of ROS production. These molecules are important in the redox regulation and in certain signal transductions but an increase in ROS level promotes oxidative stress and causes oxidative damage to nucleic acids, proteins and lipids. Thus, mitochondrial ROS may contribute to DNA damage and consequently to oncogenic transformation. [START_REF] Martindale | Cellular response to oxidative stress: signaling for suicide and survival[END_REF] In addition to nuclear p53, mitochondrial p53 could prevent DNA damage through control of ROS production. Interestingly, some patients suffering from Li-Fraumeni syndrome exhibit an increase of several markers of oxidative stress compared to control. [START_REF] Macedo | Increased oxidative damage in carriers of the germline TP53 p.R337H mutation[END_REF] In addition, Sablina et al. [START_REF] Sablina | The antioxidant function of the p53 tumor suppressor[END_REF] have described that p53 depletion prompts an increase in ROS level, and the appearance of DNA mutation. Finally, it was recently reported that knockin mice expressing a p53 mutant (3KR) that is not able to trigger cell-cycle arrest, senescence or apoptosis are still protected from early tumor formation. [START_REF] Li | Tumor suppression in the absence of p53mediated cell-cycle arrest, apoptosis, and senescence[END_REF] This p53 3KR mutant is still able to regulate ROS production. In the latter two studies ROS regulation by p53 has been associated with its transcriptional activities. [START_REF] Sablina | The antioxidant function of the p53 tumor suppressor[END_REF][START_REF] Li | Tumor suppression in the absence of p53mediated cell-cycle arrest, apoptosis, and senescence[END_REF] Here we have shown that p53 can also regulate ROS generation directly at mitochondria. In sum, these data strongly suggest that ROS regulation by p53 protects the genome from low oxidative stress, which permanently occurs during normal cell homeostasis and seems to be an intrinsic part of p53's tumor suppressor functions.

  Qproteome mitochondria isolation kit were resuspended in PBS supplemented with 1 mM protease inhibitors (Aebsf, Roche). Mitochondrial complexes were solubilized in Native Page Sample Buffer (Invitrogen), supplemented with digitonin (1%) and centrifuged at 20000 g for 30 min at 4°C. The Native Page G-250 Sample Additive (0,1%) was added to samples just before loading onto Blue-Native Page 3-12% polyacrylamide gels (Invitrogen). Oxygen consumption measurement. Cells were harvested, centrifuged and resuspended in DMEM F-12 lacking Glutamax, supplemented with 10% Fetal Bovine Serum. Oxygen consumption was measured using a Clark electrode at 37°C. 1.10 7 cells were transferred in 900 μl of the equilibrated medium into the oxygraphic chamber to record the endogenous oxygen concentration. Rate of oxygen consumption was determined by calculating the linear slope of oxygen concentration in nanomoles of O2 per milliliters per minute. ROS measurement. MitoSOX (Invitrogen) was used to measure the mitochondrial production of superoxide. The MitoSOX reagent is live-cell permeant and is rapidly and selectively targeted to the mitochondria. Once in the mitochondria, MitoSOX Red is oxidized by superoxide and exhibits red fluorescence. Briefly, cells were trypsinized, centrifugated and pellets were resuspended at 1.10 5 cells / ml in culture medium. 5 M MitoSOX were added to the cells placed at 37°C. Red fluorescence was then measured by flow cytometry each 10 min by analyzing 2000 events per experimental condition, during at least 1 hour, in order to check the linearity of fluorescence evolution. The increase of MitoSOX fluorescence (arbitrary unit) / min was then calculated for each condition. Controls using the uncoupling agent mClCCP (250 M) and the electron transport chain inhibitor NaN3 (10 mM) were performed to check the specificity of the reaction: mClCCP and NaN3 respectively increase and inhibit mitochondrial superoxide production and generation of MitoSOX red fluorescence (not shown). Flow cytometric measurements were performed using a XL3C flow cytometer (Beckman-Coulter). Fluorescence was induced by the blue line of an argon ion laser (488 nm) at 15 mW. Red fluorescence was collected with a 620 nm band pass filter.

  established. An immunoblot of H1299-p53-Mx versus pcDNA3 control line confirms low level of p53 expression (Fig.2A, lower left panel). Cellular fractionation and mitochondrial subfractionation were performed to check the intramitochondrial localization of p53 in this cell line. Figure2A(right panel) shows that whole cell lysate (Wcl) contains p53 whereas the fraction containing nuclei and unbroken cells (N*), obtained at the beginning of cellular fractionation, only harbors a small amount of p53. Approximately 5% of cells remained unbroken at this stage, explaining the minor detection of p53 in this fraction as due to contamination by intact cells (data not shown). Compared to Wcl, the fraction enriched in mitochondria (Ctrl) is highly enriched in p53, indicating that p53 is effectively targeted to mitochondria. Controls of mitochondrial purity and enrichment respectively were tested by nuclear lamins, mitochondrial mitofilin and OSCP, indicating that there is good mitochondrial enrichment and a slight contamination by nuclear components. Interestingly, treatment of the mitochondrial fraction by increasing amounts of proteinase K shows no degradation of p53,

Figure 1 .

 1 Figure 1. Endogenous p53 resides in different mitochondrial compartments in unstressed

Figure 2 .

 2 Figure 2. Targeting of p53 to the mitochondrial matrix and intermembrane space in H1299

Figure 3 .

 3 Figure 3. Mitochondrial matrix p53 promotes oxygen consumption and decreases ROS

Figure 4 .

 4 Figure 4.p53 interacts with the OSCP subunit of the F1F0-ATP synthase complex of

Figure 5 .

 5 Figure 5.Knockdown of OSCP results in a decrease of mitochondrial p53 levels.HCT116 p53 +/+ cells were transfected with OSCP siRNA or control siRNA (Ctrl). After 72

Figure 6 .

 6 Figure 6.Mitochondrial p53 increases mature F1F0-ATP synthase steady state levels.

  Figure 1

Acknowledgments

We thank Dr. Jordi Magrané (Department of Neurology and Neuroscience, Weill Medical College of Cornell University, New York, NY 10065, USA) for providing us with the pIRES-cytb2-WTSOD1 plasmid, Dr. Carole H. Sellem (Université Paris-Sud, Centre de Génétique Moléculaire, UPR3404, CNRS, Gif-sur-Yvette, France) to have helped us to perform oxygraphy analysis, and Dr. Alain Guillot (Plate Forme D'Analyse Proteomique de Paris Sud-Ouest INRA, Jouy en Josas, France) for mass spectrometry analysis.

Disclosure of Potential Conflicts of Interest

No potential conflicts of interest were disclosed.


domain: math info

text:
Philippe Moustrou

Helen Naumann

Cordian Riener

Thorsten Theobald

Hugues Verdure

Symme-

SYMMETRY REDUCTION IN AM/GM-BASED OPTIMIZATION

Keywords: Mathematics Subject Classification. 14P05, 20C30, 90C30 Positive functions, SAGE certificates, Symmetry reduction, Symmetric group

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

Deciding whether a real function only takes non-negative values is a fundamental question in real algebraic geometry. Non-negativity certificates and optimization approaches are tightly related to each other by observing that the infimum f * of a function f : R n → R can be expressed as the largest λ ∈ R for which f -λ is non-negative on R n :

f * = inf{f (x) : x ∈ R n } = sup{λ ∈ R : f -λ is non-negative on R n }.
Both in the context of polynomials and in the broader context of exponential sums, the last years have seen strong interest in non-negativity certificates and optimization techniques based on the arithmetic mean/geometric mean-inequality (AM/GM inequality). More precisely, an exponential sum (or signomial ) supported on a finite subset T ⊂ R n is a linear combination α∈T c α exp( α, x ) with real coefficients c α . In particular cases, the non-negativity of the real function defined by an exponential sum can be decided via the arithmetic-geometric mean inequality. For example, for support points α 0 , . . . , α m ∈ R n and coefficients λ = (λ 1 , . . . , λ m ) ∈ R n + satisfying m i=1 λ i = 1 and m i=1 λ i α i = α 0 , the exponential sum m i=1 λ i exp( α i , x ) -exp( α 0 , x ) is non-negative on R n as a consequence of the weighted arithmetic-geometric mean inequality, namely m i=1 λ i exp( α i , x ) m i=1 (exp( α i , x )) λ i . Clearly, sums of such exponential sums are non-negative as well. Note that exponential sums can be seen as a generalization of polynomials: when T ⊂ N n , the transformation x i = ln y i gives polynomial functions y → α∈T c α y α on R n >0 . These AM/GM-based certificates appear to be particularly useful in sparse settings. In the specialized situation of polynomials, they can be seen as an alternative to nonnegativity certificates based on sums of squares. The ideas of these approaches go back to Reznick [START_REF] Reznick | Forms derived from the arithmetic-geometric inequality[END_REF] and have been recently brought back into the focus of the developments by Pantea, Koeppl, and Craciun [START_REF] Pantea | Global injectivity and multiple equilibria in uni-and bimolecular reaction networks[END_REF], Chandrasekaran and Shah [START_REF] Chandrasekaran | Relative entropy relaxations for signomial optimization[END_REF] ("SAGE " cone: sums of arithmetic-geometric exponentials) and Iliman and de Wolff [START_REF] Iliman | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF] ("SONC " cone: sums of non-negative circuit polynomials), see also [START_REF] Katthän | A unified framework of SAGE and SONC polynomials and its duality theory[END_REF] for a generalized, uniform framework. The AM/GM certificates can be effectively obtained by relative entropy programming (see [START_REF] Chandrasekaran | Relative entropy relaxations for signomial optimization[END_REF][START_REF] Chandrasekaran | Relative entropy optimization and its applications[END_REF]), and in restricted settings these relative entropy programs become geometric programs [START_REF] Iliman | Lower bounds for polynomials with simplex Newton polytopes based on geometric programming[END_REF]. These techniques have been extended to cover constrained situations, prominently by the work of Murray, Chandrasekaran and Wierman based on partial dualization [START_REF] Murray | Signomial and polynomial optimization via relative entropy and partial dualization[END_REF]. This method can also be approached from sublinear circuits, see [START_REF] Murray | Sublinear circuits and the constrained signomial optimization problem[END_REF]. Furthermore, in the setting of polynomials, the AM/GM-based approaches can be combined with sums of squares [START_REF] Karaca | The REPOP toolbox: Tackling polynomial optimization using relative entropy relaxations[END_REF]. Other recent approaches to sparse polynomials besides the ones based on the AM/GM inequality can be found in the sparse moment hierarchies [START_REF] Wang | Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension[END_REF][START_REF] Wang | TSSOS: a moment-SOS hierarchy that exploits term sparsity[END_REF].

From an algebraic point of view, a problem is symmetric when it is invariant under some group action. Symmetries are ubiquitous in the context of polynomials and optimization, since they manifest both in the problem formulation and the solution set. This often allows to reduce the complexity of the corresponding algorithmic questions. Regarding the set of solutions, it was observed by Terquem as early as in 1840 that a symmetric polynomial does not always have a fully symmetric minimizer (see also Waterhouse's survey [START_REF] Waterhouse | Do symmetric problems have symmetric solutions?[END_REF]). However, in many instances, the set of minimizers contains highly symmetric points (see [START_REF] Friedl | Reflection groups, reflection arrangements, and invariant real varieties[END_REF][START_REF] Moustrou | Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations[END_REF][START_REF] Riener | On the degree and half-degree principle for symmetric polynomials[END_REF][START_REF] Timofte | On the positivity of symmetric polynomial functions[END_REF]). With respect to problem formulations, symmetry reduction has provided essential advances in many situations (see, for example, [START_REF] Bachoc | New upper bounds for kissing numbers from semidefinite programming[END_REF][START_REF] De Klerk | Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem[END_REF][START_REF] Dobre | Exploiting symmetry in copositive programs via semidefinite hierarchies[END_REF]), especially in the context of sums of squares (see [START_REF] Bachoc | Invariant semidefinite programs[END_REF][START_REF] Blekherman | Symmetric non-negative forms and sums of squares[END_REF][START_REF] Debus | Reflection groups and cones of sums of squares[END_REF][START_REF] Gatermann | Symmetry groups, semidefinite programs, and sums of squares[END_REF][START_REF] Heaton | Symmetry adapted Gram spectrahedra[END_REF][START_REF] Raymond | Symmetric sums of squares over k-subset hypercubes[END_REF][START_REF] Riener | Exploiting symmetries in SDPrelaxations for polynomial optimization[END_REF]).

The current paper departs from the question to which extent symmetries can be exploited in AM/GM-based optimization assuming that the problem affords symmetries. We provide a first systematic study of the AM/GM-based approaches in G-invariant situations under the action of a group G. Our focus is on symmetry-adapted representation theorems, and algorithmic symmetry reduction techniques.

Our contributions. 1. We prove a symmetry-adapted decomposition theorem and develop a symmetry-adapted relative entropy formulation SAGE exponentials in a general G-invariant setting.

2. This adaption reduces the size of the resulting relative entropy programs or geometric programs, see Theorem 3.1, Theorem 4.1 and Corollary 4.3. As revealed by these statements, the gain depends on the orbit structure of the group action.

3. In the case of the symmetric group, we use combinatorial aspects of the representation theory of the symmetric group in order to measure the size of the resulting relative entropy program. In particular, we identify situations in which the size of the symmetry adapted relative entropy program stabilizes with respect to the number of variables.

4. We evaluate the structural results in the paper in terms of computations. In situations with strong symmetry structure, the number of variables and the number of equations and inequalities becomes substantially smaller. Accordingly, the interior-point solvers underlying the computation of SAGE bounds then show strong reductions of computation time. In various cases, the symmetry-adapted computation succeeds when the conventional SAGE computation fails.

We mostly concentrate on the unconstrained optimization, but the techniques can generally also be extended to the constrained case. See, for example, Theorem 4.5.

The paper is structured as follows. After collecting relevant notions and concepts in Section 2, we provide in Section 3 a specific way of writing sums of arithmetic-geometric exponentials in the presence of a group symmetry. In Section 4, we study how to characterize and to decide whether a G-symmetric exponential sum is contained in the SAGE cone with reduced relative entropy programs. The case of the symmetric group is treated in Section 5, while Section 6 provides experimental results of an implementation of the symmetry reduction techniques. We conclude the paper in Section 7.

Acknowledgement. The authors gratefully acknowledge partial support through the project "Real Algebraic Geometry and Optimization" jointly funded by the German Academic Exchange Service DAAD and the Research Council of Norway RCN, and through the Tromsø Research foundation grant agreement 17matteCR.

Preliminaries

Throughout the article, we use the notation N = {0, 1, 2, 3, . . .}. For a finite subset T ⊂ R n , let R T be the set of |T |-tuples whose components are indexed by the set T . We denote by •, • the standard Euclidean inner product in R n .

The SAGE cone. For a given non-empty finite set T , we consider exponential sums supported on T as defined in the Introduction. For finite T ⊂ R n , the SAGE cone C SAGE (T ) is defined as

C SAGE (T ) := β∈T C AGE (T \ {β}, β),
where for A := T \ {β}

C AGE (A, β) := f = α∈A c α e α,x + c β e β,x : c α 0 for α ∈ A, c β ∈ R, f (x) 0 on R n
denotes the non-negative exponential sums which may only have a negative coefficient in the term indexed by β (see [START_REF] Chandrasekaran | Relative entropy relaxations for signomial optimization[END_REF]). The elements in these cones are called SAGE signomials and AGE signomials, respectively. The cone C SAGE (T ) is a closed convex cone in R T (see [START_REF] Katthän | A unified framework of SAGE and SONC polynomials and its duality theory[END_REF]Proposition 2.10]).

Membership to this convex cone can be decided in terms of relative entropy programming. For a finite set

∅ = A ⊂ R n , denote by D : R A >0 × R A >0 → R, D(ν, γ) = α∈A ν α ln ν α γ α
the relative entropy function, which can be extended to R A + × R A + → R ∪ {∞} via the conventions 0 • ln 0 y = 0 for y 0 and y • ln y 0 = ∞ for y > 0. To decide membership of a given signomial f supported on T to the SAGE cone, assume that f is written in the form f =

C SAGE (A, B) := β∈B C AGE (A ∪ B \ {β}, β)
the signed SAGE cone, which allows negative coefficients only in a certain subset B of the support A ∪ B. This a common notation in optimization viewpoints [START_REF] Dressler | Global optimization via the dual SONC cone and linear programming[END_REF][START_REF] Dressler | An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming[END_REF][START_REF] Iliman | Lower bounds for polynomials with simplex Newton polytopes based on geometric programming[END_REF][START_REF] Murray | Newton polytopes and relative entropy optimization[END_REF][START_REF] Murray | Signomial and polynomial optimization via relative entropy and partial dualization[END_REF].

Proposition 2.1 ([20]). A signomial f belongs to C SAGE (A, B) if and only if for every β ∈ B there exist c (β) ∈ R A + and ν (β) ∈ R A + such that α∈A ν (β) α α = ( α∈A ν (β) α )β for β ∈ B, D(ν (β) , e • c (β) ) c β for β ∈ B, β∈B c (β) α c α for α ∈ A.
Note that this proposition reflects the statement of Murray, Chandrasekaran and Wierman [START_REF] Murray | Newton polytopes and relative entropy optimization[END_REF] that every SAGE signomial can be decomposed into AGE signomials in such a way that every term with a negative coefficient only appears in a single AGE signomial.

Optimizing over the SAGE cone. Since the SAGE cone is contained in the cone of non-negative signomials, relaxing to the SAGE cone gives an approximation of the global infimum f * of a signomial f supported on T :

f SAGE = sup{λ ∈ R : f -λ ∈ C SAGE (T )} satisfying f SAGE f * .
Constrained versions. While many aspects of this article are devoted to the unconstrained situation, we briefly collect the extension of SAGE certificates to the constrained situation. Let K be a convex and closed subset of R n . For a convex set K ⊂ R n and a non-empty finite set T ⊂ R n , the K-SAGE cone C K (T ) is defined (see [START_REF] Murray | Signomial and polynomial optimization via relative entropy and partial dualization[END_REF]) as

C K (T ) := β∈T C K (T \ {β}, β),
where for A := T \ {β},

C K (A, β) := f = α∈A c α e α,x + c β e β,x : c α 0 for α ∈ A, c β ∈ R, f (x) 0 on K .
Moreover, (2.1) can be generalized by defining, for disjoint sets

∅ = A ⊂ R n and B ⊂ R n , the signed K-SAGE cone C K (A, B) := β∈B C K (A, β).
This is the set of K-SAGE signomials, where negative coefficients are only possible in a certain subset B of the support A ∪ B. The following decomposition result holds.

Theorem 2.2 ([21], Corollary 5). If f ∈ C K (A, B) with c α > 0 for all α ∈ A and c β < 0 for all β ∈ B = ∅, then there exist K-AGE signomials f β ∈ C K (A, β) for β ∈ B such that f = β∈B f β .
For the constrained approach, a similar result to Proposition 2.1 is known.

Proposition 2.3 ([21]). f ∈ C K (A∪B) if and only if for every β ∈ B there exist c (β) ∈ R A + and ν (β) ∈ R A + such that D(ν (β) , e • c (β) ) + sup x∈K - α∈A ν (β) α (α -β), x c β for β ∈ B, β∈B c (β) α c α for α ∈ A.

Orbit decompositions of symmetric exponential sums

In this section, we provide a structural result on the decomposition of symmetric SAGE exponentials as sums of orbits of (non-symmetric) AGE exponentials.

Let G be a finite group acting linearly on R n on the left, namely we have a group homomorphism ϕ :

G → GL n (R) σ → ϕ(σ) .
For σ ∈ G and x ∈ R n , we denote by σ • x the image of x through ϕ(σ). In order to get a left action on the set of functions defined on R n , we need to take

(3.1) (σ * f )(x) = f (σ -1 • x) = f (ϕ(σ -1 )(x)).
For a signomial f (x) = α c α exp( α, x ), we see an exponent vector α as an element of the dual space. Then, the dual action of G on the exponent vectors is given by

σ ⊥ α := ϕ(σ -1 ) # (α),
where A # denotes the adjoint operator of A. Note that this is a left action as well. Therefore, even if the exponents and the variables lie in isomorphic spaces, the actions of G on these spaces are different and dual to each other, and satisfy

α, σ • x = α, ϕ(σ)(x) = ϕ(σ) # (α), x = σ -1 ⊥ α, x
and furthermore, for a signomial f ,

(3.2) (σ * f )(x) = f (σ -1 • x) = α c α exp( α, σ -1 • x ) = α c α exp( σ ⊥ α, x ).
From now on, in order to keep notations as light as possible, with a slight abuse of notations, we write σ(x) = σ • x for the action on the variables, σf = σ * f for the action on functions, and σ(α) = σ ⊥ α for the dual action. Even if the actions are different, the context should clarify the correspondence. For a set S ⊂ R n of exponent vectors, the orbit of S under G is

G • S = {σ(s) : s ∈ S, σ ∈ G}.
We call a subset Ŝ ⊂ S a set of orbit representatives for S if Ŝ is an inclusion-minimal set with (G • Ŝ) = S. Moreover, let Stab β := {σ ∈ G : σ(β) = β} denote the stabilizer of an exponent vector β.

In the following statements, we consider G-invariant signomials f . It is convenient to write f here in the form

(3.3) f = α∈A c α exp( α, x ) + β∈B c β exp( β, x )
with c α > 0 for α ∈ A and c β < 0 for β ∈ B, i.e., f is an element of the signed SAGE cone C SAGE (A, B) introduced in Section 2. As already mentioned, in this notation, the overall support set of

f is A ∪ B. Theorem 3.1. Let K ⊂ R n be convex and G-invariant, let f be a G-invariant signomial of the form (3.3) and B be a set of orbit representatives for B. Then f ∈ C K (A, B) if and only if for every β ∈ B, there exists a K-AGE signomial h β ∈ C K (A, β) such that (3.4) f = β∈ B ρ∈G/ Stab( β) ρh β .
The functions h β can be chosen to be invariant under the action of Stab( β).

Here, ρ ∈ G/ Stab( β) shortly denotes that ρ runs over a set of representatives of the left quotient space G/ Stab( β), which is defined through the left cosets {σ Stab( β) : σ ∈ G}. We will also use the right quotient space, denoted by Stab( β)\G, further below.

Proof. Since it is clear that a signomial f of the form (3.4) is non-negative, we only have to show the converse direction. Let

f ∈ C K (A, B). By Theorem 2.2, there exist K-AGE signomials f β ∈ C K (A, β) for β ∈ B, such that f = β∈B f β . The G-invariance of f gives (3.5) f = 1 |G| σ∈G σf = 1 |G| σ∈G β∈B σf β .
The idea is to group in this sum all the σf β that have the same "possibly negative" term.

According to (3.2), the possibly negative term of σf β is given by σ(β). For any β ∈ B, the signomial

h β = 1 |G| σ∈G σf σ -1 (β) is a sum of K-AGE signomials in C K (A, β), hence it is contained in C K (A, β) as well.
Moreover, (3.5) can be expressed as Remark 3.2. Note that the previous results extend naturally to compact/reductive groups, since they mainly rely on the existence of a Reynolds operator. For the sake of simplicity, we presented them for finite groups, where the Reynolds operator corresponds to a finite average over the group.

f = 1 |G| σ∈G β∈B σf β = 1 |G| σ∈G γ∈B σf σ -1 (γ) = γ∈B h γ . Let β ∈ B and β ∈ B be the representative of its orbit in B. If σ, τ ∈ G are such that σ( β) = τ ( β) = β, then τ -1 σ ∈ Stab( β) and τ = σ in G/ Stab( β). Hence, f = β∈ B ρ∈G/ Stab β h ρ( β) . (3.6) Now observe that h ρ(β) = ρh β for every β ∈ B and ρ ∈ G, because |G|ρh β = σ∈G ρσf σ -1 (β) = τ ∈G τ f τ -1 ρ(β) = |G|h ρ(β) . ( 3

Symmetry reduction in relative entropy programming

Building upon the previous decomposition theorem, we provide a symmetry-adapted relative entropy formulation for containment in the SAGE cone.

D(ν ( β) , e • c ( β) ) c β for every β ∈ B, (4.2) β∈ B σ∈Stab ( β)\G c ( β) σ(α) c α for every α ∈ A. (4.3)
Remark 4.2. The right coset condition (4.3) can equivalently be expressed in terms of the left cosets,

β∈ B σ∈G/ Stab β c ( β) σ -1 (α) c α for every α ∈ A. Namely, if β ∈ B, β ∈ B and σ, τ ∈ G are such that σ -1 ( β) = τ -1 ( β) = β, then τ σ -1 ∈ Stab( β)
f = β∈ B ρ∈G/ Stab( β) ρh β .
Writing h β in the form

h β = α∈A c ( β) α exp( α, x ) + c β exp( β, x ) with coefficients c ( β)
α and c β for α ∈ A and β ∈ B, the two conditions (4.1) and (4.2) follow from the property h β ∈ C SAGE (A, β). For (4.3), we observe that for α ∈ A, the coefficient

of exp( α, x ) in ρh β is c ( β)
ρ -1 (α) . We obtain inequality (4.3), even with equality, by setting σ := ρ -1 and summing over β ∈ B and over σ ∈ Stab( β)\G, following Remark 4.2. Moreover, the Stab(h β )-invariance of h β implies the Stab( β)-invariance of c ( β) . In order to make ν ( β) invariant under Stab( β), we can replace it with

µ ( β) α = 1 | Stab( β)| σ∈Stab( β) ν ( β) σ(α) .
Obviously, this has no influence on (4.3). For (4.1), we have

| Stab( β)| α∈A µ ( β) α (α -β) = α∈A σ∈Stab( β) ν ( β) σ(α) (α -β) = σ∈Stab( β) σ -1 α∈A ν ( β) σ(α) (σ(α) -σ( β)) = σ∈Stab( β) σ -1 α∈A ν ( β) α (α -β)) = 0.
Finally, for (4.2), using c

( β) α = c ( β)
σ(α) for σ ∈ Stab( β) and applying Jensen's inequality on the convex function x → x ln x gives, for all α ∈ A,

µ ( β) α ln µ ( β) α c ( β) α =   1 | Stab( β)| σ∈Stab( β) ν ( β) σ(α)   ln 1 | Stab( β)| σ∈Stab( β) ν ( β) σ(α) c ( β) α = c ( β) α   σ∈Stab( β) ν ( β) σ(α) /c ( β) σ(α) | Stab( β)| ln σ∈Stab( β) ν ( β) σ(α) /c ( β) σ(α) | Stab( β)|   c ( β) α   1 | Stab( β)| σ∈Stab( β) ν ( β) σ(α) c ( β) σ(α) ln ν ( β) σ(α) c ( β) σ(α)   .
Using again the Stab( β)-invariance of c ( β) and the precondition then yields

α∈A µ ( β) α ln µ ( β) α ec ( β) α 1 | Stab( β)| σ∈Stab( β) α∈A ν ( β) σ(α) ln ν ( β) σ(α) ec ( β) σ(α) 1 | Stab( β)| σ∈Stab( β) c β = c β .
Conversely, assume that c ( β) and ν ( β) , invariant under the action of Stab( β), satisfy (4.1)-( 4

τ (α) = c ( β) σ(α) , ν ( β) τ (α) = ν ( β) σ(α) for α ∈ A.
Thus we can define

c (β) α = c ( β) σ(α) , ν (β) α = ν ( β) σ(α) for α ∈ A, which is independent of σ such that σ(β) = β. As a consequence, if τ ∈ Stab( β)\G, then c (τ -1 ( β)) α = c ( β)
τ (α) is well defined. To see that the first conditions of Proposition 2.1 are satisfied, let

β ∈ B and σ ∈ G such that σ(β) = β. Then α∈A ν (β) α (α -β) = α∈A ν ( β) σ(α) (α -σ -1 ( β)) = σ -1 α∈A ν ( β) σ(α) (σ(α) -β) = σ -1 α∈A ν ( β) α (α -β) = 0 and D(ν (β) , ec (β) ) = D(ν ( β) , ec ( β) ) c β = c β .
For the third condition of Proposition 2.1, we obtain

β∈B c (β) α = β∈ B τ ∈Stab( β)\G c (τ -1 ( β)) α = β∈ B τ ∈Stab( β)\G c ( β) τ (α) c α ,
which altogether shows that f ∈ C SAGE (A, B).

The following consequence of Theorem 4.1 further reduces the number of variables in the relative entropy program, since a certain number of c

ν ( β) α α ∈Stab( β)•α (α -β) = 0 for every β ∈ B, (4.4) α∈A/ Stab( β) Stab( β) • α ν ( β) α ln ν ( β) α ec ( β) α c β for every β ∈ B, (4.5) β∈ B | Stab(α)| | Stab( β)| γ∈(G•α)/ Stab( β) Stab( β) • γ c ( β) γ c α for every α ∈ Â. (4.6)
Proof. For (4.4) and (4.5), equivalence to their versions in Theorem 4.1 is straightforward to check. For (4.6), equivalence to (4.3) follows by observing that for every α ∈ A

σ∈Stab( β)\G c ( β) σ(α) = σ∈Stab( β)\G 1 | Stab( β)| τ ∈Stab( β) c ( β) τ (σ(α)) = 1 | Stab( β)| ρ∈G c ( β) ρ(α) = | Stab(α)| | Stab( β)| γ∈G•α c ( β) γ = | Stab(α)| | Stab( β)| γ∈(G•α)/ Stab( β) Stab( β) • γ c ( β) γ ,
and the last expression only depends on the orbit G • α rather than on α itself.

Remark 4.4. Note that we cannot simply assume c

(β) α = c (β)
α for some α ∈ G • α and, similarly, we cannot simply assume ν

(β) α = ν (β)
α for some α ∈ G•α, for instance due to (2.1). Namely, if an element β lies in conv A with barycentric coordinates λ, say β = α∈A λ α α, then for any σ ∈ G, we have

σ(β) = σ α∈A λ α α = α∈A σ(λ α α) = α∈A λ α σ(α) rather than σ(β) = σ( α∈A λ α α) = α∈A λ σ(α) σ(α).
Of course, this caveat does not occur whenever there is a single inner term.

For symmetric constraint sets K, a constrained version of Theorem 4.1 (and similarly, of Corollary 4.3) can be given as well. The proof is similar.

( β) ∈ R A + such that D(ν ( β) , e • c ( β) ) + sup x∈K - α∈A ν ( β) α (α -β) , x c β for every β ∈ B, β∈ B σ∈Stab β\G c ( β) σ(α)
c α for every α ∈ A.

To close this section we discuss the resulting complexity reduction: Note that the initial relative entropy formulation which does not take the symmetry into consideration will involve 2|B||A| variables. Furthermore, since every vector equality in (4.4) brings n scalar equalities, it will consist of |B|n + |B| + |A| (in)equalities.

In

| Stab(α)\G/ Stab( β)| = 1 | Stab(α)|| Stab( β)| σ∈Stab( α) τ ∈Stab( β) |G σ,τ |,
where |G σ,τ | is the number of elements of G fixed under the action of (σ, τ ). From another point of view, this number can be interpreted in terms of representation theory as follows:

It is given by the inner product of the two characters corresponding to the representations induced respectively by the trivial representations of Stab(α) and Stab( β) on G (see [START_REF] Stanley | Enumerative Combinatorics[END_REF]Exercise 7.77.a.] for more details). Furthermore, (4.4) amounts to | Â| + | B| inequalities, together with one vector equality for every element of B. We observe that for a given β, this vector is invariant by Stab( β) and therefore is contained in (R n ) Stab( β) , the subspace of R n of points fixed by Stab( β). Thus, by projecting onto this subspace the number of resulting equations reduces to dim (R n ) Stab( β) . As a conclusion, we obtain:

The case of the symmetric group

In this section, we focus our attention to the case of the Symmetric group S n acting on R n by permutation of the coordinates:

for σ ∈ S n , x ∈ R n , σ(x) = (x σ -1 (1) , . . . , x σ -1 (n) ).
Note that because the action is orthogonal, the dual action on the exponent vectors is the same. Optimization problems invariant under this action can arise in different contexts naturally, for example, in the context of graph homomorphisms ( [START_REF] Blekherman | Simple graph density inequalities with no sum of squares proofs[END_REF]). This action is very natural, and the theory of representation of the symmetric group is very well understood, and affords strong connections with combinatorics. This connection has been successfully used in several instances to reduce the sizes of optimization problems. In particular it was shown in [START_REF] Riener | Exploiting symmetries in SDPrelaxations for polynomial optimization[END_REF]Theorem 4.7 ] (see also [START_REF] Debus | Reflection groups and cones of sums of squares[END_REF]Theorem 3.21]) that the size of a semi-definite program which certifies if a given symmetric polynomial is a sum of squares is stabilizing once the number of variables is big enough. Similarly to these results we show in Theorem 5.2 an analogous result in the AM/GM setup. This result mainly stems from the fact that the cardinalities appearing in Theorem 4.6 have a combinatorial interpretation in the context of symmetric group actions.

First, up to permutation, every α ∈ R n is of the form

α = (α 1 , . . . , α 1 λ 1 , α 2 , . . . , α 2 λ 2 , . . . , α k , . . . , α k λ k ),
with λ 1 λ 2 . . . λ k > 0 and thus its stabilizer Stab(α) is, up to conjugation, of the form

S λ 1 × • • • × S λ k , so that | Stab(α)| = λ 1 ! • • • λ k !.
The corresponding partition λ = (λ 1 , . . . , λ k ) of n is called the orbit type Λ(α) of α. We then denote by len(α) the length of this partition, namely len(α) = k. Consequently, for β ∈ B, the dimension n β of the fixed subspace (R n ) Stab( β) is precisely len( β). Furthermore, let α ∈ Â of orbit type Λ(α) = (λ 1 , . . . , λ k ), and β ∈ B of orbit type Λ(β) = (µ 1 , . . . , µ ). Then, the interpretation of α(S n ) β as the inner product of characters gives a combinatorial understanding of the number α(S n

) β = | Stab(α)\S n / Stab( β)|: it is given by the number N Λ(α),Λ(β) = |M Λ(α),Λ(β) |, where M Λ(α),Λ(β)
is the set of matrices of size k × with non-negative integer coefficients such that, for 1 i k the elements of the ith row sum up to λ i , and for 1 j the elements of the jth column sum up to µ j . This quantity can be alternatively computed by using the so-called Kostka numbers defined for pairs of partitions. More precisely, we have

α(S n ) β = N Λ(α),Λ(β) = µ K µ,Λ(α) K µ,Λ(β) ,
where µ runs through the partitions of n. For more details about these interpretations, see [START_REF] Stanley | Enumerative Combinatorics[END_REF]Chapter 7], in particular Corollary 7.12.3 therein. Now we illustrate the potential gain of this reduction, already in a very small example:

Example 5.1. Consider the support set {α 0 , . . . , α 7 } = {(0, 0, 0) T , (7, 0, 0) T , (0, 7, 0) T , (0, 0, 7) T , (1, 1, 2) T , (1, 2, 1) T , (2, 1, 1) T , (2, 2, 2) T } and let G := S 3 be the symmetric group on three elements. In order to avoid too heavy notation, we will write c (i)

j instead of c (α i ) α j and ν (i) j instead of ν (α i ) α j . Consider a signomial f (x 1 , x 2 , x 3 ) = 7 i=0 c i e α i ,(x 1 ,x 2 ,x 3 ) , with c 0 , c 1 , c 2 ,
3 ), ν (4) = (ν

(4) 0 , ν (4) 1 , ν (4)
3 ),

In the context of the symmetric group it is natural to consider situations in which the number of variables grows. Such situations were studied for example in the context of sums of squares relaxations. Several examples were observed in which the complexity of the symmetry-adapted semi-definite program is independent of the number of variables. Analogously, we now describe natural sequences of signomials where the size of the relative entropy program stabilizes when the number of variables is large enough.

Fix n 0 ∈ N and start with a signomial f n 0 in n 0 variables, represented by the orbit representatives of the exponent vectors  and B, as well as the corresponding coefficients. For each of these exponents α, we denote by Λ(α) the orbit type of α where we forget about the 0 entries. For instance, when n 0 = 3,  = {α} = {(1, 1, 2)} and B = { β} = {(0, 0, 1)}, then Λ(α) = (2, 1) while Λ( β) = (1). Note that these sequences do not have to be partitions of n, we therefore introduce wt

(α) = λ∈ Λ(α) λ,
counting the number of non-zero coordinates of α, and refer to it as the weight of α. Hence wt(1, 1, 2) = 3, while wt(0, 0, 1) = 1. Now, for every n n 0 , we can see α as an exponent in R n , by adding n -n 0 zeroes. This procedure does not affect Λ(α) and wt(α). In this way, we can define for every n > n 0 , the unique S n -invariant signomial f n whose support is made of the S n -orbits of  and B with the corresponding coefficients. Clearly, in this situation, the number of constraints C n in Corollary 4. Then, for every n 2m, V n = V 2m .

Proof. We shall show by induction that for every n 2m, V n = V 2m . The initial step being obvious, assume n > 2m. The definition of m ensures that for n ≥ 2m, for every α in  ∪ B, the coordinate occurring the most in α is 0, and therefore

Λ(α) = (n -wt(α), λ 1 , . . . , λ k ),
where (λ 1 , . . . , λ k ) = Λ(α). Remember that the number of variables is given by

V n = 2 α∈ Â, β∈ B N n Λ( α),Λ( β) ,
where, if Λ(α) = (n-wt(α), λ 1 , . . . , λ k ) and Λ( β) = (n-wt( β), µ 1 , . . . , µ ), the quantity N n Λ( α),Λ( β) counts the number of matrices of size (k + 1) × ( + 1) with non-negative integer coefficients of the form (5.1)

n -wt( β) µ 1 µ 2 . . . µ         • • • . . . • n -wt(α) • • • . . . • λ 1 . . . . . . . . . . . . . . . . . . • • • . . . • λ k
where the labels give the sum of the coefficients in the corresponding row/column. Since  and B keep the same number of elements, we only need to show that for every α ∈ Â, β ∈ B, then

N n Λ( α),Λ( β) = N n-1 Λ( α),Λ ( β)
. If we start with a matrix of the form (5.2)

n -1 -wt( β) µ 1 µ 2 . . . µ         • • • . . . • n -1 -wt(α) • • • . . . • λ 1 . . . . . . . . . . . . . . . . . . • • • . . . • λ k
, adding 1 to the top left coefficients provides a matrix of the form (5.1), wich proves

N n Λ( α),Λ ( β)
N n-1 Λ( α),Λ( β) . In order to show the reverse inequality, we claim that the top left coefficient in (5.1) cannot be 0. Indeed, if it is 0, then the sum of the coefficients in the first row is at most

µ 1 + µ 2 + . . . + µ = wt( β).
This implies n -wt(α) wt( β), which forces n 2m and gives a contradiction. Now, if the top left coefficient is a positive integer, substracting 1 to this coefficient provides a matrix of the form (5.2), which proves N n Λ( α),Λ( β)

N n-1 Λ( α),Λ( β) , and hence

V n = V n-1 .
Building on this, we can actually show that for a large class of problems we have a stabilization. for every α, β satisfying the conditions of the theorem. This will be done in two steps. First, we show that if λ = (λ 1 , . . . , λ t , 1) is a partition, and λ = (λ 1 , λ 2 , . . . , λ t-1 , λ t + 1), then for every partition µ, we have

N λ ,µ N λ,µ and N µ,λ N µ,λ .
Indeed, there is a surjection from the set M λ ,µ onto M λ,µ . Namely let (x 1 , . . . , x k ) denote the t-th line of an element in M λ,µ . Let s be such that x s > 0. Replacing the t-th line of this element by (x 1 , . . . , x s-1 , x s -1, x s+1 , . . . x k ) and inserting (0, . . . , 0, 1, 0, . . . , 0) as the (t + 1)-th line we get an element in N λ ,µ . By applying this procedure recursively for rows and columns we get the inequality in (5.3).

To show the equality in (5.3), observe that the top-left element of N (n-w,1 w ),(n-w,1 w ) has to be an integer k between n -2w and n -w. For every such choice, we have to distribute n-w-k ones in the first row and first column. This gives w n-w-k 2 possibilities. Restricted to the w × w lower right submatrix, these selected lines and columns contain only 0. For each of these possibilities, after removing these chosen lines and columns, we get an (n -k) × (n -k) matrix which contains exactly one 1 per line and column. There are (n -k)! such matrices. By a change of the index variable, we get the desired result:

V n =2 α∈ Â β∈ B α(S n ) β = 2 α∈ Â β∈ B N Λ(α),Λ(β) ≤ 2lku(w).
We conclude this section by giving explicit estimates on the signomials where | B| = 1, and  = {0, α}. We have chosen four different classes of examples that show the influence of the sizes of the orbits on the numbers of variables and constraints. These classes represent extremal situations, namely when the orbits are either very large or very small. In these situations, we can actually compute the exact number of variables and constraints in both cases according to the previous discussions. Note that the last case falls into the framework of Theorem 5.2, where wt(α) = wt( β) = 1. There is also a stabilization in the first sequence: when len( β) = 1, for every α ∈ Â, the number of variables α(S n ) β is equal to 1. The subsequent table summarizes our analysis. Specific signomials realizing the cases are given in Examples 6.1-6.4 in the next section.

Standard method

Symmetric method

|S n • β| |S n • α| V n C n V n C n Example 1 n! 2n! + 3 n! + n + 2 5 4 6.1 n! n 2(n + 1)n! + 1 (n + 1)(n! + 1) 2n + 3 n + 3 6.2 n! n! 2(n! + 1)n! + 1 n!(n + 2) + 1 2n! + 3 n + 3 6.3 n n 2n(n + 1) + 1 (n + 1) 2 7 5 6.4
Table 1. Comparison of the parameters when  = {0, α} and B = { β}.

Numerical experiments

To illustrate the previous considerations, we present in this section classes of examples that spotlight the computational gains by the comparison of calculation times in the case of the symmetric group. For these computations, we used the ECOS solver and Python 3.7 on an Intel(R) Xeon(R) Platinum 8168 CPU with 2.7 GHz and 768 GB of RAM under CentOS Linux release 7.9.2009. Keeping the previous notation, for the standard method, that is the method that does not exploit the symmetries, the input consists of A, B as well as the coefficients, while for the symmetry-adapted version, the input is Â, B and the coefficients. This difference of input is mainly due to practical considerations and does not in itself influence the comparison of the time used by the solver. When both methods give an answer, the bounds coincide.

In all the tables in the sequel, dim is the dimension, V n and C n are the number of variables and constraints of the program, while t s and t r denote the solver time and the overall running time (including the building of the optimization program) in seconds. While it might happen that the standard method is slightly faster for very small instances, the size growth of the program in the standard method makes it quickly unsolvable. In that case this is represented by "-" in the table. The symmetric approach allows however to go further, and we give all the results until the solver warns about a possible inaccuracy. In this case, we mark the bound with " * ".

The first four examples give numerical results for each of the classes discussed in Table 1. We tried to choose the coefficients in a way that avoids numerical issues, namely preventing the bound to be either too small or too large.

n .

Example 6.2. Consider now the signomial

f (2) n = (n -1)! n i=1 exp(n 2 x i ) - σ∈Sn σ exp( β, x ),
where β = (1, 2, . . . , n) (and α = (n 2 , 0, . . . , 0)). The numerical results are shown in Table 3.

Standard method Symmetric method

dim bound V n C n t s t r V n C n t s t r 2 -
n .

Example 6.4. Finally, we consider the case where both orbits are small. Let 5.

Standard method

n .

Example 6.5. Finally, we give an example where A and B consist of two orbits each: Â = {(n 2 , 0, . . . , 0), (1, 4, . . . , n 2 )} and B = {(1, . . . , 1), (1, 2, . . . , n)}.

In this case, we are still able to compute the number of constraints and the number of variables. With the standard approach, V n = 2(n! + n + 1)(n! + 1) + 1, C n = (n! + 1)(n + 2) + n, while using symmetries, V n = 2n! + 2n + 9, C n = n + 6.

Conclusion and open questions

We have developed techniques to exploit symmetries in AM/GM-based optimization and confirmed their benefit in terms of computational results. In particular, in the case of symmetric signomials, we showed that both theoretically as well as practically our orbit reduction allow for substantial computational gains. This motivates a theoretical study of the strength of the AM/GM bounds in this framework. In particular, it encourages the comparison of the symmetric SAGE cones with respect to the cone of symmetric non-negative signomials.

α∈A c α

  exp( α, x ) + β∈B c β exp( β, x ) with c α > 0 for α ∈ A and c β < 0 for β ∈ B. In this notation, the overall support set of f is T = A ∪ B. Accordingly, for disjoint sets ∅ = A ⊂ R n and B ⊂ R n , it is convenient to denote by (2.1)

. 7 )

 7 Substituting (3.7) into (3.6) gives f = β∈ B ρ∈G/ Stab β ρh β as desired. Moreover, the Stab( β)-invariance of h β for β ∈ B follows from (3.7).

Theorem 4 . 1 .

 41 Let B be a set of orbit representatives for B. A G-invariant signomial f of the form (3.3) is contained in C SAGE (A, B) if and only if for every β ∈ B there exist c ( β) ∈ R A + and ν ( β) ∈ R A + , invariant under the action of Stab( β), such that α∈A ν ( β) α (α -β) = 0 for every β ∈ B, (4.1)

  and τ = σ in the right quotient space Stab( β)\G. Proof of Theorem 4.1. If f is G-symmetric, then, by Theorem 3.1, there exist Stab( β)invariant AGE signomials h β ∈ C SAGE (A, β) for every β ∈ B such that

  .3). Let β ∈ B and β ∈ B be the representative of its orbit in B. If σ, τ ∈ G are such that σ(β) = τ (β) = β, then τ σ -1 ∈ Stab( β) and τ = σ in Stab( β)\G. Since c ( β) and ν ( β) are invariant under Stab( β), we have c ( β)

α.Corollary 4 . 3 .

 43 are actually equal, and we can take each c ( β) , ν( β) in the ground set R A/ Stab( β) + Let  and B be a set of orbit representatives for A and B. A G-invariant signomial f of the form (3.3) is contained in C SAGE (A, B) if and only if for every β ∈ B there exist c ( β) ∈ R A/ Stab( β) + and ν ( β) ∈ R A/ Stab( β) + such that α∈A/ Stab( β)

Corollary 4 . 5 .

 45 Let K ⊂ R n be convex and G-invariant. A G-invariant signomial f of the form (3.3) is contained in C K (A, B) if and only if for every β ∈ B there exist c ( β) ∈ R A + and ν

  contrast, let us analyze the number of variables and constraints involved in the relative entropy program in Corollary 4.3. Observe that A/ Stab( β) is the disjoint union of the G • α/ Stab( β) where α runs through Â. It follows that for every pair β ∈ B, α ∈ Â, we have exactly 2|(G • α)/ Stab( β)| variables c ( β) γ and ν ( β) γ . By definition, |(G • α)/ Stab( β)| is the number of Stab( β)-orbits in G • α. Since G • α is in bijection with Stab α\G we get a bijection between (G • α)/ Stab( β) and the set of double cosets Stab(α)\G/ Stab( β). Therefore, the number of orbits in question equals | Stab(α)\G/ Stab( β)|, satisfying, according to Burnside's Lemma (see for instance [28, Lemma 7.24.5]):

Theorem 4 . 6 .

 46 Let  and B be a set of orbit representatives for A and B. For α ∈ Â, β ∈ B, denote by αG β the cardinality | Stab(α)\G/ Stab( β)|, and by n β the dimension of the fixed subspace (R n ) Stab( β) . Then, the relative entropy program in Corollary 4.3 consists of 2 α∈  β∈ B αG β variables, β∈ B n β scalar equalities, and | Â| + | B| inequalities.

c 3 >

 3 0 and c 4 , c 5 , c 6 , c 7 < 0, i.e., set A = {α 0 , . . . , α 3 }, B = {α 4 , . . . , α 7 }. Then  = {α 0 , α 1 } and B = {α 4 , α 7 } are sets of orbit representatives. The corresponding partitions are Λ(α 0 ) = Λ(α 7 ) = (3), and Λ(α 1 ) = Λ(α 4 ) = (2, 1). Then, by Corollary 4.3, f ∈ C SAGE (A, B) if and only there exist c (4) = (c

  3 does not depend on n, since it only involves | B|, | Â|, and the length of the elements in B, which does not change when n n 0 + 1. In this framework, a similar phenomenon holds for the number of variables: Theorem 5.2. Let n 0 ∈ N, and Â, B be finite orbit representatives of exponent vectors in R n 0 . Consider, for n n 0 , the signomial f n previously defined, and denote by V n the number of variables in the symmetry-adapted relative entropy program in Corollary 4.3. Let m = max{wt(α) : α ∈ Â ∪ B}.

Theorem 5 . 3 .

 53 Let k, l, w ∈ N be fixed. Then for every integer n 2w and every S ninvariant signomial f ∈ C(A, B) with | Â| k, | B| l, and max γ∈ Â∪ B wt(γ) w, the number of constraints and the number of variables of the symmetry adapted program are bounded by constants only depending on k, l and w: C n k + l + l(w + 1) and V n 2lku(w), Let us begin with the number of constraints. This follows from Theorem 5.2, because | Â| k, | B| l and n β w + 1, since wt( β) w. As in the previous proof, we have Λ(α) 1 = n -wt(α) and similarly for β. For the number of variables, we will show that (5.3) N Λ( α),Λ( β) N (n-w,1 w ),(n-w,1 w ) = u(w)

Example 6 . 1 .σ

 61 Consider first the signomial f exp( α, x ) -exp( β, x ), where β = (1, . . . , 1) and α = (1, 2, . . . , n). The numerical results are shown in

  n -1)(x 1 + • • • + x n ) + x i ),(β = (n, n -1, n -1, . . . , n -1) and α = (n 2 , 0, . . . , 0)). The numerical results are shown in Table

Table 2 .

 2

				Standard method		Symmetric method
	dim bound	V n	C n	t s	t r	V n C n	t s	t r
	2	-0.1481	7	6	0.0113	0.0121 5 4 0.0147 0.0158
	3	-0.2499	15	11	0.0148	0.0160 5 4 0.0149
	4	-0.3257	51	30	0.0304	0.0337 5 4 0.0139 0.0147
	5	-0.3849	243	127	-	-	5 4 0.0140 0.0147
	6	-0.4327	1443 728	-	-	5 4 0.0136 0.0144
	7 -0.4724 * 10083 5049	-	-	5 4 0.0211 0.0222

Table 2 .

 2 Numerical results for f

Table 3 .

 3 Numerical results for f Example 6.3. Next, we consider the case where both orbits are of maximal size. Let = (1, 2, . . . , n) and α = (2, 8, . . . , 2n 2 ).The numerical results are shown in Table4.

		0.2109	13	9	0.0173	0.0185 7 5 0.0297 0.0311
	3 -0.8888	49	28	0.0427	0.0454 9 6 0.0248 0.0264
	4	-4.111	241	125	0.152	0.1701 11 7 0.0296 0.0318
	5	-22.30	1441	726	0.7888	0.8433 13 8 0.0356 0.0384
	6	-141.0	10081	5047	5.422	5.843	15 9 0.0423 0.0458
	7	-1024	80641	40328	57.26	66.67	17 10 0.0491 0.0538
	8	-8418	725761	362889 1514	2211	19 11 0.0568 0.0626
	9	-77355 7257601 3628810	-	-	21 12 0.0661 0.0835
	10		79833601 39916811	-	-	23 13	-	-
						(2)

n .

Table 4 .

 4 Numerical results for f

Table 5 .

 5 Numerical results for f

	Symmetric method

Table 6

 6 shows the numerical results for the signomials = (1, 4, . . . , n 2 ) and β = (1, 2, . . . , n).

	g n =	1 n	n i=1	exp(n 2 x i ) +	1 n
							Standard method	Symmetric method
	dim bound	V n		C n	t s	t r	V n C n	t s	t r
	2 -0.1918	31		14	0.0272	0.0292	17	8 0.0738 0.0776
	3 -0.5223	141		38	0.0679	0.0727	27	9 0.0623 0.0663
	4		-2.118	1451		154	-	-	65 10 0.1436 0.1539
	5		-10.45	30493	852	-	-	259 11 0.5856 0.6320
	6				1048335 5774	-	-	1461 12	-	-

σ∈Sn σ exp( α, x ) -exp(x 1 + • • • + x n ) -1 n σ∈Sn σ exp( β, x )

for α

Table 6 .

 6 Numerical results for g n .

+ 1 + 2 + 2 = 7 linear constraints, against 2 • 4 • 4 =

variables and 4 • 3 + 4 + 4 = 20 linear constraints forgetting about symmetries.

c (7) = (c [START_REF] De Klerk | Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem[END_REF] 0 , c [START_REF] De Klerk | Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem[END_REF] 1 ) and ν (7) = (ν [START_REF] De Klerk | Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem[END_REF] 0 , ν [START_REF] De Klerk | Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem[END_REF] 1 ) satisfying the conditions ν

Note that here len(α 4 ) = 2 and len(α 7 ) = 1 so that the two vectorial equations bring together 2 + 1 scalar equations. In total, we get 2(1 + 1 + 2 + 1) = 10 variables and