Trace Reconstruction Problems in Computational Biology
  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.
