Marta Félez-Sánchez

Marleny Vergara

Silvia De Sanjosé

Xavier Castellsagué

Laia Alemany

Ignacio G Bravo
email: ignacio.bravo@ird.fr

Hidden papillomavirus diversity in vulva, penis and oropharyngeal cancers

Keywords: Cutaneous, HPVs, DNA, Broad-spectrum PCR, BetaPVs, SPF10/DEIA, FFPE

Human Papillomaviruses (HPVs) are involved in the etiology of anogenital and head and neck cancers. The HPV DNA prevalence greatly differs by anatomical site. Indeed, the high rates of viral DNA prevalence in anal and cervical carcinomas contrast with the lower fraction of cancer cases attributable to HPVs in other anatomical sites, chiefly the vulva, the penis and head and neck. Here we analyzed 2635 Formalin Fixed Paraffin Embedded surgical samples that had previously tested negative for the presence of HPVs DNA using the SPF10/DEIA procedure, in order to identify the presence of other PVs not explicitly targeted by standard molecular epidemiologic approaches. All samples were reanalyzed by using five broad-PV PCR primer sets (CP1/2, FAP6064/FAP64, SKF/SKR, MY9/MY11, MFI/MFII) targeting the main PV main clades. In head and neck carcinoma samples (n=1141), we recovered DNA from two BetaHPVs, namely HPV20 and HPV21, and from three cutaneous AlphaPVs, namely HPV2, HPV57 and HPV61. In vulvar squamous cell carcinoma samples (n=902), we found one of the samples containing DNA of one cutaneous HPV, namely HPV2, and 29 samples contained DNA from essentially mucosal HPVs. In penile squamous cell carcinoma samples (n=592), we retrieved the DNA of HPV16 in 16 samples. Our results show first that the SPF10/DEIA is very sensitive, as we recovered only 2.1% (55/2635) false negative results; second, that although the DNA of cutaneous HPVs can be detected in cancer samples, their relative contribution remains anyway minor (0.23%; 6/2635) and may be neglected for screening and vaccination purposes; and third, their contribution to malignancy is not necessarily warranted and need to be elucidated.

INTRODUCTION

Human Papillomaviruses (HPVs) are involved in the etiology of anogenital and oropharyngeal cancers [START_REF] Forman | Global burden of human papillomavirus and related diseases[END_REF]. Within Papillomaviridae, HPVs belong into five different genera, namely Alpha-, Beta-, Gamma-, Mu-and NuPVs (Bernard et al., 2010). The large majority of HPVs, essentially Beta-and GammaPVs, cause asymptomatic infections and can be detected in healthy skin swabs and for some GammaPVs, also in mucosal rinses (Bottalico et al., 2011;[START_REF] Gottschling | Cutaneotropic human beta-/gamma-papillomaviruses are rarely shared between family members[END_REF].

AlphaPVs is a very heterogeneous clade regarding tropism and clinical manifestation of the disease. Although most infections by human AlphaPVs are clinically asymptomatic some of them cause productive cutaneous warts; other cause productive mucocutaneous warts; finally a number of human AlphaPVs with mucosal tropism can induce malignant transformation after decades of persistent infection and are identified as carcinogenic or possibly/probably carcinogenic for humans [START_REF] Doorbar | The biology and life-cycle of human papillomaviruses[END_REF]IARC, 2007).

Careful retrospective investigations have shown that infections by human AlphaPVs are the most likely etiologic cancer agent, accounting for nearly 100% of cervical cancer cases [START_REF] De Sanjose | Human papillomavirus genotype attribution in invasive cervical cancer: a retrospective crosssectional worldwide study[END_REF], 88% of anal cancer cases in both males and females (Alemany et al., 2015) and for 74% of cancers of the vagina (Alemany et al., 2014). These high rates of viral DNA prevalence contrast with the lower fraction of cancer cases attributable to HPVs in other anogenital sites, chiefly the vulva and the penis. In vulvar cancers, infections by HPVs have been associated with less than 30% of the cancer cases [START_REF] De Sanjose | Worldwide human papillomavirus genotype attribution in over 2000 cases of intraepithelial and invasive lesions of the vulva[END_REF] while HPV DNA is found in around 30% of penile cancer [START_REF] Castellsague | HPV Involvement in Head and Neck Cancers: Comprehensive Assessment of Biomarkers in 3680 Patients[END_REF]. Finally, in head and neck (HN) cancers, the most consistent findings relate to oropharyngeal cancers, where HPV DNA has been detected in 25% of cancer cases in contrast with the rest of the oral cavity, where HPV DNA is found in less than 10% of the cases [START_REF] Castellsague | HPV Involvement in Head and Neck Cancers: Comprehensive Assessment of Biomarkers in 3680 Patients[END_REF][START_REF] Souza | Case-control study of human papillomavirus and oropharyngeal cancer[END_REF].

The development of PCR methods using general primers for amplification of a broadrange of HPVs had a major impact on the molecular epidemiology of viral-related infections. Many different primer sets targeting the L1 gene have been designed and used for the detection of a broad-range of HPVs, as this gene is the most conserved one at the nucleotide level [START_REF] Mengual-Chulia | Assessing parallel gene histories in viral genomes[END_REF]. Given their overwhelming contribution to cancer, most of these consensus primers were designed to target oncogenic AlphaPVs. Among these are the single pair of consensus primers GP5/6 (Snijders et al., 1990) and its extended version GP5+/6+ (de Roda [START_REF] De Roda Husman | The use of general primers GP5 and GP6 elongated at their 3' ends with adjacent highly conserved sequences improves human papillomavirus detection by PCR[END_REF]; and the MY09/11 [START_REF] Manos | The use of polymerase chain reaction amplification for the detection of genital human papillomaviruses[END_REF] and its extended version PGMY09/11 pair of degenerate primers [START_REF] Gravitt | Improved amplification of genital human papillomaviruses[END_REF]. PCR methods using PGMY09/11 primers have been extensively used in epidemiologic studies of HPVs [START_REF] Giuliano | Human papillomavirus infection at the United States-Mexico border: implications for cervical cancer prevention and control[END_REF][START_REF] Richardson | Modifiable risk factors associated with clearance of type-specific cervical human papillomavirus infections in a cohort of university students[END_REF][START_REF] Richardson | The natural history of typespecific human papillomavirus infections in female university students[END_REF]Schiffman et al., 2005;Tabrizi et al., 2005). The MY-based method generates an amplicon of 450bp and targets a wide spectrum of HPVs, including all known possibly/probably/oncogenic AlphaPVs.

The GP5+/6+ primer set has also been extensively used in many epidemiologic HPVs studies, either directly [START_REF] Frisch | Sexually transmitted infection as a cause of anal cancer[END_REF][START_REF] Hampl | Effect of human papillomavirus vaccines on vulvar, vaginal, and anal intraepithelial lesions and vulvar cancer[END_REF][START_REF] Madsen | Risk factors for invasive squamous cell carcinoma of the vulva and vagina--population-based case-control study in Denmark[END_REF]Skapa et al., 2007) or nested, after the MY primer amplification [START_REF] Fox | The value of anal cytology and human papillomavirus typing in the detection of anal intraepithelial neoplasia: a review of cases from an anoscopy clinic[END_REF][START_REF] Hampl | Comprehensive analysis of 130 multicentric intraepithelial female lower genital tract lesions by HPV typing and p16 expression profile[END_REF][START_REF] Piketty | High prevalence of anal human papillomavirus infection and anal cancer precursors among HIV-infected persons in the absence of anal intercourse[END_REF]. This GP-based PCR generates an amplicon of 150bp and can amplify at least 20 mucosal AlphaPVs [START_REF] De Roda Husman | The use of general primers GP5 and GP6 elongated at their 3' ends with adjacent highly conserved sequences improves human papillomavirus detection by PCR[END_REF].

