Search

The UMLS is a rich collection of biomedical concepts which are connected by semantic relations. Using transitively associated information for knowledge discovery has been shown to be effective for many applications in the biomedical field. Although there are a few tools and methods available for extracting transitive knowledge from the UMLS, they usually have major restrictions on the length of transitive relations or on the number of data sources.To overcome these restrictions, the web platform onGrid was developed to support efficient path queries and knowledge discovery on the UMLS. This platform provides several features such as converting natural language queries into UMLS concepts, performing efficient queries, and visualizing the result paths. It also builds relationship and distance matrices for two sets of biomedical terms, making it possible to perform effective knowledge discovery on these concepts.onGrid can be applied to study biomedical concept relations between any two sets or within one set of biomedical concepts. In this work, onGrid is used to study the gene-gene relationships in HUGO as well as disease-disease relationships in OMIM. By cross validating the results with external datasets, it is demonstrated that onGrid is very efficient to be used for conceptual-based knowledge discovery on the UMLS.onGrid is a very efficient tool for querying the UMLS for transitive relations, studying relationships between biomedical terms, and generating hypotheses. The online UMLS knowledge discovery platform has been tested on the BMI Netlab server (URL: https://netlab.bmi.osumc.edu/ongrid).

In recent years, graph pattern matching, approximate graph matching and dynamic subgraph indexing have become important graph analysis tools due to the emergence of many new applications such as computational biology and social networks analysis. In this work we investigate these three related problems.For the first problem, in previous existing models, each edge in the query pattern represents the same relationship, e.g., the two endpoint vertices have to be connected or the distance between them should be within a certain uniform threshold. However, real world applications may require edges representing different relationships or distances. Therefore, we introduce the flexible pattern matching model where a range [mine; maxe] is associated with an edge e in the query pattern, which means that the minimum distance between the matched endpoints of e is in the range of [mine; maxe]. A novel pattern matching algorithm is devised, which consists of several innovations including preprocessing the query pattern, two types of indices, and a top-k matches generation scheme.For the second problem, we study the problem of finding approximate matches of a query graph in a large database graph with (possible) missing edges. The SAPPER method is proposed, utilizing the hybrid neighborhood unit structures in the index. SAPPER also takes advantage of pre-generated random spanning trees and a carefully designed graph enumeration order.For the third problem, to the best of our knowledge, most subgraph indexing focuses on the static database graphs. However, in real applications, database graphs may change over time. Thus, we propose an indexing structure, BR-index, for large dynamic graphs. The large database graph is partitioned into a set of overlapping index regions. Features (small subgraphs) are extracted from these regions and used to index them. The updates to G can be localized to a small number of these regions. To further improve the efficiency in updates and query processing, several novel techniques and data structures are invented, which include feature lattice, maximal features, and overlapping regions.Extensive empirical studies have been conducted to show the effectiveness and efficiency of our indices and methods.