Semi-local LCS: A superglue for string comparison

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.