Alex Troitsky

Giorgio Perrella

Francisco Fuentes

Sujan Mamidi

Jan Dvorak

Florence Ngo Ngwe

Sonja Siljak-Yakovlev
email: sonia.yakovlev@universite-paris-saclay.fr

Sex Determination in Dioscorea dumetorum: Evidence of Heteromorphic Sex Chromosomes and Sex-Linked NORs

Keywords: dioecy, GC-rich DNA region, heterochromatin, molecular cytogenetics, rDNA, sex chromosomes, sex-linked NORs

Yams (Dioscorea spp.) are a pantropical genus located worldwide that constitute an important source of nutrients and pharmaceutical substances. Some Dioscorea crop species are widely grown in West Africa. One species that is mainly cultivated in Cameroon is Dioscorea dumetorum. This is a dioecious root crop whose sex-determining system was unknown until now. To address the possible presence of sex chromosomes in D. dumetorum, we performed a karyotype characterization of male and female individuals using classical and molecular cytogenetic approaches. It was determined that 2n = 40 was the most common number of chromosomes in all of the investigated samples. One chromosome pair was longer than the others in the chromosome set and was a heteromorph in male and homomorph in female individuals. This pair corresponded to sex chromosomes, and we also confirmed this with molecular cytogenetic experiments. The results of chromomycin banding revealed the presence of strong positive signals on this chromosome pair. The signals, corresponding to GC-rich DNA regions, were similar in size on the chromosomes of the female individuals, whereas they were different in size in the male individuals. This size difference in the GC-rich heterochromatin regions was also apparent in the interphase nuclei as one small and one large fluorescent spot. The results of the in situ hybridization experiment showed that these chromomycin positive signals on the sex chromosomes also corresponded to the 35S rDNA cluster. The mean 2C DNA value (genome size) obtained for D. dumentorum was 0.71 pg (±0.012), which represents a small genome size. We found no difference in the genome size between the male and female individuals. The results of this study contribute to increasing our knowledge of sex determination in D. dumetorum (standard sex-determining XX/XY system) and may have some agronomic applications.

Introduction

The pantropical genus Dioscorea Plum. ex L. (yam) comprises approximately 600 species that are mainly widespread in tropical regions [1,[START_REF] Viruel | Late cretaceous-early eocene origin of yams (Dioscorea, Dioscoreaceae) in the Laurasian Palaearctic and their subsequent Oligocene-Miocene diversification[END_REF] and includes a large number of important tuber crops. These species are mostly dioecious (separate male and female individuals) and belong to the family Dioscoreaceae R.Br. Yams are a staple food for Central and West African populations, and they increase the food security in this region of the continent [START_REF] Bricas | La consommation alimentaire des ignames. Synthèse des connaissances et enjeux par la recherche[END_REF]. The top seven yam producers in the world are Nigeria, Ivory Coast, Ghana, Benin, Togo, Central African Republic, and Cameroon [4]. In total, these countries produce 11 of the 600 yam species found around the world: D. alata L., D. esculenta (Lour.) Burkill, D. oppositifolia L., D. japonica Thunb., D. nummularia Lam., D. pentaphylla L., D. rotundata Poir. [synonym of Dioscorea cayennensis subsp. rotundata (Poir.) J. Miège], D. dumetorum (Kunth) Pax, D. cayennensis Lam., D. trifida L.f, and D. bulbifera L. [START_REF] Coursey | Evolution of Crops Plants[END_REF]. Among these yam species, D. alata, D. cayennensis, D. dumetorum, and D. rotundata are the species that are cultivated in all of the agroecological zones of Cameroon (which is a very important fact in the context of climate change), and their use increases the strength of the economy in this country [START_REF] Azeteh | Dioscorea spp.) production trends in Cameroon: A review[END_REF]. Dioscorea dumetorum has the highest nutritional value of all species of the genus because its tubers are very rich in protein (9.6%). In addition, they contain a starch that is easily digestible due to its crystal structure that is close to that of cereal starch [START_REF] Trèche | Potentialités Nutritionnelles des Ignames (Dioscorea spp.) Cultivées au Cameroun[END_REF][START_REF] Lape | Nutritional quality of yams (Dioscorea rotundata and Dioscorea dumetorum) flours for growing rats[END_REF].

Dioscorea dumetorum, known as the bitter yam, is easily distinguished from others species of the genus by the morphology of its trifoliate, pubescent, thick leaves, and loop shape tubers [START_REF] Dumont | Les Ignames au Cameroun[END_REF][START_REF] Hamon | Wild yams in West Africa: Morphological characteristics[END_REF]. In addition to nutrition, this species is also used for the medicinal purposes, namely for the treatment of diabetes [START_REF] Iwu | Hypoglycaemie activity of dioscoretine from tubers of D. dumetorum in normal and alloxan diabetic rabbits[END_REF]. The tubers contain dioscoretine (water soluble glycoside), which is exploited in pharmaceutical industries as a hypoglycemic agent [START_REF] Iwu | Hypoglycaemie activity of dioscoretine from tubers of D. dumetorum in normal and alloxan diabetic rabbits[END_REF].

In spite of its multiple uses, yam production is globally faced with several constraints, mainly the lack of high quality seeds. The main constraint, common to all cultivated yam species, is the farmers' practice of vegetative reproduction. In general, farmers use tubers from previous harvests for the new plantation. This type of vegetative reproduction is responsible for a yield reduction of approximately 80% [START_REF] Adegbite | Host suitability of crops under yam intercrop to root-knot Nematode (Meloidogyne incognita Race 2) in South-western Nigeria[END_REF] and also for a dramatic loss of genetic diversity. In addition to these constraints, another problem was observed, especially regarding D. dumetorum. The postharvest hardening of tubers occurs two or three days after harvest, which renders the tubers inedible. Therefore, such tubers cannot be used for human consumption. Thus, D. dumetorum tubers should be boiled immediately after harvest and marketed in cooked form [START_REF] Trèche | Le durcissement de Dioscorea dumetorum au Cameroun[END_REF].

Numerous studies have conducted to characterize the genome and its diversity, and to also increase D. dumetorum productivity [START_REF] Sonibare | Genetic diversity of Dioscorea dumetorum (Knuth) Pax using Amplified Fragment Length Polymorphisms (AFLP) and cpDNA[END_REF][START_REF] Sartie | Genetic and phenotypic diversity in a germplasm working collection of cultivated tropical yams (Dioscorea spp.)[END_REF][START_REF] Ngo Ngwe | Analysis of four cultivated species of yams (Dioscorea spp.) from Cameroon[END_REF][START_REF] Ngo Ngwe | Evolution and phylogenetic diversity of yam species (Dioscorea spp.): Implication for conservation and agricultural practices[END_REF][START_REF] Siadjeu | Genetic diversity of sweet yam "Dioscorea dumetorum" (Kunth) pax revealed by morphological traits in two agroecological zones of Cameroon[END_REF][START_REF] Siadjeu | Genetic diversity and population structure of trifoliate yam (Dioscorea dumetorum Kunth) in Cameroon revealed by genotyping-by-sequencing (GBS)[END_REF][START_REF] Siadjeu | High contiguity de novo genome sequence assembly of trifoliate yam (Dioscorea dumetorum) using long read sequencing[END_REF]. Yolou et al. [START_REF] Yolou | La floraison des ignames africaines cultivées (D. cayenensis-D. rotundata et D. dumetorum) dans les champs des producteurs du Centre-Bénin[END_REF] recommended the use of sexual reproduction to increase the quality of D. dumetorum because their cultivars, similar to those of the D. alata and D. cayenensis-rotundata complex, produce viable seeds. Researchers have made considerable progress in genetic improvement by sexual hybridization in D. rotundata [START_REF] Sadik | A review of sexual propagation for yam improvement[END_REF] and D. alata [START_REF] Abraham | Seed set and seedling variation in greater yam (Dioscorea alata L.)[END_REF] via sexual hybridization. In the latter species, polyploidy and infertility were related, as polyploid females were sterile [START_REF] Abraham | Floral biology and artificial pollination in Dioscorea alata L[END_REF]. Knowledge of the genome and breeding system is the key to any successful enhancement program for yams, especially considering that they are a dioecious species.

Although the dioecy is present in ~40% of angiosperm families, it is rare in the final analysis [START_REF] Kafer | On the rarity of dioecy in flowering plants[END_REF]. In contrast to gymnosperms, which present even 65% of dioecious species [START_REF] Walas | Sexual systems in gymnosperms: A review[END_REF] in angiosperms, only approximately 6% or 14,600 species from 960 genera and 200 families are dioecious [START_REF] Renner | Dioecy and its correlates in the flowering plants[END_REF][START_REF] Renner | The relative and absolute frequencies of angiosperm sexual systems: Dioecy, monoecy, gynodioecy, and an updated online database[END_REF]. Ming et al. [START_REF] Ming | Sex chromosomes in land plants[END_REF] estimated the occurrence of dioecious species among land plants at 10% and highlight the fact that dioecy presents the precondition for sex chromosome evolution. Curiously, dioecy was recorded in only three monocot families (Phoenix, Asparagus, and Dioscorea) [START_REF] Muyle | Dioecy in plants: An evolutionary dead end? Insights from a population genomics study in the Silene genus[END_REF]. They noted that the genus Dioscorea would not be appropriate subjects for evolutionary and phylogenetic studies of sex determination because it includes too many species. They stressed, however, that "it was important to study sexual dimorphism in cultured species of the genus and finally to demonstrate or not the existence of sex chromosomes". This was the main purpose of this study.

Montalvão et al. [START_REF] Montalvão | The diversity and dynamics of sex determination in dioecious plants[END_REF] emphasized the diversity of sex-determining systems in dioecious species and the importance of studying them especially for crop plants, which could lead to an increase in their agricultural value.

Genome size measurement and karyotype analyses should be used to characterize the genome of dioecious species. Genome size is important for basic and applied studies involving germplasm enhancement [START_REF] Bennett | The genome, the natural karyotype and biosystematics[END_REF]. Some authors have also mentioned cytological and chromosomal markers as essential tools for any genetic selection program [START_REF] Szinay | FISH applications for genomics and plant breeding strategies in tomato and other solanaceous crops[END_REF][START_REF] Kwiatek | Cytological markers used for identification and transfer of Aegilops spp. chromatin carrying valuable genes into cultivated forms of Triticum[END_REF]. These markers have been used, for example, to observe the sex chromosomes of dioecious plants such as the widely cultivated date palm [START_REF] Siljak-Yakovlev | Chromosomal sex determination and heterochromatin structure in date palm[END_REF].

