CRII: III: Toward the Compression of Pangenomic DNA Sequence Data Using Context-Free Grammars

DNA序列数据在医学和农业等各个科学领域变得无处不在。然而，这些数据的数量和生成速度迅速超过了存储和分析能力。该项目旨在通过开发压缩DNA序列数据的新技术来解决存储和分析问题，以便可以直接对压缩数据进行分析。具体来说，该项目旨在压缩来自同一物种或泛基因组的DNA序列数据。除了降低数据存储成本和传输时间外，这将使泛基因组分析能够以前所未有的规模进行，这可以帮助研究人员寻求了解医学背景下复杂疾病的遗传基础，或作为农业定向育种努力目标的类似复杂性状。本项目的主要目标是开发压缩泛基因组DNA序列数据的新方法。其动机来自这样一个事实，即这些数据太大，无法存储未压缩的数据，而必须由研究界持续分析。这个项目解决了这个问题，它建立在使用上下文无关语法压缩字符串集合的初步工作的基础上，使压缩集合的字符串内容能够随时间更新。该项目的第一个目标是开发新的算法，以压缩同一物种的多个基因组，从而可以直接在压缩档案上进行搜索和计算。第二个目标是开发将序列读取映射到压缩档案的方法。第三个目标是开发压缩读的方法，方法是使用它们的映射将它们集成到压缩的存档中，同时启用搜索和计算。第四个目标是开发直接在压缩读档案上执行搜索的方法。第五个目标是在一个开源软件包中实现这些方法，其中包括一个供生物数据科学研究人员使用的应用程序编程接口。该项目将创新DNA序列数据压缩技术和一般数据压缩技术。它还将使整个行业和学术界的大规模基因组分析成为可能。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

DNA sequence data is becoming ubiquitous in various domains of science, such as medicine and agriculture. However, the volume of these data and the rate at which they are being generated is rapidly outpacing storage and analysis capabilities. This project aims to address both the storage and analysis issues by developing new techniques for compressing DNA sequence data such that analyses can be performed directly on the compressed data. Specifically, the project aims to compress collections of DNA sequence data from the same species, or pangenomes. In addition to reducing data storage costs and transmission times, this will enable the analysis of pangenomes at an unprecedented scale which could aid researchers seeking to understand the genetic basis of complex diseases in medical contexts, or similarly complex traits that are targets of directed breeding efforts in agricultural.The primary goal of this project is to develop new methods for compressing pangenomic DNA sequence data. The motivation comes from the fact that these data are too large to store uncompressed but must be continuously analyzed by the research community. This project addresses the issue by building on preliminary work that compresses collections of strings using context-free grammars in a manner that allows the string content of a compressed collection to be updated over time. The first aim of the project is to develop new algorithms for compressing multiple genomes of the same species in a manner that enables search and computation directly on compressed archives. The second aim is to develop methods for mapping sequencing reads to compressed archives. The third aim is to develop methods for compressing reads by using their mappings to integrate them into the compressed archive while enabling search and computation. The fourth aim is to develop methods for performing searches directly on compressed read archives. And the fifth aim is to implement these methods in an open-source software package including an Application Programming Interface for use by biological data science researchers. This project will innovate both DNA sequence data compression techniques and general data compression techniques. It will also enable pagenomic analyses at scale across industry and academia.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.