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

职业：非马尔可夫序列的基于模型的压缩和概率分析

• 批准号: 2144974
• 负责人: Farzad Farnoud
• 金额: $ 55.95万
• 依托单位: University of Virginia Main Campus
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2027-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2144974&HistoricalAwards=false
• 关键词: CAREER; Model; based; compression; probabilistic

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.

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