The SPF10 primer set has been extensively used in epidemiological studies due to its high sensitivity and specificity. This method is able to amplify of 69 known AlphaPVs generating a small fragment (65bp) of the L1 gene [START_REF] Kleter | Novel short-fragment PCR assay for highly sensitive broad-spectrum detection of anogenital human papillomaviruses[END_REF]. Tests that rely on shorter fragments of the viral genome are considered to be more sensitive and usable for less preserved specimens. None of these widely used methods of HPVs detection are generally able to detect Beta-or GammaPVs. Another system widely used is the FAP primer set, which is very useful in identifying new PVs [START_REF] Forslund | Population-based type-specific prevalence of highrisk human papillomavirus infection in middle-aged Swedish women[END_REF][START_REF] Forslund | A broad range of human papillomavirus types detected with a general PCR method suitable for analysis of cutaneous tumours and normal skin[END_REF]. This system is able to detect a broad-spectrum of PVs from both human and animal species (Antonsson et al., 2000;[START_REF] Forslund | Population-based type-specific prevalence of highrisk human papillomavirus infection in middle-aged Swedish women[END_REF] and is usually the choice for detecting the presence of unknown, largely divergent PVs (Antonsson and McMillan, 2006;[START_REF] Bzhalava | Deep sequencing extends the diversity of human papillomaviruses in human skin[END_REF][START_REF] Garcia-Perez | Novel papillomaviruses in free-ranging Iberian bats: no virus-host co-evolution, no strict host specificity, and hints for recombination[END_REF] The aim of the present study was to reanalyze samples from squamous cell carcinomas of the HN, penis and vulva that had previously tested negative for the presence of HPVs DNA using the SPF10/DEIA procedure in order to identify the presence of other PVs not targeted by standard epidemiologic approaches, covering mucosal as well as cutaneous HPVs.

MATERIALS AND METHODS

Sample Collection

Samples were obtained from a Formalin Fixed Paraffin Embedded (FFPE) repository from a retrospective cross-sectional study coordinated by the Catalan Institute of Oncology (ICO), Barcelona, Spain, designed and constructed for the assessment of the HPV contribution to a number of anogenital and HN human tumors [START_REF] Castellsague | HPV Involvement in Head and Neck Cancers: Comprehensive Assessment of Biomarkers in 3680 Patients[END_REF]Alemany et al., 2015;Alemany et al., 2014;[START_REF] Castellsague | HPV Involvement in Head and Neck Cancers: Comprehensive Assessment of Biomarkers in 3680 Patients[END_REF][START_REF] De Sanjose | Worldwide human papillomavirus genotype attribution in over 2000 cases of intraepithelial and invasive lesions of the vulva[END_REF][START_REF] De Sanjose | Human papillomavirus genotype attribution in invasive cervical cancer: a retrospective crosssectional worldwide study[END_REF]. All specimens were tested for the presence of tumour tissue as well as for the presence of HPV DNA using a two-step SPF10/DEIA/LiPA25 protocol [START_REF] Kleter | Development and clinical evaluation of a highly sensitive PCR-reverse hybridization line probe assay for detection and identification of anogenital human papillomavirus[END_REF]. Amplification products testing positive for the presence of HPVs DNA but that resulted negative for LiPA25 genotyping were Sanger-sequenced to identify the nature of the viral DNA amplified.

The detailed protocols and results for cervical [START_REF] De Sanjose | Human papillomavirus genotype attribution in invasive cervical cancer: a retrospective crosssectional worldwide study[END_REF]), anal (Alemany et al., 2015), vaginal (Alemany et al., 2014), vulvar (de Sanjose et al., 2013), penile (Alemany et al., 2016) and HN cancers [START_REF] Castellsague | HPV Involvement in Head and Neck Cancers: Comprehensive Assessment of Biomarkers in 3680 Patients[END_REF] are described elsewhere. For the purpose of this study, only squamous cell carcinoma samples from the vulva, penis and HN cancer that had tested negative for the presence of HPV DNA using the SPF10/DEIA protocol were included in the analyses. As positive controls, for each anatomical location we included further 5-10% samples of the same study that had tested positive for the presence DNA from a single HPV. The final dataset for the present work consisted of 1141 cases randomly chosen among all HPV DNA negative squamous head-and-neck cancers (380 cases from the larynx, 380 cases from the oral cavity and 381 cases from the pharynx) and 59 controls for squamous head-and-neck cancers, 902 cases and 83 controls for squamous vulvar cancers and 592 cases and 57 controls for squamous penile cancers.

PCR and sequencing

DNA was released from FFPE material by incubation of four 5µm slices with 250 µL of Proteinase K solution (10 mg/mL proteinase K, 50 mM Tris-HCl, pH 8.0) overnight at 56ºC. Samples were subsequently incubated at 95ºC for 8 minutes to inactivate proteinase K and stored at -80ºC until use. To serve as a control for the presence of input DNA, the human tubulin gene was targeted to generate an amplicon of 65 bp, the same length as the one generated by the SPF10 primers on the HPVs genomes (Alemany et al., 2015). For vulvar and penile cancer samples, the DNA solutions obtained after proteinase K treatment had been stored for several months at -80 ºC.

For samples from these locations, to facilitate the release of DNA adsorbed to the plastic walls, tubes were heated at 60ºC during 48h prior to aliquot withdrawing for PCR.

Samples were analyzed using different sets of previously described primers, listed in Table S1, designed to detect a broad range of mucosal and cutaneous PVs: i) CPI/CPII (Tieben et al., 1993); ii) FAP6085/FAP64 (Li et al.); iii) MY9/MY11 [START_REF] Manos | The use of polymerase chain reaction amplification for the detection of genital human papillomaviruses[END_REF]; iv) SKF/SKR [START_REF] Sasagawa | Novel polymerase chain reaction method for detecting cutaneous human papillomavirus DNA[END_REF]. Additionally, we designed a new set of broad-HPV primers by using CODEHOP (Rose et al 2003), (MFI/II) specifically targeting the E1 gene of cutaneous AlphaPVs. The MFI/II primer set was designed in order to complement the HPV detection of the SK primer set, as not all cutaneous AlphaPVs can be detected by using the SK primer set.

All PCRs reaction mixtures contained: 0.05 U/µL DNA Polymerase (Biotools), 1.0 x PCR reaction buffer (10X), 1.5 mM MgCl2, 0.4 mM dNTPs (Invitrogen), 0.2 µM of each primer (Biolegio) and 100 ng of DNA. Each PCR mixture was underwent 40 amplification cycles with different annealing temperatures for each primer set: 45ºC for SKF/R; 50ºC for CPI/II, FAP6084/64, MFI/II; and 47ºC for MY09/11. Finally, PCR products from those samples with an amplicon were sequenced at the Genoscreen facilities (Lille, France) in both strands, using the same primers used for amplification.

For all samples previously classified as SPF10/DEIA-negative in which we identified by Sanger-sequencing the presence of DNA from an HPV included in the 69 AlphaPVs detected by DEIA, we additionally performed a fresh SPF10 PCR followed by the LiPA25 genotyping assay [START_REF] Kleter | Development and clinical evaluation of a highly sensitive PCR-reverse hybridization line probe assay for detection and identification of anogenital human papillomavirus[END_REF].

RESULTS

We have tested a total of 2,635 FFPE surgical samples from squamous carcinomas of the HN, penis and vulva that had previously tested negative for the presence of HPV DNA using the SPF10/DEIA procedure.

For squamous cancers of the HN, we were able to properly identify and genotype the HPV-DNA present in 31 out of 59 controls (53%) (Table 1). In all cases, the HPV hereby identified matched the one previously genotyped by LiPA25. We tested 1141 SPF10/DEIA-negative HN cancer samples, and we retrieved sequences specific for a one particular HPV in 15 out of these 1141 (1.3%) samples (Table 1, Table S2). In ten out of these 15 samples (66.7%), we detected DNA from mucosal HPVs, namely HPV16 (n=8), HPV51 (n=1) and HPV74 (n=1). Finally, we recovered DNA from two BetaHPVs, namely HPV20 and HPV21, and from three cutaneous AlphaPVs, namely HPV2, HPV57 and HPV61. Although ten from these 15 samples were expected to have tested positive for the initial SPF10/DEIA screening (i.e. those containing either HPV16, 51 or 74, targeted by the SPF10/DEIA) they resulted negative. When we performed a new SPF10/LiPA25 test, we recovered five of them (50%) as positive for HPV-DNA, matching in all cases the HPV genotype identified with the broad-spectrum primers, including HPV16 (n=3), HPV51 and HPV74.

For vulvar cancer samples, we were able to identify and genotype 62 out of 83 (75%) SPF10/DEIA-positive control samples. We tested further 902 SPF10/DEIA-negative samples and found HPV-DNA in 30 of them (3.3%) (Table 1, Table S3). One of the samples contained DNA of one cutaneous HPV, namely HPV2, while the remaining 29 samples contained DNA from essentially mucosal HPVs, namely HPV16 (n=18) HPV33 (n=1), HPV45 (n=2), HPV52 (n=1), HPV53 (n=1), HPV56 (n=1), HPV66 (n=1), HPV70 (n=1) and HPV74 (n=3). All these 29 samples should have tested positive for the initial SPF10/DEIA screening, and indeed 16 of them (55%) resulted positive when we performed a new SPF10/LiPA25 on them, the results matching those obtained with the broad primer sets. Specifically, we detected HPV16 (n=9), HPV33 (n=1), HPV45 (n=2), HPV52 (n=1), HPV70 (n=1) and HPV74 (n=2).

Finally, for penile cancer control samples, we successfully identified the presence of HPVs DNA in 37 out of 57 (65%). Among the 592 SPF10/DEIA-negative samples, we identified the presence of HPV DNA in 16 of them (2.7%), and in all cases the retrieved sequences corresponded to HPV16 (Table 1, Table S5). When we performed a new SPF10/LiPA25 genotyping on these 16 samples, four of them (25%) tested indeed positive and revealed the presence of HPV16 DNA.

DISCUSSION

We present here the largest study assessing the presence of DNA from cutaneous and mucosal HPVs in squamous cell carcinomas of the vulva, penis and HN, aiming at HPVs beyond those already identified as (probable/possible) oncogenic factors for these sites. We confirmed by multiple PCR tests the presence of DNA from a number of cutaneous HPVs in a very small number (6/2635) of cancer cases that seem to be truly negative for oncogenic HPVs. Nevertheless, it is important to keep in mind that the presence of viral DNA alone does not necessarily imply causation or relation to malignancy.

In the present study we have analyzed HPV-negative cancer cases of the HN, vulva and penis, previously tested by SPF10/DEIA/LiPA25 protocol. In HN samples, we detected HPV DNA in 15 out of 1141 (1.3%) samples previously diagnosed as HPV negative by SPF10/DEIA technology. Among them, five types corresponded to cutaneous HPVs: two belonging to BetaPVs (HPV20 and HPV21) and three belonging to AlphaPVs (HPV2, HPV57 and HPV61). All these samples came from the oral cavity except the HPV20, which was retrieved from a laryngeal cancer sample. In the same repository, we already confirmed the presence of two single infections by cutaneous HPVs (Table 3) [START_REF] Castellsague | HPV Involvement in Head and Neck Cancers: Comprehensive Assessment of Biomarkers in 3680 Patients[END_REF]. Studies on HPV prevalence demonstrated a high prevalence (more than 60%) of cutaneous HPVs in the oral cavity of healthy individuals (Bottalico et al., 2011;[START_REF] Kuhs | Prevalence of and risk factors for oral human papillomavirus among young women in Costa Rica[END_REF]. Our results suggest that the contribution of these cutaneous types to cancer remains minor and may be neglected for screening and vaccination purposes. A prospective investigation (Agalliu et al., 2016) reported a positive association between infections with Beta and/or GammaPVs and increased head-and-neck cancer risk. Indeed, the authors reported that Beta1, Gamma11 and Gamma12 species were associated with 3.3 to 5.5-fold higher risk of HN carcinomas after adjusting for smoking, alcohol consumption and HPV16 detection.

However, residual confounding cannot be ruled out as an explanation of these findings [START_REF] Rollison | The Alpha, Beta, Gammas of Oral Human Papillomavirus Infection and Head and Neck Cancer Risk[END_REF].

Other studies have also analyzed the presence of cutaneous HPVs in malignant headand-neck tumours (Agalliu et al., 2016;[START_REF] Koskinen | Prevalence and physical status of human papillomavirus in squamous cell carcinomas of the head and neck[END_REF][START_REF] Lindel | Cutaneous human papillomavirus in head and neck squamous cell carcinomas[END_REF][START_REF] Paolini | Both mucosal and cutaneous papillomaviruses are in the oral cavity but only alpha genus seems to be associated with cancer[END_REF]. Lindel and colleagues [START_REF] Lindel | Cutaneous human papillomavirus in head and neck squamous cell carcinomas[END_REF] found a high prevalence of cutaneous HPVs in head-and-neck carcinomas samples (16/18 HPV-DNA positive tumours) by PCR amplification with multiple primers. The authors reported the presence of BetaPVs DNA as a single infection in eleven samples, and in two samples they found a multiple infection of two (or three) BetaPVs; finally, in three samples they found a multiple infection of a cutaneous BetaPV in combination with a low-risk AlphaPV. Paolini and colleagues [START_REF] Paolini | Both mucosal and cutaneous papillomaviruses are in the oral cavity but only alpha genus seems to be associated with cancer[END_REF]) also demonstrated the presence of cutaneous BetaHPVs (HPV5,14,20,21,25,36,47,100,105 and 111) in HN squamous carcinomas samples (16/78 samples). However, they could not find cutaneous viral transcripts in any of these cancer samples.

We also analyzed penile SPF10/DEIA-negative cancer samples. Although in the analyzed samples, we did not find any cutaneous HPV type, the original description of the dataset already included the presence of cutaneous HPVs in two penile squamous carcinoma samples, namely HPV27 and HPV76 (Table3) [START_REF] Castellsague | HPV Involvement in Head and Neck Cancers: Comprehensive Assessment of Biomarkers in 3680 Patients[END_REF]. Few published studies have examined the presence of cutaneous HPVs in penile carcinomas. Moreover, all have used varying methods and have focused on a single lesion type, making comparisons across studies difficult. By using PCR amplification with multiple primers, Wieland and colleagues (Wieland et al., 2000) described the presence of HPV8 (as single infection and as co-infection with a mucosal oncogenic type) in in situ squamous cell carcinomas of the penis (12/12 samples). In another study, the presence of HPV8 was found in penile squamous carcinoma samples, being that type the second most prevalent type (10/46 samples) as a single infection (6/10 samples) or as co-infection with a mucosal oncogenic type (4/10 samples) [START_REF] Humbey | Detection of the human papillomavirus and analysis of the TP53 polymorphism of exon 4 at codon 72 in penile squamous cell carcinomas[END_REF]. These authors also found other cutaneous BetaHPVs (HPV12, HPV17, HPV20 and HPV23) [START_REF] Humbey | Detection of the human papillomavirus and analysis of the TP53 polymorphism of exon 4 at codon 72 in penile squamous cell carcinomas[END_REF].

Regarding vulvar squamous carcinomas, we detected the DNA of one cutaneous virus (HPV2) in one sample. De Koning and colleagues, by using PM-PCR reverse hybridization assay did not find any cutaneous HPV in a total of 39 vulvar cancer cases (de [START_REF] De Koning | Prevalence of mucosal and cutaneous human papillomaviruses in different histologic subtypes of vulvar carcinoma[END_REF]. However, their study did not include squamous carcinoma samples in their set, making difficult the comparison of the results across the two studies.

Epidemiologic studies using standard methods of detection have demonstrated that other HPVs beyond high-risk HPVs can be involved in the malignization process [START_REF] Guimera | The occasional role of low-risk human papillomaviruses 6, 11, 42, 44, and 70 in anogenital carcinoma defined by laser capture microdissection/PCR methodology: results from a global study[END_REF], although their prevalence is very low (Table 2). In the present study we describe the presence of HPV-DNA of cutaneous types in cancer samples. However, the mere presence of HPV-DNA in cancer samples is not sufficient to prove viral causation as it might simply reflect an ongoing viral infection unrelated to the carcinogenic process [START_REF] Sarid | Viruses and human cancer: from detection to causality[END_REF]. Thus, it is important to explore the expression patterns of other markers associated with HPV-induced carcinogenesis to assess the biological and oncogenic activities of HPVs identified in these cancers.

Although the pathogenic pathway for malignant transformation in oncogenic AlphaPVs has been extensively studied (Bello et al., 2015;[START_REF] Duensing | Mechanisms of genomic instability in human cancer: insights from studies with human papillomavirus oncoproteins[END_REF][START_REF] Jones | Analysis of the p53-mediated G1 growth arrest pathway in cells expressing the human papillomavirus type 16 E7 oncoprotein[END_REF][START_REF] Moody | Human papillomavirus oncoproteins: pathways to transformation[END_REF][START_REF] Munger | The E6 and E7 genes of the human papillomavirus type 16 together are necessary and sufficient for transformation of primary human keratinocytes[END_REF], the putative oncogenic mechanism of cutaneous HPVs remains unknown and may probably involves different molecular pathways than those well described for HPV16 and other oncogenic HPVs [START_REF] Groves | Pathogenesis of human papillomavirusassociated mucosal disease[END_REF][START_REF] Rusan | Genomic landscape of human papillomavirus-associated cancers[END_REF].

In SPF10/DEIA-negative samples, we detected the DNA of one of the 69 types detected by the SPF10/DEIA technology [START_REF] Kleter | Development and clinical evaluation of a highly sensitive PCR-reverse hybridization line probe assay for detection and identification of anogenital human papillomavirus[END_REF]. Among the 1,141 HN SPF10/DEIA-negative samples, ten samples contained an HPV type detected by DEIA.

In five out of these ten samples, the type was confirmed by performing a LiPA25 analysis. In vulvar cancer samples 29/902 samples resulted positive for types detected by DEIA, and the LiPA25 confirmed the HPV type detected by PCRs methods in 16 of them. Finally, for penile samples the LiPA25 detected the HPV type reported by PCR in four out of 16/592 samples. Our results suggest that the SPF10/DEIA/LiPA25 methodology present very small rates of false-negative cases (ranging between .0.9-3.5%), which confirm its high sensitivity, especially for FFPE samples [START_REF] Geraets | The original SPF10 LiPA25 algorithm is more sensitive and suitable for epidemiologic HPV research than the SPF10 INNO-LiPA Extra[END_REF].

The fraction of SPF10/DEIA-positive samples detected by the PCR methods used in this study ranged from 53% in HN to 65-75% in penile and vulvar cancer samples, respectively, demonstrating that our results might be underestimating the presence of cutaneous HPVs, as well the number of SPF10/DEIA false negative samples. Globally, the broad-spectrum primers sets used in this study are not optimized for retrieving small amplicons. Primer selection has been done taking into account the spectrum of the HPV types detected, in order to cover both mucosal and cutaneous HPVs; and their sensitivity in a single round assay. Using this primer selection, we aimed to covering both mucosal and cutaneous HPVs, detecting both E1 and L1 genes, with an amplicon range from 150bp to 450bp. Nevertheless, the amplicon length was larger than the 65bp targeted by the SPF10 primers [START_REF] Kleter | Novel short-fragment PCR assay for highly sensitive broad-spectrum detection of anogenital human papillomaviruses[END_REF]. This difference in amplicon size can easily explain the incompletely recovery of positive SPF10/DEIA samples.

Another technical factor that might also contribute to a hypothetical underestimation of the presence of cutaneous HPVs is the storage of the samples at -80ºC, which might compromise the DNA quality of the samples (Lee et al 2010). In order to minimize this effect we heated all the stored samples (including samples from the vulva and penis), during 48h at 60ºC. We found that this pretreatment may help recover DNA possibly adsorbed onto the plastic tube walls, as the positivity of control samples were higher in the localizations were the pretreatment were performed. However, this recovery remained incomplete and still, samples with low DNA concentration may result in low DNA detection rates.

CONCLUSIONS

Our results show that previous estimates of HPVs involvement in vulvar, penile and HN cancers, based on SPF10/DEIA procedure do not suffer from significant underestimation biases. We show further that other HPVs beyond mucosal HPVs, typically detected by standard methods of detection may be present in carcinomas of the penis, vulva and HN, albeit their relative contribution remains minor and may have no public health impact whatsoever, and may be neglected for vaccination and cancer screening purposes. Nevertheless, our results brace previous reports with lower sample size, and mounting evidence suggests that certain cutaneous HPVs may be linked to a small number of cancer cases. Our results call for further studies to elucidate the pathogenic role of these "non-oncogenic" HPVs, the possible malignisation routes and mechanisms and the interplay between viral infection, host genetics and environment. a HPVs detected: HPV20 (n=1, BetaPV), HPV21 (n=1, BetaPV), HPV2 (n=1, AlphaPV), HPV57 (n=1, AlphaPV), HPV61 (n=1, AlphaPV), HPV16 (n=8, AlphaPV), HPV51 (n=1, AlphaPVs), HPV74 (n=1, AlphaPVs). b HPVs detected: HPV2 (n=1, AlphaPVs), HPV16 (n=18, AlphaPVs) HPV33 (n=1, AlphaPVs), HPV45 (n=2, AlphaPVs), HPV52 (n=1, , AlphaPV), HPV53 (n=1, AlphaPV), HPV56 (n=1, AlphaPV), HPV66 (n=1, AlphaPV), HPV70 (n=1, AlphaPVs) and HPV74 (n=3, , AlphaPVs). c HPVs detected: HPV16 (n=16, AlphaPV)

Table 3: Number of single HPV infections found in head and neck, penile and vulvar carcinomas. For each anatomical location, the first column corresponds to the number of single HPV infections found by SPF10-DEIA-LIPA25 methodology [12][13][14]. The second column corresonds to the number of single HPV infections found in the negative SPF10/DEIA/LIPA25 samples from the corresponding repository in the same anatomical location.

Squamous carcinoma Head and

FUNDING

  MFS is the recipient of an IDIBELL PhD scholarship. Partial support for this work was obtained from grants from the Instituto de Salud Carlos III (grants FIS PI081535, FIS PI1102096, FIS PI1102104, RCESP C03/09, RTICESP C03/10, RTIC RD06/0020/0095, RD12/0036/0056,), from the Agència de Gestió d'Ajuts Universitaris i de Recerca (2014SGR2016), from the Stichting Pathologie Ontwikkeling en Onderzoek (SPOO) foundation (the Netherlands), and from Sanofi Pasteur MSD and Merck & Co, Inc. None of the founders had any role in data analysis, interpretation, article writing or publishing. Aknowledgements We are grateful for the work of all the Institut Català d'Oncologia (ICO) team and the ICO International HPV in HN Cancer Study Group. The study is also part of the Human Papillomavirus Vulva, Vagina, Anus and Penis (HPV VVAP) international study coordinated at ICO, Barcelona, Spain. ., Saunier, M., Alvarado-Cabrero, I., Quiros, B., Salmeron, J., Shin, H.R., Pirog, E.C., Guimera, N., Hernandez-Suarez, G., Felix, A., Clavero, O., Lloveras, B., Kasamatsu, E., Goodman, M.T., Hernandez, B.Y., Laco, J., Tinoco, L., Geraets, D.T., Lynch, C.F., Mandys, V., Poljak, M., Jach, R., Verge, J., Clavel, C., Ndiaye, C., Klaustermeier, J., Cubilla, of papillomaviruses (PVs) based on 189 PV types and proposal of taxonomic amendments. Virology 401, 70-79. Bottalico, D., Chen, Z., Dunne, A., Ostoloza, J., McKinney, S., Sun, C., Schlecht, N.F., Fatahzadeh, M., Herrero, R., Schiffman, M., Burk, R.D., 2011. The oral cavity contains abundant known and novel human Schiffman, M., Wheeler, C.M., Dasgupta, A., Solomon, D., Castle, P.E., 2005. A comparison of a prototype PCR assay and hybrid capture 2 for detection of carcinogenic human papillomavirus DNA in women with equivocal or mildly abnormal papanicolaou smears. Am J Clin Pathol 124use of general primers in the polymerase chain reaction permits the detection of a broad spectrum of human papillomavirus genotypes. J Gen Virol 71 ( Pt 1), 173-181. Tabrizi, S.N., Stevens, M., Chen, S., Rudland, E., Kornegay, J.R., Garland, S.M., 2005. Evaluation of a modified reverse line blot assay for detection and typing of human papillomavirus. Am J Clin Pathol 123, 896-899. Tieben, L.M., ter Schegget, J., Minnaar, R.P., Bouwes Bavinck, J.N., Berkhout, R.J., Vermeer, B.J., Jebbink, M.F., Smits, H.L., 1993. Detection of cutaneous and genital HPV types in clinical samples by PCR using consensus primers. J Virol Methods 42

Table 1 :

 1 Concordance between SPF10-DEIA and HPV broad-spectrum PCR (CPI/II, SKF/R, FAP6064/64, MY09/11 and MFI/II) in Head-and-neck (N=1200), Penile (N=649) and Vulvar (N=985) squamous cell carcinoma samples.

				SPF10-DEIA
		Broad-HPV PCR							Total
	Head and Neck			+			-
	Squamous cell		N		%	N		%
	carcinoma	+	31	50.8 15 a 1.3	46
		-	30	49.2 1126 98.7 1156
		Total	61	100 1141 100 1202
				SPF10-DEIA
	Vulvar Squamous cell	Broad-HPV PCR	N	+	%	N	-	%	Total
	carcinoma	+	62	74.7 30 b 3.3	92
		-	21	25.3 872 96.7 893
		Total	83	100 902 100 985
				SPF10-DEIA
	Penile Squamous	Broad-HPV PCR	N	+	%	N	-	%	Total
	cell carcinoma	+	37	64.9 16 c 2.7	53
		-	20	35.1 576 97.3 596
		Total	57	100 592 100 649

TABLES

20

Table 2: HPV prevalence distribution found in anogenital and head and neck cancers. Information was obtained from the larger cross-sectional study on HPV prevalence distribution coordinated by the Catalan Institute of Oncology [9][10][11][12][13][14]. HPVs were classified according their phylogeny and clinical presentation: Mucosal oncogenic AlphaPVs, Mucocutaneous AlphaPVs causing genital warts, AlphaPVs causing cutaneous warts, Asymptomatic cutaneous BetaPVs and Asymptomatic GammaPVs.

Genus


F Aït-Salaht
email: farah.ait-salaht@inria.fr

F Desprez

A Lebre

C Prud'homme

M Abderrahim

Service Placement in Fog Computing Using Constraint Programming

Keywords: Fog Computing, Edge Computing, Services Placement, Constraint Programming, Choco Solver

This paper investigates whether the use of Constraint Programming (CP) could enable the development of a generic and easy-to-upgrade placement service for Fog Computing. Our contribution is a new formulation of the placement problem, an implementation of this model leveraging Chocosolver and an evaluation of its scalability in comparison to recent placement algorithms. To the best of our knowledge, our study is the first one to evaluate the relevance of CP approaches in comparison to heuristic ones in this context. CP interleaves inference and systematic exploration to search for solutions, letting users on what matters: the problem description. Thus, our service placement model not only can be easily enhanced (deployment constraints/objectives) but also shows a competitive tradeoff between resolution times and solutions quality.

I. INTRODUCTION

Cloud platforms are part of the distributed computing landscape. However, given the massive arrival of IoT devices, together with an exponential number of related applications (smart-metering, smart-transportation, augmented reality, wearable computing, etc.), the deployment of more decentralized infrastructures such as the Fog ones [START_REF] Bonomi | Fog Computing and Its Role in the Internet of Things[END_REF] is now crucial. Distributing the infrastructure itself and installing processing resource in different locations, closer to users, is the only way to cope with the requirements in terms of throughput and latency of the aforementioned applications. Processing a data stream as close as possible to where it has been generated, mitigates, for instance, network congestion [START_REF] Zhang | The Cloud is Not Enough: Saving IoT from the Cloud[END_REF]. Figure 1 gives an overview of a Fog Computing infrastructure: a large number of heterogeneous interconnected devices between clouds and IoT sensors.

While Fog Computing infrastructures will soon allow the deployment of processing/storage resources closer to the edge of the network, there are still open questions related to the resource management aspects. Among them, the service placement problem (i.e. "how to assign IoT applications to computing nodes which are distributed in a Fog environment?") has generated lots of interests in the scientific community [START_REF] Yousefpour | All One Needs to Know about Fog Computing and Related Edge (a) For G 2 (with 120 nodes)[END_REF][START_REF] Nath | A Survey of Fog Computing and Communication: Current Researches and Future Directions[END_REF]. However, all placement service proposals have been designed to solve one particular use case, which strongly limits their adoption into a general resource management system for Fog infrastructures. Although our community has been Fig. 1: A Fog Computing architecture as presented in [START_REF] Wen | Fog Orchestration for Internet of Things Services[END_REF]. investigating this challenge for a couple of years [START_REF] Yousefpour | QoSaware Dynamic Fog Service Provisioning[END_REF][START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF][START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF][START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF][START_REF] Naas | iFogStor: An IoT Data Placement Strategy for Fog Infrastructure[END_REF][START_REF] Donassolo | Fog Based Framework for IoT Service Provisioning[END_REF], we claim that proposed approaches are not generic enough to deal with all applications' specifics that Fog infrastructures would have to host. Current algorithms rely mainly or Integer Linear Programming (ILP) or heuristic approaches that are not easily expandable (i.e. cannot easily evolve to integrate new application or infrastructure characteristics, and allow new placement constraints to be easily developed and integrated), or upgradeable in the sense of exploiting any resolution approach that is implied by the user, allowing independent sub-problems to be solved in parallel. In this paper, we investigate whether a model built on the Constraint Programming (CP) [START_REF]Handbook of Constraint Programming[END_REF] can be envisioned to develop a generic and easy-to-upgrade placement service for Fog infrastructures. Besides being faster and more robust than the known ILP approach, the CP code is significantly smaller, which implies it would be easier to implement and maintain. Plus, many open-source yet efficient CP solvers are distributed whereas the ILP uses an external (potentially expensive) commercial ILP solver. In view of that, we propose in this work a new formulation and relatively simple model for the placement problem considering a general definition of service and infrastructure network through graphs using constraint programming. We underline that the contribution of this study is not only related to the model provided but also to its validation in terms of extensibility and scalability. Although the use of CP approaches have been proven efficient in several problem solvers, in particular in Cloud Computing placement problems (i.e. Entropy VEEE, BTRPlace) [START_REF] Hermenier | Entropy: A Consolidation Manager for Clusters[END_REF], CPsolvers are still facing negative preconceived ideas regarding their capacity to deal with large problems. Here, we propose to extend those models to take into account Edge specifics, and show through our evaluation results that the implementation of our model in Choco-solver [START_REF] Prud'homme | Choco Documentation[END_REF] is competitive w.r.t the most recent solutions of the literature.

The remaining of the paper is organized as follow. Section II presents the related work to placement challenges in Fog Computing platforms and motivates the need for a holistic placement service. Section III describes our model and the way we solve the placement problem using Choco-solver. Section IV discusses experiments we performed to evaluate the efficiency of our placement service. Finally, Section V concludes this paper and gives some perspectives.

II. RELATED WORK AND MOTIVATION

The service placement problem in Fog infrastructures has been highly discussed with several solutions based on different application scenarios, network assumptions, and objective functions. Based on our analysis of the state-of-the-art, most of the scenarios undertaken so far can be categorized as follows:

• Scenario 1: deploy a set of services each abstracted as a single component. This scenario considers monolithic applications (e.g. data) [START_REF] Yousefpour | QoSaware Dynamic Fog Service Provisioning[END_REF][START_REF] Naas | iFogStor: An IoT Data Placement Strategy for Fog Infrastructure[END_REF]. In [START_REF] Naas | iFogStor: An IoT Data Placement Strategy for Fog Infrastructure[END_REF], the authors investigate the problem of IoT data placement in a Fog infrastructure. They propose to formulate the problem as a generalized assignment problem by considering the resource capabilities constraints and minimize the overall latency while storing and retrieving the data set. In order to accelerate the solving time, the authors provide a heuristic based on geographical zoning to reduce search space and find out a placement in a reasonable time.

In [START_REF] Yousefpour | QoSaware Dynamic Fog Service Provisioning[END_REF], Yousefpour et al. study the dynamic Fog service provisioning problem. The study aims to dynamically provisioning IoT applications on the fog nodes, to comply with the QoS terms (delay threshold, penalties, etc.) with minimal resource cost. The problem is formulated as an integer non linear programming task, and two heuristics are proposed to solve it efficiently. • Scenario 2: deploy a set of services each abstracted as a set of interdependent components. This scenario assumes that each service is pre-partitioned into a set of components (resp. modules), where only components requirements are taken into account. As an example, we cite the work of Skarlat et al. in [START_REF] Skarlat | Optimized IoT Service Placement in the Fog[END_REF], that propose to study the placement of IoT services on virtualized Fog resources. This work present a placement strategy that maximize the number of service placements to fog resources, while satisfying the QoS constraints. Only resource application components and application execution deadline are specified. The service placement problem is formulated as an ILP and solved by CPLEX. A genetic algorithm in a centralized manner is proposed to reduce and accelerate the execution time of ILP.

• Scenario 3: deploy a set of services each abstracted as a Directed Acyclic Graph (DAG). The service in this scenario is assumed to be pre-partitioned into interconnected components (resources and networking requirements are considered) having a DAG topology [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF][START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF][START_REF] Donassolo | Fog Based Framework for IoT Service Provisioning[END_REF]. The DAG graph models a wide range of realistic IoT applications like healthcare, latency-critical gaming that involve a hierarchical set of processes (or virtual machines), including streaming, multicasting, and data aggregation applications. Among the works considering this scenario, we cite the work of Brogi et al. [START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF] that propose a model to support the QoS-aware deployment of multicomponent IoT applications in Fog infrastructures. The proposed model provides eligible deployments (if any) of an application by performing pre-processing plus backtracking approaches. As we can remark here and in many other works that try to address the placement problem in Fog environments [START_REF] Yousefpour | All One Needs to Know about Fog Computing and Related Edge (a) For G 2 (with 120 nodes)[END_REF][START_REF] Nath | A Survey of Fog Computing and Communication: Current Researches and Future Directions[END_REF], each solution targets a specific sets of applications topology, network assumptions, and objectives. If targeting a specific use case enables our community to move forward, a more general framework should be designed in order to handle requirements/constraints of the different applications. Our work targets this objective and handle all the aforementioned scenarios. Indeed, we provide in this paper a new formulation of the placement problem considering a general definition of service and infrastructure network through graphs using constraint programming as discussed in the following section.

III. SERVICE DEPLOYMENT PROBLEM: SYSTEM MODEL AND PROBLEM FORMULATION

In this section, we propose to describe the accurate and the comprehensive framework provided to address the Service Placement Problem (SPP). The framework includes a system model and a constraint satisfaction model, to represent the problem using attributes that are critical for SPP in Fog environments. Before describing the constraints and the optimization problem, we propose to model the infrastructure network, and the Fog applications first.

A. System model a) Infrastructure model: Definition 1. The Fog Computing infrastructure is defined as a directed graph G I =< H, E >, where H is the set of host nodes (Cloud, Fog, and Things nodes) and E the network connections between the nodes.

The infrastructure nodes may represent Cloud nodes (data centers), Fog nodes (resources which provide computational power and/or storage. e.g., routers, switches, PCs, etc.), or IoT devices (sensors and actuators), at possibly different hierarchical layers. Each infrastructure node f is characterized by its capacities U (f ) such that U =(CPU, RAM, . . . ). Metrics like: storage, network, energy resources, etc, can also be specified.

Nodes are interconnected via a set of links E, E = H × H. Each link e i,j ∈ E, is characterized by the latency LAT (e i,j ) between source node i and sink node j, where LAT (e i,i ) = 0, and the bandwidth of the link as BW (e i,j ), where BW (e i,i ) = ∞.

b) Service model: The service model considered here encompasses the different scenarios depicted in Section II. Unlike the works found in the literature, which fits only in one of the scenarios mentioned, our work is distinguished by the genericity of the proposed model. Indeed, we consider any type of services topology, as long as it can be represented as a graph. So, let A be the set of services to be deployed in physical network, the services can be abstracted to application graphs. An application is denoted as a connected graph G a =< C a , L a >, where C a defines the set of all components of application a, and edges L a ⊆ C a × C a defines the inter-dependencies and communication demands between components. Components and links are respectively defined as in Definition 2, and Definition 3.

Definition 2. A component c ∈ C a is
defined by a set of resource types denoted u(c), such as u = (Reqcpu, Reqram, . . . ), where Reqcpu (resp. Reqram) is the number of cores (resp. the amount of memory) required by the component. Other requirements can be specified. An application component can be a fixed component, i.e., has a specific infrastructure node where it must be deployed. We denote by Φ a ⊆ C a the set of fixed components and by φ a (c) the physical node where the component must be deployed.

Definition 3. A link (or pair) k ∈ L a is a couple k = (source, sink)
, where source, sink ∈ C a are respectively source and sink component of k. For each k, we define Reqlat(k) as the maximum acceptable latency between components, and Reqbw(k) as the bandwidth requirements for k.

In the rest of the paper, we use interchangeably the term service and application.

c) Deployment: Deployment of a set of applications A over a Fog infrastructure G I is a mapping of all the components C such that C = a∈A C a , over the nodes in H and of all the pairs in L such that L = a∈A L a onto the physical links in E. The deployment of C on H amounts to finding the infrastructure devices that satisfy the constraints on resource capacities, i.e., ensure that the resources of all the deployed components do not exceed the resource capacities of the infrastructures nodes. The mapping of a pair k ∈ L is to find a path in the physical graph such that the networking constraints are respected i.e., satisfy the required networking resources (in term of bandwidth, latency...).

