Vincent Ranwez
email: vincent.ranwez@univ-montp2.fr

Sylvie Ranwez
email: sylvie.ranwez@mines-ales.fr

Stefan Janaqi
email: stefan.janaqi@mines-ales.fr

Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs

Keywords: [II. Artificial Intelligence / IV. Knowledge Representation Formalisms and Methods] [II. Discrete Mathematics / II. Graph Theory] Keywords-Sub-ontology extraction, Ontology transformation, Directed acyclic graph, Least common ancestor, Greatest common descendant

Ontologies are successfully used as semantic guides when navigating through the huge and ever increasing quantity of digital documents. Nevertheless, the size of numerous domain ontologies tends to grow beyond the human capacity to grasp information. This growth is problematic for a lot of key applications that require user interactions such as document annotation or ontology modification/evolution. The problem could be partially overcome by providing users with a sub-ontology focused on their current concepts of interest. A sub-ontology restricted to this sole set of concepts is of limited interest since their relationships can generally not be explicit without adding some of their hyponyms and hypernyms. This paper proposes efficient algorithms to identify these additional key concepts based on the closure of two common graph operators: the least common-ancestor and greatest common descendant. The resulting method produces ontology excerpts focused on a set of concepts of interest and is fast enough to be used in interactive environments. As an example, we use the resulting program, called OntoFocus (http://www.ontotoolkit.mines-ales.fr/), to restrict, in few seconds, the large Gene Ontology (~30,000 concepts) to a sub-ontology focused on concepts annotating a gene related to breast cancer.

INTRODUCTION

ith rapid technological progress, the scope of digital data is overwhelming, ranging from real-time data flows to digitalized documents through specialized databases. Many dedicated applications make use of them, and they often become the core of company decision-making processes. However, their number constitutes a bottleneck for human beings striving to get an overall grasp of information and an impediment to high performance computing. Efficient filtering tools are thus needed to provide the user with the right information at the right time.

Wondering about the Semantic Web, Tim Berners Lee imagined an environment where software agents and humans might cooperate using the same information [START_REF] Berners-Lee | The Semantic Web[END_REF]. Its architecture relies on machine readable semantic models (ontologies) as backbones to structure collections of information and sets of rules to conduct reasoning. This architecture was proposed for the Web, but also appears to be efficient for Information Systems (IS) dealing with large amounts of data [START_REF] Abecker | Ontologies for Knowledge Management[END_REF]. Specialized ontologies endow many Web independent applications with a semantic guide while browsing through documents, filtering and retrieving relevant information or analyzing data in a given context.

However, ontologies, especially those shared and accepted as standards in a given domain, tend to grow beyond the human capacity to manage them (browse, visualize, edit, analyze and share.) This growth is problematic for a lot of applications that require user interactions such as document annotation or ontology modification/evolution. A natural solution to help users would be to provide them with a subontology focused on their current concepts of interest. Of course, as mentioned by [START_REF] Wouters | Large scale ontology visualisation using ontology extraction[END_REF], individual concepts or terms may always be found by textual searches within the ontology, but links between concepts are tedious to look for. Moreover, given an initial set of concepts of interest, their relationships can generally not be explicit without adding some hyponyms and hypernyms.

In this paper, given a reference-ontology, a "good" subontology is envisaged as the smallest excerpt containing concepts of interest, additional concepts to specify their interconnections and corresponding relationships. We identified (but were not limited to) three main applications:

• Conception/Extension of ontologies: when designing an ontology, it is often necessary to zoom in on a specific part of it. While modifying an ontology, people may consider a very restricted subset of concepts and analyze them through relationships that interconnect them before adding new concepts or new relations or reorganizing them. • Ontology based information retrieval/filtering: given a set of concepts that annotate a set of documents, having relationships that link them may improve the user's understanding of the annotations.

• Browsing and display of ontologies and related indexations: human cognitive and perceptive limits underline the crucial need for suitable representation tools. Displaying the overall ontology is generally unconceivable and thus some views of it often have to be built. Sub-ontology is a pre-requisite for ontology visualization which is essential to favor user interactions with ontology based systems. Indeed, we agree with [START_REF] Dolan | Using ontology visualization to understand annotations and reason about them[END_REF] that "regardless of the ontology, presenting terms in a graphical context makes the relationships of ontology terms clear, provides context for annotations, and makes the examination of large annotation sets feasible." Some sub-ontology extraction methods have been proposed in the Knowledge Engineering literature. They are discussed in the state of the art presented in section 2. Most of them highlight the importance of the is-a relationship that may be considered as the backbone of the ontology. This kind of relationship can be represented as a directed acyclic graph (dag). Given an initial set of nodes, this paper proposes a definition of relevant nodes using graph operators. Section 3 reviews useful graph definitions and introduces the notion of least common ancestor closure, denoted ܷ closure, to determine the searched subset of relevant concepts. Section 4 presents optimized algorithms to compute this closure. Having grasped the set of relevant concepts, Section 5 details the process for inferring relations among them.

The major contribution of this work is to propose a subontology extraction method that significantly reduces the number of concepts in a very short time (an ontology having thirty thousand concepts may be restricted to a hundred concepts in few seconds on a standard desktop computer). It favors different displays corresponding to different views on the reference ontology. It is thus possible to embed it within interactive applications where domain experts may focus on relevant concepts of their specialized domain. Visualization of the corresponding ontology excerpt enables users to better comprehend the underlying semantics of their concepts of interest. This extraction algorithm was developed in a program called OntoFocus that takes the OWL reference ontology and a list of concepts of interest as input. Written in JA-VA and using the Jena library, this software may be freely used on-line at the address http://www.ontotoolkit.minesales.fr/. An application in the life-science domain is detailed in Section 6. The results are analyzed and discussed and outcomes are presented. Section 7 concludes by recapitulating the approach and discussing its impact.

STATE OF THE ART: DIFFERENT SUB-ONTOLOGY

EXTRACTION APPROACHES

The need for restricted ontologies, particularly in the Life Science domain, is underlined in [START_REF] Kim | Pruning Bio-Ontologies[END_REF] where different approaches are compared and their strengths and weaknesses are analyzed with respect to the restriction objectives. For authors, ontology restriction methods often involve a twostep process: identification of the set of concepts of interest and then the restriction phase. However, they argue that none can be applied universally. In what follows, the subontology extraction context is given and some methods are presented, organized according to three main application contexts: 1) conception of an ontology, 2) reuse of existing ontologies, and 3) visualization. We then consider subontology extraction in the light of graph theory and present related works in this domain.

Pruning and trimming ontologies during their

conception Concerning ontology conception, some studies have been conducted to try to automatically identify conceptual spaces from a corpus analysis using natural language processes [START_REF] Chen | A parallel computing approach to creating engineering concept spaces for semantic retrieval: The Illinois Digital Library Initiative project[END_REF], even during the querying phase [START_REF] Smits | Resource Discovery in a European Spatial Data Infrastructure[END_REF]. A statistical approach is usually used to determine potential concepts based on their frequency in the corpus and relationships among them are created de novo. After having automatically collected and organized concepts from the textual corpus, such approaches often rely on a pruning and trimming phase [START_REF] Navigli | Automatically extending, pruning and trimming general purpose ontologies[END_REF][START_REF] Sabou | Learning web service ontologies: an automatic extraction method and its evaluation[END_REF]. The trimming step proposed in [START_REF] Navigli | Automatically extending, pruning and trimming general purpose ontologies[END_REF] to reduce the built ontology is closely related to sub-ontology extraction. Yet this step is more a way to clean up de novo relationships and remove redundant, useless or too fine-grained potential concepts than a real sub-ontology extraction. One point must be underlined here. Some concepts, identified as belonging to high level ontology or domain ontology, cannot be removed and are always kept in their "sub-ontologies". We do not distinguish such levels in our approach and all nodes are considered in the same manner.

Sub-ontology extraction to favor their recycling

