Methods: A LALR strategy was applied to 7,763 LOINC and 2,050 SNOMED procedure terms using a common set of defining relationships taken from the LOINC data model. Candidate value restrictions were derived by lexically comparing the procedure's name with other terms contained in the reference SNOMED topography, living organism, function, and chemical axes. These candidate restrictions were reviewed by a domain expert, transformed into terminologic definitions for each of the terms, and then algorithmically classified.

Results: The authors successfully defined 5,724 (73%) LOINC and 1,151 (56%) SNOMED procedure terms using a LALR strategy. Algorithmic classification of the defined concepts resulted in an organization mirroring that of the reference hierarchies. The classification techniques appropriately placed more detailed LOINC terms underneath the corresponding SNOMED terms, thus forming a complementary relationship between the LOINC and SNOMED terms.

Discussion: LALR is a successful strategy for merging overlapping terminologies in a test case where both terminologies can be defined using the same defining relationships, and where value restrictions can be drawn from a single reference hierarchy. Those concepts not having lexically suggested value restrictions frequently indicate gaps in the reference hierarchy.

We believe that pragmatic solutions to our terminology problems may be found in hybrid solutions that leverage the best characteristics of each approach. Here we describe an evaluation of a “lexically assign, logically refine” (LALR) strategy that combines the efficiency of linguistically based approaches with the precise semantics of description logic. We leverage lexical algorithms and language's inherent structure to propose relationships for terms in a terminology. These proposed definitions are then reviewed and refined by domain experts, and subsequently loaded into a description logic classifier. The LALR strategy allows us to efficiently and formally define terms to the extent pragmatically possible with the concomitant benefits of decreased ambiguity and increased precision available to represent medical observations, diagnoses, and patient management plans.

Using our hybrid approach, we seek to demonstrate the practicality of a LALR strategy that we believe can scale to answer the terminologic challenges posed by the Computer-Based Patient Record Institute⁷ and the Institute of Medicine.⁸ Although our test case focuses on the semi-automated merging of overlapping terminologies, we believe that the LALR approach can be generally applied to a wide variety of terminologic challenges.

We selected the SNOMED (Systematized Nomenclature of Human and Veterinary Medicine) laboratory procedures⁹ and the LOINC (Logical Observation Identifier Names and Codes) laboratory procedures¹⁰ as our test case because the terminologies are individually important to our respective organizations, and the two terminologies have complementary strengths.

SNOMED III is the foundation of Kaiser Permanente's Convergent Medical Terminology project,¹¹ and has been shown to have broad content coverage in many clinical domains.^12,13 Despite SNOMED's broad coverage of medical concepts, it is missing many of the detailed laboratory terms necessary for standardizing reporting of laboratory information, although it provides a hierarchical classification of laboratory procedures.

The LOINC database contains finely detailed test result identification codes suitable for standardized reporting of laboratory information and has been endorsed by the American Clinical Laboratory Association (ACLA). ACLA recommends that all members report laboratory results using LOINC codes (ACLA members account for approximately 70% of the volume of tests performed in the United States). Additionally, the Health Care Financing Administration is constructing ICD-10-PCS codes using LOINC terms.¹⁴

Despite LOINC's finely detailed identification codes and consensus regarding its adoption, LOINC lacks a hierarchical organization of those identification codes. We chose to test our LALR strategy using LOINC and SNOMED because we felt that a combination of LOINC and SNOMED could produce a comprehensive strategy for representing detailed laboratory terms as well as appropriately classify those terms.

Figure 1 The LOINC (Logical Observation Identifier Names and Codes) data model. (See the Background section for details.)

Lexical Techniques Lexical algorithms typically perform an initial normalization process on the terms to be compared in an attempt to abstract away from lexical (syntactic, morphologic, and orthographic) variation in terms.^2,5,6,18,19 The process may involve breaking each string into its constituent words and morphemes; lower-casing each word; removing punctuation, stop words, and duplicate words; and sorting the words in alphabetical order (e.g., the term “Cell count of synovial fluid with differential count” would become “cell count differential fluid synovial”).

