The Taub Faculty of Computer Science Events and Talks

Levenshtein's reconstruction model was first introduced in 2001 and suggests transmitting a word over multiple noisy channels, then using the channels' outputs to recover the transmitted word. This talk will discuss the reconstruction model when the channels are prone to combinations of errors, or when unique retrieval of the transmitted word is not guaranteed to succeed. In particular, when the channels introduce a limited number of insertions (or deletions), and unique decoding is not guaranteed to succeed, bounds on the largest list size will be presented. Furthermore, a recently proposed optimization to DNA synthesis using shortmers (i.e., sequences of bases) will be investigated from a theoretical point of view. This optimization differs from the conventional synthesis process by appending in each cycle not only single bases, but also shortmers. The significance of this optimization lies in reducing the number of cycles, which then determines the time and monetary cost of the synthesis process. Hence, the talk will discuss several questions pertaining to this optimization, such as which shortmers to use and how to calculate the minimum number of cycles.