This research addresses combinatorial and algorithmic problems related to searching and matching of strings. The main emphasis of the research is on problems that are recurrent in the vast and growing domain of molecular sequence analysis, but the results of this study will benefit various other fields.
Specific issues addressed include the efficient (i.e., suitable for very fast serial as well as parallel access) structuring of large sequence databanks; techniques for the identification of various regularities in strings; schemes for the efficient compaction and retrieval of strings and higher structures; variants of string searching and comparisons problems; and some typical optimization problems in molecular biology.
Such issues are explored within both serial and parallel computational environments, from a deterministic, as well as, a probabilistic perspective.
This research represents in part a natural extension of our work under a previous NSF sponsorship. It also purports to cover some of the foundational aspects emerged in the course of a larger interdisciplinary effort currently carried out by the PI's in cooperation with molecular biologists and biochemists.
CS Annual Report - 19 APR 1996