Remark 1. The mapping of a pair k ∈ L may form an Hamiltonian path.

In the next section We define the deployment of components to the infrastructure's nodes and its related constraints.

B. A constraint-based model for SPP (CP-SPP model)

In this section, we describe how to tackle service placement problem in Fog infrastructure using constraint programming approach.

Constraint programming [START_REF]Handbook of Constraint Programming[END_REF] has been widely used in a variety of domains such as production planning, scheduling, timetabling, and product configuration. The basic idea of constraint programming is that user formulates a real-world problem as a CSP (Constraint Satisfaction Problem) and then a general purpose constraint solver calculates solution for it. Formally, a CSP is defined by a triplet V, D, C , where V is the set of variables, D is the set of domains associated with the variables, and C is the set of constraints. A constraint cstr(j), associates with a sub-sequence vars(cstr(j)) ∈ V, defines the allowed combinations of values which satisfy cstr(j). A constraint is equipped with a monotonically decreasing function that removes from the domains of vars(cstr(j)) values that cannot satisfy cstr(j). Combining the definition of service placement problem and the basic idea of constraint programming, the problem of applications mapping can be modeled by CSP in the following way:

1) Set of variables and their domains: To translate the component placement problem into a constraint satisfaction problem, we introduce a set of decision variables. We propose to distinguish here the variables related to nodes and those related to arcs respectively. We note that for the needs of the modeling, we increase the G I by adding a supersink node to which all graph nodes can access (including itself). The supersink denoted by α has an unlimited resources (CPU, RAM...), and the edges that link the infrastructure node to α, and α to itself, have an infinite capacity.

