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.