AF: Medium: The Trace Reconstruction Problem

涉及信息传输和恢复的问题在计算机科学和许多相关领域中扮演着重要的角色。例如，编码理论领域研究如何巧妙地对消息进行编码，以便即使在消息受到噪声的某种破坏之后，潜在信息仍然可以恢复。虽然编码理论已经取得了巨大的成功和影响，但在许多现实世界中，噪声过程影响着信息的“野外”，而编码方案却无法应用。例如，给定一个可能发生突变或缺失的DNA序列，就没有机会使用编码理论的工具对该序列进行编码，因为它在自然界中以一种不受人类控制的方式发生。因此，需要一种技术来重建尚未被巧妙编码，但已被不同类型的噪声破坏的信息。一种特别具有挑战性的噪声类型是“删除噪声”，这意味着消息中的一些字符被删除，而不给出删除发生在哪里的指示。幸运的是，在许多这种情况下，很自然地假设存在多个受缺失困扰的数据的独立副本；例如，在生物环境中，一个给定的DNA序列可能有多个副本，其中缺失以不同的方式影响每个副本。本项目将研究在上述情况下执行重建的算法。该项目的另一个重要目标是宣传和外联活动。计划的活动包括关于重建问题的新的高级课程，通过研究合作培训研究生和博士后，通过研讨会演讲、调查文章和其他出版物传播研究成果，以及继续进行旨在提高更广泛人群对理论计算机科学的兴趣和认识的外联活动。更详细地说，研究小组将以他们的初步结果为基础，为痕迹重建问题开发新的算法，在这种情况下，可以获得因删除而损坏的数据的独立副本(这种被删除-损坏的数据串称为“痕迹”)，挑战是重建原始的未损坏的数据。他们将分析这个问题的许多不同的自然变量，这些变量是通过对删除过程的性质(低、中或高删除率、相关与不相关的删除等)、正在传输的数据类型(最差情况数据、平均情况数据等)以及成功重建的期望(完美重建与不同近似重建概念)进行不同假设而获得的。研究小组还将调查与删除噪声相关的新算法问题，包括上述问题的更具挑战性的版本，其中重建算法被给予来自多个不同源串的痕迹的混合，目标是重建源串的整个潜在的“群体”，而不仅仅是单个源串。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Problems that involve the transmission and recovery of information play an important role in computer science and many related areas. For example, the field of coding theory studies how to cleverly encode a message so that the underlying information can still be recovered even after the message has been subjected to some kind of corruption by noise. While coding theory has been hugely successful and influential, there are many real-world settings in which a noise process affects information "in the wild" where coding schemes cannot be applied. For example, given a DNA sequence that is subject to mutations or deletions, there is no opportunity to encode the sequence using tools of coding theory because it occurs in nature in a way that is not under human control. So, there is a need for techniques that can reconstruct information that has *not* been cleverly encoded, and yet has been corrupted with different types of noise. One particularly challenging type of noise is "deletion noise", meaning that some of the characters of the message are deleted with no indication being given as to where the deletions took place. Fortunately, in many scenarios of this sort it is natural to assume that multiple independent copies of the deletion-plagued data are available; for example, in a biological setting one might have many copies of a given DNA sequence where deletions have affected each copy in a different way. This project will study algorithms for performing reconstruction in scenarios such as the above. Another important goal of this project will be dissemination and outreach activities. Planned activities include new advanced courses on reconstruction problems, training graduate students and postdocs through research collaboration, disseminating research results through seminar talks, survey articles and other publications, and continuing ongoing outreach activities aimed at increasing interest in and awareness of theoretical computer science in a broader population.In more detail, the research team will build on their preliminary results to develop new algorithms for the trace-reconstruction problem, where independent copies of data corrupted by deletions (such a deletion-corrupted data string is known as a "trace") are available and the challenge is to reconstruct the original uncorrupted data. They will analyze a number of different natural variants of this problem, which are obtained by making different assumptions about the nature of the deletion process (low, intermediate, or high deletion rates, correlated versus uncorrelated deletions, and so on); the type of data that is being transmitted (worst-case data, average-case data, etc); and the desiderata for successful reconstruction (perfect reconstruction versus different notions of approximate reconstruction). The research team will also investigate new algorithmic problems related to deletion noise, including more challenging versions of the problem described above in which the reconstruction algorithm is given a mixture of traces from multiple different source strings and the goal is to reconstruct the entire underlying "population" of source strings rather than just a single source string.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.