An alternative strategy is to reuse parts of existing ontologies. A Web ontology segmentation was proposed in [START_REF] Seidenberg | Web ontology segmentation: analysis, classification and use[END_REF] to extract customized ontologies, specific to given applications, from large ontologies. Unfortunately, by keeping all ascendants and descendants of concepts of interest, the size of the resulting sub-ontology might be very large. This customized ontology may be used alone or to enrich a project-specific ontology. In this latter context, partial ontologies are also called modules [START_REF] Grau | Mod-ular reuse of ontologies: Theory and practice[END_REF][START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF]. When a project related ontology P is enriched with an external module Q, the safety of this enrichment must be ensured. Indeed, if a common label is used for distinct concepts in the two ontologies, these can lead to some erroneous reasoning. More formally, an enrichment of P, using Q, is said to be safe when it "produces exactly the same logical consequences over the vocabulary of Q as Q alone" [START_REF] Grau | Mod-ular reuse of ontologies: Theory and practice[END_REF][START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF]. This property is not straightforward to check and may result in complex algorithms and high computation times. It should however be noted that safety is only related to ontology merging and not to sub-ontology extraction.

Sub-ontology extraction as visualization aid

Displaying large ontologies is challenging. This problem can be tackled by two complementary approaches: using infor-Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

mation visualization techniques suited for scalability (e.g. treemap, hyperbolic trees, etc.) and/or using a semantic filtering based on sub-ontology extraction. A complete overview of ontology visualization tools is provided in [START_REF] Katifori | Ontology visualization methods -A survey[END_REF].

Most of them only propose functionalities to zoom in on a local part of the ontology hierarchy rather than displaying an explicit and semantic excerpt of it. Solutions to obtain such excerpts are discussed in what follows.

When focusing on a subset of concepts (e.g. those indexing a given document or those over represented in the index of a set of documents) a graphical representation of their hierarchical relationships is very helpful. The most widespread solution is to display concepts that are in this subset plus those that are ancestors of one of them. This straightforward solution is (manually) used in many publications (e.g. [START_REF] Dolan | Using ontology visualization to understand annotations and reason about them[END_REF][START_REF] Dolan | Using Ontology Visualization to Coordinate Cross-species Functional Annotation for Human Disease Genes[END_REF]) as well as within Web-based tools 1 .

An Australian team proposed a solution for what they call the "user-driven automatic extraction of valid sub-ontology" [START_REF] Bhatt | Onto-Move: A knowledge based framework for semantic requirement profiling and resource acquisition[END_REF][START_REF] Bhatt | A distributed approach to sub-ontology extraction[END_REF]. The need for sub-ontology extraction is clearly highlighted in [START_REF] Bhatt | A distributed approach to sub-ontology extraction[END_REF], where the authors point out the fact that an application focuses only on particular aspects of the whole ontology. For the authors, sub-ontologies are valid independent ontologies, known as materialized ontologies that are specifically extracted to meet certain needs -what they call tailoring. However, they concede that tailoring is time consuming and thus developed a distributed approach in order to be able to deal with ontologies embedding thousands of concepts. This work was supplemented in [START_REF] Wouters | Large scale ontology visualisation using ontology extraction[END_REF], where the authors state that traditional visualization techniques fail to achieve semantic representativeness and user friendliness, and propose a methodology for extracting a sub-ontology before applying visualization techniques. Therefore they reinterpret the notion of views that is used in the database domain to transform data upon request according to given specifications. For these authors, the resulting sub-ontology should be valid and complete itself [START_REF] Flahive | A service oriented architecture for extracting and extending sub-ontologies in the semantic grid[END_REF]. In the same line, we think that the term "sub-ontology" implies that the restricted set of concepts and embedded relations constitute a valid ontology.

For us, sub-ontology extraction is definitely devoted to assisting end-users and enhancing their understanding of the interconnection between concepts. Visualization thus constitutes the main goal of this work.

From concept of interest selection to subontology extraction

As previously mentioned, sub-ontology extraction starts with the selection of concepts of interest. "In large ontologies, which may contain thousands of elements, […] the selection method is not very efficient, because it requires human intervention and there are too many concepts involved in the process" [START_REF] Kim | Pruning Bio-Ontologies[END_REF]. In cases where documents are annotated with concepts of the domain ontology, the selection of concepts of interest according to a subset of documents can be automated. One can simply keep any concepts 1 http://www.informatics.jax.org/GOgraphs/OrthoDisease/ that annotate at least one document of interest. This may result in keeping numerous concepts. Several studies have been carried out to detect concepts that annotate more of these documents than expected by randomly sampling the same number of documents. Such tools are especially useful and widespread in life science applications [START_REF] Bauer | Ontologizer 2.0 -a multifunctional tool for GO term enrichment analysis and data exploration[END_REF][START_REF] Grossmann | Improved detection of overrepresentation of Gene-Ontology annotations with parentchild analysis[END_REF].

Pruning methods are evaluated in [START_REF] Kim | Pruning Bio-Ontologies[END_REF] according to: their degree of automation, the kind of relationships they consider and the ratio between the number of concepts that they keep and those they trim. Whereas methods presented in [START_REF] Kim | Pruning Bio-Ontologies[END_REF] only remove a few concepts from the original ontology, our algorithm considerably reduces the size of the ontology in a very short time. This leads to a core sub-ontology focused on end-users' concepts of interest that meet their needs.

Given a reference ontology and a set of concepts of interest, few methods allow the extraction of a corresponding sub-ontology meeting both objectives: finding a concise yet informative restriction (i.e. that can be grasped by a human operator), and being fast enough to be used in an interactive environment. As mentioned in section 2.3, the main subontology extraction study that was designed according to these objectives was conducted by the Australian team of Carlo Wouters, Tharam Dillon, Wenny Rahayu and associates. Even though their objectives for constructing views are very similar to ours, the two solutions differ with respect to various points. In their proposal [START_REF] Wouters | Large scale ontology visualisation using ontology extraction[END_REF], concepts of the materialized ontology may be a compression (rename) of concepts of interest. They are obtained via optimization schemes, a logical grouping of rules, and actions of the user. Conversely, for us, each concept that appears in the subontology is directly derived from the reference ontology. Moreover, they considered the possibility of extending each sub-ontology independently [START_REF] Flahive | A service oriented architecture for extracting and extending sub-ontologies in the semantic grid[END_REF], whereas we propose a rapid solution to allow the creation of sub-ontologies on request. The latter may thus be considered as instantaneous views on the large ontology, which is the sole ontology that can be used for automated reasoning (e.g. during information retrieval) and that can evolve. This avoids redundancy and related maintenance difficulties. Moreover, while their method needs to be parallelized for handling large ontologies, ours can filter such ontologies in few seconds on a standard desktop computer.

Having the set of concepts of interest (or signature), our main objective is to identify hyponyms and hypernyms that must be added to clarify relationships among the remaining concepts and thus to obtain an explicit sub-ontology.

This problem was addressed (for hypernyms) by Nebot and Berlanga [START_REF] Nebot | Efficient retrieval of ontology fragments using an interval labeling scheme[END_REF], who propose three main extraction strategies. The first two (SCA -Signature Common Ancestors, ASA -All Signature Ancestors), as acknowledged by the authors, can result in an excessive amount of irrelevant nodes in the output sub-ontology. The third one (ASA-ST -All Signature Ancsestors Spanning Tree) tries to improve this situation, but its output depends on the arbitrary choice of a tree spanning the initial ontology. See section 5.1 for an illustrative example.

Our solution provides many more concise sub-ontologies

Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

than SCA and ASA strategies. Moreover, since it is based on a well defined lca-closure operator, its output does not depend on the arbitrary choice of a spanning tree.

A new graph based sub-ontology approach

In the following, sub-ontology extraction is tackled by using an algorithmic approach that is based on is-a relationships and two common operators: least common ancestor (lca) and greatest common descendant (gcd). When the reference-ontology is represented by a Direct Acyclic Graph (dag), the "explicit" sub-ontology will be a subgraph that is closed for the above mentioned operators.

Before detailing our solution, some choices have to be justified. As underlined in the introduction, the is-a relationship is of particular interest. It is often considered as the backbone of the ontology -perhaps because it is commonly used by people to organize things around them. This relationship is central to ontologies as it is the sole one that appears in formal ontology definitions ( [START_REF] Necib | Ontology based query processing in database management systems[END_REF] or [START_REF] Guarino | What is an Ontology?[END_REF]). Moreover, previous works have been proposed to use the hierarchical domain structure to compute similarity [START_REF] Ganesan | Exploiting hierarchical domain structure to compute similarity[END_REF] or in information retrieval systems [START_REF] Baziz | An Information Retrieval Driven by Ontology: from Query to Document Expansion[END_REF][START_REF] Khan | Retrieval effectiveness of an ontology-based model for information selection[END_REF]. Within these contexts, adding other relations just adds noise. Therefore we decided to focus on the dag representing is-a relationships to identify relevant concepts. Other relationships are considered and added during post-processing, as described in section 5.3.

