Survey of Sequence Reconstruction Problems and Their Applications in DNA-Based Storage

In DNA sequencing, we often need to infer an unknown sequence from a collection of its corrupted copies. Each copy cannot faithfully tell the truth due to DNA fragmentation, point mutations, and measurement errors. The theoretical guarantee of unique reconstruction is thus of concern. This motivated the study of sequence reconstruction problems three decades ago. Recently, synthetic DNA has been regarded as an ultra-dense data storage medium. Sequence reconstruction is a crucial step in achieving reliable and efficient data readout. In this survey, we summarize mainly two types of problems, reconstruction from subsequences or substrings, in both combinatorial and probabilistic settings. Meanwhile, we discuss codes and algorithms that may assist with the future development of DNA-based data storage systems.