Lluis Vanessa Fritz

Lluis Fajas
email: lluis.fajas@inserm.fr.

Metabolism and proliferation share common regulatory pathways in cancer cells

Keywords: cancer Metabolism, proliferation and cancer Cancer, Metabolism, Oncogenes, Cell-Cycle regulators, Glycolysis, de novo Lipogenesis. Metabolism, proliferation and cancer Fritz and Fajas

Metabolism and proliferation share common regulatory

pathways in cancer cells.

Introduction

Over the past decades, accumulating evidence of a metabolic reorganization during cancer development has emerged from studies on various tumor types. We present herein the view that participation of cell-cycle regulators and oncogenic proteins to cancer development extend beyond the control of cell proliferation, and discuss how these new functions may be implicated in metabolic alterations concomitant to the pathogenesis of human cancers. This is consistent with the observation that changes in metabolism are part of a coordinated response of the cell to distinct physiological and pathological conditions. In mammalian cells the metabolic response requires a permanent coordination of cell activity, including cell proliferation with nutrient availability, hormonal and stress signaling and with regulation of energy homeostasis. This links external signaling events with the activation or inhibition of particular metabolic pathways, such as oxidative or glycolytic metabolism, and biosynthetic processes. Nutrient availability enables nucleic acid, protein, and lipid synthesis to promote cell growth and proliferation. It is also correlated with increased glycolytic flux, and decreased oxidative metabolism [START_REF] Jezek | Distinctions and similarities of cell bioenergetics and the role of mitochondria in hypoxia, cancer, and embryonic development[END_REF]. On the opposite, nutrient deprivation implicates a metabolic switch that triggers energy production pathways, such as oxidative phosphorylation that restrict cell proliferation. In general, cell proliferation and metabolism are tightly linked cellular processes. In non-proliferating cells from differentiated tissues, catabolic metabolism is predominantly used to fuel energetic needs, and is associated to preferential use of mitochondrial oxidative phosphorylation (OXPHOS) with oxidation of macromolecules. In sharp contrast, in tissues with high proliferative rate, bioenergetics resources and biosynthetic pathways are reorganized to allow cell cycle progression, leading to a shift toward an anabolic metabolism, with high glycolytic flux, lactate production and biosynthesis of macromolecules. Several physiopathological conditions are indeed characterized by a switch from an oxidative to a glycolytic metabolism. This is the case for developmental processes, tissue regeneration, intensive exercise, or immune response. In a pathological context, it is currently well established that cancer growth and invasion also involves major alterations of cells' metabolism. A common regulatory pathway exists therefore between cell proliferation and metabolism to insure a coordinated cellular response. 4 This supports the hypothesis, which we develop in this review that the same factors that trigger proliferation, such as oncogenes or cell cycle regulators are indeed coordinators of the metabolic response of the cells to the external stimuli.

Metabolic changes in cancer: the contribution of lipids metabolism

One of the first identified biochemical hallmark of cancer cells were changes in metabolism. Early in the last century, Otto [START_REF] Warburg | Metabolism of Tumors[END_REF] observed that tumor cells have a higher rate of glucose metabolism than their normal counterparts and preferentially use glycolysis instead of OXPHOS even under appropriate oxygen concentrations [START_REF] Warburg | Metabolism of Tumors[END_REF], Warburg 1956a[START_REF] Warburg | On respiratory impairment in cancer cells[END_REF]. Since this first observation, the « aerobic » glycolysis switch has been detected in many tumor types and cumulating studies on various proliferating cells have led to the evidence of a global metabolic reorganization concomitant to cancer progression. Most tumor cells are characterized by higher rates of glycolysis, lactate production, and macromolecules and lipids biosynthesis [START_REF] Kroemer | Tumor cell metabolism: cancer's Achilles' heel[END_REF]Pouyssegur 2008, Vander Heiden et al 2009). During aerobic glycolysis, glucose is converted to pyruvate, and the final sub-product of this reaction is lactate, which is exported out of the cell, contributing to extracellular acidification. The preferential use of aerobic glycolysis offers several advantages to highly proliferating cells, concerning both bioenergetics and biosynthetic requirements. First, it allows for the use of the most abundant extracellular nutrient, which is glucose. Second, the flux of ATP can exceed that produced during OXPHOS. Third, it is likely that one of the critical roles of aerobic glycolysis in cancer cells is to provide essential metabolic intermediates for biosynthesis of macromolecules (lipids, proteins and nucleic acids) in order to support increased proliferation [START_REF] Bauer | ATP citrate lyase is an important component of cell growth and transformation[END_REF].

Increased de novo fatty acids (FA) synthesis, or lipogenesis, is considered as another major metabolic alteration of cancer cells [START_REF] Medes | Metabolism of neoplastic tissue. IV. A study of lipid synthesis in neoplastic tissue slices in vitro[END_REF][START_REF] Sabine | Control of lipid metabolism in hepatomas: insensitivity of rate of fatty acid and cholesterol synthesis by mouse hepatoma BW7756 to fasting and to feedback control[END_REF]. Figure 1 summarizes the participation of lipids and carbohydrates metabolism in cancer development and progression. Although de novo FA synthesis is very active during embryogenesis, most adult normal cells and tissues, even those with high cellular turnover, preferentially use circulating FA for the synthesis of new structural lipids. In contrast, various tumors and their 5 precursor lesions, undergo exacerbated endogenous FA biosynthesis irrespective of the levels of extracellular lipids [START_REF] Medes | Metabolism of neoplastic tissue. IV. A study of lipid synthesis in neoplastic tissue slices in vitro[END_REF]. The increased lipogenesis in cancer is reflected in over expression and hyperactivity of lipogenic enzymes such as ATP citrate lyase (ACL), acetyl-CoA carboxylase (ACC), or the fatty acid synthase (FAS) [START_REF] Kuhajda | Fatty-acid synthase and human cancer: new perspectives on its role in tumor biology[END_REF]. ACC carboxylates acetyl-CoA to form malonyl-CoA, which is further converted to long-chain FA by FAS. Interestingly, studies with chemical inhibitors have revealed that inhibition of FAS activity results in decreased proliferation and increased apoptosis of cancer cells [START_REF] Kuhajda | Fatty acid synthesis: a potential selective target for antineoplastic therapy[END_REF][START_REF] Kuhajda | Fatty-acid synthase and human cancer: new perspectives on its role in tumor biology[END_REF]). De novo FA biosynthesis is required for cancer cells to synthesize new membranes, which have a particular lipidic composition that facilitates the formation of lipid rafts for increased signaling of cell growth receptors. Some lipid synthesis intermediates, such as malonyl CoA participate in the transcriptional regulation of growth factor receptors (reviewed in [START_REF] Menendez | Fatty acid synthase and the lipogenic phenotype in cancer pathogenesis[END_REF]. Moreover, circulating lipids impact on cell cancer growth, migration, and invasion. This is the case for the lysophosphatidic acid (LPA), which signals through LPA receptors to stimulate cancer cell proliferation and survival [START_REF] Bauer | ATP citrate lyase is an important component of cell growth and transformation[END_REF]. Enhanced lipogenesis in cancer cells has also been proposed to be required to balance the redox potential via the utilization of NADPH [START_REF] Porstmann | A new player in the orchestra of cell growth: SREBP activity is regulated by mTORC1 and contributes to the regulation of cell and organ size[END_REF]. In addition, de novo FA synthesis in cancer cells facilitates the production of lipids that will regulate the activity of various oncogenes. Indeed, signaling lipids, such as phosphatidyl inositol, phosphatidyl serine, or phosphatidyl coline, are recognized to be important factors that activate and mediate proliferative and survival pathways, notably the PI3K/AKT, Ras, or Wnt pathways [START_REF] Nadolski | Protein lipidation[END_REF]. Finally, post-translational modification with lipid moieties is also a key process regulating transport and function of various cellular and secreted oncoproteins.

Indeed, several studies have demonstrated that fatty acid synthesis facilitates the formation of particular fatty acids that modify the protein structure of a particular set of oncogenes, such as Ras, Src, or Wnt. This in turn facilitates the activation of their oncogenic pathways [START_REF] Nadolski | Protein lipidation[END_REF]Linder 2007, Xue et al 2004). These findings highlight the relevance of lipid synthesis in oncogenesis and fully support the investigation of lipid synthesis inhibitors as anti-cancer agents.

6

Cell cycle, transcription factors, and oncogenes, as dual proliferation-metabolism regulators.

Increasing evidence support the symmetrical effects of oncogenes and cell cycle regulators on metabolic pathways. Uncontrolled cell growth is an invariable characteristic of human cancer that implies well-documented genetic alterations of the cell cycle regulators, particular transcription factors and oncogenes. Importantly, beside their well-known role in controlling cell proliferation increasing evidence points to these factors as crucial regulators of cell metabolism. It is likely that oncogenic and proliferative factors not only control proliferation and spread of cancer cells, but also concomitantly trigger an adapted metabolic response of these cells. This is illustrated in figure 2, and will be discussed below.

Cell cycle regulators

Cell cycle progression is a tightly regulated process that support cell proliferation during normal growth and development. It involves the coordinated action of many regulatory proteins that comprises the retinoblastoma tumor suppressor family (pRB, p107, p130), the cyclin dependent kinases (cdks) and their regulatory partners the cyclins (cyc), as well as the family of the cdk inhibitors (CKI). Members of E2F transcription factors (E2F1-8) family play pivotal role in regulating survival and proliferation, by conferring cell-cycle specific expression to promoters containing E2F-binding sites, which concern many genes involved in cell-cycle progression [START_REF] Helin | Regulation of cell proliferation by the E2F transcription factors[END_REF]. Indeed, E2F activity is essential for transactivation of genes that regulate the onset of S phase, such as c-Myc and cyclin E, DNA replication and mitosis. When they do not function as free heterodimers with DP1 or DP2, E2Fs exist in repressive association with members of the pRB family that actively inhibit E2F transactivation through the recruitment of histones deacetylases [START_REF] Brehm | Retinoblastoma protein recruits histone deacetylase to repress transcription[END_REF][START_REF] Magnaghi-Jaulin | Retinoblastoma protein represses transcription by recruiting a histone deacetylase[END_REF] and lysine/Arginine methyl-transferases [START_REF] Fabbrizio | Negative regulation of transcription by the type II arginine methyltransferase PRMT5[END_REF].

The subsequent phosphorylation of retinoblastoma proteins by the cyclins-cdks complexes releases E2F, allowing transcription of its target genes and cell cycle progression trough the G1/S phase [START_REF] Dimova | The E2F transcriptional network: old acquaintances with new faces[END_REF].

7

E2F activity is commonly increased in numerous human cancers, including glioblastoma, lung, ovarian, breast, stomach and colon cancers [START_REF] Chen | Emerging roles of E2Fs in cancer: an exit from cell cycle control[END_REF] and much evidence support an oncogenic role for E2F1-3. It is clear that the increased expression of E2Fs contributes to the uncontrolled proliferation of cancer cells, although a specific role of E2Fs in the deregulation of cancer cell metabolism cannot be ruled out. There is compelling evidence for an E2F-RB specific effect in metabolism. This includes a recent observation implicating RB in the control of oxidative metabolism in adipose tissue [START_REF] Dali-Youcef | Adipose tissue-specific inactivation of the retinoblastoma protein protects against diabesity because of increased energy expenditure[END_REF]. In addition, we previously demonstrated that cell cycle regulators participate in lipids metabolism. We showed that E2Fs regulate adipogenesis through modulating the expression of the nuclear receptor PPARγ, which is a master regulator of adipogenesis [START_REF] Fajas | E2Fs regulate adipocyte differentiation[END_REF]. Similarly, we have documented the adipogenic role of Cyclin D3 [START_REF] Sarruf | Cyclin D3 promotes adipogenesis through activation of peroxisome proliferator-activated receptor gamma[END_REF], cdk4 [START_REF] Abella | Cdk4 promotes adipogenesis through PPARgamma activation[END_REF] and cdk9 [START_REF] Iankova | Peroxisome proliferator-activated receptor gamma recruits the positive transcription elongation factor b complex to activate transcription and promote adipogenesis[END_REF] through their positive regulation of PPARγ activity. At the opposite, we found that PPARγ activity and adipocyte differentiation are repressed by RB through the recruitment of HDAC3 (Fajas et al 2002a).

Although no gross abnormalities were originally observed in E2F1-/-mice [START_REF] Field | E2F-1 functions in mice to promote apoptosis and suppress proliferation[END_REF][START_REF] Yamasaki | Tumor induction and tissue atrophy in mice lacking E2F-1[END_REF], a first evidence for a role of E2F1 in regulating glucose homeostasis came from the observation that E2F1-/-mice present impaired postnatal pancreatic growth and dysfunctional β-cells associated with defective insulin secretion and glucose intolerance [START_REF] Fajas | Impaired pancreatic growth, beta cell mass, and beta cell function in E2F1 (-/-)mice[END_REF]. Furthermore, the observation that E2F1 was robustly expressed in non-proliferating β-cells suggested a role for E2F1 in pancreatic β-cells, independent to the control of proliferation. This hypothesis was demonstrated showing that the CDK4-pRB-E2F1 pathway mediates the transcriptional response to glucose regulating the expression of genes such as Kir6.2, a key component of the K ATP channel involved in the regulation of glucose-induced insulin secretion [START_REF] Annicotte | The CDK4-pRB-E2F1 pathway controls insulin secretion[END_REF]. This role of E2F1 seems to be specific of this E2F-family member, since no major metabolic phenotype has been observed in other E2F-/-mice. E2F2 could however partially compensate E2F1 deficiency. Indeed E2F1-2-/-mice are diabetic, but contribution of E2F2 is likely related to its role in bone marrow-derived cells [START_REF] Iglesias | Diabetes and exocrine pancreatic insufficiency in E2F1/E2F2 double-mutant mice[END_REF][START_REF] Li | The development of diabetes in E2f1/E2f2 mutant mice reveals important roles for bone marrowderived cells in preventing islet cell loss[END_REF]. Recent data suggest, in addition, that E2F1 is involved in the control of several other metabolic processes. In a

Metabolism, proliferation and cancer

Fritz and Fajas 8 genome-wide studies approach, a cohort of genes that are involved in mitochondrial function were identified among E2F targets, indicating a potential role for E2Fs in linking the metabolic state of the cell to cell cycle status [START_REF] Cam | A common set of gene regulatory networks links metabolism and growth inhibition[END_REF]. E2F1 transcriptional activation of the pyruvate dehydrogenase kinase 4 (PDK4) gene, a key nutrient sensor that is constitutively highly expressed in diabetes, was also demonstrated to regulate glucose homeostasis in muscle through inhibition of glucose oxidation [START_REF] Hsieh | Regulation of the PDK4 isozyme by the Rb-E2F1 complex[END_REF]. More recently, we also evidenced that E2F1 is a negative regulator of oxidative metabolism in skeletal muscle through the repression of PGC-1 α (unpublished results), suggesting that E2F1 may participate in the metabolic switch from OXPHOS to aerobic glycolysis in proliferative cells. Taken together these results support a dual role for the E2F pathway in the control of both cell proliferation and the metabolic response (Figure 3).

Sp family of transcription factors

Members of the Sp/KLF family of transcription factors Sp1, Sp3 and Sp4, which are over expressed in a variety of cancers are known to regulate cell proliferation by modulating the expression of genes containing GC-rich Sp1 binding sites, including but not limited to several cell cycle regulatory proteins [START_REF] Black | Sp1 and kruppel-like factor family of transcription factors in cell growth regulation and cancer[END_REF]. Interestingly, Sp1 sites were also found in the promoters of lipogenic enzymes, such as ACL, ACC and FAS [START_REF] Daniel | Sp1 mediates glucose activation of the acetyl-CoA carboxylase promoter[END_REF][START_REF] Moon | Characterization of regulatory elements on the promoter region of human ATP-citrate lyase[END_REF][START_REF] Xiong | Sterol regulation of human fatty acid synthase promoter I requires nuclear factor-Y-and Sp-1-binding sites[END_REF] and it was previously showed that both Sp1 and Sp3 can activate ACL in response to glucose in hepatoma cells [START_REF] Moon | Characterization of regulatory elements on the promoter region of human ATP-citrate lyase[END_REF]. In a recent report, the role of Sp in coordinating proliferation and lipogenesis in the context of cancer was investigated. In this work, the authors demonstrated that Sp1 regulates both proliferation and FAS expression in human MCF-7 breast, HCT116 colon and LNCaP prostate -cancer cells [START_REF] Lu | Sp1 coordinately regulates de novo lipogenesis and proliferation in cancer cells[END_REF]. Stimulation of proliferation by Sp1 is mediated by the regulation of specific cell cycle proteins, such as CDC25A. This dual regulation of metabolic and proliferative genes by a single transcription factor supports the hypothesis that common regulatory pathways exist between proliferative and metabolic factors.

Metabolism, proliferation and cancer

Fritz and Fajas 9

ChREBP