Basic filtering, which involves keeping ancestors of concepts of interest, may preserve too many concepts since some concepts may have numerous ancestors (e.g. Aspirin has 152 ancestors in UMLS2003AA). The choice of lca operator to identify relevant concepts is motivated and validated through end-user evaluations in [START_REF] Tao | A tool for abstracting relevant classes of concepts: The common ancestry summarizer[END_REF], with the aim of assisting experts who have to choose an ancestor concept to summarize a group of concepts for adjusting indexation granularity. The resulting tool displays the whole ancestor hierarchy but emphasizes lca concepts to assist experts in making choices. Our approach goes a step further and filters the ancestor hierarchy to display only ancestral concepts that are least common ancestors of some other preserved concepts. Moreover, unlike existing solutions focused on ancestors, we also preserve greatest common descendent concepts. These two key improvements considerably reduce the number of displayed concepts while preserving enough of them to render relationships among initial concepts. As a counterpart, a straightforward algorithm based on numerous lca computations results in high computation times.

Some works have been proposed to efficiently find the lca of concepts [START_REF] Liu | Identifying meaningful return information for XML keyword search[END_REF][START_REF] Xu | Efficient keyword search for smallest LCAs in XML databases[END_REF]. However, they often calculate lca only for a pair of concepts (and not for a set of them) and do not search for the possibly numerous lcas but only for one of them. The algorithm introduced in [START_REF] Xu | Efficient keyword search for smallest LCAs in XML databases[END_REF] for multilabeled trees (i.e. where a single term can label more than one node) can easily be adapted for dag; but this solution cannot be used for large ontologies due to its time complexity. The next section introduces an efficient algorithm to identify relevant concepts based on lca. The key idea is to exploit the dag structure so as to compute in a single graph, traversal lca of any pair of concepts within the extracted subontology.

In the following section, based on the experience of the graph community, a solution is developed to build subontologies.

LEAST COMMON ANCESTOR OPERATOR AND ITS CLOSURE

Preliminary definitions

Restricting a tree to a subset of nodes is a well defined operation used in various computer science fields. Yet its extension to dags is not straightforward. This section introduces some basic graph notations and provides two equivalent formal definitions of lca closure in dags. Before going any further, and to avoid misunderstandings, it is important to note that in most of the graph literature dag edges are oriented from parents toward children, whereas in the ontology literature edges of the is-a dag are instead oriented from children toward parents in order to stress the is-a semantic. Though the following results hold for any dag, we clearly worked in the ontology framework and thus adopt the corresponding edge orientation convention (from children towards parents).

The following definitions are provided to make the paper self-contained. For further definitions on graphs see [START_REF] Bondy | Graph Theory with Appplications[END_REF]. The is-a relationship graph is a dag ܩ ൌ ሺܸ, ܧሻ. The indegree ݀ ீ ି ሺݒሻ (outdegree ݀ ீ ା ሺݒሻ) of a vertex ݒ is the number of edges with head ݒ (tail .)ݒ When ܩ contains a directed ,ݒ( -)ݑpath, the vertex ݑ is said to be an ancestor of ݒ and the vertex ݒ is a descendant of .ݑ For a non-empty subset ܹ of ܸ, the subgraph of ܩ whose vertex set is ܹ and whose arc set is the set of arcs of ܩ that have both ends in ܹ is called the subgraph of ܩ induced by ܹ and is denoted ܩሾܹሿ.

Using these notations, it is now possible to define the least common ancestor operator that is extensively used in our sub-ontology extraction approach. Given a vertex ݒ of the dag ܩ ൌ ሺܸ, ܧሻ, the set ܣ ீ ሺݒሻ denotes the subset of ancestors of ݒ in .ܩ The generalization of this definition to a set ܵ ك ܸ of vertices is straightforward, i.e. ܣ ீ ሺܵሻ ൌ ځ ܣ ீ ሺݒሻ ௩אௌ . For simplicity, we will omit index ܩ from the notations whenever there is no ambiguity. This definition generalizes the widely known definition of least common ancestor (see [START_REF] Bender | Finding least common ancestors in directed acyclic graphs[END_REF][START_REF] Yuster | All-pairs disjoint paths from a common ancestor in O (n(omega)) time[END_REF][START_REF] Harel | Fast Algorithms for Finding Nearest Common Ancestors[END_REF][START_REF] Schieber | On Finding Lowest Common Ancestors -Simplification and Parallelization[END_REF]) for a couple of vertices, i.e. ݈ܿܽሺሼ,ݔ ݕሽሻ ൌ ݈ܿܽሺ,ݔ ݕሻ. It follows immediately from Definition 3.1.1 that ݔ ൌ ݈ܿܽሺ,ݔ ݕሻ if there is a directed ,ݕ( -)ݔpath. By extension, we define ݈ܿܽሺ,ݔ ݔሻ ൌ ݔ for all .ݔ Note that, unless the dag ܩ is a tree, the existence of a pair of nodes ,ݔ ݕ א ܵ such that ݈ܿܽሺ,ݔ ݕሻ ൌ ݈ܿܽሺܵሻ is not guaranteed. For instance, in the example presented in Fig. 1, lcaሺሼC1, C2, C3ሽሻ ൌ ሼA1, A2ሽ while lcaሺC1, C2ሻ ൌ ሼB1, 2ܣሽ, lcaሺC1, C3ሻ ൌ B2 and lcaሺC2, C3ሻ ൌ ሼA1, B3ሽ.

Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

operator and two equivalent definitions of its closure in a dag

Closure operators are widely used in mathematics, especially in geometry. The best known example concerns convexity in a Euclidian space where a convex polygon can be obtained by giving a finite set of points and the segment operation ,ݔሺݏ ݕሻ (that could correspond to ݈ܿܽሺ,ݔ ݕሻ operation).

In the previous section, we provided an intuitive and natural definition of the least common ancestors of a set of vertices denoted ݈ܿܽሺܵሻ. Yet, when considering a set of vertices ܵ, every least common ancestor of a pair of vertices of ܵ is a key vertex to gain insight into relationships between vertices of ܵ. We thus now introduce a new operator that makes use of the ݈ܿܽሺ,ݔ ݕሻ operator and generalizes it to a well defined closure operator.

Definition 3.2.1. Let ܵ be a subset of vertices of .ܩ The ܷ operator on ܵ is defined as:

ܷ ሺܵሻ ൌ ڂ ݈ܿܽሺ,ݔ ݕሻ ௫,௬אௌ (1)
It follows from this definition that ܵ ⊆ ܷ ሺܵሻ and that the ܷ operator is monotonic, i.e.:

ܣ ك ܤ ֜ ܷ ሺܣሻ ك ܷ ሺܤሻ. In some cases, having only ܷ ሺܵሻ and/or ݈ܿܽሺܵሻ is not enough to understand all relationships among concepts of ܵ. This case is depicted in Fig. 3, where concept ܣ is helpful for understanding 1ܥ and 2ܥ relationships but is neither included in ܷ ሺܵሻ nor in ݈ܿܽሺܵሻ. Concept ܣ is of interest since ܣ is the lca of 1ܤ and ,2ܤ which in turn are lcas of two concepts of ܵ. This leads us to the following definition of the ܷ closure of ܵ. This definition provides a simple iterative algorithm to compute ܷ closure. The time complexity of this algorithm is related to the closure index. In the simple case where ܩ is a tree, the closure index cannot be greater than 1. The following lemma shows that this is no longer true in the general case.

Lemma 3.2.1. For a dag ܩ ൌ ሺܸ, ܧሻ and a set ܵ ك ܸ, the number of iterations needed to obtain ܵ ҧ is ܱሺ|ܸ|ሻ.

Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