More sophisticated normalization techniques attempt to convert each word to its canonical uninflected form (e.g., “treats” or “treated” becomes “treat”),^5,18 expand abbreviations,⁵ attempt to correct spelling errors,²⁰ and substitute preferred terms for synonyms (e.g., “kidney” becomes “renal”).^2,5,21 Rocha et al.^18,19 lexically compared normalized word fragments (digrams) using a similarity function. Digram comparisons break each word into fragments of two letters each for comparison. For example, the word “morphemic” would be broken into the fragments mo, or, rp, ph, he, em, mi, and ic for comparison with the digrams from another word. This technique is less sensitive to minor morphologic variations in words introduced by mis-spellings or other normal variations in morphology. Digrams are created algorithmically and do not require any knowledge about word formation rules, and do not rely upon the existence of affix dictionaries.

Following the normalization process, terms are compared using various techniques such as exact normalized string matching, the Longest Common Substring algorithm,²² or a similarity scoring approach.¹⁸ Many of these techniques are included in the National Library of Medicine's lexical variant generation (lvg) tools, which are available to anyone who has signed the UMLS license agreement.²³

Logic-based Techniques Logic-based techniques are used to formally define concepts and to map and classify terms based on similarities of their definitions.^24,25,26,27 So, for example, if two distinct and lexically unrelated terms each define a type of laboratory procedure that measures sodium, the two terms will be appropriately classified together. There has been a general trend in terminology research to make more explicit the definition of medical concepts,^{4,19,27,28,29} both to disambiguate concepts and to facilitate automated terminology merging efforts. The Canon group has argued for a medical-concept representation language containing semantic types for each concept and a network of general medical concepts in which implicit relations between elements are made explicit.⁴

There has been an evolution over time in the formal representation of medical concepts. An early effort to abstract away from specific terms to term representations for use in modeling general medical language was developed by Evans in the MedSORT project.²⁸ To represent concepts, MedSORT required both a semantic classification scheme and rules that determined how elements in the classification scheme might combine. Masarie et al.²⁵ defined concepts from several vocabularies using a frame-based system, where the definitions were based on an analysis of the terms to be merged. Cimino et al.²⁷ have used a semantic network for defining the concepts in the Columbia-Presbyterian MED vocabulary. Their network is a notation for representing conceptual entities and links between them, allowing the storage of factual knowledge that can be intensional (describing the entities themselves) and extensional (describing how entities are related to other entities), and includes a classification hierarchy. Description logic, which defines concepts based on formal logic theory, was developed to make explicit the semantics of frame-based systems^* and semantic networks while retaining an emphasis on taxonomic structure as an organizing principle.³⁰

Campbell et al.³ have previously argued that formal logic can provide a framework for formalizing the representation of medical concepts. It is well recognized that there is a tradeoff in expressiveness and tractability of term classification that has to be considered when using formal logic.^31,32 Rector et al.³³ have argued for a more expressive formalism, claiming that worst-case computational complexity is an inappropriate guide to the choice of formalism. On the other hand, several description logics have been defined that support less then full first-order logic, and offer complete and sound algorithms for the classification of terms defined by the logic.^34,35 Such a subset, used in this study, is supported by K-Rep, a description logic classification and terminology authoring system developed by researchers at IBM.³⁶ Expressiveness is deliberately constrained in the K-Rep system so that algorithmic classification is guaranteed to be sound and complete. While this constraint may pose a limitation in the definition of certain concepts requiring, for example, a logical “or” or a logical “not,” this was not an issue in the definition of the concepts in this study, all of which could be fully defined. The explicit representation of medical concepts in a description logic enables the formal determination of the expressiveness and tractability of a particular representational syntax.

