Time: 4.5.2021 at 13:00
Speaker: Alexander Tiskin, St Petersburg University
Title: The surprising algebra of string comparison
Abstract:We consider the classical Longest Common Subsequence (LCS) problem on a pair of strings, also known as the Sequence Alignment problem in bioinformatics. The textbook solution for this problem is based on dynamic programming, and seems to be the only possible. We will show that this is not the case: a suitably generalised version of the LCS problem can be solved efficiently by a divide-and-conquer algorithm. In this alternative solution, subproblems are combined using a seemingly unrelated structure, known as the Hecke (or “sticky braid”) monoid, which can be defined via tropical matrix multiplication, and bears a close resemblance with the classical braid group. Such an approach is not only of theoretical interest, but also allows us to obtain efficient algorithms for approximate pattern matching on compressed strings without decompression, parallel string comparison, the maximum clique problem on circle graphs, as well as some real-life bioinformatics problems.