a) Variables related to nodes: For each pair k ∈ L , we define the following:

• s = {s k |k ∈ [1, |L |]}.
n = {n k,j |k ∈ [1, |L |], j ∈ [1, |H|]}. n k,j
denotes the host node at position j in the path of pair k. The variables n k,j takes these values in H.

• h = {h i |i ∈ [1, |C |]}. h i denotes the node that hosts component i, ∀i ∈ C . h i takes these values in H. • p = {p k |k ∈ [1, |L |]}. Variable p k denotes the position of t k in n k (position of s k = 0). p k takes these values in {1, . . . |H|}.
Remark 2. Since the only outgoing arc of α is a loop, n always ends with at least one occurrence of α.

b) Variables related to arcs: For each pair k ∈ L , we define the following variables:

• a = {a k,j |k ∈ [1, |L |], j ∈ [1, |H|]}. a k,j denotes the arc
between n k,j and n k,j+1 in path of pair k. The variables a k,j takes these values in E.

• b = {b k,j |k ∈ [1, |L |], j ∈ [1, |H|]}. b k,j is the bandwidth on arc a k,j . • l = {l k,j |k ∈ [1, |L |], j ∈ [1, |H|]}. l k,j is the latency on arc a k,j .
Remark 3. From Remark 2, the only outgoing arc from t k is the one to α.

2) Set of constraints: Next we look at the relevant constraints of the problem. We introduce two types of constraints: constraints related to nodes, and constraints related to arcs.

a) Constraints on nodes:

• C1. BINPACKING constraints [START_REF] Shaw | A Constraint for Bin Packing[END_REF] on resource capacities of infrastructure nodes. These constraints are considered for physical network nodes and are related to computational and memory limitations respectively. In a simplified way, we can say that a binpacking constraint ensures that for all physical nodes, the sum of all mapped applications components demand not exceed their maximum available capacities, with adding transversal filtering.

