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

网络的指数级增长，分子生物学的最新技术进步，大规模数字图书馆项目的启动，以及在我们的指尖交换信息的能力，都有助于以数字形式创造前所未有的文本数据量。纯文本或半结构化文本仍然是交换信息的最通用的格式，而且有如此多的数据，除非我们访问信息的方式得到极大的改进，否则大多数数据可能永远不会被任何人阅读。处理大型文本数据集的主要限制因素通常与空间而不是时间有关。当数据量太大而无法存储在主存储器中时，计算机科学家不得不求助于能够处理压缩数据表示的算法（称为“草图”或“索引”）。对于文本数据，草图的构造通常涉及保持子字符串或相关关联或规则的统计信息。这个项目的第一个目标是围绕一个新的草图，这个草图是基于一个新的缺口图案家族。我们将新索引应用于三个选定的问题：数据库；数据压缩;还有计算生物学。在第二组目标中，我们将模式发现问题扩展到二维矩阵。与二维模式相关的发现问题具有广泛的应用范围，包括基因表达数据的分析、推荐系统和协同过滤、web社区的识别、负载平衡和关联规则的发现。该提案的教育目标是建立跨学科生物信息学课程的算法和基本软件开发组成部分。这项提案的资金正用于通过开发计算基因组学的新课程来加强这些活动，以便对个性化研究课题进行深入培训。由于加州大学洛杉矶分校是一所为少数族裔服务的机构，这项计划也将对代表性不足的学生的教育产生影响。

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.