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

University Of Virginia Main Campus, Charlottesville VA

Investigators

Abstract

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.