Mining non-lattice subgraphs for detecting missing hierarchical relations and concepts in SNOMED CT.
OBJECTIVE
Quality assurance of large ontological systems such as SNOMED CT is an indispensable part of the terminology management lifecycle. We introduce a hybrid structural-lexical method for scalable and systematic discovery of missing hierarchical relations and concepts in SNOMED CT.


METHODS
All non-lattice subgraphs (the structural part) in SNOMED CT are exhaustively extracted using a scalable MapReduce algorithm. Four lexical patterns (the lexical part) are identified among the extracted non-lattice subgraphs. Non-lattice subgraphs exhibiting such lexical patterns are often indicative of missing hierarchical relations or concepts. Each lexical pattern is associated with a potential specific type of error.


RESULTS
Applying the structural-lexical method to SNOMED CT (September 2015 US edition), we found 6801 non-lattice subgraphs that matched these lexical patterns, of which 2046 were amenable to visual inspection. We evaluated a random sample of 100 small subgraphs, of which 59 were reviewed in detail by domain experts. All the subgraphs reviewed contained errors confirmed by the experts. The most frequent type of error was missing is-a relations due to incomplete or inconsistent modeling of the concepts.


CONCLUSIONS
Our hybrid structural-lexical method is innovative and proved effective not only in detecting errors in SNOMED CT, but also in suggesting remediation for these errors.
Department of Computer Science, University of Kentucky, Lexington, KY, USA.|Institute for Biomedical Informatics, University of Kentucky.
Licong
L
Cui
Institute for Biomedical Informatics, University of Kentucky.
Wei
W
Zhu
Institute for Biomedical Informatics, University of Kentucky.|Division of Biomedical Informatics, College of Medicine, University of Kentucky.
Shiqiang
S
Tao
National Library of Medicine, Bethesda, MD, USA.
James T
JT
Case
National Library of Medicine, Bethesda, MD, USA.
Olivier
O
Bodenreider
Institute for Biomedical Informatics, University of Kentucky.|Division of Biomedical Informatics, College of Medicine, University of Kentucky.
Guo-Qiang
GQ
Zhang
D057225:Data Mining / Q000379:methods*; D011785:Quality Assurance, Health Care; D013358:Subject Headings; D039061:Systematized Nomenclature of Medicine
SNOMED CT; non-lattice subgraph; ontology; quality assurance