Skip to main content

Semi-local LCS: A superglue for string comparison

Alexander Tiskin ( University of Warwick )

The computation of a longest common subsequence (LCS) between two strings is a classical algorithmic problem and a textbook application of dynamic programming. A generalisation of this problem, which we call semi-local LCS, asks for the LCS between a string and all substrings of another string, and/or the LCS between all prefixes of one string and all suffixes of another. This generalised problem turns out to be fundamental whenever a solution to the LCS problem has to be "glued together" from its solutions on substrings: for example, computing LCS of compressed strings; computing LCS in parallel; dynamic LCS support. In such cases, semi-local LCS can be used as an efficient alternative to dynamic programming, where the "gluing" procedure has an elegant description in the language of semigroup algebra. This approach to string comparison also turns out to have some unexpected connections with computational geometry, graph algorithms and comparison networks, as well as practical applications in computational molecular biology.

Speaker bio

Dr Alexander Tiskin graduated from St Petersburg University (Russia) in 1992, and obtained a DPhil in Computation from University of Oxford in 1999. Since 1999, he is associate professor at the Department of Computer Science, University of Warwick. Dr Tiskin's main research interests are string algorithms, parallel algorithms, discrete mathematics and combinatorial optimisation.

 

 

Share this: