CRII: CIF: Model-based Compression of Biological Sequences

随着高通量基因组测序技术的日益广泛应用，生物序列数据量的增长速度远远快于存储介质成本的下降速度。为了避免使可用存储容量饱和，必须对此类数据进行高比率压缩。生物序列是在进化过程中通过突变过程产生的，包括替换、插入、删除和复制。虽然这些过程塑造了基因组序列的统计特性，并在确定哪种压缩方法将提供更好的性能方面发挥了关键作用，但目前的方法并未考虑到这些过程。该项目的目标是通过开发和利用接近基因组序列生成过程的突变模型，提供一种有原则的生物数据压缩方法。该项目的主要研究重点是：1)确定生物序列可压缩性的基本极限；2)开发和评估接近这些极限的编码和解码算法。识别压缩的限制依赖于开发组合和随机字符串编辑模型，这些模型代表了通过基因组突变产生的序列。然后从信息论的角度研究这些模型，以确定它们的组合能力和随机能力，从而提供基因组序列可压缩性的界限。第二个推力利用突变模型（如重复结构）产生的统计特性来开发有效的压缩工具。除了改进压缩方法外，这些研究方向的成功将增强我们对复杂序列生成过程的理解，使生成忠实的合成数据成为可能，并有助于定量研究突变在产生新的生物功能中的作用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

With the increasingly widespread use of high-throughput genome sequencing, the amount of biological sequence data is growing at a rate much faster than the decrease in the cost of storage media. To avoid saturating available storage capacity, such data must be compressed at a high ratio. Biological sequences are created over the course of evolution by mutation processes, including substitution, insertion, deletion, and duplication. While these processes shape the statistical properties of genomic sequences and play a critical role in determining which compression approaches will provide improved performance, they are not taken into account by current methods. The goal of this project is to provide a principled approach to biological data compression by developing and leveraging mutation models that approximate the generation process of genomic sequences.The main research thrusts of the project are: 1) determining the fundamental limits of the compressibility of biological sequences; and 2) developing and evaluating encoding and decoding algorithms that approach these limits. Identifying the limits of compression relies on developing combinatorial and stochastic string-editing models that represent sequence generation through genomic mutations. These models are then studied from an information-theoretic point of view to determine their combinatorial and stochastic capacities, thus providing bounds on the compressibility of genomic sequences. The second thrust leverages the statistical properties arising from mutation models, such as repeat structures, to develop efficient compression tools. In addition to improving compression methods, the success of these research directions will enhance our understanding of complex sequence generation processes, enable the generation of faithful synthetic data, and facilitate the quantitative study of the role of mutations in generating novel biological functions.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.