Trace Reconstruction Problems in Computational Biology

Autor:	Bhardwaj, Vinnu, Pevzner, Pavel A., Rashtchian, Cyrus, Safonova, Yana
Rok vydání:	2020
Předmět:	Computer Science - Computational Complexity Computer Science - Information Theory Computer Science - Machine Learning Quantitative Biology - Genomics F.2.3 G.3 E.4 J.2
Druh dokumentu:	Working Paper
Popis:	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. Comment: 20 pages, 8 figures. Accepted to the Special Issue of IEEE Transactions on Information Theory Dedicated to the Memory of Vladimir I. Levenshtein (copyright of journal version transferred to IEEE)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2010.06083 Zobrazit plný text záznamu View this record from Arxiv