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

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

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.