Edit distances, string alignments and dynamic programming

Speaker : Marc-Olivier Buob
Nokia Bell Labs France
Date: 03/02/2021
Time: 11:00 am - 12:00 pm


Edit distances quantify how dissimilar two strings are by counting the minimum number of edit operation (insertion, deletion, etc) to transform one string into the other. They are used in computer science (approximate string matching, file comparison, …), in bioinformatic (nucleic acid sequence alignment…), etc. This presentation presents the main edit distances (Longest Common Subsequence, Levenshtein, Hamming, …), and shows how to compute them using dynamic programming.

This presentation was prepared in collaboration with Maxime Raynal (Nokia Bell Labs France).