论文标题
计算生物学中的痕量重建问题
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.
