Trace Reconstruction with Language Models
This addresses data retrieval errors in applications like DNA data storage, offering improved correction for technology-specific error patterns, though it appears incremental as it builds on prior deep learning approaches.
The paper tackles the trace reconstruction problem, which recovers original sequences from noisy copies with deletions, insertions, and substitutions, by proposing TReconLM, a method using language models, and it outperforms state-of-the-art algorithms by recovering a substantially higher fraction of sequences without error.
The general trace reconstruction problem seeks to recover an original sequence from its noisy copies independently corrupted by deletions, insertions, and substitutions. This problem arises in applications such as DNA data storage, a promising storage medium due to its high information density and longevity. However, errors introduced during DNA synthesis, storage, and sequencing require correction through algorithms and codes, with trace reconstruction often used as part of the data retrieval process. In this work, we propose TReconLM, which leverages language models trained on next-token prediction for trace reconstruction. We pretrain language models on synthetic data and fine-tune on real-world data to adapt to technology-specific error patterns. TReconLM outperforms state-of-the-art trace reconstruction algorithms, including prior deep learning approaches, recovering a substantially higher fraction of sequences without error.