Karyological studies of D. dumetorum are scarce and, to our knowledge, no studies using molecular cytogenetics have been reported for this species or for the genus Dioscorea in general. The fact that the dioecious species of the genus, especially those that are cultivated, have not attracted more interest on the karyological and cytogenetic level is strange.

With the present work, we mainly aim to more thoroughly understand the sexdetermining system of Dioscorea dumetorum. To achieve this, we first investigated a possible presence of sex chromosomes via a karyotype characterization of male and female individuals using conventional and molecular cytogenetic approaches: fluorochrome banding to detect GC-rich DNA regions and Fluorescent In Situ Hybridization (FISH) to physically map rRNA genes on chromosomes. In addition, to check an eventual difference in DNA amount between male and female individuals, we evaluated the genome size with flow cytometry.

Results

Genome Size and Chromosome Number

The mean 2C DNA content obtained for two accessions of D. dumentorum (individuals in these samples were mixed males and females) from Southwest and Central Cameroon was 0.716 pg (±0.012; CV% = 1.64) and 0.716 (±0.718; CV% = 1.99), respectively. No significant difference was found in the genome size between male and female individuals assessed separately in three accessions (Table 1). After Feulgen staining, we found that 2n = 40 was the most frequent chromosome number inl the investigated samples. In some cells, the numbers of 2n = 36 or 38 were rarely observed. Two heteromorphic chromosomes, that were longer than the other chromosomes in the set, were observed in all male individuals (Figure 1A, arrows). In the female individuals, one chromosomal pair was also larger than the other chromosomes in the karyotype, but it was homomorphic compared with that of the male individuals. These chromosomes corresponded to sex chromosomes (XX/XY), which was additionally confirmed with fluorochrome banding (chromomycin-CMA) and FISH (Figure 1B-F). Same prometaphase plate chowing activity of rRNA genes (arrows) stained by chromomycin (E) and after FISH (F). The beginning of decondensation of sex chromosomes at the early prophase (E, framed detail). Bar = 10 µm.

Heterochromatin and rDNA Physical Mapping

The chromomycin banding revealed that the biggest chromosome pair observed after Feulgen staining presented strong CMA + bands. These bands (signals) corresponded to heterochromatinized GC-rich DNA regions. In the female individuals similar size on the chromosomes (Figure 1B) and in the interphase nuclei (Figure 1B, framed detail). In contrast, such signals were a different size in the chromosomes and interphase nuclei of the male individuals (Figure 1C, arrows, and framed detail).

The FISH experiment confirmed this observation and showed that the CMA + DNA regions corresponded to 35S rDNA sites, strongly labelled with the 18S-5.8S-26S probe (Figure 1D, red signals). These GC-rich heterochromatin normally appeared to be DAPI

Heterochromatin and rDNA Physical Mapping

The chromomycin banding revealed that the biggest chromosome pair observed after Feulgen staining presented strong CMA + bands. These bands (signals) corresponded to heterochromatinized GC-rich DNA regions. In the female individuals similar size on the chromosomes (Figure 1B) and in the interphase nuclei (Figure 1B, framed detail). In contrast, such signals were a different size in the chromosomes and interphase nuclei of the male individuals (Figure 1C, arrows, and framed detail).