One of the important advantages of aerobic glycolysis common regulatory pathways relies on the possibility to redirect glucose carbon flux into anabolic pathways such as de novo lipogenesis and nucleotide biosynthesis. Sensing increased glucose input is therefore of utmost importance for cancer cells to trigger an adequate transcriptional response. This relies, at least partially on the carbohydrate responsive element binding protein (ChREBP), which is a glucose-responsive transcription factor. The critical role of ChREBP in mediating glucosedependent induction of glycolytic and lipogenic genes has been extensively explored in nonproliferating hepatocytes [START_REF] Denechaud | Role of ChREBP in hepatic steatosis and insulin resistance[END_REF][START_REF] Dentin | Hepatic glucokinase is required for the synergistic action of ChREBP and SREBP-1c on glycolytic and lipogenic gene expression[END_REF][START_REF] Yamashita | A glucose-responsive transcription factor that regulates carbohydrate metabolism in the liver[END_REF].

More recently, a role for ChREBP in proliferating cells has been described, showing its contribution in cancer cell proliferation and tumorigenesis through attenuation of p53 activity [START_REF] Tong | The glucose-responsive transcription factor ChREBP contributes to glucose-dependent anabolic synthesis and cell proliferation[END_REF]. One important finding in this study is the demonstration that ChREBP suppression in HCT116 colorectal and HepG2 hepatic human cancer cell lines resulted in decreased glycolysis, associated with diminished de novo lipogenesis and nucleotide biosynthesis, although mitochondrial respiration was increased. These data strongly suggest the participation of ChREBP in the metabolic switch from OXPHOS to aerobic glycolysis in cancer cells, a hypothesis that will require further investigation.

The oncogenic pathways: from Akt to c-Myc and Ras

The serine threonine kinase Akt (or PKB) is a paradigm of the dual and integrative regulation of metabolism and proliferation. Possibly, is the most versatile factor that controls the metabolic response to both metabolic and oncogenic stimuli, such as insulin and Ras signaling respectively. The function of Akt in metabolism covers from glucose homeostasis to protein and fatty acid synthesis. It is also a component of the growth factor signaling transduction cascade regulating a wide range of cellular functions including growth, survival and proliferation (reviewed in [START_REF] Manning | AKT/PKB signaling: navigating downstream[END_REF]). Since Akt is known to be a major mediator of glucose uptake and utilization it is thereby not surprising that Akt activity is correlated with high glycolytic rates in cancer cells [START_REF] Drosten | Genetic analysis of Ras signalling pathways in cell proliferation, migration and survival[END_REF]. Several studies have brought important clues to understand the participation of Akt in the glycolytic cancer

Metabolism, proliferation and cancer

Fritz and Fajas 10 phenotype. Indeed, growth factor-induced Akt activation was shown to result in increased expression and membrane distribution of the GLUT1 glucose transporter [START_REF] Barthel | Regulation of GLUT1 gene transcription by the serine/threonine kinase Akt1[END_REF][START_REF] Wieman | Cytokine stimulation promotes glucose uptake via phosphatidylinositol-3 kinase/Akt regulation of Glut1 activity and trafficking[END_REF][START_REF] Wofford | IL-7 promotes Glut1 trafficking and glucose uptake via STAT5-mediated activation of Akt to support T-cell survival[END_REF], association of hexokinase I and II to the mitochondria [START_REF] Gottlob | Inhibition of early apoptotic events by Akt/PKB is dependent on the first committed step of glycolysis and mitochondrial hexokinase[END_REF][START_REF] Majewski | Hexokinasemitochondria interaction mediated by Akt is required to inhibit apoptosis in the presence or absence of Bax and Bak[END_REF][START_REF] Robey | Mitochondrial hexokinases, novel mediators of the antiapoptotic effects of growth factors and Akt[END_REF], and stimulation of phospho-fructokinase activity, thereby increasing glycolysis. In addition to its welldocumented function in regulating glucose homeostasis, and cell proliferation there is also growing evidence that Akt plays important role in activating de novo FA synthesis. Activation of Akt was shown to induce gene expression of numerous enzymes involved either in cholesterol or fatty acid biosynthesis, including but not limited to the HMG-CoA synthase, HMG-CoA reductase, ACL, FAS, and stearoyl-CoA desaturase (SCD) [START_REF] Porstmann | PKB/Akt induces transcription of enzymes involved in cholesterol and fatty acid biosynthesis via activation of SREBP[END_REF]. Transcription of these enzymes in regard to Akt pathway has been shown to require the activity of the sterol regulatory element-binding protein (SREBP) family of transcription factors, which synthesis and nuclear accumulation are also induced by activated Akt [START_REF] Porstmann | PKB/Akt induces transcription of enzymes involved in cholesterol and fatty acid biosynthesis via activation of SREBP[END_REF]. Of particular importance is the observation that Akt also directly phosphorylates and activates the ATP-citrate lyase (ACL) [START_REF] Bauer | ATP citrate lyase is an important component of cell growth and transformation[END_REF][START_REF] Berwick | The identification of ATPcitrate lyase as a protein kinase B (Akt) substrate in primary adipocytes[END_REF][START_REF] Buzzai | The glucose dependence of Akt-transformed cells can be reversed by pharmacologic activation of fatty acid beta-oxidation[END_REF], which is a key enzyme integrating glucose and lipid metabolism.

Akt participates therefore in the first committed step in channeling glucose-derived metabolites towards a lipid biosynthetic fate.

Myc or Ras oncogenes can be also considered as coordinators of the proliferative and metabolic response of transformed cells [START_REF] Deberardinis | The biology of cancer: metabolic reprogramming fuels cell growth and proliferation[END_REF]. Altered expression or mutations in the Myc or Ras oncogenes respectively, have been associated to the genesis of most common human cancers. Apart from its role in the regulation of cell proliferation and cell cycle, there is compelling evidence that c-Myc and Ras also participate to the control of cancer cell metabolism. Since the discovery that c-Myc regulates the lactate dehydrogenase A (LDH-A) [START_REF] Lewis | Tumor induction by the c-Myc target genes rcl and lactate dehydrogenase A[END_REF][START_REF] Shim | c-Myc transactivation of LDH-A: implications for tumor metabolism and growth[END_REF], which converts pyruvate to lactate and contributes to the Warburg effect, c-Myc has been found to directly regulate many enzymes from the glycolytic pathway, therefore promoting glucose uptake and utilization [START_REF] Kim | Evaluation of myc E-box phylogenetic footprints in glycolytic genes by chromatin immunoprecipitation assays[END_REF][START_REF] Kim | Hypoxia-inducible factor 1 and dysregulated c-Myc cooperatively induce vascular endothelial growth factor and metabolic switches hexokinase 2 and pyruvate dehydrogenase kinase 1[END_REF][START_REF] Osthus | Deregulation of glucose transporter 1 and glycolytic gene expression by c-Myc[END_REF]. Furthermore, many studies have evidenced that c-Myc also plays a pivotal role in regulating mitochondrial biogenesis and function. This was supported by the observations that many genes involved in mitochondrial biogenesis and function are over-expressed among c-Myc direct transcriptional targets [START_REF] Kim | Global identification of Myc target genes reveals its direct role in mitochondrial biogenesis and its E-box usage in vivo[END_REF][START_REF] Li | Myc stimulates nuclearly encoded mitochondrial genes and mitochondrial biogenesis[END_REF][START_REF] Morrish | The oncogene c-Myc coordinates regulation of metabolic networks to enable rapid cell cycle entry[END_REF]. Since one important issue discussed in this review is the participation of cell cycle regulators in the metabolic control of cancer cells it is worth mentioning the link between Myc and E2F1 pathway. Both c-Myc and E2F1 are important regulators of cell cycle, and it has been suggested that c-Myc metabolic gene targets are regulated in a cell cycle dependent way. Indeed, after induction of energy metabolism and ribosomal biogenesis-related genes during the G1 phase, c-Myc induces E2F1 expression as cells entry into the S-phase, that together with c-Myc activate genes involved in nucleotide biosynthesis and DNA replication [START_REF] Liu | Global regulation of nucleotide biosynthetic genes by c-Myc[END_REF]. There is no need to discuss the importance of Ras oncogenes in the control of cell proliferation and tumor development [START_REF] Drosten | Genetic analysis of Ras signalling pathways in cell proliferation, migration and survival[END_REF]. Interestingly, Ras-mediated cell transformation is coupled to profound changes in metabolism, including enhanced glucose uptake and glycolysis, mitochondrial dysfunction, and increased lactic acid production. This is the result of increased expression of several genes of the aerobic glycolytic pathway and lactate dehydrogenase [START_REF] Chiaradonna | Rasdependent carbon metabolism and transformation in mouse fibroblasts[END_REF][START_REF] Mazurek | Metabolic cooperation between different oncogenes during cell transformation: interaction between activated ras and HPV-16 E7[END_REF][START_REF] Ramanathan | Perturbational profiling of a cell-line model of tumorigenesis by using metabolic measurements[END_REF]. Similar to other oncogenes, Ras also participates in the control of de novo lipid synthesis, mainly through regulation of the activity of the transcription factor SREBP mediated by the MAPK pathway [START_REF] Menendez | Why does tumor-associated fatty acid synthase (oncogenic antigen-519) ignore dietary fatty acids?[END_REF][START_REF] Yang | Activation of fatty acid synthesis during neoplastic transformation: role of mitogen-activated protein kinase and phosphatidylinositol 3-kinase[END_REF]. Most interestingly, recent data from our lab show that Ras transformation is abrogated when lipid synthesis pathways are inhibited (unpublished results). Taken together, the available literature suggests that oncogenes are at the origin of the metabolic transformations observed during cell transformation. These metabolic changes contribute to sustained proliferation of cancer cells, creating a positive feed-back loop. This is supported by the observation that changes in metabolism are also required to sustain the activation of oncogenes. Notably, oncogene-induced fatty acid synthesis, such as described above facilitates the formation of a subset of fatty acids, such as palmitate and palmitoleate, which impact on the traffic and cellular localization of several oncogenes, such as Ras, facilitating their anchorage to membranes required for the activation of their oncogenic pathways [START_REF] Nadolski | Protein lipidation[END_REF]. From these findings we can argue that inhibition of key enzymes 12 involved in lipid synthesis will abrogate activation of oncogenic signaling, and therefore will result in tumor growth arrest. This has been shown for ACL [START_REF] Bauer | ATP citrate lyase is an important component of cell growth and transformation[END_REF], FAS [START_REF] Kuhajda | Fatty acid synthesis: a potential selective target for antineoplastic therapy[END_REF][START_REF] Kuhajda | Fatty-acid synthase and human cancer: new perspectives on its role in tumor biology[END_REF], or SCD1 [START_REF] Scaglia | Inhibition of Stearoyl-CoA Desaturase 1 expression in human lung adenocarcinoma cells impairs tumorigenesis[END_REF] inhibition.

