Guest Editorial Special Issue: 'From Deletion-Correction to Graph Reconstruction: In Memory of Vladimir I. Levenshtein'

Autor: Gilles Zémor, Gyula O. H. Katona, János Körner, Andrew McGregor, Ryan Gabrys, Sihem Mesnager, Olgica Milenkovic, Lara Dolecek, Alexander Barg
Rok vydání: 2021
Předmět:
Zdroj: IEEE Transactions on Information Theory. 67:3187-3189
ISSN: 1557-9654
0018-9448
DOI: 10.1109/tit.2021.3072555
Popis: There are few mathematicians whose contributions go beyond named conjectures and theorems: Vladimir Iosifovich Levenshtein ( , 1935–2017) is one such true exception. During the five decades of his active research career, he enriched combinatorics, coding, and information theory with elegant problem formulations, ingenious algorithmic solutions, and highly original proof techniques. However, his work accomplished much more—it paved the way for the creation and advancement of new scientific disciplines, such as natural language processing, metagenomics, sequence alignment, and reference-based genome assembly, as well as DNA-based data storage, to name a few. A crucial concept behind sequence alignment algorithms used in phylogeny, comparative, and cancer genomics, as well as in natural language processing is the Levenshtein (edit) distance and its extension, termed the Damerau–Levenshtein distance between strings. The Levenshtein distance equals the smallest number of insertions, deletions, or substitutions required to convert one string into another. Levenshtein introduced this metric in 1965 [item 1) in the Appendix], followed by the notion of deletion and insertion error-correcting codes that have since been used in a myriad of systems presented with synchronization errors [items 1) and 2) in the Appendix]. Levenshtein’s work also inspired the introduction of the trace reconstruction problem [items 3) and 4) in the Appendix] which has since sparked substantial interest in the field of DNA-based data storage.
Databáze: OpenAIRE
Externí odkaz: