Christophe A Girard

Margaux Lecacheur

Rania Ben Jouira

Ilona Berestjuk

Serena Diazzi

Virginie Prod'homme

Aude Mallavialle

Frédéric Larbret

Maeva Gesson

Sébastien Schaub

R Ben Jouira

S Pisano

S Audebert

B Mari

C Gaggioli

E Leucci

J C Marine

Marcel Deckert
email: deckert@unice.fr

Sophie Tartare-Deckert

A Feed-Forward Mechanosignaling Loop Confers Resistance to Therapies Targeting the MAPK Pathway in BRAF-Mutant Melanoma

Keywords: melanoma, extracellular matrix, YAP, MRTF, targeted therapies, resistance

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

INTRODUCTION

Reciprocal feedback between the ECM and tumor cells influence the hallmarks of cancer by providing biological abilities to malignant cells that are required for growth, survival and dissemination. The ECM is a dynamic network of macromolecules with distinctive biochemical and mechanical properties that plays a major role in establishing tumor niches [START_REF] Lu | The extracellular matrix: a dynamic niche in cancer progression[END_REF]. Increased ECM deposition, fiber alignment and covalent cross-link between collagen molecules lead to tumor stiffening, which has been associated to an elevated risk of cancer and poor clinical outcome in patients with breast or pancreatic cancers [START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF][START_REF] Laklai | Genotype tunes pancreatic ductal adenocarcinoma tissue tension to induce matricellular fibrosis and tumor progression[END_REF].

Cancer-associated fibroblasts (CAFs) are the main producers of tumorigenic ECM and function like myofibroblasts during wound healing and fibrosis [START_REF] Hinz | The myofibroblast: paradigm for a mechanically active cell[END_REF]. Cells apply contractile forces to sense the physical environmental stiffness through integrin-based focal adhesion (FA) complexes that connect the actin-myosin cytoskeleton with the ECM [START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF][START_REF] Paszek | Tensional homeostasis and the malignant phenotype[END_REF]. Matrix rigidity also leads to enhanced nucleus localization and activity of the mechanical-responsive YAP transcriptional regulator of the Hippo pathway [START_REF] Dupont | Role of YAP/TAZ in mechanotransduction[END_REF]. In CAFs, YAP acts as a critical factor regulating force-mediated ECM remodeling towards increased stiffening [START_REF] Calvo | Mechanotransduction and YAP-dependent matrix remodelling is required for the generation and maintenance of cancer-associated fibroblasts[END_REF]. Similar to YAP, the SRF transcriptional co-activator MRTF is translocated to the nucleus upon actin polymerization and functionally interacts with YAP to coordinate mechanosignaling and CAF contractility [START_REF] Finch-Edmondson | Framework to function: mechanosensitive regulators of gene transcription[END_REF][START_REF] Foster | Mutual dependence of the MRTF-SRF and YAP-TEAD pathways in cancer-associated fibroblasts is indirect and mediated by cytoskeletal dynamics[END_REF]. Beside, YAP mainly through its interaction with TEAD transcription factors have been shown to promote resistance to RAF/MEK-targeted cancer therapies in tumor cells such as melanoma [START_REF] Lin | The Hippo effector YAP promotes resistance to RAF-and MEK-targeted cancer therapies[END_REF][START_REF] Kim | Actin remodeling confers BRAF inhibitor resistance to melanoma cells through YAP/TAZ activation[END_REF][START_REF] Verfaillie | Decoding the regulatory landscape of melanoma reveals TEADS as regulators of the invasive cell state[END_REF].

Because of its resistance to treatment and propensity for metastasis, cutaneous melanoma is one of the most aggressive human cancers [START_REF] Shain | From melanocytes to melanomas[END_REF]. Melanoma comprises phenotypically heterogeneous subtypes of cancer cells that can switch between transcriptional programs and differentiation states [START_REF] Widmer | Systematic classification of melanoma cells by phenotype-specific gene expression mapping[END_REF][START_REF] Tirosh | Dissecting the multicellular ecosystem of metastatic melanoma by single-cell RNA-seq[END_REF][START_REF] Tsoi | Multi-stage Differentiation Defines Melanoma Subtypes with Differential Vulnerability to Drug-Induced Iron-Dependent Oxidative Stress[END_REF]. The majority of human melanomas display genetic alterations in BRAF or NRAS, leading to constitutive activation of the MAP Kinase (MAPK) pathway. MAPK pathway inhibitors, such as BRAF inhibitors (BRAFi), MEK inhibitors (MEKi), or their combination, achieve significant clinical benefits in patients with BRAFV600-mutant melanoma. However, most patients relapse within months due to the acquisition of drug resistance attributed to intrinsic genetic and non-genetic changes in melanoma cells. While genetic resistance frequently result from the reactivation of the MAPK pathway through de novo mutations, such as NRAS mutations [START_REF] Flaherty | From genes to drugs: targeted strategies for melanoma[END_REF][START_REF] Shi | Acquired resistance and clonal evolution in melanoma during BRAF inhibitor therapy[END_REF], non-genetic mechanisms involve epigenetic and/or transcriptomic changes in tumor cells during the early phase of treatment [START_REF] Hugo | Non-genomic and Immune Evolution of Melanoma Acquiring MAPKi Resistance[END_REF][START_REF] Titz | JUN dependency in distinct early and late BRAF inhibition adaptation states of melanoma[END_REF]. Such mechanisms often result in a de-differentiation cell state characterized by downregulation of the master regulator of melanocyte differentiation Microphthalmia-Associated Transcription Factor (MITF) and up-regulation of receptor tyrosine kinases (RTKs) such as AXL [START_REF] Nazarian | Melanomas acquire resistance to B-RAF(V600E) inhibition by RTK or N-RAS upregulation[END_REF][START_REF] Villanueva | Acquired resistance to BRAF inhibitors mediated by a RAF kinase switch in melanoma can be overcome by cotargeting MEK and IGF-1R/PI3K[END_REF][START_REF] Girotti | Inhibiting EGF receptor or SRC family kinase signaling overcomes BRAF inhibitor resistance in melanoma[END_REF]. In addition, the de-differentiated resistant MITF low /AXL high population was shown to display a mesenchymal invasive phenotype [START_REF] Muller | Low MITF/AXL ratio predicts early resistance to multiple targeted drugs in melanoma[END_REF][START_REF] Sun | Reversible and adaptive resistance to BRAF(V600E) inhibition in melanoma[END_REF][START_REF] Rathore | Cancer cellderived long pentraxin 3 (PTX3) promotes melanoma migration through a tolllike receptor 4 (TLR4)/NF-kappaB signaling pathway[END_REF]. Transcriptional reprogramming of proliferative drug-sensitive melanoma cells into invasive drug-resistant cell population is thus a critical event in acquired resistance to targeted therapies.

Beside tumor cell-autonomous events, there is evidence that extrinsic factors derived from the tumor microenvironment contribute to melanoma resistance to MAPK pathway inhibition.

Stromal cells including CAFs and macrophages secrete growth and inflammatory factors, and ECM components such as fibronectin, which contribute to drug tolerance [START_REF] Straussman | Tumour micro-environment elicits innate resistance to RAF inhibitors through HGF secretion[END_REF][START_REF] Kaur | sFRP2 in the aged microenvironment drives melanoma metastasis and therapy resistance[END_REF][START_REF] Smith | The immune microenvironment confers resistance to MAPK pathway inhibitors through macrophage-derived TNFalpha[END_REF][START_REF] Young | An adaptive signaling network in melanoma inflammatory niches confers tolerance to MAPK signaling inhibition[END_REF][START_REF] Hirata | Intravital imaging reveals how BRAF inhibition generates drug-tolerant microenvironments with high integrin beta1/FAK signaling[END_REF].

Interestingly, melanoma cells have the ability to secrete their own matrix, in particular upon cellular transition to a de-differentiated mesenchymal state occurring in response to MAPK pathway inhibition [START_REF] Titz | JUN dependency in distinct early and late BRAF inhibition adaptation states of melanoma[END_REF][START_REF] Gaggioli | Tumorderived fibronectin is involved in melanoma cell invasion and regulated by V600E B-Raf signaling pathway[END_REF][START_REF] Naba | The matrisome: in silico definition and in vivo characterization by proteomics of normal and tumor extracellular matrices[END_REF]. In this study we asked whether melanoma cell-derived ECM impacts on tumor mechanics and contributes to resistance to targeted therapies. We show that both acquired resistance and early adaptation to MAPK signaling inhibition paradoxically induces a force-mediated ECM reprogramming in melanoma cells that increases cancer cell intrinsic mechanical sensing properties and alters ECM composition and topography. This fuels a mechanical positive-feedback loop where melanoma cell-derived ECM and YAP/MRTF intracellular pathways play a pivotal role and that could favor the reservoir of therapyresistant cells.

MATERIALS AND METHODS

Cells and reagents. Melanoma cell lines 501Mel and MNT1 were obtained as described before [START_REF] Didier | Targeting the Proteasome-Associated Deubiquitinating Enzyme USP14 Impairs Melanoma Cell Survival and Overcomes Resistance to MAPK-Targeting Therapies[END_REF][START_REF] Tichet | Tumour-derived SPARC drives vascular permeability and extravasation through endothelial VCAM1 signalling to promote metastasis[END_REF]. 1205Lu cells were from Rockland (USA). Isogenic pairs of Verumafenibsensitive (P) and resistant (R) cells (M229, M238, M249) were provided by R. Lo [START_REF] Nazarian | Melanomas acquire resistance to B-RAF(V600E) inhibition by RTK or N-RAS upregulation[END_REF]. Cells were cultured in Dulbecco's modified Eagle Medium (DMEM) plus 7% FBS (Hyclone).

Resistant cells were continuously exposed to 1 μM Vemurafenib. Cell lines were used within 6 months between resuscitation and experimentation. To guarantee cell line authenticity, cells were expanded and frozen at low passage after their receipt from original stocks, used for a limited number of passages after thawing and routinely tested for the expression of melanocyte-lineage proteins such as MITF. All cell lines were routinely tested for the absence of mycoplasma by PCR. For live imaging, M2380P, 501Mel and 1205Lu were transduced with NucLight Red lentivirus reagent (Essen Bioscience) and selected with puromycin (1 μg/ml).