The counteracting tumor suppressor pathway

It is not surprising that tumor suppressors not only have opposite effects than oncogenes on the control of cell proliferation and cell cycle, but they also directly participate in the reversal of the glycolytic phenotype of the cells. Several examples are illustrative of this striking observation. The tumor suppressor p53, in addition to its well-known function in the control of cell cycle and apoptosis have an important role in the control of glycolytic and oxidative metabolism. It was shown that p53 participates in mitochondrial biogenesis and function, oxygen consumption, and decrease in glycolysis [START_REF] Matoba | p53 regulates mitochondrial respiration[END_REF]. These effects were mediated, at least in part through direct transcriptional regulation of the synthesis of cytochrome c oxidase 2, and apoptosis-inducing factor, which are essential genes in the control of mitochondrial function [START_REF] Matoba | p53 regulates mitochondrial respiration[END_REF]. Furthermore, opposite to oncogenes, such as Ras or Akt, p53 represses the expression of glucose transporters GLUT-1 and GLUT-4, thereby inhibiting glycolysis (Schwartzenberg-Bar-Yoseph et al 2004). In addition, p53 also senses the metabolic stress of the cell. Interestingly, under hypoxia or nutrient depletion, which are conditions characteristic of cancer cell environment, p53 appears to inhibit autophagy, which is required, under these conditions, to facilitate cancer cell growth [START_REF] Tasdemir | Regulation of autophagy by cytoplasmic p53[END_REF]. PTEN is another major tumor suppressor. Most of its effects are mediated through inactivation of the PI3K/Akt pathway. It is indeed a phosphatase of phosphatidyl inositol tri-phosphate (PIP 3 ), which is a major effector of Akt. Loss of function or mutations in PTEN is not only related to cancer development, but also exhibits dramatic consequences for metabolism homeostasis. For instance, Pten-deleted muscle, liver or fat tissue exhibits increased glucose sensitivity indicating that PTEN modulates glucose uptake and utilization in the cells [START_REF] Li | PTEN, a putative protein tyrosine phosphatase gene mutated in human brain, breast, and prostate cancer[END_REF][START_REF] Stiles | Liver-specific deletion of negative regulator Pten results in fatty liver and insulin hypersensitivity [corrected][END_REF][START_REF] Wijesekara | Musclespecific Pten deletion protects against insulin resistance and diabetes[END_REF]. This is of particular relevance in cancer cells, which are fully dependent on increased glycolytic flux.

PTEN is also a negative regulator of the insulin pathway, and therefore has negative effects 13 on lipogenesis, another hallmark of cancer cells. Paradoxically pRB is, in contrast to the other tumor suppressors, a major modulator of oxidative metabolism. RB specific deletion in adipose tissue results in increased mitochondrial activity and reversal from anabolic white adipose tissue to catabolic oxidative brown adipose tissue [START_REF] Dali-Youcef | Adipose tissue-specific inactivation of the retinoblastoma protein protects against diabesity because of increased energy expenditure[END_REF]. In this particular situation RB would facilitate a cancer-type metabolism. More studies are required, however, to better understand the role of pRB in the metabolic control in cancer cells.

Concluding remarks

It is well established that the process of cancer development and growth involves major alterations of cells' metabolism. In addition to triggering signaling cascades involved in proliferation and survival, oncogenes such as Ras, c-Myc or Akt, and most importantly cell cycle regulators such as the cdk4-E2F1 axis, also trigger concomitant metabolic changes. The majority of oncoproteins have been shown to stimulate aerobic glycolysis in transformed cells, including Akt, c-Myc, Ras and Src. Moreover, there is compelling evidence that in addition to trigger proliferation, oncogenes require the modification of metabolism, notably the increase in de novo FA synthesis in order to transform the cell. This modification in lipid synthesis results, in addition to other effects, in the activation of oncoproteins through protein lipidation. This creates a positive feed-back loop that contributes to sustained cancer cell growth and proliferation.

Most efforts have been directed towards the inhibition of the proliferative and invasive effects of oncogenes in cancer cells, whereas little attention has been paid to the metabolic changes in these cells. Further identification of the particular metabolic pathways regulated by oncogenic factors will certainly contribute to broaden the therapeutic options for cancer treatment.

Figure legends

Figure 1. Cross-talk between glycolysis and de novo FA synthesis in cancer cells. This model highlights the main differences in glucose and fatty acids utilization between quiescent (A) and highly proliferative cells (B). Red arrows indicate preferred metabolic pathway. In non-proliferating cells glucose can either be used for glycogen or fatty acids synthesis, or can be converted to pyruvate through basal rate of glycolysis that occurs in the cytoplasm.

Pyruvate is then imported into the mitochondrion where it is decarboxylated to acetyl Coa or oxalacetate (OAA). Circulating fatty acids are also imported into non-proliferating cells were they are stored as triglycerides or oxidized into the mitochondrion to generate acetyl-CoA.

Acetyl-CoA derived from both glucose and fatty acids is then oxidized through TCA cycle that produces intermediate citrate that is directed toward mitochondrial OXPHOS to generate ATP. In contrast, in proliferative cancer cells, the glycolytic flux is largely increased and most of the imported glucose is converted to the glycolytic end-product, pyruvate. The resulting pyruvate is mainly converted to lactate which is secreted from the cells, whereas the remaining pyruvate is converted to acetyl-CoA, which in turn is directed toward de novo FA synthesis. Circulating fatty acids are also mainly oxidized to generate acetyl-CoA. Acetyl-CoA derived from both glucose and fatty acids is then oxidized through TCA cycle to produced intermediate citrate. The resulting citrate is not directed toward OXPHOS but rather is exported to the cytoplasm where it is re-converted to acetyl-CoA, which, in turn, is used for de novo fatty acids biosynthesis.

Abbreviations: Glc, glucose; FA, fatty acids; OAA, oxaloacetate; TCA, tricarboxylic acid; OXPHOS, oxidative phosphorylation.

Figure 2 .Figure 3 .

 23 Figure 2. Oncogenic regulatory pathways in the control of the cancer cells metabolism. This scheme represents the main implications of oncogenic pathways (in red) in the regulation of glycolysis and de novo lipogenesis in cancer cells. Metabolic effects of the PI3K/Akt, Ras and c-Myc oncogenic pathways include enhanced glucose uptake through increased surface expression of glucose transporter. Hence, they enhance the glycolytic flux, including lactate production, by stimulating glycolytic enzymes activity. Moreover, both Akt and Ras

Acknowledgements

Members of the Fajas' lab are acknowledged for support and discussions. This work was supported by grants from Agence Nationale pour la Recherche (ANR physio), Association pour la Recherche contre le Cancer, Institut National du Cancer (INCA), and Fondation pour la Recherche Médicale. VF is supported by a grant of the INCA.


Laurent Boyer
email: laurent.boyer@univ-savoie.fr

Guillaume Theyssier ⋆⋆

On Factor Universality in Symbolic Spaces