Proof. It is clear that ܵ increases with at least one vertex at each iteration, hence proving that ܿ ሺ|ܸ| െ |ܵ|). On the other hand, as shown by the example below, c can be as large as ሺ|ܸ| െ |ܵ|ሻ/2. It follows that the number of iterations needed to obtain ܵ ҧ is ܱሺ|ܸ|ሻ. There is an alternative (descending) way to define ܷ closure in a dag ܩ ൌ ሺܸ, ܧሻ. For this, let the family of ܷ closed sets containing ܵ be denoted by:

ࣦሺܵሻ ൌ ሼܮ ⊆ ܸ | ܵ ⊆ ܮ ܽ݊݀ ܮ ൌ ܷ ሺܮሻሽ (2)
Lemma 3.2.2. The family ࣦሺܵሻ is non-empty and closed for the intersection, i.e. ,ܯ ܰ א ࣦሺܵሻ ֜ ܯ ת ܰ א ࣦሺܵሻ.

Proof. ࣦሺܵሻ is non-empty since V obviously belongs to ࣦሺܵሻ. Let us now prove that ,ܯ ܰ א ࣦሺܵሻ ֜ ܯ ת ܰ א ࣦሺܵሻ. We denote ݏ ൌ |ܵ | and estimate the number ܰ of calls of the ݈ܿܽሺ,ݔ ݕሻ-operator. In Algorithm 1, ܰ depends on the closure index ܿ that determines how many times the while loop is done. As this number ܿ ൌ ܱሺ|ܸ|ሻ (Lemma 3.2.1), the number ܰ of calls of the ݈ܿܽሺ,ݔ ݕሻ-operator for this algorithm is:

• ܵ ⊆ ܯ ת ܰ. As ܵ ⊆ ܯ and ܵ ⊆ ܰ, ܵ ⊆ ܯ ת ܰ. • ܯ ת ܰ ൌ ܷ ሺܯ ת ܰሻ. o ܯ ת ܰ ⊆ ܷ ሺܯ ת ܰሻ,
ܰ ሺ݈ܽ݃1ሻ ൌ ∑ ݏ ଶ ୀ ൌ ∑ ܱሺ|ܸ| ଶ ሻ ைሺ||ሻ ୀ ൌ ܱሺ|ܸ| ଷ ሻ (
Result: ܵ ҧ the ܷ closure of ܵ. ܵ ՚ ܵ; ܵ ௪ ՚ ܵ; do ܵ ௧ ՚ ܵ ; for each ሺ,ݔ ݕሻ א ܵ ൈ ܵ ܵ ௧ ՚ ܵ ௧  ݈ܿܽሺ,ݔ ݕሻ; end ܵ ௪ ՚ ܵ ௧ െ ܵ ; ܵ ՚ ܵ ௧ ; while ܵ ௪ ്  return ܵ Algorithm 2. Slightly improved Ulca-closure algorithm.
This high complexity is due to the fact that some ݈ܿܽሺ,ݔ ݕሻ are computed several times, for instance those of S are computed ܿ times. This is obviously useless, and Algorithm 2 computes ݈ܿܽሺ,ݔ ݕሻ only when needed, i.e. only if x and/or y Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

are/is in ܵ ௪ . Yet the lca should be computed for any couple of vertices of ܵ ҧ . It follows that:

ܰ ሺ݈ܽ݃2ሻ ൌ ∑ 1 ௫,௬אௌ ҧ ൌ ܱሺ|ܸ| ଶ ሻ (4)
The time complexity of this second algorithm is ܱሺ|ܸ| ଶ ሻ times the complexity of the ݈ܿܽሺ,ݔ ݕሻ subroutine.

Several optimized algorithms are available to retrieve one vertex ݒ א ݈ܿܽሺ,ݔ ݕሻ. We stress the word "one" because, in our approach we need all the vertices of ݈ܿܽሺ,ݔ ݕሻ. Most optimized solutions to retrieve one vertex ݒ א ݈ܿܽሺ,ݔ ݕሻ rely on the shortest path algorithm. After preprocessing, done in ሺ|ܸ| ఠ ሻ with ߱ ൌ 2.688, a representative lca can be obtained in constant time for any couple of nodes (see [START_REF] Bender | Finding least common ancestors in directed acyclic graphs[END_REF][START_REF] Yuster | All-pairs disjoint paths from a common ancestor in O (n(omega)) time[END_REF][START_REF] Harel | Fast Algorithms for Finding Nearest Common Ancestors[END_REF]). An improved solution, with ߱ ൌ 2.575, is described in [START_REF] Czumaj | Faster algorithms for finding lowest common ancestors in directed acyclic graphs[END_REF]. As the domain is active, [START_REF] Eckhardt | Fast lowest common ancestor computations in dags[END_REF] have given an algorithm that calculates all ݈ܿܽሺ,ݔ ݕሻ for all pairs of vertices with a mean time complexity ܱሺ|ܸ| ଷ ݈݈݃݃ሺ|ܸ|ሻሻ and worst time complexity ܱሺ|ܸ| ଷ.ଷଷଽଽ ሻ.

Recall that we need the ܷ െ ݁ݎݑݏ݈ܿ of a set ܵ (denoted by ܵ) and Algorithm 2, even with the optimized subroutine [START_REF] Eckhardt | Fast lowest common ancestor computations in dags[END_REF] for computing lca, would have a complexity of at least ܱሺ|ܸ| ଷ.ଷଷଽଽ ሻ for computation time and ܱሺ|ܸ| ଶ ሻ for memory space (in order to store pre-computed ݈ܿܽ). We thus introduce an optimized dedicated solution that takes the topological vertex order induced by the dag into account. This solution has lower worst time complexity -ܱሺ|S ത |||ܧሻ -and space -ܱሺ|S ത ||ܸ|ሻ -complexity. The advantage of this solution is even more relevant in practice, since for most real cases |ܵ ҧ | ا |ܸ| and for most ontologies |ܧ| ا |ܸ ଶ |.

Optimized algorithm to compute U lca closure in ሺ| ഥ |||ሻ

This subsection details an optimized algorithm that determines the ܷ closure of ܵ for a dag ܩ ൌ ሺܸ, ܧሻ in ܱሺ|S ത |||ܧሻ. The key idea of this algorithm is that, although there are ܱሺ|ܸ| ଶ ሻ couples of vertices, at most ܱሺ|ܸ|ሻ nodes can be added to ܵ. Rather than computing the lca for each pair of vertices, we thus consider each node and decide greedily whether or not it must be added to ܵ. This can be done efficiently by taking the topological vertex order induced by the dag into account. These are classical algorithms that we recall below so that the paper will be selfcontained. Our ܷ closure algorithm considers vertices in post order, i.e. a vertex is never considered before considering all of its descendants. Indeed, vertices of a dag can be ordered along a horizontal line such that all descendants of a vertex are placed to its left. We call this a post order since, as shown in [START_REF] Thomas | Graph Algorithms[END_REF], one can be efficiently obtained using the post-order indices of a depth-first search (Algorithm 3).

Name: postOrder

ܵ ሺ݊ሻ ൌ ܵ ሺݏ ଵ ሻ  …  ܵ ൫ݏ ൯ (6)
The test at the point (**) of the algorithm is used to decide whether or not ݊ is in the closure and should be added to ܵ ሺ݊ሻ and to ܵ . For each node ݊, the three following characteristics are displayed: its label, its rank in the postOrder vector and its current set ܵ ሺ݊ሻ. This figure displays information available at the point (**) while processing the node 1ܤ (dotted circle). At this step the four sets ܵ ሺ1ܥሻ, ܵ ሺ2ܥሻ, ܵ ሺ3ܥሻ and ܵ ሺܦሻ have already been computed. Other ܵ sets are not yet initialized (marked with '?'). ,1ܥ 2ܥ and 3ܥ have been identified as part of the ܷ closure of ܵ (encircled) and the algorithm considers whether or not 1ܤ is also part of this ܷ closure. At point (**) the current set ܵ ሺ1ܤሻ is the union of the two sets ܵ ሺ1ܥሻ and ܵ ሺ2ܥሻ. This union being larger than the two sets used to deduce it, 1ܤ is identified as part of the ܷ closure of ܵ and ܵ ሺ1ܤሻ will be updated accordingly (see fig. 6). sure algorithm requires ܱሺ|ܵ ҧ ||ܸ|ሻ ൌ ܱሺ|ܸ| ଶ ሻ memory space.

Proof. For each node of the outer "for" loop of algorithm 4, a subset of ܵ ҧ is stored. In the worst case, |ܵ ҧ | ൌ |ܸ| leading to a complexity of ܱሺ|ܸ| ଶ ሻ.

Note that in most cases |ܵ ҧ | ا |ܸ|. Moreover, when all parents of a node ݊ have been treated, the subset of ܵ ҧ attached to ݊ becomes useless, which means that some memory space can be freed. This can be easily done by maintaining a counter for each node initialized to its number of parents. When treating a node, the counters of all of its children are decreased by one, and when a child reaches a zero value its memory is freed. This does not reduce the worst case complexity, since this optimization is useless when the dag is made of one node that has |ܸ| െ 1 children, but it significantly reduces the memory space needed in most real cases.

The algorithms presented in this section are used for identifying a set of relevant concepts according to those of interest. Their relationships have to be rebuilt in order to obtain the intended sub-ontology. An efficient algorithm has been described to compute the ܷ closure of a set of concepts. Yet, when considering a set of vertices ܵ, every greatest common descendant (ܷ ௗ ) of a pair of vertices of ܵ is also a key vertex to grasp relationships between vertices of ܵ. All results and algorithms of the previous section concerning lca can easily be transposed to gcd. This is due to the duality of the two operators. Let ܩ be the dag ሺܸ, ܧሻ and let ܩ כ the dag ܩ כ ൌ ሺܸ, ܧ כ ሻ such that ሺv, uሻ א E כ iff ሺu, vሻ א E. Then, for all ݔ and ݕ of ܸ, an lca (resp. gcd) of ݔ and ݕ in ܩ is a gcd (resp. lca) of ݔ and ݕ in ܩ כ . ܵ ҧ denotes the ܷ closure of ܵ and, similarly, ܵ, denotes its ܷ ௗ closure.

BUILDING THE SUB-ONTOLOGY

The previous section describes efficient algorithms to compute ܷ and ܷ ௗ closures of a set of concepts. Both algorithms have been used within a broader process to extract the sub-ontology.

Using and closures to define the set of relevant concepts.

Given a set ܵ containing concepts of interest, we define the set ܵ of relevant concepts kept in the sub-ontology as ܵ ൌ ܵ ҧ  ܵ. Note that this set is not closed with respect to lca or gcd operators, as illustrated by Fig. 7, where B and D belongs to ܵ whereas their least common ancestor A1 does not. One could thus be tempted to use the set ܵ defined by the closure of both operators. For instance, concept A1 in Fig. 7 is present in S because A1 ൌ lcaሺlcaሺC1, C2ሻ, gcdሺC2, C3ሻሻ. The relationship between such concepts and the initial ones is thus hard to interpret and including them in the sub-ontology can be more confusing than helpful. We thus build the sub-ontology with Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

respect to S using only concepts within S ത  S since this is faster and more meaningful than using S.

Note that the set of concepts derived from the SCA and ASA strategies from Nebot and Berlanga [START_REF] Nebot | Efficient retrieval of ontology fragments using an interval labeling scheme[END_REF], is {C1, C2, C3, B, X, A1, Thingሽ ـ S ത . Indeed, though poorly informative, X and A1 are kept because they are common ancestors of C1 and C2. X is discarded by their third strategy (ASA-ST) while the A1 concept may be captured or not, depending on their choice of spanning tree.

Adding hyponymic and hypernymic relationships among relevant concepts

Once the set of relevant concepts ܵ has been found, hypernymic (and hyponymic) relationships among them have to be identified. We want to preserve the hypernymic and hyponymic relationship between concepts in ܵ even though intermediary concepts have not been kept in ܵ . Definition 5.2.1. Given the dag ܩ ൌ ሺܸ, ܧሻ, the relevant subdag ܩ ൌ ሺܸ , ܧ ሻ is defined with:

• ܸ ൌ ܵ ҧ  ܵ • ሺ,ݑ ݒሻ א ܧ iff there is a directed path in G going from ݑ to ݒ without crossing any nodes of ܸ The set ܧ of edges can be efficiently computed due to the topological order induced by the dag. This time we will consider a vertex ݑ only after having considered all of its ascendants. Such an order, that we will call a pre order, can be obtained by simply considering the post order vector from tail to head. Let ܸ ோோ ሺݑሻ be the set of Relevant Reachable Ancestors of ݑ containing vertices that are present in ܸ and can be reached from ݑ through a path crossing no other nodes of ܸ . When considering vertices in pre order, the set ܸ ோோ ሺݑሻ of the current node ݑ is simply the union of ܸ ோோ ሺ݂ሻ sets of all of its parent nodes that are not in ܸ , plus all its parent nodes that are in ܸ . The set ܧ is then constructed by adding, for each node ݑ of ܸ , edges ሺ,ݑ ݒሻ between ݑ and any node ݒ of ܸ ோோ ሺݑሻ as detailed in Algorithm 5. As for Algorithm 4, the key instruction, line (*), computes the union of two sets of at most |ܸ | elements and is executed for every parent of every node of the initial dag ܩ i.e. ܱሺ||ܧሻ times. The overall complexity of this algorithm is thus ܱሺ|ܵ ҧ  ܵ||E|ሻ = ܱሺ|V||E|ሻ.

Name: subIsaDag

Input

Adding other kinds of relationships between relevant concepts

While ontologies may include various kinds of concept relationships, most sub-ontology extractions identify relevant concepts only using the is-a relationship. Indeed this relationship is the only one shared by all ontologies and it constitutes their backbone. The key role of the is-a relationship is clearly explicit in the formal definition of the ontology proposed by [START_REF] Maedche | Ontology Learning for the Semantic Web[END_REF] (p. 244-). Consequently, our method to select relevant concepts relies only on this relationship. However, other relationships may be added among those selected concepts. This section describes the strategy we used within this second phase.

Having the relevant sub-isa-dag ܩ ൌ ሺܸ , ܧ ሻ obtained from the original ontology Մ, one should at least enrich the relevant sub-ontology Մ with any relationship ݒܴݑ of Մ concerning two concepts ,ݑ ݒ of ܸ . Some additional relationships between two concepts ,ݑ ݒ of ܸ can be deduced from the original ontology even if the relation ݒܴݑ is not explicitly present in Մ. For instance, let ,ܽݏܫ ݍܧ and ݂ܲ be the is-a, equivalence and part-of relationships, respectively. If we consider the case where ܣ ܽݏܫ ,ܤ ܣ ݂ܲ ܥ and ܣ ݍܧ ,ܦ and ܸ ൌ ሼ,ܦ ܥሽ, the relationship ܦ ݂ܲ ܥ can be added since ܣ ݂ܲ ܥ and ܣ ݍܧ .ܦ Formalizing the relationship that should be kept is far from obvious and the semantics of the relationships at stake must be properly taken into account. Yet some general rules can be applied for the simplest cases. In particular, for any transitive relationship ܴ (i.e. when ܴܾܽ ܽ݊݀ ܾܴܿ ֜ ܴܽܿ), we can add the relation ݒܴݑ to Մ for any pairs of concepts such that there is a sequence of relationships ܴܽݑ ଵ , ܽ ଵ ܴܽ ଶ , … , ܽ ݒܴ in Մ and no ܽ concept belongs to ܸ . This is a straightforward generalization of the approach used to determine the is-a relationship of Մ .

Algorithm 5, formulated to add the is-a relationship to Մ , relies on the fact that the underlying graph representation of these relationships is a dag. Hence, this algorithm can only handle anti-symmetric relationships (that induce a dag structure) and is only meaningful for transitive relationships (otherwise it will induce wrong relationships). It can thus be used on is-a and part-of relationships but not for the equivalence one that is transitive but not anti-symmetric and may thus induce cycle ܣ( ݍܧ ,ܤ ܤ ݍܧ ܥ and ܥ ݍܧ ).ܣ All of the presented algorithms have been implemented in an application called OntoFocus using Java and the Jena library. OntoFocus takes an OWL ontology and a set of concepts of interest ܵ as input, and an OWL sub-ontology focused on ܵ as output. The current version adds any direct relationships existing between two relevant concepts and uses Algorithm 5 to add direct and induced is-a and part-of relationships between them. Applications are discussed in the following section.

Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

APPLICATIONS, RESULTS AND PERSPECTIVES

The accumulation of digital information has become problematic in many domains, especially in Life Sciences where genome decryption, for example, leads to hundreds of databases and interacting applications. They often make use of ontologies to organize the information, to support semantic information retrieval and visual navigation through it. The size and scope of bio-ontologies have increased almost as rapidly as the biological data. However, in numerous cases, only a few of their concepts are useful at once. For example, molecular biologists often visualize and analyze a graph representation of the ontology relations of a subset of Gene Ontology concepts, but unfortunately this analysis is often done by hand [START_REF] Lindberg | Effect of infliximab on mRNA expression profiles in synovial tissue of rheumatoid arthritis patients[END_REF][START_REF] Alexa | Improved scoring of functional groups from gene expression data by decorrelating GO graph structure[END_REF][START_REF] Del Pozo | Defining functional distances over gene ontology[END_REF].

OntoFocus has been used to restrict the Gene Ontology to the subset of concepts related to the BRCA1 gene associated with BReast CAncer susceptibility. More precisely, we downloaded the annotation of the Swiss-Prot protein P38398 (associated with BRCA1) via the Go Annotation (GOA) service provided by the European Bioinformatics Institute (http://www.ebi.ac.uk/GOA/.) We thus obtained 102 redundant annotations corresponding to a set of 50 individual GO concepts. The corresponding sub-ontology inferred by On-toFocus in about one minute contains 92 relevant concepts (instead of thirty thousand). As illustrated in Fig. 8, the visualization is very comfortable and within human cognitive and perceptive limits. Here two of the three connected parts of the sub-ontology are presented: concepts that correspond to molecular functions (GO_0003674) and those that correspond to cellular components (GO_0005575). The last part corresponding to biological processes is not presented here. However, it contains 63 concepts, which also facilitates visualization.

Giving a specific view on the ontology may highlight part of it and clarify the fact that some concepts are refinements of others. Fig. 8 highlights, for example, that several annotations are refinements of the protein binding function (GO_0005515.) Such user-centered sub-ontologies may be useful for biological users exploiting annotations, especially for collaboratively updating gene annotations. This approach is also widespread in comparative genomic analysis in which gene function variation among species (gene annotations, in this case, are species dependant) is studied. An intuitive way to summarize this variation is to color concepts of an ontology excerpt. Such representations have been achieved on a large scale for genes related to human diseases [START_REF] O'brien | OrthoDisease: a database of human disease orthologs[END_REF] and made available on a Web site (http://www.informatics.jax.org/GOgraphs/OrthoDisease/). These excerpts have been obtained by keeping all ancestor concepts (hence including useless concepts while ignoring common descendants). This rough strategy can thus be advantageously replaced by the one presented in this paper and integrated in OntoFocus.

The same approach may be used to simultaneously apprehend annotations of several genes that share some biological characteristics (e.g. genes having similar expression profiles in microarray experiments.) In such cases, GO concepts are useful for giving biological meaning to the corresponding gene clusters. These annotating genes can be used to automatically define the set of concepts of interest that can serve as an OntoFocus input. The resulting sub-ontology highlights gene annotation relationships and helps to determine the cluster semantic. The additional concepts proposed by OntoFocus are also good candidates for annotating a cluster as a whole. Indeed, as underlined by [START_REF] Tao | A tool for abstracting relevant classes of concepts: The common ancestry summarizer[END_REF], least common ancestor concepts are of particular interest for summarizing annotations. Our approach, illustrated here by a biological application, may be used in every Information System dealing with amounts of data and huge ontologies. Indeed, having sub-Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

ontologies may be helpful in any computer assisted ontology operation requiring a human expert (e.g. ontology design and evolution or visual filtering within conceptual maps). To be effective, visual representations must be semantically guided so that the user may observe semantics while browsing data. Therefore, we plan to adapt sub-ontology extraction in order to enrich the sub-ontology with additional information such as the number of children/parents in the reference ontology and the original path length of an is-a edge. This additional information will allow us to compute the semantic distance separating two relevant concepts with respect to the reference ontology [START_REF] Lee | Comparison of ontology-based semantic-similarity measures[END_REF].

Concerning ontology visualizations, as mentioned in [13] many papers have been proposed but they all focus on hierarchy representation. "In general the main drawback is that the semantics entailed by the ontologies is not used fully" [START_REF] Wouters | Large scale ontology visualisation using ontology extraction[END_REF]. We assume that there is an alternative way of representing ontologies. In [START_REF] Ranwez | Ontological distance measures for information visualisation on conceptual maps[END_REF] a semantic distance has been proposed to evaluate similarity between concepts. This distance, combined with visualization techniques using multidimensional scaling, provides a different view of the concept hierarchy. Concerning the prospects of the work presented in this paper, we plan to insert OntoFocus in an environment that we have developed: OBIRS (ontology based information retrieval system) [START_REF] Ranwez | User Centered and Ontology Based Information Retrieval System for Life Sciences[END_REF]. In response to a query built with concepts of a domain ontology, OBIRS builds semantic maps to display the retrieved documents. These maps may be used for navigating through, analyzing or viewing digital documents annotated by concepts of a given ontology.

CONCLUDING REMARKS

After justifying the crucial need for sub-ontology extraction methods for different purposes, this paper introduces a graph based definition of relevant concepts for highlighting relationships among concepts of interest and provides an optimized algorithm to identify them. According to a reference ontology and a set of concepts of interest, it computes ܷ and ܷ ௗ closures on direct acyclic graphs (dag) induced by is-a relationships. It then infers relationships among these relevant concepts to provide a user-centered sub-ontology. The complexity of this algorithm is proportional to the number of kept concepts in addition to the number of reference dag edges.

The resulting OntoFocus program may be freely used online (http://www.ontotoolkit.mines-ales.fr/). Many applications may benefit from this algorithm. One of them, developed in this paper, concerns the life science domain and the use of gene ontology to analyze gene annotations. Because of the very short calculation time (few seconds for about 30.000 concepts), calculations may be performed each time a user needs a specific view. This ensures that the subontology is always compliant with the reference ontology and offers novel prospects for real-time user interactions. For instance, this provides the possibility of chaining several extractions, progressively refining the ontology so that the user can precisely tune the filtering process.

Future directions of our work include ontology visualization, organization of query results and dedicated applications coupled with Gene Ontology.

Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 [START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300.

Definition 3 .

 3 1.1. ([30])The least common ancestors ݈ܿܽሺܵሻ of a vertex subset ܵ ⊆ V with respect to a dag ܩ ൌ ሺܸ, ܧሻ are vertices ݑ א ܣሺܵሻ, such that ݀ ு ି ሺݑሻ ൌ 0 in the graph H ൌ Gሾܣሺܵሻሿ induced by ܣሺܵሻ.

Fig. 1 .

 1 Fig. 1. Hypothetical illustration of the lca operator

Fig. 2

 2 Fig.2illustrates the definition of the ܷ operator. This example also highlights the difference between the two least common ancestor operators. Given the set ܵ ൌ ሼ,1ܥ ,2ܥ 3ܥሽ, ܷ ሺܵሻ ൌ ሼ,1ܣ ,2ܣ ,1ܤ ,2ܤ ,3ܤ ,1ܥ ,2ܥ 3ܥሽ, while ݈ܿܽሺܵሻ ൌ ሼ,1ܣ 2ܣሽ.

Fig. 2 .

 2 Fig. 2. Hypothetical example of the ܷ operator and the way it differs from the lca operator.

Fig. 3 .

 3 Fig. 3. Hypothetical illustration of ܷ closure Let ܵ be a subset of vertices of .ܩ Let the increasing set sequence defined by: ܵ ൌ ܵ and ܵ ାଵ ൌ ܷ ݈ܿܽ ሺܵ ሻ, ݇ ൌ 0, 1, … . As ܩ is finite, there is a number ܿ, 0 ܿ |ܸ| such that ݇ ܿ, ܵ ൌ ܷ ݈ܿܽ ሺܵ ሻ. This fixpoint (or fixset) is reached because of the monotonicity of the ܷ operator. In fact, once this relation holds for a given k, it holds for all greater values. So ܿ and ܵ are well defined. Definition 3.2.2. The number ܿ is called the closure index and the set ܵ is called the ܷ closure of ܵ and is denoted ܵ ҧ .

Fig. 4 .

 4 Fig. 4. Hypothetical example where the closure index is proportional to |ܸ|. ܵ ൌ ሼܣ , ܤ ሽ, at iteration k two vertices ሼܣ , ܤ ሽ are added so that ܵ ൌ ሼܣ , … , ܣ , ܤ , . . ܤ ሽ.

  by the ܷ operator definition. o ܷ ሺܯ ת ܰሻ ⊆ ܯ ת ܰ. This comes from the fact that the ܷ operator preserves monotonicity:ܯ ת ܰ ⊆ ܯ ֜ ܷ ሺܯ ת ܰሻ⊆ ܷ ሺܯሻ ൌ ܯ ܯ ת ܰ ⊆ ܰ ֜ ܷ ሺܯ ת ܰሻ⊆ ܷ ሺܰሻ ൌ ܰ ܷ ሺܯ ת ܰሻ ⊆ ܯ ܽ݊݀ ܷ ሺܯ ת ܰሻ ⊆ ܰ ֜ ܷ ሺܯ ת ܰሻ ⊆ ܯ ת ܰ. Definition 3.2.3. The ܷ closure of ܵ is the set ܵ Ӗ ൌ ځ ܯ ெࣦאሺௌሻ . Lemma 3.2.3.The above two definitions of ܷ closure are equivalent.Proof. We have to show that ܵ Ӗ ൌ ܵ ҧ .• ܵ Ӗ ⊆ ܵ ҧ . By definition, ܵ ҧ ൌ ܷ ሺܵ ҧ ሻ, furthermore the monotonicity of the set sequence ܵ , ܵ ଵ … , ܵ ҧ ensures that ܵ ⊆ ܵ ҧ . Therefore ܵ ҧ א ࣦሺܵሻ, thus proving that ܵ Ӗ ⊆ ܵ ҧ . • ܵ ҧ ⊆ ܵ Ӗ . By definition, set S is included in every set of ࣦሺܵሻ and thus in their intersections. It follows that ܵ ⊆ ܵ Ӗ , and therefore ܷ ሺܵ ሻ⊆ܷ ሺ ܵ Ӗ ሻ, which can be rewritten ܵ ଵ ⊆ ܵ Ӗ . Applying the ܷ operator to both terms leads to ܵ ଶ ⊆ ܵ Ӗ , ܵ ଷ ⊆ ܵ Ӗ and so on until ܵ ⊆ ܵ Ӗ , thus proving that ܵ ҧ ⊆ ܵ Ӗ .These definitions provide the framework for our subontology extraction.

4 4 . 1

 41 AN EFFICIENT ALGORITHM TO COMPUTE U LCA CLOSURE Since ontologies may contain several thousand concepts, efficient algorithms are needed to compute the ܷ closure of a set ܵ of concepts of interest with respect to their underlying is-a dag ܩ ൌ ሺܸ, ܧሻ. Straightforward algorithms to compute U lca closure We give below, as a lower bound on complexity, two straightforward solutions to calculate ܷ closure (the second being a slight improvement of the first, see Algorithm 2).

3 )

 3 Name: Straightforward_ܷ _closure Input: a dag ܩ and a set of nodes ܵ of .ܩ Result: ܵ ҧ the ܷ closure of ܵ. ܵ ௧ ՚ ܵ; do ܵ ՚ ܵ ௧ ; ܵ ௧ ՚ ; for each ሺ,ݔ ݕሻ א ܵ ൈ ܵ ܵ ௧ ՚ ܵ ௧  ݈ܿܽሺ,ݔ ݕሻ; end while ܵ ് ܵ ௧ return ܵ Algorithm 1. Straightforward Ulca-closure algorithm Name: Slightly_improved_ܷ _closure Input: a dag ܩ and a set of nodes ܵ of .ܩ

  Name: ܷ closure Input: a dag ,ܩ a set ܵ containing nodes of interest. Result: the ܷ closure of ܵ. ܵ ՚  P = postOrder()ܩ for n in P ܵ ሺ݊ሻ ՚  // ܵ ሺ݊ሻ is the set of descendants of // ݊ present in the ܷ closure of ܵ ܵݔܽ݉ ሺ݊ሻ ՚ 0 // ܵݔܽ݉ ሺ݊ሻ is the maximal value // |ܵ ሺݏሻ| with ݏ a child of ݊ for s in children(n) ܵ ሺ݊ሻ ՚ ܵ ሺ݊ሻ  ܵ ሺݏሻ (*) ܵݔܽ݉ ሺ݊ሻ ՚ max(|ܵ ሺݏሻ |, ܵݔܽ݉ ሺ݊ሻ) end if ( (݊ א ܵ) OR ( |ܵ ሺ݊ሻ|> ܵݔܽ݉ ሺ݊ሻ ) ) (**) ܵ ሺ݊ሻ ՚ ܵ ሺ݊ሻ  {n} ܵ ՚ ܵ  ሼ݊ሽ end end return ܵ Algorithm 4. Computation of ܷ closure Proposition 4.2.1. (Proof of correctness). Given the inputs ܩ ൌ ሺܸ, ܧሻ and ܵ, the set ܵ returned by Algorithm 4 is the closure of ܵ with respect to ,ܩ ܵ ൌ ܵ Ӗ ൌ ܵ ҧ . Proof. Let ܲ denote the array of nodes of ܩ sorted by the postOrder function. The ܷ closure algorithm goes through ܲሾ1ሿ, … , ܲሾ݇ሿ, … , ܲሾ|ܸ|ሿ gathering, for each k, a subset of ܵ denoted ܵ ሺ݇ሻ. It is clear that ܵ ൌ ܵ ሺ|ܸ|ሻ. We show by induction that: ܵ ሺ݇ሻ ൌ ܵ Ӗ ת ܲሾ1. . ݇ሿ ܽ݊݀ ܵ ሺܲሾ݇ሿሻ ൌ ܵ Ӗ ת ݀݁ܿݏሺܲሾ݇ሿሻ, ݇ ൌ 1, 2, … , |ܸ|.

( 5 )

 5 Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24[START_REF] Jimenez-Ruiz | Safe and economic re-use of ontologies: A logic-based methodology and tool support[END_REF], 2288-2300. The statement (5) holds for ൌ . Node ܲሾ1ሿ has no descendant. It is kept in ܵ if and only if ܲሾ1ሿ א ܵ ⊆ ܵ ന (the line (**) of the algorithm.) Thus, ܵ ሺ1ሻ ൌ ܵ Ӗ ת ܲሾ1. .1ሿ and ܵ ሺܲሾ1ሿሻ ൌ ܵ Ӗ ת ݀݁ܿݏሺܲሾ1ሿሻ. Assuming that (5) holds for indices , … , ሺ െ ሻ, then (1) also holds for indices , . . , . Let ݊ ൌ ܲሾ݇ሿ be the current node and ሼݏ ଵ , … , ݏ ሽ be the set of immediate descendants (children) of ݊. Since nodes are considered in post order, all children of ݊ are at the left of ݊ in array ܲ. When the algorithm is considering ݊, all of its children ݏ ଵ , … , ݏ have already been treated and set ܵ ሺݏ ሻ has been recorded for each ݏ א ሼݏ ଵ , … , ݏ ሽ. At the point (**), the current recorded set for node ݊ (see point (*)) is:

•

  If ݊ א S, ݊ is added to ܵ ሺ݇ሻ as well as to ܵ ሺ݊ሻ and evidently ݊ א ܵ Ӗ ת ܲሾ1. . ݇ሿ and ܵ ሺܲሾ݇ሿሻ ൌ ܵ Ӗ ת ݀݁ܿݏሺܲሾ݇ሿሻ. • If ݊ ∉ S. In this case, by the induction hypothesis, at the point (**) any node of ܵ ൌ ܵ ሺݏ ଵ ሻ  …  ܵ ൫ݏ ൯ are in ܵ Ӗ and we have ܵ ൌ ܵ ሺ݊ሻ െ ሼ݊ሽ ൌ ܵ Ӗ ת ݀݁ܿݏሺ݊ሻ. The only thing remaining to prove is that ݊ will be included in ܵ ሺ݇ሻ and in ܵ ሺ݊ሻ iff it is the least common ancestor of two nodes of ܵ . o If ൫|ܵ ܦ ሺ݊ሻ| ܵݔܽ݉ ܦ ሺ݊ሻ൯ then there are at least two nodes ,ݖ ݐ of ܵ , such that ݊ ൌ ݈ܿܽሺ,ݖ ݐሻ and ݊ should be added to ܵ ሺ݇ሻ as well as to ܵ ሺ݊ሻ. (see Fig. 5 for an example) As |ܵ ሺ݊ሻ| ܵݔܽ݉ ሺ݊ሻ, there are at least two nodes ,ݖ ݐ א ܵ such that ሼ,ݖ ݐሽ م ܵ ሺݏ ሻ, ݅ ൌ 1, … , . It follows that there are two distinct children ݏ , ݏ of ݊ such that ݖ א ܵ ሺݏ ሻ, ݐ א ܵ ൫ݏ ൯. By definition of the lca, ݊ א ݈ܿܽሺ,ݖ ݐሻ if and only if, ݊ א ,ݖሺܣ ݐሻ and ݊ has no descendant in the ancestor set .ሻݐሺܣځሻݖሺܣ The former assertion is obvious, let us prove the latter by supposing this is not the case (reductio ad absurdum). So, there is a node ݊′ א ሻݐሺܣځሻݖሺܣ and a ሺ݊, ݊ ′ ሻ directed path in .ܩ This path necessarily goes through a child ݏ of ݊ and, by the induction hypothesis, ܵ ሺݏ ሻ ൌ ܵ Ӗ ת ݏܿሺݏ݁݀ ሻ. It follows that ሼ,ݖ ݐሽ ك ܵ ሺݏ ሻ, which is impossible. o If the test (**) is not true, then ݊ is not in the closure and is added neither to ܵ nor to ܵ . The main thing to prove is that when |ܵ ሺ݊ሻ| ൌ ܵݔܽ݉ ሺ݊ሻ, there are not two nodes ,ݖ ݐ of ܵ ሺ݊ሻ such that ݊ ൌ ݈ܿܽሺ,ݖ ݐሻ. (see Fig.

Proof.

  Obtaining the postOrder vector of nodes is done through a classical depth first search traversal of the graph in ܱሺ||ܧሻ. The complexity of the remaining part of the algorithm, made of two nested for loops, is obviously determined by the number of executions of line (*). This line computes the union of two sets of at most |ܵ ҧ | elements and is executed for every child of every node, i.e. ܱሺ||ܧሻ times. It follows that the whole complexity of this algorithm is ܱሺ|ܵ ҧ |||ܧሻ. In the worst case, |ܵ ҧ | equals |ܸ| leading to a complexity of ܱሺ|ܸ|||ܧሻ. Note however that generally |ܵ ҧ | ا |ܸ|.

Fig. 5 .

 5 Fig. 5. ܷ closure algorithm: considering a node of the ܷ closure of ܵ.For each node ݊, the three following characteristics are displayed: its label, its rank in the postOrder vector and its current set ܵ ሺ݊ሻ. This figure displays information available at the point (**) while processing the node 1ܤ (dotted circle). At this step the four sets ܵ ሺ1ܥሻ, ܵ ሺ2ܥሻ, ܵ ሺ3ܥሻ and ܵ ሺܦሻ have already been computed. Other ܵ sets are not yet initialized (marked with '?'). ,1ܥ 2ܥ and 3ܥ have been identified as part of the ܷ closure of ܵ (encircled) and the algorithm considers whether or not 1ܤ is also part of this ܷ closure. At point (**) the current set ܵ ሺ1ܤሻ is the union of the two sets ܵ ሺ1ܥሻ and ܵ ሺ2ܥሻ. This union being larger than the two sets used to deduce it, 1ܤ is identified as part of the ܷ closure of ܵ and ܵ ሺ1ܤሻ will be updated accordingly (see fig.6).

Proposition 4 . 2 . 3 .

 423 (Space complexity of ܷ closure algorithm) For a node set ܵ in a dag ܩ ൌ ሺܸ, ܧሻ, the ܷ clo-Comment citer ce document : Ranwez, V., Ranwez, S., Janaqi, S. (2013). Sub-ontology extraction using hyponym and hypernym closure on is-a directed acyclic graphs . IEEE Transactions on Knowledge and Data Engineering, 24 (12), 2288-2300.

Fig. 6 .

 6 Fig. 6. ܷ closure algorithm: considering a node that is not part of the ܷ closure of ܵ. (see Fig. 5 for legend). The algorithm is considering .1ܣ At the point (**), the set ܵ ሺ1ܣሻ combines the three sets ܵ ሺ1ܥሻ, ܵ ሺܺሻ and ܵ ሺܦሻ. With the resulting set being equal to ܵ ሺܺሻ and 1ܣ ב ܵ, 1ܣ will not be added to the ܷ closure of ܵ.

Definition 5 . 1 . 1 .

 511 Let the increasing set sequence defined by: S ൌ S and S ୩ାଵ ൌ S ୩ തതത  S ୩ , k ൌ 0, 1, …Set S ഥ is equal to set S ୡ associated with index c such that k c, S ୩ ൌ S ୩ തതത  S ୩ .

Fig. 7 .

 7 Fig. 7. Hypothetical illustration of ൌ ഥ  Using this constructive definition, set S ഥ can be obtained by iterating the ܷ closure and ܷ ௗ closure algorithms until a fixed point (set) is obtained. This can be done in an O ቀหS ഥ ห ଶ |E|ቁ algorithm. Yet the concepts of S that are not in S ത  S are obtained by applying both lca and gcd operators.

  : a dag ܩ ൌ ሺܸ, ܧሻ a set ܵ containing nodes of interest Result: ܩ the relevant subDAGܸ ՚ ܵ ത  ܵ ܩ ึ ሺܸ ݎ , ሻ for each u in reverse(postOrder(G)) ܸ ோோ ሺݑሻ ึ  for each f in parents(u) if ሺ݂ ב ܸ ݎ ሻ ܸ ோோ ሺݑሻ ึ ܸ ோோ ሺݑሻܸڂ ோோ ሺ݂ሻ (*) else ܸ ோோ ሺݑሻ ึ ܸ ோோ ሺݑሻ݂ڂ if ሺݑ א ܸ ݎ ሻ for each ݒ in ܸ ோோ ሺݑሻ ܩ . ,ݑ݀݃݁ሺܧ݀݀ܽ ݒሻ return ܩ Algorithm 5. Sub-isa-dag algorithm

Fig. 8 .

 8 Fig. 8. Visualization of molecular function (GO_0003674) and cellular component (GO_0005575). GO-sub-ontologies constructed by OntoFocus using BRCA1 annotation (blue colored concepts were added by OntoFocus to make the sub-ontology explicit).

  In this case, ݊ cannot be the lca of a couple of nodes ሺ,ݖ ݐሻ because node ݏ is (by construction) an ancestor of ,ݖ ݐ and a descendant of ݊. It follows that ݊ ∉ ܵ Ӗ and the proof is complete.  Proposition 4.2.2. (Time complexity of ܷ closure algorithm) For a node set ܵ in a dag ܩ ൌ ሺܸ, ܧሻ, the ܷ closure algorithm runs in ܱሺ|ܵ ҧ |||ܧሻ ൌ ܱሺ|ܸ|||ܧሻ.

6 for an example). As |ܵ ሺ݊ሻ| ൌ ܵݔܽ݉ ሺ݊ሻ then there is some ݅ א ሼ1, … , ሽ such that ܵ ሺ݊ሻ ൌ ܵ ሺݏ ሻ.

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, MANUSCRIPT ID

ACKNOWLEDGMENTS

We would like to thank Pierre Jean for his help in deploying the OntoFocus Web server.

The authors wish to thank the reviewers for their many detailed comments and proposals to improve the paper. This publication is the result of a collaboration between the "Institut des Sciences de l'Evolution de Montpellier" (UMR 5554 -CNRS) and the "LGI2P Research Centre from Ecole des Mines d'Alès". This work was supported by the French Agence Nationale de la Recherche 'Domaines Emergents' [ANR-08-EMER-011 'PhylAriane'] and is the contribution N°2011-067 of ISEM.