Collaborative Research: CIF: Small: Coded String Reconstruction Problems in Molecular Storage

合作研究：CIF：小型：分子存储中的编码串重建问题

• 批准号: 2008125
• 负责人: Olgica Milenkovic
• 金额: $ 23.15万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008125&HistoricalAwards=false
• 关键词: Collaborative; Research; CIF; Small; Coded

The problem of reconstructing text strings from their fragments or masses of fragments is of focal importance in computational biology as current DNA and protein sequencing platforms are unable to read the content of long strings that denote protein/gene sequences. One prototypical example of string reconstruction arises in DNA assembly: there, one creates multiple copies of the same long string and cuts the copies to read out short overlapping substrings that can be put together by matching their prefixes and suffixes. The reconstructed string may not be a perfect replica of the original string due to errors in the fragmentation and matching processes. Furthermore, for many strings unique reconstruction is inherently impossible. This represents a major issue for next generation sequencing technologies used in fundamental biological research, since in this setting it is impossible to ensure unambiguous results. The successful code designs pursued in this project can resolve reliability and content retrieval issues impeding implementations of emerging molecular computing and storage paradigms. This project is concerned with developing novel coding methods for unique reconstruction of strings or pools of strings based on their constituent substrings, subsequences and substring compositions. The techniques employed represent a combination of new graph-theoretic, combinatorial optimization and information theory approaches. In particular, the project will investigate the use of balanced partial de Bruijn strings for substring-based reconstruction, Catalan-like paths for multiset composition reconstruction as well as coded multi-trace reconstruction methods involving specialized modifications of deletion-correcting codes and superposition codes. The coding schemes will be tested on DNA-based and synthetic polymer-based data storage platforms under the development at the University of Illinois.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.

从碎片或碎片质量中重建文本字符串的问题在计算生物学中至关重要，因为当前的DNA和蛋白质测序平台无法读取表示蛋白质/基因序列的长字符串的内容。 DNA组装中出现了字符串重建的一个原型示例：在那里，一个人创建了相同长字符串的多个副本，并切割了副本以读取可以通过匹配其前缀和后缀来匹配的简短重叠子字符串。由于片段和匹配过程中的错误，重建的字符串可能不是原始字符串的完美复制品。此外，对于许多字符串而言，独特的重建本质上是不可能的。这代表了基本生物学研究中使用的下一代测序技术的一个主要问题，因为在这种情况下，不可能确保明确的结果。该项目中所追求的成功代码设计可以解决妨碍新兴分子计算和存储范式实现的可靠性和内容检索问题。该项目涉及开发新的编码方法，以基于其组成子字符串，子序列和子字符组成的独特重建字符串或字符串池。所采用的技术代表了新的图理论，组合优化和信息理论方法的组合。特别是，该项目将调查平衡的部分de Bruijn字符串用于基于基因线的重建，类似加泰罗尼亚的多层组合物重建的路径，以及编码的多条跟踪重建方法，涉及涉及删除验证代码和叠加代码的专业修改。编码方案将在伊利诺伊大学开发的基于DNA的基于DNA和基于合成聚合物的数据存储平台上进行测试。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点评估来支持的，并具有更广泛的影响。

项目成果

The Gapped k-Deck Problem

k-Deck 缺口问题

• 发表时间: 2022
• 期刊: International Symposium on Information Theory and its Applications
• 作者: Rebecca Golm, Mina Nahvi