Pierre Monnin
email: pierre.monnin@loria.fr

Miguel Couceiro
email: miguel.couceiro@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Adrien Coulet
email: adrien.coulet@loria.fr

Knowledge-Based Matching of n-ary Tuples

Keywords: Alignment, Matching, n-ary Tuple, Order, Ontology

An increasing number of data and knowledge sources are accessible by human and software agents in the expanding Semantic Web. Sources may differ in granularity or completeness, and thus be complementary. Consequently, they should be reconciled in order to unlock the full potential of their conjoint knowledge. In particular, units should be matched within and across sources, and their level of relatedness should be classified into equivalent, more specific, or similar. This task is challenging since knowledge units can be heterogeneously represented in sources (e.g., in terms of vocabularies). In this paper, we focus on matching n-ary tuples in a knowledge base with a rule-based methodology. To alleviate heterogeneity issues, we rely on domain knowledge expressed by ontologies. We tested our method on the biomedical domain of pharmacogenomics by searching alignments among 50,435 n-ary tuples from four different real-world sources. Results highlight noteworthy agreements and particularities within and across sources.

Introduction

In the Semantic Web [START_REF] Berners-Lee | The Semantic Web[END_REF], data or knowledge sources often describe similar units but may differ in quality, completeness, granularity, and vocabularies. Unlocking the full potential of the knowledge that these sources conjointly express requires matching equivalent, more specific, or similar knowledge units within and across sources. This matching process results in alignments that enable the reconciliation of these sources, i.e., the harmonization of their content [START_REF] Euzenat | Ontology Matching, Second Edition[END_REF]. Such a reconciliation then provides a consolidated view of a domain that is useful in many applications, e.g., in knowledge fusion and fact-checking.

Here, we illustrate the interest of such a matching process to reconcile knowledge within the biomedical domain of pharmacogenomics (PGx), which studies the influence of genetic factors on drug response phenotypes. PGx knowledge originates from distinct sources: reference databases such as PharmGKB, biomedical literature, or the mining of Electronic Health Records of hospitals.

Knowledge represented in these sources may differ in levels of validation, completeness, and granularity. Consequently, reconciling these sources would provide a consolidated view on the knowledge of this domain, certainly beneficial in precision medicine, which aims at tailoring drug treatments to patients to reduce adverse effects and maximize drug efficacy [START_REF] Caudle | Incorporation of pharmacogenomics into routine clinical practice: the clinical pharmacogenetics implementation consortium (cpic) guideline development process[END_REF][START_REF] Coulet | Mining electronic health records to validate knowledge in pharmacogenomics[END_REF]. PGx knowledge consists of n-ary relationships, here represented as tuples relating sets of drugs, sets of genomic variations, and sets of phenotypes. Such an n-ary tuple states that a patient being treated with the specified sets of drugs, while having the specified genomic variations will be more likely to experience the given phenotypes, e.g., adverse effects. For example, Figure 1 depicts the tuple pgt 1, which states that patients treated with warfarin may experience cardiovascular diseases because of variations in the CYP2C9 gene. If a source contained the same tuple but with the genetic factor unknown, then it should be identified as less specific than pgt 1. Conversely, if a source contained the same tuple but with myocardial infarction as phenotype, then it should be identified as more specific than pgt 1. Motivated by this application, we propose a general and mathematically wellfounded methodology to match n-ary tuples. Precisely, given two n-ary tuples, we aim at deciding on their relatedness among five levels such as being equivalent or more specific. We suppose that such tuples are represented within a knowledge base that is expressed using Semantic Web standards. In such standards, only binary predicates exist, which requires the reification of n-ary tuples to represent them: tuples are individualized and linked to their components by predicates (see Figure 1) [START_REF] Noy | Defining N-ary Relations on the Semantic Web[END_REF]. In these knowledge bases, entities can also be associated with ontologies, i.e., formal representations of a domain [START_REF] Gruber | A translation approach to portable ontology specifications[END_REF]. Ontologies consist of classes and predicates, partially ordered by the subsumption relation, denoted by . This relation states that a class (respectively a predicate) is more specific than another.

The process of matching n-ary tuples appears naturally in the scope of ontology matching [START_REF] Euzenat | Ontology Matching, Second Edition[END_REF], i.e., finding equivalences or subsumptions between classes, predicates, or instances of two ontologies. Here, we match individuals representing reified n-ary tuples, which is somewhat related to instance matching and the extraction of linkkeys [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF]. However, we allow ourselves to state that a tuple is more specific than another, which is unusual in instance matching but com-mon when matching classes or predicates with systems such as PARIS [START_REF] Suchanek | PARIS: probabilistic alignment of relations, instances, and schema[END_REF] and AMIE [START_REF] Galárraga | Mining rules to align knowledge bases[END_REF]. Besides, to the best of our knowledge, works available in the literature do not deal with the complex task of matching n-ary tuples with potentially unknown arguments formed by sets of individuals. See Appendix A for further details.

