CIF: Small: Fundamental Limits of DNA-Based Storage

对数据存储的需求持续快速增长，给当前的数据中心带来了重大挑战，并激发了人们对新存储技术开发的极大兴趣。DNA是携带所有生物遗传信息的分子，由于其寿命长和信息密度高，已成为长期档案数据存储的有前途的介质。这种新的数据存储方法带来了独特的挑战。与典型的硬盘驱动器不同，数据位以有序的线性方式存储，在DNA上存储数据需要合成大量的DNA分子，然后在液体溶液中无序混合。这使得在存储之后可靠地阅读数据的过程明显更昂贵并且计算复杂。该项目的目标是了解DNA作为存储介质的基本限制和能力。特别是，本研究旨在描述成本、信息密度、阅读和写入速度以及可靠性之间的基本权衡，旨在开发新的编码策略，以释放这种创新方法的全部潜力。该项目将通过关注三个主要目标来调查DNA存储系统的基本限制。第一个目标是开发一个信息理论框架来正式分析这些系统。DNA存储系统将通过洗牌通道的抽象来建模，该通道捕获了这样一个事实，即在基于DNA的存储中，许多数据块被打乱顺序。这些信道的容量将根据不同的噪声模型和性能的最佳编码方案进行了研究。一个特别令人感兴趣的问题是如何设计容量最佳的索引策略，使数据的适当重新排序。由于合成长DNA链的成本是实际DNA存储的主要障碍，第二个研究目标将处理在许多非常短的DNA链上存储数据的系统，每个DNA链都太短，无法编码任何有意义的信息。因此，将提出在溶液中不同DNA分子的浓度中编码信息的新策略，并建立其基本能力。第三个研究目标将集中在与联合处理大量DNA序列相关的计算挑战。特别是，将建立存储容量和计算要求之间的基本权衡，以及最近在大规模序列比对算法的进步将被利用对计算效率的解码algorithm.This奖项反映了NSF的法定使命的发展，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

The demand for data storage continues to increase at a rapid pace, posing significant challenges to current data centers and spurring significant interest in the development of new storage technologies. DNA, the molecule that carries the genetic information of all living matter, has become a promising medium for long-term archival data storage due to its longevity and very high information density. This new approach to data storage presents unique challenges. Unlike typical hard drives, where data bits are stored in a well-ordered linear fashion, storing data on DNA requires the synthesis of a large number of DNA molecules that are then mixed out of order in a liquid solution. This makes the process of reliably reading the data after storage significantly more expensive and computationally complex. The goal of this project is to understand the fundamental limitations and capabilities of DNA as a storage medium. In particular, this research seeks to characterize basic tradeoffs between cost, information density, reading and writing speeds, and reliability, aiming to develop new coding strategies that can unlock the full potential of this innovative approach to data storage.The project will investigate the fundamental limits of DNA storage systems by focusing on three main objectives. The first objective is to develop an information theory framework to formally analyze these systems. DNA storage systems will be modeled via the abstraction of a shuffling channel, which captures the fact that, in DNA-based storage, many blocks of data are shuffled out of order. The capacity of these channels will be characterized under different noise models and properties of optimal coding schemes will be studied. A particular question of interest is how to design capacity-optimal indexing strategies that allow the proper reordering of the data. Since the cost of synthesizing long DNA strands is the main obstacle to practical DNA storage, the second research objective will deal with systems that store data on many very short DNA strands, each of which is too short to encode any meaningful information. For that reason, new strategies to encode information in the concentration of different DNA molecules in the solution will be proposed, and their fundamental capabilities established. The third research objective will focus on the computational challenges associated with the joint processing of a large set of DNA sequences. In particular, basic tradeoffs between storage capacity and computational requirements will be established, and recent algorithmic advances in large-scale sequence alignment will be leveraged towards the development of computationally efficient decoding algorithms.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.