The study of factoring relations between subshifts or cellular automata is central in symbolic dynamics. Besides, a notion of intrinsic universality for cellular automata based on an operation of rescaling is receiving more and more attention in the literature. In this paper, we propose to study the factoring relation up to rescalings, and ask for the existence of universal objects for that simulation relation. In classical simulations of a system S by a system T , the simulation takes place on a specific subset of configurations of T depending on S (this is the case for intrinsic universality). Our setting, however, asks for every configurations of T to have a meaningful interpretation in S. Despite this strong requirement, we show that there exists a cellular automaton able to simulate any other in a large class containing arbitrarily complex ones. We also consider the case of subshifts and, using arguments from recursion theory, we give negative results about the existence of universal objects in some classes.

Introduction and definitions

Tilings and cellular automata are two paradigmatic models often considered in the fields of complex systems and natural computing. They are complementary -one is static and non-deterministic and the other is dynamic and deterministic-but they are both formally simple and both related to symbolic spaces. Moreover, many links are now established between the two models (see for instance [START_REF] Kari | The Nilpotency Problem of One-dimensional Cellular Automata[END_REF][START_REF] Hochman | On the dynamics and recursive properties of multidimensional symbolic systems[END_REF]) so it is natural to consider them together.

Both are known to be Turing-powerful since their introduction in the mid-20th century [START_REF] Wang | Proving theorems by pattern recognition ii[END_REF][START_REF] Neumann | Theory of Self-Reproducing Automata[END_REF]. However, analyzing their ability to process information only through translations into the Turing world is very restrictive. Such models of natural computing deserve a natural and intrinsic notion of reduction to compare their objects one to each other. Following this line of thought, several notions of simulations were proposed recently which are intrinsic to each model, and lead to corresponding intrinsic notions of universality [START_REF] Ollinger | Automates Cellulaires : structures[END_REF][START_REF] Theyssier | Automates Cellulaires : un modèle de complexités[END_REF][START_REF] Lafitte | An almost totally universal tile set[END_REF][START_REF] Doty | Intrinsic universality in self-assembly[END_REF]: a system is universal if it is able to simulate any other from the same class.

Intrinsic universality for cellular automata is probably the most studied of such notions [START_REF] Ollinger | The quest for small universal cellular automata[END_REF][START_REF] Ollinger | The intrinsic universality problem of one-dimensional cellular automata[END_REF][START_REF] Moreira | Universality and decidability of number-conserving cellular automata[END_REF][START_REF] Boyer | On local symmetries and universality in cellular automata[END_REF][START_REF] Olivier | Intrinsic universality of a 1-dimensional reversible cellular automaton[END_REF]. The underlying relation of simulation uses uniform encodings working at the level of blocks of cells. More precisely, S simulates T if S, when restricted to a suitable subset of 'correct' configurations, is isomorphic to T via such an encoding. Our approach is different and uses redundancy of information instead of restriction to a subset of configurations. In our setting, S simulates T if there is a uniform way of projecting the whole phase space of S onto the phase space of T (a precise definition is given below). The question addressed by this paper is the existence of universal objects with respect to that simulation relation, we call them factor universal objects.

The first contribution of this paper is the formalism based on the well-known mathematical notion of action: it allows to encompass both subshifts and cellular automata, it gives a new look at the notion of cell grouping which is the root of the simulation relation used in intrinsic universality, and it establishes connections with the work of Hochman [START_REF] Hochman | A note on universality in multidimensional symbolic dynamics[END_REF] where the use of sub-actions is crucial. Our main result is that, although factor-universal objects do not generally exist (theorem 1), it can still be constructed for some large class like the set of cellular automata having a persistent state (theorem 2).

Basic definitions. Given a finite set Q and an integer d ≥ 1, the symbolic space of dimension d over alphabet Q is the set Q Z d . It can be seen as an infinite set of cells arranged as a lattice Z d and each carrying a value from Q. An element of Q Z d is called a configuration. Q Z d is naturally equipped with the compact Cantor topology [START_REF] Kůrka | Topological and symbolic dynamics[END_REF] which is the product topology of the discrete topology on Q (it can also be defined via a metric).

Another key notion in the context of symbolic spaces is that of finite patterns that may occur in infinite configurations. For our purpose, rectangular patterns will be enough. Given z = (z 1 , • • • , z d ) ∈ Z d with z i > 0 for all i, the hyperrectangle R z is the set of vectors

z ′ = (z ′ 1 , • • • , z ′ d ) ∈ Z d such that 0 ≤ z ′ i < z i for all i. A Q-pattern of shape R z is a coloring of R z by Q, that is an element of Q Rz . Given a configuration c ∈ Q Z d ,
the pattern of shape R zs extracted from c at position z p ∈ Z d , denoted by P zs zp (c), is simply: z ∈ R zs → c(z p + z). The objects we study (subshifts and cellular automata) share the property of being uniform, i.e. invariant by translations. Formally, given z ∈ Z d the translation of vector z, denoted σ z , is the function mapping

a configuration c ∈ Q Z d to the configuration σ z (c) such that ∀z ′ ∈ Z d , σ z (c)(z ′ ) = c(z ′ + z).
A subshift is a subset of Q Z d which is translation invariant and closed for the Cantor topology. Equivalently, a subshift is a set Σ L of configurations avoiding any occurrence of any finite pattern from a given language of patterns L:

Σ L = c ∈ Q Z d : ∀z, z ′ ∈ Z d with z i > 0 for all i, P z z ′ (c) ∈ L .
A subshift of finite type is a subshift of the form Σ L where L is finite. There are strong connections between subshifts of finite type in dimension 2 and sets of tilings generated by a set of wang tiles. In particular, due to Berger's theorem [START_REF] Berger | The undecidability of the domino problem[END_REF], it is undecidable, given a finite L, to determine whether Σ L is empty or not.

A cellular automaton is a local and uniform map on a symbolic space. Formally, it is given as a 4-tuple by its dimension d, its alphabet Q, its neighborhood V ⊆ Z d (finite) and its local transition map f : Q V → Q. To that formal object we associate a global map F acting on Q Z d as follows:

∀c ∈ Z d , ∀z ∈ Z d , F (c)(z) = f z ′ ∈ V → c(z + z ′ ) .
The fundamental theorem of Curtis-Lyndon-Hedlund [START_REF] Hedlund | Endomorphisms and Automorphisms of the Shift Dynamical Systems[END_REF] states that global maps of cellular automata are exactly continuous maps on symbolic spaces which commute with translations.

Actions and rescalings. Let (M, +) be a monoid (a set equipped with an associative law and a neutral element). An M-action on a space X is a function Ψ : M × X → X such that Ψ (0, x) = x (for all x ∈ X and 0 being the neutral element of M) and

∀x ∈ X, ∀m, m ′ ∈ M, Ψ (m + m ′ , x) = Ψ m, Ψ (m ′ , x) .
We will use the formalism of action to study both subshifts and cellular automata:

-if Σ ⊆ Q Z d is a subshift, we canonically associate to it the Z d -action Ψ Σ on Σ defined by Ψ Σ (z, x) = σ z (x); -if F is a cellular automaton on the space Q Z d , we canonically associate to it the N × Z d -action Ψ F on Q Z d defined by Ψ F (t, z), x = σ z • F t (x).
If M ′ is a sub-monoid of M, Ψ induces an M ′ -action by restriction to the domain M ′ × X. M and M ′ can be isomorphic or not and both cases might be interesting. For instance, studying a cellular automaton F as a classical dynamical system consists in forgetting the spacial component of Ψ F and focusing on the pure temporal action of F . This point of view was often adopted in the literature (e.g., topological dynamics of cellular automata [START_REF] Kůrka | Topological and symbolic dynamics[END_REF]) but, interestingly enough, recent work of Sablik [START_REF] Sablik | Directional dynamics for cellular automata: A sensitivity to initial condition approach[END_REF] tends to re-incorporate the spacial component of actions to better study the dynamics of cellular automata.

In this paper, we will only consider the case where M and M ′ are isomorphic. More precisely, in our context, M will be of the form Z d or N × Z d and we will consider sub-monoids of the form M ′ = t 0 N × z 1 Z × • • • × z d Z, with t 0 > 0 and z i > 0 for all i. In this case, passing from the M-action to the M ′ -action can be seen as a neutral change of point of view on the system that we call rescaling in the sequel. The intuition is that we change the discrete units of time and space, passing from 1 to t 0 in time and 1 to z i in direction i. Given a subshift or a cellular automaton, a scaled action is simply the restriction of their canonical action to some sub-monoid of the form M ′ . It is worth noticing that a scaled action associated to a subshift (resp. a cellular automaton) on the alphabet Q is always isomorphic to the canonical action of a subshift (resp. a cellular automaton) on an alphabet of the form Q k . More concretely, this isomorphism comes from the natural one-to-one map from