Culture reagents were purchased from Thermo Fisher Scientific. BRAFi (PLX4032, Vemurafenib), MEKi (GSK1120212, Trametinib) and ROCK inhibitor Y27632 were from Selleckem. YAP inhibitor Verteporfin was from Sigma.

RNAi studies. siGENOME siRNA SMARTpools for YAP1, MRTFa and nontargeting control were from Dharmacon (Horizon Discovery). 50 nM of either siRNA pool was transfected using Lipofectamine RNAiMAX (Thermo Fisher Scientific), following the manufacturer's protocol.

Immunoblot analysis and antibodies. Cell lysates were subjected to immunoblot analysis as described before [START_REF] Tichet | Tumour-derived SPARC drives vascular permeability and extravasation through endothelial VCAM1 signalling to promote metastasis[END_REF]. The following antibodies were used at dilution of 1:1,000, unless otherwise stated: Type I collagen and α-SMA (Abcam); TAGLN2 (Genetex); PDGFRβ (Cohesion Biosciences); EGFR and LOXL2 (Bio-Techne); LOX (Novus Biological); MITF (Thermo Fisher Scientific); fibronectin, thrombospondin (TSP1), β1 integrin, FAK, paxillin, FAP, and MRTF (BD Biosciences); SPARC (Haematologic Technologies); ERK1/2, HSP90, HSP60, MLC2 (Santa Cruz Biotechnology); AXL, YAP, phospho-Paxillin (Y118), phospho-ERK1/2 (T202/Y204), phospho-Rb (S807/811), Rb, p27KIP1, caveolin-1, survivin and tubulin (Cell Signaling Technology).

Real-time quantitative PCR. Gene expression levels were determined by RT-qPCR as described [START_REF] Didier | Targeting the Proteasome-Associated Deubiquitinating Enzyme USP14 Impairs Melanoma Cell Survival and Overcomes Resistance to MAPK-Targeting Therapies[END_REF]. Data were presented as relative gene expression according to the ΔΔCt method. Heatmaps depicting fold changes of gene expression were prepared using MeV software. Primer sequences are available upon request.

Generation of cell-derived ECM and drug-protection assays. 3D ECMs were generated as previously described [START_REF] Beacham | Preparation of extracellular matrices produced by cultured and primary fibroblasts[END_REF]. Briefly, gelatin-coated culture dishes were seeded with cells and cultured for 8 days in complete medium, supplemented with 50 μg/ml ascorbic acid every 48 h. Cell cultures were then washed with PBS and matrices were denuded following a 2 min treatment with pre-warmed extraction buffer (PBS 0.5% Triton X-100, 20 μM NH4OH).

Matrices were then gently washed several times with PBS. For drug-protection assays, melanoma cells were seeded onto decellularized matrices for 24 h, and cultured for another 48 h period in presence or not of indicated drugs.

Cell proliferation.

Cell cycle profiles were determined by flow cytometry as described before [START_REF] Didier | Targeting the Proteasome-Associated Deubiquitinating Enzyme USP14 Impairs Melanoma Cell Survival and Overcomes Resistance to MAPK-Targeting Therapies[END_REF]. Proliferation was measured by a MTS conversion assay [START_REF] Didier | Targeting the Proteasome-Associated Deubiquitinating Enzyme USP14 Impairs Melanoma Cell Survival and Overcomes Resistance to MAPK-Targeting Therapies[END_REF] or followed by live imaging of NucLight Red-stained cells using the IncuCyte ZOOM™ system according to the manusfacturer's instructions (Essen BioScience) or by nuclei quantification of Hoeschtstained cells.

Cell contraction assay. 5×10 4 melanoma cells were embedded in 100 µl of collagen I/Matrigel and seeded on a glass bottom 96-well plate (MatTek). Once the gel was set (1 h at 37°C), cells were maintained in DMEM 10% FBS with or without indicated drugs. Gel contraction was monitored at day 3. The gel area was measured using ImageJ software and the percentage of contraction was calculated using the formula 100 × (well diameter-gel diameter)/well diameter as described [START_REF] Albrengues | LIF mediates proinvasive activation of stromal fibroblasts in cancer[END_REF].

Traction force microscopy (TFM).

Contractile forces exerted by melanoma cells were assessed by TFM as described (38) using collagen-coated polyacrylamide hydrogels with shear modulus of 4kPa coated with red fluorescent beads (SoftTrac, Cell Guidance Systems).

Cells were plated on fluorescent bead-conjugated gels for 48 h. Images were acquired before and after cell removal using a fluorescence microscope (Leica DMI6000, 10X magnification).

Tractions exerted by cells were estimated by measuring beads displacement fields, computing corresponding traction fields using Fourier transformation and calculating root-mean-square traction using the particle image velocity plugin on ImageJ. The same procedure was performed on a cell-free region to measure baseline noise.

Immunofluorescence analysis. Cell were grown either on glass coverslips or collagencoated polyacrylamide/bisacrylamide synthetic hydrogels with defined stiffness as described [START_REF] Tse | Preparation of hydrogel substrates with tunable mechanical properties[END_REF]. Following treatment, cells were rinsed, fixed in 4% formaldehyde, and incubated in PBS 0.2% saponin 1% BSA in PBS for 1 h with 1:100 dilution of the indicated primary antibodies.

Following incubation with AlexaFluor-conjugated secondary antibodies (1:1,000), coverslips and hydrogels were mounted in Prolong antifade (Thermo Fisher Scientific). F-actin was stained with Texas Red-X or AlexaFluor488 phalloidin (1:100, Thermo Fisher Scientific).

Nuclei were stained with DAPI. Images were captured on a widefield microscope (Leica DM5500B, 40X magnification). The orientation of fibronectin fibers was assessed on immunofluorescence images using ImageJ software. Data were plotted as a frequency distribution.

Collagen imaging. Collagen fibers were stained using Picrosirius red accordingly to [START_REF] Estrach | CD98hc (SLC3A2) loss protects against ras-driven tumorigenesis by modulating integrin-mediated mechanotransduction[END_REF].

