FEDRR: Fast, Exhaustive Detection of Redundant Hierarchical Relations in Large Biomedical Ontologies

Abstract

Redundant hierarchical relations refer to such patterns as two paths from one concept to another, one with length one (direct) and the other with length greater than one (indirect). This paper introduces a novel and scalable approach, called FEDRR { Fast, Exhaustive Detection of Redundant Relations { for quality assurance work during ontological evolution. FEDRR combines the algorithm ideas of Dynamic Programming with Topological Sort, for exhaustive mining of all redundant hierarchical relations in ontological hierarchies, in O(c jV j + jEj) time, where jV j is the number of concepts, jEj is the number of the relations, and c is a constant in practice. Using FEDRR, we performed exhaustive search of all redundant is-a relations in two of the largest ontological systems in biomedicine: SNOMED CT and Gene Ontology (GO). 235 and 1609 redundant is-a relations were found in the 2015-03-01 version of SNOMED CT and 2015-05-01 version of GO, respectively. Each redundant relation represents a possibly unintended defect that needs to be corrected in the ontology quality assurance process. FEDRR provides a generally applicable, e ective tool for systematic detecting redundant relations in large ontological systems for quality improvement.

Keywords

• Redundant relations
• SNOMED CT
• Gene Ontology
• Dynamic Programming

-

Ontologies are shared conceptualizations of a domain represented in a formal language. They represent not only the concepts (nodes) but the relationships (edges) between the concepts. Ontologies have become a critical knowledge source in informatics and data intensive applications, such as information retrieval [ 1 ], data integration [ 2 ], data management [ 3 ], and decision support [ 4 ].

This paper focuses on a particular type of ontological structural defect: redundant relations. Redundant hierarchical relations refer to such patterns as two paths from concept X to concept Y , one with length one (direct) and the other with length greater than one (indirect). For hierarchical relations such as subsumption (is-a), relations implied by transitivity should not be explicitly stated. For example, in Gene Ontology (GO 2015-05-01 version) we have (see Table 1): ? Corresponding author.

GO Id A GO:0046879 B GO:0009914 C GO:0010817 D GO:0065008 E GO:0065007

Relation

is-a is-a is-a is-a is-a

GO Id B GO:0009914 C GO:0010817 D GO:0065008 E GO:0065007

F GO:0008150

However, \A (GO:0046879) is-a F (GO:0008150)" is directly asserted as well (Fig. 1). This represents redundant relations to be studied in this paper: two paths exist between A and F: one directly between A and F, and the other indirectly through B, C, D, and E as intermediate concept nodes.

The principle of parsimony in ontological modeling refers to the omission of relations implied by the transitive property of a relationship, such as \is-a" relations in GO. By violating this principle, redundant relations may increase maintenance burden for ontology curators. It can also cause and inaccurate methods and algorithms based on this general principle. For example, semantic distance between concepts is a widely used technique [ 5 ]. Ontological mapping and alignment methods rely on the ordered structure of the hierarchical relation [ 6 ], with notions of neighborhood and proximity serving as their foundation. The presence of redundant relations induce a short-circuit: two concepts with a larger semantic distance may result in a smaller distance by mistake; and concepts not within a neighborhood may be counted as such.

Using brute force, exhaustive detection of redundant relations can be computationally expensive for large ontologies. For example, SNOMED CT (201503-01 version) contains over 300,000 active concepts. A naive approach would be to nd the longest paths between the end nodes of each of the over 500,000 edges (relations). Assuming each edge takes 100ms, processing a single version of SNOMED CT would take 14 hours. Finding all paths between all possible pairs among the 300k nodes would take over 10,000 days if each pair takes 10ms.

This paper introduces a novel and scalable approach, called FEDRR, Fast, Exhaustive Detection of Redundant Relations, for quality assurance work during ontological evolution. In contrast to the 14 hours naive approach required for each SNOMED CT version, FEDRR needed <20 seconds (Section 4).

Using FEDRR, we performed exhaustive search of all redundant is-a relations in two of the largest ontological systems in biomedicine: SNOMED CT and GO. 235 and 1609 redundant is-a relations were found in the most recent versions of SNOMED CT and GO, respectively. Each redundant relation represents a possibly unintended defect that needs to be corrected in the ontology quality assurance process. We further performed longitudinal analyses using FEDRR on 5 recent versions of SNOMED CT and 10 versions of GO. 2

Background

SNOMED CT. SNOMED CT is the world's largest clinical terminology [ 7, 8 ]. It provides broad coverage of clinical medicine, including ndings, diseases, and procedures for use in electronic medical records. From a structural perspective, SNOMED CT can be seen as a series of large directed acyclic graphs, one for each of its 19 \sub-hierarchies" including Procedure, Substance, Body structure, Specimen, Clinical nding, and Organism. No concept is shared across sub-hierarchies except for the root. Each concept comes with a SNOMED CT identi er, which is an integer. SNOMED CT concepts are linked by hierarchical relations within each sub-hierarchy.

Gene Ontology. The Gene Ontology [ 9 ] is a collection of three ontologies to describe attributes of gene products in three non-overlapping domains of molecular biology: Cellular Component, the parts of a cell or its extracellular environment; Molecular Function, the elemental activities of a gene product at the molecular level, such as binding or catalysis; and Biological Process, operations or sets of molecular events with a de ned beginning and end, pertinent to the functioning of integrated living units (cells, tissues, organs, and organisms). Within each ontology, terms have free text de nitions and unique identi ers. GO terms can be related to each other by is-a and part-of relationships, forming a directed acyclic graph. The GO vocabulary is designed to be species-agnostic, and is intended to capture multiple organisms.

Ontology Quality Assurance. Large, comprehensive terminological systems such as SNOMED CT and GO continue to evolve over time [12{19]. Ontology Quality Assurance (OQA) is an indispensable part of the ontological engineering lifecycle [ 10, 11 ]. OQA attempts to assess and improve the overall quality of ontologies in aspects such as the consistency of the ontological structure with respect to the explicit and implicit knowledge they capture; the coverage of the ontology in terms of classes and properties needed to support speci c applications; and the non-redundancy of classes and properties.

The basic premise of OQA is a mixed closed-world assumption (CWA) and open-world assumption (OWA). In a formal system of logic used for knowledge representation, such as ontological systems, CWA refers to the assumption that a relationship holds true between two concepts is also explicitly asserted to be true, unless they are implied by logical properties such as transitivity. It dictates that, in reverse, a relationship between two concepts that is not asserted explicitly, must be false. OWA, on the other hand, refers to the assumption that lack of knowledge does not imply falsity.

In the context of OQA, OWA refers to the evolving state of knowledge in a domain, in the sense that new concepts may be included in an ontological system in a continuous fashion. The lack of a concept in an ontological system does not imply that such a concept does not exist. CWA, on the other hand, implies that, among existing concepts in an ontological system, the lack of an explicit relationship of a known relation-type between two concepts means that such a relationship does not exist between the two concepts.

The principle of parsimony in ontological modeling is a direct consequence of CWA. It refers to the fact that relations implied by the transitive property of a relationship, such as the example given in Fig. 1, must not be explicitly stated. By violating this principle, redundant relations can cause methods and algorithms based on this general principle inaccurate. Detecting redundant relations is an important task for OQA, which is the focus of this paper. 3

Methods

The general mathematical abstraction of an ontological structure is a graphtheoretic one: nodes correspond to concepts, and edges correspond to relations (between nodes). For hierarchical relations in ontological systems such as \is-a," which obeys the transitivity property that

if A is-a B and B is-a C, then A is-a C, one can model the structure of an ontological system as a directed acyclic graph (DAG, as shown in part in Fig. 1).

De nition 1. Suppose G = (V; E) is a directed acyclic graph with V a set of nodes, and E a set of edges between the nodes. A redundant relation in G is a pair of nodes (s; t) such that (s; t) 2 E, and there is an indirect path (i.e., length more than 1) from s to t.

The closely related known algorithm for computing redundant relations in the literature is all-pair longest path [ 20 ]. Although xed source longest path can be solved in time-complexity O(jV j + jEj) in a DAG [ 20 ], all-pair longest path requires iteration over V , resulting in an O(jV j jEj + jV j2) time-complexity algorithm. For large ontological systems such as SNOMED CT, such a running time amounts to an intractable amount of processing time (requiring 10,000 days if all-pair paths were to be computed).

FEDRR solves this problem in time-complexity O(c jV j + jEj), where c is the average number of descendants of a node. For the latest version of SNOMED CT, we have c = 17:12 (see Time Complexity Analysis). For a single version of SNOMED CT, the actual processing time is less than 20 seconds.

There are two key algorithmic ideas behind FEDRR. One is avoidance of repeated computations by remembering the set of directly reachable nodes as well as the set of indirectly reachable nodes, for each node. The second is to completely skip node pairs that are not connected by a directed path. These ideas are re ected in FEDRR using a novel combination of dynamic programming with topological sort. The sparsity of most ontological structures, viewed as a DAG, is a particularly suitable property for the second idea to take advantage of.

For a node u in a DAG G = (V; E), we introduce two sets, Du and Iu, where { Du = fv j (v; u) 2 Eg, called the D-set, consists of the direct descendants (i.e. children) of u; and { Iu, called the I-set of u, is the set of all indirect descendants of u. The design of our algorithm is based on the following observation. Lemma 1. For each node v 2 Du \ Iu, (v; u) is redundant.

Our algorithm amounts to the computation of (Du; Iu) for each node u. To utilize the idea of dynamic programming, we update (Du; Iu) for each node u according to the order by topological sort. The basic update scheme is illustrated in the following diagram: (fv1; v2; : : :g; Sik=1(Dvi [ Ivi))

Parent u v2 v1 vk

Children (Dv1; Iv1) (Dv2; Iv2)

(Dvk; Ivk)

Suppose we have obtained (Dvi ; Ivi ) for each i = 1; : : : ; k, where fv1; v2; : : :g = fv j (v; u) 2 Eg. Then we set Du = fv1; v2; : : :g and Iu = Sik=1(Di [ Ii): The pseudo-code of FEDRR appears in Algorithm 1. Algorithm 1 FEDRR: Dynamic programming using topological sort to compute the D-set and I-set of each node 1: Input: G(V ) 2: q := new Queue() 3: for all v 2 V do 4: I[v] := ; 5: D[v] := ; 6: if no incoming edge for v then 7: q:enqueue(v) 8: end if 9: end for 10: while q not empty do 11: s := q:dequeue() 12: for all t 2 s:to do 13: I[t] := I[t] [ I[s] [ D[s] 14: D[t] := D[t] [ fsg 15: mark edge (s; t) 16: if no unmarked incoming edge for t then 17: q:enqueue(t) 18: end if 19: end for 20: end while

FEDRR starts by initializing an empty queue to hold the nodes that will be sorted (line 2). Then nodes with no incoming edges are put to the queue, with the D-set and I-set initialized as empty (lines 3 - 9). In the next phase (lines 10 - 20), the nodes are dequeued one at a time, with the I-sets and D-sets (for t) updated according to the mechanism described in Fig. 2.

We illustrate the steps of Algorithm 1 using an example. The input DAG is given below, and there is a redundant edge (colored in red) that FEDRR is supposed to detect.

The algorithm starts with setting initial values for the D-set and the I-set and enqueuing those node with no incoming edges, as shown on the top of Fig. 3 on the right.

After lines 2 - 9, nodes 1; 2 are enqueued.

(f1g;;) 3 4 (f1;2g;;) 5 (f1;2g;;) Nodes 1; 2 dequeued, D set and I set updated on 3; 4; 5. Nodes 3; 4; 5 enqueued.

(;;;) (;;;) (;;;) (;;;) (;;;) (;;;)

(;;;) 2 (;;;) (;;;) (;;;) 1

2 (;;;) (f3g;;) (f4g;f1;2g)

6 (f4;5g;f1;2g) (;;;) 1

2 (;;;) 8 (f3;7g;f1;2;4;5;6g) 7 (f4;6g;f1;2;4;5g)

6 (f4;5g;f1;2g) (f1g;;) 3 4 (f1;2g;;) 5 (f1;2g;;) After nodes 3, 4, 5 dequeued, D-set and I-set updated on nodes 6, 7, 8 (7, 8 not enqueued yet, thus not numbered). Node 6 enqueued. (f1g;;) 3 4 (f1;2g;;)

5 (f1;2g;;) (;;;) 1 2 (;;;) Node 6 dequeued, D-set and I-set updated on node 7. Node 7 enqueued. Node 7 dequeued, D-set and I-set updated on node 8. Node 8 enqueued.

Fig. 3: Illustration of Algorithm 1.

For this sample DAG, the result is shown in Fig. 4. 8 (f3; 7g; f1; 2; 4; 5; 6g) 7 (f4; 6g; f1; 2; 4; 5g)

6 (f4; 5g; f1; 2g)

Correctness. The correctness of the algorithm can be proved using mathematical induction by showing I[vi] = Ivi and D[vi] = Dvi after node vi is dequeued (line 11) for i = 1 : : : jV j.

Proof. i = 1: The rst dequeued node must be a node with no incoming edges. This means Iv1 = ; and Dv1 = ;. As both I[v1] = ; and D[v1] = ; from lines 4 and 5, we have I[v1] = Iv1 and D[v1] = Dv1 .

Suppose I[vi] = Ivi and D[vi] = Dvi is true for i = 1 : : : k 1. For i = k, then we have D[vk] = fv j (v; vk) 2 Eg and I[vk] = Sj (D[vkj ] [ I[vkj ]); where vkj 2 fv j (v; vk) 2 Eg. Based on the de nition of Dv, we have Dvk = fv j (v; vk) 2 Eg = D[vk]. From the induction hypothesis, we have I[vi] = Ivi and D[vi] = Dvi for i = 1 : : : k 1. This means I[vk] = Sj (D[vkj ][I[vkj ]) = Sj (Dvkj [Ivkj ) = Ivk : version of GO, c = 54527;;957590 = 12:97.

Time Complexity Analysis. The topological sorting itself takes O(jV j + jEj) time [ 21 ]. With the computation of D-set and I-set, the total time is O(P(u;v)2E (jDvj + jIvj) + jV j + jEj). When jEj = O(jV j) (which is the case for both SNOMED CT and GO), the running time is O(Pv(jDvj + jIvj) + jV j + jEj). If we let c = Pv(jDjVvjj+jIvj) , then the running time is in O(c jV j + jEj). Based on the de nition of Dv and Iv, Pv(jDvj + jIvj) is the size of transitive closure pairs shown in Tables 2 and 4. Even though the worst-case running time is O(jV j2)(when c = jV j), c is a relatively small constant for ontological systems in practice. This is validated by our experimental results shown in Tables 2 and 4. For the latest version of SNOMED CT, c = 5;408;010 = 17:12, and for the latest 315;904 4

Results

4.1

Experimental Environment To detect redundant is-a relations from SNOMED CT and Gene Ontology, we ran the FEDRR method on a MacBook Pro running the Mac OS X Yosemite with 16 GB RAM and Intel Core i7 processor. FEDRR was implemented in Java programming language based on JDK7. 4.2

Redundant is-a relations in SNOMED CT

We ran the FEDRR method on 5 versions of SNOMED CT (US edition) from 2013 to 2015 dated on 2013-03-01, 2013-09-01, 2014-03-01, 2014-09-01, and 201503-01. Table 2 summarizes the result of each version including numbers of concepts, is-a relations, and transitive closure pairs (TC), and number of redundant is-a relations (RR); percentage of redundant is-a relations (RR%) among transitive closure pairs; and computing time in milliseconds to detect redundant is-a relations. For example, for the 2015-03-01 version, there were 315,904 concepts, 467,799 is-a relations, 5,408,010 transitive closure pairs, and 235 redundant is-a relations; the percentage of the redundant is-a relations among the transitive closure pairs is 0.00435%; and it took about 15 seconds to complete. For each version, it only took a few seconds to identify all the redundant is-a relations, indicating the e ciency of FEDRR.

Redundant is-a relations in Gene Ontology We ran the FEDRR method to detect redundant is-a relations in 10 versions of Gene Ontology from 2014-08-01 to 2015-05-01 updated monthly. Table 4 summarizes the basic results of each version. For instance, for the 2015-05-01 version, there were 42,979 concepts, 71,954 is-a relations, 557,550 transitive closure pairs, and 1,609 redundant is-a relations; the percentage of the redundant is-a relations among the transitive closure pairs is 0.2886%; and it took 1,538 milliseconds to complete. As the number of concepts and is-a relations were increasing, the number and percentage of redundant is-a relations (RR) were monotonically increasing every month and increased more than twice from the 2014-08-01 version (497; 0.0961%) to the 2015-05-01 version (1,609; 0.2886%). For each version, it only took a couple of seconds to identify all the redundant is-a relations, indicating the e ciency of FEDRR.

Evaluation

Even though in most cases redundant edges should be removed, in some cases the redundancy is caused by a mistake of an edge along the indirect path. For example, in Fig. 5, the assertion that \Bilateral congenital dislocation of hip" is-a \Congenital dislocation of right hip" is most likely in error. This is because a concept involving \bilateral" should not be a subclass of a concept of limited laterality: \right" (but not \left"). Removing this edge would have automatically eliminated the redundancy of the detected relation.

To evaluate the performance of FEDRR's detection of redundant is-a relations, a random sample of 30 redundant relations from SNOMED CT (2015-03-01 version) and 50 from GO (2015-05-01 version) were selected and manually reviewed by two human annotators. One annotator was asked to manually verify if the redundant hierarchical relations identi ed by FEDRR are correct. The other annotator was asked to review each redundant relation and provide on feedback if the redundant relation (direct edge) should be removed or an edge in the indirect path should be removed.

The rst annotator veri ed that all of the redundant hierarchical relations identi ed by FEDRR are correct, that is, 100% accurancy. Table 6 shows the feedback of the second annotator. Among 30 redundant is-a relations in SNOMED CT, 24 (80%) should have direct edge removed, and 6 (20%) should have indirect edge removed. Among 50 redundant is-a relations in GO, 45 (90%) should have direct edge removed, and 5 (10%) should have indirect edge removed.

Discussions

Related Work There has been related work on exploring redundant relations in biomedical ontologies or terminologies [22{24]. Bodenreider [ 22 ] investigated the redundancy of hierarchical relations across biomedical terminologies in the Uni ed Medical language System. Di erent from this work, FEDRR focuses on developing a fast and scalable approach to detect redundant hierarchical relations in a single ontology.

Gu et al [ 23 ] investigated ve categories of possibly incorrect relationship assignment including redundant relations in the Foundational Model of Anatomy. The redundant relations were detected based on the interplay between the is a and other structural relationships (part of, tributary of, branch of). A review of 20 samples from possible redundant part of relations validated 14 errors, a 70% correctness. FEDRR di ers from this work in two ways. Firstly, FEDRR aims to provide an e cient algorithm to identify redundant hierarchical relations from large ontologies with 100% accuracy. Secondly, FEDRR can be used for detecting redundant relations in all DAG with the transitivity property.

Mougin [ 24 ] studied redundant relations as well as missing relations in GO. The identi cation of redundant relations was based on the combination of relationships including is a and is a, is a and part of, part of and part of, and is a and positively regulates. FEDRR's main focus is to provide a generalizable and e cient approach to detecting redundant hierarchical relations in any ontology, which has been illustrated by applying it to two of the largest biomedical ontologies SNOMED CT and GO. Moreover, the redundant hierarchical relations detected by FEDRR were evaluated by human experts, while only number of redundant relations was reported in [ 24 ] without human annotator's validation. 6

Conclusion

Detecting and removing redundant relations is an important quality improvement task for biomedical ontologies because non-redundancy is the basic premise of all semantic measures derived from ontological structures, such as semantic distance between concepts and ontology mapping and alignment. We introduced FEDRR for fast and exhaustive detection of all redundant hierarchical relations in ontological hierarchies. Our algorithm runs in linear time to the size of the ontological structure in practice.

Using FEDRR, we performed systematic and exhaustive search of all redundant relations in two of the largest ontological systems in biomedicine: SNOMED CT and Gene Ontology. The algorithmic core of FEDRR is easy to implement and extremely e cient. In our extensive experiments on real-world, largest ontological structures, it took less than 20 seconds for FEDRR to process SNOMED CT and Gene Ontology.

With these results, we believe that FEDRR is production ready. After creating a user guide and a technical guide, with an associated visualization interface, we intend to release it as an open-source tool to the ontological engineering community in the near future.

Acknowledgments. We thank Shiqiang Tao for the SVG template which helped the rendering of the diagrams used for this work. The project described was supported by the National Center for Advancing Translational Sciences, UL1TR000117, and in part by the Software Solutions of Applied Research and Technology Program at Western Kentucky University. The content is solely the responsibility of the authors and does not necessarily represent the o cial views of the NIH.

References

1. Cui L , Tao S , Zhang GQ . A Semantic-based Approach for Exploring Consumer Health Questions Using UMLS . AMIA Annual Symp Proc 2014 , pp. 432 - 441 .

2. Zhang GQ , Cui L , Lhatoo S , Schuele S , Sahoo S. MEDCIS : Multi-Modality Epilepsy Data Capture and Integration System . AMIA Annual Symp Proc 2014 , pp. 1248 - 1257 .

3. Jayapandian C , Chen CH , Dabir A , Lhatoo S , Zhang GQ , Sahoo S. Domain Ontology As Conceptual Model for Big Data Management: Application in Biomedical Informatics . International Conference on Conceptual Modeling, Atlanta, 2014 (in press).

4. Bodenreider O. Biomedical ontologies in action: role in knowledge management, data integration and decision support. Geissbuhler A , Kulikowski C , editors. IMIA Yearbook of Medical Informatics 2008. Methods Inf Med 2008 ; 47 ( Suppl 1 ): 67 - 79 .

5. Couto , Francisco M., Mario J. Silva , and Pedro M. Coutinho . Measuring semantic similarity between Gene Ontology terms . Data & knowledge engineering 61 , no. 1 ( 2007 ): 137 - 152 .

6. Giunchiglia F , Autayeu A , Pane J , S-match: an open source framework for matching lightweight ontologies Semantic Web , 3 ( 3 ) ( 2012 ), pp. 307 - 317

7. Donnelly K. SNOMED-CT : The advanced terminology and coding system for eHealth . Stud Health Technol Inform Vol. 121 , pages 279 - 90 , 2006 .

8. Bodenreider , O. The uni ed medical language system (UMLS): integrating biomedical terminology . Nucleic acids research , 32 ( suppl 1 ), D267 - D270 , 2004 .

9. Gene Ontology Consortium. The Gene Ontology (GO) database and informatics resource . Nucleic acids research 32.suppl 1 : D258 - D261 , 2004 .

10. Min H , Perl Y , Chen Y , Halper M , Geller J , Wang Y . Auditing as part of the terminology design life cycle . J Am Med Inform Assoc 2006 ; 13 ( 6 ): 676 - 690 .

11. He Z , Ochs C , Agrawal A , Perl Y , Zeginis D , Tarabanis K , Elhanan G , Halper M , Noy N , Geller J. A family-based framework for supporting quality assurance of biomedical ontologies in BioPortal . In AMIA Annual Symposium Proceedings 2013 , pp. 581 - 590 .

12. Tao S , Cui L , Zhu W , Sun M , Bodenreider O , Zhang GQ . Mining Relation Reversals in the Evolution of SNOMED CT Using MapReduce . AMIA Joint Summits on Translational Science 2015 , pp. 46 - 50 .

13. Ceusters W. Applying Evolutionary Terminology Auditing to SNOMED CT . AMIA Annu Symp Proc. 2010 Nov 13 ; 2010 : 96 - 100 .

14. Hartung M , Grob A , Rahm E. COnto-Di : generation of complex evolution mappings for life science ontologies . J Biomed Inform . 2013 Feb; 46 ( 1 ): 15 - 32 .

15. Kirsten T , Gross A , Hartung M , Rahm E. GOMMA: a component-based infrastructure for managing and analyzing life science ontologies and their evolution . J Biomed Semantics. 2011 Sep 13 ; 2:6 . doi: 10 .1186/2041-1480-2-6.

16. Jiang G , Chute CG . Auditing the semantic completeness of SNOMED CT using formal concept analysis . J Am Med Inform Assoc 2009 ; 16 ( 1 ): 89 - 102 .

17. Zhang GQ and Bodenreider O. Using SPARQL to Test for Lattices: application to quality assurance in biomedical ontologies . The Semantic Web-ISWC 2010 , pages 273 - 288 , 2010 .

18. Zhang GQ and Bodenreider O. Large-scale, exhaustive lattice-based structural auditing of SNOMED CT. American Medical Informatics Association (AMIA) Annual Symposium , pages 922 - 926 , 2010 .

19. Zhang GQ , Zhu W , Sun M , Tao S , Bodenreider O , Cui L . MaPLE: A MapReduce Pipeline for Lattice-based Evaluation of SNOMED CT . IEEE International Conference on Big Data , 2014 ; 754 - 9 .

20. Sedgewick R , Wayne K , Algorithms (4th ed.), Addison-Wesley Professional , pp. 661 - 666 , ISBN 9780321573513, 2011 .

21. Cormen , Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein , Cli ord ( 2001 ), Section 22 .4: Topological sort , Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill , pp. 549 - 552 , ISBN 0-262-03293-7.

22. Bodenreider O. Strength in numbers: exploring redundancy in hierarchical relations across biomedical terminologies . AMIA Annual Symp Proc 2003 , pp. 101 - 105 .

23. Gu HH , Wei D , Mejino JLV , and Elhanan G. Relationship auditing of the FMA ontology . Journal of biomedical informatics 42 (3) : 550 - 557 , 2009 .

24. Mougin F. Identifying redundant and missing relations in the gene ontology . Studies in health technology and informatics 210 : 195 - 199 , 2014 .