Q Z d to Q Rz s Z d
, where z s = (z 1 , . . . , z d ), which maps a configuration c to: z → P zs z×zs (c), where the operation × on Z d denotes coordinate-wise multiplication. Our notion of rescaling for cellular automata is similar to the one in [START_REF] Ollinger | Automates Cellulaires : structures[END_REF][START_REF] Theyssier | Automates Cellulaires : un modèle de complexités[END_REF] which is the basic ingredient to define intrinsic universality.

Factors. One of the central notion in symbolic dynamics is that of factor. Intuitively, a factor is a uniform continuous projection. This notion has also been used with success in the study of expansive cellular automata [START_REF] Nasu | The dynamics of expansive invertible onesided cellular automata[END_REF] and more generally as a classification tools for cellular automata [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF][START_REF] Cervelle | Ultimate traces of cellular automata[END_REF]. As we study both multi-dimensional subshifts and cellular automata, we give a unified definition using the formalism of actions.

Definition 1 Let M and M ′ be isomorphic monoids via i : M → M ′ . We say an

M ′ -action φ ′ on X ′ is a factor of a M-action φ on X if there is a continuous onto map π : X → X ′ such that: ∀x ∈ X, ∀m ∈ M, π φ(m, x) = φ ′ i(m), π(x) .
Two key points are that: (1) any orbit in (φ, X) projects onto some orbit of (φ ′ , X ′ ) via π, and (2) any orbit of φ ′ can be realized as such a projection. In a word, the simulation of (φ ′ , X ′ ) by (φ, X) is everywhere meaningful and complete.

Factor Universality

At this point, we could compare subshifts or cellular automata through the factoring relation between their canonical actions, saying that system S factors onto system T if the canonical action of S factors onto that of T . However, this gives an excessive importance to the alphabet and forbid the existence of universal objects due to entropy considerations (factoring cannot increase entropy). In [START_REF] Hochman | A note on universality in multidimensional symbolic dynamics[END_REF], this limitation is bypassed via dimension changes: a d-dimensional system is compared to k-dimensional systems (k < d) via its k-dimensional sub-actions. Our point of view is different. We always work at constant dimension, but we use another kind of sub-actions: scaled actions defined above. For a fixed dimension, monoids of scaled actions are all isomorphic and we will consider only canonical component-wise isomorphisms between them. We can now formulate the central definition of the paper.

Definition 2 Let S and T be two d-dimensional subshifts (resp. CA). We say that T is simulated by S, denoted T S, if some scaled action of S factors onto some scaled action of T .

As usual when working on symbolic spaces, continuity and uniformity implies locality (Curtis-Lyndon-Hedlund theorem [START_REF] Hedlund | Endomorphisms and Automorphisms of the Shift Dynamical Systems[END_REF]). In our context of rescalings, the locality is no longer expressed at the level of cells, but at the level of groups of cells. More precisely, we say that a map φ :

Q Z d 1 → Q Z d
2 is local if there exist: r ∈ N (locality radius), two shapes R z1 and R z2 (source and destination scales), and a local function f : Q

R (2r+1)z 1 1 → Q Rz 2 2 such that ∀c ∈ Q Z d 1 , ∀z ∈ Z d , P z2 z×z2 (φ(c)) = f P (2r+1)z1 z×z1-rz2 (c) . To fix ideas, if d = z 1 = z 2 = 1 and Q 1 = Q 2 ,
f is just the local map of a cellular automaton of radius r and φ is its corresponding global map.

Proposition 1 Fix a dimension d. Let Σ 1 and Σ 2 be two d-dimensional subshifts and let F 1 and F 2 be two d-dimensional CA of alphabet Q 1 and Q 2 respectively. Then we have:

-Σ 2 Σ 1 if and only if there is a local map φ such that φ(Σ 1 ) = Σ 2 ; -F 2 F 1 if and only if there is an onto local map φ from Q Z d 1 to Q Z d 2 and integers t 1 , t 2 ∈ N such that φ • F t1 1 = F t2 2 • φ.
Besides the work of Hochman [START_REF] Hochman | A note on universality in multidimensional symbolic dynamics[END_REF], notions of simulations similar to have already been considered for tilings [START_REF] Lafitte | An almost totally universal tile set[END_REF] or for cellular automata [START_REF] Theyssier | Automates Cellulaires : un modèle de complexités[END_REF][START_REF] Delorme | Bulking ii: Classifications of cellular automata[END_REF] or more general settings [START_REF] Kurka | Zero-dimensional dynamical systems, formal languages, and universality[END_REF]. Each time, one of the main concern is the existence of universal objects: this is precisely the central point of the present paper.

Definition 3 Let C be a class of subshifts (resp. cellular automata). A subshift (resp. cellular automaton)

U is C-universal if U ∈ C and X U for any X ∈ C.
Whatever the fixed dimension, there is no universal subshift for cardinality reasons: there are uncountably many subshifts but for a given subshift U there are at most countably many different subshifts -simulated by U (by proposition 1). The following theorem uses recursion theoretic arguments to yield other negative results concerning universality (similar arguments where used in [START_REF] Ollinger | Automates Cellulaires : structures[END_REF][START_REF] Hochman | A note on universality in multidimensional symbolic dynamics[END_REF] in different settings).

Theorem 1 Fix a dimension d ≥ 2. Then there is no universal subshift of finite type of dimension d and there is no surjective-universal CA of dimension d.

A Large Class with a Universal Object

In this section, we restrict to dimension 1 to make a clear exposition of the main result (theorem 2). Definition 4 A CA A is said to be persistent if there is a state q 0 ∈ Q A such that for any configuration c ∈ Q A Z if c(i) = q 0 then A(c) (i) = q 0 . We denote by P the set of all persistent CA.

Note that for any CA, you may add an extra persistent state and obtain a CA in P containing the dynamics of the first one.

Theorem 2 There exists a P-universal cellular automaton.

In the following, we describe such a P-universal CA U with radius 1 and alphabet Q U .

We denote by P 0 the set of CA of P with radius 1 and alphabet of size 2 p for some p ∈ N. One may easily describe for any CA B ∈ P a CA A ∈ P 0 such that B A. Using transitivity of , it will be sufficient, in order to prove P-universality of U, to exhibit for any CA A ∈ P 0 an onto local map

φ A from Q U Z to Q A Z and an integer τ A such that U τA • φ A = φ A • A.
To do so, for each A, we introduce an integer l A and a dichotomy on words of Q U lA .

on the one side we have what we call A-correct macrocells (or A-macrocells).

They encode information about a current state x ∈ Q A , about the local rule of A, and a machinery used to apply this rule to update the current state.

In almost any case, they will be interpreted through φ A as x.

on the other side we call all the other patterns A-incorrect, and they will be interpreted as the persistent state of A.

The idea behind the local rule of U is to make every A-macrocell determine if it is surrounded by other A-macrocells. If this is the case, then interaction is possible, and the current state of the neighbor will be taken into account to compute the new current state, following the rule of A. Otherwise, there is no interaction, the A-macrocell evolves considering every A-incorrect neighborhood as a persistent state neighbor. The difficulty is that although correctness is related to the particular CA being simulated, every configuration must evolve correctly for every possible CA.

The proof of universality uses the combination of two key properties: on one hand, correct patterns remain correct and evolve according to the rule being simulated, even if not surrounded by correct patterns (lemma 4); on the other hand, incorrect patterns are interpreted as the persistent state and never become correct (lemma 5).

To make the construction of U readable, we describe its state set as a superposition of several layers: the main layer M contains most of the information about the simulation and the macrocells informations; signals layers are used to manage the evolution of the main layer; and clock layers guarantee synchronizations.

Correct macrocells description

In the following we consider a simulated CA A ∈ P 0 with radius 1 and state set Q A of size n = 2 p . We use a canonical binary enumeration of the state set, in which the first word (0 log(n) ) represents a persistent state of A, denoted p A . Our A-correct macrocells will be words of length l A (specified above) whose main layer follow the pattern # C i |T ransition table| |State| |memory| # -# are delimiters, they never appear or disappear during the computation -C i is the control state used to control the successive steps of computation.

-|T ransition table| is the binary description of the transition table of A.

-|State| contains the binary value of the current state of the macrocell.

-|memory| is a binary area which will be used to keep the values of the neighbors' current states before computing the new current state of the macrocell.

|T ransition table|, |State| and |memory| are encoded with disjoint binary sub-alphabets. A cell whose state belongs to one of those sub-alphabets will never change sub-alphabet. Moreover, the states of the transition table's cells are never modified.

The current state description is log(n)-bits-long. In the transition table, images are ordered canonically, so the length of the description is simply n 3 log(n).

The memory should be at least 2log(n)-bits-long in order to contain current state values of the two neighbors. But in order to simplify some proofs, we chose l A such that it is at least half the total size of the macrocell, and such that the function A → l A is one-to-one.