Images were acquired under polarized illumination using a light transmission microscope (Zeiss Axio Observer, 5X magnification). Background signal was determined on each sample from an empty zone. Background was then subtracted from the signal emitted by the region of interest. A minimum of 3 background-subtracted samples was used for quantification. The area was calculated as followed: area of tumors was selected based on HE staining to exclude analysis of peritumoral regions. Images were then converted into gray scale pictures and the threshold option ''Minimum'' on the ImageJ software (https://imagej.nih.gov/ij/) was selected to quantify the area of collagen fibers and normalize it to the total area selected.

Second harmonic generation (SHG) and multiphoton-fluorescence images were acquired on a Zeiss 780NLO (Carl Zeiss Microscopy) with Mai Tai HP DeepSee (Newport Corporation). (PDX platform at the KULeuven University) and treated with the BRAFi-MEKi combination as described before [START_REF] Rambow | Toward Minimal Residual Disease-Directed Therapy in Melanoma[END_REF] (see Supplementary Informations for details). Tumor biopsies were formalin-fixed and paraffin embedded in sections of about 5 µm for picrosirius red staining and immunohistochemistry.

Elastic modulus measurements. Mechanical properties of tumor sections were analyzed by atomic force microscopy (AFM) as described before [START_REF] Bertero | Vascular stiffness mechanoactivates YAP/TAZ-dependent glutaminolysis to drive pulmonary hypertension[END_REF] with a Bioscope Catalyst operating in Point and Shoot (Bruker Nano Surfaces), coupled with an inverted optical microscope (Leica DMI6000B, Leica Microsystems Ltd.). The apparent Young's Modulus (Εapp) was measured on unfixed frozen tumor sections using a Borosilicate Glass spherical tip (5 μm of diameter) mounted on a cantilever with a nominal spring constant of 0.06 N/m (Novascan Technologies). The force-distance curves were collected using a velocity of 2 μm/s, in relative trigger mode and by setting the trigger threshold to 1 nN. Εapp values were presented in a boxplot using GraphPad Prism (GraphPad software).

Gene Expression Omnibus (GEO) data analysis. Public datasets of human melanoma cell

lines developing drug resistance to Vemurafenib (M229R and SKMel28R) and double resistance to Vemurafenib and Selumetinib (M229DDR and SKMel28DDR) were used to analyze gene levels compared to drug-naive parental cell lines (GSE65185) [START_REF] Hugo | Non-genomic and Immune Evolution of Melanoma Acquiring MAPKi Resistance[END_REF]. Differential gene expression was also examined in datasets derived from tumor biopsies from melanoma patients before and after development of drug resistance to BRAFi, MEKi or BRAFi/MEKi combination (GSE50535 (25); Tirosh et al. Supplementary information [START_REF] Tirosh | Dissecting the multicellular ecosystem of metastatic melanoma by single-cell RNA-seq[END_REF]). Normalized data were prepared using MeV software.

Statistical analysis.

Unless otherwise stated, all experiments were repeated at least three times and representative data/images are shown. Statistical data analysis was performed using GraphPad Prism 5 software. Unpaired two-tailed Mann-Whitney test were used for statistical comparisons between two groups and Kruskal-Wallis test with Dunn posttests or two-way analysis of variance test with Bonferroni post tests to compare three or more groups.

Error bars are ± s.d.

RESULTS

MITF low /AXL high BRAFi-resistant cells display increased mechano-responsiveness and YAP/MRTF activation. To investigate whether acquired resistance to BRAFi modifies mechanosensing pathways, we exploited models of isogenic pairs of parental (P) and resistant (R) melanoma cells showing either reactivation of MAPK pathway through NRAS mutation (M249R) or upregulation of AXL, EGFR and PDGFRβ RTKs associated with low levels of MITF and reduced differentiation of melanoma cells (M229R, M238R) (Supplementary Fig. S1) [START_REF] Titz | JUN dependency in distinct early and late BRAF inhibition adaptation states of melanoma[END_REF][START_REF] Nazarian | Melanomas acquire resistance to B-RAF(V600E) inhibition by RTK or N-RAS upregulation[END_REF]. Cells were cultured on collagen-coated hydrogels with stiffness ranging from 0.2kPa (low), 4kPa (medium) to 50 kPa (high) [START_REF] Tse | Preparation of hydrogel substrates with tunable mechanical properties[END_REF]. In contrast to parental sublines, a dramatic modification of M238R (Fig. 1A andB) and M229R (Supplementary Fig. S2A andB) cell morphology measured by actin reorganization, cell roundness and area was noticeable upon increased substrate stiffness. In contrast, the shape and actin cytoskeleton of the NRASmutated M249R subline and its parent M249P showed no significant changes in response to mechanical stimulation (Fig. 1C and 1D; Supplementary Fig. S2C andS2D). Importantly, mesenchymal BRAFi-resistant cells M229R and M238R, but not NRAS-mutated M249R cells, exhibited an enhanced capacity to proliferate on a collagen-coated stiff substrate (Fig. 1E andS2E).

The β1 integrin/FA pathway is essential for ECM mechanosignaling [START_REF] Humphrey | Mechanotransduction and extracellular matrix homeostasis[END_REF]. Consistently, when compared to drug-sensitive cells, M238R and M229R cells expressed higher levels of β1 integrin and increased phosphorylation of FA components, including FAK, p130Cas and paxillin (Supplementary Fig. S1). In addition, M238R cells displayed higher number of FAs upon increased matrix rigidity compared to parental cells (Supplementary Fig. S3).

YAP and MRTF are critical transcriptional mediators of mechanical signals in mammalian cells

through partially overlapping signaling pathways and target genes [START_REF] Dupont | Role of YAP/TAZ in mechanotransduction[END_REF][START_REF] Calvo | Mechanotransduction and YAP-dependent matrix remodelling is required for the generation and maintenance of cancer-associated fibroblasts[END_REF][START_REF] Foster | Mutual dependence of the MRTF-SRF and YAP-TEAD pathways in cancer-associated fibroblasts is indirect and mediated by cytoskeletal dynamics[END_REF][START_REF] Zhao | Force activates smooth muscle alpha-actin promoter activity through the Rho signaling pathway[END_REF].

Immunofluorescence analysis of melanoma cells plated on soft or rigid substrates revealed that in contrast to M238P cells, M238R cells showed higher levels of nuclear YAP (Fig. 2A) on low stiffness substrates. Nuclear YAP (Fig. 2A) and MRTF (Fig. 2B) markedly increased in M238R cells plated on medium and high substrate stiffness, while translocation of YAP and MRTF was only apparent when parental cells were plated on stiff substrate. Consistently, the expression of shared YAP/MRTF target genes paralleled increasing collagen rigidity in M238R, but not M238P cells (Fig. 2C). Furthermore, impairment of the actomyosin cytoskeleton with the ROCK inhibitor Y27632 reduced the nuclear localization of YAP and MRTF in M238R cells grown on high stiffness substrate (Fig. 2D). Accordingly, ROCK inhibition abrogated the expression of two shared YAP/MRTF target genes CTGF and CYR61 activated in M238R cells on stiff substrate (Fig. 2E).

Finally, to evaluate the potential contribution of ECM stiffness-induced YAP and MRTF activation in the mesenchymal resistant phenotype, M238R cells cultured on rigid collagen hydrogels were transfected with siRNA pool targeting YAP or MRTF and treated with increasing doses of BRAFi (Vemurafenib). The sensitivity of M238R cells to BRAFi-induced cell proliferation arrest was partially restored upon YAP or MRTF knockdown, suggesting that collagen stiffening through YAP and MRTF activation contributes to acquired BRAFi resistance (Fig. 2F). Together, these results indicate that the de-differentiated MITF low /AXL high resistant cell state is associated with a mechanophenotype.

MITF low /AXL high BRAFi-resistant cells display YAP and MRTF-dependent contractile

activity and assemble an organized ECM. Further functional analysis of the dedifferentiated MITF low mesenchymal resistant state revealed that M229R and M238R cells were characterized by high expression levels of typical CAF markers such as caveolin-1 (CAV1), myosin light-chain 2 (MLC2), smooth muscle actin-α (α-SMA), fibroblast activation protein (FAP), transgelin-2 (TAGLN2), in addition to ECM proteins collagen 1 (COL1) and fibronectin (Fig. 3A). In contrast, parental and mutant NRAS-driven resistance M249R cell lines showed low or no expression of such markers. We thus examine whether MITF low /AXL high resistant cells display CAFs-associated features such as ROCK-dependent actomyosin contractility and force-mediated ECM remodeling leading to fibers organization [START_REF] Calvo | Mechanotransduction and YAP-dependent matrix remodelling is required for the generation and maintenance of cancer-associated fibroblasts[END_REF][START_REF] Albrengues | LIF mediates proinvasive activation of stromal fibroblasts in cancer[END_REF]. We first compared traction stresses generated by sensitive and BRAFi-resistant cells using traction force microscopy (TFM) and observed that M238R cells applied stronger forces on collagen-coated stiff matrices than their drug-sensitive parental counterparts (Fig. 3B).

Next, we performed collagen gel contraction assays to assess cell contractility. Contractility in 3D collagen gel was observed for M238R, but not for M238P cells. Inhibition of ROCK by Y27632 or YAP by Verteporfin reduced the capacity of M238R cells to contract collagen gels to levels that are observed for drug-sensitive M238P cells (Fig. 3C). Moreover, siRNA-mediated knockdown of YAP or MRTF abrogated the contractile activity of drug-resistant M238R cells (Fig. 3D).

Given that increased cellular forces lead to matrix fiber organization and that BRAFi-resistant mesenchymal cells secrete high levels of ECM proteins [START_REF] Titz | JUN dependency in distinct early and late BRAF inhibition adaptation states of melanoma[END_REF][START_REF] Nazarian | Melanomas acquire resistance to B-RAF(V600E) inhibition by RTK or N-RAS upregulation[END_REF], we analyzed the topography of the fibronectin and collagen network generated by this resistant cellular state. First, we compared ECM proteins differentially produced and deposited by M238P and M238R cells.

Cell-derived 3D matrices were generated, denuded of cells and analyzed by quantitative mass spectrometry. Compared to M238P cells, M238R cells assembled a matrix that was enriched in ECM glycoproteins (fibronectin, fibrilin-1, thrombospondin-1 and fibulin-1/2), collagens, proteoglycans (versican and biglycan), as well as collagen-modifying enzymes such as transglutaminase 2 and LOXL2 (Supplementary Table S1). Furthermore, in contrast to parental cells, M238R cells produced and assembled fibronectin and collagen fibers oriented in parallel patterns that resembled those produced by TGFβ-activated fibroblasts (Fig. 3E).

Fibronectin fibers organization was quantified by measuring the relative orientation angle of fibers. The percentages were 16.5%, 23.7% and 27.8% for M238P, M238R and fibroblasts 3D ECM, respectively (Fig. 3F). Importantly, the lower degree of ECM production by parental cells was not due to a difference in proliferation as evidenced by nuclear and fibronectin stainings of M238P and M238R cell cultures before the decellularization process (Supplementary Fig. S4). Together, these results suggest that MITF low /AXL high BRAFi-resistant cells display increased traction forces and contractility leading to aligned organization of ECM fibers.

Given our observations so far, we explored publicly available expression array studies searching for mechanosignaling, and cell contractility gene expression in drug-resistant human melanoma cell lines. Data extracted from the GEO database (GSE65185) [START_REF] Hugo | Non-genomic and Immune Evolution of Melanoma Acquiring MAPKi Resistance[END_REF] showed increased levels of several YAP/MRTF target genes (THBS1, CYR61, CTGFAMOTL2, ANKRD1 and SERPINE1) together with high levels of ECM genes (COL1A1, COL1A2 and FN1) and mesenchymal markers (PDGFRB, MYL9, ACTA2, FAP and TAGLN) in MITF low /AXL high cells developing drug resistance to Vemurafenib (BRAFi) (M229R and SKMel28R) and double resistance to Vemurafenib and Selumetinib (BRAFi + MEKi) (M229DDR and SKMel28DDR) as compared to drug-sensitive parental cell lines (Fig. 3G). Moreover, analysis of gene expression on tumor biopsies from patients progressing during therapy with BRAFi and/or MEKi (GSE50535 and Tirosh et al (Supplementary info)) [START_REF] Tirosh | Dissecting the multicellular ecosystem of metastatic melanoma by single-cell RNA-seq[END_REF][START_REF] Sun | Reversible and adaptive resistance to BRAF(V600E) inhibition in melanoma[END_REF] revealed that the expression of ECM and mechanosignaling genes markedly increased in a subset of relapsing patients with MITF low /AXL high expression (Fig. 3G).

Early adaptation to MAPK pathway inhibition induces mechanotransduction pathways,

contractility and ECM fiber organization. We next questioned whether adaptive response to MAPK pathway inhibition involves mechanosensing pathways and ECM remodeling. BRAFmutant melanoma cells (M238P and 1205Lu) were plated on collagen-coated hydrogels with medium stiffness and treated with the BRAFi Vemurafenib or the MEKi Trametinib (Fig. 4 and Supplementary Fig. S5). In both cases, drug-treated cells displayed pronounced morphological and actin cytoskeleton changes that were accompanied by increased YAP and MRTF nuclear localization (Fig. 4A and Supplementary Fig. S5A andB), and transcriptional activation of the YAP/MRTF shared target gene CYR61 relative to untreated cells (Supplementary Fig. S5C).

Moreover, drug-treated M238P and 1205Lu cells displayed significantly higher number of FAs with larger size as compared with control cells (Supplementary Fig. S6). We further confirmed that a short-term treatment of cells with either BRAFi or MEKi increased the expression of collagen 1 (COL1) and fibronectin and of the YAP/MRTF target thrombospondin-1 (TSP1), along with reduced phosphorylation of RB and increased expression of p27KIP1, two cell cycle markers that are modulated by MAPK pathway inhibition (Fig. 4B). Importantly, shortterm treatment with BRAFi or MEKi was sufficient to increase the contractile activity of 1205Lu cells embedded in 3D collagen gels (Fig. 4C). Consistently, when cultivated one week in the presence of Vemurafenib, 1205Lu cells assembled an organized ECM composed of collagen and fibronectin fibers that were anisotropically oriented, as compared to untreated cells (Fig. 4D). A further indication of the involvement of mechanopathways in the adaptation of melanoma cells to MAPK inhibition was brought by the observation that M238P, 1205Lu and 501Mel cells cultivated on stiff collagen-coated substrates were significantly more resistant to increasing doses of BRAFi as compared to cells cultivated on soft substrates (Fig. 4E). Together, these results demonstrate that melanoma cells rapidly adapt to MAPK pathway inhibition by acquiring an ECM-remodeling contractile phenotype associated with increased mechanosignaling pathways.

Mesenchymal-associated resistance and early adaptation to MAPK pathway inhibition

induce the production of a drug-protective ECM. The findings described above support the notion that a subset of BRAF-mutant melanoma cells in response to early and late MAPK pathway inhibition acquire the capacity to produce and remodel a matrix reminiscent to CAFderived ECM. Because ECM plays a major role in mediating drug resistance, we hypothesized that melanoma cell-derived matrix functions as a supporting niche for melanoma cell behavior. To investigate the effect of melanoma cell-derived ECM on survival and resistance to targeted therapies, drug naïve BRAF-mutant melanoma cells were plated on 3D matrices generated from parental cells (M238P and M229P) or their BRAFi-resistant counterparts (M238R and M229R), and treated or not with Vemurafenib alone or the combination Vemurafenib/Trametinib (Fig. 5; Supplementary Fig. S7). Time-lapse monitoring of 501Mel proliferation revealed that matrices derived from BRAFi-resistant cells significantly reduced the proliferation arrest induced by MAPK pathway inhibition in contrast to ECMs from BRAFisensitive cells, which had no impact on the cytostatic action of BRAF and MEK inhibition (Fig. 5A andB; Supplementary Fig. S7A andB). Cell cycle analysis further confirmed the protective action of matrices from BRAFi-resistant, but not from BRAFi-sensitive cells, over the G0/G1 cell cycle arrest induced by BRAFi on drug-naive 501Mel and MNT1 cells (Fig. 5C; Supplementary Fig. S7C andD). At the molecular level, matrix-mediated therapeutic escape from BRAF inhibition was associated in both 501Mel and MNT1 cells with sustained levels of the proliferation marker phosphorylated-RB and of survivin, low levels of the cell cycle inhibitor p27KIP1 together with maintained phosphorylation of ERK1/2 in presence of the drug (Fig. 5D; Supplementary Fig. S7E andF). Importantly, similar biochemical events were promoted in BRAFi-sensitive 501Mel cells escaping from the combination of BRAFi and MEKi upon adhesion to M238R-derived, but not M238P-derived ECM (Fig. 5E). Next we wondered if short term MAPK pathway inhibition fosters a drug-protective ECM program in melanoma cells. 501Mel cells were plated on matrices generated from vehicle or Vemurafenib-treated 1205Lu cells, and treated with or without BRAFi. Cell cycle and biochemical analysis showed that BRAF inhibition rapidly promoted the production by 1205Lu cells of an ECM that significantly counteracted the cytostatic action of Vemurafenib in 501Mel cells (Fig. 5F andG).

Finally, we investigated the involvement of the mechanoresponsive YAP and MRTF transcriptional pathways in ECM-mediated drug protection. 501Mel cells were cultured on matrices prepared from parental M238P or drug-resistant M238R cells and the subcellular location of YAP and MRTF was examined by immunofluorescence microscopy. In contrast to ECM from M238P cells, matrices derived from M238R cells promoted the nuclear translocation of YAP and MRTF (Fig. 6A), and their transcriptional activation as indicated by the increased expression of ANKRD1 and SERPINE1 genes (Fig. 6B). Consistently, the drug protective action provided by matrices derived from therapy-resistant M238R cells against BRAFi or the combination BRAFi/MEKi was dramatically reduced in 501Mel cells in which either YAP (Fig. 6C) or MRTF (Fig. 6D) expression was knocked-down. Depletion of YAP or MRTF enhanced the efficacy of MAPK pathway inhibition as shown by reduced levels of phosphorylation of ERK1/2 and RB and increased expression of p27KIP1 (Fig. 6E andF). This suggests that melanoma cell-derived ECM mediates drug protection through YAP and MRTF regulation.

Collectively, our findings demonstrate that both early and late adaptation to MAPK pathway inhibition involves the mechanical reprogramming of melanoma cells leading to the assembly of an organized matrix that confers de novo resistance to targeted therapies in a YAP and MRTF-dependent manner.

In vivo MAPK pathway inhibition promotes melanoma cell-derived ECM accumulation and tumor stiffening. Exposure of BRAF-mutant melanoma cells to MAPK pathway inhibition promotes a mechanophenotype associated with drug tolerance in vitro, which could have important outcomes for disease progression in vivo. To address this, we first explored whether BRAF inhibition induces ECM remodeling in human melanoma xenograft models. BRAF-mutant melanoma cells 1205Lu or M229P were xenografted into nude mice (melanoma CDX), which were treated blindly with either vehicle or Vemurafenib (Supplementary Fig. S8A). As expected, BRAF targeting induced a strong inhibition of tumor growth (Supplementary Fig. S8B andC). Histological, transcriptomic and biophysical analyses were then performed at the experiment end point. Vemurafenib treatment triggered a profound remodeling of the 1205Lu (Fig. 7A) and M229P (Supplementary Fig. S8D) tumor stroma, with a marked increase of collagen fibers area and thickness, as measured by polarized light of picrosirius red-labeled tumors and second harmonic generation (SHG) microscopy (Fig. 7A and B; Supplementary Fig. S8D). We then examined gene expression on BRAFi-treated melanoma tumors by performing RT-qPCR analysis using human and mouse probes.

Consistent with a previous study [START_REF] Hirata | Intravital imaging reveals how BRAF inhibition generates drug-tolerant microenvironments with high integrin beta1/FAK signaling[END_REF], Vemurafenib was found to significantly activate tumorassociated host stromal cells. However, compared to untreated tumors, tumors exposed to BRAFi also dramatically upregulated human mesenchymal and ECM genes, including genes for collagens (COL1A1, COL3A1, COL5A1, COL15A1), fibronectin (FN1), collagen-modifying enzyme (LOX) and myofibroblast markers (SPARC, ACTA2), as well as YAP and/or MRTF target genes, such as AXL, CYR61, SERPINE1, AMOTL2 and THBS1 (Fig. 7C). This observation supports the notion that BRAF inhibition can promote a cancer cell-autonomous mechanism of ECM production in vivo. Consistent with the changes in ECM composition and assembly, Vemurafenib treatment significantly increased tumor elastic modulus in the two CDX models when measured by atomic force microscopy (AFM) (Fig. 7D; Supplementary Fig. S8E), suggesting that ECM stiffening constitute an adaptive response of melanoma cells to MAPK pathway inhibition in vivo. We next wished to validate these observations in melanoma patient-derived xenografts (PDX). PDX exposed or not to the combination of BRAFi and MEKi were stained with picrosirius red (Fig. 7E). Combined BRAF and MEK inhibition also resulted in a marked accumulation of collagen fibers in the tumor stroma of melanoma PDX (Fig. 7E and F). Finally, Verteporfin, a FDA approved drug used in photodynamic therapy for macular degeneration and a known inhibitor of YAP was used to interrogate if YAP contributes to BRAFi-induced collagen remodeling and therapy response in vivo. Whereas Verteporfin alone did not affect 1205Lu melanoma tumor growth, co-treatment with Vemurafenib plus Verteporfin had a greater anti-tumor effect than Vemurafenib alone after 17 days of drug regimens (Fig. 7G andH). Thus, combined Verteporfin and Vemurafenib therapy enhanced Vemurafenib response in a pre-clinical melanoma model. Furthermore, Verteporfin treatment abrogated the accumulation of collagen fibers induced by BRAF inhibition in the stroma of melanoma xenografts (Fig. 7I andJ). Together these data suggest that YAP mechanosensing pathway contributes to collagen reorganization in response to MAPK pathway inhibition and support the concept of a combinatorial approach to overcome ECM-mediated therapy resistance in BRAF mutated melanoma models.

DISCUSSION

Pathological ECM remodeling and biomechanical signaling have been linked to tumor aggressiveness in several solid cancers. In the tumor stroma, resident or recruited fibroblasts are activated by tumor-derived factors such as TGFβ to become CAFs, which are considered as the main producers of the tumor ECM [START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF]. In melanoma, BRAFi therapy paradoxically activates melanoma-associated fibroblasts to generate drug-tolerant niches through paracrine HGF or fibronectin secretion [START_REF] Straussman | Tumour micro-environment elicits innate resistance to RAF inhibitors through HGF secretion[END_REF][START_REF] Hirata | Intravital imaging reveals how BRAF inhibition generates drug-tolerant microenvironments with high integrin beta1/FAK signaling[END_REF][START_REF] Fedorenko | BRAF Inhibition Generates a Host-Tumor Niche that Mediates Therapeutic Escape[END_REF]. Despite multiple evidence that melanoma cells autonomously produce its own ECM [START_REF] Gaggioli | Tumorderived fibronectin is involved in melanoma cell invasion and regulated by V600E B-Raf signaling pathway[END_REF][START_REF] Naba | The matrisome: in silico definition and in vivo characterization by proteomics of normal and tumor extracellular matrices[END_REF][START_REF] Chapman | Heterogeneous tumor subpopulations cooperate to drive invasion[END_REF], little is known about the contribution of melanoma cell-derived ECM to drug adaptation and resistance. A major resistance program in BRAF-mutant melanomas exposed to MAPK-targeting therapies is linked to a dedifferentiated, mesenchymal transcriptional cell state characterized by low levels of the melanoma differentiation factor MITF and high levels of RTKs including AXL [START_REF] Tirosh | Dissecting the multicellular ecosystem of metastatic melanoma by single-cell RNA-seq[END_REF][START_REF] Hugo | Non-genomic and Immune Evolution of Melanoma Acquiring MAPKi Resistance[END_REF][START_REF] Nazarian | Melanomas acquire resistance to B-RAF(V600E) inhibition by RTK or N-RAS upregulation[END_REF][START_REF] Villanueva | Acquired resistance to BRAF inhibitors mediated by a RAF kinase switch in melanoma can be overcome by cotargeting MEK and IGF-1R/PI3K[END_REF][START_REF] Girotti | Inhibiting EGF receptor or SRC family kinase signaling overcomes BRAF inhibitor resistance in melanoma[END_REF][START_REF] Muller | Low MITF/AXL ratio predicts early resistance to multiple targeted drugs in melanoma[END_REF].

The MITF low /AXL high resistant cells exhibit multiple traits of the Hoek's invasive gene signature [START_REF] Widmer | Systematic classification of melanoma cells by phenotype-specific gene expression mapping[END_REF], including prominent expression of ECM proteins [START_REF] Titz | JUN dependency in distinct early and late BRAF inhibition adaptation states of melanoma[END_REF][START_REF] Nazarian | Melanomas acquire resistance to B-RAF(V600E) inhibition by RTK or N-RAS upregulation[END_REF]. Here we showed that this resistant cell population also exhibits key aspects of CAFs involved in ECM remodeling: they acquired a mechanical phenotype associated with an actomyosin/YAP/MRTF-dependent contractile activity, and the ability to deposit ECM to create a tumor-permissive environment.

In contrast, drug-naive cells and a population of MITF high /NRAS-mutant resistant cells displayed no such mechano-responsive features and ECM remodeling activities. Importantly, we also found that early adaptation to MAPK pathway inhibition promotes de novo acquisition of a CAF-like phenotype leading to biomechanical reprogramming both in vitro and in vivo. We thus uncover a previously unidentified feed-forward loop between drug-exposed or resistant MITF low /AXL high melanoma cells and ECM remodeling to increase tumor tissue stiffness, mechanosensing and resistance through YAP and MRTF regulation (Fig. 7K).

We showed that short-term treatment of melanoma cells with targeted drugs induced actin dynamics, mechanosensitive regulation of YAP and MRTF and increased melanoma cell contractility. This differs from another early adaptation state to BRAF inhibition characterized by the emergence of a slow-cycling NGFR/CD271 high persistent cell population [START_REF] Titz | JUN dependency in distinct early and late BRAF inhibition adaptation states of melanoma[END_REF]. However, our results are in line with the observation that BRAFi modulates actin reorganization and YAP/TAZ activation [START_REF] Kim | Actin remodeling confers BRAF inhibitor resistance to melanoma cells through YAP/TAZ activation[END_REF] as well as Rho GTPase signaling [START_REF] Klein | B-RAF regulation of Rnd3 participates in actin cytoskeletal and focal adhesion organization[END_REF]. Thus, our findings underscore the exquisite phenotypic plasticity of melanoma cells and the notion that their biomechanical reprogramming may actively participate to tumor heterogeneity and therapeutic escape.

Another indication of the ability of targeted therapies to switch melanoma cells towards a CAF-like phenotype is based on our findings that BRAFi induces melanoma cells to autonomously remodel a fibrillar and drug-protective ECM network, an additional trait typical of CAFs. A previous study has shown that short-term BRAF inhibition up-regulates adhesion signaling and drug tolerance in BRAF-mutant/PTEN-null melanoma cells [START_REF] Fedorenko | Fibronectin induction abrogates the BRAF inhibitor response of BRAF V600E/PTEN-null melanoma cells[END_REF]. Extending this observation, our data demonstrate that short-term MAPK pathway inhibition induces the assembly by melanoma cells of an aligned ECM containing collagens, fibronectin and thrombospondin-1, indicating that targeted therapies have the capacity to rapidly exacerbate the intrinsic ability of melanoma cells to produce a pro-invasive ECM [START_REF] Gaggioli | Tumorderived fibronectin is involved in melanoma cell invasion and regulated by V600E B-Raf signaling pathway[END_REF][START_REF] Chapman | Heterogeneous tumor subpopulations cooperate to drive invasion[END_REF]. Vemurafenib treatment was shown to activate melanoma-associated fibroblasts to generate a drug-tolerant niche through fibronectin-mediated integrin β1/FAK signaling [START_REF] Hirata | Intravital imaging reveals how BRAF inhibition generates drug-tolerant microenvironments with high integrin beta1/FAK signaling[END_REF]. In this study, cell death following BRAF inhibition was reduced when melanoma cells were cultured on stiff substrates containing the combination of fibronectin, thrombospondin-1 and tenascin-C [START_REF] Hirata | Intravital imaging reveals how BRAF inhibition generates drug-tolerant microenvironments with high integrin beta1/FAK signaling[END_REF]. A part from ECMs assembled by therapy-activated fibroblasts, our study reveals a crucial role of fibronectin and collagen-rich ECMs derived from either drug-resistant or drug-exposed melanoma cells in driving tolerance. The protection against the cytostatic effect of MAPK inhibition brought by melanoma-derived matrices is evidenced by the persistence of cycling cells, with sustained levels of proliferative markers and YAP/MRTF nuclear translocation.

Remarkably, tolerance to BRAFi was achieved when BRAF-mutant melanoma cells were plated on collagen-coated stiff matrices, supporting the notion that, in addition to fibronectin [START_REF] Hirata | Intravital imaging reveals how BRAF inhibition generates drug-tolerant microenvironments with high integrin beta1/FAK signaling[END_REF][START_REF] Fedorenko | Fibronectin induction abrogates the BRAF inhibitor response of BRAF V600E/PTEN-null melanoma cells[END_REF], the collagen network and ECM stiffening are major mediators of melanoma drug resistance. Interestingly, previous studies with bioengineered materials have shown the impact of substrate stiffness on targeted drugs responses in melanoma [START_REF] Tokuda | Modulation of matrix elasticity with PEG hydrogels to study melanoma drug responsiveness[END_REF] and carcinoma cell lines [START_REF] Nguyen | Sorafenib resistance and JNK signaling in carcinoma during extracellular matrix stiffening[END_REF].

YAP-TEAD and MRTF-SRF pathways functionally interact to coordinate mechanosignaling required for the maintenance of the CAF phenotype in solid tumors [START_REF] Calvo | Mechanotransduction and YAP-dependent matrix remodelling is required for the generation and maintenance of cancer-associated fibroblasts[END_REF][START_REF] Finch-Edmondson | Framework to function: mechanosensitive regulators of gene transcription[END_REF][START_REF] Foster | Mutual dependence of the MRTF-SRF and YAP-TEAD pathways in cancer-associated fibroblasts is indirect and mediated by cytoskeletal dynamics[END_REF][START_REF] Cordenonsi | The Hippo transducer TAZ confers cancer stem cell-related traits on breast cancer cells[END_REF]. Similarly, we showed that the contractile behavior of the de-differentiated resistant melanoma cells requires YAP and MRTF expression. Importantly, we found that YAP and MRTF are activated upon mechanical stress and contribute to ECM-mediated drug resistance. This is in agreement with recent reports demonstrating the contribution of the YAP pathway in BRAFi resistance [START_REF] Lin | The Hippo effector YAP promotes resistance to RAF-and MEK-targeted cancer therapies[END_REF][START_REF] Kim | Actin remodeling confers BRAF inhibitor resistance to melanoma cells through YAP/TAZ activation[END_REF][START_REF] Verfaillie | Decoding the regulatory landscape of melanoma reveals TEADS as regulators of the invasive cell state[END_REF]. However, these studies were conducted on rigid plastic dishes that do not reflect tissue mechanical compliance. In contrast, we demonstrated the exacerbated ability of dedifferentiated resistant and BRAFi-exposed melanoma cells to adapt to substrate rigidity using cell-derived 3D ECMs and collagen-coated hydrogels with defined stiffness, which model more accurately the activation of YAP and MRTF mechanosensors. In contrast to YAP-TEAD pathway, the role of MRTF-SRF pathway in melanoma therapeutic resistance remains less defined. MRTF controls several cytoskeletal genes, including α-SMA and MLC2 (8) that we found enriched in the MITF low /AXL high resistant cells and in MITF low tumor biopsies from progressing melanoma patients. Moreover, several components of the matrisome from MITF low resistant cells, such as tenascin-C, CYR61, thrombospondin-1 and serpine1 are known YAP and/or MRTF targets [START_REF] Foster | Mutual dependence of the MRTF-SRF and YAP-TEAD pathways in cancer-associated fibroblasts is indirect and mediated by cytoskeletal dynamics[END_REF]. Remarkably, a YAP1 enrichment signature has also been identified as a driver event of melanoma acquired resistance [START_REF] Hugo | Non-genomic and Immune Evolution of Melanoma Acquiring MAPKi Resistance[END_REF]. This is in line with our in silico gene expression analyses from public datasets that revealed a similar trend towards an increased expression of YAP/MRTF target genes in MITF low tumor biopsies from patients relapsing from therapy. Of note, a recent study identified AXL, a RTK required to maintain the resistant phenotype in melanoma [START_REF] Muller | Low MITF/AXL ratio predicts early resistance to multiple targeted drugs in melanoma[END_REF], in a YAP/TAZ target gene signature [START_REF] Wang | Comprehensive Molecular Characterization of the Hippo Signaling Pathway in Cancer[END_REF]. Accordingly, we found several YAP/MRTF target genes including AXL induced upon BRAFi treatment in our xenograft model. This raises the possibility that the reservoir of AXL high resistant cells is promoted by biomechanical adaptation of melanoma cells to oncogenic BRAF pathway inhibition. Interestingly, collagen stiffening has been recently shown to promote melanoma differentiation via YAP/PAX3-mediated MITF expression [START_REF] Miskolczi | Collagen abundance controls melanoma phenotypes through lineage-specific microenvironment sensing[END_REF]. This study and our present report support the emerging notion that collagen density and rigidity is a key microenvironmental factor that governs melanoma cell plasticity and intra-tumor heterogeneity. How YAP and MRTF actually coordinate mechanical signals from tumor microenvironments to drive melanoma differentiation, invasive behavior or drug resistance is currently unknown and requires further investigations. Importantly, our data reveal a targetable vulnerability of Vemurafenib-induced mechanical reprograming of melanoma in vivo. Melanoma tumors treated with BRAFi or combined BRAFi/MEKi therapy displayed an intense remodeling of the tumor niche associated to increased collagen fibers organization and YAP/MRTF-mediated gene expression. Earlier studies have underscored the critical role of melanoma-associated fibroblasts activated by BRAF inhibition for the development of resistant niches [START_REF] Straussman | Tumour micro-environment elicits innate resistance to RAF inhibitors through HGF secretion[END_REF][START_REF] Kaur | sFRP2 in the aged microenvironment drives melanoma metastasis and therapy resistance[END_REF][START_REF] Hirata | Intravital imaging reveals how BRAF inhibition generates drug-tolerant microenvironments with high integrin beta1/FAK signaling[END_REF][START_REF] Fedorenko | BRAF Inhibition Generates a Host-Tumor Niche that Mediates Therapeutic Escape[END_REF]. Accordingly, we found that host stromal cells that likely include fibroblasts produce some ECM genes in response to Vemurafenib. However, we demonstrated that the molecular changes associated with the dramatic remodeling of the tumor niche in response to MAPK pathway inhibition also results from the activation of human melanoma cells, thereby promoting an autocrine production of a rigid ECM enriched in collagen fibers. In line with the key role of the YAP pathway during melanoma relapse [START_REF] Hugo | Non-genomic and Immune Evolution of Melanoma Acquiring MAPKi Resistance[END_REF] and phenotypic heterogeneity [START_REF] Verfaillie | Decoding the regulatory landscape of melanoma reveals TEADS as regulators of the invasive cell state[END_REF], we found that YAP-TEAD inhibition by Verteporfin reverses Vemurafenib-induced excessive collagen deposition.

Consequently, melanoma tumors treatment with Verteporfin cooperated with Vemurafenib to reduce tumor growth. Whether targeting MRTF-SRF signaling pathway may also demonstrate therapeutic efficiency is currently under investigation.

In conclusion, our findings disclose a novel mechanism of BRAF-mutant melanoma cells adaptation to MAPK-targeted therapies through the acquisition of an auto-amplifying CAF-like phenotype in which melanoma cell-derived ECM modulates mechanosensing pathways to promote tumor stiffening. In addition to therapy-induced tumor secretomes [START_REF] Obenauf | Therapy-induced tumour secretomes promote resistance and tumour progression[END_REF], therapyinduced mechanical phenotypes could endow cancer cells with unique cell-autonomous abilities to survive and differentiate within challenging tumor-associated microenvironments, thereby contributing to drug resistance and relapse. Our results suggest that cancer cell-ECM interactions and tumor mechanics provide promising targets for therapeutic intervention aimed at enhancing targeted therapies efficacy in melanoma.

FIGURES LEGENDS

  Acquisitions were achieved simultaneously in backward through 10x dry NA 0.45 objective and forward through condenser NA 0.55. Each side is equipped with dual NDD GaAspP detectors (BiG) with 440/10 (for SHG forward and backward) and 525/50 filter (for autofluorescence). Transmission images were acquired with 514nm laser through the 525/50 filter. Cell line-derived xenograft (CDX) tumor models. Mouse experiments were carried out in accordance with the Institutional Animal Care and the local ethical committee (CIEPAL-Azur agreement NCE/2014-179). 1 × 10 6 melanoma cells were subcutaneously implanted into both flanks of 6 week old female athymic nude nu/nu mice (Envigo). When tumor reached 100 mm 3 , mice were randomly grouped into control and test groups. The BRAFi group received 6 intraperitoneal injections of Vemurafenib (35 mg/kg) over a period of 2 weeks. Verteporfin was delivered intraperitoneally three times per week at 45 mg/kg. Mice in the control group were treated with vehicle. At the end of the experiment, mice were sacrificed, tumors were dissected, weighed, and either snap frozen in liquid nitrogen (for mRNA and protein analysis), in Tissue-Tek O.C.T. (VWR) (for AFM analysis) or formalin fixed and paraffin embedded for picrosirius red staining, SHG analysis and immunohistochemistry. Patient-derived xenograft (PDX) tumor models. PDX models were developed by TRACE

Figure 1 :

 1 Figure 1: Mesenchymal BRAFi-resistant melanoma cells display increased mechanosensitivity and proliferation on collagen stiff substrate. (A) Representative images of parental (M238P) versus mesenchymal BRAFi-resistant (M238R) cell morphology after 48 h culture on collagen-coated hydrogels of increasing stiffness (low: 0.2 kPa; medium: 4 kPa; high: 50 kPa). Fluorescence stains represent F-actin (green) and nucleus (blue). Scale bar, 100 µm. Insets show higher magnification views. (B) Quantification of cell morphological changes (area, roundness). Data is represented as scatter plot with mean ± s.d. from 10 samples. **P<0.01, ***P<0.001, Kruskall-Wallis analysis. (C) Morphology of mesenchymal BRAFi-resistant M229R and of BRAFi-resistant M249R harboring a secondary NRAS mutation cells compared to parental cells, 48 h after plating on hydrogels of intermediate stiffness (4 kPa). Fluorescence stains represent F-actin (green) and nucleus (blue). Scale bar, 100 µm. Insets show higher magnification views. (D) Quantification of morphological changes (area, roundness) of M229R, M249R and their parental lines (M229P, M249P) on hydrogels of medium stiffness. Data is represented as scatter plot with mean ± s.d from 10 samples. *P<0.05, **P<0.01, ***P<0.001, Kruskall-Wallis analysis. (E) Bar plot of cell number quantification of parental and resistant melanoma cells cultured for 72 h on collagen low (0.2 kPa) versus high (50 kPa) stiffness. Cells were counted by Hoechst-labeled nuclei staining. Data are normalized to the parental cells on soft substrate. *P<0.05, **P<0.01, ***P<0.001, 2way ANOVA analysis.

Figure 2 :

 2 Figure 2: The mechanosensors YAP and MRTF are activated in mesenchymal BRAFiresistant melanoma cells. Effect of substrate stiffening on YAP (A) and MRTF (B) nuclear translocation assessed by immunofluorescence in M238P versus M238R cells cultured for 48 h on collagen-coated hydrogels of increasing stiffness. Left panels, representative images. Insets show nuclei staining by DAPI on the same fields. Scale bar, 40 µm. Right panels, bar graphs show the proportion of single cells in which YAP and MRTF were located either in the nucleus (N) or in the cytoplasm (C), as a function of stiffness (n = 3; 30 cells/condition per experiment). (C) qPCR analysis of the expression of YAP-MRTF target genes in M238P and M238R cells plated for 48 h on substrates with increased stiffness (low: 0.2 kPa; medium: 4 kPa; high: 50 kPa). Data are normalized to the expression in parental cells plated on soft (L) substrate. Data is represented as mean ± s.d. from 3 samples. *P<0.05, **P<0.01, ***P<0.001,

Figure 3 :

 3 Figure 3: Mesenchymal BRAFi-resistant melanoma cells produce an organized ECM fibrillar network through increased contraction forces and contractility. (A) Immunoblot analysis of myofibroblast markers on lysates from BRAFi-resistant cells compared to parental cells. HSP90, loading control. (B) Heat scale plot showing the traction forces applied by M238P versus M238R seeded on 4kPa fluorescent bead-embedded collagencoated hydrogels for 48 h. Bottom panel, quantification of contractile forces applied by the cells. Data is the mean ± s.d. (n=30 fluorescent bead displacement measured per cell from 6 cells). ***P<0.001, Kruskall-Wallis analysis. (C) Collagen gel contraction assays of M238P and M238R cells in presence or not of Y27632 (10 µM) or Verteporfin (1 µM). Representative images of contraction assays are shown. Bottom panel, quantification of gel contraction (percent). Bar graph represents the mean ± s.d. of triplicate experiments. ***P<0.001, Kruskall-Wallis test. (D) Collagen gel contraction assays of M238R transfected with a siRNA Control (siCtrl), siYAP or siMRTF. Representative images of contraction assays are shown. Bottom panel, quantification of the percentage of gel contraction. Bar graph is mean ± s.d. of triplicate experiments. **P<0.01, ***P<0.001. (E) Fibronectin and collagen staining of decellularized 3D ECM derived from M238P cells, M238R cells or skin fibroblasts. Top panels, anti-fibronectin immunofluorescence; Bottom panels, picrosirius red staining. Scale bar, 50 µm. (F) Quantification of fibronectin fibers orientation in ECMs from parental and BRAFiresistant cells. Fibronectin fibers were visualized as in (D) and their orientation angles plotted as a frequency distribution. Percentages indicate oriented fibers accumulated in a range of ± 21° around the modal angle. Data is represented as mean ± s.d. (n=10 random fields from a

Figure 4 :

 4 Figure 4: MAPK signaling inhibition triggers mechanoactivation pathways, melanoma cell contractility activity and ECM fibril alignment. (A) Representative images of YAP and MRTF immunostaining of drug-sensitive 1205Lu cells plated for 48 h on 2.8kPa collagencoated hydrogels and treated with 1% DMSO (vehicle), 3 µM Vemurafenib (BRAFi) or 1 µM Trametinib (MEKi). Scale bar, 40 µm. Insets show nuclei staining by DAPI on the same images. Bottom panels, quantification of the nucleocytoplasmic distribution of YAP (left) and MRTF (right) (n = 3; 30 cells/condition per experiment). (B) Collagen gel contraction assays of 1205Lu cells pre-treated for 72 h with 1% DMSO (vehicle), 3 µM Vemurafenib (BRAFi) or 1 µM Trametinib (MEKi). Right panel, quantification of the percentage of gel contraction. Bar graph is the mean ± s.d. of triplicate experiments. ***P<0.001. (C) Immunoblot analysis of ECM proteins and cell proliferation markers on lysates from M238P and 1205Lu cells treated as above. Tubulin, loading control. (D) Immunofluorescence analysis of fibronectin and collagen I fibers assembly in decellularized ECM generated from 1205Lu cells treated with vehicle (DMSO) or Vemurafenib for 7 days. Scale bar, 40 µm. Left histograms, quantification of fibronectin fibers orientation. Percentages indicate fibers accumulated in a range of ± 21° around the modal angle. (E) Indicated melanoma cells were cultured on low (0.2 kPa) versus high (50 kPa) stiffness substrate for 72 h in the presence of the indicated dose of Vemurafenib. Bar graphs show cell number quantification by Incucyte analysis of NucLight red-labeled cell nuclei. Data are normalized relative to the number of cells on soft substrate and 1µM Vemurafenib. *P<0.05, **P<0.01, ***P<0.001, 2-way ANOVA analysis.

Figure 5 :

 5 Figure 5: Early adaptation and mesenchymal-associated resistance to MAPK pathway inhibition is associated with the production of a drug-protective ECM. (A) Proliferation curves of 501Mel cells cultured on decellularized 3D cell-derived matrices generated from parental (M238P) or BRAFi-resistant (M238R) melanoma cells and treated with vehicle or

Figure 6 :

 6 Figure 6: Matrices generated by resistant melanoma cells induces YAP and MRTF activation to confer protection to MAPK pathway inhibition. (A) 501Mel cells were cultured on M238P or M238R cell-derived matrices for 48 h and subjected to immunofluorescence analysis of YAP (red) and MRTF (green). Insets show nuclei staining by DAPI on the same fields. Scale bar, 40 µm. Right panel, quantification of the nucleocytoplasmic distribution of YAP and MRTF (n>30 cells, ***P<0.001). P-values were determined using Mann-Whitney U test. (B) RT-qPCR analysis of shared YAP/MRTF target genes expression in 501Mel cells obtained from A. Data is represented as mean ± s.d. from 3 samples. *P<0.05, **P<0.01, 2-way ANOVA analysis. (C, D) Bar graphs showing the quantification of cell proliferation of 501Mel plated on M238P or M238R cell-derived matrices and treated for 72 h with vehicle or with 2 µM Vemurafenib in combination or not with 0.1 µM Trametinib following transfection with control siRNA (siCtrl) or YAP (siYAP) siRNA (C), or following transfection with siCtrl or MRTF (siMRTF) siRNA (D). Data are the mean ± s.d. (n=3). *P<0.05, ***P<0.001 (2 way-ANOVA). Right panels in C and D show immunoblots of YAP and MRTF levels in transfected cells. HSP60, loading control. (E, F) Immunoblot analysis of cell cycle

Figure 7 :

 7 Figure 7: In vivo MAPK inhibition drives melanoma cell biomechanical reprogramming and tumor stiffening in human melanoma tumors. (A) Sections of 1205Lu melanoma cellderived xenografts (CDX) treated with DMSO (vehicle) or with Vemurafenib (BRAFi) were stained with picrosirius red and imaged under original bright field (parallel, top) or polarized light (orthogonal, bottom). Scale bar, 500 µM. Collagen fibers area was quantified from picrosirius red stainings with Image J software. Values represent mean ± s.d. of 4 independent fields. *P<0.05, **P<0.01. (B) Second harmonic generation (SHG)microscopy from samples described in (A). Scale bar, 500 µM. SHG intensity was quantified with Image J software. Values represent mean ± s.d. of 4 independent fields. *P<0.05, **P<0.01. (C) Heatmap showing the differential expression of a selection of human and mouse ECM genes, dedifferentiation markers and YAP/MRTF target genes in untreated versus Vemurafenib-treated 1205Lu melanoma tumors. Gene expression was assessed by RT-qPCR. (D) Scatter plot with mean ± s.d. showing Young's modulus (Eapp) measurements of vehicle and Vemurafenib-treated 1205Lu tumors. ****P<0.0001. (E) Tumor sections obtained from melanoma patient-derived xenografts (PDX) that were treated or not with BRAFi (Dabrafenib) and MEKi (Trametinib) were stained with hematoxylin/eosin or picrosirius red, and imaged under transmission (parallel) or polarized light (orthogonal) microscopy. Scale bar, 150 µM. (F) Collagen fibers area was quantified from picrosirius red stainings with Image J software. Values represent mean ± s.d. of 4 independent fields. (G) 1205Lu cells (1 x 10 6 ) were injected s.c. into nude mice. Tumor volume was assessed with caliper and when tumors reached 100 mm 3 , mice were randomized into four groups and were administered (i.p. injection) vehicle (DMSO), Vemurafenib (BRAFi) (35 mg/kg), Verteporfin (a YAP/TEAD inhibitor) (45 mg/kg), or the combination of Vemurafenib and Verteporfin for 19 days. Data shown are mean ± s.d. Left panels, photographs of representative mice and tumors taken at day 19 are shown. (H) Bar graphs showing tumor weights at the end of the experiments shown in G. Data are means ± s.d. (n=6; *P<0.05, **P<0.01, ***P<0.01, Kruskall-Wallis test). (I) Sections of 1205Lu melanoma CDX tumors from the experiment shown in G were stained with hematoxylin/eosin or picrosirius red, and imaged under transmission (parallel) or polarized light (orthogonal) microscopy. (J) Bar graphs showing the quantification of collagen fibers area on images of tumor sections obtained from I. Values are the mean ± s.d. of 4 independent fields. **P<0.01,

Figure 1 D

 1 Figure 1

Acknowledgments. We thank R.S. Lo for M229P/R, M238P/R and M249P/R melanoma cells.

We acknowledge the C3M animal room facility and the C3M imaging facility. The SHG microscopy was done at MICA facility, in the IBV-CNRS UMR 7277-INSERM U1091-UNS. We thank TRACE (PDX platform at the KULeuven University) for providing the PDX models.

Financial support: This work was supported by funds from Institut National de la Santé et de la Recherche Médicale (Inserm), Ligue Contre le Cancer, Institut National du Cancer (INCA_12673), Fondation ARC, ITMO Cancer Aviesan (Alliance Nationale pour les Sciences de la Vie et de la Santé, National Alliance for Life Science and Health) within the framework of the Cancer Plan, and the French Government (National Research Agency, ANR) through the ''Investments for the Future'' LABEX SIGNALIFE: program reference # ANR-11-LABX-0028-01. We also thank financial supports by Conseil général 06 and Canceropôle PACA. R.B.J. was a recipient of a doctoral fellowship from Fondation ARC. I.B. was a recipient of a doctoral fellowship from La Ligue Contre le Cancer.


Raguet Hugo
email: <hugo.raguet@lilo.org>.

Landrieu Loic

Parallel Cut Pursuit For Minimization of the Graph Total Variation

We present a parallel version of the cut-pursuit algorithm for minimizing functionals involving the graph total variation. We show that the decomposition of the iterate into constant connected components, which is at the center of this method, allows for the seamless parallelization of the otherwise costly graph-cut based refinement stage. We demonstrate experimentally the efficiency of our method in a wide variety of settings, from simple denoising on huge graphs to more complex inverse problems with nondifferentiable penalties. We argue that our approach combines the efficiency of graph-cuts based optimizers with the versatility and ease of parallelization of traditional proximal splitting methods.

Introduction

In 2017, [START_REF] Landrieu | Cut pursuit: Fast algorithms to learn piecewise constant functions on general weighted graphs[END_REF] introduced the cutpursuit algorithm, a working-set algorithm for minimizing functionals involving the total variation structured by a graph G " pV, E, wq , w P R E `being edge weights:

F : x P Ω V Þ Ñ f pxq `ÿ pu,vqPE w pu,vq x u ´xv . (1)
where x " px v q vPV P Ω V is the variable of interest and Ω is some base space, typically R or R n , n P N ˚. The core idea of this approach is to exploit the coarseness of the solution, i.e. the fact that it can be decomposed into a small number of constant connected graph components of the graph compared to the total number of vertices. This method was further refined by [START_REF] Raguet | Cut-pursuit algorithm for regularizing nonsmooth functionals with graph total variation[END_REF], allowing for the efficient regularization of a larger class of functionals. In particular, they dropped the convexity requirements in the optimality analysis, and extended the

The cut-pursuit algorithm starts by associating all vertices to the same constant connected component and then repeats the two following steps: reduction and refinement.

In the reduction step, the problem is solved under the constraint that all vertices in a same component have the same value. On many problems, when the number of constant connected components is smaller than the number of vertices in the graph, the reduced problem can be solved more efficiently than the original one, as it has fewer variables. In the refinement step, new "degrees of freedom" are added by splitting each constant connected component into smaller ones, based on a subproblem involving the directional derivatives of the functionals and which can be solved by graph cuts. This process is illustrated in Figure 1.

This scheme provably converges to a critical point in a finite number of steps; ensuring global optimality in the convex case. When the number of constant connected components of the solution is actually small, only a few iterations are needed for convergence. Succinctly, this approach allows to solve a wide range problems regularized by the graph total variation, in a little more than a few graph cuts.

In contrast, classical first-order proximal algorithms require many iterations, each of them updating all variables. Still, they attract considerable attention, notably because they can be preconditioned and easily parallelized; see for instance [START_REF] Raguet | Preconditioning of a generalized forward-backward splitting and application to optimization on graphs[END_REF][START_REF] Möllenhoff | Combinatorial preconditioners for proximal algorithms on graphs[END_REF][START_REF] Kumar | Convex optimization for parallel energy minimization[END_REF][START_REF] Padilla | The dfs fused lasso: Linear-time denoising over general graphs[END_REF][START_REF] Barbero | Modular proximal optimization for multidimensional total-variation regularization[END_REF]. On the other hand, the efficient use of graph cuts is reminiscent of the method of [START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF], which uses a parametric maximum flow formulation. However, the latter can only be used to compute the proximity operator of the graph total variation (also called "graph total variation denoising", or "graph fused LASSO signal approximation"), that is f restrained to a sum of square differences. Not only can our method handle a much more general class of problems, but now that it can be parallelized, it combines the advantages of both proximal and graph cuts-based methods.

Method

Reduced Problem

We consider V " tU 1 , . . . , U |V| u a partition of the vertices V of graph G. We define the reduced problem as minimizing the objective functional F under the constraint that the variable is constant over each component of the partition:

F pVq : ξ P Ω V Þ Ñ F p ÿ U PV ξ U b 1 U q , where ξ U b 1 U P Ω V is a notation for pξ U b 1 U q v " ξ U if v P U , 0 otherwise. In many problems, ξ Þ Ñ f p ř U PV ξ U b 1 U q
has regularity and structure similar to f . But since the reduced problem can be rewritten as a problem of only |V| variables, F pVq is easier to solve than F , typically with preconditioned first-order proximal splitting algorithms.

Refinement

The goal of the refinement step in the cut pursuit algorithm is to split the current partition V such that the solution of the next reduced problem can decrease the objective functional F as much as possible. This is done by considering firstorder information through finding a steepest directional derivative of F at the current iterate x " ř U PV ξ U b 1 U , where ξ is the solution of the last reduced problem:

d pxq P arg min dPΩ V F 1 px, dq .
Interestingly, to make the problem more tractable, the space of directions to consider can be restricted to a finite set D. [START_REF] Landrieu | Cut pursuit: Fast algorithms to learn piecewise constant functions on general weighted graphs[END_REF] show that if f is differentiable and Ω " R, D " t´1, 1u V is sufficient to retain optimality at convergence. [START_REF] Raguet | Cut-pursuit algorithm for regularizing nonsmooth functionals with graph total variation[END_REF] extend this result to functions f with a nondifferentiable part which is separable along the graph G, with D " t´1, 0, 1u V . Furthermore, they provide heuristic direction sets

D pxq " Ś vPV D pxq v for multidimensional Ω.
The search for a steepest descent direction restricted to a finite set D defines a new partition by computing the cross partition between the current partition and the maximal constant connected components of d pxq . This problem is a combinatorial optimization problem involving unary and binary terms:

F 1 px, dq " ÿ vPV δpx, d v q `ÿ pu,vqPE pxq " w u,v d u ´dv , (2)
where E pxq " " tpu, vq P E | x u " x v u. In the monodimensional case, this problem is equivalent to finding a minimum cut in a convenient flow graph; in the multidimensional case, it can be solved approximately via a series of graph cuts.

Parallelization

In practice, the refinement step is often the computational bottleneck of the cut-pursuit algorithm. While there exists very efficient graph cut solvers, they require a lot of memory and are not well-suited to parallelization. Now, since the only binary terms in (2) are for edges within the constant components of x, the steepest descent problem is separable along the components of V:

F 1 px, dq " ÿ U PV F 1 U px U , d U q , with for all U P V, F 1 U px U , d U q " ÿ vPU F 1 px v , d v q `ÿ pu,vqPE pxq " XU 2 w u,v d u ´dv ,
where we note d U " td v u vPU . Consequently, this problem can be decomposed into finding the steepest descent direction

d pxq U P D pxq U " Ś vPU D pxq v in each component U independently.
This allows us to perform the graph cuts in parallel with only a slight adaptation of augmenting path graph cut methods such as the one of [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF], and with no supplementary memory cost.

The above modifications already allows us to significantly speed up the cut-pursuit algorithm. However, thread utilization can still be improved. Indeed, when performing the split step in parallel along components, each component is assigned to a single thread, thus the computation is at least as long as the time required for splitting the hardest one, typically the largest. If the partition is unbalanced, this can lead to most threads being idle while the last one finishes. Consider in particular the very first iteration, in which the partition only has one component.

A naive approach would be to cap the maximal number of vertices in each component of V according to the problem size and the number of available threads; coherence with the graph structure could be enforced by greedily constructing each component with breadth-first search, until the component is exhausted, or until the cap is reached. However, such arbitrary balancing components might not be beneficial for the reduced problem: in nonconvex settings, they might lead to bad local minima, and even in convex settings, they might not be consistent with the structure of the main problem and both slow down and reduce the accuracy of the solution.

For this reason, we advocate to decompose large components only for the split step; then modifying the augmenting path algorithm accordingly to perform the graph cuts in parallel along these components. In a nutshell, this corresponds to isolating the balancing components by setting their border edge capacities to 0 instead of w u,v d u ´dv as they would be normally set to in the steepest direction problem. Unfortunately, the corresponding minimum cuts now solve only approximately the original problem.

As edges separating the balancing components are ignored by these parallel graph cuts, the question remains as how to define the new partition of a large component from the steepest directions found for its balancing components. Observe that all vertices of a component U share the same set of candidate directions D pxq U , even in the multidimensional setting where it might change from one component to another. Consequently, the balancing components partitioning a given large component also share the same direction set. We can can thus refine U from d pxq U regardless of the presence of balancing components.

Note that this is not the only possible strategy. Depending on the problem at hand, it might still be relevant to apply the naive approach, or to compensate the discarded edge capacities by adjusting unary terms. However, the strategy presented here provided the most consistent improvement across our numerical experiments (alternative not shown).

We stress that solving only approximately the steepest direction problem invalidates the theoretical guarantees of the Algorithm 1 Parallel Cut Pursuit (PCP)

Initialize: V " tV u repeat -----reduced problem ----- Find: ξ pVq stationary point of F pVq x Ð ř U PV ξ pVq U b 1 U -----parallel refinement ----- for all U P V do in parallel Find: d pxq U P D pxq U minimizing F 1 U px, d U q UÐ max. constant connected components of d pxq U V Ð VztU u Y U end for until V does not change
monodimensional setting, and might degrade the approximation further in the multidimensional setting. Although our experiments display this effect, they also show that such solutions remain satisfying at usual precision levels.

Let us finally note that there is still room for many improvements. For instance, finding rationales replacing the greedy breadth-first construction of the balancing components, or even randomizing it along iterations, might alleviate further the suboptimality. More importantly, in-depth study of the graph cuts complexity might suggest better parallel scheduling than a balancing only based on the number of involved vertices. This exploration is however beyond the scope of the present work, and left for future research.

Numerical Experiments

In this section, we show that our algorithm outperforms not only the highly specialized parametric maximum flow approach for the simpler problem of the proximity operator of the graph total variation, but also flexible preconditioned proximal algorithms on ill-conditioned problems involving several nondifferentiable regularizers beyond the total variation. All experiences are run on a 14-cores, 28-threads i9-7940X CPU 3.10GHz with 64 GB RAM.

Throughout this section, we compare our approach to the following state-of-the-art algorithms:

• PMF: the parametric max flow-based algorithm of [START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF] for the proximity operator of the graph total variation;

• PFDR: the preconditioned Forward-Douglas-Rachford splitting algorithm of [START_REF] Raguet | A note on the forward-douglas-rachford splitting for monotone inclusion and convex optimization[END_REF], with all proximal steps parallelized;

• CP: the cut pursuit algorithm of [START_REF] Raguet | Cut-pursuit algorithm for regularizing nonsmooth functionals with graph total variation[END_REF], using PFDR to solve the reduced problem;

• PCP: our proposed parallelization of CP, without balancing the parallel workload distribution; • PCP-balanced: PCP with balancing.

Point Cloud Reflectance Regularization: We consider the problem of spatially regularizing LiDAR reflectance on a large point cloud acquired with a mobile scanning vehicle as described by [START_REF] Paparoditis | Stereopolis ii: A multi-purpose and multi-sensor 3d mobile mapping system for street visualisation and 3d metrology[END_REF]. The problem is defined as a graph-total variation denoising problem f : x Þ Ñ x ´y 2 with y the observed noisy reflectance. G is the 5-nearest-neighbors graph of the point cloud (|V | " 109 412 178 and |E| " 317 096 212).

Brain Source Identification in Electroencephalography

We consider the inverse problem of brain source identification in Electroencephalography. The brain of a patient is mapped to a triangular mesh with adjacency structure G " pV, Eq with |V | " 19 626 and |E| " 29 439. A set of N " 91 electrodes records the brain activity y P R N of the patient and the goal is to retrieve the activity on the mesh G. The relationship between the electrodes output and the brain activity is given by the lead-field operator φ : R V Þ Ñ R N . To model the regularity, sparsity and positivity of brain signals, we chose

f : x Þ Ñ 1 2 y ´φx 2 `ÿ vPV `λv |x v | `ιR`p x v q ˘,
with λ v the parameters of the weighted LASSO regularization and ι R`t he set indicator function of R `.

Point Cloud Classification Regularization We consider the problem of spatially regularizing a noisy semantic labeling of a point cloud with class set K [START_REF] Hackel | NET: A new large-scale point cloud classification benchmark[END_REF]. G is the 10-nearest-neighbors graph of the point cloud, (|V | " 3 000 111 and |E| " 17 206 938). A noisy classification y P R V ˆK is obtained from a random forest classifier trained on handcrafted geometric features as described by [START_REF] Guinard | Weakly supervised segmentationaided classification of urban scenes from 3d lidar point clouds[END_REF]. Noting ι ∆ K the convex indicator of the standard simplex in dimension |K|, and KL pr, sq " ř kPK r k logpr k {s k q the Kullback-Leibler divergence, we choose

f : x Þ Ñ KL pβu`p1´βqy v , βu`p1´βqx v q`ÿ vPV ι ∆ K px v q,
with u " p1{ |K|q kPK the uniform discrete distribution and β a smoothing constant (taken as 10 ´1).

We report performances in Figure 2. All cut-pursuit approaches significantly outperform PFDR. Our parallelization scheme further increases this gap by a large margin for the large-scale point cloud regularization problems, even outperforming the specialized PMF. In contrast, parallelization brings virtually no gain for the medium-scale brain source identification problem. Then, balancing the parallel workload distribution of the split step is beneficial in terms of speed, in particular for the classification regularization problem, in which one of the components (the road in the middle of the scene) comprises half of the vertices. However, it can be seen that the balanced version stops at a suboptimal solution, which is nonetheless close to solutions found by the others (data not shown). Finally for the brain source identification problem, our balancing method is detrimental both in terms of speed and of accuracy. Our interpretation is that it misses the important sparsity structure of the problem and the strong correlation between the variables introduced by the lead-field operator.

Conclusion

We introduce the first fully parallel graph-cut based approach for graph total variation minimization. It combines the advantages of traditional first-order proximal splitting algorithms and specialized graph cut-based methods. It significantly outperforms the state-of-the-art on many of the currently used total variation-regularization formulations.

We provide an implementation of our method, in C++ parallelized with OpenMP, with interfaces for GNU Octave, Matlab and Python, at one of the authors GitHub repository /1a7r0ch3/parallel-cut-pursuit.

Figure 2 .

 2 Figure 2. Objective functional against the running time of the algorithms; optimal values are estimated by longest, high-precision runs.

  Illustration of the cut pursuit algorithm. The vertices of a graph G are initially combined into a single component. This graph is recursively split into constant connected components. At each iteration, a reduced graph G encoding the adjacency between constant components is computed. The values associated with each constant components can be computed using the smaller reduced graph. The vertex colors represent their values, from low in blue to high in red.

	Reduction	Refinement	Reduction	Refinement	Reduction
	G
	G
	Figure 1.