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

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

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.