Most of the computation will happen on those very constrained patterns. In the next definition, we add an extra constraint on the control state to obtain A-correct macrocells.

By stability of the sub-alphabets, such a correct A-macrocell remains correct, but the state value may change. This is why we take some care when defining the current state value associated to the macrocell.

Definition 5 A word u ∈ Q U lA of length l
A is said to be a A-correct macrocells, denoted by u ∈ C A , if its main layer follows the structure defined above (correct sub-alphabets for each cell, and correct transition table of A), and if its control state is in C 0 .

For each such A-correct macrocell u, we define its associated state value v(u) ∈ Q A , which is the state described by its current state value after l A steps of computation by U. And this state value v(u) only depends on u.

To ensure that the sate value only depends on u, the memory area is used as a buffer to prevent modification of the current state value coming from the left, before the computation has been initialized. Details will be given in the following.

By extension we may sometime call A-macrocells words following the general pattern, even with non-C 0 control state, in particular when they are images of a A-correct macrocell.

The local rule. We describe the local behavior of U starting from a correct A-macrocell. The local rule will first determine which neighbors it may interact with (Check of the neighbor's length and synchronization, and Transition table and state encoding check ), and then compute its new current state according to the rule of A and eventually the value of those neighbors (New current state computation).

In order to guarantee the synchronization between A-macrocells, we specify the duration of each step, and even of some sub-steps. It is done by a clock, which use specific layers of the states; their existence is proved by the following lemma:

Lemma 1 For any k, h ∈ N \ {1}, there exist a CA, and two states q s , and q f such that the leftmost cell of an area delimited by two # separated by l -2 cells turns to state q f at some time t > k • l 2 + h • l iff this cell was in state q s exactly k • l 2 + h • l steps before. Moreover, this property is guaranteed independently of what is outside the two #.

At the beginning of each step, the control state C i will turn to C i+1 , initiate the corresponding clock, and initiate some signals which will manage the evolution. Those signals are distinct states propagating on upper layers of the configuration, and interacting with the main layer and other signals. We say that a signal belongs to a macrocell if it was generated in this macrocell's area, between the two #. And, thanks to our evolution rule, a signal always knows if it is in its cell or in the area to the right or left of its cell. It is also useful sometimes to make signals carry one extra bit of information. It is simple to do it using distinct states, since the number of bits is bounded.

Check of the neighbor's length and synchronization. C 0 → C 1 (that is to say that when the control cell's state is C 0 it becomes C 1 ):

Recall that we are interested to the behavior in the case of an A-correct macrocell. When C 0 becomes C 1 , it initializes two control bits with value 0, in the main layer of the control cell, and it launches signals. Since the construction is classical, we simply illustrate the desired behaviors by figure 1. Those two pictures illustrate the signal machinery in the case of respectively left and right neighbors of same length and with state C 0 appearing simultaneously (what we call synchronized). Every transition whose image is one of the signal involved in this checking appears on those pictures.

The first signals s 1 and s 4 erase all signals belonging to our macrocell. Together with the length of the memory being bigger than the length between the control state where signals are generated and the end of the current state area, it constitutes the protection of the current state value from eratic signals coming from outside the macrocell, and justifies that in definition 5 v(u) is a function of u.

If the neighbors have same length and are synchronized, this whole step takes 4 times the length of the macrocell, l A . After 4 • l A steps, the control state C 1 becomes C 2 , and if it did not receive a positive result from one side, it concludes that the involved neighbor is incorrect. This is managed using a clock signal (with h = 2 and k = 0 in lemma 1) initialized by C 0 on a specific layer. When q f is raised on this layer, C 1 becomes C 2 . The important point is that we ensure the following property.

Lemma 2

The control state of an A-correct macrocell becomes C 2 exactly 4 • l A steps after C 0 appeared. At this step each control bit has turned to 1 iff the corresponding neighboring macrocell has same length and synchronisation than the considered macrocell.

The proof of this lemma is direct for the length but asks to enter into some more (simple but fastidious) details for the synchronization part.

Transition table and state encoding check. C 2 → C 3 :

In this step, for each neighboring pattern with same length and synchronization, the macrocell checks whether the transition table and the current state are compatible with its own (same lengths, and same content for the transition table) or not.

When C 2 appears it launches the following test for each neighbor whose corresponding control bit was 1, and initializes two fresh bits to 0. First, a signal is generated and puts a mark (that is to say a non-moving signal) on the first cell of the transition table of its macrocell, and another mark on the first cell of the transition table of the neighbor it checks. Then signals are exchanged between those two marks that will each time carry the binary state of the cell pointed by one mark to the next unchecked cell of the other macrocell; it compares this cell's binary state to the carried binary state, and push the mark by two cells. If no difference is detected and if both marks reach the end of the transition tables simultaneously, a correctness signal is sent to the control state. After the transition table has been checked, the same mechanism is used to check that the current state encoding areas have same length. At the end of those tests, the results are sent to the control cell which again keeps the information on two control bits. For each cell of the transition table or the current state, checking takes 2 • l A steps. So checking a whole neighbor takes less than 2 • l 2

s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1 s ′′ 1
A . Again, a clock is used to make this test last exactly 2 • l 2 A steps. Then the control cell is turned to C 4 .

Lemma 3 The control state of our macrocell becomes C 4 exactly 2•l 2

A steps after C 2 appeared. At this step each control bit has turned to 1 iff the corresponding neighboring pattern has same length, synchronization, and if the lengths of the transition tables and current states, and the content of the transition table are equal. In this case we say that this pattern is compatible with our A-macrocell.

The proof of this lemma is straightforward. Keep in mind that some signals erased all erratic signals that could interact with our cell at a previous step.

New current state computation. C 4 → C 5 :

After all the tests have been done, the new current state has to be computed. We need to explicit how we consider the neighboring pattern. In the following, what we call detected state of one such pattern by our macrocell will be: either the persistent state if the neighbor is non-compatible with our A-macrocell, or its current state if this is a compatible A-macrocell.

At first, the detected states of the left and right neighbors are written to the memory. It is written in the binary memory alphabet. Each detected state is written on log(n) cells. If one neighbor is compatible, we copy its current state value to the memory using marks and signals similarly to the previous step. If it is not compatible, we write 0 log(n) , the length being the same as that of the current state area. We add a clock to specify that copies last exactly 2 • l 2

A steps, the neighbor being correct or not.

After 2 • l 2 A additional steps, the search for the image in the transition table starts. It consists in reading the binary word formed by the three image states (the current state of the cell followed by the two detected states copied in the memory), and turning it into a unary position in the transition table. It is then possible to place a mark at this position, and finally copy this pointed state to the current state area. We make the reading of the position last 4 • l 2

A steps. And copying the new state lasts 2 • l 2

A . After the whole computation step, which lasts 7 • l 2 A , the control state turns to C 5 . Finally one step of simulation is completed after exactly τ A = 9 • l 2 A + 4 • l A steps. After this time the control state turns to C 5 .

To become C 0 again, and launch a new step of computation, we add another condition. We ask a clock launched exactly τ A steps before to raise a flag. And obviously this clock may only be launched by C 0 . It is realized using again signals of the lemma 1 computing on one more layer.

The state set of the universal CA is given by

Q U = M × S × C ∪ {C f } with -the main layer : M = {C 0 , C 5 } ∪ {C i } i∈{1,..,4} × {0, 1} 2 ∪ {0 i , 1 i } i∈{tt,cs,m} -the signals layers : S = × i∈I {s i } × × j∈J ({s j } × {0, 1})
the clocks layers (see lemma 1), one for each duration needed. C = ({0, 1} × {s i } i∈Ic ) 4 -C f is a single persistent state ensuring that U ∈ P Yet, the transition rule of U is partially specified, we call correct transitions those defined up to now, in the case of correct macrocells. But the other transitions may not be chosen arbitrarily. We specify the following behaviors:

-C f is never modified by any transition the main layer is never modified by a non-correct transition: they act as the identity on the main layer. -concerning the signal layer, apart from the collisions corresponding to the behavior described in the previous steps, all signals may cross each other (each kind of signal is evolving on its own layer). However, except for transitions involved in the behavior described above, any signal that crosses a # is destroyed.

Interpretation We now describe the continuous onto map φ A :

Q U Z → Q A Z associated to A.
This map is induced by a local map f A from patterns of shape l A to individual states of A. More precisely, using notation from proposition 1, we have r = 0, z 1 = l A , z 2 = 1, t 2 = 1 and t 1 = τ A . If p A is the persistent state of A, the local map ψ A is defined as follows:

1. ∀u ∈ C A , f A (u) = p A 2. ∀u ∈ C A , f A (u) = v(u), with v(u) the value from definition 5
Proof of theorem 2 The proof of the theorem relies on the two following lemmas. They are consequences of the construction, the intermediate lemmas and the clock lemma.