Logic-based classification algorithms typically organize a set of concepts into a taxonomy based on axiomatic term definitions. As an initial step, the defining characteristics for the set of concepts to be classified must be determined. A LOINC concept, as shown in Figure 1, is defined by its analyte, measured property, measurement time aspect, specimen, scale, and method. Cimino et al.²⁷ defined laboratory specimens, laboratory tests, and medications based on relationships taken from the UMLS Semantic Network.³⁷ Once the defining relationships have been determined, appropriate value restrictions for each defining relationship must be assigned. These values can be determined by a combination of manual assignment, lexical suggestion, or logical inheritance using the methods described above.

Once concepts are defined, logic-based classification algorithms are employed.^27,32,34,35 Cimino et al.^27,38 have provided a description of their classification algorithms, which are used to deepen a hierarchy and to identify the most appropriate location for a given term in a given classification hierarchy. Description logic classification algorithms are discussed in more detail by Fitting.³⁹

Prior experience with logic-based techniques suggests that these methods may enhance results achievable with lexical techniques alone. Here we present our evaluation of a specific strategy for combining logic-based and linguistic-based techniques: Lexically Assign, Logically Refine (LALR).

Figure 3 Algorithmic classification based on measured component. Given the analyte hierarchy for the SNOMED Function Axis and the concept definitions shown, the resulting SNOMED Procedure hierarchy is automatically generated. (Concept HLA-A1-Measurement_L-4718-3 (more ...)

Lexical techniques were used to suggest value restrictions for the SNOMED test data set. The set of SNOMED concepts was cross-referenced with each of the other SNOMED axes looking for potential lexical matches that might provide an appropriate restriction for any of the defining relationships. Prior to comparison, term strings in the SNOMED test data set and in the target SNOMED axis were normalized (including all SNOMED synonyms) using the norm program available from the National Library of Medicine.²³ A detailed description of this process is provided by McCray et al.,⁵ and includes breaking each string into its constituent words, lower-casing each word, removing punctuation and stop words, sorting the words in alphabetical order, and conversion of each word to its uninflected form. In addition, certain patterns, such as “oscope/oscopy” were identified as high-yield for detecting matches. Comparison of the normalized concepts included partial phrase matching (e.g., “Alkaline phosphatase isoenzymes measurement” would pair with “Alkaline phosphatase isoenzyme”).

Potential matches were placed into a report for manual review. A single reviewer (RHD) examined the report to determine whether or not the lexically suggested target SNOMED term would be accepted as a value restriction for the corresponding test SNOMED concept, and to indicate the defining relationship for the restriction.

Our primary focus was on defining each concept at least with respect to its measured component (i.e., determining the concept filling the HAS-ANALYTE value restriction) because procedure names frequently contain some lexical variant of the substance being analyzed, thereby greatly enabling a lexical approach, and because a classification based on measured components results in a clinically sensible hierarchical structure.

Figure 2 A sample concept defined according to the LOINC model (of Figure 1). The middle section shows the concept defined in conceptual graph notation, while the bottom section shows a similar definition in description logic syntax.

All target SNOMED axes (i.e., all SNOMED axes that contain value restrictions for concepts in the SNOMED and LOINC test data sets), are also defined in the description logic and included in the terminology database. In general, these axes are comprised of “primitive” concepts—concepts that cannot be fully defined, and are instead placed into a manually constructed hierarchy. The hierarchical structure of these axes exist within the SNOMED database, and was reflected in the description logic via the specification of “IsA” relationships. For example, Figure 3 shows a representation of the SNOMED Function Axis, in which HLA-A-Antigen-NOS_F-C4100 IsA HLA-Antigen-NOS_F-C4000.

A detailed description of classification algorithms similar to those used by K-Rep for this report have previously been published.³² The initial step involves parsing the textual concept definitions for syntactic correctness. Next comes a process of normalization that converts the definitions into a standard form. This is followed by completion, during which value restrictions are inherited from the transitive closure of all parent concepts. These inherited restrictions are logically intersected with local restrictions contained in the concept definition to form a completely explicit concept definition. From there, a concept is automatically integrated into the taxonomy by comparing its definition with definitions of concepts already in the taxonomy. The process of determining a new concept's location in the taxonomy is called classification. When one concept is more general than another, the first concept properly subsumes the second. This can arise if the restriction of a defining relationship of one concept subsumes the restriction of the same relationship of another concept, as represented in the target SNOMED axis, or when the second concept's definition expresses additional constraints beyond those of the first concept. When two concepts are equivalent, they subsume one another, but neither properly subsumes the other. For one concept to subsume another, every value restriction of the first concept must also be true of the second concept.

Table 1 Lexical Determination of the Measured Components or Analytes of LOINC and SNOMED Concepts

Previously, SNOMED concepts had not been cross-referenced to their corresponding analytes. Lexical algorithms in this study suggested 3,852 restrictions for the HAS-ANALYTE relationship, of which 1,151 (30%) were accepted as valid, resulting in 56% of the SNOMED concepts being assigned a HAS-ANALYTE value restriction (Table 1). These restrictions were found in several SNOMED axes, including Topography (e.g., Eosinophil, T-C1340), Function (e.g., 11-Deoxycortisol, F-B2480), Living Organisms (e.g., Bordetella pertussis, L-12801), and Chemicals (e.g., Acetaminophen, C-60130). 472 restrictions for the HAS-SYSTEM role and 45 restrictions for the HAS-SCALE-TYPE role were also determined. No restrictions for the HAS-PROPERTY, HAS-TIME-ASPECT, or HAS-METHOD-TYPE roles were found using our lexical approach.

Overall, of the 9,813 concepts in the combined SNOMED and LOINC test set, 6,875 (70%) had a restriction for the HAS-ANALYTE relationship determined by lexical techniques.

Faulty classification can result from errors in the reference hierarchy. This is illustrated in Figure 4. In this example, Androstenedione_F-B2820 is modeled as a child of Androgen-NOS_F-B2800, but should also be modeled as a child of 17-Ketogenic-steroids_F-B2420. Making this manual correction in the Function Axis will automatically correct the classification of concepts in the Procedure Axis.

Figure 4 Faulty classification due to reference hierarchy. Classification errors in the reference Function Axis are mirrored in the automatically generated Procedure Axis. In this case, Androstenedione_F-B2820 also IsA 17-Ketogenic-steroids_F-B2420. Making (more ...)

When two concepts measure the same component (i.e., have the same restriction for the HAS-ANALYTE relationship), the determination of the parent-child relationship is determined by the other defining relationships and value restrictions. More formally, if one concept is more general than another, the first concept is said to properly subsume the second. In such a case, the second concept's definition expresses additional constraints beyond those of the first concept. In the hierarchy, the second concept will appear as a child of the first concept. This is shown in Figure 5.

Figure 5 Classification of laboratory procedures measuring the same substance. When one concept is more general than another, the first concept will properly subsume the second. Given the concept definitions shown, the resulting SNOMED Procedure hierarchy is (more ...)

Of the SNOMED procedures in the test database, 80% share some measured component with a LOINC concept, and as a result will acquire a LOINC concept as a child. Because the initial merge combines LOINC and SNOMED concepts into SNOMED Procedure categories, all LOINC concepts acquire a SNOMED parent. Of the LOINC concepts, 50% share some measured component with a SNOMED concept, and as a result will also be classified under a more granular SNOMED concept (as in Figure 5). The remaining LOINC concepts potentially can form a flat hierarchy and an algorithm similar to that used by Cimino et al.^27,38 can be used to deepen these areas. A flat hierarchy can also result where there are a number of specific tests without a more general test defined. This is shown in Figure 4, where the concept Hormone-measurement-NOS_P3-XFB has been created based on the structure of the reference hierarchy to deepen the Procedure hierarchy.

We found the LALR strategy works well for automatically merging overlapping terminologies if the terminologies to be merged can be logically defined using the same model (i.e., both terminologies can be defined using the same defining relationships), and if their value restrictions can be drawn from the same reference hierarchy. Key points in our approach are that concept definitions are expressed in a formal description logic, defining relationships are taken from a pre-established model (LOINC), lexical techniques are used in the determination of value restrictions, and value restrictions for the terminologies to be merged are drawn from the same reference terminology (SNOMED). Generalizing this approach outside the realm of laboratory procedures will rely on the presence of defining models for concepts in other domains, and a rich reference terminology that is likely to provide lexically suggested value restrictions for concepts in the terminologies to be merged.

Blois⁴¹ has described a hierarchical schema of the sciences, ranging from the low-level sciences (e.g., mathematics, chemistry, and physics), which lend themselves to formalization over a relatively small domain of possible values and can therefore be more precisely defined, to the more abstract sciences (e.g., psychiatry and social science), which in part are built up from the underlying sciences, and are less able to be precisely defined. This would suggest that the application of description logic and classification might inherently be easier to implement for certain domains (where concepts can be defined) than for other domains. Consistent with Blois's assertions are the emergence of models defining surgical procedures, human anatomy, and medications,^1,14,27,42 although models defining mental health, rehabilitation, and human disease states are also being developed.^14,43 The emergence of these models will support the extension of our methods outside the scope of laboratory procedures.

Within the LOINC database, concepts filling the HAS-PROPERTY relationship are drawn from the International Union of Pure and Applied Chemistry (IUPAC),⁴⁴ and those filling the HAS-SYSTEM relationship are drawn from ASTM E1238-94⁴⁵ and HL7 version 2.2.⁴⁶ Lexical techniques were then used to map these concepts to synonymous SNOMED concepts. If evolving terminologies were to be defined from the outset based on atomic SNOMED building blocks, subsequent merging efforts could be substantially decreased, not to mention the beneficial impact this might have on increasing the overall content coverage of SNOMED. Our test database contained 2,039 LOINC concepts that could not be lexically mapped to a SNOMED analyte. To allow these LOINC concepts to be fully defined, 590 new concepts were added to SNOMED 3.4 (Kent Spackman, personal communication). Such enhancements to the overall content coverage of SNOMED are likely to benefit subsequent applications of our approach.

Our methodology suggests the need for different manual tasks when modeling concepts that can be logically defined than when modeling those that cannot. The reference SNOMED hierarchies that furnished value restrictions (such as Chemicals, Living Organisms) are generally composed of “primitive” concepts, meaning concepts that are unable to be fully defined with defining relationships. Manual tasks may include hierarchy construction and refinement as well as the addition of new concepts. For those concepts that can be logically defined (such as laboratory procedures), manual tasks may be better directed at refining concept definitions, including the review of lexically suggested restrictions, and adding new reference terms where necessary to allow for expression of value restrictions. Emerging environments such as Gálapagos¹¹ will enable the comparison of manually and automatically generated hierarchies to cross validate both the term definitions and the structure of the reference hierarchies.

Cimino et al.³⁷ have previously described a set of terminology design criteria. While the use of description logic does add formalism to terminology, allowing for the greater fulfillment of these criteria, it also will require a consideration of the optimal balance between expressiveness and tractability (of classification), similar to such considerations in other areas of medical informatics and computer science in general.^32,47 Criteria for a healthcare terminology include, among others, the ideas of nonvagueness and nonredundancy. Nonvagueness is achieved when concepts in the terminology are complete in meaning. Redundancy exists when multiple terms for the same concept are added to the terminology as unique concepts. If the achievement of nonvagueness requires the expressive power of full first-order logic, then the automatic determination of redundancy can become intractable or undecidable. The emergence of a workable terminology that is applied to real clinical situations and to pooled clinical data should help illustrate these tradeoffs.

The authors thank Simon P. Cohn, MD, MPH (Kaiser Permanente Healthcare), and John E. Mattison, MD (Kaiser Permanente, Southern California Region), for their support of this work; Stephanie Lipow, of Lexical Technology, Incorporated, for her help with the lexical processing; the JAMIA reviewers for their detailed insightful comments; and the members of the Kaiser Permanente Interregional Convergent Medical Terminology group for their constant reminder that nothing is without controversy, and that through controversy comes convergence.