Coding Solutions for Polymer-Based Data Storage

Prof. Olgica Milenkovic

University of Illinois, Urbana-Champaign

Meeting Details
Meeting Link: https://tum-conf.zoom.us/j/63350982282
Meeting ID: 633 5098 2282
Meeting Passcode: 604930

Abstract:

Molecular storage systems are ultradense information recorders that use DNA, proteins or polymers as storage media. By now, many efficient coding solutions are known for DNA-based platforms, but the unique challenges associated with reading information from other molecular media have not been properly addressed. To mitigate this problem, we introduce unique reconstruction and error-control codes for polymer-based data-storage. In polymer-based storage systems, binary information strings are represented by chains comprising two molecules of substantially different masses. Writing amounts to stitching the “molecular bits” together while reading is performed via tandem mass spectrometry. Mass spectrometers, roughly speaking, report noisy measurements of masses of collections of substrings of the binary string. Unique reconstruction codes ensure that each coded string can be uniquely recovered given the masses of all of its substrings. Mass spectrometry error-correction codes, on the other hand, offer both unique reconstruction properties as well as resilience to a fixed number of mass errors. We describe how to construct such codes using techniques developed for solving turnpike-type problems, Catalan paths and evaluation codes. We also consider the same problems applied to mixtures of strings, which are more practically relevant settings. In this case, we use Knuth-balancing type of arguments with new constructions for binary and nonbinary B_h sequences. Our results show that reconstruction and limited mass error-correction constraints incur negligible coding redundancy, while mixing strings results in coding rates that scale inversely proportional with the number of strings in the mixture.


This is joint work with Ryan Gabrys and Sri Pattabiraman.

Biography:

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. More recently, she organized a special issue of the IEEE Transactions on Information Theory in memory of V. I. Levenshtein.