CIF: Medium: Coding Theory for DNA Storage: Synthesis, Retention, and Reconstruction

需要新的信息存储技术来适应现代社会收集和产生的日益增长的数据洪流。在过去的十年里，几个实验已经证明，脱氧核糖核酸(简称DNA)--携带生物遗传信息的分子--是一种潜在的可行存储介质。基于DNA的存储将具有许多吸引人的特征：前所未有的数据密度、不会过时的记录格式、数千年的归档耐用性以及轻松的数据复制。另一方面，DNA存储需要从根本上将数据编码成DNA序列的新方法，以使存储过程高效和可靠。该项目的目标有两个：(1)了解基于DNA的存储的效率、可靠性和信息密度的数学限制，以及(2)开发新的数据编码和解码算法，以帮助实现这些限制。该项目将为本科生和研究生提供一个鼓舞人心的研究机会，鼓励跨大学边界的团队合作和跨学科的合作。该项目侧重于编码方法，以解决DNA存储过程关键阶段的关键问题：高效的DNA序列合成，稳定的存储序列保留，以及可靠的数据检索和重建。具体目标是：(1)利用DNA记录过程的数学抽象，建立对DNA存储容量的基本信息论限制，(2)开发源代码编码技术，以最大限度地将数据编码为合成DNA序列阵列所需的时间，(3)设计编码算法，以有效地对合成DNA序列中允许的核苷酸模式实施约束，以确保其长期保留，以及(4)开发重建算法和纠错码，以从可能因核苷酸的插入、删除和替换而破坏的无序副本集合中恢复一组DNA序列。该项目开发工具来解决编码理论和信息理论中的经典问题，这些问题是研究的许多方面的基础。其中包括为有符号成本的有限状态通信信道构建最优码，设计纠正多个插入和删除错误的最优短码，开发渐近接近有删除错误的通信信道容量的高效编码技术，以及分析能够从多个噪声观测重建序列的算法和代码，无论是准确的还是在一小部分候选序列中。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

New information-storage technologies are needed to accommodate the growing deluge of data being collected and generated by modern society. In the past decade, several experiments have demonstrated that deoxyribonucleic acid (abbreviated DNA) – the molecule that carries the genetic information of living organisms – is a potentially viable storage medium. DNA-based storage would have many attractive features: unprecedented data density, a recording format that will not become obsolete, archival durability over thousands of years, and easy data replication. On the other hand, DNA storage requires fundamentally new methods for encoding data into DNA sequences to make the storage process efficient and reliable. The aim of the project is two-fold: (1) to understand the mathematical limits on the efficiency, reliability, and information density of DNA-based storage, and (2) to develop novel data-encoding and decoding algorithms to help achieve those limits. The project will provide a stimulating research opportunity for undergraduate and graduate students, encouraging teamwork across university boundaries and collaboration across disciplines.The project focuses on coding methods that address critical problems in the key stages of the DNA storage process: efficient synthesis of DNA sequences, stable retention of stored sequences, and reliable data retrieval and reconstruction. Specific objectives are: (1) establish fundamental information-theoretic limits on the storage capacity of DNA using mathematical abstractions of the DNA recording process, (2) develop source coding techniques to minimize the time needed to encode data into synthesized arrays of DNA sequences, (3) design coding algorithms to efficiently enforce constraints on the allowed nucleotide patterns in synthesized DNA sequences to ensure their long-term retention, and (4) develop reconstruction algorithms and error-correcting codes that can recover a set of DNA sequences from an unordered collection of copies that may be corrupted by insertions, deletions, and substitutions of nucleotides. The project develops tools to address classical problems in coding theory and information theory that underlie many aspects of the research. These include the construction of optimal codes for finite-state communication channels with symbol costs, the design of optimal short-length codes that correct multiple insertion and deletion errors, the development of efficient coding techniques that asymptotically approach the capacity of a communication channel with deletion errors, and the analysis of algorithms and codes that enable reconstruction of a sequence from multiple noisy observations, either exactly or within a small list of candidate sequences.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.