标题： 计算生物学中的迹重构问题 显示英文标题

标题： Trace Reconstruction Problems in Computational Biology

摘要： 从其有错误的副本中重建字符串的问题，即痕迹重建问题，是由 Vladimir Levenshtein 二十年前提出的。 尽管在痕迹重建方面已有大量理论工作，但实际解决方案仅在最近才开始出现在两个迅速发展的研究领域：免疫基因组学和 DNA 数据存储中。 在免疫基因组学中，痕迹对应于由适应性免疫系统自然产生的基因突变副本。 在 DNA 数据存储中，痕迹对应于编码数字数据的 DNA 分子的噪声副本，错误是数据检索过程中的产物。 在本文中，我们引入了若干新的痕迹生成模型以及与免疫基因组学和 DNA 数据存储相关的痕迹重建的新问题，综述了痕迹重建的理论结果，并强调了它们与计算生物学的联系。 在整个过程中，我们讨论了已知解决方案的适用性和不足之处，并提出了未来的研究方向。 显示英文摘要

摘要： The problem of reconstructing a string from its error-prone copies, the trace reconstruction problem, was introduced by Vladimir Levenshtein two decades ago. While there has been considerable theoretical work on trace reconstruction, practical solutions have only recently started to emerge in the context of two rapidly developing research areas: immunogenomics and DNA data storage. In immunogenomics, traces correspond to mutated copies of genes, with mutations generated naturally by the adaptive immune system. In DNA data storage, traces correspond to noisy copies of DNA molecules that encode digital data, with errors being artifacts of the data retrieval process. In this paper, we introduce several new trace generation models and open questions relevant to trace reconstruction for immunogenomics and DNA data storage, survey theoretical results on trace reconstruction, and highlight their connections to computational biology. Throughout, we discuss the applicability and shortcomings of known solutions and suggest future research directions.