Shortest Path Edit Distance for Enhancing UMLS Integration and Audit

Expansion of the UMLS is an important long-term research project. This paper proposes Shortest Path Edit Distance (SPED) as an algorithm for improving existing source-integration and auditing techniques. We use SPED as a string similarity measure for UMLS terms that are known to be synonyms because they are assigned to the same concept. We compare SPED with several other well known string matching algorithms using two UMLS samples as test bed. One of those samples is SNOMED-based. SPED transforms the task of calculating edit distance among two strings into a problem of finding a shortest path from a source to a destination in a node and link graph. In the algorithm, the two strings are used to construct the graph. The Pulling algorithm is applied to find a shortest path, which determines the string similarity value. SPED was superior for one of the data sets, with a precision of 0.6.