String reconstruction problems frequently arise in many areas of genomic data processing molecular storage, and synthetic biology. In the most general setting, they may be described as follows: one is given a single or multiple copies of a coded or uncoded string, and the copies are subsequently subjected to some form of (random) processing such as fragmentation or repeated transmission through a noise-inducing channel. The goal of the reconstruction method is to obtain an exact or approximate version of the string based on the processed outputs. Examples of string reconstruction questions include reconstruction from noisy traces, reconstruction from substrings and k-decks and reconstruction from compositional substring information. We review the above and some related problems and then proceed to describe coding methods that lead to strings that can be reconstructed exactly from their noisy traces, substrings and compositions. In particular, we focus on DNA profile codes, hybrid reconstruction from traces and uniquely reconstructable code designs. In the process, we introduce new questions in the areas of restricted de Bruin graphs, counting of rational points in polytopes, and string replacement methods.
This is a joint work with Ryan Gabrys, Han Mao Kiah, Srilakshmi Pattabiraman and Gregory Puleo.
Olgica Milenkovic is a professor of Electrical and Computer Engineering at the University of Illinois, Urbana-Champaign (UIUC), and Research Professor at the Coordinated Science Laboratory. She obtained her Masters Degree in Mathematics in 2001 and PhD in Electrical Engineering in 2002, both from the University of Michigan, Ann Arbor. Prof. Milenkovic heads a group focused on addressing unique interdisciplinary research challenges spanning the areas of algorithm design and computing, bioinformatics, coding theory, machine learning and signal processing. Her scholarly contributions have been recognized by multiple awards, including the NSF Faculty Early Career Development (CAREER) Award, the DARPA Young Faculty Award, the Dean's Excellence in Research Award, and several best paper awards. In 2013, she was elected a UIUC Center for Advanced Study Associate and Willett Scholar while in 2015 she was elected a Distinguished Lecturer of the Information Theory Society. In 2018 she became an IEEE Fellow. She has served as Associate Editor of the IEEE Transactions of Communications, the IEEE Transactions on Signal Processing, the IEEE Transactions on Information Theory and the IEEE Transactions on Molecular, Biological and Multi- Scale Communications. In 2009, she was the Guest Editor in Chief of a special issue of the IEEE Transactions on Information Theory on Molecular Biology and Neuroscience.