BINPACKING( h, Reqcpu , CP U ), BINPACKING( h, Reqram , RAM ).

• Links between variables h k , n k,j and p k -C2. The node at position 0 in the path n k is the node that hosts the source component of pair k:

n k,0 = s k , ∀k ∈ L -C3. The item at position p k in path n k is equal to t k : t k = n k,p k , ∀k ∈ L . -C4. Position of t k if
source and sink component of a pair are the same:

s k = t k ⇐⇒ p k = 1. -C5. Avoid cycles in n k (all items of n k are differ- ent [16] except if s k = t k ):
ALLDIFFERENT(n k,j , ∀ j = {1, . . . , |H|}), ∀k ∈ L -C6. Make sure that a path n k ends with at least one occurrence of α (see Remark 2). REGULAR [START_REF] Pesant | A Regular Language Membership Constraint for Finite Sequences of Variables[END_REF] constraint ensures that values assigned to sequence of variables belong to a given regular language, here expressed by a regular expression :

REGULAR(n k , "[ˆα] + [α] + "), ∀k ∈ -C7.
Contiguous pairs: t k = s k , for all two pairs k and k sharing a same application component

• C8. Locality constraint: h i = φ a (i), ∀i ∈ Φ a , ∀a ∈ A.
Restrict the fixed component to the specified locality (i.e., to a given infrastructure node). b) Constraints on arcs:

• C9. Respect bandwidth limit of each arcs:

BINPACKING( b, Reqbw , BW )

This constraint ensures that for each physical link, the bandwidth demands of all applications must not exceed maximum available bandwidth. This constraint is encoded as a BINPACKING constraint. • C10. Satisfy latencies, per pair:

l k,j = LAT (a k,j ), ∀k ∈ C , ∀j ∈ {0, . . . , |n k |} |n k | j=0 l k,j ≤ Reqlat(k), ∀k ∈ C
This constraint ensures that the end-to-end latency along a path of pair k does not exceed the maximum acceptable latency between the component of the pair.

C. Problem Optimization

An optimal solution to the CSP problem can be defined as: given an objective function F , where the optimal solution is achieved when F is minimized (resp. maximized), corresponds to find a mapping M ∈ M, such that ∀M,

F (M ) ≤ F (M) (resp. F (M ) ≥ F (M)).
We notice that the expressive modeling power provided by CP enables the development of compact and "natural" models whereas the domain reduction by constraint propagation ensures the determination of the globally optimal solution. Additional features like the efficient determination of the multiple solutions and near best solutions makes CP an attractive optimization technique [START_REF] Kotecha | Efficient optimization strategies with constraint programming[END_REF].

D. Search strategy

A key feature of constraint programming is the ability to design specific search strategies to solve problems. In this work a very basic enumeration strategy is applied on decision variables s, t and n. The next variable to branch on is selected in a sequential way (input order) and assigns to its current lower bound.

E. Implementation of Constraint Programming-Based Service Placement Algorithm (CP-SPP)

After formulating the service placement problem as CSP, we now choose a constraint solver to solve the problem. Constraint programming is often realized in imperative programming by software library, such as CPLEX CP Optimizer [START_REF] Laborie | IBM ILOG CP Optimizer for Scheduling[END_REF], JaCoP [START_REF] Kuchcinski | JaCoP -Java Constraint Programming Solver[END_REF] and Choco [START_REF] Prud'homme | Choco Documentation[END_REF]. We choose Choco as our constraint solver (many times awarded at international solver competitions MiniZinc1 ). Choco is a free Open-Source Java library dedicated to Constraint Programming. It aims at describing real combinatorial problems in the form of constraint satisfaction problems and solving them with constraint programming techniques by alternating constraint filtering algorithms with a search mechanism. The CP-SPP algorithm takes as inputs the infrastructure network and the set of applications graphs to deploy, and output the set of all feasible mapping. We can set an optimization function and timeout for this algorithm to respectively compute an optimal solution and reduce the search time of constraint solver. In this case, constraint solver will return local or global optimal solution until timeout expired. The performance of the elaborated algorithm is described in the next section.

IV. EXPERIMENTAL EVALUATION

In this section, we evaluate the performance of the provided CP-SPP model built and solved using Choco solver [START_REF] Prud'homme | Choco Documentation[END_REF]. The experiments presented here focus essentially on the computing times of our approach (how long it takes to solve the placement algorithm) and its scalability. We first provide an overview of our experimental setup before evaluating the benefits in solving time of our framework.

A. Experimental Settings a) Experimental Setting 1: For the first experiment, the motivating example is based on the Fog infrastructure and Smart Bell application introduced in [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF] and illustrated in Figure 2. The infrastructure contains a Cloud server, three network Points of Presence (PoP) in the edge layer and a number of end devices in forty-three homes in the extreme edge layer. End devices in each home has a box and a PC / mobile. The global infrastructure is composed by 91 fog nodes and 86 sensors (camera and screen). The considered application in this example is the Smart Bell application. It notifies home inhabitants when they get a visitor. It serves three homes in a same neighborhood. The main components of the application are: i) Extractor that extracts human faces in captured images, ii) DB that stores inhabitants' and friends' information, iii) Recognizer that try to recognize visitors, iv) Decider that makes reaction decisions for each visitor, v) Executor that generate and send commands to inform inhabitants through screens, and vi) Recorder that stores strangers' information and counting how many times a stranger appears.

The considered capacities of each fog node and links as well as the requirements of each component and each application binding are similar to those given in [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF]. b) Experimental Setting 2: For the second part of our evaluations, we consider an infrastructure network selected from the Internet Topology Zoo2 as shown in Figure 3. This practical topology allow us to evaluate in an accurate manner the performance of our proposal for a realistic infrastructure. The considered topology is based on the Greek Forthnet topology composed by 60 PoPs and 59 links. Because Fog Computing is a new paradigm which has not been practically deployed in a reasonably large scale, we propose in these experiments to derive larger graph by replicating the network as follows: G k denotes the graph generated by replicating k-1 time the Forthnet topology. To ensure the connectivity of the generated graph, we randomly connect two nodes of the graph (n) and graph (n -1), ∀n = {1, . . . , k}. Here, we consider respectively the following graphs: G 2 (with 120 nodes), G 5 (300 nodes), G 10 (600 nodes) and G 20 (1200 nodes).

The processing and the memory capacities for each infrastructure node are chosen randomly from respectively 10 to 100 GHz for CPU and 20 to 200 GB for RAM. For each edge in the network, the bandwidth is chosen randomly to be between 100 and 10000 Mbps, and the latency to be between 1 and 10 ms.

We consider three types of application graphs as shown in Figure 4 to deploy on infrastructure graph. Each of the graphs feature a different number of components. For the first service, we propose to consider an application composed respectively by four components and four edges [START_REF] Donassolo | Fog Based Framework for IoT Service Provisioning[END_REF]. This application is characterized by three types of components: i) trigger service which sends tokens. These tokens transport the collected measurements related to the end devices', ii) processing service that emulates the performed application treatment, and iii) storage service that stores the received tokens in memory for further processing (if necessary).

For the second application, we consider the "Smart Bell application" [START_REF] Letondeur | A Demo of Application Lifecycle Management for IoT Collaborative Neighborhood in the Fog: Practical Experiments and Lessons Learned around Docker[END_REF] composed by six components and five edges. [START_REF] Donassolo | Fog Based Framework for IoT Service Provisioning[END_REF], (b) Smart Bell application [START_REF] Letondeur | A Demo of Application Lifecycle Management for IoT Collaborative Neighborhood in the Fog: Practical Experiments and Lessons Learned around Docker[END_REF], and (c) A face recognition application [START_REF] Perala | Fog omputing and Efficient Resource Management in the era of Internet-of-Video Things (IoVT)[END_REF].

Application is based on the following set of software entities: i) a Message Oriented Middleware (MQTT) that permits asynchronous communications and eventing among the software entities, ii) A Complex Event Processor (CEP) that operates as an IoT event hub to aggregate, filter, and trigger IoT events according to business rules, iii) A Mashup Engine called Cocktail, that permits the execution of a graph of actions on actuators and services. iv) An IoT Capillary Router called Sensonet, which enlists heterogeneous connected things and collects data, and v) a Face Recognition enabler.

