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序列。该项目开发工具来解决编码理论和信息论中的经典问题，这些问题是研究的许多方面的基础。其中包括为具有符号成本的有限状态通信信道构建最佳代码，设计纠正多个插入和删除错误的最佳短长度代码，开发具有删除错误的通信信道容量渐近的高效编码技术，以及分析能够从多个噪声观测中重建序列的算法和代码。要么完全正确，要么在一个小的候选序列列表中。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.