CAREER: Combinatorial Algorithms for Pattern Discovery with Applications to Data Mining and Computational Biology

University Of California-Riverside, Riverside CA

Investigators

Abstract

The exponential growth of the web, the recent technological progresses in molecular biology, the launch of massive-scale digital library projects, and the ability of exchanging information at our fingertips, have all contributed to the creation of an unprecedented quantity of textual data in digital form. Plain or semi-structured text is still the most versatile format in which to exchange information and there is so much of this data that is likely that the large majority of it will never be read by anyone, unless the way in which we access information drastically improves. The major limiting factor in handling large textual datasets is typically related to space rather than time. When the amount of data is too large to be stored in main memory, computer scientists have to resort to algorithms capable of dealing with compressed representations of the data (called 'sketches' or 'indexes'). For textual data, the construction of the sketch typically involves keeping statistics on substrings or related associations or rules. The first set of objectives of this project is centered around a new sketch based on a novel family of gapped patterns. We are applying the new index to three selected problems: databases; data compression; and computational biology. In the second set of objectives we are extending the pattern discovery problem to two-dimensional matrices. The discovery problem associated with two-dimensional patterns has a wide spectrum of applications including the analysis of gene expression data, recommender systems and collaborative filtering, identification of web communities, load balancing, and discovery of association rules. The education goal of the proposal is to establish the algorithmic and the fundamental software development component of an interdisciplinary bioinformatics curriculum. Funds from this proposal are being used to enhance these activities through the development of new courses in computational genomics for in-depth training on individualized research topics. Since UCR is a minority-serving institution, this plan will also have an impact on the education of under-represented students.