Coded String Reconstruction Problems
Presenter(s)
Presenter Profile Picture
Olgica Milenkovic
University of Illinois Urbana-Champaign

IEEE ISIT 2020, Los Angeles (Virtual)
Plenary Lecture

Video image begins at 0:30

Date

Abstract

String reconstruction problems frequently arise in genomic data processing, molecular storage system implementations and synthetic biology. In the most general setting, the problems may be summarized as follows: one is given a single or multiple copies of a string. The copies are subsequently processed and transmitted through noise-inducing channels. The goal of the reconstruction method is to recover the original string or an approximation thereof using the noisy string information. Examples of string reconstruction questions include reconstruction from noisy traces, reconstruction from substrings and k-decks and reconstruction from substring composition sets. We review the above and related problems and then proceed to describe coding methods that lead to collections of strings that can be more accurately and efficiently reconstructed than their uncoded counterparts.