The FISH experiment confirmed this observation and showed that the CMA + DNA regions corresponded to 35S rDNA sites, strongly labelled with the 18S-5.8S-26S probe (Figure 1D, red signals). These GC-rich heterochromatin normally appeared to be DAPI (4',6-diamidino-2-phenylindole) negative (AT-poor regions) when observed only with the DAPI filter (Figure 1D, framed detail).

The activity of both 35S sites was also demonstrated after CMA fluorochrome banding and FISH (Figures 1E and1F, respectively).

However, an uneven chromatin decondensation level of sex chromosomes in the male individuals was noticed. The X chromosome decondensed more than the Y chromosome for which the terminal heterochromatin blocks that remained highly condensed were well visible (Figure 1E, framed detail).

From all these results, we can conclude that a standard sex-determining XX/XY system is to the basis of sex determinism in D. dumetorum.

Discussion

Chromosome Feature and Genome Size

For several decades, karyological studies have been conducted for the genus Dioscorea [START_REF] Smith | Notes on the cytology and distribution of the Dioscoreaceae[END_REF][START_REF] Miège | Contribution À L'Étude Systématique des Dioscorea D Afrique Occidentale[END_REF][START_REF] Miège | Nombre chromosomique et répartition géographique de quelques plantes tropicales et équatoriales[END_REF][START_REF] Martin | Chromosome numbers in some Dioscorea species[END_REF][START_REF] Baquar | Chromosome behavior in Nigerian yams (Dioscorea)[END_REF][START_REF] Araki | Some characteristics of interspecific hybrids between Dioscorea japonica Thumb. and Dioscorea opposite Thumb[END_REF][START_REF] Essad | Variation géographique des nombres chromosomiques de base et polyploïdie dans le genre Dioscorea à propos du dénombrement des espèces transversa Brown, pilosiuscuia Bert. et trifida[END_REF][START_REF] Zoundjihèkpon | Dénombrement chomosomique dans dix groups variétaux du compexe Dioscorea cayenensisrotundata[END_REF] and reported chromosome numbers ranged from 2n = 18 to 2n = 144, which demonstrates a varying ploidy level (from 2x to 13x). The majority of Dioscorea species are polyploid, but the tetraploid cytotype (2n = 4x = 40) is becoming the more common [START_REF] Essad | Variation géographique des nombres chromosomiques de base et polyploïdie dans le genre Dioscorea à propos du dénombrement des espèces transversa Brown, pilosiuscuia Bert. et trifida[END_REF][START_REF] Rice | The Chromosome Counts Database (CCDB)-A community resource of plant chromosome numbers[END_REF].

The results of karyological analyses of the Dioscorea genus demonstrated the existence of three base chromosome numbers (x = 9, 10, and 12). The basic chromosome number of x= 9 was mainly reported in Dioscorea species from the New-Word [START_REF] Martin | Chromosome numbers in some Dioscorea species[END_REF][START_REF] Essad | Variation géographique des nombres chromosomiques de base et polyploïdie dans le genre Dioscorea à propos du dénombrement des espèces transversa Brown, pilosiuscuia Bert. et trifida[END_REF][START_REF] Rama-Rao | Meiotic studies in species and hybrids in medicinal yams[END_REF] whereas x = 10 is mainly found in African [START_REF] Miège | Contribution À L'Étude Systématique des Dioscorea D Afrique Occidentale[END_REF][START_REF] Martin | Chromosome numbers in some Dioscorea species[END_REF][START_REF] Essad | Variation géographique des nombres chromosomiques de base et polyploïdie dans le genre Dioscorea à propos du dénombrement des espèces transversa Brown, pilosiuscuia Bert. et trifida[END_REF] and Asian representatives of the genus [START_REF] Ramachandran | Cytological studies in Dioscoreaceae[END_REF][START_REF] Takeuchi | Chromosome numbers of some Japanese Dioscorea species[END_REF][START_REF] Ching | cytotaxonomic study on Chinese Dioscorea L. the chromosome numbers and their relation to the origin and evolution of the genus[END_REF]. The basic number of x = 12 was found in two European paleoendemic diploid species: D. pyrenaica Bubani & Bordère ex Gren. and D. balcanica Košanin [START_REF] Martin | Chromosome numbers in some Dioscorea species[END_REF]. The results of all these studies show that the descending disploidy (from x = 12 to x = 9) and polyloidy (from 2x to 8x for x = 10 and from 2x to 16x for x = 9) are the main evolutionary mechanisms in the genus Dioscorea.

We found that D. dumetorum from Cameroon displayed a stable chromosome number 2n = 40, which confirmed the basic chromosome number of x = 10 and a tetraploid state of this cytotypes with a secondary basic chromosome number of x = 20. Miège [START_REF] Miège | Contribution À L'Étude Systématique des Dioscorea D Afrique Occidentale[END_REF] and Baquar [START_REF] Baquar | Chromosome behavior in Nigerian yams (Dioscorea)[END_REF] already reported the same number of chromosomes for D. dumetorum. Miège [START_REF] Miège | Nombre chromosomique et répartition géographique de quelques plantes tropicales et équatoriales[END_REF] and Martin and Ortiz [START_REF] Martin | Chromosome numbers in some Dioscorea species[END_REF] found 2n = 36, 45, and 54 for D. dumetorum, and therefore demonstrated the existence of variability in the chromosome number and ploidy level of this species. In some Dioscorea species, several ploidy levels exist: in D. alata, the authors of [START_REF] Arumuganathan | Nuclear DNA content of some important plant species[END_REF][START_REF] Dansi | Ploidy level and nuclear DNA content of some accessions of water yam (Dioscorea alata) collected at Savè, a district of central Benin[END_REF] reported tetraploid and octoploid chromosome numbers, respectively, and in a D. cayenensis-rotundata complex, the authors of [START_REF] Hamon | Etude des index d'ADN de huit ignames (Dioscorea spp.) par cytométrie en flux[END_REF] even detected three ploidy levels (4x, 6x, and 8x).

Several Dioscorea species, which are considered tetraploid, have been revealed as diploid by the microsatellite markers, namely a diploidized tetraploid, with the secondary basic chromosome number x = 20. It is the case of D. rotundata [START_REF] Scarcelli | Segregation Patterns of izozyme loci and microsatellite markers show the diploidy of African yam Dioscorea rotundata (2n = 40)[END_REF] and D. alata [START_REF] Arnau | Revision of ploidy status of Dioscorea alata (Dioscoreaceae) by cytogenetic and microsatellite segregation analysis[END_REF]. The similar studies, coupled with a meiosis study, should be performed on D. dumetorum to confirm its basic chromosomic number and consequently its ploidy state, which is important for genetic diversity studies and breeding programs.

The genome size of Dioscorea species with 2n = 40 range from 0.70 pg in D. dumentorum to 2.10 pg in D. esculenta [START_REF] Siadjeu | High contiguity de novo genome sequence assembly of trifoliate yam (Dioscorea dumetorum) using long read sequencing[END_REF][START_REF] Hamon | Etude des index d'ADN de huit ignames (Dioscorea spp.) par cytométrie en flux[END_REF][START_REF] Obidiegwu | Estimation of the nuclear DNA content in some representatives of genus Dioscorea[END_REF], which presents a large panel of variation for the same ploidy level. Dioscorea dumentorum with 2C values of 0.71 pg belong to the very small genome category (2C ≤ 2.8 pg) according to the categories established by Leitch et al. [START_REF] Leitch | Phylogenetic analysis of DNA C-values provides evidence for a small ancestral genome size in flowering plants[END_REF]. A similar value was already reported for D. dumetorum from Benin, Nigeria, Ghana, Togo [START_REF] Obidiegwu | Estimation of the nuclear DNA content in some representatives of genus Dioscorea[END_REF], and Cameroon [START_REF] Ngo Ngwe | Analysis of four cultivated species of yams (Dioscorea spp.) from Cameroon[END_REF]. In this study, we did not detect any significant difference in genome size between male and female individuals.

Because D. dumetorum has a very small genome (0.71 pg/2C or 347 Mbp/1C in the present data; 322 to 350 Mbp/1C reported by Siadjeu et al. [START_REF] Siadjeu | High contiguity de novo genome sequence assembly of trifoliate yam (Dioscorea dumetorum) using long read sequencing[END_REF]), this species could be a useful model to study sex chromosome evolution in the genus Dioscorea, of which almost all the species are dioecious.

Molecular Cytogenetics Characterization of Sex Chromosomes

The results of the cytological analyses after Feulgen staining revealed two heteromorphic chromosomes that were longer than the other chromosomes in the male individuals. These chromosomes corresponded to sex chromosomes, which was additionally confirmed by fluorochrome banding and FISH methods. The use of these techniques allowed us to solve the difficulties concerning the cytogenetical studies of the genus Dioscorea.

In the past, several studies have been performed to show a possible presence of sex chromosomes in the Dioscorea genus via cytological observations. Some reports suggested the presence of heteromorphic sex chromosomes [START_REF] Smith | Notes on the cytology and distribution of the Dioscoreaceae[END_REF][START_REF] Ramachandran | Studies on the cytology and sex determination of the Dioscoreaceae[END_REF][START_REF] Bhat | Sex chromosomes in Dioscorea deltoidea wall[END_REF], whereas others did not [START_REF] Martin | Chromosome numbers in some Dioscorea species[END_REF][START_REF] Takeuchi | Chromosome numbers of some Japanese Dioscorea species[END_REF]. However, none of these authors were able to cytologically demonstrate the presence of sex chromosomes. Given the difficulties associated with observing chromosomes, several authors have used genetic or molecular methods as an alternative to validate the presence of sex chromosomes in the Dioscorea genus [START_REF] Siadjeu | High contiguity de novo genome sequence assembly of trifoliate yam (Dioscorea dumetorum) using long read sequencing[END_REF][START_REF] Martin | Sex ratio and sex determination in Dioscorea[END_REF][START_REF] Terauchi | Mapping of Dioscorea tokoro genome: AFLP markers linked to sex[END_REF][START_REF] Tamiru | Genome sequencing of the staple food crop white Guinea yam enables the development of a molecular marker for sex determination[END_REF][START_REF] Cormier | A reference high-density genetic map of greater yam (Dioscorea alata L.)[END_REF][START_REF] Mondo | Genome-Wide Association Studies for Sex Determination and Cross-Compatibility in Water Yam (Dioscorea alata L.)[END_REF]. Researchers typically used Dioscorea tokoro as a model species for genetic studies because creating a controlled cross of D. tokoro is relatively easy [START_REF] Terauchi | Mapping of Dioscorea tokoro genome: AFLP markers linked to sex[END_REF][START_REF] Terauchi | DNA polymorphism at the Pgi locus of a wild yam, Dioscorea tokoro[END_REF]. These genetic studies led scientists to propose that the male, but not the female, determines the sex of the progeny, and that the male is the heterogametic. Following the sequencing of the D. dumetorum genome, Siadjeu et al. [START_REF] Siadjeu | High contiguity de novo genome sequence assembly of trifoliate yam (Dioscorea dumetorum) using long read sequencing[END_REF] suggested "that only one locus may be involved in sex determination and may be inherited via a system of XX/XY sex chromosomes involving heterogametic males (XY)".

We initiated these studies as part of a thesis [START_REF] Ngo Ngwe | Evaluation de la Diversité Génétique des Dioscorea Spp. du Cameroun Et Développement des Techniques de Conservation[END_REF] and presented the first results at a conference in 2019 [START_REF] Ngo Ngwe | Heterochromatin and rDNA pattern revealed heteromorphic sex chromosomes in Dioscorea dumetorum. 1st Congress of Geneticists in Bosnia and Herzegovina[END_REF]. We implemented chromomycin banding and FISH techniques, which made it possible to demonstrate the presence of sex chromosomes and characterize them in the D. dumetorum karyotype. These chromosomes are homomorphic in female (XX) individuals whereas they are heteromorphic in male (XY) individuals. The X and Y chromosomes are easily distinguished by their size, as the Y is the largest, and by the size of the CMA and FISH signals. The strong signals corresponding to GC-rich heterochromatin could be explained by the accumulation of repetitive sequences due to the lack of recombination between the sex chromosomes.

The application of the FISH protocol to other dioecious species such as the palm date also revealed differences in sex chromosome structures [START_REF] Siljak-Yakovlev | Chromosomal sex determination and heterochromatin structure in date palm[END_REF]. The sex chromosome structure found in D. dumetorum with both chromomycin banding and physical rDNA mapping was similar to those of the corresponding chromosomes present in the palm date [START_REF] Siljak-Yakovlev | Chromosomal sex determination and heterochromatin structure in date palm[END_REF].

Approximately 40 species (from 21 genera and 15 families of angiosperms) are known to have sex chromosomes, and of these, only ~20 species from six genera (Cannabis, Humulus, Silene, Coccinia, Trichosanthes, and Rumex) have heteromorphic sex chromosomes [START_REF] Ming | Sex chromosomes in land plants[END_REF]. Now, because of the results we obtained in this study (the cytologically observable heteromorphic sex chromosomes), the genus Dioscorea can be added to this list.

Unusual Association of rDNA Cluster and NORs with Sex Chromosomes

Another finding worth highlighting is that D. dumetorum sex chromosomes also carry ribosomal genes (in the NORs), which have already reported in date palms and some other plant species such as Spinacia oleracea [START_REF] Lan | Differentiating sex chromosomes of the dioecious Spinacia oleracea L. (spinach) by FISH of 45S rDNA[END_REF] and Marchantia polymorpha [START_REF] Fujisawa | Evolution of ribosomal DNA unit on the X chromosome independent of autosomal units in the liverwort Marchantia polymorpha[END_REF]. Therefore, these chromosomes are of particular importance in the genome as they carry both the sex-determining region and the ribosomal genes that control nucleolus formation. This phenomenon has also been detected in animals, especially in fish [START_REF] Reed | Polymorphism of the nucleolus organizer region (NOR) on the putative sex chromosomes of Arctic char (Salvelinus alpinus) is not sex related[END_REF][START_REF] Ocalewicz | Chromosomal location of Ag/CMA3 -NORs, 5S rDNA and telomeric repeats in two stickleback species[END_REF] and very rarely in mammals [START_REF] Proskuryakova | The case of X and Y localization of nucleolus organizer regions (NORs) in Tragulus javanicus (Cetartiodactyla, Mammalia)[END_REF].

Charlesworth [START_REF] Charlesworth | Plant sex determination and sex chromosomes[END_REF] stressed that the sex chromosome systems independently arose several times in angiosperms from hermaphroditic ancestors (mainly monoecious species). According Hobza et al. [START_REF] Hobza | Impact of repetitive DNA on sex chromosome evolution in plants[END_REF][START_REF] Hobza | Impact of repetitive elements on the y chromosome formation in plants[END_REF], "an early event shaping the Y chromosome" could be a consequence of a recombination restriction caused by the accumulation of repetitive sequences particularly on the Y chromosomes. In our case, these sequences were particularly present in the rDNA cluster region, which was considerably larger on Y chromosomes than on X chromosomes. The fact that rDNA was presently found in sex chromosomes (sex-linked NORs) may suggest that the origin of these chromosomes is related to the nucleolar autosomes of hermaphroditic ancestors.

Materials and Methods

Plant Materials

The materials included yam tubers from male and female D. dumetorum individuals that we collected in the central and southwest regions of Cameroon (Table 1). These regions belong to the agro-ecological zones where yam production is the most important. The tubers were enveloped in blotting paper and placed in plastic bags to initiate root development. The first roots appear after two weeks and the first leaves after three to four weeks. The secondary root tips obtained after germination were used for the cytogenetic studies and the first leaves were used for the genome size assessment.

Chromosome Number Determination

We pretreated secondary roots tips, obtained from the germination of the tubers in the laboratory, with 0.002 M 8-hydroxyquinoline at 16 • C for 3 h and performed a fixation in freshly prepared 3:1 (v/v) ethanol-acetic acid for at least 48 h. After this first fixation, the root tips could be stored in ethanol 70% at -20 • C for several months. We hydrolyzed the roots tips in 1N HCL for 16 min at 60 • C and stained them with a Schiff reagent using the standard Feulgen method. To intensify the staining, we performed the squash in a drop of orcein or acetic carmine and determined the chromosome number on several well-spread metaphase plates from at least 5 individuals per accession.

Genome Size Assessment Using Flow Cytometry

The leaves of D. dumentorum were collected from tubers sprouted in germination at the laboratory. For each accession, nuclei were isolated following the method of Bourge et al. [START_REF] Bourge | Flow cytometry as tool in plant sciences, with emphasis on genome size and ploidy level assessment[END_REF]: 50 mg of yam leaves together with 20 mg of leaves from the internal standard [tomato, Solanum lycopersicum, 2C = 1.99 pg [START_REF] Lepers-Andrzejewski | Diversity and dynamics of plant genome size: An example of polysomaty from a cytogenetic study of Tahitian vanilla (Vanilla x tahitensis, Orchidaceae)[END_REF] were co-chopped with a razor blade in a Petri dish containing 1 mL of cold Gif nuclear isolating buffer-GNB [START_REF] Bourge | Flow cytometry as tool in plant sciences, with emphasis on genome size and ploidy level assessment[END_REF]): 45 mM MgCl 2 , 30 mM Sodium-Citrate and 60 mM MOPS acid pH 7.0, 1% PVP 10.000, RNAse (2.5 U/mL) and 10 mM sodium metabisulfite (S 2 O 5 .Na 2 ), which is a reducing agent that is less toxic than β-mercaptoethanol. This GNB buffer can be complemented by 0.5% Triton X-100. The nuclei suspension was filtered through nylon mesh (pore size 30 µg/mL; Sigma, Ronkonkoma, NY, USA) and nuclei were stained with 100 µg/mL propidium iodide (PI), a specific DNA fluorochrome intercalating dye, and kept it for 5 min at 4 • C.

Ten or five individuals from two accessions were analyzed for average genome size. Two individuals, one male and one female, from three accessions were measured to assess the possible difference between the two sexes. At least 5000 nuclei were measured using a Partec CyFlowSL3 (Partec, Münster, Germany) 532-nm laser cytometer. Fluorescence histograms were analyzed for each sample and internal standard. The nuclear DNA content was estimated using the linear relationship between the fluorescent signals from stained nuclei of the Dioscorea specimens and the internal standard obtained with the following formula: The fixed root tips were first washed in a 0.01 M citrate buffer (pH 4.6) for 15 min, then incubated in an enzymatic mixture composed of 4% cellulase RS (Onozuka Yakult Honsha Co., Tokyo, Japan), 1% pectolyase Y23 (Seishin Pharmaceuical Co, Tokio, Japan), and 4% hemicellulase (Sigma Chemical Co., Ronkonkoma, NY, USA) in a 0.01 M citrate buffer at pH 4.6. Enzymatic digestion time depended on the size of the roots and was carried out from 30 min to 1 h at 37 • C. Then, the digested meristems were squashed onto a drop of freshly prepared 50% acetic acid and the preparations were observed with a phase contrast microscope. The best slides were frozen at -80 • C for at least 12 h. The cover slips were removed and the slides were rinsed with absolute ethanol and air-dried.

Fluorochrome Banding

The chromomycin A 3 (CMA) fluorochrome was used for detection of the GC-rich DNA regions. The technique of fluorochrome banding was performed, following Schweizer [START_REF] Schweizer | Reverse fluorescent chromosome banding with chromomycin and DAPI[END_REF] with minor modifications from Siljak-Yakovlev et al. [START_REF] Siljak-Yakovlev | Nuclear DNA content, base composition, heterochromatin and rDNA in Picea omorika and Picea abies[END_REF]: chromomycin concentration was 0.2 mg/mL, staining time was 60 min and slides were mounted in citifluor AF2 (Agar Scientific Ltd., Stanstead, Essex, UK). Some slides were used for the FISH experiment after discoloration in an ethanol-glacial acetic acid solution (3/1, v/v), and dehydration in a graded ethanol series (70%, 90%, 100%) for 3 min each and then air-drying.

Florescence In Situ Hybridization

The fluorescence in situ hybridization (FISH) was performed following Heslop-Harrison et al. [START_REF] Heslop-Harrison | In situ hybridization with automated chromosome denaturation techniques[END_REF] with slight modifications. The FISH was accomplished to detect the 35S rRNA genes. The 35S rDNA probe was a clone of 4-kb from the EcoRI fragment, which included 18S-5.8S-26S rDNA sequences from Arabidopsis thaliana (L.) Heynh labelled with the direct Cy3 fluorochrome (Amersham, Courtaboeuf, Les Ulis, France) by a nick translation, according to the manufacturer's protocol.

Observation of the chromosome plates was made with an epifluorescence Zeiss Axiophot microscope with different combinations of excitation and emission filter sets (01, 07, 15) and the triple filter [START_REF] Kafer | On the rarity of dioecy in flowering plants[END_REF]. Hybridization signals were analyzed using a highly sensitive CCD camera (Retiga 2000R; Princeton instruments, Evry, France). The images of the 35S rDNA patterns were overlapped using a Metavue Image Analyzer (Evry, France) to obtain a final FISH image.

Conclusions

Sex determination in D. dumetorum is based on the standard XX/XY sex determining system. We confirmed the presence of heteromophic sex chromosomes in male individuals and homomorphic sex chromosomes in female individuals with classic and molecular cytogenetic approaches. These chromosomes were the only ones in the chromosomal set to have strong heterochromatic GC-rich DNA regions of unequal size in the male individuals. The ribosomal genes (rRNA) or sex-linked NORs were located in the same regions. The sex-determining genes are also probably located in this non-recombining region. Because D. dumetorum has a very small genome (347 Mbp/1C), the sex-determining regions may be identified in the near future with genome sequencing, which will be carried out in our future research. The results presented in this study contribute to enhancing our understanding of D. dumetorum sex determination and opens new perspectives for the improvement and resumption of interspecific crossing and selection programs in yam crops.

Figure 1 .

 1 Figure 1. (A-F) orcein-stained metaphase of male individual (2n = 40) with sexual chromosomes X and Y indicated by arrows (A). Chromomycin-stained metaphase and interphase nuclei (framed details) of female (B) and male (C) individuals. Note the strong difference in size of CMA signals in male individual (C). Same chromosome plate after FISH experiment. CMA signals were also strongly labelled with rDNA 35S probe (D, red signals) but were DAPI negatives (D, framed detail). Same prometaphase plate chowing activity of rRNA genes (arrows) stained by chromomycin (E) and after FISH (F). The beginning of decondensation of sex chromosomes at the early prophase (E, framed detail). Bar = 10 µm.

Figure 1 .

 1 Figure 1. (A-F) orcein-stained metaphase of male individual (2n = 40) with sexual chromosomes X and Y indicated by arrows (A). Chromomycin-stained metaphase and interphase nuclei (framed details) of female (B) and male (C) individuals. Note the strong difference in size of CMA signals in male individual (C). Same chromosome plate after FISH experiment. CMA signals were also strongly labelled with rDNA 35S probe (D, red signals) but were DAPI negatives (D, framed detail). Same prometaphase plate chowing activity of rRNA genes (arrows) stained by chromomycin (E) and after FISH (F). The beginning of decondensation of sex chromosomes at the early prophase (E, framed detail). Bar = 10 µm.

2C

  DNA content/nucleus (pg) = (Yam 2C peak mean/Tomato 2C peak mean) × Tomato 2C DNA (pg) 4.4. Fluorochrome Banding and Fluorescence In Situ Hybridization 4.4.1. Protoplast Preparation

Table 1 .

 1 Origin of material and 2C DNA values obtained for Dioscorea studied accessions.

		Collection Site	Geographic Coordinats Latitude (N) Longitude E	2C DNA in pg (SD; CV%)	N • of Measured Individuals
	D. dumetorum mix *	Muyaka	4 • 43 18 N	9 • 38 27 E	0.714 (0.012; 1.64)	5
	D. dumetorum mix *	Mbangassina	4 • 37 47 N	11 • 42 25 E	0.718 (0.014; 1.99)	10
	D. dumetorum ♂ D. dumetorum ♀ D. dumetorum ♂ D. dumetorum ♀ D. dumetorum ♂ D. dumetorum ♀	Ombessa Ombessa Ekona Ekona Bafoussam Bafoussam	4 • 36 0 N 4 • 14 00 N 5 • 28 66 N	11 • 15 0 E 9 • 20 04.0 E 10 • 25 03 E	0.712 0.720 0.694 0.714 0.729 0.718	1 1 1 1 1 1

* The individuals in these samples were mixed, males and females.

Acknowledgments:

We are grateful to Perla Hamon for the very interesting and useful discussions during the preparation of this manuscript. We thank Spencer Brown and Michael Bourge for their expertise with the Flow Cytometry of I2BC, Gif-sur-Yvette, France.

Data Availability Statement: Not applicable.

Plants 2023, [START_REF] Adegbite | Host suitability of crops under yam intercrop to root-knot Nematode (Meloidogyne incognita Race 2) in South-western Nigeria[END_REF] 228

Conflicts of Interest:

The authors declare no conflict of interest.


Nacira Abbas
email: nacira.abbas@inria.fr

Alexandre Bazin
email: alexandre.bazin@umontpellier.fr

Jérôme David
email: jerome.david@inria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures

A link key between two RDF datasets 𝐷 1 and 𝐷 2 is a set of pairs of properties allowing to identify pairs of individuals 𝑥 1 and 𝑥 2 through an identity link such as x 1 owl ∶ sameAs x 2 . In this paper, relying on and extending previous work, we introduce an original formalization of link key discovery based on the framework of Partition Pattern Structures (pps). Our objective is to study and evaluate the redundancy of link keys based on the fact that owl:sameAs is an equivalence relation. In the pps concept lattice, every concept has an extent representing a link key candidate and an intent representing a partition of instances into sets of equivalent instances. Experiments show three main results. Firstly redundancy of link keys is not so significant in real-world datasets. Nevertheless, the link key discovery approach based on pps returns a reduced number of non redundant link key candidates when compared to a standard approach. Moreover, the pps-based approach is efficient and returns link keys of high quality.

Introduction

In this paper, we are interested in data interlinking whose objective is to discover identity links across two RDF datasets over the web of data [START_REF] Ferrara | Data Linking for the Semantic Web[END_REF][START_REF] Christen | Data Matching -Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection[END_REF][START_REF] Nentwig | A survey of current Link Discovery frameworks[END_REF]. The same real world entity can be represented in two RDF datasets by different subjects in RDF triples having the form (subject, property, object). Then, for cleaning data and providing data of better quality, it is meaningful to detect such identities. There are both numerical and logical approaches for discovering these identities. For example, interlinking methods have been implemented in systems such as LIMES [START_REF] Ngomo | LIMES -A Time-Efficient Approach for Large-Scale Link Discovery on the Web of Data[END_REF] and SILK [START_REF] Volz | Silk -A Link Discovery Framework for the Web of Data[END_REF]. These systems use link specifications, i.e. rules that declare whether two IRIs should be linked. Link specifications can also be specified by users or learned from data [START_REF] Isele | Active learning of expressive linkage rules using genetic programming[END_REF][START_REF] Ngomo | EAGLE: Efficient Active Learning of Link Specifications Using Genetic Programming[END_REF][START_REF] Ngomo | Unsupervised learning of link specifications: deterministic vs. non-deterministic[END_REF].

In particular, link keys which are under investigation in this paper are special kinds of rules allowing to infer identity links between two RDF datasets. More formally, a link key is composed of two sets of pairs of properties ({(𝑝 𝑖 , 𝑞 𝑖 )} 𝑖 , {(𝑝 ′ 𝑗 , 𝑞 ′ 𝑗 )} 𝑗 ) associated with a pair of classes (𝑐 1 , 𝑐 2 ). Then, whenever an instance 𝑎 1 of class 𝑐 1 has the same (non empty) set of values as an instance 𝑏 1 of class 𝑐 2 , i.e. 𝑝 𝑖 (𝑎 1 ) = 𝑞 𝑖 (𝑏 1 ) for all pairs of properties in the first set (universal quantification), and shares at least one value for all pairs of properties in the second set (existential quantification), i.e. 𝑝 ′ 𝑗 (𝑎 1 ) ∩ 𝑞 ′ 𝑗 (𝑏 1 ) ≠ ∅, then 𝑎 1 and 𝑏 1 denote the same entity, i.e., an owl:sameAs relation can be established between 𝑎 1 and 𝑏 1 . More concretely, the expression k=({(designation,title)},{(designation,title),(creator,author)}, (Book,Novel))

states that whenever an instance 𝑎 of class Book has the same non empty values for the property designation as an instance 𝑏 of the class Novel for title, and that 𝑎 and 𝑏 share at least one value for the properties creator and author, then 𝑎 and 𝑏 denote the same entity a owl:sameAs link can be established between 𝑎 and 𝑏.

Link keys are not provided with the datasets and algorithms are designed for automatically discovering such link keys [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF][START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF][START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF]. Given two RDF datasets, these algorithms reduce the search space and focus on the discovery of "link key candidates" instead of checking every combination of pairs of properties and pairs of classes. The notion of a link key candidate -made precise below-involves maximality and closure. Following this line, natural links were established in [START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF][START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF] between link key discovery and Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]). Indeed, FCA appeared as a suitable framework for the discovery of link key candidates, which are then evaluated thanks to appropriate quality measures [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF].

Given two RDF datasets, FCA is applied in [START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF] to a binary table where rows correspond to pairs of individuals and columns to pairs of properties. The intent of a resulting concept corresponds to a link key candidate, which remains to be validated thanks to suitable quality measures. The extent of the concept includes the potential identity links between individuals. A generalization of the former approach is proposed in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF], which is based on pattern structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF] and which takes into account different pairs of classes at the same time in the discovery of link keys.

Actually, "good" link key candidates over two RDF datasets have to generate different and maximal link sets, i.e., a mapping between individuals which is "close to a bijection". However it appears that two different link key candidates may generate the same link set when the link set is considered as a partition w.r.t. the owl:sameAs equivalence relation. This means that these two link key candidates present a certain redundancy, and then they can be considered as equivalent and merged in a way to be defined. This redundancy can be detected thanks to the properties of owl:sameAs as an equivalence relation, i.e. reflexivity, symmetry, and transitivity. Then, the owl:sameAs relation generates partitions among pairs of individuals that can be used for reducing the number of potential link key candidates. Indeed, two candidates relying on the same partition are considered as redundant and can be merged. However, we do not have a concrete idea of the importance of such redundancy and we should find a way to measure it. This is one objective of this paper to try to materialize this redundancy and to measure its importance.

For doing so, taking inspiration from the work carried out in [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF] on the discovery of functional dependencies, we provide a formalization of link key discovery based on "partition pattern structures" (pps), which allow us to take into account sets of equivalent individuals w.r.t. owl:sameAs as partitions. Then, a pattern concept represents a link key candidate and the related partition induced by the candidate. This approach is able to retrieve all link key candidates as a set of "non redundant" link keys. Moreover, this link key discovery process based on pps is operational and original 1 . Actually, this is the first time that the characteristics of owl:sameAs as an equivalence relation are considered, and that the related partitions of pairs of individuals are directly used for defining link key candidates. Thanks to pps, we are able to define redundancy of link key candidates and we also introduce a new measure based on the size of partitions for evaluating the quality of the discovered candidates. Finally, the experiments proposed in the last part of this paper provide three main results. Firstly, the redundancy of link keys in real-world datasets appears to be not so significant. Nevertheless, the current link key discovery approach based on pps is efficient and returns a reduced number of non redundant link key candidates. Moreover, this pps-based approach returns link keys of very high quality when compared to competitors.

The summary of the paper is as follows. Section 2 presents some basics about link keys. Then the discovery of non-redundant link keys based on pattern structures and partition pattern structures is made precise in Section 3. A running example illustrates all these constructions. New quality measures related to non redundant link keys are defined in Section 4. Finally, experiments in Section 5 show the capability and efficiency of the pps-based approach in link key discovery.

Preliminaries

This section introduces the basic definitions relative to data interlinking with link keys. We recall what an RDF dataset is and then we introduce two forms of link keys, namely link key expressions and link key candidates.

RDF Data

Definition 1 (RDF Dataset). Let 𝑈 denote a set of IRIs, i.e., "Internationalized Resource Identifiers", 𝐵 a set of blank nodes, i.e., "anonymous resources", and 𝐿 a set of literals, i.e., "string values".

An RDF dataset is a set of triples (𝑠, 𝑝, 𝑜) ∈ (𝑈 ∪ 𝐵) × 𝑈 × (𝑈 ∪ 𝐵 ∪ 𝐿).

Let 𝐷 be an RDF dataset, 𝑆(𝐷) = {𝑠 | ∃ 𝑝, 𝑜 (𝑠, 𝑝, 𝑜) ∈ 𝐷} denotes the set of individual identifiers, 𝑃(𝐷) = {𝑝 | ∃ 𝑠, 𝑜 (𝑠, 𝑝, 𝑜) ∈ 𝐷} the set of property identifiers, and 𝐶(𝐷) = {𝑐 | ∃ 𝑠 (𝑠, rdf:type, 𝑐) ∈ 𝐷} the set of class identifiers.

Moreover, 𝐼 (𝑐) = {𝑠 | ∃ 𝑠 (𝑠, rdf:type, 𝑐) ∈ 𝐷} denotes the set of instances of 𝑐 ∈ 𝐶(𝐷) while 𝑝(𝑠) = {𝑜 | (𝑠, 𝑝, 𝑜) ∈ 𝐷} denotes the set of objects -or values-associated with 𝑠 through property 𝑝.

An identity link is an RDF triple of the form (𝑎, owl:sameAs, 𝑏) stating that the IRIs 𝑎 and 𝑏 are referring to the same entity, alternatively 𝑎 and 𝑏 are denoting the same individual.

Example 1. In Figure 1, the RDF datasets 𝐷 1 and 𝐷 2 include 𝑃(𝐷 1 ) = {𝑝 1 , 𝑝 2 , 𝑝 3 , 𝑝 4 } and 𝑃(𝐷 2 ) = {𝑞 1 , 𝑞 2 , 𝑞 3 , 𝑞 4 } as sets of property identifiers, and 𝐶(𝐷 1 ) = {𝑐 1 } and 𝐶(𝐷 2 ) = {𝑐 2 } as class identifiers. In addition, 𝐼 (𝑐 1 ) = {𝑎 1 , 𝑎 2 , 𝑎 3 , 𝑎 4 , 𝑎 5 } and 𝐼 (𝑐 2 ) = {𝑏 1 , 𝑏 2 , 𝑏 3 , 𝑏 4 , 𝑏 5 } denote respectively the sets of instances of class 𝑐 1 and class 𝑐 2 . Finally, considering subject 𝑏 3 and property 𝑞 2 , the related set of objects or the "value" of 𝑏 3 for property 𝑞 2 is 𝑞 2 (𝑏 3 ) = {𝑜 8 , 𝑜 9 }. 1 The present paper extends a short preliminary version published in [START_REF] Abbas | Non-Redundant Link Keys in RDF Data: Preliminary Steps[END_REF].

𝑎 1 𝑎 2 𝑎 3 𝑎 4 𝑎 5 𝑜 1 𝑜 2 𝑜 3 𝑜 4 𝑜 5 𝑜 6 𝑜 7 𝑜 8 𝑜 9 𝑜 10 𝑜 11 𝑜 12 𝑜 13 𝑏 1 𝑏 2 𝑏 3 𝑏 4 𝑏 5 𝑝1 𝑞 1 𝑝2 𝑞 2 𝑝 2 𝑞 2 𝑝1 𝑞1 𝑝 2 𝑞 2 𝑝 1 𝑞1 𝑝 1 𝑞 1 𝑝 2 𝑞2 𝑞2 𝑝 3 𝑞3 𝑝 4 𝑞 4 𝑝 3 𝑞 3 𝑝 4 𝑞 4 𝑐 1 𝑐 2 𝐷 1 𝐷 2 Figure 1:
An example of two related RDF datasets. On the left-hand side, the dataset 𝐷 1 is populated with instances of class 𝑐 1 while on the right-hand side the dataset 𝐷 2 is populated with instances of class 𝑐 2 .

Link Keys

Link keys are logical constructions allowing to infer identity links between instances of two classes lying in two RDF datasets. In the following we introduce two syntactic definitions of link keys, namely "link key expressions" and "link key candidates". A definition of a link key and its semantics using Description Logics interpretation is proposed in [START_REF] Atencia | On the relation between keys and link keys for data interlinking[END_REF]. However, in this paper we will stick to these two syntactic definitions for the sake of simplicity. Intuitively, a link key expression 𝑘 = (𝐸𝑞, 𝐼 𝑛, (𝑐 1 , 𝑐 2 )) is composed of two sets of pairs of properties, i.e., 𝐸𝑞 and 𝐼 𝑛, where 𝐸𝑞 is based on equality and 𝐼 𝑛 on non empty intersection, while links are generated between instances of classes 𝑐 1 and 𝑐 2 . More formally we have: Definition 2 (Link key expression). Let 𝐷 1 and 𝐷 2 be two RDF datasets, 𝑘 = (𝐸𝑞, 𝐼 𝑛, (𝑐 1 , 𝑐 2 )) is a link key expression over 𝐷 1 and 𝐷 2 iff 𝐼 𝑛 ⊆ 𝑃(𝐷 1 ) × 𝑃(𝐷 2 ), 𝐸𝑞 ⊆ 𝐼 𝑛, 𝑐 1 ∈ 𝐶(𝐷 1 ) and 𝑐 2 ∈ 𝐶(𝐷 2 ).

The set of links generated by 𝑘 is denoted by 𝐿(𝑘) and includes a set of pairs of instances (𝑎, 𝑏) ∈ 𝐼 (𝑐 1 ) × 𝐼 (𝑐 2 ) satisfying:

(i) for all (𝑝, 𝑞) ∈ 𝐸𝑞, 𝑝(𝑎) = 𝑞(𝑏) and 𝑝(𝑎) ≠ ∅, (ii) for all (𝑝, 𝑞) ∈ 𝐼 𝑛 ⧵ 𝐸𝑞, 𝑝(𝑎) ∩ 𝑞(𝑏) ≠ ∅.

The number of link key expressions may be exponential w.r.t. the number of properties. To reduce the search space, algorithms for link key discovery only consider "link key candidates", i.e., link key expressions which generate at least one link and which are "maximal" among the set of link key expressions.

PS objects (g) descriptions (𝛿(𝑔))

(𝑎 1 , 𝑏 1 ) {∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )} (𝑎 1 , 𝑏 2 ) {∃(𝑝 2 , 𝑞 2 )} (𝑎 2 , 𝑏 1 ) {∃(𝑝 1 , 𝑞 1 )} (𝑎 2 , 𝑏 2 ) {∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )} (𝑎 3 , 𝑏 3 ) {∀(𝑝 1 , 𝑞 1 ), ∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )} (𝑎 4 , 𝑏 4 ) {∀(𝑝 3 , 𝑞 3 ), ∃(𝑝 3 , 𝑞 3 )} (𝑎 4 , 𝑏 5 ) {∀(𝑝 4 , 𝑞 4 ), ∃(𝑝 4 , 𝑞 4 )} (𝑎 5 , 𝑏 4 ) {∀(𝑝 4 , 𝑞 4 ), ∃(𝑝 4 , 𝑞 4 )} (𝑎 5 , 𝑏 5 ) {∀(𝑝 3 , 𝑞 3 ), ∃(𝑝 3 , 𝑞 3 )}

Table 1

The pattern structure related to datasets 𝐷 1 and 𝐷 2 given in Fig. 1.

Definition 3 (Link key candidate). A link key expression

𝑘 1 = (𝐸𝑞 1 , 𝐼 𝑛 1 , (𝑐 1 , 𝑐 2 )) is a link key candidate if: (i) 𝐿(𝑘 1 ) ≠ ∅, (
ii) there does not exist another link key expression

𝑘 2 = (𝐸𝑞 2 , 𝐼 𝑛 2 , (𝑐 1 , 𝑐 2 )) over 𝐷 1 and 𝐷 2 such that 𝐸𝑞 1 ⊂ 𝐸𝑞 2 , 𝐼 𝑛 1 ⊂ 𝐼 𝑛 2 , and 𝐿(𝑘 1 ) = 𝐿(𝑘 2 ).
For example, consider the expressions 𝑘 1 and 𝑘 2 :

(i)

𝑘 1 = ({(𝑝 1 , 𝑞 1 )}, {(𝑝 1 , 𝑞 1 ), (𝑝 2 , 𝑞 2 )}, (𝑐 1 , 𝑐 2 )), (ii) 𝑘 2 = ({(𝑝 1 , 𝑞 1 )}, {(𝑝 1 , 𝑞 1 )}, (𝑐 1 , 𝑐 2 )). The related link sets are 𝐿(𝑘 1 ) = 𝐿(𝑘 2 ) = {(𝑎 3 , 𝑏 3 )}.
Then 𝑘 1 and 𝑘 2 are both link key expressions but only 𝑘 1 is a link key candidate as it is maximal on the link set {(𝑎 3 , 𝑏 3 )} while 𝑘 2 is not.

The set of link key expressions is denoted by lke, the set of link key candidates by lkc, and we have that lkc ⊆ lke. The definition of link key candidates is based on the idea of maximality which involves a certain form of closure. This gave rise to a number of papers studying the potential relations existing between Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]) and the discovery of link keys [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF][START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF]. Following the same line, we make precise in the next section two ways of discovering link key candidates based on two extensions of FCA, pattern structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF][START_REF] Kaytoue | Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis[END_REF] and partition pattern structures [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF].

From Link Keys to Non Redundant Link Keys

Discovering Link Keys with Pattern Structures

In this section we shortly recall how pattern structures can be used in the discovery of link keys (details can be read in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF][START_REF] Abbas | Sandwich: An Algorithm for Discovering Relevant Link Keys in an LKPS Concept Lattice[END_REF]). For the sake of simplicity and readability, we rely on a motivating example. Then we show how "Partition Pattern Structures" [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF][START_REF] Baixeries | Characterizing Approximate-Matching Dependencies in Formal Concept Analysis with Pattern Structures[END_REF] allow to discover the so-called "non-redundant link key candidates" denoted as nrlkc.

Example 2. Let us consider the pattern structure lkps = (𝐺, (𝐸, ⊓), 𝛿) displayed in Table 1. All details for building lkps and the associated pattern concept lattice are given in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF]. In the rows ("PS objects"), 𝐺 includes pairs of related instances, i.e., (𝑎 𝑖 , 𝑏 𝑗 ) with 𝑎 𝑖 ∈ 𝐼 (𝑐 1 ) and 𝑏 𝑗 ∈ 𝐼 (𝑐 2 ), which correspond to the objects of lkps. The set of potential descriptions (𝐸, ⊓) includes all possible pairs of properties preceded either by ∀ or ∃. For the sake of simplicity, the ⊓ operator corresponds here to set intersection. The mapping 𝛿 relates a pair of instances (𝑎, 𝑏) ∈ 𝐼 (𝑐 1 ) × 𝐼 (𝑐 2 ) to a description as follows: (i) 𝛿(𝑎, 𝑏) includes ∀(𝑝, 𝑞) whenever 𝑝(𝑎) = 𝑞(𝑏) and 𝑝(𝑎) ≠ ∅, (ii) 𝛿(𝑎, 𝑏) includes ∃(𝑝, 𝑞) whenever 𝑝(𝑎) ∩ 𝑞(𝑏) ≠ ∅. Actually, such descriptions correspond to link key expressions w.r.t. the pairs of classes (𝑐 1 , 𝑐 2 ). In this work, we only consider the pair of classes 𝑐 1 and 𝑐 2 , while dealing with several pairs of classes is explained in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF].

Based on Fig. 1, the description of 𝛿(𝑎 1 , 𝑏 1 ) is given by

{∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )} because 𝑝 1 (𝑎 1 ) ∩ 𝑞 1 (𝑏 1 ) ≠ ∅ and 𝑝 2 (𝑎 1 ) ∩ 𝑞 2 (𝑏 1 ) ≠ ∅, while 𝛿(𝑎 2 , 𝑏 1 ) = {∃(𝑝 1 , 𝑞 1 )} because 𝑝 1 (𝑎 2 ) ∩ 𝑞 1 (𝑏 1 ) ≠ ∅.
Then, 𝛿(𝑎 1 , 𝑏 1 ) ⊓ 𝛿(𝑎 2 , 𝑏 1 ) = {∃(𝑝 1 , 𝑞 1 )} and thus 𝛿(𝑎 2 , 𝑏 1 ) ⊑ 𝛿(𝑎 1 , 𝑏 1 ). This can be read in the pattern concept lattice displayed in Fig. 2 where the pattern concept 𝑝𝑐 5 is subsumed by the pattern concept 𝑝𝑐 4 , i.e., the intent {∃(𝑝 1 , 𝑞 1 )} of 𝑝𝑐 4 is included in the intent {∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )} of 𝑝𝑐 5 , while the extent {(𝑎 1 , 𝑏 1 ), (𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} of 𝑝𝑐 5 is included in the extent of 𝑝𝑐 4 which is {(𝑎 1 , 𝑏 1 ), (𝑎 2 , 𝑏 1 ), (𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )}.

In this way, the set of all pattern concepts is organized within the pattern concept lattice in Fig. 2. Moreover, all link key candidates are lying in the intents of the pattern concepts.

Discovering Non Redundant Link Keys with Partition Pattern Structures

Motivation: sameAs is an Equivalence Relation.

Having a careful look at Fig. 2, one can verify that more compact link keys could be designed. For example, in the extent of 𝑝𝑐 3 , {(𝑎 1 , 𝑏 1 ), (𝑎 1 , 𝑏 2 ), (𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )}, the three first pairs have a non empty intersection when considered in a particular order, i.e., 𝑎 1 is shared by {(𝑎 1 , 𝑏 1 ), (𝑎 1 , 𝑏 2 )} and 𝑏 2 is shared by {(𝑎 1 , 𝑏 2 ), (𝑎 2 , 𝑏 2 )}. Actually there exists a potential owl:sameAs -or simply sameAsrelation between the elements in such pairs. Being an equivalence relation, sameAs generates an equivalence class. Hence, we can "merge" some of these pairs in such an equivalence class. For example (𝑎 1 , 𝑏 1 ) and (𝑎 1 , 𝑏 2 ) can be merged, i.e., a 1 sameAs b 1 and a 1 sameAs b 2 yield b 1 sameAs b 2 (symmetry and transitivity of sameAs). Moreover (𝑎 1 , 𝑏 2 ) and (𝑎 2 , 𝑏 2 ) can be merged because a 1 sameAs b 2 and a 2 sameAs b 2 yield a 1 sameAs a 2 . Finally, from a 1 sameAs a 2 and a 1 sameAs b 1 it comes a 2 sameAs b 1 . Then a 1 , a 2 , b 1 , b 2 , are in the same equivalence class w.r.t. sameAs.

Two important facts should be noticed: (i) the link a 2 sameAs b 1 , absent in 𝑝𝑐 3 but present in 𝑝𝑐 4 , is inferred from the extent of 𝑝𝑐 3 thanks to the properties of sameAs while in the same way a 1 sameAs b 2 could be inferred in 𝑝𝑐 4 , (ii) the equivalence class {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 )} which can be built in 𝑝𝑐 3 and as well in 𝑝𝑐 4 , allows us to merge the link keys in 𝑝𝑐 3 and 𝑝𝑐 4 because they have now the "same extent". Relying on this observation, we define an equivalence relation over the extents of pattern concepts as follows.

Let us consider two RDF datasets 𝐷 1 and 𝐷 2 , a link key 𝑘, two classes 𝑐 1 and 𝑐 2 , and the set of instances 𝐼 = 𝐼 (𝑐 1 ) ∪ 𝐼 (𝑐 2 ). Given 𝑥 0 and 𝑥 𝑛 ∈ 𝐼, there exists a chain of sameAs relations between 𝑥 0 and 𝑥 𝑛 iff there exists a sequence of elements 𝑥 1 , 𝑥 2 , … , 𝑥 𝑛-1 such that x 0 sameAs x 1 , x 1 sameAs x 2 , … , x n-1 sameAs x n holds, where the symmetry of sameAs may be used. Then, we define a relation between 𝑥 0 and 𝑥 𝑛 in 𝐼 w.r.t. the link key 𝑘, denoted as 𝑥 0 ≃ 𝑘 𝑥 𝑛 , iff there exists a chain of sameAs relations between 𝑥 0 and 𝑥 𝑛 . It can be checked that ≃ 𝑘 is an equivalence relation as sameAs itself is an equivalence relation. For example, 𝐸𝑥𝑡(𝑝𝑐 3 )/≃ ∃(𝑝 2 ,𝑞 2 ) = {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} where 𝐸𝑥𝑡(𝑝𝑐 3 ) denotes the extent of 𝑝𝑐 3 . In the same way, 𝐸𝑥𝑡(𝑝𝑐 4 )/≃ ∃(𝑝 1 ,𝑞 1 ) = {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )}. Then the two link keys ∃(𝑝 1 , 𝑞 1 ) and ∃(𝑝 2 , 𝑞 2 ) can be "identified" or "merged" because they have the same equivalence classes.

As a consequence, one may obtain more comparable sets of linked elements and thus minimize the number of possible link key candidates. Moreover, it can be noticed that an equivalence class determines a partition within the set of instances under study (singletons if any are omitted here).

The design of a PPS for "Non Redundant Link Keys".

Hereafter, one main objective is to build a specific pattern structure where concepts are related to unique equivalence classes and yield "non redundant link key candidates" denoted as nrlkc. Here "non redundant" means any two elements in nrlkc are associated with different equivalence classes. In addition, an equivalence class corresponds to a partition of the set of instances. Accordingly, we define a "partition pattern structure" (pps) based on descriptions which are partitions and used to discover non redundant link key candidates. Indeed, in such a pps, objects in the rows correspond to pairs of properties and descriptions correspond to partitions. An example of pps is proposed in [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF] where pps are introduced for mining functional dependencies.

Accordingly, we define a partition pattern structure over classes 𝑐 1 and 𝑐 2 as a triple (lkc, (𝑃𝑎𝑟𝑡(𝐼 ), ⊓ 𝑝𝑎𝑟𝑡 ), 𝛿) such as:

• lkc is the set of all link key candidates w.r.t. classes 𝑐 1 and 𝑐 2 which are given by a pattern concept lattice (as displayed in Fig. 2).

pps objects (𝑘 𝑖 )

Descriptions (partitions, 𝛿(𝑘 𝑖 )) 𝑘 1 = {∃(𝑝 4 , 𝑞 4 ), ∀(𝑝 4 , 𝑞 4 )} {(𝑎 4 , 𝑏 5 ), (𝑎 5 , 𝑏 4 )} 𝑘 2 = {∃(𝑝 3 , 𝑞 3 ), ∀(𝑝 3 , 𝑞 3 )} {(𝑎 4 , 𝑏 4 ), (𝑎 5 , 𝑏 5 )} 𝑘 3 = {∃(𝑝 2 , 𝑞 2 )} {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} 𝑘 4 = {∃(𝑝 1 , 𝑞 1 )} {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} 𝑘 5 = {∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )} {(𝑎 1 , 𝑏 1 ), (𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} 𝑘 6 = {∀(𝑝 1 , 𝑞 1 ), ∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )} {(𝑎 3 , 𝑏 3 )}

Table 2

The partition pattern structure related to the pattern structure in Table 1 over the classes 𝑐 1 and 𝑐 2 in datasets 𝐷 1 and 𝐷 2 .

• (𝑃𝑎𝑟𝑡(𝐼 ), ⊓ 𝑝𝑎𝑟𝑡 ) is the set of potential descriptions or partitions and ⊓ 𝑝𝑎𝑟𝑡 is the "meet" of two partitions. • 𝛿 maps a link key candidate 𝑘 to the partition 𝐼 / ≃ 𝑘 , which is the quotient set of 𝐼 w.r.t. ≃ 𝑘 .

As it can be seen in Table 2, pps objects are the link key candidates already computed and lying in the intents of the pattern concept lattice. This means that link key candidates will compose pps-concept extents, while partitions involving elements are declared in the descriptions and thus will compose pps-concept intents. Moreover, partitions reduced to a singleton are omitted in the descriptions of the pps objects.

Let us examine a concrete example of pps based on the pattern structure given in Table 1. For 𝑝𝑐 3 , we have 𝐸𝑥𝑡(𝑝𝑐 3 ) = {(𝑎 1 , 𝑏 1 ), (𝑎 1 , 𝑏 2 ), (𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} and 𝐼 𝑛𝑡(𝑝𝑐 3 ) = {∃(𝑝 2 , 𝑞 2 )}. The related partition, 𝐸𝑥𝑡(𝑝𝑐 3 )/≃ ∃(𝑝 2 ,𝑞 2 ) = {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )}, where singletons are omitted, is associated with row 𝑘 3 ({∃(𝑝 2 , 𝑞 2 )}) in Table 2 . In the same way, considering 𝑝𝑐 4 and {∃(𝑝 1 , 𝑞 1 )}, 𝐸𝑥𝑡(𝑝𝑐 4 )/≃ ∃(𝑝 1 ,𝑞 1 ) is associated with row 𝑘 4 ({∃(𝑝 1 , 𝑞 1 )}) in Table 2. Moreover, 𝐸𝑥𝑡(𝑝𝑐 4 )/≃ ∃(𝑝 1 ,𝑞 1 ) = {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} and is equal to 𝐸𝑥𝑡(𝑝𝑐 3 )/≃ ∃(𝑝 2 ,𝑞 2 ) . As already observed, 𝑘 3 and 𝑘 4 are inducing the same partition and can be "merged". The other pps objects, namely 𝑘 1 , 𝑘 2 , 𝑘 5 , and 𝑘 6 , are obtained from the corresponding pattern concepts in Fig. 2 in the same way. Finally, the pps over classes 𝑐 1 and 𝑐 2 related to the datasets 𝐷 1 and 𝐷 2 is displayed in Table 2.

The meet -or similarity-operation used to compare the rows in the pps corresponds to the meet of two partitions 𝑝𝑎𝑟𝑡 1 and 𝑝𝑎𝑟𝑡 2 over 𝐼 and is denoted by 𝑝𝑎𝑟𝑡 1 ⊓ 𝑝𝑎𝑟𝑡 𝑝𝑎𝑟𝑡 2 . This meet operation is classically defined as the intersection of the respective equivalence classes, also known as the "coarsest common refinement of the two partitions" (see [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF]). For example the meet 𝛿(𝑘 4 ) ⊓ 𝑝𝑎𝑟𝑡 𝛿(𝑘 5 ) is given by {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} ⊓ 𝑝𝑎𝑟𝑡 {(𝑎 1 , 𝑏 1 ), (𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )} which yields the partition {(𝑎 1 , 𝑏 1 ), (𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )}. In particular, this means that 𝛿(𝑘 4 ) ⊓ 𝛿(𝑘 5 ) = 𝛿(𝑘 5 ) and thus that 𝛿(𝑘 5 ) ⊑ 𝛿(𝑘 4 ).

Based on this meet operation, the pps concept lattice is constructed and shown in Fig. 3. The extent of a pps concept includes the 𝐸𝑞 and the 𝐼 𝑛 parts of a link key candidate (𝐸𝑞, 𝐼 𝑛, (𝑐 1 , 𝑐 2 )) in lkc. For example, the intent of 𝑝𝑝𝑠𝑐 6 is {(𝑎 3 , 𝑏 3 )} and its extent is 𝑘 6 , i.e., {∀(𝑝 1 , 𝑞 1 ), ∃(𝑝 1 , 𝑞 1 ), ∃(𝑝 2 , 𝑞 2 )}. As all elements in the extents of the pps concept lattice, 𝑘 6 is an element of nrlkc, i.e., a non redundant link key candidate. Moreover, 𝑘 6 corresponds to a closed set and thus verifies maximality, and it is non redundant w.r.t. the partition in the associated intent, i.e., no other link key candidate induces the same partition.

Discussion: From LKC to NRLKC.

We now discuss what is gained in relying on pattern structures and then on partition pattern structures. Actually, the discovery of link key candidates (lkc) is based on the construction of the pattern concept lattice. Then the construction of the pps concept lattice yielding the non redundant link key candidates should be considered as a "refinement" where equivalent link key candidates, i.e., link key candidates inducing the same partition, are merged. For example, both concepts 𝑝𝑐 3 and 𝑝𝑐 4 in Fig. 2 are merged into a single concept 𝑝𝑝𝑠𝑐 34 in Fig. 3. The resulting pps concept lattice is of smaller size and more concise as link key candidates in the concept extents are non redundant.

The relations existing between lkc and nrlkc can be characterized as follows. By construction, nrlkc ⊆ lkc as the discovery of non redundant link keys is based on lkc, i.e., the link key candidates lying in the intents of concepts in the pattern concept lattice. Then, the candidates which have the same equivalence classes w.r.t. the sameAs relation are merged to produce the non redundant link key candidates in nrlkc. Thus, it comes that nrlkc ⊆ lkc and that |nrlkc | ≤ |lkc | (where |X| denotes the cardinality of set X). In other words, a non redundant link key candidate is always a link key candidate while the converse is not true.

The definition of nrlkc allows us to introduce a new quality measure for evaluating and validating non redundant link key candidates. In the next section we make precise this new quality measure and we discuss the benefits related to the discovery of non redundant link key candidates.

Quality Measures for Non Redundant Link Key Candidates

Not all link key candidates are eligible to be final link keys. Some candidates can be too general or related to noise in the data and thus they may generate owl:sameAs links which are not correct or have a bad quality. For example the link key candidate ({}, {(country,country)}, (Person,Human)) states that two individuals (subjects) sharing the same country represent the same person, and this is obviously not true. The candidate ({}, {(name,title)}, (Person,Book)) may be discovered by chance and will generate non correct links as well.

An ideal link key candidate should be "correct" and "complete", and specific "quality measures" are defined for assessing these properties. In a supervised setting, when a set of reference links is available, the correctness of a link key candidate is measured thanks to "precision" and the completeness thanks to "recall". In an unsupervised setting as this is the case here, the measures of "coverage" and "discriminability" are defined over the set of links directly generated by a link key candidate [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF]. The global quality of a link key candidate is then estimated thanks to the harmonic mean of these two measures.

The coverage of a set 𝐿 of links over 𝑐 1 and

𝑐 2 is 𝑐𝑜𝑣(𝐿, 𝑐 1 , 𝑐 2 ) = |𝜋 1 (𝐿) ∪ 𝜋 2 (𝐿)| |𝐼 (𝑐 1 ) ∪ 𝐼 (𝑐 2 )| where 𝜋 1 (𝐿) = {𝑎|(𝑎, 𝑏) ∈ 𝐿} and 𝜋 2 (𝐿) = {𝑏|(𝑎, 𝑏) ∈ 𝐿}.
The

discriminability of 𝐿 is 𝑑𝑖𝑠(𝐿) = 𝑚𝑖𝑛(|𝜋 1 (𝐿)|, |𝜋 2 (𝐿)|) |𝐿| .
Link Coverage and discriminability evaluate how close a set of links is to a total, respectively bijective, mapping. Coverage is maximum when all instances of the considered classes are linked to at least another instance, while discriminability is maximum when instances are linked to at most one instance.

In the present setting, we are interested in the "redundancy" of link key candidates, and we would like to evaluate the quality of "non redundant" candidates. A link key candidate 𝑘 is said to be "redundant" in 𝐻 ⊆ lkc if there exists another link key candidate ℎ ∈ 𝐻 such that 𝐼 /≃ 𝑘 = 𝐼 /≃ ℎ , i.e., 𝑘 generates the same partition as ℎ. This is the case in the running example for the link key candidates 𝑘 3 and 𝑘 4 . One main consequence of detecting redundancy is to reduce the number of candidates by merging candidates inducing the same partition. Then, since ≃ 𝑘 3 and ≃ 𝑘 4 induce the same partition, 𝑘 3 and 𝑘 4 are merged into a non redundant link key candidate 𝑘 34 = {𝑘 3 , 𝑘 4 } interpreted as "𝑘 3 or 𝑘 4 ".

Accordingly, we introduce the new quality measure 𝑝𝑆𝑖𝑧𝑒(𝑘) that is compliant with the semantics of sameAs and defined w. The normalized measure 𝑛𝑝𝑆𝑖𝑧𝑒(𝑘) evaluates how close are 𝑐 1 and 𝑐 2 w.r.t. ≃ 𝑘 , and is maximal when all instances are linked. However, this is not always satisfactory, especially when the cardinalities of the two classes significantly differ (i.e., classes are not balanced). Then, it is more accurate to maximize the measure as soon as all instances of one class are linked as follows: 𝑠𝑠𝑝𝑐(𝑘) = 𝑝𝑆𝑖𝑧𝑒(𝑘)/𝑚𝑖𝑛(|𝐼 (𝑐 1 )/≃ 𝑘 |, |𝐼 (𝑐 2 )/≃ 𝑘 |) (also known as the "Szymkiewicz-Simpson partition coefficient"). For example, 𝑠𝑠𝑝𝑐(𝑘 3 ) = 2/4 with: 𝑠𝑠𝑝𝑐(𝑘 3 ) = |{(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )}|/𝑚𝑖𝑛(|{(𝑎 1 , 𝑎 2 ), 𝑎 3 , 𝑎 4 , 𝑎 5 }|, |{(𝑏 1 , 𝑏 2 ), 𝑏 3 , 𝑏 4 , 𝑏 5 }|).

Experiments

Datasets and experimental settings

We run experiments on DB-Yago datasets provided in [START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF]. These datasets are used by the approaches to which we compare our results in the last series of experiments. They have been rewritten into Terse RDF Triple Language (Turtle) which is a syntax for expressing RDF data [START_REF] Beckett | RDF 1.1 Turtle, W3C Recommendation, W3C[END_REF]. They are derived from DBpedia and Yago and organized into nine tasks. One particular task consists in finding links between instances of a class in DBpedia and instances of a class in Yago, e.g., db:Actor and yago:Actor. A set of reference links (i.e., owl:sameAs links) denoted by 𝐿 𝑟𝑒𝑓 is provided for each task. The statistics of DB-Yago datasets are given in Table 3.

Experiments were run on a MacBook Pro 2018 with Intel Core i7-8850H@2,6 GHz, 16GB of RAM. The link key candidates are provided by a tool called Linkex2 in which we have implemented the lkps algorithm i.e. the link key discovery algorithm based on pattern structures proposed in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF]. A basic text normalization consisting in removing diacritics, tokenizing and sorting the resulting bag of tokens is performed.

Redundancy of Link Key Candidates is not so Significant

In Table 3, column |lkc| represents the number of link key candidates discovered by lkps algorithm while column |nrlkc| represents the number of non redundant link key candidates. In most of the tasks, we can observe that |nrlkc| is equal to |lkc|, except for the tasks Actor and Film where |nrlkc| is lower than |lkc| by 1% and by 5% respectively. This means that, in general, link key candidates produce different partitions and only a few are redundant. By contrast, if redundancy does not significantly reduce the number of link key candidates, it gives a good idea of the compactness of partitions related to link key candidates.

Nevertheless, even if redundancy is not so significant, we decided to compare the quality of the resulting sets of candidates measured with 𝑝𝑆𝑖𝑧𝑒 and the results of competitors, namely keys and conditional keys as they are studied in [START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF].

Non Redundant Candidates, Classical Keys and Conditional Keys

The 𝑝𝑆𝑖𝑧𝑒 measure is used to evaluate and select the best link key candidates, -in this experiment the link key candidate ranked first-in every task listed in Table 3. Then, we compare recall, precision, and F-measure of the links generated by the best link key candidates selected by 𝑝𝑆𝑖𝑧𝑒 against interlinking approaches providing classical keys and conditional keys as reported in [START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF].

In Figure 4 we can observe that: (i) recall of link keys is significantly better than recall of classical and conditional keys, (ii) precision of classical and conditional keys is slightly better than precision of link keys in most of the tasks, (iii) F-measure is much higher for selected link key candidates than for classical and conditional keys.

Link keys have a better recall because they are more flexible than classical keys, i.e., a link key is not necessarily a pair of keys and an instance of class 𝑐 1 may be linked to many instances of class 𝑐 2 .

For summarizing, it can be concluded that considering the best link key candidates selected by 𝑝𝑆𝑖𝑧𝑒 will ensure a higher interlinking quality compared to classical and conditional keys. We also observe that the best link key according to discriminability and coverage is the same that the best non redundant link key selected thanks to 𝑝𝑆𝑖𝑧𝑒. Actually, the Actor dataset makes an exception: the link key candidate selected with 𝑝𝑆𝑖𝑧𝑒 obtains an F-measure of 0.95 contrasting the score of 0.34 obtained with coverage and discriminability. In addition, contrasting key-based approaches, link key discovery does not require any prior knowledge such as property or class alignments. [START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF] and link keys. Actually a recall of 0 stands for a very small recall close to 0.

Synthesis and Conclusion

This paper introduces a formalization of link key discovery based on partition pattern structures (pps). This approach allows to discover the set nrlkc of link key candidates which are not redundant w.r.t. the owl:sameAs equivalence relation, while still being correct and complete. In addition, new appropriate quality measures are proposed.

Practically, we observe in experiments that the redundancy of link key candidates in public datasets is rather rare. Nevertheless, the experiments and the associated results show that link key based on pps obtain better F-measure values than two other key-based approaches to data-interlinking.

Among the perspectives, a first one is to consolidate the theory and practice of link key discovery based on pps introduced and detailed in this paper. A second and very important direction of investigation is related to the discovery of "fuzzy link keys". We make the hypothesis that the redundancy of link key candidates is rather rare because we are using the crisp equality operator when we are building the link key candidates. Instead, in considering the discovery of link key candidates as depending on a similarity relation, i.e., reflexive and symmetric -also called a tolerance relation-rather than on an equality, then we could propose a formalization of fuzzy link key candidates in the spirit of approximate-matching dependencies as they are studied in [START_REF] Baixeries | Characterizing Approximate-Matching Dependencies in Formal Concept Analysis with Pattern Structures[END_REF]. We could also expect much more differences between crisp and fuzzy link key candidates. In addition, a reduction of the size of the concept lattice related to nrlkc could also be investigated thanks to similarities between partitions.

Figure 3 :

 3 Figure 3: The pps concept lattice over the partition pattern structure and the pattern concept lattice given in Fig. 2.

  r.t. the partition associated with the equivalence relation ≃ 𝑘 : 𝑝𝑆𝑖𝑧𝑒(𝑘) = | {𝑥 ∈ 𝐼 /≃ 𝑘 | |𝑥| > 1} | where 𝐼 = 𝐼 (𝑐 1 ) ∪ 𝐼 (𝑐 2 ) and 𝐼 /≃ 𝑘 is the quotient set of 𝐼 w.r.t. ≃ 𝑘 . For example, 𝑝𝑆𝑖𝑧𝑒(𝑘 3 ) = 𝑝𝑆𝑖𝑧𝑒(𝑘 4 ) = |{(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 )}| = 2. The lower bound of 𝑝𝑆𝑖𝑧𝑒(𝑘) is 1 since 𝑘 generates at least one link. The upper bound is 𝑚𝑖𝑛(|𝐼 (𝑐 1 )|, |𝐼 (𝑐 2 )|) and this is achieved when 𝑘 determines a 1-1 mapping. Moreover, pSize can be normalized into 𝑛𝑝𝑆𝑖𝑧𝑒(𝑘) = 𝑝𝑆𝑖𝑧𝑒(𝑘)/|𝐼 / ≃ 𝑘 |. Then 𝑛𝑝𝑆𝑖𝑧𝑒(𝑘 3 ) = 2/6 as 𝐼 / ≃ 𝑘 3 = {(𝑎 1 , 𝑏 1 , 𝑎 2 , 𝑏 2 ), (𝑎 3 , 𝑏 3 ), 𝑎 4 , 𝑏 4 , 𝑎 5 , 𝑏 5 }, where this time singletons are counted.

Figure 4 :

 4 Figure 4:Interlinking performances of classical keys, conditional keys as given in[START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF] and link keys. Actually a recall of 0 stands for a very small recall close to 0.

Table 3

 3 DB-Yago datasets statistics, where |triples| denotes the number of triples in each dataset, |subjects| the number of instances, and |properties| the number of properties.

	Interlinking task datasets	|triples|	|subjects| |properties|	|lkc|	|nrlkc| time
	Actor	db:Actor yago:Actor	94 606 1 029 580	5 807 108 415	16 16	2 198	2 177	56s
	Album	db:Album yago:Album	594 144 762 238	85 002 136 848	5 5	44	44	28s
	Book	db:Book yago:Book	247 372 185 032	29 846 41 849	7 7	82	82	39s
	Film	db:Film yago:Film	1 369 600 1 067 084	82 099 123 822	9 9	18 718 17 643 34m
	Mountain	db:Mountain yago:Mountain	135 442 233 562	16 397 32 874	5 5	39	39	5m
	Museum	db:Museum yago:Museum	15 940 163 342	1 826 21 050	7 7	48	48	9s
	Organization	db:Organization yago:Organization 4 410 854 4 487 205	183 665 430 071	17 17	1 425	1 425	57m
	Scientist	db:Scientist yago:Scientist	128 360 671 266	18 409 92 828	10 18	862	862	2m
	University	db:University yago:University	241 838 263 624	10 352 23 334	9 9	213	213	56s

Linkex is available online at https://gitlab.inria.fr/moex/linkex.