In our approach, we assume that the tuples to match have the same arity, the same indices for their arguments, and that they are reified with the same predicates and classes. Arguments are formed by sets of individuals (no literal values) and may be unknown. This matching task thus reduces to comparing each argument of the tuples and aggregating these comparisons to establish their level of relatedness. We achieve this process by defining five general rules, designed to satisfy some desired properties such as transitivity and symmetry. To tackle the heterogeneity in the representation of tuples, we enrich this structure-based comparison with domain knowledge, e.g., the hierarchy of ontology classes and links between individuals.

This paper is organized as follows. In Section 2, we formalize the problem of matching n-ary tuples. To tackle it, we propose two preorders in Section 3 to compare sets of individuals by considering domain knowledge: links between individuals, instantiations, and subsumptions. These preorders are used in Section 4 to define matching rules that establish the level of relatedness between two n-ary tuples. These rules are applied to PGx knowledge in Section 5. We discuss our results in Section 6 and present some directions of future work in Section 7. Appendices are available online (https://arxiv.org/abs/2002.08103).

Problem Setting

We aim at matching n-ary tuples represented within a knowledge base K, i.e., we aim at determining the relatedness level of two tuples t 1 and t 2 (e.g., whether they are equivalent, more specific, or similar). K is represented in the formalism of Description Logics (DL) [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] and thus consists of a TBox and an ABox.

Precisely, we consider a set T of n-ary tuples to match. This set is formed by tuples whose matching makes sense in a given application. For example, in our use-case, T consists of all PGx tuples from the considered sources. All tuples in T have the same arity n, and their arguments are sets of individuals of K. Such a tuple t can be formally represented as t = (π 1 (t), . . . , π n (t)), where π i : T → 2 ∆ is a mapping that associates each tuple t to its i-th argument π i (t), which is a set of individuals included in the domain of interpretation ∆. The index set is the same for all tuples in T . Tuples come from potentially noisy sources and some arguments may be missing. As K verifies the Open World Assumption, such arguments that are not explicitly specified as empty, can only be considered unknown and they are set to ∆ to express the fact that all individuals may apply. To illustrate, pgt 1 in Figure 1 could be seen as a ternary tuple pgt 1 = ({warfarin} , {CYP2C9} , {cardiovascular diseases}), where arguments respectively represent the sets of involved drugs, genetic factors, and phenotypes.

In view of our formalism, matching two n-ary tuples t 1 and t 2 comes down to comparing their arguments π i (t 1 ) and π i (t 2 ) for each i ∈ {1, . . . , n}. For instance, if π i (t 1 ) = π i (t 2 ) for all i, then t 1 and t 2 are representing the same knowledge unit, highlighting an agreement between their sources. In the next section, we propose other tests between arguments that are based on domain knowledge.

Ontology-Based Preorders

As previously illustrated, the matching of two n-ary tuples t 1 and t 2 relies on the comparison of each of their arguments π i (t 1 ) and π i (t 2 ), which are sets of individuals. Such a comparison can be achieved by testing their inclusion or equality. Thus, if π i (t 1 ) ⊆ π i (t 2 ), then π i (t 1 ) can be considered as more specific than π i (t 2 ). It is noteworthy that testing inclusion or equality implicitly considers owl:sameAs links that indicate identical individuals. For example, the comparison of {e 1 } with {e 2 } while knowing that owl:sameAs(e 1 , e 2 ) results in an equality. However, additional domain knowledge can be considered to help tackle the heterogeneous representation of tuples. For instance, some individuals can be part of others. Individuals may also instantiate different ontological classes, which are themselves comparable through subsumption. To consider this domain knowledge in the matching process, we propose two preorders, i.e., reflexive and transitive binary relations.

Preorder p Based on Links Between Individuals

Several links may associate individuals in π i (t j ) with other individuals in K. Some links involve a transitive and reflexive predicate (i.e., a preorder). Then, for each such predicate p, we define a preorder p parameterized by p as follows 1 :

π i (t 1 ) p π i (t 2 ) ⇔ ∀e 1 ∈ π i (t 1 ), ∃e 2 ∈ π i (t 2 ), K |= p(e 1 , e 2 ) (1)
Note that, from the reflexivity of p and the use of quantifiers ∀ and ∃, π i (t 1 ) ⊆ π i (t 2 ) implies π i (t 1 ) p π i (t 2 ). The equivalence relation ∼ p associated with p is defined as usual by:

π i (t 1 ) ∼ p π i (t 2 ) ⇔ π i (t 1 ) p π i (t 2 ) and π i (t 2 ) p π i (t 1 ) (2)

Preorder O Based on Instantiation and Subsumption

The Note that ci(O, e) may be empty. We explicitly exclude from ci(O, e) since K may be incomplete. Indeed, individuals may lack instantiations of specific classes but instantiate by default. Thus, is excluded to prevent O from inadequately considering these individuals more general than individuals instantiating classes other than 2 .

Given Given an ontology O, we define the preorder O based on set inclusion and subsumption as follows 4 :

C = {C 1 , C 2 , . . . , C k } ⊆ classes(O),
π i (t 1 ) O π i (t 2 ) ⇔ ∀e 1 ∈ π i (t 1 ), e 1 ∈ π i (t 2 ) (3a) msci(O, e 1 ) = ∅ ∧ ∀C 1 ∈ msci(O, e 1 ), ∃e 2 ∈ π i (t 2 ), ∃C 2 ∈ msci(O, e 2 ), C 1 C 2 (3b) (3)
Clearly, if π i (t 1 ) is more specific than π i (t 2 ) and e 1 ∈ π i (t 1 ), then (3a) e 1 ∈ π i (t 2 ), or (3b) all the most specific classes instantiated by e 1 are subsumed by at least one of the most specific classes instantiated by individuals in π i (t 2 ). Thus individuals in π i (t 2 ) can be seen as "more general" than those in π i (t 1 ). As before, O induces the equivalence relation ∼ O defined by:

π i (t 1 ) ∼ O π i (t 2 ) ⇔ π i (t 1 ) O π i (t 2 ) and π i (t 2 ) O π i (t 1 ) (4)
The preorder O can be seen as parameterized by the ontology O, allowing to consider different parts of the TBox of K for each argument π i (t j ), if needed.

Using Preorders to Define Matching Rules

Let t 1 , t 2 ∈ T be two n-ary tuples to match. We assume that each argument i ∈ {1, . . . , n} is endowed with a preorder i ∈ ⊆, p , O that enables the comparison of π i (t 1 ) and π i (t 2 ). We can define rules that aggregate such comparisons for all i ∈ {1, . . . , n} and establish the relatedness level of t 1 and t 2 . Hence, our matching approach comes down to applying these rules to every ordered pair (t 1 , t 2 ) of n-ary tuples from T .

Here, we propose the following five relatedness levels: =, ∼, , ≶, and ∝, from the strongest to the weakest. Accordingly, we propose five matching rules of the form B ⇒ H, where B expresses the conditions of the rule, testing equalities, equivalences, or inequalities between arguments of t 1 and t 2 . Classically, these conditions can be combined using conjunctions or disjunctions, respectively denoted by ∧ and ∨. If B holds, H expresses the relatedness between t 1 and t 2 to add to K . Rules are applied from Rule 1 to Rule 5. Once conditions in B hold for a rule, H is added to K and the following rules are discarded, meaning that at most one relatedness level is added to K for each pair of tuples. When no rule can be applied, t 1 and t 2 are considered incomparable and nothing is added to K. The first four rules are the following:

Rule 1. ∀i ∈ {1, . . . , n} , π i (t 1 ) = π i (t 2 ) ⇒ t 1 = t 2 Rule 2. ∀i ∈ {1, . . . , n} , π i (t 1 ) ∼ i π i (t 2 ) ⇒ t 1 ∼ t 2 Rule 3. ∀i ∈ {1, . . . , n} , π i (t 1 ) i π i (t 2 ) ⇒ t 1 t 2 Rule 4. ∀i ∈ {1, . . . , n} , [ (π i (t 1 ) = π i (t 2 )) ∨ (π i (t 2 ) = ∆ ∧ π i (t 1 ) i π i (t 2 )) ∨ (π i (t 1 ) = ∆ ∧ π i (t 2 ) i π i (t 1 )) ] ⇒ t 1 ≶ t 2
Rule 1 states that t 1 and t 2 are identical (=) whenever t 1 and t 2 coincide on each argument. Rule 2 states that t 1 and t 2 are equivalent (∼) whenever each argument i ∈ {1, . . . , n} of t 1 is equivalent to the same argument of t 2 . Rule 3 states that t 1 is more specific than t 2 ( ) whenever each argument i ∈ {1, . . . , n} of t 1 is more specific than the same argument of t 2 w.r.t. i . Rule 4 states that t 1 and t 2 have comparable arguments (≶) whenever they have the same specified arguments (i.e., different from ∆), and these arguments are comparable w.r.t.

i . Rules 1 to 3 satisfy the transitivity property. Additionally, Rules 1, 2, and 4 satisfy the symmetry property.

In Rules 1 to 4, comparisons are made argument-wise. However, other relatedness cases may require to aggregate over arguments. For example, we may want to compare all individuals involved in two tuples, regardless of their arguments. Alternatively, we may want to consider two tuples as weakly related if their arguments have a specified proportion of comparable individuals. To this aim, we propose Rule 5. Let I = {I 1 , . . . , I m } be a partition of {1, . . . , n}, defined by the user at the beginning of the matching process. We define the aggregated argument I k of t j as the union of all specified π i (t j ) (i.e., different from ∆) for i ∈ I k . Formally,

π I k (t j ) = i∈I k πi(tj ) =∆ π i (t j ).
We assume that each aggregated argument I k ∈ I is endowed with a preorder I k ∈ ⊆, p , O . We denote by SSD(π

I k (t 1 ), π I k (t 2 )) the semantic set difference between π I k (t 1 ) and π I k (t 2 ), i.e., SSD(π I k (t 1 ), π I k (t 2 )) = {e 1 | e 1 ∈ π I k (t 1 ) and {e 1 } I k π I k (t 2 )} .
Intuitively, it is the set of elements in π I k (t 1 ) preventing it from being more specific than π I k (t 2 ) w.r.t. I k . We define the operator ∝ I k as follows:

π I k (t 1 ) ∝ I k π I k (t 2 ) = 1 if π I k (t 1 ) I k π I k (t 2 ) or π I k (t 2 ) I k π I k (t 1 ) 1 - |SSD(π I k (t1),π I k (t2)) ∪ SSD(π I k (t2),π I k (t1))| |π I k (t1) ∪ π I k (t2)| otherwise
This operator returns a number measuring the similarity between π I k (t 1 ) and π I k (t 2 ). This number is equal to 1 if the two aggregated arguments are comparable. Otherwise, it is equal to 1 minus the proportion of incomparable elements. We denote by I =∆ (t 1 , t 2 ) = {I k | I k ∈ I and π I k (t 1 ) = ∆ and π I k (t 2 ) = ∆} the set of aggregated arguments that are specified for both t 1 and t 2 (i.e., different from ∆). Then, Rule 5 is defined as follows:

Rule 5. Let I = {I 1 , . . . , I m } be a partition of {1, . . . , n}, and let γ =∆ , γ S , and γ C be three parameters, all fixed at the beginning of the matching process.

|I =∆ (t 1 , t 2 )| ≥ γ =∆ ∀I k ∈ I =∆ (t 1 , t 2 ), π I k (t 1 ) ∝ I k π I k (t 2 ) ≥ γ S ∨ I k ∈I =∆ (t1,t2) 1 (π I k (t 1 ) ∝ I k π I k (t 2 ) = 1) ≥ γ C ⇒ t 1 ∝ t 2
Rule 5 is applicable if at least γ =∆ aggregated arguments are specified for both t 1 and t 2 . Then, t 1 and t 2 are weakly related (∝) whenever all these specified aggregated arguments have a similarity of at least γ S or when at least γ C of them are comparable. Notice that ∝ is symmetric.

Application to Pharmacogenomic Knowledge

Our methodology was motivated by the problem of matching pharmacogenomic (PGx) tuples. Accordingly, we tested this methodology on PGxLOD5 [START_REF] Monnin | PGxO and PGxLOD: a reconciliation of pharmacogenomic knowledge of various provenances, enabling further comparison[END_REF], a knowledge base represented in the ALHI Description Logic [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. In PGxLOD, 50,435 PGx tuples were integrated from four different sources: (i) 3,650 tuples from structured data of PharmGKB, (ii) 10,240 tuples from textual portions of PharmGKB called clinical annotations, (iii) 36,535 tuples from biomedical literature, and (iv) 10 tuples from results found in EHR studies. We obtained the matching results summarized in Table 1 and discussed in Section 6. Details about formalization, code and parameters are given in Appendix G.

Discussion

In Table 1, we observe only a few inter-source links, which may be caused by missing mappings between the vocabularies used in sources. Indeed, our matching process requires these mappings to compare individuals represented with different vocabularies. This result underlines the relevance of enriching the knowledge base with ontology-to-ontology mappings. We also notice that Rule 5 generates more links than the other rules, which emphasizes the importance of weaker relatedness levels to align sources and overcome their heterogeneity. Some results were expected and therefore seem to validate our approach. For example, some tuples from the literature appear more general than those of PharmGKB (with 15 and 42 skos:broadMatch links). These links are a foreseen consequence of the completion process of PharmGKB. Indeed, curators achieve this completion after a literature review, inevitably leading to tuples more specific or equivalent to the ones in reviewed articles. Interestingly, our methodology could ease such a review by pointing out articles describing similar tuples. Clinical annotations of PharmGKB are in several cases more specific than structured data (9,325 skos:broadMatch links). This is also expected as structured data are a broadlevel summary of more complex phenotypes detailed in clinical annotations. Regarding our method, using rules is somehow off the current machine learning trend [START_REF] Alam | Reconciling event-based knowledge through RDF2VEC[END_REF][START_REF] Nickel | A review of relational machine learning for knowledge graphs: From multi-relational link prediction to automated knowledge graph construction[END_REF][START_REF] Ristoski | Rdf2vec: RDF graph embeddings for data mining[END_REF]. However, writing simple and well-founded rules constitutes a valid first step before applying machine learning approaches. Indeed, such explicit rules enable generating a "silver" standard for matching, which may be useful to either train or evaluate supervised approaches. Rules are readable and may thus be analyzed and confirmed by domain experts, and provide a basis of explanation for the matching results. Additionally, our rules are simple enough to be generally true and useful in other domains. By relying on instantiated classes and links between individuals, we illustrate how domain knowledge and reasoning mechanisms can serve a structure-based matching. In future works, conditions under which preorders p and O could be merged into one unique preorder deserve a deeper study. See Appendix H for further discussion.

Conclusion

In this paper, we proposed a rule-based approach to establish the relatedness level of n-ary tuples among five proposed levels. It relies on rules and preorders that leverage domain knowledge and reasoning capabilities. We applied our methodology to the real-world use case of matching pharmacogenomic relationships, and obtained insightful results. In the future, we intend to compare and integrate our purely symbolic approach with ML methodologies.

A Details about Related Works

In ontology matching [START_REF] Euzenat | Ontology Matching, Second Edition[END_REF], existing works use different features to suggest alignments. For example, some methods rely on the syntax of units label (e.g., string matching). However, labels may not always be available. Structure-based techniques can alleviate such limitations. They rely either on the internal structure of a unit (i.e., predicates used to link a unit to literals) or the relational structure of a unit (i.e., its links with other units). Two examples of frequently considered relational structures are the hierarchy of classes and partOf links in an ontology. As our matching approach compares tuples based on the individuals involved in their arguments and their associated domain knowledge, it relies on the relational structure of reified tuples.

Linkkeys are defined by Atencia et al. [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF] as a structure-based method to align individuals. A linkkey consists of a pair of classes and a set of pairs of properties from two ontologies. Instances of these classes that share common values for all properties in the linkkey are regarded as identical. Alternatively, PARIS is a holistic method proposed by Suchanek et al. [START_REF] Suchanek | PARIS: probabilistic alignment of relations, instances, and schema[END_REF] to align individuals, classes, and predicates. In this framework, alignments for each type of unit fertilize the others: they are performed repeatedly until convergence. Rules in PARIS rely on the internal and relational structures of units and the functionality of predicates. Similarly, Galarraga et al. [START_REF] Galárraga | Mining rules to align knowledge bases[END_REF] mine specific rules to align ontologies, using the AMIE system. This system relies on the Partial Completeness Assumption, which is also built upon the functionality of predicates.

B Proof that p is a preorder

Proof. From the fact that p is reflexive, it immediately follows that p is reflexive. Indeed, for every E ⊆ ∆, E p E since for every e ∈ E, p(e, e).

To prove that p is a preorder, it remains to show that p is transitive. Consider E 1 , E 2 , E 3 ⊆ ∆ such that:

E 1 p E 2 and E 2 p E 3 .
In other words,

∀e 1 ∈ E 1 , ∃e 2 ∈ E 2 , K |= p(e 1 , e 2 ) and ∀e 2 ∈ E 2 , ∃e 3 ∈ E 3 , K |= p(e 2 , e 3 )
. By the transitivity of p, we then have that

∀e 1 ∈ E 1 , ∃e 3 ∈ E 3 , K |= p(e 1 , e 3 ),
i.e., E 1 p E 3 . This shows that p is transitive, and the proof is complete.

C Example of Use of p

Example 1. partOf is transitive and reflexive. Thus, this predicate is a suitable candidate for the p preorder. Consider three individuals e 1 , e 2 , e 3 such that K |= partOf(e 3 , e 1 ). Then it follows that:

-{e 1 } partOf {e 1 , e 2 }, from set inclusion.

-{e 3 , e 2 } partOf {e 1 , e 2 }.

-{e 3 } partOf {e 1 , e 2 }.

-{e 3 , e 1 } ∼ partOf {e 1 }. As e 3 is a part of e 1 , having both e 3 and e 1 in the same set can be seen as a redundancy. Such a case may arise in K due to source heterogeneity. This redundancy is adequately identified by this equivalence result.

D Details about Excluding in ci(O, e)

Example 2. Consider two PGx tuples pgt 1 and pgt 2 that involve the same drug and genetic factor. Regarding the phenotype, pgt 1 is linked with an individual representing headache that does not instantiate the class Headache in O (e.g., MeSH) but instantiates by default. pgt 2 is linked with an individual pain that instantiates P ain, with Headache P ain. Intuitively, the knowledge expressed by pgt 1 is more specific than pgt 2 . However, by considering instantiated classes and knowing that P ain , O would inadequately conclude that pgt 1 is more general than pgt 2 . By excluding from ci(O, e), the tuples are incomparable, which avoids this unwanted behavior.

E Proof that O is a preorder

Recall that, for every

E 1 , E 2 ⊆ ∆, E 1 O E 2 ⇔ ∀e 1 ∈ E 1 , e 1 ∈ E 2 (5a) msci(O, e 1 ) = ∅ ∧ ∀C 1 ∈ msci(O, e 1 ), ∃e 2 ∈ E 2 , ∃C 2 ∈ msci(O, e 2 ), C 1 C 2 (5b) (5)
Proof. The reflexivity of O follows immediately from (5a). To see that it is also transitive, consider distinct

E 1 , E 2 , E 3 ⊆ ∆ such that E 1 O E 2 and E 2 O E 3 . We need to prove that E 1 O E 3 , that is, ∀e 1 ∈ E 1 , e 1 ∈ E 3 msci(O, e 1 ) = ∅ ∧ ∀C 1 ∈ msci(O, e 1 ), ∃e 3 ∈ E 3 , ∃C 3 ∈ msci(O, e 3 ), C 1 C 3 So let e 1 ∈ E 1 . If e 1 ∈ E 2 , then it follows from E 2 O E 3 that e 1 ∈ E 3 msci(O, e 1 ) = ∅ ∧ ∀C 1 ∈ msci(O, e 1 ), ∃e 3 ∈ E 3 , ∃C 3 ∈ msci(O, e 3 ), C 1 C 3 , (6)
and we are done. Otherwise,

msci(O, e 1 ) = ∅ ∧ ∀C 1 ∈ msci(O, e 1 ), ∃e 2 ∈ E 2 , ∃C 2 ∈ msci(O, e 2 ), C 1 C 2 .
As E 2 O E 3 , we have two possible cases for each e 2 ∈ E 2 :

e 2 ∈ E 3 and for each C 1 ∈ msci(O, e 1 ) we also have:

∃e 3 ∈ E 3 , ∃C 3 ∈ msci(O, e 3 ), C 1 C 3 , or -∃e 3 ∈ E 3 , ∃C 3 ∈ msci(O, e 3 ), C 2 C 3 .
Since the subsumption relation is transitive, C 1 C 3 , and

∃e 3 ∈ E 3 , ∃C 3 ∈ msci(O, e 3 ), C 1 C 3
From these two cases, it follows that for each

e 1 ∈ E 1 such that msci(O, e 1 ) = ∅ ∧ ∀C 1 ∈ msci(O, e 1 ), ∃e 2 ∈ E 2 , ∃C 2 ∈ msci(O, e 2 ), C 1 C 2 , we have that ∃e 3 ∈ E 3 , ∃C 3 ∈ msci(O, e 3 ), C 1 C 3 . (7)
From Equations ( 6) and ( 7), it then follows that:

∀e 1 ∈ E 1 , e 1 ∈ E 3 msci(O, e 1 ) = ∅ ∧ ∀C 1 ∈ msci(O, e 1 ), ∃e 3 ∈ E 3 , ∃C 3 ∈ msci(O, e 3 ), C 1 C 3 , thus showing that E 1 O E 3 .
As the latter holds for every

E 1 , E 2 , E 3 ⊆ ∆, O is transitive. F Examples of Use of O Example 3.

G Application to Pharmacogenomic Knowledge (details)

We experimented our methodology with PGxLOD6 [START_REF] Monnin | PGxO and PGxLOD: a reconciliation of pharmacogenomic knowledge of various provenances, enabling further comparison[END_REF], a PGx knowledge base represented in the ALHI Description Logic [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF].

In PGxLOD, PGx tuples are represented using classes and predicates of the PGxO ontology 7 . PGx tuples are n-ary, and thus, they are reified as instances of the PharmacogenomicRelationship class. All the individuals involved in PGx tuples instantiate the Drug, GeneticFactor, or Phenotype classes. They are linked with reified PGx tuples by predicates qualifying their association to tuples. These predicates are organized in a hierarchy defined by subsumption axioms, such as causes influences isAssociatedWith. It is noteworthy that, in PGxLOD, partOf links indicate that instances of GeneticFactor compose others such instances. For example, a genomic variation may be part of a gene. Similarly, instances of Phenotype may have dependencies, expressed with dependsOn links. These dependencies enable representing complex phenotypes that refer to other phenotypes or drugs. For example warfarin-caused hemorrhage is a phenotype linked with dependsOn to hemorrhage and warfarin. The TBox of PGxLOD contains, alongside PGxO, three other ontologies: individuals representing drugs may instantiate classes from ATC or ChEBI, and individuals representing phenotypes may instantiate classes from MeSH. Table 2 provides global statistics about PGxLOD. To apply the matching rules on PGx tuples, we specified their arguments. Each argument of a tuple is the set of individuals with a specific type (Drug, GeneticFactor, or Phenotype) that are linked with a specific predicate to the tuple. For example, given pgt a PGx tuple, π Phenotype,causes (pgt) contains all the phenotypes caused by pgt. Hence, as there are 3 types of individuals and 38 predicates, PGx tuples have 3 × 38 = 114 arguments. Once arguments of tuples are specified, their associated preorders can be defined. Based on the available data and knowledge in PGxLOD, it makes sense to use the partOf preorder for arguments involving instances of GeneticFactor. Similarly, we use ODrug and OPhenotype as preorders for arguments respectively involving instances of Drug and Phenotype, where O Drug is the concatenation of ATC and ChEBI, and O Phenotype is the MeSH ontology.

Finally, to apply Rule 5, a natural three-way partition of arguments appears based on the three types of involved individuals. Therefore, discarding predicates, we gather all drugs, genetic factors, and phenotypes involved in a tuple in three aggregated arguments. To benefit from dependencies of complex phenotypes, we choose to add them to the aggregated arguments corresponding to their type. For example, in warfarin-caused hemorrhage, hemorrhage is added to the aggregated argument representing phenotypes and warfarin is added to the one representing drugs. We arbitrarily set γ =∆ = 3, γ S = 0.8, and γ C = 2. These values mean that two PGx tuples pgt 1 and pgt 2 will be matched by Rule 5 if their three aggregated arguments are specified (i.e., different from ∆). Additionally, each of the three aggregated arguments of pgt 1 must have at least 80% of comparable individuals with the same aggregated argument of pgt 2 , or at least two aggregated arguments of pgt 1 must be comparable with the same aggregated arguments of pgt 2 .

To illustrate the interest of this formalization as well as reasoning mechanisms from Description Logics, let pgt 1 and pgt 2 be two PGx tuples. pgt 1 causes a phenotype ph 1 and is associated with a phenotype ph 2 , and pgt 2 is associated with both phenotypes. Thus, by applying reasoning mechanisms along the hierarchy of predicates, it follows that: π Phenotype,causes (pgt 1 ) = ph 1 ; π Phenotype,isAssociatedWith (pgt 1 ) = ph 1 , ph 2 π Phenotype,causes (pgt 2 ) = ∆; π Phenotype,isAssociatedWith (pgt 2 ) = ph 1 , ph 2 By definition of OPhenotype , π Phenotype,causes (pgt 1 ) OPhenotype π Phenotype,causes (pgt 2 ) as well as π Phenotype,isAssociatedWith (pgt 1 ) OPhenotype π Phenotype,isAssociatedWith (pgt 2 ). Therefore, by applying Rule 3, pgt 1 is more specific than pgt 2 . This makes sense as the predicate connecting ph 1 with pgt 1 is more specific with than the one used with pgt 2 .

We implemented our matching methodology in C++ with multithreading. Our code is available on GitHub8 . Our program interacts with the knowledge base thanks to SPARQL queries. Previously, we indicated that an unspecified argument of an n-ary tuple is set to ∆. Accordingly, when a SPARQL query returns ∅ for an argument of a tuple, it is interpreted as if it is returning ∆. On PGxLOD, the matching rules led to perform 50,435 2 = 1, 271, 819, 395 comparisons in approximately 54 hours using 4 cores and 15 GB of RAM.

H Discussion (details)

By looking more closely at the results in Table 1, we notice that all owl:sameAs links are intra-source and thus indicate duplicates. This is expected in the case of the literature since several articles could mention the same tuple. The 5 skos:closeMatch links between tuples from structured data and clinical annotations of PharmGKB highlight expected agreements between these two related sources. However, linked tuples are expressed with different individuals instantiating the same ontology classes, preventing their reconciliation with owl:sameAs.

The results of Rule 4 underline that sources may contain tuples with comparable arguments. Source owners can benefit from such results by considering adding a tuple formed by the most specific arguments of the matched tuples. We notice that only Rule 5 generates links between the tuples from EHRs and other sources. As tuples from EHRs are manually represented, there are only a few of them, minimizing the chance of overlap with other sources. Additionally, phenotypes involved in tuples from EHRs are very specific, making their comparison with phenotypes from biomedical literature or PharmGKB difficult.

Regarding our method, we believe our rules are simple and abstract enough to be useful in other domains. Additionally, their readability facilitates their review by experts, for example, to define the arguments and preorders to use in another application domain. Finally, it is noteworthy that the O preorder may result in many equivalences if the ontology O is not granular enough in terms of width and depth. Such equivalences may make sense, depending on the application domain and the ontology. If not, the two other preorders (i.e., ⊆ and p ) could be used. It is for now up to experts to choose the correct preorder for each argument. However, in future works, we could investigate metrics about domain knowledge that may guide their choice.

Fig. 1 .

 1 Fig.1. Representation of a PGx relationship between gene CYP2C9, drug warfarin and phenotype cardiovascular diseases. It can be seen as an n-ary tuple pgt 1 = ({warfarin} , {CYP2C9} , {cardiovascular diseases}). This tuple is reified through the individual pgt 1, connecting its components through the causes predicate.

  second preorder we propose takes into account classes of an ontology O ordered by subsumption and instantiated by individuals in π i (t j ). We denote by classes(O) the set of all classes of O. As it is standard in DL, denotes the largest class in O. Given an individual e, we denote by ci(O, e) the set of classes of O instantiated by e and distinct from , i.e., ci(O, e) = {C ∈ classes(O)\ { } | K |= C(e)} . 1 See Appendix B and Appendix C for the proof and examples.

  we denote by msc(C) the set of the most specific classes of C, i.e., msc(C) = {C ∈ C | D ∈ C, D C} 3 . Similarly, we denote by msci(O, e) the set of the most specific classes of O, except , instantiated by an individual e, i.e., msci(O, e) = msc(ci(O, e)).

Figure 2 Fig. 2 .

 22 Fig. 2. Examples of use cases of the preorder O . Circles represent ontology classes. Solid arrows depict class subsumptions and dashed arrows depict class instantiations by individuals e1, e2, and e3. The light gray color identifies classes in msci(O, e1). The dark gray color identifies classes in msci(O, e2) and msci(O, e3).

Table 1 .

 1 Number of links resulting from each rule. Links are generated between tuples of distinct sources or within the same source. PGKB stands for "PharmGKB", sd for "structured data", and ca for "clinical annotations". As Rules 1, 2, 4, and 5 satisfy symmetry, links from t1 to t2 as well as from t2 to t1 are counted. Similarly, as Rules 1 to 3 satisfy transitivity, transitivity-induced links are counted. Regarding skos:broadMatch links, rows represent origins and columns represent destinations.

			PGKB (sd) PGKB (ca) Literature EHRs
	Links from Rule 1 Encoded by owl:sameAs	PGKB (sd) PGKB (ca) Literature EHRs	166 0 0 0	0 10,134 0 0	0 0 122,646 0	0 0 0 0
	Links from Rule 2 Encoded by skos:closeMatch	PGKB (sd) PGKB (ca) Literature EHRs	0 5 0 0	5 1,366 0 0	0 0 16,692 0	0 0 0 0
	Links from Rule 3 Encoded by skos:broadMatch	PGKB (sd) PGKB (ca) Literature EHRs	87 9,325 0 0	3 605 0 0	15 42 75,138 0	0 0 0 0
	Links from Rule 4 Encoded by skos:relatedMatch	PGKB (sd) PGKB (ca) Literature EHRs	20 0 0 0	0 110 0 0	0 0 18,050 0	0 0 0 0
	Links from Rule 5 Encoded by skos:related	PGKB (sd) 100,596 PGKB (ca) 287,670 Literature 414 EHRs 2	287,670 706,270 1,103 19	414 1,103 1,082,074 15 2 19 15 0

Table 2 .

 2 Statistics about PGxLOD. # denotes "number of". Instances linked by owl:sameAs are counted separately. partOf links are counted without transitivity inference. All PGx tuples were programmatically extracted from their sources, except the ten tuples from EHRs that were manually added as a proof of concept.

	Class	# instances Predicate	# links
	Drug	47,584 partOf	16,697
	GeneticFactor	464,302 dependsOn	23,976
	Phenotype	61,330
	PharmacogenomicRelationship	50,435
	From PharmGKB (structured data)	3,650
	From PharmGKB (clinical annotations)	10,240
	From biomedical literature	36,535
	From EHRs	10

See Appendix D for a detailed example.

D C means that D C and D ≡ C.

See Appendix E and Appendix F for the proof and examples.

https://pgxlod.loria.fr

https://pgxlod.loria.fr

https://pgxo.loria.fr

https://github.com/pmonnin/tcn3r

Supported by the PractiKPharma project, founded by the French National Research Agency (ANR) under Grant ANR15-CE23-0028, by the IDEX "Lorraine Université d'Excellence" (15-IDEX-0004), and by the Snowball Inria Associate Team.