CRII: CIF: Model-based Compression of Biological Sequences

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

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.