Portal de Periódicos da CAPES

Trace Reconstruction Problems in Computational Biology

2020; Institute of Electrical and Electronics Engineers; Volume: 67; Issue: 6 Linguagem: Inglês

10.1109/tit.2020.3030569

1557-9654

Vinnu Bhardwaj, Pavel A. Pevzner, Cyrus Rashtchian, Yana Safonova,

Algorithms and Data Compression

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.