The third application (face recognition application [START_REF] Perala | Fog omputing and Efficient Resource Management in the era of Internet-of-Video Things (IoVT)[END_REF]) is composed by eight components and seven edges. The face detection process starts from the Pre-Processing part that includes the necessary color conversion. Then, the Skin-tone extraction is performed in order to differentiate areas that are face candidates among other objects in the video frame.

From that stage, the potential face region is detected and the equivalent facial features are extracted. This intermediate result is fed into the database that finally replies if the face that was detected exists in the database or not.

The applications presented here and considered for our evaluations allow us to capture a variety of application scenarios where Fog Computing is relevant. Regarding the application component requirements, the CPU and RAM, as well as bandwidth and latency are chosen randomly respectively: within the range of 1 to 2 for CPU (GHz), RAM (GB) and bandwidth (Mbps), and from 100 to 1000 ms for latency.

In these experiments, we assume that applications arrive by batch according to a Poisson law, and the placement service policy is called either periodically or each time a new job should be provisioned.

B. Performance Analysis

The goal of our analysis is to investigate the resolution trends of our model based on the following three factors: number of applications, number of components per application, and infrastructure size. First, we propose to compare the performance of our model with the algorithms provided in [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF]. Next, we push the experiments further by analyzing the model and observing the solving time of CP-SPP under the second experimental setting. [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF]: This evaluation compares the CP-SPP model with (i) an Integer Linear Programming (ILP) algorithm implemented using IBM CPLEX [START_REF] Laborie | IBM ILOG CP Optimizer for Scheduling[END_REF]), (ii) First Fit heuristic (based on backtrack algorithm, that returns the first solution found (if any)), (iii) a metaheuristic Genetic Algorithm (GA) (based on refining a population (a set of placements) and continuously generates new placements and adds them into the population), and (iv) the heuristic "DAFNO-InitCO-DCO(0.3)" provided by Xia et al. [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF] that relies on a backtrack search algorithm accompanied by two heuristics: (1) naive search that order the fog nodes and applications components, and (2) search based on anchors to minimize average latency. Here, we propose (as considered in [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF]) to deploy a single Smart Bell instance on the infrastructure graph depicted in Figure 2.(a) while minimizing a weighted average latency. In Table I, we give the results (in term of quality of the solution and execution times) provided in [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF] by these four algorithms. We present also the results obtained by the elaborated CP-SPP model. The column "Quality of the solution" in Table I describes the difference of the solution found compared to the optimal ones. The solution provided by the approaches is normalized according to the optimum. The optimal solution is considered as 100%.

By integrating the objective function considered in [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF], the provided CP-SPP allows obtaining the optimal solution almost instantaneously compared to the traditional ILP approach that takes more than 5 minutes. For the first fit algorithm, we remark that the heuristic provides quite bad results whether in terms of computing time or in terms of the quality of the solution obtained. Indeed, the solution found is 87% higher than the optimal solution, this is due to the risk of doing a search based on backtracking that returns the first solution found. GA meta-heuristic provides better results than the First fit however, in terms of the quality of the solution, it remains far from optimum with difference of 43%. The heuristic proposed by Xia et al. [START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF] provides a better resolution time but with a slight deviation from the optimum solution. Given these first results, we can say that the CP-SPP model elaborated in this work provide an interesting trade-off between quality of the solution provided and the computing time which is significantly better compared to conventional approaches.

2) Execution Times vs. Number of Deployed Services and Infrastructure Size: These evaluations are based on the second experimental settings presented in Section IV-A. In most works found in the literature, to evaluate the performance of their approaches and placement strategies, authors propose to deploy only one application at each time interval on a relatively small or medium infrastructure3 , our work aims to push the evaluations further by deploying a batch of applications at once and displays the advantage of our model in the context of Fog Computing regarding the scalability issue. Hence, to show the practicality of our framework, we propose to vary the number of deployed service from 1 to 100 applications and observe respectively the building and the resolution time of our model for the first feasible solution that minimizes the number of hosts in Fog infrastructure. We emphasize that the solutions provided by the CP-SPP model present a proven upper bound for the considered minimization problem. Figures 5 depict the results of this analysis for the different network sizes.

For Figure 5, we notice that the deployment of a single service and therefore the definition of a solution that satisfies all the constraints is done almost instantaneously with a very low impact of the infrastructure size, and this for all types of considered applications, i.e, application with 1, 4, 6, or 8 components. The same trend is observed for the deployment of monolithic services. Indeed, for this type of application the size of the infrastructure has a slight influence on the search time of an admissible solution.

For an infrastructure of 120 nodes, we observe that the deployment of 100 applications with number of components less than six are almost instant, and remain low when increasing the services size (less than 1 minute for application with six and eight components). For infrastructure of size 300, we remark that the computing time remains relatively low. For larger infrastructures (e.g., for G 10 and G 20 ), we remark that our model is not intractable and it provides solutions to such a problem size, which represents a significant advantage. Regarding the execution time trend, it is straightforward to see that this time increase when increasing the number of deployed services and components. This aspect can be favored by using another search strategy than the one used in this paper (see Section III-D). This flexibility is provided by the CP modeling, because we are not dependent on how the problem is solved. So, the improvement and the modification of the model is very simplified in this case.

V. CONCLUSION

This paper presents the use of constraint programming to address in a more generic manner the service placement problem in Fog Computing infrastructures. Our model considers the applications and the Fog infrastructure following different scenarios. We provide a set of constraints that formulates the problem and solve it using Choco-solver.

The evaluations we performed show that our implementation on top of Choco-solver provides a good tradeoff between resolution times and solutions quality. We thus argue that CPbased approaches can be effectively used to address this kind of problems. The expressive and flexible modeling language CP natively comes with minimizes placement description effort and eases its enhancement. In addition, the systematic resolution algorithm is almost configuration-less and provides competitive performance.

As future works, we identify three important directions. First, we plan to extend our model to include the notion of the service sharing. Our idea is to add new rules that will enable the merge of identical software components (i.e. processing units that provide the same service) and thus reduce the processing footprint overall. The use-cases we envision are related to the (i) network function chaining and (ii) data-stream problems. In both cases similar functions (load-balancing, firewall, data-filtering, etc.) might be deployed several times across the Fog infrastructure. Second, we will investigate the relevance of our model in the context of the reconfiguration (in the current study, only the initial placement has been considered). The challenges is related to the modeling of the dynamic aspect of both IoT applications and the Fog Computing infrastructure. Finally, it would be interesting to study how our CP-based approach can be extended to answer questions such as "How many replicas of a service we should deploy to ensure a certain quality of services to all users ?"

Fig. 2 :

 2 Fig. 2: Motivating example based on the experiments depicted in [9]. (a) Fog infrastructures, and (b) Smart Bell application.

Fig. 3 :

 3 Fig. 3: Greek Forthnet topology.

Fig. 4 :

 4 Fig. 4: Considered applications. (a) Storage Application[START_REF] Donassolo | Fog Based Framework for IoT Service Provisioning[END_REF], (b) Smart Bell application[START_REF] Letondeur | A Demo of Application Lifecycle Management for IoT Collaborative Neighborhood in the Fog: Practical Experiments and Lessons Learned around Docker[END_REF], and (c) A face recognition application[START_REF] Perala | Fog omputing and Efficient Resource Management in the era of Internet-of-Video Things (IoVT)[END_REF].

TABLE I :

 I Evaluation Results of Different Placement Algorithms for the Smart Bell application[START_REF] Xia | Combining Hardware Nodes and Software Components Ordering-based Heuristics for Optimizing the Placement of Distributed IoT Applications in the Fog[END_REF].

	1) Comparison of the CP-SPP Model with Algorithms pro-
	vided in

https://www.minizinc.org/challenge.html

http://www.topology-zoo.org/

e.g., in[START_REF] Brogi | QoS-Aware Deployment of IoT Applications Through the Fog[END_REF], the authors considers an application of three components and proposes to deploy it on infrastructure of size 9. In[START_REF] Donassolo | Fog Based Framework for IoT Service Provisioning[END_REF], one application is deployed composed by four components every 2 minutes on infrastructure with 70 nodes. Ditto in many other papers.

ACKNOWLEDGMENTS

This work was performed and funded by the Inria Project Lab Discovery. This is Open-Science Initiative aiming at implementing a fully decentralized IaaS manager. See http://beyondtheclouds.github.io for more information.