title: FEDRR: fast, exhaustive detection of redundant hierarchical relations for quality improvement of large biomedical ontologies.
abstract: BACKGROUND
  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). Each redundant relation represents a possibly unintended defect that needs to be corrected in the ontology quality assurance process. Detecting and eliminating redundant relations would help improve the results of all methods relying on the relevant ontological systems as knowledge source, such as the computation of semantic distance between concepts and for ontology matching and alignment.
  
  
  RESULTS
  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, inO(c·|V|+|E|) time, where |V| is the number of concepts, |E| is the number of the relations, andcis 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). 372 and 1609 redundant is-a relations were found in the 2015-09-01 version of SNOMED CT and 2015-05-01 version of GO, respectively. We have also performed FEDRR on over 190 source vocabularies in the UMLS - a large integrated repository of biomedical ontologies, and identified six sources containing redundant is-a relations. Randomly generated ontologies have also been used to further validate the efficiency of FEDRR.
  
  
  CONCLUSIONS
  FEDRR provides a generally applicable, effective tool for systematic detecting redundant relations in large ontological systems for quality improvement.
authors: Department of Computer Science, Western Kentucky University, Bowling Green, 42101 KY USA.
authors: Guangming
authors: G
authors: Xing
authors: Institute of Biomedical Informatics, University of Kentucky, Lexington, 40536 KY USA.
authors: Guo-Qiang
authors: GQ
authors: Zhang
authors: Institute of Biomedical Informatics, University of Kentucky, Lexington, 40536 KY USA ; Department of Computer Science, University of Kentucky, Lexington, 40506 KY USA.
authors: Licong
authors: 0000-0001-5549-8780
authors: L
authors: Cui
keywords: Dynamic programming; Gene ontology; Redundant relations; SNOMED CT; UMLS