CAREER: Model-based compression and probabilistic analysis of non-Markovian sequences

该项目旨在基于概率模型为大型复杂数据开发有效的数据压缩和分析方法，从而促进算法设计、分析和评估。该项目提出了能够准确表示此类数据的灵活概率模型。这些模型将用于设计可伸缩的分析和压缩算法，确定其基本限制，并提供可证明的性能保证。特别是，该项目将研究用于在大型数据存储系统中消除冗余的数据压缩算法，传统的压缩方法在计算上是不可行的。它还将为基因组序列开发新的估计和测试算法，其中现有的概率模型限制太大，无法忠实地表示其内部统计结构。该项目考虑信息论和统计信号处理方面的基本问题，并有可能通过对基因组数据进行更准确的统计分析，为公共卫生作出贡献。研究成果将被纳入一系列教育活动，包括开发交互式和可访问的在线课程，这些课程将强调数学、工程和科学之间的联系，并促进基于原则的基于模型的方法来解决工程和科学问题。该项目有两个研究重点，它们对应于两个关键设置，其中传统的序列概率模型，最常见的是马尔可夫模型，以及独立和同分布（iid）模型及其相关方法，都不适用。第一个重点是具有远程冗余的序列，即在大距离上出现的长重复块，在太字节规模的数据存储系统中很常见。该项目将为具有近似重复的源开发生成数据驱动模型，建立压缩它们的信息论界限，并开发和优化压缩算法，包括分布式源的压缩和具有未知参数的源的通用压缩。第二个重点是进化来源，即那些通过连续编辑产生数据的来源，用于模拟基因组数据的生成过程。参数估计、假设检验和演化源未来行为的预测等问题将通过制定一个随机逼近框架来解决，其中分析了序列的渐近和有限时间行为。由此产生的分析方法和算法将用于研究生物信息学中的几个问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project aims to develop efficient data-compression and analysis methods for large and complex data based on probabilistic models that will facilitate algorithm design, analysis, and evaluation. The project advances flexible probabilistic models capable of accurately representing such data. These models will be leveraged to design scalable analysis and compression algorithms, establish their fundamental limits, and provide provable performance guarantees. In particular, the project will study data-compression algorithms for removing redundancy in large-scale data-storage systems, where traditional compression methods are computationally infeasible. It will also develop novel estimation and testing algorithms for genomic sequences, where existing probabilistic models are too restrictive to faithfully represent their internal statistical structure. The project considers fundamental problems in information theory and statistical signal processing and has the potential to contribute to public health through more accurate statistical analysis of genomic data. The research results will be incorporated in a range of educational activities, including developing interactive and accessible online courses that will emphasize connections between mathematics, engineering, and science, and promote a principled model-based approach to solving engineering and scientific problems. The project has two research thrusts, which correspond to two critical settings in which conventional probabilistic models of sequences, most commonly Markov as well as independent and identically distributed (iid) models, and their associated methods, are inapplicable. The first thrust focuses on sequences with long-range redundancy, i.e., with long repeated blocks appearing at large distances, common in terabyte-scale data storage systems. The project will develop generative data-driven models for sources with approximate repeats, establish information-theoretic bounds on compressing them, and develop and optimize compression algorithms, including compression of distributed sources and universal compression for sources with unknown parameters. The second thrust focuses on evolutionary sources, i.e., those that produce data through consecutive edits, used to model the generation process of genomic data. Problems such as parameter estimation, hypothesis testing, and the prediction of future behavior for evolutionary sources will be addressed by formulating a stochastic approximation framework in which asymptotic and finite-time behavior of sequences are analyzed. The resulting analysis methods and algorithms developed in this thrust will be used to study several problems in bioinformatics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.