Lemma 4 ∀ c ∈ Q U Z , t 0 ∈ N, if U t0 (c) [0,lA-1] ∈ C A , then v = U t0+τA (c) [0,lA-1] ∈ C A , and ψ A (v) = δ A (ψ A (c [-lA,-1] ), ψ A (c [0,lA-1] ), ψ A (c [lA,2•lA-1] )). Lemma 5 If ∃ t ≥ τ A , c ∈ Q U Z such that u = U t (c) [0,lA-1] ∈ C A then v = U t-τA (c) [0,lA-1] ∈ C A .
We can finally prove our main claim: ∀A ∈ P 0 , A U. We use the characterization of proposition 1. Let A ∈ P 0 the associated length l A and function φ A are defined as explained before. First, φ A is local (by definition) and onto, because correct macrocells are enough to encode any state of A and thus concatenations of correct macrocells allow to encode any configuration of A. Second, we have φ A •U τA = A•φ A . To see this we discuss on the pattern of shape R lA at position 0 and the rest follows by translation. If this pattern is not in C A its image after τ A steps remains out of C A (lemma 5). If conversely this central word belongs to C A , lemma 4 gives the desired property.

Perspectives

A natural extension of our work could be to generalize the construction to cellular automata having an equicontinuous point. The idea would be to use blocking words as a replacement for the persistent state. But it seems much harder, if not impossible.

Besides, the main open question left by this paper is the existence of universal CA. We conjecture that they do not exist and more precisely that no CA can simulate all products of shifts. A possible way to obtain this negative result would be to study limit sets: by a compacity argument, one can show that a universal CA must have a universal limit set. The main obstacle is that subshifts that are limit sets of CA are not well characterized.

Finally, we also leave open the existence of universal SFT and universal surjective CA in dimension 1.

to Q Rz 2 2
. By eventually completing f and by definition of the factoring π between M and M ′ -scaled actions, f induces a local map from Q Z d 1 to Q Z 2 associated with shapes R z1 and R z2 . It is onto because π is onto.

For cellular automata, the reasoning is similar and adding the temporal component in actions translates exactly into the desired property of weak commutation between the global maps of cellular automata and the onto map between configuration spaces.

⊓ ⊔ Proof (Theorem 1). For the case of surjective CA, it is enough to notice that surjectivity is preserved by the relation . Indeed, if F G we have

φ • G t1 = F t2 • φ
for some onto map φ. Therefore F must be surjective if G is surjective.

Then the proof follows from Kari's theorem [START_REF] Kari | Reversibility and Surjectivity Problems of Cellular Automata[END_REF] establishing that surjective CA are not recursively enumerable. Indeed, given a surjective universal CA U , we could enumerate thanks to the local presentation of factors (proposition 1) all CA F such that F U : they are all surjective (surjectivity is preserved by factor) and all surjective CA are among them (universality).

We consider now the case of subshifts of finite type. Without loss of generality, any subshift of finite type can be presented as a subshift Σ L where L is a finite set of patterns having all the same shape R z for some z. By Berger's theorem [START_REF] Berger | The undecidability of the domino problem[END_REF] the set of such L verifying that Σ L is not empty can not be recursively enumerated. We show below that the existence of a universal subshift of finite type implies the existence of an algorithm of enumeration of all L of the form above such that Σ L is not empty.

So suppose that there exists some universal subshift of finite type Σ LU where L U is a set of Q U -patterns of shape R zU . Obviously, Σ LU must be non-empty. For any L and any pattern p of larger shape, we say that p is L-valid if it contains no occurrence of any pattern from L (occurrence requires that one shape is completely included into the other).

Let L be a set of Q-patterns of shape R z and ψ be a local map from Q Z d U to Q Z d associated to shapes R z1 and R z2 Consider the minimal shape R z + containing both R z and R 2z2 . Since ψ is local, one can check in finite time the following property called validity property: any pattern p of shape R z + which has a L U -valid preimage via ψ is L-valid (the size of preimages of finite patterns depends on the radius r associated to ψ but details don't matter here). By the definition of local maps and the hypothesis on shapes, this property implies that ψ(Σ LU ) ⊆ Σ L and therefore Σ L = ∅ (the choice of shape R 2z2 ensures that validity is checked inside blocks of shape R z2 but also across the boundary between two such adjacent blocks).

It follows that we can recursively enumerate couples (L, ψ) having the property above. More precisely, maps ψ are enumerated via their local presentation (shapes, radius and local function). This way, we can enumerate a list of finite languages L such that Σ L is not empty. To conclude the proof it is sufficient to show that all L such that Σ L = ∅ are present in the list. Suppose by contradiction that some L over alphabet Q with Σ L = ∅ is such that no local map from Q Z d U to Q Z d verifies the validity property above. By universality of Σ LU , there exists a local map ψ sending Σ LU to Σ L . Let r, R z1 and R z2 , and local function f , be the parameters associated to ψ. For any k ≥ 0 we can define the same map ψ with another presentation by increasing artificially the radius r to kr and changing the local function f accordingly (shapes are kept unchanged). We call it the k th presentation of ψ. Since, by hypothesis on L, no such presentation has the validity property, we deduce that there must exist some finite pattern p which is not L-valid and such that, for any k, p has a L U -valid preimage under the k th presentation of ψ. Therefore, by a simple compacity argument, there exists c ∈ Σ LU such that ψ(c) has an occurrence of p. Hence, ψ(c) ∈ Σ L which is a contradiction.

⊓ ⊔

B Proofs from section 3

Proof of lemma 1: We first build a CA that satisfies our lemma for k = 2, h = 0. Its state set will be made of one binary layer, and a signal layer. The behavior is simple: when q s appears it generates a signal that will keep oscillating between the #. When the signal is generated for the first time, it initialize the area, turning the first binary cell to 1 and the other one to 0s. Then, the signal keep moving from right to left and back between the #. Each time it goes to the right, it turns one more binary cell to 1. And when the rightmost cell's binary layer is finally turned to 1 a new special signal is sent to the left which will generate the q f . If two or more signals crosses, one of them may survive. If one of them is initializing it will survive.

So, in 2.l steps of computation, the total number of 1s may be non increasing only in the following cases:

if there is no signal at all if all cell's binary layer is already 1 and in this case a q f was generated if an initialization signal has been sent.

In particular, if a q f appears at some step, then in the previous 4.l steps, a 1 was generated. And in each previous 2.l step, at least a 1 was generated.

Thus, in the previous 2.l 2 steps, at least one initialization signal was launched and a q s has appeared. But by construction, after a q s state appears, the first q f state appears only exactly 2.l 2 steps later.

It concludes the proof of the clock lemma in case k = 2, h = 0. For other values of k, simply slow down the signal going right to left. For other values of h, after the end of the quadratic part, launch a signal that will go right with speed 1 and come back left with speed 1/(h -1) before raising q f . ⊓ ⊔ Proof of lemma 5: By definition of a correct pattern, u is given by: # C 0 |T ransition table| |State| |memory| # First of all, the # are never created or destroyed. The transition table and maximal state information are never modified, so they are the same in u and in v. And the sub-alphabet corresponding to control state, current state and memory alphabets are stable. The structure of v is the same as this of u. To prove our lemma it remains to prove that the second letter in v is C 0 , and that the current state value is smaller than the maximal value.

But, to make C 0 appear, at step t, a signal q f was raised by the global clock, which implied, using the clock lemma, that the second letter of v is C 0 . Thus all tests are launched. ⊓ ⊔

Fig. 1 .

 1 Fig. 1. Successful left (resp. right) neighbor test by the right (resp. left) macrocell (mix of main and signal layers for easier reading)

⋆ ⋆ ⋆ Partially supported by French ANR 'projet blanc' EMC (NT09 555297)

A Proofs from section 2

Proof (Proposition 1). First, an onto local map from Σ 1 to Σ 2 with shapes R z1 and R z2 induces a factoring relation from the M-scaled action of Σ 1 onto the M ′ -scaled action of Σ 2 with

Conversely, suppose that the relation Σ 1 Σ 2 is realized by a factor map π from the M-scaled action of Σ 1 onto the M ′ -scaled action of Σ 2 with

Consider now each pattern p ∈ Q

. Since the cylinder C p defined by

is both open and closed, so is π -1 (C p ). By compacity, and since cylinders form a basis of the topology, we get that π -1 (C p ) is a finite union of cylinders of Q Z d 1 . We can suppose without loss of generality that they are all of shape R (2r+1)z1 for some large enough r (finite unions of cylinders of small shape can always be defined as finite unions of cylinders of larger shapes). Doing this with the same value of r for all p, we get a (possibly partial) function f from Q